Iterator & Composite Pattern - Traversal Abstractions

▶

Steps

setup

Create Leaf Components

Leaf components FileA, FileB, and FileC are instantiated with their names.

💡 Leaves represent end nodes in the composite structure and will yield themselves once when iterated.

Line:

class Leaf(Component):
    def create_iterator(self):
        return LeafIterator(self)

💡 Leaves have a simple iterator that returns themselves once, enabling uniform traversal.

setup

Create Composite Components

Composite components Folder1 and Folder2 are instantiated, each able to hold children components.

💡 Composites can contain children and provide iterators that traverse their children recursively.

Line:

class Composite(Component):
    def __init__(self, name):
        super().__init__(name)
        self.children = []

💡 Composite components aggregate children and delegate traversal to their children's iterators.

setup

Build Composite Tree Structure

Folder1 adds FileA and FileB as children; Folder2 adds FileC as a child.

💡 Building the tree structure sets up the hierarchy for traversal.

Line:

folder1.add(fileA)
folder1.add(fileB)
folder2.add(fileC)

💡 Children are stored in composites, enabling recursive traversal through the tree.

setup

Create Root Composite and Add Children

Root composite is created and Folder1 and Folder2 are added as its children.

💡 The root composite represents the entire tree and starts the traversal.

Line:

root = Composite('root')
root.add(folder1)
root.add(folder2)

💡 The root composite holds top-level children, enabling traversal from the root down.

setup

Create Iterator for Root Composite

The root composite creates a CompositeIterator to traverse its children.

💡 CompositeIterator manages traversal over multiple children iterators recursively.

Line:

iterator = root.create_iterator()

💡 Traversal begins with the root's iterator, which will delegate to children iterators.

compare

Check hasNext on Root Iterator (First Call)

Root iterator checks if there are children left to traverse; initializes current_iterator with Folder1's iterator.

💡 hasNext prepares the next iterator to use, enabling lazy traversal.

Line:

if self.current_iterator is None:
    if self.index >= len(self.children):
        return False
    self.current_iterator = self.children[self.index].create_iterator()
    self.index += 1

💡 Iterator lazily initializes child iterators only when needed.

expand

Traverse Folder1 (Composite) - Create Iterator

Folder1's iterator is created, which will iterate over FileA and FileB.

💡 CompositeIterator recursively creates iterators for children composites.

Line:

self.current_iterator = self.children[self.index].create_iterator()

💡 Traversal expands into Folder1's children by creating its iterator.

traverse

Traverse Folder1 - Yield Folder1 Itself

Folder1 is yielded first in traversal as the current composite node.

💡 CompositeIterator yields the composite node before traversing its children.

Line:

return self.leaf  # in LeafIterator.next() or current composite node

💡 Traversal visits composite nodes before their children, following depth-first order.

expand

Traverse Folder1's Children - Create Iterator for FileA

Folder1's iterator moves to FileA, creating a LeafIterator for it.

💡 LeafIterator yields the leaf node once, enabling uniform traversal.

Line:

self.current_iterator = self.children[self.index].create_iterator()

💡 Traversal expands into leaf nodes by creating their simple iterators.

traverse

Traverse FileA - Yield FileA

FileA is yielded as the next leaf node in traversal.

💡 LeafIterator returns the leaf component once and then marks done.

Line:

if self.done:
    raise StopIteration
self.done = True
return self.leaf

💡 Leaves are visited exactly once in traversal, confirming depth-first order.

expand

Traverse Folder1's Children - Move to FileB Iterator

Folder1's iterator moves to FileB, creating a LeafIterator for it.

💡 CompositeIterator advances to next child iterator after finishing previous.

Line:

if not self.current_iterator.hasNext():
    self.current_iterator = None

💡 Iterator manages switching between children iterators seamlessly.

traverse

Traverse FileB - Yield FileB

FileB is yielded as the next leaf node in traversal.

💡 LeafIterator returns the leaf component once and then marks done.

Line:

if self.done:
    raise StopIteration
self.done = True
return self.leaf

💡 Traversal continues visiting leaves in order under Folder1.

expand

Traverse Root Iterator - Move to Folder2 Iterator

Root iterator moves to Folder2, creating its CompositeIterator for traversal.

💡 CompositeIterator moves to next child composite after finishing previous.

Line:

if self.current_iterator is None:
    self.current_iterator = self.children[self.index].create_iterator()
    self.index += 1

💡 Traversal continues depth-first into next top-level composite.

traverse

