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

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 ) 并且树被展开。它的工作只是因为一个 hack - 前端创建自己的结构副本，将一些 :uniqe_magic_id 字符串附加到每个资源 ID(每个叶子)，并且在向后端发送请求时，它会剥离魔法部分。 :uniqe_magic_id 仅供前端用于扩展上面显示的树中的适当项目。这对我来说似乎是一个巧妙的解决方案(我正在重构这段代码并删除了 cleanId 方法，我认为这不是必需的但在向后端发送请求之前剥离了魔法......)我正在寻找一个更好的。

我可以同时修改前端和后端。我想到了某种具有以下节点的树:

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

并使用someUniqueHash。

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

Answer 1

如何仅断言项目的 ID 对于您正在创建的菜单在本地是唯一的，并且当子级附加到每个项目时更新对父级的引用？

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

可以通过工厂模式断言项目的本地唯一性，方法是添加一个名为 Menu 的新类，并使 Menu 中的子级可变。

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 更改为接口(interface)并实现复制原始 Menu 和 Item 的不可变变体，然后添加一个 copyImmutable 方法将构建请求的结构的 Menu 类。

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

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

菜单生成算法

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

我希望本文描述的解决方案可能会给您带来解决问题的灵感!