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. When a client calls a method on a Proxy object that controls access to a resource-intensive service, what is the typical sequence of events that occurs internally?

easy

A. Proxy performs access control, then lazily initializes the real service if needed, and finally forwards the call

B. Proxy immediately forwards the call to the real service without any checks

C. Proxy modifies the request parameters before forwarding to the real service

D. Proxy creates a simplified interface hiding the complexity of the real service

Solution

1. Step 1: Understand Proxy's role

   Proxy controls access and may delay creation of the real service (lazy initialization).

2. Step 2: Trace the call flow

   Client calls Proxy -> Proxy checks access -> Proxy creates real service if not already created -> Proxy forwards call -> Real service executes.

3. Step 3: Eliminate incorrect options

   B is incorrect because Proxy usually adds control logic before forwarding. C is incorrect as Proxy typically does not modify parameters (that's Decorator or Adapter). D describes Facade, not Proxy.

4. Final Answer:

   Option A -> Option A

Hint: Proxy = gatekeeper + lazy loader

Common Mistakes:

• Assuming Proxy always forwards calls immediately without checks
• Confusing Proxy with Facade's simplification role
• Thinking Proxy modifies request parameters

2. Trace the sequence of events when a player rolls the dice and lands on a ladder in a well-designed Snake and Ladder game. Which of the following best describes the correct order of internal state changes?

easy

A. Player rolls dice -> GameController calculates new position -> Board checks for ladder -> GameController updates Player position accordingly

B. Player rolls dice -> Player position updated -> Board checks for ladder -> Player position updated again if ladder found

C. Player rolls dice -> Board updates Player position directly if ladder found -> Player notified of new position

D. Player rolls dice -> Dice notifies Board -> Board updates Player position -> GameController confirms move

Solution

1. Step 1: Dice roll triggers GameController

   Dice generates number; GameController uses it to calculate tentative position.

2. Step 2: Board checks for ladder or snake

   GameController queries Board to see if new position has ladder or snake.

3. Step 3: GameController updates Player position

   Based on Board's info, GameController updates Player's position accordingly.

4. Step 4: Player position is finalized

   Player's position reflects ladder climb if applicable.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Only GameController manages state changes; Board is queried but does not update Player directly.

Hint: GameController mediates all state changes after dice roll [OK]

Common Mistakes:

• Assuming Player updates position before Board check
• Believing Board directly updates Player position
• Thinking Dice notifies Board

3. You need to design a system where a fixed sequence of steps is followed to prepare different types of beverages, but some steps vary depending on the beverage type. Which design approach best ensures code reuse and enforces the sequence while allowing subclasses to customize specific steps?

easy

A. Implement separate classes with duplicated code for each beverage type.

B. Apply a greedy algorithm to select steps dynamically at runtime based on beverage type.

C. Use a base class defining the skeleton of the algorithm with abstract methods for variable steps, overridden by subclasses.

D. Use a brute force approach that tries all possible step sequences and picks the correct one.

Solution

1. Step 1: Identify the problem structure

   The problem requires a fixed sequence of steps with some steps varying by subclass.

2. Step 2: Match to design pattern

   The Template Method Pattern defines a skeleton algorithm in a base class and lets subclasses override specific steps, ensuring reuse and consistent sequence.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Base class controls sequence; subclasses customize steps [OK]

Hint: Fixed sequence with customizable steps -> Template Method [OK]

Common Mistakes:

• Thinking duplicated code is acceptable for reuse
• Confusing dynamic step selection with greedy algorithms

4. 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

5. If the Snake and Ladder game is extended to support multiple concurrent games running in parallel, which design consideration is most critical to avoid shared state bugs?

hard

A. Ensuring each game instance has its own independent GameController and Player objects

B. Centralizing player positions in a global data structure accessible by all games

C. Sharing the Dice instance across games to reduce resource usage

D. Using a singleton pattern for the Board class to ensure consistency across games

Solution

1. Step 1: Singleton Board pattern

   Incorrect: Singleton would cause shared state across games, leading to conflicts.

2. Step 2: Independent GameController and Player per game

   Correct: Isolates state per game, preventing interference.

3. Step 3: Sharing Dice instance

   Incorrect: Shared Dice can cause race conditions or inconsistent rolls.

4. Step 4: Global player positions

   Incorrect: Global state breaks isolation and causes bugs.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Isolating state per game instance is key for concurrency safety.

Hint: Isolate state per game instance to avoid concurrency bugs [OK]

Common Mistakes:

• Using singleton for shared components without considering concurrency
• Sharing mutable objects like Dice across threads
• Centralizing state globally ignoring isolation