为树状数据寻找更好的结构

Question

我有一个可扩展的树(在HTML页面中)：

+ Category 1
- Category 2
+ Subcategory 1
- Subcategory 2
|- Foo
|- Bar
|- Link 42

它由一个结构(在后端定义)表示：

class Demo {
static ImmutableList<Item> sample() {
return ImmutableList.of(
new Item("Category 1", ImmutableList.of(
new Item("Some link title", "resource_id_1"),
new Item("Another link title", "resource_id_2"))),
new Item("Category 2", ImmutableList.of(
new Item("Subategory 1", ImmutableList.of(
new Item("Another link title", "resource_id_3"))),
new Item("Subcategory 2", ImmutableList.of(
new Item("Foo", "resource_id_1"),
new Item("Bar", "resource_id_2"),
new Item("Link 42", "resource_id_42"))))));
}
}

Item定义如下：

public class Item {
private String readableName;
private String resourceId;
private ImmutableList<Item> children;
Item(String name, String resourceId) {
this.readableName = name;
this.resourceId = resourceId;
}
Item(String name, ImmutableList<Item> children) {
this.readableName = name;
this.children = children;
}
public String getReadableName() {
return readableName;
}
public String getResourceId() {
return resourceId;
}
public ImmutableList<Item> getChildren() {
return children;
}
}

resourceId可以有不同的可读名称，并且可以在整个结构中放置多次，但在当前类别/子类别中只能放置一次。

目前，当用户点击链接或写入URL时，会加载资源(例如链接Foo映射到/showResource?id=resource_id_1:uniqe_magic_id)，并展开树。它之所以能工作，只是因为有黑客攻击——前端会创建自己的结构副本，并在每个资源id(每个叶)上附加一些:uniqe_magic_id字符串，当向后端发送请求时，它会对神奇的部分进行条纹处理。:uniqe_magic_id仅由前端用于扩展上述树中的适当项目。对我来说，这似乎是一个巧妙的解决方案(我重构了这段代码，并删除了cleanId方法，我认为这不是必要的，但在向后端发送请求之前，它很神奇…)，我正在寻找更好的解决方案。

我可以修改前端和后端。我想到了一种带有节点的树，比如：

class Node {
Node next;
Node child;
String readableName;
String resourceId;
String someUniqueHash;
}

并使用CCD_ 7。

有没有更好的方法可以在不复制前端整个结构的情况下实现相同的结果？

Answer 1

对于您正在创建的菜单，断言Item的id在本地是唯一的，并且当将子项附加到每个项时，更新对父项的引用，怎么样？

这将允许您扩展url中关注的任何内容的子树，前端(假设为html)将动态导航向用户显示各种类别的菜单。

通过添加名为Menu的新类并使Menu中的children可变，可以通过工厂模式断言项的本地唯一性。

class Menu {
final HashMap<String, Item> items = new HashMap<String, Item>();
final List<Item> root = new ArrayList<Item>();
public Item createItem(String title, String id, Item parent) {
if (items.containsKey(id)) {
raise SomeRuntimeException();
}
final Item item = new Item(title, id, parent, this);
if (parent == null) {
root.add(item);
}
else {
parent.addChild(item);
}
items.put(id, item);
}
/* default to have no parent, these are root items. */
public Item createItem(String title, String id, Item parent) {
return addItem(title, id, null);
}
}

对Item类的一些修改。

class Item {
private final Menu menu;
private final Item parent;
private final List<Item> children = new ArrayList<Item>();
public Item(String name, String resourceId, Menu menu, Item parent) {
...
this.menu = menu;
this.parent = parent;
}
public Item addChild(String name, String resourceId) {
final Item item = this.menu.createItem(name, resourceId, this);
this.children.add(item);
return item;
}
}

现在，我牺牲了一些不可变性，因为我相信这种模式在处理错误时比提供一组嵌套列表更具表现力。

生成不可变菜单

如果不变性是的一个大问题，您可以始终将Menu和Item更改为接口，并实现复制原始Menu和Item的不可变变体，然后向Menu类添加一个copyImmutable方法，该方法将构建请求的结构。

class MenuBuilder {
/* ... contains all things previously declared in Menu ... */
Menu copyImmutable() {
ImmutableList<Item> root = ...
ImmutableMap<String, Item> items = ...
return new ImmutableMenu(root, items)
}
}

这意味着您递归地对所有Item执行相同的操作。

生成菜单的算法

1. 从菜单类中查找项目(处理潜在错误)
2. 将每个父项循环到该菜单，并记录路径采取
3. 当到达根节点时，将其存储为activeRoot
4. 从菜单按顺序迭代所有根节点并渲染它们。当点击activeRoot时，递归地渲染所有子项，但只输入在pathTake中注册的子项

我希望这描述了一个解决方案，它可能会给你解决问题的灵感！

Answer 2

在前端复制树是必要的，因为它代表了一个不同的概念：后端的树代表模型，而前端的树代表模型的视图。这是一个非常重要的区别：后端的树说要显示什么，而前端的树说如何显示。具体来说，前端知道树的哪些部分被扩展：后端不应该知道，因为不同用户的树节点的打开/关闭状态会不同。

也许你应该做的是明确职责分工。与其复制树并向其资源ID添加唯一标识符，不如为VisualItem创建一个单独的类，封装实际项目的ID，并拥有自己的唯一ID(唯一ID永远不会进入后端)：

class VisualItem {
String resourceId;
ImmutableList<VisualItem> children;
String uniqueId;    // Used only in the front end
boolean isExpanded; // Tells you if the subtree is expanded or not
// You can add more attributes here to avoid requesting the Item.
// For example, you could add a readableName here
}

确保ID唯一性的一种方法是使用UUID类：它提供了一个非常方便的randomUUID()方法，为您提供了唯一的标识符。

Answer 3

如果我理解正确，您正试图在只给定非唯一ID的情况下可靠地识别项目在树结构中的位置。

生成的URL是否为"永久链接"，即当树结构可能发生变化时，用户是否可以安全地将其添加到书签中，并在n年后返回？树的结构会改变吗？特别是，您是否会将资源移动到其他类别，但希望其旧链接将用户带到新位置？

如果是后者，您别无选择，只能为每个资源ID生成或指定一个唯一的标识符。您可以生成/使用UUID，或者让用户指定一个ID并让代码强制唯一性。

否则，您可以使用项目在树中的位置为您提供一个唯一的ID(因为树结构不会更改，或者如果资源在树中急剧移动，用户就不能依赖保存的指向未来工作的资源的链接)。

例如后者，给定一个树：

- A
|- Resource1
- B
+ X
+ Y
- Z
|- Resource1
|- Resource24

因此，可以根据每个项目在树中的位置及其非唯一资源标识符，为其分配一个复合资源ID服务器端。例如，"A/Resource1"one_answers"B/Z/Resource1"。

或者，如果您不想依赖于显示名称或在整个过程中分配ID，请使用每个类别在其父类别中的顺序位置，例如，"1/Resource1"(第一个类别，然后是Resource1)可以与"2/3/Resource1"(第二个类别，然后是其第三个子类别，然后为Resource1)区分开来。

这正是普通文件系统所做的：识别没有唯一名称的资源(文件/文件夹)，并为其提供一个唯一的项目路径。

(由于服务器端可以完成此分配-向Item添加一个Parent字段，然后添加一个简单的getUniqueResourceId()方法，该方法通过Parent链接在树上迭代以组成一个唯一路径+getResourceId(