Traverse Folder2 - Yield Folder2

Folder2 is yielded as the next composite node in traversal.

💡 CompositeIterator yields composite nodes before their children.

Line:

return self.leaf  # in LeafIterator.next() or current composite node

💡 Traversal visits Folder2 before its children, maintaining depth-first order.

expand

Traverse Folder2's Children - Create Iterator for FileC

Folder2's iterator moves to FileC, creating a LeafIterator for it.

💡 LeafIterator yields leaf nodes once, enabling uniform traversal.

Line:

self.current_iterator = self.children[self.index].create_iterator()

💡 Traversal expands into leaf nodes under Folder2.

traverse

Traverse FileC - Yield FileC

FileC is yielded as the last leaf node in traversal.

💡 LeafIterator returns the leaf component once and then marks done.

Line:

if self.done:
    raise StopIteration
self.done = True
return self.leaf

💡 Traversal completes visiting all leaves in depth-first order.

compare

Check hasNext on Root Iterator - No More Children

Root iterator checks for more children but finds none, signaling traversal end.

💡 hasNext returns false when all children have been traversed.

Line:

if self.index >= len(self.children):
    return False

💡 Traversal ends when all children iterators are exhausted.

reconstruct

Traversal Complete - Output Traversal Order

Traversal order is read from the sequence of yielded components: Folder1, FileA, FileB, Folder2, FileC.

💡 The iterator interface abstracts traversal order without exposing tree structure.

Line:

while iterator.hasNext():
    component = iterator.next()
    print(component.name)

💡 Unified iterator interface enables client code to traverse composite trees transparently.

from collections import deque

class Iterator:
    def hasNext(self):  # STEP 6,11,17
        raise NotImplementedError
    def next(self):  # STEP 8,10,12,16
        raise NotImplementedError

class Component:
    def __init__(self, name):  # STEP 1,2,4
        self.name = name
    def create_iterator(self):  # STEP 1,2
        raise NotImplementedError

class Leaf(Component):
    def create_iterator(self):  # STEP 1,9
        return LeafIterator(self)

class Composite(Component):
    def __init__(self, name):  # STEP 2,4
        super().__init__(name)
        self.children = []
    def add(self, component):  # STEP 3,4
        self.children.append(component)
    def create_iterator(self):  # STEP 5,7,13
        return CompositeIterator(self.children)

class LeafIterator(Iterator):
    def __init__(self, leaf):  # STEP 1,9
        self.leaf = leaf
        self.done = False
    def hasNext(self):  # STEP 6,11,17
        return not self.done
    def next(self):  # STEP 8,10,12,16
        if self.done:
            raise StopIteration
        self.done = True
        return self.leaf

class CompositeIterator(Iterator):
    def __init__(self, children):  # STEP 5
        self.stack = deque()
        self.children = children
        self.index = 0
        self.current_iterator = None
    def hasNext(self):  # STEP 6,11,17
        while True:
            if self.current_iterator is None:
                if self.index >= len(self.children):
                    return False
                self.current_iterator = self.children[self.index].create_iterator()
                self.index += 1
            if self.current_iterator.hasNext():
                return True
            else:
                self.current_iterator = None
    def next(self):  # STEP 8,10,12,16
        if not self.hasNext():
            raise StopIteration
        return self.current_iterator.next()

# Setup components
fileA = Leaf('FileA')  # STEP 1
fileB = Leaf('FileB')  # STEP 1
fileC = Leaf('FileC')  # STEP 1
folder1 = Composite('Folder1')  # STEP 2
folder1.add(fileA)  # STEP 3
folder1.add(fileB)  # STEP 3
folder2 = Composite('Folder2')  # STEP 2
folder2.add(fileC)  # STEP 3
root = Composite('root')  # STEP 4
root.add(folder1)  # STEP 4
root.add(folder2)  # STEP 4

# Traverse
iterator = root.create_iterator()  # STEP 5
traversal_order = []
while iterator.hasNext():  # STEP 6,11,17
    component = iterator.next()  # STEP 8,10,12,16
    traversal_order.append(component.name)
print('Traversal order:', ', '.join(traversal_order))  # STEP 18

📊

Iterator & Composite Pattern - Traversal Abstractions - Watch the Algorithm Execute, Step by Step

Watching each iterator creation and traversal step reveals how the composite and iterator patterns work together to abstract tree traversal without type checks.

Leaf class encapsulates simple components with a single-element iterator.

Leaf

+name: string

+create_iterator()

Composite class manages children and provides recursive iterators.

