A tree of parts that you treat as one part. Ask a single item or a whole cart the same question, and each answers in its own way.
Open a food app and look at the menu. It has sections (wraps, drinks), the sections have items, and some items are really combos: a wrap and a lassi for 20 rupees less than the two separately. Then a family feast turns up, which is a combo that contains a combo. Put it all in a cart and the app must answer two plain questions: how much is this, and how many items are in it? And it must answer them the same way whether "this" is a tea, a combo or the whole cart.
The Composite pattern is the answer: a group and a single thing share one interface, so a group is built from things that may themselves be groups, and the caller never asks which it is. This lesson builds a menu in Python, Java, C++ and JavaScript, then does the part that decides whether you can explain it: where the add method lives (the safety-versus-transparency trade-off), what stops a tree from containing itself, and what a parent pointer costs you. Two case studies use it: the in-memory file system, whose Directory holds Nodes that may be directories, and the text editor, whose Compound command is made of commands.
Every box answers one question: what is your price? A hamper asks the boxes inside it, so hampers hold hampers and the cashier never asks the kind.
The first version: an if-ladder for every operation#
The first menu is one Node class with a kind tag, because that is the quickest way to hold items, combos and categories in one tree. Every operation then asks the tag:
# first_version.py: a menu as one Node with a kind tag, and one if-ladder per operation
class Node:
def __init__(self, kind, name, price=0, off=0, children=None):
self.kind, self.name, self.price, self.off = kind, name, price, off
self.children = children or []
def total(node): # what would it cost to order everything under this node?
if node.kind == "item":
return node.price
elif node.kind == "combo":
return sum(total(c) for c in node.children) - node.off
elif node.kind == "category":
return sum(total(c) for c in node.children)
def count(node): # how many items are under this node?
if node.kind == "item":
return 1
elif node.kind == "category":
return sum(count(c) for c in node.children)
return 0 # the combo branch was never written, so a combo counts as nothing
def show(node, depth=0):
pad = " " * depth
if node.kind == "item":
print(f"{pad}{node.name} {node.price}")
elif node.kind == "combo":
print(f"{pad}{node.name} ({node.off} off)")
for c in node.children:
show(c, depth + 1)
elif node.kind == "category":
print(f"{pad}{node.name}")
for c in node.children:
show(c, depth + 1)
combo = Node("combo", "Wrap + Lassi", off=20, children=[Node("item", "Paneer wrap", 150), Node("item", "Lassi", 60)])
wraps = Node("category", "Wraps", children=[Node("item", "Paneer wrap", 150), Node("item", "Egg wrap", 130), combo])
show(wraps)
print(f"total {total(wraps)}")
print(f"count {count(wraps)}")// FirstVersion.java: a menu as one Node with a kind tag, and one if-ladder per operation
import java.util.ArrayList;
import java.util.List;
class FirstVersion {
static final class Node {
final String kind, name;
final int price, off;
final List<Node> children = new ArrayList<>();
Node(String kind, String name, int price, int off, Node... children) {
this.kind = kind;
this.name = name;
this.price = price;
this.off = off;
this.children.addAll(List.of(children));
}
}
static int total(Node node) { // what would it cost to order everything under this node?
if (node.kind.equals("item")) {
return node.price;
} else if (node.kind.equals("combo")) {
return node.children.stream().mapToInt(FirstVersion::total).sum() - node.off;
} else if (node.kind.equals("category")) {
return node.children.stream().mapToInt(FirstVersion::total).sum();
}
throw new IllegalStateException(node.kind);
}
static int count(Node node) { // how many items are under this node?
if (node.kind.equals("item")) {
return 1;
} else if (node.kind.equals("category")) {
return node.children.stream().mapToInt(FirstVersion::count).sum();
}
return 0; // the combo branch was never written, so a combo counts as nothing
}
static void show(Node node, int depth) {
String pad = " ".repeat(depth);
if (node.kind.equals("item")) {
System.out.println(pad + node.name + " " + node.price);
} else if (node.kind.equals("combo")) {
System.out.println(pad + node.name + " (" + node.off + " off)");
for (Node c : node.children) show(c, depth + 1);
} else if (node.kind.equals("category")) {
System.out.println(pad + node.name);
for (Node c : node.children) show(c, depth + 1);
}
}
public static void main(String[] args) {
Node combo = new Node("combo", "Wrap + Lassi", 0, 20, new Node("item", "Paneer wrap", 150, 0), new Node("item", "Lassi", 60, 0));
Node wraps = new Node("category", "Wraps", 0, 0, new Node("item", "Paneer wrap", 150, 0), new Node("item", "Egg wrap", 130, 0), combo);
show(wraps, 0);
System.out.println("total " + total(wraps));
System.out.println("count " + count(wraps));
}
}// first_version.cpp: a menu as one Node with a kind tag, and one if-ladder per operation
#include <iostream>
#include <string>
#include <vector>
struct Node {
std::string kind, name;
int price = 0, off = 0;
std::vector<Node> children;
};
int total(const Node& node) { // what would it cost to order everything under this node?
int sum = 0;
if (node.kind == "item") {
return node.price;
} else if (node.kind == "combo") {
for (const Node& c : node.children) sum += total(c);
return sum - node.off;
} else if (node.kind == "category") {
for (const Node& c : node.children) sum += total(c);
return sum;
}
return 0;
}
int count(const Node& node) { // how many items are under this node?
if (node.kind == "item") {
return 1;
} else if (node.kind == "category") {
int sum = 0;
for (const Node& c : node.children) sum += count(c);
return sum;
}
return 0; // the combo branch was never written, so a combo counts as nothing
}
void show(const Node& node, int depth) {
std::string pad(depth * 2, ' ');
if (node.kind == "item") {
std::cout << pad << node.name << " " << node.price << "\n";
} else {
std::cout << pad << node.name;
if (node.kind == "combo") std::cout << " (" << node.off << " off)";
std::cout << "\n";
for (const Node& c : node.children) show(c, depth + 1);
}
}
int main() {
Node combo{"combo", "Wrap + Lassi", 0, 20, {{"item", "Paneer wrap", 150, 0, {}}, {"item", "Lassi", 60, 0, {}}}};
Node wraps{"category", "Wraps", 0, 0, {{"item", "Paneer wrap", 150, 0, {}}, {"item", "Egg wrap", 130, 0, {}}, combo}};
show(wraps, 0);
std::cout << "total " << total(wraps) << "\n";
std::cout << "count " << count(wraps) << "\n";
}// firstVersion.js: a menu as one Node with a kind tag, and one if-ladder per operation
class Node {
constructor(kind, name, price = 0, off = 0, children = []) {
Object.assign(this, { kind, name, price, off, children });
}
}
function total(node) { // what would it cost to order everything under this node?
if (node.kind === "item") {
return node.price;
} else if (node.kind === "combo") {
return node.children.reduce((sum, c) => sum + total(c), 0) - node.off;
} else if (node.kind === "category") {
return node.children.reduce((sum, c) => sum + total(c), 0);
}
}
function count(node) { // how many items are under this node?
if (node.kind === "item") {
return 1;
} else if (node.kind === "category") {
return node.children.reduce((sum, c) => sum + count(c), 0);
}
return 0; // the combo branch was never written, so a combo counts as nothing
}
function show(node, depth = 0) {
const pad = " ".repeat(depth);
if (node.kind === "item") {
console.log(`${pad}${node.name} ${node.price}`);
} else if (node.kind === "combo") {
console.log(`${pad}${node.name} (${node.off} off)`);
node.children.forEach((c) => show(c, depth + 1));
} else if (node.kind === "category") {
console.log(`${pad}${node.name}`);
node.children.forEach((c) => show(c, depth + 1));
}
}
const combo = new Node("combo", "Wrap + Lassi", 0, 20, [new Node("item", "Paneer wrap", 150), new Node("item", "Lassi", 60)]);
const wraps = new Node("category", "Wraps", 0, 0, [new Node("item", "Paneer wrap", 150), new Node("item", "Egg wrap", 130), combo]);
show(wraps);
console.log(`total ${total(wraps)}`);
console.log(`count ${count(wraps)}`);Wraps
Paneer wrap 150
Egg wrap 130
Wrap + Lassi (20 off)
Paneer wrap 150
Lassi 60
total 470
count 2Read the numbers by hand. The category holds a paneer wrap (150), an egg wrap (130) and a combo. The combo is a paneer wrap and a lassi, 150 + 60, less 20 off, so 190. The total is 150 + 130 + 190 = 470, and total has a branch for every kind, so it is right. But the printed tree shows 4 items (paneer wrap, egg wrap, and the combo's paneer wrap and lassi), and count says 2. It has a branch for items and one for categories, and the combo falls through to the last line, return 0. Nothing crashed and nothing was logged. The count is wrong because a function that branches on kinds must be edited every time a kind is added, and one of three functions was missed.
- Every operation repeats the ladder. Three operations and three kinds make 9 branches to write and keep in step. Here 8 exist.
- A new kind edits every function. A "bundle" or a "voucher" node means a new branch in
total,countandshow, and a function you forget is wrong silently. - The fall-through hides the miss. The last line says "anything else is nothing", so an unhandled kind looks like a valid answer.
- The node is a bag of fields.
offmeans something only for combos andpriceonly for items, and nothing stops a category from having a price.
Before the refactor: which part changes?
All three functions walk the same tree, and every new kind of node means editing all of them. What should vary, and what should stay put?
One strong answer
The part that varies is what one node does for each question. The walk is the same every time. Move each question onto the node: an item answers price() with its own price, and a group answers it by asking each child the same thing and adding the answers. The caller then asks one question of any node and never looks at the kind. That is Composite.
The pattern#
The book that named it (Design Patterns, 1994, by Gamma, Helm, Johnson and Vlissides) states the intent of Composite as: "Compose objects into tree structures to represent part-whole hierarchies. Composite lets clients treat individual objects and compositions of objects uniformly."
| Role | In the menu code | Its one job |
|---|---|---|
| Component | MenuNode |
The interface every node has: price, count, show. The client only knows this |
| Leaf | Item |
A node with no children. Does the work itself (its own price, one item) |
| Composite | Group |
A node that holds other MenuNodes, and answers each question by asking them the same one and combining the answers |
| Client | describe, the cart screen |
Calls the interface on any node, and never asks which kind it is |
%% title: Composite: a group is a node that holds nodes, so the tree can be any depth
classDiagram
class MenuNode {
<<interface>>
+name str
+price() int
+count() int
+show(depth)
}
class Item {
-cost int
}
class Group {
-off int
+add(child) Group
}
class Client
MenuNode <|.. Item : implements
MenuNode <|.. Group : implements
Group o-- "0..*" MenuNode : children
Client --> MenuNode : price, countRead the arrows. Item and Group both implement MenuNode, so anything that holds a MenuNode can hold either. The arrow from Group back to MenuNode is the whole pattern: a group's children are the interface type, so a child can be another group, and so on to any depth. The client has one arrow, to the interface. It has none to Item or Group.
The client asks the interface, never the kind. Item and Group both implement MenuNode, and a Group holds MenuNodes, so the tree can be any depth.
The code: one question, any depth#
Here is the refactor in all four languages. A leaf answers a question itself. A group answers it by asking every child the same question and combining the answers (sum, and take off the combo discount). describe is the client, and it takes any MenuNode:
# composite.py: leaf and group share one interface, so a client treats a tea and a whole cart alike
from abc import ABC, abstractmethod
class MenuNode(ABC): # the component: what every node can do
def __init__(self, name: str) -> None:
self.name = name
@abstractmethod
def price(self) -> int: ...
@abstractmethod
def count(self) -> int: ...
@abstractmethod
def show(self, depth: int = 0) -> None: ...
class Item(MenuNode): # the leaf: no children, so no add()
def __init__(self, name: str, cost: int) -> None:
super().__init__(name)
self.cost = cost
def price(self) -> int:
return self.cost
def count(self) -> int:
return 1
def show(self, depth: int = 0) -> None:
print(f"{' ' * depth}{self.name} {self.cost}")
class Group(MenuNode): # the composite: holds MenuNodes, which may be groups
def __init__(self, name: str, off: int = 0) -> None:
super().__init__(name)
self.off, self.children = off, []
def add(self, child: MenuNode) -> "Group":
self.children.append(child)
return self
def price(self) -> int:
return sum(c.price() for c in self.children) - self.off
def count(self) -> int:
return sum(c.count() for c in self.children)
def show(self, depth: int = 0) -> None:
print(f"{' ' * depth}{self.name}" + (f" ({self.off} off)" if self.off else ""))
for c in self.children:
c.show(depth + 1)
def describe(node: MenuNode) -> None: # one function for a leaf, a combo or a cart
print(f"{node.name}: price {node.price()}, items {node.count()}")
tea = Item("Tea", 30)
combo = Group("Wrap + Lassi", 20).add(Item("Paneer wrap", 150)).add(Item("Lassi", 60))
wraps = Group("Wraps").add(Item("Paneer wrap", 150)).add(Item("Egg wrap", 130)).add(combo)
drinks = Group("Drinks").add(Item("Lassi", 60)).add(tea)
Group("Menu").add(wraps).add(drinks).show()
for node in (tea, combo, wraps):
describe(node)
feast = Group("Family feast", 30).add(Group("Wrap + Lassi", 20).add(Item("Paneer wrap", 150)).add(Item("Lassi", 60)))
feast.add(Item("Egg wrap", 130)).add(Item("Brownie", 80))
cart = Group("Cart").add(Item("Tea", 30)).add(feast)
cart.show()
describe(cart)// Composite.java: leaf and group share one interface, so a client treats a tea and a whole cart alike
import java.util.ArrayList;
import java.util.List;
class Composite {
interface MenuNode { // the component: what every node can do
String name();
int price();
int count();
void show(int depth);
}
record Item(String name, int cost) implements MenuNode { // the leaf: no children, so no add()
public int price() { return cost; }
public int count() { return 1; }
public void show(int depth) { System.out.println(" ".repeat(depth) + name + " " + cost); }
}
static final class Group implements MenuNode { // the composite: holds MenuNodes, which may be groups
private final String name;
private final int off;
private final List<MenuNode> children = new ArrayList<>();
Group(String name, int off) {
this.name = name;
this.off = off;
}
Group(String name) { this(name, 0); }
Group add(MenuNode child) {
children.add(child);
return this;
}
public String name() { return name; }
public int price() { return children.stream().mapToInt(MenuNode::price).sum() - off; }
public int count() { return children.stream().mapToInt(MenuNode::count).sum(); }
public void show(int depth) {
System.out.println(" ".repeat(depth) + name + (off > 0 ? " (" + off + " off)" : ""));
for (MenuNode c : children) c.show(depth + 1);
}
}
static void describe(MenuNode node) { // one function for a leaf, a combo or a cart
System.out.println(node.name() + ": price " + node.price() + ", items " + node.count());
}
public static void main(String[] args) {
Item tea = new Item("Tea", 30);
Group combo = new Group("Wrap + Lassi", 20).add(new Item("Paneer wrap", 150)).add(new Item("Lassi", 60));
Group wraps = new Group("Wraps").add(new Item("Paneer wrap", 150)).add(new Item("Egg wrap", 130)).add(combo);
Group drinks = new Group("Drinks").add(new Item("Lassi", 60)).add(tea);
new Group("Menu").add(wraps).add(drinks).show(0);
for (MenuNode node : List.of(tea, combo, wraps)) describe(node);
Group feast = new Group("Family feast", 30).add(new Group("Wrap + Lassi", 20).add(new Item("Paneer wrap", 150)).add(new Item("Lassi", 60)));
feast.add(new Item("Egg wrap", 130)).add(new Item("Brownie", 80));
Group cart = new Group("Cart").add(new Item("Tea", 30)).add(feast);
cart.show(0);
describe(cart);
}
}// composite.cpp: leaf and group share one interface, so a client treats a tea and a whole cart alike
#include <iostream>
#include <memory>
#include <string>
#include <utility>
#include <vector>
class MenuNode { // the component: what every node can do
public:
explicit MenuNode(std::string name) : name_(std::move(name)) {}
virtual ~MenuNode() = default;
const std::string& name() const { return name_; }
virtual int price() const = 0;
virtual int count() const = 0;
virtual void show(int depth) const = 0;
private:
std::string name_;
};
class Item : public MenuNode { // the leaf: no children, so no add()
public:
Item(std::string name, int cost) : MenuNode(std::move(name)), cost_(cost) {}
int price() const override { return cost_; }
int count() const override { return 1; }
void show(int depth) const override { std::cout << std::string(depth * 2, ' ') << name() << " " << cost_ << "\n"; }
private:
int cost_;
};
class Group : public MenuNode { // the composite: holds MenuNodes, which may be groups
public:
explicit Group(std::string name, int off = 0) : MenuNode(std::move(name)), off_(off) {}
Group& add(std::unique_ptr<MenuNode> child) {
children_.push_back(std::move(child));
return *this;
}
int price() const override {
int sum = 0;
for (const auto& c : children_) sum += c->price();
return sum - off_;
}
int count() const override {
int sum = 0;
for (const auto& c : children_) sum += c->count();
return sum;
}
void show(int depth) const override {
std::cout << std::string(depth * 2, ' ') << name();
if (off_ > 0) std::cout << " (" << off_ << " off)";
std::cout << "\n";
for (const auto& c : children_) c->show(depth + 1);
}
private:
int off_;
std::vector<std::unique_ptr<MenuNode>> children_;
};
std::unique_ptr<MenuNode> item(const std::string& name, int cost) { return std::make_unique<Item>(name, cost); }
void describe(const MenuNode& node) { // one function for a leaf, a combo or a cart
std::cout << node.name() << ": price " << node.price() << ", items " << node.count() << "\n";
}
int main() {
auto tea = item("Tea", 30);
const MenuNode& tea_ref = *tea; // the group below takes ownership; the object stays where it is
auto combo = std::make_unique<Group>("Wrap + Lassi", 20);
combo->add(item("Paneer wrap", 150)).add(item("Lassi", 60));
const MenuNode& combo_ref = *combo;
auto wraps = std::make_unique<Group>("Wraps");
wraps->add(item("Paneer wrap", 150)).add(item("Egg wrap", 130)).add(std::move(combo));
const MenuNode& wraps_ref = *wraps;
auto drinks = std::make_unique<Group>("Drinks");
drinks->add(item("Lassi", 60)).add(std::move(tea));
Group menu("Menu");
menu.add(std::move(wraps)).add(std::move(drinks));
menu.show(0);
for (const MenuNode* node : {&tea_ref, &combo_ref, &wraps_ref}) describe(*node);
auto inner = std::make_unique<Group>("Wrap + Lassi", 20);
inner->add(item("Paneer wrap", 150)).add(item("Lassi", 60));
auto feast = std::make_unique<Group>("Family feast", 30);
feast->add(std::move(inner)).add(item("Egg wrap", 130)).add(item("Brownie", 80));
Group cart("Cart");
cart.add(item("Tea", 30)).add(std::move(feast));
cart.show(0);
describe(cart);
}// composite.js: leaf and group share one interface, so a client treats a tea and a whole cart alike
class Item { // the leaf: no children, so no add()
constructor(name, cost) {
this.name = name;
this.cost = cost;
}
price() { return this.cost; }
count() { return 1; }
show(depth = 0) { console.log(`${" ".repeat(depth)}${this.name} ${this.cost}`); }
}
class Group { // the composite: holds nodes, which may be groups
constructor(name, off = 0) {
this.name = name;
this.off = off;
this.children = [];
}
add(child) {
this.children.push(child);
return this;
}
price() { return this.children.reduce((sum, c) => sum + c.price(), 0) - this.off; }
count() { return this.children.reduce((sum, c) => sum + c.count(), 0); }
show(depth = 0) {
console.log(" ".repeat(depth) + this.name + (this.off > 0 ? ` (${this.off} off)` : ""));
this.children.forEach((c) => c.show(depth + 1));
}
}
function describe(node) { // one function for a leaf, a combo or a cart
console.log(`${node.name}: price ${node.price()}, items ${node.count()}`);
}
const tea = new Item("Tea", 30);
const combo = new Group("Wrap + Lassi", 20).add(new Item("Paneer wrap", 150)).add(new Item("Lassi", 60));
const wraps = new Group("Wraps").add(new Item("Paneer wrap", 150)).add(new Item("Egg wrap", 130)).add(combo);
const drinks = new Group("Drinks").add(new Item("Lassi", 60)).add(tea);
new Group("Menu").add(wraps).add(drinks).show();
for (const node of [tea, combo, wraps]) describe(node);
const feast = new Group("Family feast", 30).add(new Group("Wrap + Lassi", 20).add(new Item("Paneer wrap", 150)).add(new Item("Lassi", 60)));
feast.add(new Item("Egg wrap", 130)).add(new Item("Brownie", 80));
const cart = new Group("Cart").add(new Item("Tea", 30)).add(feast);
cart.show();
describe(cart);Menu
Wraps
Paneer wrap 150
Egg wrap 130
Wrap + Lassi (20 off)
Paneer wrap 150
Lassi 60
Drinks
Lassi 60
Tea 30
Tea: price 30, items 1
Wrap + Lassi: price 190, items 2
Wraps: price 470, items 4
Cart
Tea 30
Family feast (30 off)
Wrap + Lassi (20 off)
Paneer wrap 150
Lassi 60
Egg wrap 130
Brownie 80
Cart: price 400, items 5Check the cart by hand. The tea is 30. The family feast holds the wrap and lassi combo (150 + 60 − 20 = 190), an egg wrap (130) and a brownie (80), which is 400, less its own 30 off: 370. The cart is 30 + 370 = 400. The items are 1 (tea) + 2 (combo) + 1 (egg wrap) + 1 (brownie) = 5. And the Wraps line, 470 with 4 items, is the number the first version got wrong: count is now right because there is no combo branch to forget. A combo is a Group with an off, and Group.count already adds up whatever it holds.
Look at what is missing: no if on a kind, and no kind tag. Adding a new kind of node (a voucher that takes 50 off) means one new class with its three methods, and describe, Group and the cart screen are not edited. What each language brings:
- Python needs no shared base class for this: a duck-typed
ItemandGroupwould work too. The abstract base is there so a type checker and a reader see the contract, and so that forgettingcountis an error at construction. - Java makes
MenuNodean interface andItemarecord, so a leaf is three lines. A type error is caught at compile time, which matters in the next section. - C++ gives the group
std::unique_ptr<MenuNode>children, so the tree owns its nodes and deletes them with itself. The base class needs a virtual destructor, or deleting a group through aMenuNodepointer is undefined behaviour. - JavaScript has no interface keyword, so the contract is "an object with
price,countandshow". The browser's DOM is a composite you already use: an element and a text node are both aNode, and an element holds more of them.
One call on the cart asks the tea and the family feast, which asks its combo. The answers come back up: 400 rupees and 5 items.
Where do add and remove live?#
There is one design question the pattern leaves to you, and interviewers ask it: which classes have add and remove? The book calls the trade-off transparency against safety.
Safe: only the group has add
- A leaf has no
add, so adding to it is a compile-time error in Java and C++, an error from a type checker such as mypy or TypeScript, and only a run-time error without one - The leaf's interface is honest: it has exactly what a leaf can do
- But a client holding a
MenuNodecan't add to it, because the interface has noadd: it needs a type check or a cast to reach the group
Transparent: every node has add
- Every node has the same interface, so a client treats leaf and group uniformly, including for child management
- A leaf has to do something with
add: refuse it with an exception, or ignore it - The mistake of adding to a leaf moves from compile time to run time
The code above is the safe design: add is only on Group, and Item has none. The book says it emphasises transparency over safety, because the point of the pattern is that the client never asks the kind. Neither is wrong. Safe suits code where whoever builds the tree knows the groups (a menu built from a config file); transparent suits code that receives a node and must add to it without knowing what it is (a UI toolkit, a document model). The two real examples disagree: Java's java.awt.Container extends Component and holds add(Component), so a plain Component can't take a child (safe), while the DOM's Node.appendChild exists on every node, and calling it on a text node throws a HierarchyRequestError (transparent).
The second program makes the other choice, and adds the two guards a real tree needs:
# transparent.py: add() is on every node (a leaf refuses it), and a group guards against cycles and a second parent
class Node:
def __init__(self, name: str) -> None:
self.name, self.parent = name, None
def add(self, child: "Node") -> None: # transparent: every node has add(), so a leaf must refuse
raise TypeError(f"{self.name} cannot hold children")
def remove(self, child: "Node") -> None:
raise TypeError(f"{self.name} cannot hold children")
def path(self) -> str: # the parent pointer makes this a walk upwards
return self.name if self.parent is None else f"{self.parent.path()} > {self.name}"
def price(self) -> int:
raise NotImplementedError
class Item(Node):
def __init__(self, name: str, cost: int) -> None:
super().__init__(name)
self.cost = cost
def price(self) -> int:
return self.cost
class Group(Node):
def __init__(self, name: str) -> None:
super().__init__(name)
self.children = []
def add(self, child: Node) -> None:
node = self
while node is not None: # the child must not be this group or any group above it
if node is child:
raise ValueError(f"cycle: {self.name} cannot contain {child.name}")
node = node.parent
if child.parent is not None: # one parent only: move it with remove() first
raise ValueError(f"{child.name} is already in {child.parent.name}")
child.parent = self
self.children.append(child)
def remove(self, child: Node) -> None:
self.children.remove(child)
child.parent = None
def price(self) -> int:
return sum(c.price() for c in self.children)
def attempt(action) -> None:
try:
action()
except (TypeError, ValueError) as e:
print(f"refused: {e}")
menu, wraps, combos = Group("Menu"), Group("Wraps"), Group("Combos")
paneer, egg = Item("Paneer wrap", 150), Item("Egg wrap", 130)
menu.add(wraps)
menu.add(combos)
wraps.add(paneer)
wraps.add(egg)
print(f"path: {paneer.path()}")
attempt(lambda: egg.add(paneer))
attempt(lambda: combos.add(paneer))
attempt(lambda: wraps.add(wraps))
attempt(lambda: wraps.add(menu))
wraps.remove(paneer)
combos.add(paneer)
print(f"path: {paneer.path()}")
print(f"menu price {menu.price()}")// Transparent.java: add() is on every node (a leaf refuses it), and a group guards against cycles and a second parent
import java.util.ArrayList;
import java.util.List;
class Transparent {
static abstract class Node {
final String name;
Group parent;
Node(String name) { this.name = name; }
void add(Node child) { throw new UnsupportedOperationException(name + " cannot hold children"); } // transparent: a leaf must refuse
void remove(Node child) { throw new UnsupportedOperationException(name + " cannot hold children"); }
String path() { return parent == null ? name : parent.path() + " > " + name; } // the parent pointer makes this a walk upwards
abstract int price();
}
static final class Item extends Node {
private final int cost;
Item(String name, int cost) {
super(name);
this.cost = cost;
}
int price() { return cost; }
}
static final class Group extends Node {
private final List<Node> children = new ArrayList<>();
Group(String name) { super(name); }
@Override
void add(Node child) {
for (Node node = this; node != null; node = node.parent) { // the child must not be this group or any group above it
if (node == child) throw new IllegalArgumentException("cycle: " + name + " cannot contain " + child.name);
}
if (child.parent != null) throw new IllegalArgumentException(child.name + " is already in " + child.parent.name); // one parent only
child.parent = this;
children.add(child);
}
@Override
void remove(Node child) {
children.remove(child);
child.parent = null;
}
int price() { return children.stream().mapToInt(Node::price).sum(); }
}
static void attempt(Runnable action) {
try {
action.run();
} catch (RuntimeException e) {
System.out.println("refused: " + e.getMessage());
}
}
public static void main(String[] args) {
Group menu = new Group("Menu"), wraps = new Group("Wraps"), combos = new Group("Combos");
Item paneer = new Item("Paneer wrap", 150), egg = new Item("Egg wrap", 130);
menu.add(wraps);
menu.add(combos);
wraps.add(paneer);
wraps.add(egg);
System.out.println("path: " + paneer.path());
attempt(() -> egg.add(paneer));
attempt(() -> combos.add(paneer));
attempt(() -> wraps.add(wraps));
attempt(() -> wraps.add(menu));
wraps.remove(paneer);
combos.add(paneer);
System.out.println("path: " + paneer.path());
System.out.println("menu price " + menu.price());
}
}// transparent.cpp: add() is on every node (a leaf refuses it), and a group guards against cycles and a second parent
#include <algorithm>
#include <functional>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
class Group;
class Node {
public:
explicit Node(std::string name) : name_(std::move(name)) {}
virtual ~Node() = default;
const std::string& name() const { return name_; }
Group* parent() const { return parent_; }
virtual void add(Node&) { throw std::logic_error(name_ + " cannot hold children"); } // transparent: a leaf must refuse
virtual void remove(Node&) { throw std::logic_error(name_ + " cannot hold children"); }
virtual int price() const = 0;
std::string path() const; // the parent pointer makes this a walk upwards
protected:
friend class Group;
Group* parent_ = nullptr;
private:
std::string name_;
};
class Item : public Node {
public:
Item(std::string name, int cost) : Node(std::move(name)), cost_(cost) {}
int price() const override { return cost_; }
private:
int cost_;
};
class Group : public Node { // children are owned by the caller here; the group only points at them
public:
explicit Group(std::string name) : Node(std::move(name)) {}
void add(Node& child) override {
for (const Node* node = this; node != nullptr; node = node->parent()) { // the child must not be this group or any group above it
if (node == &child) throw std::invalid_argument("cycle: " + name() + " cannot contain " + child.name());
}
if (child.parent() != nullptr) throw std::invalid_argument(child.name() + " is already in " + child.parent()->name()); // one parent only
child.parent_ = this;
children_.push_back(&child);
}
void remove(Node& child) override {
children_.erase(std::remove(children_.begin(), children_.end(), &child), children_.end());
child.parent_ = nullptr;
}
int price() const override {
int sum = 0;
for (const Node* c : children_) sum += c->price();
return sum;
}
private:
std::vector<Node*> children_;
};
std::string Node::path() const { return parent_ == nullptr ? name_ : parent_->path() + " > " + name_; }
void attempt(const std::function<void()>& action) {
try {
action();
} catch (const std::exception& e) {
std::cout << "refused: " << e.what() << "\n";
}
}
int main() {
Group menu("Menu"), wraps("Wraps"), combos("Combos");
Item paneer("Paneer wrap", 150), egg("Egg wrap", 130);
menu.add(wraps);
menu.add(combos);
wraps.add(paneer);
wraps.add(egg);
std::cout << "path: " << paneer.path() << "\n";
attempt([&] { egg.add(paneer); });
attempt([&] { combos.add(paneer); });
attempt([&] { wraps.add(wraps); });
attempt([&] { wraps.add(menu); });
wraps.remove(paneer);
combos.add(paneer);
std::cout << "path: " << paneer.path() << "\n";
std::cout << "menu price " << menu.price() << "\n";
}// transparent.js: add() is on every node (a leaf refuses it), and a group guards against cycles and a second parent
class Node {
constructor(name) {
this.name = name;
this.parent = null;
}
add(child) { throw new TypeError(`${this.name} cannot hold children`); } // transparent: every node has add(), so a leaf must refuse
remove(child) { throw new TypeError(`${this.name} cannot hold children`); }
path() { return this.parent === null ? this.name : `${this.parent.path()} > ${this.name}`; } // the parent pointer makes this a walk upwards
}
class Item extends Node {
constructor(name, cost) {
super(name);
this.cost = cost;
}
price() { return this.cost; }
}
class Group extends Node {
constructor(name) {
super(name);
this.children = [];
}
add(child) {
for (let node = this; node !== null; node = node.parent) { // the child must not be this group or any group above it
if (node === child) throw new RangeError(`cycle: ${this.name} cannot contain ${child.name}`);
}
if (child.parent !== null) throw new RangeError(`${child.name} is already in ${child.parent.name}`); // one parent only
child.parent = this;
this.children.push(child);
}
remove(child) {
this.children.splice(this.children.indexOf(child), 1);
child.parent = null;
}
price() { return this.children.reduce((sum, c) => sum + c.price(), 0); }
}
function attempt(action) {
try {
action();
} catch (e) {
console.log(`refused: ${e.message}`);
}
}
const menu = new Group("Menu"), wraps = new Group("Wraps"), combos = new Group("Combos");
const paneer = new Item("Paneer wrap", 150), egg = new Item("Egg wrap", 130);
menu.add(wraps);
menu.add(combos);
wraps.add(paneer);
wraps.add(egg);
console.log(`path: ${paneer.path()}`);
attempt(() => egg.add(paneer));
attempt(() => combos.add(paneer));
attempt(() => wraps.add(wraps));
attempt(() => wraps.add(menu));
wraps.remove(paneer);
combos.add(paneer);
console.log(`path: ${paneer.path()}`);
console.log(`menu price ${menu.price()}`);path: Menu > Wraps > Paneer wrap
refused: Egg wrap cannot hold children
refused: Paneer wrap is already in Wraps
refused: cycle: Wraps cannot contain Wraps
refused: cycle: Wraps cannot contain Menu
path: Menu > Combos > Paneer wrap
menu price 280Read it in order. The paneer wrap sits under Wraps under Menu, and its path() is a walk up the parent pointer. Adding a child to the egg wrap, a leaf, is refused at run time: that is the price of transparency. Adding the paneer wrap to Combos while it is still in Wraps is refused too: a node has one parent. Then the two cycle attempts, a group added to itself and a group added to the group above it. Moving the paneer wrap takes two calls, remove and then add, and its path changes to Menu > Combos > Paneer wrap. The menu price is 150 + 130 = 280 both before and after, because the move changed where a node sits and not what the tree holds.
Safe puts add only on the group, so adding to a leaf won't compile, but interface code can't add. Transparent puts add everywhere, and a leaf refuses.
Cycles, parents and shared nodes#
Three problems come with any real tree, and each one has a clean answer.
A cycle. If a group could contain itself, or contain a group that contains it, then price() would ask a child, which asks its child, which asks the first group again, for ever. It ends in a stack overflow: a RecursionError in Python, a StackOverflowError in Java, a RangeError in JavaScript, and a crash in C++. The guard runs when a child is added: walk up from the group you are adding to, and refuse if you meet the child on the way. With a parent pointer that walk costs the depth of the tree. Without one you would search the child's whole subtree for the group instead. This is the check the file system lesson makes when it refuses mv /home /home/asha/old: a directory can't move inside itself.
A parent pointer. It gives you path() for free and lets a node remove itself from its parent. It costs three things. A node can have only one parent, so a combo that appears in two carts has to be copied (see the Prototype lesson) and not shared. The pointer has to be kept in step with the child list, so add and remove are the only ways to change either, and nothing touches children directly. And in C++ it must be a raw or a weak_ptr, never a shared_ptr, or parent and child own each other and nothing is ever freed. In Python, Java and JavaScript the garbage collector handles the loop.
A shared node. A node with two parents is not a cycle: it is a diamond. Nothing loops, but price() counts it twice, once per path. That is right if the cart really holds two teas, and a bug if one tea was meant to be a single object. The parent pointer's "one parent only" rule is what rules it out, and it is the reason a design that wants sharing (a tree of fine-grained parts that appear thousands of times) reaches for Flyweight instead.
Two smaller costs. Recursion has a depth. Python's default limit is 1,000 frames. Java and JavaScript have no fixed count: the stack size and the size of each frame decide (a one-line recursive price() on a chain of groups went about 13,000 deep on Node 22 and over 100,000 on Java 23, on one laptop), and C++ doesn't check at all, so too deep a tree crashes the process. A menu is never that deep, but a tree built from user data can be (a pathological file system), and then the walk needs an explicit stack instead of recursive calls. And a recursive operation visits every node: price() on the root is O(n). If it is called often, cache it on the groups and, on every change, clear the cache up the parent chain, which is another thing the parent pointer buys. The file system lesson says the same about du: it computes sizes on demand, and notes the cached alternative as a follow-up, not a build.
A cart that contains itself
A bug adds the family feast to its own combo, which is inside the family feast. The cart screen freezes, and the log shows a stack overflow. What should have stopped it, and where?
One strong answer
add should have refused it, by walking up the parents from the combo and finding the feast on the way. The cycle check belongs in the group's add, not in price(): by the time price() runs, the tree is already broken and every operation on it would loop. With parent pointers the walk costs the depth of the tree. The error message names both groups, as the output above does.
Without a check, a feast can join its own combo and nothing complains, until the price call loops for ever. Add should walk up the parents and refuse.
Composite and its look-alikes#
| Pattern | What it does | How to tell it apart |
|---|---|---|
| Decorator | Wraps one component to add behaviour | Structurally close: a decorator is a composite with a single child. But a composite combines many children into one answer, and a decorator changes one child's answer |
| Iterator | Walks a collection one element at a time | Composite is the shape of the data, and iterating a composite (a walk() that yields every node) is a separate job |
| Visitor | Adds a new operation over a class hierarchy without editing it | A composite puts each operation in its classes (price in Item and Group). A visitor moves operations out when you would rather not edit every class for each new one |
| Command | A request as an object | A command made of commands (a macro) is a composite, like Compound in the text editor lesson |
| Flyweight | Shares fine-grained objects | The leaves of a composite are often flyweights, when there are very many of them and few kinds |
The easiest confusion is with Decorator: both hold a child that has the same interface as themselves. Ask what the holder is for. A decorator wraps one thing and the answer is that thing's answer, adjusted. A composite holds a collection and the answer is all the children's answers, combined.
When not to use it#
- When the structure isn't a tree. If parts belong to several parents, or have links across the tree, you have a graph, and a composite's recursion will count things twice or loop.
- When leaves and groups don't answer the same questions. If half the operations make sense only for groups ("how many children?") or only for leaves, the uniform interface fills with methods that throw. That is the transparency cost, and a lot of it is a sign to keep two types.
- When there are only two levels. A category with items, and nothing deeper, is a list inside an object. A composite is for trees of unbounded depth.
- When the tree is deep and the operation is hot. A recursive call per node, on every render, adds up. Cache, or hold the tree flat.
- When the operations keep growing. Ten new operations means ten new methods in every class. That is when Visitor, or a plain function that matches on the type, starts to earn its place.
Where it shows up in the case studies#
Two of the 22 rounds use Composite, and the two uses show its two faces: a tree of data and a tree of commands.
| Case study | Composite | What it shows |
|---|---|---|
| In-memory file system | Node (abstract size, path), File (the leaf), Directory (the composite) |
Directory.size() is the sum of its children's size(), so du is one call at any depth. It is the safe design: only Directory holds children. Every node has a parent, which gives path() and the walk that refuses moving a directory inside itself |
| Text editor with undo and redo | Compound(Command), holding Insert and Delete commands |
A command made of commands. do runs the parts in order and undo runs them in reverse, so typing over a selection (a delete then an insert) is one undo step. It is a small composite: its parts are fixed when it is built, so it has no add and no safety question |
In the interview#
Say it with the catch: "Composite lets a client treat a leaf and a group of leaves the same way, through one interface. A group answers a question by asking its children, so the tree can be any depth. The catch is where add lives: on the interface for transparency, or only on the group for safety."
Then expect the follow-ups:
- "Safety or transparency?" Transparent puts
addon every node, so the client never asks the kind, and a leaf refuses it at run time. Safe puts it only on the group, so the mistake is a compile-time error, but a client holding the interface needs a type check to add. Say which you chose and why. - "What stops a cycle?" The group's
addwalks up its parents and refuses a child it meets on the way. Do it atadd, not inside the recursive operation. - "Why a parent pointer, and what does it cost?" It gives
path()and a cheap cycle check. It means one parent per node, so sharing becomes copying, and it has to be updated byaddandremoveonly. - "How do you add an operation?" A method on every class, which is easy until there are many (then Visitor), or a function that walks the tree.
- "Composite or Decorator?" Both hold children with their own interface. A decorator wraps one and adjusts its answer; a composite holds many and combines theirs.
- "Where have you seen it?" A file system, a UI toolkit's widgets, the DOM, a menu, an expression tree, a macro command.
Common mistakes#
- Branching on the kind in the client, which is the if-ladder the pattern removes.
- Putting
addon the leaf and then letting it fail silently. Refuse it loudly, or keep it off the leaf. - No cycle guard. The first bug report is a frozen screen and a stack overflow.
- Sharing one node under two parents by accident, so
price()counts it twice and a parent pointer points at only one of them. - A composite with rules of its own. A group that decides discounts by walking its children's kinds is the if-ladder again, one level up.
- Calling a decorator a composite, or the reverse, because both hold a child with the same interface.
Composite
Q1/4 What does the Composite pattern let a client do?
Answer & explanation
Answer: B
The intent is to treat individual objects and compositions of objects uniformly. A group answers each question by asking its children the same one, so the client calls one interface at any depth. Sharing is Flyweight, wrapping is Decorator, and walking is Iterator.
Q2/4 In the safe design,
addis only on the group. What is the cost?Answer & explanation
Answer: C
Safe gives up transparency: leaves and groups have different interfaces, so code that holds a
MenuNodecan't calladdon it. In exchange, adding to a leaf is a compile-time error in Java and C++, or a type-checker error in Python and TypeScript. The transparent design makes the opposite trade.Q3/4 A group is added to one of its own descendants, and
price()then never returns. What should have stopped it?Answer & explanation
Answer: C
The check belongs where the tree is changed. By the time
price()runs, the structure is already broken. Walking up the parents from the group you are adding to, and refusing the child if it is found, costs the depth of the tree. A parent pointer helps the walk, but it doesn't forbid the loop on its own.Q4/4 The text editor lesson's
Compoundcommand holds an insert and a delete, runs them in order and undoes them in reverse. Why is that a Composite?Answer & explanation
Answer: B
Storing parts in a list isn't the pattern: the pattern is that the group has the same interface as one part, so the editor's history can't tell a
Compoundfrom anInsert. Adding behaviour around one command would be a Decorator.
this lesson in shorts · 3
play them all →One idea from this lesson in about a minute each, made for your phone.
New lessons by email
New lessons, side quests and case files as they ship, at most once a week. No spam, unsubscribe anytime.
Discussion · …
Public: everyone reading this lesson sees comments. Be kind and keep it on the material.