Composite: árboles de objetos

  • Lección 16 de 32
  • 10 min
  • Inicial
  • 11 pasos

Una función que calcula el tamaño de una carpeta y pregunta en cada paso «¿esto es archivo o carpeta?». Vas a darles una interfaz común y ver qué ganas y qué pagas.

Funciones a editar por tipo nuevo
—
Explorertu códigoExplorersrc/ul · 3 lisrc/ · 200src/ · 240src/ · 200a.tslia.ts · 120a.ts · 120a.ts · 120lib/frag ·vacíolib/ · 80lib/ · 120lib/ · 80b.tslib.ts · 80b.ts · 80b.ts · 80pack.ziplipack.zip ·40pack.zipEntryinterfaceEntryFileEntryFileEntryFolderFolder¿FileEntry o Folder?Explorer pregunta el tipofunction getSize(e: FileEntry | Folder) {▸if (e instanceof FileEntry)return e.bytes;let sum = 0;for (const c of e.children)sum += getSize(c);return sum;}tipo nuevo: ZipFile3 funciones a editarDónde hay que tocargetSize()+ if ZipFileprintTree()+ if ZipFilefindBig()+ if ZipFileimplementa EntryUn contrato, dos clasesinterface Entry {size(): number;print(indent?: string): void;}class FileEntry implements Entry { … }class Folder implements Entry { … }a.size()hoja · 120La hojaclass FileEntry implements Entry {constructor(private name: string,private bytes: number,) {}▸size() { return this.bytes; }}size() de cada hijoEl grupo (extracto)class Folder implements Entry {private children: Entry[] = [];add(e: Entry) { this.children.push(e); }size() {return this.children.reduce(▸(s, c) => s + c.size(), 0);}}src.size() → 200src.size()src/200 Ba.ts120 Blib/80 Bb.ts80 Bvalores de ejemplotipo nuevo: ZipFiletu código no cambiaUn tipo nuevo+class ZipFile implements Entry {+constructor(private bytes: number) {}+size() { return this.bytes; }+print() { console.log("pack.zip"); }+}+lib.add(new ZipFile(40));src.size(); // 240ul.appendChild(frag)Un nodo o un grupoconst frag = new DocumentFragment();frag.appendChild(li2);frag.appendChild(li3);▸ul.appendChild(frag); // mueve los 2ul.children.length; // 3frag.childNodes.length; // 0sin add()add() solo aquíDos ideas equivocadas«todo árbol es un Composite»la clave es la interfaz común«la hoja necesita add()»add() solo en el grupocada size() recorre todoCuándo no usarlolista planaun array bastahoja ≠ grupointerfaz forzadaárbol grandeO(n) por size()una interfaz, cualquier nivelComposite en una tablaproblemainstanceof en cada funciónsoluciónhoja y grupo con una interfazel grupodelega en sus hijostipo nuevouna clase, 0 funciones a editarno lo usescon una lista plana
  • petición
  • respuesta

Paso 1 de 11

Problema

Una función que pregunta el tipo en cada nodo

Un explorador de archivos muestra cuánto ocupa la carpeta src. Dentro hay un archivo, a.ts, y otra carpeta, lib, con b.ts adentro.

getSize recibe algo y lo primero que hace es preguntar: ¿es un FileEntry? Si no, asume que es un Folder, recorre sus hijos y se llama a sí misma. Quien llama conoce las dos clases y sabe cómo se arma el árbol.

Paso 2 de 11

Problema

Llega un tercer tipo de entrada

Ahora el explorador también muestra archivos .zip, que cuentan su tamaño de otra forma. Nace ZipFile.

Hay que abrir las tres funciones y añadir otra rama al if en cada una. Si olvidas una, findBig trata el zip como una carpeta, busca children y no encuentra nada.

Qué cambió

  • ZipFile
  • getSize, printTree y findBig

Paso 3 de 11

Concepto

Hojas y grupos con la misma interfaz

La idea de Composite: un archivo (la hoja) y una carpeta (el grupo) cumplen el mismo contrato, Entry, con size() y print().

