Create object hierarchy with string prefixes

Question

I'm working on a project where a REST endpoint responds with a flat list of objects. These objects have a String name, a String shorthand and a String structure which contains all the parent shorthands separated by a comma ,. The structure property includes information of the parent-child relationship between the objects. Example structure="abc,abc_DEF,abc_DEF_persons". So, abc is a parent object, abc_DEF its child object, abc_DEF_persons the child of the child object.

Now my job is to restore the hierarchy in a Java-based service after receiving the list from the endpoint. They are received in no particular order.

response.json

[
 {
  "name": "Object1",   // parent
  "shorthand": "abc",
  "structure": null
 },
 {
  "name": "Object2",   // child of abc
  "shorthand": "abc_DEF",
  "structure": "abc"
 },
 {
  "name": "Object3",   // child of abc_DEF
  "shorthand": "abc_DEF_123",
  "structure": "abc,abc_DEF"
 },
 {
  "name": "Object4",   // child of abc_DEF
  "shorthand": "abc_DEF_456",
  "structure": "abc,abc_DEF"
 },
 {
  "name": "Object5",   // parent
  "shorthand": "xyz",
  "structure": null
 },
 {
  "name": "Object6",   // child of xyz
  "shorthand": "xyz_UVW",
  "structure": "xyz"
 },
 {
  "name": "Object7",   // child of xyz
  "shorthand": "xyz_RST",
  "structure": "xyz"
 }
]

Item.java

public class Item {
    public String name;
    public String shorthand;
    public String structure;
    public List<Item> items;

    public Item() {
    }

    public Item(String name, String shorthand, String structure, List<Item> items) {
        this.name = name;
        this.shorthand = shorthand;
        this.structure = structure;
        this.items= items;
    }
}

ItemService.java

   private createHierarchicalItems(List<Item> flatItems) {
        // Create generic root item
        Item root = new Item();

        // Sort items by length of structure (null first)
        flatItems.sort((a, b) -> {
             if(a.structure != null && b.structure != null) {
                 return a.structure.split(",").length - b.structure.split(",").length;
             }
             return (a.structure == null) ? -1 : 1;
        });

        // Iterate over the flatItems from the HTTP response
        for(Item flatItem of flatItems) {
            List<String> parentShorthands = new ArrayList<>();

            // If the structure property has content, create a list of parent shorthands
            if(flatItem.structre != null && flatItem.structure.length > 0) {
                parentShorthands = flatItem.structure.split(",");
            }
            
            buildTree(root, parentShortHands);      // TBD
        }
    }

My current approach is to create a tree structure by building it recursively, but I´m still struggling with the buildTree method.

expectedStructure.json

[
    {
        "name": "Object1",
        "shorthand": "abc",
        "structure": null,
        "categories": [
            {
                "name": "Object2",
                "shorthand": "abc_DEF",
                "structure": "abc",
                "categories": [
                    {
                        "name": "Object3",
                        "shorthand": "abc_DEF_123",
                        "structure": "abc,abc_DEF",
                        "categories": []
                    },
                    {
                        "name": "Object4",
                        "shorthand": "abc_DEF_456",
                        "structure": "abc,abc_DEF",
                        "categories": []
                    }
                ]
            }
        ]
    },
    {
        "name": "Object5",
        "shorthand": "xyz",
        "structure": null,
        "categories": [
            {
                "name": "Object6",
                "shorthand": "xyz_UVW",
                "structure": "xyz",
                "categories": []
            },
            {
                "name": "Object7",
                "shorthand": "xyz_RST",
                "structure": "xyz",
                "categories": []
            }
        ]
    }
]

Answer 1

Assuming that the last part of a structure is always the immediate parent, I was able to create the expected output with following code:

public class Test {

    public static void main(String[] args) {
        // mix up order of input
        List<Item> flatItems = new ArrayList<>();
        flatItems.add(new Item("Object2", "abc_DEF", "abc"));
        flatItems.add(new Item("Object3", "abc_DEF_123", "abc,abc_DEF"));
        flatItems.add(new Item("Object4", "abc_DEF_456", "abc,abc_DEF"));
        flatItems.add(new Item("Object1", "abc", null));
        flatItems.add(new Item("Object6", "xyz_UVW", "xyz"));
        flatItems.add(new Item("Object5", "xyz", null));
        flatItems.add(new Item("Object7", "xyz_RST", "xyz"));
        // sort items. Can also be done in createHierarchicalItems method
        flatItems
                .sort(Comparator.comparing(Item::getStructureLength, Comparator.nullsFirst(Comparator.naturalOrder())));

        List<Item> createHierarchicalItems = createHierarchicalItems(flatItems);
        printItems(createHierarchicalItems);

    }

    private static void printItems(List<Item> createHierarchicalItems) {
        //only used to structure printing
        for (Item item : createHierarchicalItems) {
            System.out.println(item);
            if (item.categories.size() > 0) {
                printItems(item.categories);
            }
        }
    }

    private static List<Item> createHierarchicalItems(List<Item> flatItems) {
        List<Item> parents = new ArrayList<>();

        for (Item flatItem : flatItems) {
            // check if the item is a parent item
            if (flatItem.structure == null)
                parents.add(flatItem);
            else {
                // if not a parent, search for immediate parent
                findImmediateParent(parents, flatItem);
            }
        }
        return parents;
    }

