Finding the best tree data structure

Question

I have an extensible tree (in an HTML page):

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

which is represented by a structure (defined in the backend):

 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")))))); } } 

with Item is defined as follows:

 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 can have different readable names and can be placed several times in a holistic structure, but only once in the current category / subcategory.

Currently, when users click a link to a link or , a resource is being loaded (for example, the Foo link is mapped to /showResource?id=resource_id_1:uniqe_magic_id ), and the tree expands. It only works because of a hack - the frontend creates its own copy of the structure, adding a line :uniqe_magic_id for each resource identifier (each sheet), and when sending a request to the backend, it will mark up the magic part. :uniqe_magic_id used only by the interface to extend the correct elements in the tree shown above. It seems to me that this was a smooth solution (I reviewed this code and deleted the cleanId method, which I did not need, but was an alternation of magic before sending a request for the backend ...), and I'm looking for the best one.

I can change the interface and backend. I was thinking of some kind of tree with nodes such as:

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

and using someUniqueHash .

Is there a better way to achieve the same result without copying the entire structure in the frontend?

Answer 1

As soon as you claim that the Item identifier is locally unique for the menu you are creating, and when children are added to each item update, a link to the parent?

This will allow you to expand the subtree of what is focused in the URL, the interface (assuming html) will dynamically navigate through the menu representing various categories to the user.

The local uniqueness of the elements can be confirmed using the factory template by adding a new class called "Menu" and making children in the Menu mutable.

 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); } } 

Some changes to the Item class.

 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; } } 

Now I have sacrificed some immutability, because I believe that this template is much more expressive in error handling than providing a set of nested lists.

Creating an immutable menu

If immutability is a big problem, you can always change the menu and item to interfaces and implement immutable options that copy the original menu and item, and then add the copyImmutable method to the Menu class, which will create the requested structure.

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

This means that you recursively do the same for all elements.

Menu Creation Algorithm

• Search for an item from a menu class (eliminating potential errors)
• Each parent iterates into this menu and pathTaken entry.
• When the root node user is reached, save it as activeRoot .
• Iterate all the root nodes according to the menu and visualize them. When you hit activeRoot, recurse all the children recursively, but enter only those that are registered in pathTaken .

I hope this describes a solution that can inspire you to solve your problem!

Answer 2

Making a copy of your tree at the front end is necessary because it means a different concept: while the tree at the back represents the model, the tree at the front represents the model. This is a very important difference: the tree in the back says what to show, while the tree in the front says how to display. In particular, the front part knows which parts of the tree will be expanded: the end should not know this, because the state of opening / closing of the tree nodes will be different for different users.

Perhaps you should make a clear separation of duties. Instead of making a copy of the tree and adding unique identifiers to its resource identifier, create a separate class for VisualItem , encapsulating the identifier of the actual element and having a unique identifier (a unique identifier will never be the back end):

 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 } 

One way to ensure unique identifiers is to use the UUID class : it provides a very convenient randomUUID() , giving you a unique identifier.

Answer 3

If I understand correctly, you are trying to reliably identify the position of a position in a tree structure, given only a non-unique identifier.

Are the permalinks URLs generated, i.e. can the user safely add them and return after n years when the tree structure could be changed? Will the tree structure change? In particular, do you move the resource to another category, but expect its old link to lead users to a new location?

If the latter , you have little alternative, but to create or specify a unique identifier for each resource identifier. You can generate / use a UUID or specify an identifier for the user and have a code that ensures uniqueness.

Otherwise, you can use the position of the element in the tree to give you a unique identifier (because either the tree structure does not change, or users cannot rely on a saved link to a resource that will work in the future if the resource moves sharply inside the tree).

For example, for the latter, given the tree:

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

Thus, each element can be assigned a group of composite resources of the ID server based on its position in the tree and its unique resource identifier. For example, "A / Resource1" and "B / Z / Resource1".

Or, if you do not want to rely on the display name or assign identifiers everywhere, use the ordinal position of each category in your parent, for example, "1 / Resource1" (1st category, then Resource1) can be distinguished from "2/3 / Resource1" ( second category, then her third child, then Resource1).

This is exactly what the vanilla file system does: it identifies resources (files / folders) that do not have unique names, given the unique path to the element.

(Since the server side can fulfill this assignment, add the parent field to the element, and then add the simple getUniqueResourceId () method, which iterates through the parent links to create a unique path + getResourceId () and pass this to the client, not for getResourceId () - no need to influence the external HTML interface.)