System Design (LLD): Composite Design Pattern

The Composite Design Pattern is a structural design pattern used to treat individual objects (leaf nodes) and compositions of objects (composite nodes) uniformly. Rather than relying on generic foundational design patterns, the Composite pattern addresses a specific, recurring structural challenge: handling hierarchical, tree-like data structures where containers can hold both atomic elements and other containers seamlessly.

1. Introduction: Foundational vs. Use-Case-Specific Patterns

In Low-Level System Design (LLD), design patterns generally fall into two broad categories:

1. Foundational Patterns: Generic patterns applicable across almost every application layer (e.g., Strategy, Factory, Singleton, Observer).
2. Use-Case-Specific Patterns: Structural patterns tailored to solve specific structural or architectural problems (e.g., Composite, Decorator, Flyweight).

Core Mental Model (DSA Trees):
If you are familiar with Tree Data Structures in DSA, you already understand the core intuition behind the Composite pattern. Any problem statement that can be expressed as a tree hierarchy composed of Leaf Nodes (terminal nodes) and Non-Leaf / Composite Nodes (intermediate nodes) is a candidate for the Composite Design Pattern.

2. The Naive Approach: Designing a File System

To understand why the Composite pattern is necessary, consider the classic engineering challenge: Designing an Operating System File System.

A file system consists of:

• Files: Leaf items that contain metadata and data, but cannot contain other items.
• Folders (Directories): Composite items that hold both files and nested sub-folders.

Naive Implementation (Without Design Patterns)

A naive approach attempts to model File and Folder as two separate, decoupled classes:

// Naive File Class
class File {
    string name;
    int size;
    string content;

public:
    File(string name, int size) : name(name), size(size) {}
    void open() {
        cout << "Displaying content of file: " << name << endl;
    }
};

// Naive Folder Class
class Folder {
    string name;
    vector<File> files;      // List of files
    vector<Folder> folders;  // List of sub-folders

public:
    Folder(string name) : name(name) {}
    
    void addFile(File f) { files.push_back(f); }
    void addFolder(Folder f) { folders.push_back(f); }
};

3. Pitfalls of the Naive Approach

While the naive approach appears simple initially, it breaks down quickly when implementing operations such as ls (list directory) or openAll (recursively expand the entire directory tree).

Critical Flaws in the Naive Approach

1. Disrupted Ordering / Loss of Insertion History: Maintaining two separate collections (vector<File> and vector<Folder>) loses the natural creation or insertion order of directory contents. Executing a display command outputs all files first, followed by all folders, rather than rendering them in their actual sequence.

2. Explosion of Type Checking (if-else Branching): To maintain ordering, you might attempt to store a single list of generic void or base pointers. However, processing this list requires constant runtime type checks:

// Flawed conditional handling inside client/folder logic
for (auto item : commonList) {
    if (typeid(*item) == typeid(File)) {
        // Handle File logic
        item->printName();
    } else if (typeid(*item) == typeid(Folder)) {
        // Handle Folder logic
        item->openAll(); // Recursive invocation
    }
}

3. High Coupling & Violation of Open/Closed Principle: Adding new features (such as cd [Change Directory] or getSize) forces modifications across multiple classes, introducing repetitive conditional branching throughout the codebase.

4. The Philosophy of the Composite Design Pattern

The Composite Design Pattern states:

Core Principle: Treat individual atomic objects (Leaf) and compositions of objects (Composite) uniformly through a shared common interface.

By decoupling client code from concrete implementations, the client interacts solely with a unified abstraction (FileSystemItem). The client does not need to know whether an item is a single file or a directory containing thousands of nested items.

The Dual Relationship in Composite Structures

In this pattern, the composite object (Folder) exhibits two distinct relationships with the base interface (FileSystemItem):

1. IS-A Relationship: Folder extends/implements FileSystemItem.
2. HAS-A Relationship: Folder holds a collection (1 to Many) of FileSystemItem pointers.

Note: This dual IS-A and HAS-A structure is structural sibling to the Decorator Design Pattern, where a decorator both inherits from and wraps a base component.

5. Structural Architecture & UML Diagram

GoF Standard Component Roles

Textual UML Class Diagram

6. Recursive Tree Traversal Walkthrough

When an operation like openAll() or getSize() is executed on the Root component, polymorphic recursion handles the traversal automatically without requiring manual type inspection.

Execution Flow: getSize() Calculation

7. Complete C++ Implementation

Here is a complete, production-ready C++ implementation of the File System designed using the Composite Pattern.

#include <iostream>
#include <string>
#include <vector>
#include <memory>
#include <iomanip>

using namespace std;

// Base Component Interface
class FileSystemItem {
public:
    virtual void ls(int indent = 0) const = 0;
    virtual void openAll(int indent = 0) const = 0;
    virtual int getSize() const = 0;
    virtual FileSystemItem* cd(const string& target) = 0;
    virtual string getName() const = 0;
    virtual bool isFolder() const = 0;
    virtual ~FileSystemItem() = default;
};