Composite

+name: string

−children: List<Component>

+add()

+create_iterator()

Composite aggregates children components, demonstrating composition.

Composite

+name: string

−children: List<Component>

+add()

+create_iterator()

Leaf

+name: string

+create_iterator()

Composite ▷ ComponentLeaf ▷ Component

Root composite aggregates top-level folders, enabling unified traversal.

Composite

+name: string

−children: List<Component>

+add()

+create_iterator()

Leaf

+name: string

+create_iterator()

Composite ▷ ComponentLeaf ▷ Component

CompositeIterator encapsulates recursive traversal logic using a stack.

CompositeIterator

−stack: deque

−children: List<Component>

−index: int

−current_iterator: Iterator

+hasNext()

+next()

CompositeIterator ▷ Iterator

Lazy initialization of child iterators optimizes traversal.

CompositeIterator

−children: List<Component>

−index: int

−current_iterator: Iterator

+hasNext()

Composite

+name: string

−children: List<Component>

+create_iterator()

CompositeIterator ▷ IteratorComposite ▷ Component

Recursive iterator creation enables depth-first traversal.

CompositeIterator

−children: List<Component>

−index: int

−current_iterator: Iterator

+hasNext()

Composite

+name: string

−children: List<Component>

+create_iterator()

CompositeIterator ▷ IteratorComposite ▷ Component

LeafIterator yields the leaf component once.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

Composite

+name: string

LeafIterator ▷ Iterator

LeafIterator encapsulates single-element traversal.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

LeafIterator ▷ Iterator

LeafIterator marks leaf as done after yielding.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

LeafIterator ▷ Iterator

CompositeIterator handles iterator transitions between children.

CompositeIterator

−children: List<Component>

−index: int

−current_iterator: Iterator

+hasNext()

CompositeIterator ▷ Iterator

LeafIterator yields leaf and marks done.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

LeafIterator ▷ Iterator

CompositeIterator recursively traverses nested composites.

CompositeIterator

−children: List<Component>

−index: int

−current_iterator: Iterator

+hasNext()

Composite

+name: string

−children: List<Component>

+create_iterator()

CompositeIterator ▷ IteratorComposite ▷ Component

LeafIterator yields composite node as leaf for traversal.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

Composite

+name: string

LeafIterator ▷ Iterator

LeafIterator encapsulates single-element traversal.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

LeafIterator ▷ Iterator

LeafIterator marks leaf as done after yielding.

LeafIterator

−leaf: Leaf

−done: bool

+hasNext()

+next()

LeafIterator ▷ Iterator

hasNext signals traversal completion when no children remain.

CompositeIterator

−children: List<Component>

−index: int

−current_iterator: Iterator

+hasNext()

CompositeIterator ▷ Iterator

Composite and Iterator patterns unify traversal abstraction.

«abstract»Component

+name: string

+create_iterator()

Composite ▷ ComponentLeaf ▷ ComponentCompositeIterator ▷ IteratorLeafIterator ▷ Iterator

Key Takeaways

✓ The composite and iterator patterns combine to provide a unified traversal interface for tree structures.

This insight is hard to see from code alone because the recursive iterator creation and delegation are subtle and abstract.

✓ Traversal order is depth-first, visiting composite nodes before their children, and leaves exactly once.

Visualizing each iterator creation and next call clarifies the traversal sequence clearly.

✓ The iterator lazily initializes child iterators only when needed, optimizing traversal and simplifying client code.

Seeing hasNext manage iterator transitions step-by-step reveals this lazy evaluation behavior.

Practice

1. What is a common trade-off when using getters and setters for every private field in a class?

medium

A. They can increase code verbosity and reduce encapsulation if used indiscriminately

B. They always improve performance by reducing method calls

C. They eliminate the need for access modifiers entirely

D. They guarantee thread safety without additional synchronization

Solution

1. Step 1: Understand getters/setters purpose

   They provide controlled access but can clutter code if overused.

2. Step 2: Analyze trade-offs

   Excessive getters/setters expose internal structure, reducing encapsulation benefits and increasing verbosity.

3. Step 3: Evaluate incorrect options

   They always improve performance by reducing method calls is false; method calls add overhead. They eliminate the need for access modifiers entirely is wrong; access modifiers remain essential. They guarantee thread safety without additional synchronization is incorrect; thread safety requires explicit handling.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Use getters/setters judiciously to balance encapsulation and code clarity.

Hint: More getters/setters ≠ better encapsulation or performance [OK]

