percheros - Árbol de Java para representar el sistema de archivos(archivos/dir) de la lista de rutas

palo para loro

Question

Tengo una lista de caminos como este

/mnt/sdcard/folder1/a/b/file1
/mnt/sdcard/folder1/a/b/file2
/mnt/sdcard/folder1/a/b/file3
/mnt/sdcard/folder1/a/b/file4
/mnt/sdcard/folder1/a/b/file5
/mnt/sdcard/folder1/e/c/file6
/mnt/sdcard/folder2/d/file7
/mnt/sdcard/folder2/d/file8
/mnt/sdcard/file9

Entonces, de esta lista de rutas (Stings) necesito crear una estructura de árbol Java que tenga carpetas como nodos y archivos como hoja (no habrá carpetas vacías como hoja).

Lo que necesito, creo que es el método de agregar donde les paso una Cadena (ruta del archivo) y la agrego al lugar correcto en el árbol, creando nodos correctos (Carpeta) si aún no están allí.

Esta estructura de árbol necesitará que obtenga una lista de nodos cuando esté en un nodo y una lista de hojas (pero creo que esto será una característica normal de los árboles)

Siempre tendré cadenas como rutas y no archivos o carpetas reales. ¿Hay algo listo para usar o un código fuente para comenzar?

Muchas gracias.

Answer 1

Eche un vistazo en el nuevo paquete de Java 7 - nio2 . Todo lo que necesitas está dentro.

Answer 2

Gracias por toda su respuesta. Hice mi implementación de trabajo. Creo que necesitaré mejorarlo para que funcione mejor con más almacenamiento en caché al agregar elementos a la estructura de árbol.

Como dije, lo que necesitaba era una estructura que me permitiera tener una representación "virtual" de un FS.

MXMTree.java

public class MXMTree {

    MXMNode root;
    MXMNode commonRoot;

    public MXMTree( MXMNode root ) {
        this.root = root;
        commonRoot = null;
    }

    public void addElement( String elementValue ) { 
        String[] list = elementValue.split("/");

        // latest element of the list is the filename.extrension
        root.addElement(root.incrementalPath, list);

    }

    public void printTree() {
        //I move the tree common root to the current common root because I don''t mind about initial folder
        //that has only 1 child (and no leaf)
        getCommonRoot();
        commonRoot.printNode(0);
    }

    public MXMNode getCommonRoot() {
        if ( commonRoot != null)
            return commonRoot;
        else {
            MXMNode current = root;
            while ( current.leafs.size() <= 0 ) {
                current = current.childs.get(0);
            }
            commonRoot = current;
            return commonRoot;
        }

    }


}

MXMNode.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class MXMNode {

    List<MXMNode> childs;
    List<MXMNode> leafs;
    String data;
    String incrementalPath;

    public MXMNode( String nodeValue, String incrementalPath ) {
        childs = new ArrayList<MXMNode>();
        leafs = new ArrayList<MXMNode>();
        data = nodeValue;
        this. incrementalPath = incrementalPath;
    }

    public boolean isLeaf() {
        return childs.isEmpty() && leafs.isEmpty();
    }

    public void addElement(String currentPath, String[] list) {

        //Avoid first element that can be an empty string if you split a string that has a starting slash as /sd/card/
        while( list[0] == null || list[0].equals("") )
            list = Arrays.copyOfRange(list, 1, list.length);

        MXMNode currentChild = new MXMNode(list[0], currentPath+"/"+list[0]);
        if ( list.length == 1 ) {
            leafs.add( currentChild );
            return;
        } else {
            int index = childs.indexOf( currentChild );
            if ( index == -1 ) {
                childs.add( currentChild );
                currentChild.addElement(currentChild.incrementalPath, Arrays.copyOfRange(list, 1, list.length));
            } else {
                MXMNode nextChild = childs.get(index);
                nextChild.addElement(currentChild.incrementalPath, Arrays.copyOfRange(list, 1, list.length));
            }
        }
    }

    @Override
    public boolean equals(Object obj) {
        MXMNode cmpObj = (MXMNode)obj;
        return incrementalPath.equals( cmpObj.incrementalPath ) && data.equals( cmpObj.data );
    }

    public void printNode( int increment ) {
        for (int i = 0; i < increment; i++) {
            System.out.print(" ");
        }
        System.out.println(incrementalPath + (isLeaf() ? " -> " + data : "")  );
        for( MXMNode n: childs)
            n.printNode(increment+2);
        for( MXMNode n: leafs)
            n.printNode(increment+2);
    }

    @Override
    public String toString() {
        return data;
    }


}

