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
- —
- 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.
← → step · R replay · Space pause
You will learn
- Spot the problem: code that asks with `instanceof` whether it holds a leaf or a group. (covered)
- Give leaves and groups one shared interface, `Entry`. (covered)
- Make a group delegate to its children and add up what they return. (covered)
- Spot the pattern in the DOM: `appendChild` takes one node or a `DocumentFragment` holding many. (covered)
- Know when a Composite is too much. (covered)