preface

Autolinked table refers to storing hierarchical data in the same table, which contains the unique key of the current node and the unique key field of the parent node. Usually we find a List from the database, sometimes we need to convert the back end into a structure like a tree.

The transformation method presented here has the following characteristics:

  1. The time complexity is n;
  2. Entity must contain node unique key, parent node unique key, and child node List collection (cannot be null, please initialize or change this method).
  3. Use Function to support generics. This method can be used to transform any entity object with self-linking form.
  4. Shallow clone, which affects the original data List collection.

Practical example

  • System Settings
    • Account management
      • User management
      • Role management
    • Parameter management
    • Timing task
  • Log management
    • Log on to log
    • The audit log

Data structure before and after conversion

Transformation before

[{"id": "1"."name": "System Settings"."pid": "999"."parentName": ""."child": []}, {"id": "101"."name": "Account Management"."pid": "1"."parentName": "System Settings"."child": []}, {"id": "10101"."name": "User Management"."pid": "101"."parentName": "Account Management"."child": []}, {"id": "10102"."name": "Role Management"."pid": "101"."parentName": "Account Management"."child": []}, {"id": "102"."name": "Parameter Management"."pid": "1"."parentName": "System Settings"."child": []}, {"id": "103"."name": "Scheduled task"."pid": "1"."parentName": "System Settings"."child": []}, {"id": "2"."name": "Log Management"."pid": "999"."parentName": ""."child": []}, {"id": "201"."name": "Login Log"."pid": "2"."parentName": "Log Management"."child": []}, {"id": "202"."name": "Audit Log"."pid": "2"."parentName": "Log Management"."child": []}]Copy the code

After the transformation

[{"id": "1"."name": "System Settings"."pid": "999"."parentName": ""."child": [{"id": "101"."name": "Account Management"."pid": "1"."parentName": "System Settings"."child": [{"id": "10101"."name": "User Management"."pid": "101"."parentName": "Account Management"."child": []}, {"id": "10102"."name": "Role Management"."pid": "101"."parentName": "Account Management"."child": []}]}, {"id": "102"."name": "Parameter Management"."pid": "1"."parentName": "System Settings"."child": []}, {"id": "103"."name": "Scheduled task"."pid": "1"."parentName": "System Settings"."child": []}]}, {"id": "2"."name": "Log Management"."pid": "999"."parentName": ""."child": [{"id": "201"."name": "Login Log"."pid": "2"."parentName": "Log Management"."child": []}, {"id": "202"."name": "Audit Log"."pid": "2"."parentName": "Log Management"."child": []}]}]Copy the code

code

@Data
@AllArgsConstructor
@NoArgsConstructor
class Menu {
    private String id;
    private String name;
    private String pid;
    private String parentName;
    private List<Menu> child;
}

// translate Method
/** * convert **@paramThe data data *@paramGetIdFunc method to get "node unique key" *@paramGetParentIdFunc Method to get the "unique key of the parent node" *@paramGetChildFunc Method to get a List of child nodes@returnList<T> Converted data */
public static <T> List<T> translate(List
       
         data, Function
        
          getIdFunc, Function
         
           getParentIdFunc, Function
          
           > getChildFunc)
          ,>
         ,>
        ,>
        {
    // List data to Map key->id, value->element
    Map<Object, T> idMap = data.stream().collect(Collectors.toMap(getIdFunc, t -> t));

    // put node into parent node's child list & mark node which has parent
    Set<Object> nodeIdWhichHasParent = new HashSet<>();
    for (T node : data) {
        Object parentId = getParentIdFunc.apply(node);
        T parentNode = idMap.get(parentId);
        if (null != parentNode) {
            getChildFunc.apply(parentNode).add(node);
            nodeIdWhichHasParent.add(getIdFunc.apply(node));
        }
    }

    // Map to result List
    List<T> result = new ArrayList<>();
    for (Map.Entry<Object, T> t : idMap.entrySet()) {
        if (!nodeIdWhichHasParent.contains(t.getKey())) {
            result.add(t.getValue());
        }
    }
    return result;
}

// Main
public static void main(String[] args) throws JsonProcessingException {
    List<Menu> menus = new ArrayList<>();
    menus.add(new Menu("1"."System Settings"."999"."".new ArrayList<>()));
    menus.add(new Menu("101"."Account Management"."1"."System Settings".new ArrayList<>()));
    menus.add(new Menu("10101"."User Management"."101"."Account Management".new ArrayList<>()));
    menus.add(new Menu("10102"."Role Management"."101"."Account Management".new ArrayList<>()));
    menus.add(new Menu("102"."Parameter Management"."1"."System Settings".new ArrayList<>()));
    menus.add(new Menu("103"."Scheduled task"."1"."System Settings".new ArrayList<>()));
    menus.add(new Menu("2"."Log Management"."999"."".new ArrayList<>()));
    menus.add(new Menu("201"."Login Log"."2"."Log Management".new ArrayList<>()));
    menus.add(new Menu("202"."Audit Log"."2"."Log Management".new ArrayList<>()));

    List<Menu> result = translate(menus, Menu::getId, Menu::getPid, Menu::getChild);
}

Copy the code