TreeDirBuilder

gistfile1.txt

package interview;

import com.alibaba.fastjson.JSON;
import lombok.Data;

import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.*;

import static java.util.Comparator.comparing;
import static java.util.stream.Collectors.maxBy;
import static java.util.stream.Collectors.toList;

/**
 * <pre>
 * 面试题：
 * 输入路径列表：
 * /home/test
 * /home/test/data1
 *
 * /home/lab/express/
 * /home/lab/express/data2
 *
 * 转成一个TreeDir对象

 * TreeDir
 * - String path
 * - List<TreeDir> childs
 *
 * </pre>
 * Created by zhuguowei on 5/10/17.
 */
public class TreeDirBuilder {
    public static void main(String[] args) {
        List<String> pathList = new ArrayList<>();
        pathList.add("/home/test");
        pathList.add("/home/test/data1");

        pathList.add("/home/lab/express");
        pathList.add("/home/lab/express/data2");

        pathList.add("/home/foo");

        pathList.add("/usr/bin/");
        pathList.add("/usr/bin/xargs");

        TreeDir root = new TreeDirBuilder().parse(pathList);
        System.out.println(root);

        System.out.println(JSON.toJSONString(root));


    }

    public TreeDir parse(List<String> pathList){
        Map<Integer, Set<String>> level2PathMap = groupPathByLevel(pathList);
        Integer max = level2PathMap.entrySet().stream().collect(maxBy(comparing(e -> e.getKey()))).get().getKey();
        int level = 1;
        TreeDir root = new TreeDir("/");
        build(level,max,level2PathMap, root);
        return root;

    }

    private Map<Integer, Set<String>> groupPathByLevel(List<String> pathList) {
        Map<Integer, Set<String>> level2PathMap = new HashMap<>();
        for (String pathStr : pathList) {
            Path path = Paths.get(pathStr);
            int nameCount = path.getNameCount();
            for (int i = 0; i < nameCount; i++) {
                Path subpath = path.subpath(0, i + 1);
                level2PathMap.putIfAbsent(i + 1, new HashSet<>());
                level2PathMap.get(i + 1).add("/" + subpath);
            }

        }
        return level2PathMap;
    }

    private void build(int level,int max,Map<Integer,Set<String>> level2PathMap,TreeDir parent){
        if(level > max){
            return;
        }
        Set<String> paths = level2PathMap.get(level);
        for (String path : paths) {
            if(!path.startsWith(parent.getPath())){
                continue;
            }
            TreeDir current = new TreeDir(path);
            parent.addChild(current);
            build(level+1,max,level2PathMap,current);
        }
    }

    @Data
    static class TreeDir {
        private final String path;
        private List<TreeDir> childs;

        public void addChild(TreeDir treeDir) {
            if (this.childs == null) {
                this.childs = new ArrayList<>();
            }
            childs.add(treeDir);
        }
    }
}