创建带有字符串前缀的对象层次结构

Question

我正在进行一个项目，其中REST端点使用一个平面对象列表进行响应。这些对象有一个String name、一个String shorthand和一个String structure，其中包含由逗号,分隔的所有父缩写。structure属性包含对象之间父-子关系的信息。例如structure="abc,abc_DEF,abc_DEF_persons"。因此，abc是父对象，abc_DEF是子对象，abc_DEF_persons是子对象的子对象。

现在，我的工作是在从端点接收到列表之后，恢复基于Java的服务中的层次结构。它们并不是按特定顺序收到的。

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

我目前的方法是通过递归构建树结构来创建树结构，但是我仍然在努力使用buildTree方法。

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

假设结构的最后一部分始终是直系亲属，我可以用以下代码创建预期的输出：

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 + "]";
    }
}

以下是打印的输出：

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]

并查看调试视图，明确哪个项具有哪个子项。

​

​

Answer 2

1. 按深度排序原始项，升序

1. 循环项目并将它们放到地图中，键是项路径，在本例中为结构+速记

。

1. 通过key = item structure

获取父级

1. 将项添加到子列表

公共类RawItem {

公共静态类RawItemComparator实现比较器{@覆盖公共int比较( RawItem o1，RawItem o2) { int深度=空== o1结构?0: o1.structure.split("，").length；int otherDepth =空== O2结构?0: o2.structure.split("，").length；if(深度== otherDepth) {返回0；}否则如果(深度> otherDepth) {返回1；}{返回-1；}}@覆盖公共布尔值=(对象obj) {返回false；}私有最终字符串名称；私有最终字符串速记；私有最终字符串结构；@JsonCreator公共字符串结构(@JsonProperty(“名称”)字符串名称，@JsonProperty(“速记”)字符串简写，@JsonProperty(“结构”)字符串结构){ this.name =名称；this.shorthand =速记；this.structure =结构；}公共字符串getName() {返回名称；}公共字符串getShorthand() {返回速记；}公共字符串getStructure() {返回结构；}@重写公共字符串toString() {返回"RawItem{“+ "name='”+名称+‘\’+ "，shorthand='“+速记+ '\'‘+，structure=’‘+结构+’+‘}；}

}

主班

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

将输入读入List<Item>，其中填充name、shorthand和structure，items列表为空(但不是null)。

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

使用shorthand作为键映射这些项。

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

此时，所有项目都在itemList中，所有项都在itemMap中。我们希望itemList只包含根对象(即那些没有父对象的对象)，但是将所有子对象显示在其父对象的parent.items列表中。为此，我们将使用一个itemList来迭代Iterator。对于给定的Item，如果它没有结构，那么我们跳过它，因为它是根项。否则，我们从结构中标识父项，从itemMap中获取父项，并将此项添加到其parent.items列表中。然后调用iterator.remove()从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);
}

当这个迭代完成后，itemList元素将是根Item，每个元素都填充了自己的子元素，以及由其子元素填充的子元素，等等。