Composite: trees of objects

  • Lesson 16 of 32
  • 10 min
  • Beginner
  • 11 steps

A function that works out the size of a folder and asks at every step «is this a file or a folder?». You will give both one shared interface and see what you gain and what you pay.

Functions to edit per new type
—
Exploreryour codeExplorersrc/ul · 3 lisrc/ · 200src/ · 240src/ · 200a.tslia.ts · 120a.ts · 120a.ts · 120lib/frag ·emptylib/ · 80lib/ · 120lib/ · 80b.tslib.ts · 80b.ts · 80b.ts · 80pack.ziplipack.zip ·40pack.zipEntryinterfaceEntryFileEntryFileEntryFolderFolderFileEntry or Folder?Explorer asks the typefunction 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;}new type: ZipFile3 functions to editWhat you have to touchgetSize()+ if ZipFileprintTree()+ if ZipFilefindBig()+ if ZipFileimplements EntryOne contract, two classesinterface Entry {size(): number;print(indent?: string): void;}class FileEntry implements Entry { … }class Folder implements Entry { … }a.size()leaf · 120The leafclass FileEntry implements Entry {constructor(private name: string,private bytes: number,) {}▸size() { return this.bytes; }}size() of each childThe group (excerpt)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 Bexample valuesnew type: ZipFileyour code does not changeA new type+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)One node or a groupconst frag = new DocumentFragment();frag.appendChild(li2);frag.appendChild(li3);▸ul.appendChild(frag); // moves bothul.children.length; // 3frag.childNodes.length; // 0no add()add() only hereTwo wrong ideas«every tree is a Composite»the key is the shared interface«the leaf needs add()»add() only on the groupevery size() walks it allWhen not to use itflat listan array is enoughleaf ≠ groupforced interfacebig treeO(n) per size()one interface, any levelComposite in one tableprobleminstanceof in every functionsolutionleaf and group, one interfacethe groupdelegates to its childrennew typeone class, 0 functions to editdo not use itwith a flat list
  • request
  • response

Step 1 of 11

Problem

A function that asks the type at every node

A file explorer shows how much space the src folder takes. Inside there is a file, a.ts, and another folder, lib, with b.ts in it.

getSize takes something and first asks: is it a FileEntry? If not, it assumes a Folder, walks its children and calls itself. The caller knows both classes and how the tree is built.

Step 2 of 11

Problem

A third kind of entry arrives

Now the explorer also shows .zip files, which count their size another way. ZipFile is born.

You have to open all three functions and add another branch to the if in each. Forget one and findBig treats the zip as a folder, looks for children and finds nothing.

What changed

  • ZipFile
  • getSize, printTree and findBig

Step 3 of 11

Concept

Leaves and groups with one interface

The idea of Composite: a file (the leaf) and a folder (the group) meet the same contract, Entry, with size() and print().

Both classes implement it (dashed line with a hollow triangle). So the caller works with «an Entry» and never needs to know which of the two it holds.

What changed

  • interface Entry

Step 4 of 11

Technique

The leaf answers on its own

FileEntry is the easy part: it keeps its name and its bytes, and size() returns those bytes. It has no children and does not know folders exist.

Ask for a.size() and the answer comes straight back: 120 in this example.

Step 5 of 11

Solution

The folder delegates to its children

Folder keeps a list of Entry, not of files or folders: of anything that meets the contract. Its size() asks each child for size() and adds up the answers.

The folder does not ask what each child is. If the child is another folder, it does the same with its own. print() works the same way: it prints itself and asks each child to print itself.

What changed

  • Folder.children: Entry[]
  • instanceof

Step 6 of 11

Technique

One call walks the whole tree

Your code calls src.size() once. src asks a.ts, which answers 120; then lib, which asks b.ts and answers 80.

src adds 120 + 80 = 200 and returns it. Nobody wrote a tree walk: the recursion comes for free because each folder delegates to its children.

Step 7 of 11

Solution

The new type, touching nobody

Back to ZipFile. With Composite it is one new class that implements Entry, and you put it in lib with add().

Folder does not change, and neither does your code: it still calls src.size(). Now lib is 80 + 40 = 120 and src is 120 + 120 = 240.

What changed

  • ZipFile

Step 8 of 11

Technique

The DOM is a Composite you already use

In the DOM, elements hold child nodes, and appendChild adds a node to a parent's children. A DocumentFragment is a group of nodes with no visible parent.

Pass a fragment to ul.appendChild and it moves all its contents into the list, leaving the fragment empty. The same call works for one node or for a group. React components nest the same way, through children.

Step 9 of 11

Concept

Not every tree is a Composite

Two common wrong ideas. Any tree is not a Composite: what defines the pattern is that leaves and groups share the interface, so the caller cannot tell them apart.

And the leaf does not need add(). It is safer to keep add() only on Folder: a file with an add() that fails at run time is worse than none. The price: to add children, you have to know you hold a folder.

Step 10 of 11

Trade-off

When a Composite is too much

If your data is a flat list, an array and a reduce are enough. It does not fit either when leaves and groups need very different operations: you end up with an interface full of methods half the classes cannot honour.

And watch out for big trees: every size() walks all the nodes below, O(n) per call. If you call it all the time, keep the total in the folder and update it when its children change.

Step 11 of 11

Summary

One interface for the leaf and the group

When your code asks «is this a leaf or a group?» to walk a tree, give both one shared interface. The group delegates to its children and the recursion comes for free.

A new type is a new class, without touching the caller. If the structure is flat, do not use it.

You will learn

  • Spot the problem: code that asks with `instanceof` whether it holds a leaf or a group.
  • Give leaves and groups one shared interface, `Entry`.
  • Make a group delegate to its children and add up what they return.
  • Spot the pattern in the DOM: `appendChild` takes one node or a `DocumentFragment` holding many.
  • Know when a Composite is too much.