// Leaf Node: File
class File : public FileSystemItem {
private:
    string name;
    int size;

public:
    File(string name, int size) : name(name), size(size) {}

    void ls(int indent = 0) const override {
        cout << string(indent, ' ') << name << endl;
    }

    void openAll(int indent = 0) const override {
        cout << string(indent, ' ') << name << endl;
    }

    int getSize() const override {
        return size;
    }

    FileSystemItem* cd(const string& target) override {
        // Operations like 'cd' are unsupported on terminal Leaf nodes.
        return nullptr;
    }

    string getName() const override {
        return name;
    }

    bool isFolder() const override {
        return false;
    }
};

// Composite Node: Folder
class Folder : public FileSystemItem {
private:
    string name;
    vector<FileSystemItem*> children;

public:
    Folder(string name) : name(name) {}

    void add(FileSystemItem* item) {
        children.push_back(item);
    }

    void ls(int indent = 0) const override {
        for (const auto& child : children) {
            if (child->isFolder()) {
                cout << string(indent, ' ') << "+ " << child->getName() << endl;
            } else {
                cout << string(indent, ' ') << child->getName() << endl;
            }
        }
    }

    void openAll(int indent = 0) const override {
        cout << string(indent, ' ') << "+ " << name << endl;
        for (const auto& child : children) {
            child->openAll(indent + 4);
        }
    }

    int getSize() const override {
        int totalSize = 0;
        for (const auto& child : children) {
            totalSize += child->getSize(); // Polymorphic recursive aggregation
        }
        return totalSize;
    }

    FileSystemItem* cd(const string& target) override {
        for (auto child : children) {
            if (child->isFolder() && child->getName() == target) {
                return child;
            }
        }
        return nullptr;
    }

    string getName() const override {
        return name;
    }

    bool isFolder() const override {
        return true;
    }

    ~Folder() {
        for (auto child : children) {
            delete child;
        }
    }
};

// Main Execution
int main() {
    // Construct Root Directory
    Folder* root = new Folder("root");
    root->add(new File("file1.txt", 1));
    root->add(new File("file2.txt", 1));

    // Construct Sub-Folder: docs
    Folder* docs = new Folder("docs");
    docs->add(new File("resume.pdf", 1));
    docs->add(new File("notes.txt", 1));
    root->add(docs);

    // Construct Sub-Folder: images
    Folder* images = new Folder("images");
    images->add(new File("photo.jpg", 1));
    root->add(images);

    cout << "=== 1. Execution of openAll() on Root ===" << endl;
    root->openAll();

    cout << "\n=== 2. Execution of ls() on Root ===" << endl;
    root->ls();

    cout << "\n=== 3. Execution of ls() inside 'docs' folder ===" << endl;
    docs->ls();

    cout << "\n=== 4. Execution of cd('docs') from Root ===" << endl;
    FileSystemItem* cwd = root->cd("docs");
    if (cwd != nullptr) {
        cout << "Successfully changed directory to: " << cwd->getName() << endl;
        cwd->ls();
    } else {
        cout << "Directory not found!" << endl;
    }

    cout << "\n=== 5. Total Root Directory Size ===" << endl;
    cout << "Total Size: " << root->getSize() << " KB" << endl;

    delete root; // Cleanup memory
    return 0;
}

8. Handling Edge Cases & Operational Behavior

When defining interface operations across Leaf and Composite nodes, certain operations make sense for both node types, while others apply cleanly to only one.

Operational Matrix

Handling Unsupported Operations (cd on Leaf):
Defining cd() on a base component interface means Leaf elements must handle it gracefully. Returning nullptr or throwing an UnsupportedOperationException indicates that terminal nodes cannot be traversed deeper.

9. Real-World Applications

The Composite Design Pattern is ideal for systems requiring hierarchical structuring and uniform treatment of individual and grouped elements.

10. Summary and Key Takeaways

• Target Structure: The Composite Design Pattern fits tree-structured domain problems containing Leaf (atomic) and Composite (container) components.
• Uniformity: Allows client code to interact with complex tree hierarchies through a single interface, ignoring the distinction between individual elements and compositions.
• Eliminates Branching: Removes complex runtime type inspections (typeid, instanceof, or nested if-else blocks) during hierarchy traversals.
• Dual Relationship: Composite nodes exhibit both an IS-A relationship (inheriting from the base interface) and a HAS-A relationship (containing a collection of base interface references).
• Polymorphic Recursion: Operations like getSize() or openAll() rely on recursive polymorphic calls down the component tree until reaching terminal leaf nodes.
• Extensibility: Adheres to the Open/Closed Principle. New component types (such as SymLink or Shortcut) can be added without modifying existing client or traversal logic.