    private static void findImmediateParent(List<Item> parents, Item flatItem) {
        for (Item parent : parents)
            // check if the parent item is immediate parent, based on the fact that last item of structure is immediate parents shorthand
            if (parent.shorthand.equals(flatItem.structure.split(",")[flatItem.structure.split(",").length - 1])) {
                parent.addChild(flatItem);
            } else if (parent.categories.size() > 0) {
                // search for possible parents in children of current parent
                findImmediateParent(parent.categories, flatItem);
            }
    }

}

class Item {
    public String name;
    public String shorthand;
    public String structure;
    public List<Item> categories;

    public Item() {
    }
    // utility method to add a child item
    public void addChild(Item flatItem) {
        categories.add(flatItem);
    }

    public Item(String name, String shorthand, String structure) {
        this.name = name;
        this.shorthand = shorthand;
        this.structure = structure;
        categories = new ArrayList<>();
    }

    // used for sorting
    Integer getStructureLength() {
        return structure != null ? structure.split(",").length : null;
    }

    @Override
    public String toString() {
        return "Item [name=" + name + ", shorthand=" + shorthand + ", structure=" + structure + "]";
    }
}

Here is the output of the print:

Item [name=Object1, shorthand=abc, structure=null]
Item [name=Object2, shorthand=abc_DEF, structure=abc]
Item [name=Object3, shorthand=abc_DEF_123, structure=abc,abc_DEF]
Item [name=Object4, shorthand=abc_DEF_456, structure=abc,abc_DEF]
Item [name=Object5, shorthand=xyz, structure=null]
Item [name=Object6, shorthand=xyz_UVW, structure=xyz]
Item [name=Object7, shorthand=xyz_RST, structure=xyz]

and a look at the debugging view, making it clear which item has which children.

Answer 2

1. sort raw items by depth, ascending

2. loop over items and put them in map, key is the item path, in this case structure + shorthand

3. get the parent by key = item structure

4. add item to child list

   public class RawItem {

   public static class RawItemComparator implements Comparator<RawItem> {
   
       @Override
       public int compare(RawItem o1, RawItem o2) {
           int depth = null == o1.structure ? 0 : o1.structure.split(",").length;
           int otherDepth = null == o2.structure ? 0 : o2.structure.split(",").length;
   
           if(depth == otherDepth) {
               return 0;
           } else if(depth > otherDepth) {
               return 1;
           } else {
               return -1;
           }
       }
   
       @Override
       public boolean equals(Object obj) {
           return false;
       }
   }
   
   private final String name;
   private final String shorthand;
   private final String structure;
   
   @JsonCreator
   public RawItem(@JsonProperty("name") String name, @JsonProperty("shorthand") String shorthand, @JsonProperty("structure") String structure) {
       this.name = name;
       this.shorthand = shorthand;
       this.structure = structure;
   }
   
   public String getName() {
       return name;
   }
   
   public String getShorthand() {
       return shorthand;
   }
   
   public String getStructure() {
       return structure;
   }
   
   @Override
   public String toString() {
       return "RawItem{" +
               "name='" + name + '\'' +
               ", shorthand='" + shorthand + '\'' +
               ", structure='" + structure + '\'' +
               '}';
   }
   

   }

main class

public class Starter {

    public static void main(String[] args) throws IOException {

        Map<String, Item> itemMap = new HashMap<>();

        ObjectMapper mapper = new ObjectMapper();

        List<RawItem> items = Arrays.asList(mapper.readValue(mapper.getClass().getResourceAsStream("/data.json"), RawItem[].class));
        items.sort(new RawItem.RawItemComparator());

        items.forEach(item -> {
            Item parent = null == item.getStructure() ? null : itemMap.get(item.getStructure());

            Item current = new Item(item.getName(), item.getShorthand(), item.getStructure(), new ArrayList<>());
            if(parent != null) {
                parent.items.add(current);
            }

            itemMap.put(current.structure == null ? current.shorthand : current.structure + "," + current.shorthand, current);
        });
    }
}

Answer 3

Read the input into a List<Item> where the name, shorthand, and structure are populated and the items List is empty (but not null).

List<Item> itemList = readItemsFromFile(..);

Map these items using the shorthand as the key.

Map<String, Item> itemMap = mapItems(items);

At this point, all Items are in itemList and all Items are in itemMap. We want itemList to contain only the root objects (i.e. those with no parent) but to have all of the child objects appear in the parent.items List of their parent. To do this, we'll iterate over the itemList using an Iterator. For a given Item, if it has no structure then we skip it because it is a root Item. Otherwise, we identify the parent from the structure, fetch the parent from the itemMap, and add this Item to its parent.items List. Then invoke the iterator.remove() to pull this elements from itemList.

for (Iterator<Item> iterator = items.iterator() ; iterator.hasNext() ;) {
  Item item = iterator.next();
  if (null == item.getStructure()) {
    continue;
  }
  iterator.remove();
  String parentKey = identifyParent(item.getStructure());
  Item parent = itemMap.get(parentKey);
  Objects.requireNotNull(parent, "parentKey does not map to an Item "+parentKey);
  parent.getItems().add(item);
}

When this iteration is complete, the itemList elements will be the root Items, each populated with its children and the those children populated with their children, etc.

Answer 4

You will need to set the parent equal to 0 or -1 whatever you want in the database. Next, you will use a method to find all the parents (parent id equal to 0 or -1) and you'll create a list of arrays for each specific parent id. After creating the arraylist with the parents, you'll go and set the corresponding child in the specific arraylist. You can an int variable for setting the depth and etc.. you need two methods , one for finding the parents and one for creating the lists and recursive the method for searching for the childs and then setting them to the list , the hard part is to understand the second level and bellow of your literation. I hope it helps.