Из файла пути к уникальной структуре данных

Question

Я читаю из файла список путей. Я хочу сохранить их во встроенной структуре Java, которая может автоматически удалять дубликаты. Под дубликатами я имею в виду, если у меня есть /usr/bin а потом добавляю /usr bin папка должна быть удалена, потому что она "содержится" внутри usr папка. Я читаю файл последовательно, поэтому я предпочел бы не проверять все данные дважды, если это возможно.

Пример кода:

UnknownType<Path> database;
BufferedReader reader = new BufferedReader(new FileReader(new File("db.txt")));

String line;
while ((line = reader.readLine()) != null) {
    Path path = Paths.get(line).toRealPath();
    database.add(path);
}

Пример файла:

/usr/bin
/usr
/dev
/dev/sda1
/dev/sda2
/home/user/Desktop/file.txt
/home/user/Documents/file2.txt
/home/user/Documents/file3.txt

Ожидаемый результат:

data structure containing paths: 
/usr
/dev
/home/user/Desktop/file.txt
/home/user/Documents/file2.txt
/home/user/Documents/file3.txt

Answer 1

Основанное на дереве решение (возможно, более эффективное):

class Database {

  public void add(String p) {
    root.add(Arrays.asList(p.split("\\\\|/")), 0);
  }

  public void addAll(Collection<? extends String> list) {
    for (String p : list)
    add(p);
  }

  public List<String> getPathsList() {
    ArrayList<String> list = new ArrayList<>();
    root.listPaths(list, "");
    return list;
  }

  PathNode root = new PathNode("");

  static class PathNode {

    public final String name;
    public Map<String, PathNode> children = new HashMap<>();

    public PathNode(String name) {
      this.name = name;
    }

    public boolean isLeaf() {
      return children.size()==0;
    }

    public boolean isRoot() {
      return name.isEmpty();
    }

    public void add(List<String> path, int i) {
      String childName = path.get(i);
      PathNode child = children.get(childName);

      if (child != null) {
        if (path.size()-i <= 1) child.children.clear();
        else child.add(path, i+1);
      } else if (!isLeaf() || isRoot()) {
        PathNode node = this;
        for (; i < path.size(); i++) {
          String key = path.get(i);
          node.children.put(key, node = new PathNode(key));
        }
      }
    }

    public void listPaths(ArrayList<String> list, String prefix) {
      for (PathNode child : children.values()) {
        if (child.isLeaf()) list.add(prefix+child.name);
        else child.listPaths(list, prefix+child.name+File.separator);
      }
    }

  }

}

Тест для проверки правильности: http://ideone.com/cvqEVT

Эта реализация будет принимать пути Windows и Unix при работе на любой платформе. Пути, возвращаемые Database.getPathsList() все равно будет использовать разделитель файлов ОС; Вы можете изменить это, изменив File.separator в Database.PathNode.listPaths (последняя строка реального кода).

Answer 2

Простое решение:

class Database {

  public void add(Path p) {
    for (int i = 0; i < paths.size(); i++) {
      Path p2 = paths.get(i);
      if (p2.startsWith(p)) {
        // replace with new path
        paths.set(i, p);
        return;
      }
      if (p.startsWith(p2)) {
        // don't add this new one
        return;
      }
    }
    // else, add the new one
    paths.add(p);
  }

  ArrayList<Path> paths = new ArrayList<>();

}

LinkedList реализация:

class Database {

  public void add(Path p) {
    for (ListIterator<Path> it = paths.listIterator(0); it.hasNext();) {
      Path p2 = it.next();
      if (p2.startsWith(p)) {
        // replace with new path
        it.set(p);
        return;
      }
      if (p.startsWith(p2)) {
        // don't add this new one
        return;
      }
    }
    // else, add the new one
    paths.add(p);
  }

  LinkedList<Path> paths = new LinkedList<>();

}

Answer 3

static ArrayList<Path> paths = new ArrayList<Path>();

public static void main (String[]args) { 
    add(Paths.get("/usr/bin"));
    add(Paths.get("/usr"));
    add(Paths.get("/dev"));
    add(Paths.get("/dev/sda"));
    add(Paths.get("/home/user/Desktop/file.txt"));
    System.out.println(paths.toString());
} 

public static void add(Path path){
    // get root
    String firstDir = path.subpath(0, 1).toString();
    // check all known paths
    for (int q = 0; q < paths.size(); q++){
        Path p = paths.get(q);
        // get root of saved path
        String pFirstDir = p.subpath(0, 1).toString();

        // do they have the same root path
        if (pFirstDir.equals(firstDir)){
            // the new path needs to have less folders otherwise return
            if (path.getNameCount()>p.getNameCount()){
                return;
            }

            // set the new path and return
            paths.set(q, path);
            return;
        }
    }
    // no paths found taht match so add
    paths.add(path);
}

напечатает:

[\usr, \dev, \home\user\Desktop\file.txt]