Test.java para código de prueba

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {

        String slist[] = new String[] { 
                "/mnt/sdcard/folder1/a/b/file1.file", 
                "/mnt/sdcard/folder1/a/b/file2.file", 
                "/mnt/sdcard/folder1/a/b/file3.file", 
                "/mnt/sdcard/folder1/a/b/file4.file",
                "/mnt/sdcard/folder1/a/b/file5.file", 
                "/mnt/sdcard/folder1/e/c/file6.file", 
                "/mnt/sdcard/folder2/d/file7.file", 
                "/mnt/sdcard/folder2/d/file8.file", 
                "/mnt/sdcard/file9.file" 
        };

        MXMTree tree = new MXMTree(new MXMNode("root", "root"));
        for (String data : slist) {
            tree.addElement(data);
        }

        tree.printTree();
    }

}

Por favor, dime si tienes algún buen consejo sobre mejoras.

Answer 3

Parece que puedes adaptar un Trie / Radix Trie o un Binary Search Tree para trabajar en cualquier situación. Puede aumentar un Trie para almacenar "carpetas" como nodos internos (en lugar de caracteres como en un Trie normal) o puede aumentar un Árbol de búsqueda binario para almacenar "carpetas" como nodos internos (siempre que implementen una interfaz comparable) y "archivos" como nodos de hoja.

Mi implementación de esas estructuras está vinculada en el texto anterior.

Answer 4

Recomendaría leer sobre estructuras de datos , particularmente trees . En Java, puede representarlos creando una clase de nodo que tenga referencias a otros nodos. Por ejemplo:

public class Node {
    private Node[] children;
    /* snip other fields */
    public boolean isFile() {
         return children.count == 0;
    }
}

Obviamente, puede almacenar las referencias de sus nodos de todos modos, como arrays o colecciones funcionarán con árboles no binarios.

Dada su lista de archivos, puede leerlos y completar su estructura de árbol.

Answer 5

Yo mismo implementé una solución al desafío, está disponible como GitHubGist .

Estoy representando cada nodo de una jerarquía de sistema de archivos en un DirectoryNode. Un método helper createDirectoryTree (String [] filesystemList) crea un direcotry-tree.

Aquí está el ejemplo de uso, que se incluye en el GitHubGist .

final String[] list = new String[]{
  "/mnt/sdcard/folder1/a/b/file1.file",
  "/mnt/sdcard/folder1/a/b/file2.file",
  "/mnt/sdcard/folder1/a/b/file3.file",
  "/mnt/sdcard/folder1/a/b/file4.file",
  "/mnt/sdcard/folder1/a/b/file5.file",
  "/mnt/sdcard/folder1/e/c/file6.file",
  "/mnt/sdcard/folder2/d/file7.file",
  "/mnt/sdcard/folder2/d/file8.file",
  "/mnt/sdcard/file9.file"
};

final DirectoryNode directoryRootNode = createDirectoryTree(list);

System.out.println(directoryRootNode);

El System.out.println -output es:

  {value=''mnt'', children=[{value=''sdcard'', children=[{value=''folder1'', 
  children=[{value=''a'', children=[{value=''b'', children=[{value=''file1.file'', 
  children=[]}, {value=''file2.file'', children=[]}, {value=''file3.file'', 
  children=[]}, {value=''file4.file'', children=[]}, {value=''file5.file'', 
  children=[]}]}]}, {value=''e'', children=[{value=''c'', 
  children=[{value=''file6.file'', children=[]}]}]}]}, 
  {value=''folder2'', children=[{value=''d'', children=[{value=''file7.file'', 
  children=[]}, {value=''file8.file'', children=[]}]}]}, 
  {value=''file9.file'', children=[]}]}]}