Von Datei des Pfades zu eindeutiger Datenstruktur

Question

Ich lese aus einer Datei eine Liste von Pfaden. Ich möchte sie in einer integrierten Java-Struktur speichern, die die Duplikate automatisch löschen kann. Durch Duplikate meine ich, wenn ich /usr/bin habe und dann /usr hinzufüge, muss der bin Ordner gelöscht werden, da er im Ordner usr "enthalten" ist. Ich lese die Datei sequenziell, damit ich nicht alle Daten zweimal überprüfen muss, wenn möglich.

Beispielcode:

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

Beispieldatei:

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

Erwartete Ausgabe:

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

Answer 1

Ein Baum-basierte Lösung (wahrscheinlich effiziente):

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

    } 

} 

-Test Richtigkeit zu überprüfen: http://ideone.com/cvqEVT

Diese Implementierung akzeptiert Windows- und Unix-Pfade, wenn sie auf einer beliebigen Plattform ausgeführt werden. Die von Database.getPathsList() zurückgegebenen Pfade verwenden weiterhin den Dateitrenner des Betriebssystems. Sie könnten dies ändern, indem Sie File.separator in Database.PathNode.listPaths (die letzte Zeile des echten Codes) ändern.

Answer 2

Eine einfache Lösung:

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 Umsetzung:

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

druckt:

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