Las dos clases lo implementan (línea discontinua con triángulo hueco). Así quien llama trabaja con «un Entry» y nunca necesita saber cuál de los dos tiene.

Qué cambió

  • interface Entry

Paso 4 de 11

Técnica

La hoja responde sola

FileEntry es la parte fácil: guarda su nombre y sus bytes, y size() devuelve esos bytes. No tiene hijos ni sabe que existen las carpetas.

Si pides a.size(), la respuesta llega directo: 120 en este ejemplo.

Paso 5 de 11

Solución

La carpeta delega en sus hijos

Folder guarda una lista de Entry, no de archivos ni de carpetas: de cualquier cosa que cumpla el contrato. Su size() le pide size() a cada hijo y suma lo que responden.

La carpeta no pregunta qué es cada hijo. Si el hijo es otra carpeta, esa hará lo mismo con los suyos. print() funciona igual: se imprime y le pide a cada hijo que se imprima.

Qué cambió

  • Folder.children: Entry[]
  • instanceof

Paso 6 de 11

Técnica

Una llamada recorre todo el árbol

Tu código llama src.size() una vez. src le pregunta a a.ts, que responde 120; luego a lib, que le pregunta a b.ts y responde 80.

src suma 120 + 80 = 200 y te lo devuelve. Nadie escribió un recorrido del árbol: la recursión sale sola porque cada carpeta delega en sus hijos.

Paso 7 de 11

Solución

El tipo nuevo, sin tocar a nadie

Volvemos a ZipFile. Con Composite es una clase nueva que implementa Entry, y la metes en lib con add().

Folder no cambia, y tu código tampoco: sigue llamando src.size(). Ahora lib vale 80 + 40 = 120 y src vale 120 + 120 = 240.

Qué cambió

  • ZipFile

Paso 8 de 11

Técnica

El DOM es un Composite que ya usas

En el DOM, los elementos contienen nodos hijos, y appendChild añade un nodo a los hijos de un padre. Un DocumentFragment es un grupo de nodos sin padre visible.

Si a ul.appendChild le pasas un fragmento, mueve todo su contenido a la lista y el fragmento queda vacío. La misma llamada sirve para un nodo o para un grupo. Los componentes de React se anidan igual, a través de children.

Paso 9 de 11

Concepto

No todo árbol es un Composite

Dos ideas equivocadas comunes. Un árbol cualquiera no es un Composite: lo que define el patrón es que hojas y grupos compartan la interfaz, para que quien llama no los distinga.

Y la hoja no necesita add(). Es más seguro dejar add() solo en Folder: un archivo con un add() que falla en tiempo de ejecución es peor que no tenerlo. El precio: para añadir hijos, tienes que saber que tienes una carpeta.

Paso 10 de 11

Compromiso

Cuándo un Composite sobra

Si tus datos son una lista plana, un array y un reduce bastan. Tampoco encaja si hojas y grupos necesitan operaciones muy distintas: terminas con una interfaz llena de métodos que la mitad de las clases no sabe cumplir.

Y cuidado con los árboles grandes: cada size() recorre todos los nodos que hay debajo, O(n) por llamada. Si lo llamas a cada rato, guarda el total en la carpeta y actualízalo cuando cambian sus hijos.

Paso 11 de 11

Resumen

Una interfaz para la hoja y para el grupo

Cuando tu código pregunta «¿es una hoja o un grupo?» para recorrer un árbol, dale a los dos una interfaz común. El grupo delega en sus hijos y la recursión sale sola.

Un tipo nuevo es una clase nueva, sin tocar a quien llama. Si la estructura es plana, no lo uses.

Aprenderás

  • Reconocer el problema: código que pregunta con `instanceof` si tiene una hoja o un grupo.
  • Dar a hojas y grupos una misma interfaz, `Entry`.
  • Hacer que un grupo delegue en sus hijos y sume lo que responden.
  • Reconocer el patrón en el DOM: `appendChild` acepta un nodo o un `DocumentFragment` con varios.
  • Saber cuándo un Composite sobra.