¿Cuál sería un buen enfoque para generar un árbol de carpetas?

7

Supongamos que tengo una serie de cadenas, como esta:

var folders = new[]
{
    "Foo",
    "Bar",
    "Foo\Bar"
    "Foo\Bar\Baz"
};

Y que tengo un objeto que representa una carpeta, algo como esto:

class Folder
{
    private readonly string _name;
    private readonly IEnumerable<Folder> _folders;

    public Folder(string name, IEnumerable<Folder> folders)
    {
        _name = name; 
        _folders = folders;
    }

    public string Name { get { return _name; } }
    public IEnumerable<Folder> Folders { get { return _folders; } }
}

¿Cuál sería una buena manera de terminar con una estructura de objetos como esta?

- Folder {Name:Foo}
  - Folder {Name:Bar}
    - Folder {Name:Baz}
- Folder {Name:Bar}

Estoy pensando esto en términos de dividir las cadenas en el delimitador y luego agrupar ... y estoy pensando que esto está mal, simplemente no tengo un enfoque para llegar allí, no va a ninguna parte. Tengo el presentimiento de que necesito involucrar recursión de alguna manera , pero no veo dónde encajar eso, estoy atascado.

El código de ejemplo anterior es C #, pero no necesito el código real, solo un pseudo-código , o una línea de pensamiento, una pequeña pista.

... Espero que esté dentro del alcance?

    
pregunta Mathieu Guindon 12.01.2016 - 23:53

3 respuestas

7

El siguiente algoritmo debería hacer casi lo que pediste.

paths : List<String>    ;; your list of paths
tree : Folder = NEW Folder("")
FOREACH path IN paths DO
    node : Folder = tree
    FOREACH component IN split(path, "/") DO
        next : Folder = node.getChild(component)
        IF next IS NULL THEN
            next := NEW Folder(component)
            node.addChild(next)
        FI
        node := next
    DONE
DONE

Estoy diciendo casi porque creará un directorio árbol bajo un nodo raíz común etiquetado con la cadena vacía (como / en los sistemas de archivos POSIX). Si no quieres esto, sino que tienes un bosque de árboles de directorios, deberías escribir una pequeña estructura de datos para contener los árboles del bosque. O sigue adelante y usa la raíz común y, después de construir el árbol, extrae sus nodos secundarios (los árboles) en una lista.

El ejemplo de código asume un método Folder::getChild que devolverá una referencia a un niño con ese nombre si existe o el puntero NULL. Por supuesto, se supone que Folder::addChild agrega otro niño Folder .

    
respondido por el 5gon12eder 13.01.2016 - 00:16
5

Supongamos que tiene un método adicional GetOrCreate(name) que devuelve una carpeta para un nombre dado, o lo crea si no existe tal carpeta, y que tiene una carpeta root que contiene toda su jerarquía. Luego, dada una lista de cadenas path , podemos implementar fácilmente una solución iterativa:

Folder current = root;
for (name in path)
  current = current.GetOrCreate(name);

Alternativamente, puedes definir un método recursivo MakePath(path) :

public void MakePath(names) {
  return if path is empty;
  GetOrCreate(path.First).MakePath(path.Rest);
}

La pregunta interesante es cómo podría funcionar GetOrCreate . Su problema es que está utilizando un IEnumerable<Folder> , donde realmente desea una estructura de datos asociativa (mapa, diccionario, tabla hash, como se llame en su idioma). Esto permite una fácil prueba de membresía y aplica la singularidad, no hay dos carpetas con el mismo padre que puedan compartir el mismo nombre.

La carpeta raíz sería otro problema en su diseño actual, ya que no tiene ningún nombre obvio (bueno, en Windows Land sería algo así como las letras de unidad, pero eso podría ser inútil en su aplicación). En su lugar, el nombre de childs podría ser una propiedad de la carpeta principal, no de las carpetas secundarias. El nombre está implícito como la clave en la tabla hash en lugar de una propiedad de objeto explícita. Esto evita la duplicación de datos, pero dificulta la respuesta a preguntas como "dada esta carpeta, ¿cuál es su nombre?". Por supuesto, ya es difícil responder "dada esta carpeta, ¿cuál es su ruta completa?", A menos que cada carpeta tenga un acceso fácil a su nombre y su principal.

    
respondido por el amon 13.01.2016 - 00:15
3

Si observa cómo el sistema de archivos maneja las carpetas dentro de su estructura, hay una diferencia vital que facilita el desplazamiento de las cosas y es el seguimiento de los elementos principales, así como las carpetas (y archivos).

En su caso, esto significa que debe hacer un seguimiento del padre de cualquier Folder dado, y tomar una decisión con respecto al nivel superior para tener una carpeta superior vacía, o dejar que la carpeta en el nivel superior tenga null como carpeta principal, permitiendo así que la carpeta esté al mismo nivel.

Esto significa que necesita un constructor que tome hasta tres parámetros:

  • name : el nombre de la carpeta actual, debe requerir un valor siempre
  • parent : enlace a la carpeta principal, preferiblemente una referencia débil para evitar una referencia circular fuerte que pueda arrojar a los recolectores de basura. Puede por defecto a null
  • folders : lista de subcarpetas, o null para indicar que aún no hay subcarpetas. Sin embargo, asegúrese de que el constructor cree una instancia adecuada de la lista de carpetas. Puede estar vacío, pero debería estar listo para agregar nuevas carpetas.

Con respecto a los métodos para esta clase, sugeriría al menos lo siguiente:

  • GetOrCreate(folderName) : busca en la lista de carpetas y, si no se encuentra, crea una nueva carpeta con self / this como principal. Devuelve este Folder recién creado
  • Opcionalmente AddPath(path) - Acepta una ruta completa, que se divide en los componentes de la carpeta. Comenzando en el nivel actual, haga un GetOrCreate() , cambie el nivel actual y repita para el siguiente componente de la carpeta.
  • GetFullPath() - Comenzando en el nivel actual, prepárese el nivel actual con todos los niveles principales para darle la ruta completa.

Si no implementa el AddPath() como un método separado, aún necesita hacer lo siguiente para la lista de rutas, y esto podría ser un método estático de su clase Folder() :

  • define tu nivel superior, es decir, tree = new Folder("")
  • para cada path en paths :
    • current = tree
    • para cada component en la división path
      • current = current.GetOrCreate(component, current.parent)

Espero que esto te ayude a comenzar.

    
respondido por el holroy 13.01.2016 - 01:13

Lea otras preguntas en las etiquetas