Common Mistakes:

• Assuming getters/setters improve performance
• Believing they replace access modifiers
• Thinking they ensure thread safety automatically

2. What is the time complexity of performing a deep copy on an object with nested collections of total size n, assuming the deep copy recursively duplicates all nested objects?

medium

A. O(1) because only references are copied, no nested duplication

B. O(n log n) because copying nested objects requires sorting references

C. O(n) because each nested object must be duplicated once

D. O(n^2) because each nested object is copied multiple times due to recursion

Solution

1. Step 1: Identify what deep copy does

   Deep copy recursively duplicates each nested object exactly once, traversing the entire object graph.

2. Step 2: Analyze complexity

   Since each of the n nested objects is copied once, the time complexity is linear in n. The recursion does not cause repeated copying of the same object due to memoization.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Deep copy visits each nested object once -> O(n) time [OK]

Hint: Deep copy time scales linearly with total nested objects [OK]

Common Mistakes:

• Thinking recursion causes quadratic copying

3. Which of the following statements about the Single Responsibility Principle is INCORRECT?

medium

A. SRP means a class should only have one method to ensure simplicity.

B. Applying SRP improves cohesion and reduces coupling.

C. A class should have only one reason to change, which means it should have only one responsibility.

D. Violating SRP can lead to fragile code that breaks when unrelated changes occur.

Solution

1. Step 1: Analyze each statement

   A class should have only one reason to change, which means it should have only one responsibility. correctly states the core SRP definition.

2. Step 2: Evaluate SRP means a class should only have one method to ensure simplicity.

   SRP is about reasons to change, not the number of methods; a class can have many methods if they serve one responsibility.

3. Step 3: Confirm options A, B, and D

   Options A, B, and D are true: SRP improves cohesion, reduces coupling, and prevents fragile code.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   SRP ≠ one method per class; it's about one reason to change.

Hint: SRP is about reasons to change, not method count.

Common Mistakes:

• Confusing responsibility with method count.
• Assuming fewer methods always means better design.
• Ignoring cohesion and coupling effects.

4. If you want to reuse parts already built in a complex object (e.g., reuse walls and roof when building multiple houses), which modification to the Builder pattern is most appropriate?

hard

A. Modify the Builder to reset the product after each get_result call to avoid reuse.

B. Use Abstract Factory instead, as it naturally supports part reuse.

C. Cache built parts inside the Builder and reuse them when building new objects.

D. Switch to Factory pattern for simpler object creation and reuse.

Solution

1. Step 1: Understand reuse requirement

   Reusing parts means the Builder should keep built parts cached and reuse them instead of rebuilding.

2. Step 2: Evaluate options

   Cache built parts inside the Builder and reuse them when building new objects. caches parts inside Builder, enabling reuse. Modify the Builder to reset the product after each get_result call to avoid reuse. resets product, preventing reuse. Abstract Factory and Factory do not handle stepwise reuse well.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Caching parts in Builder enables reuse efficiently [OK]

Hint: Cache parts in Builder to enable reuse [OK]

Common Mistakes:

• Resetting product disables reuse
• Confusing Abstract Factory with Builder reuse

5. If a class overloads a method and also overrides it in a subclass, which method call resolution scenario can cause unexpected behavior, and why?

hard

A. Calling an overloaded method with parameters matching the superclass signature may invoke the superclass version even if the subclass overrides another variant

B. Overloaded methods are resolved at runtime, so the most specific subclass method is always called

C. Calling the overloaded method via a superclass reference always invokes the subclass's overridden method, ignoring overloading

D. Overriding disables overloading in subclasses, so only one method version is callable

Solution

1. Step 1: Recall overloading vs overriding resolution

   Overloading is resolved at compile time based on reference type and parameter list; overriding is resolved at runtime based on object type.

2. Step 2: Analyze call with superclass reference

   If the method call matches an overloaded method signature declared in the superclass, that method is chosen at compile time.

3. Step 3: Consider overridden methods

   If the subclass overrides a different method variant, it won't affect calls resolved to the superclass's overloaded method signature.

4. Step 4: Identify unexpected behavior

   This can cause the superclass method to be called unexpectedly, even if the subclass has an overridden variant with a different signature.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Overloading resolution depends on reference type and parameters, potentially bypassing subclass overrides.

Hint: Overloading resolved by reference type; overriding by object type

Common Mistakes:

• Assuming overloaded methods are dynamically dispatched
• Believing overriding disables overloading
• Thinking subclass overrides affect all overloaded variants