GeeCON Prague 2014*
The moose likes OO, Patterns, UML and Refactoring and the fly likes Head First Design Patterns Composite Iterator Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Engineering » OO, Patterns, UML and Refactoring
Bookmark "Head First Design Patterns Composite Iterator" Watch "Head First Design Patterns Composite Iterator" New topic
Author

Head First Design Patterns Composite Iterator

Paul Kiszka
Greenhorn

Joined: Mar 27, 2006
Posts: 1
Does anyone know the answer (if there was any) to the question about page 374 of Head First Design Patterns posted on January 12,2006? It was about the Composite Iterator (external iterator) bug.

Thanks.
Peer Reynders
Bartender

Joined: Aug 19, 2005
Posts: 2922
    
    5
The Question about page 374 of Head First Design Patterns topic?
Someone left some comments in the unconfirmed errata.
B.Sathish
Ranch Hand

Joined: Aug 18, 2005
Posts: 372
I could find out that its not a bug in the Java API, its a bug in the logic of the program rather. Its related to pushing the composite iterator into the stack. The bug is that for every additional level of nesting that you introduce, that level will be traversed that many number of times. ie If you have a third level of nesting, that level will be traversed 3 times (instead of once). There is a redundancy in pushing the composite iterator into the stack. I tried to work out the fix for that code, but things started going above my head and I quit
Peer Reynders
Bartender

Joined: Aug 19, 2005
Posts: 2922
    
    5
Considering the dual node/leaf nature of a Composite component the assumption that the iterator doesn't iterate over the node that produced it (the root of the (sub)tree) seems strange.
Once you accept that the iterator has to iterate over the root node of the tree, it also becomes clear that that leaf node cannot return a null iterator - instead it must return an iterator that iterates only over the leaf node itself (MenuItem):

In the case of a non-leaf node the node itself (i.e. the root of that subtree) has to be supplied (Menu):


The following is only a first pass for the iterator - so it might still contain bugs (i.e. it hasn't been unit tested) or there may be a (much) better way to do it:

[ March 29, 2006: Message edited by: Peer Reynders ]
Remco Bos
Greenhorn

Joined: Feb 14, 2005
Posts: 3
P.374
The main problem the folowing statement in the next() method of the CompositeIterator class:

The createIterator() returns a new CompositeIterator, and so a new Stack!

How I solved it:

1. The Menu should return just an iterator, not an CompositeIterator



2. Let the Waitress instantiate the CompositeIterator instead of asking the Menu for one.



3. The Menu should not iterate over it's children, we use an external CompositeIterator for that!



4. The root (allMenus) is not returned by the iterator. This is because we ask the allMenus for an iterator for it's children, not for the Menu itself!

5. The printMenu() method in the Waitress should also use the CompositeIterator.



Took me some time to figure this out, maybe I'm totally wrong, please test!!

[ March 30, 2006: Message edited by: Remco Bos ]

[ March 30, 2006: Message edited by: Remco Bos ]
[ March 30, 2006: Message edited by: Remco Bos ]
Ed Sciore
Greenhorn

Joined: Aug 18, 2006
Posts: 1
I'm the person who submitted the bug report to O'Reilly about the problem with Composite Iterator. I thought that my comments would go to the authors, which is why I made them sketchy. If I knew that they were being sent out to the public, then I would have been more clear.

The basic idea is that there are two kinds of iteration going on in the code: the iterator method that clients call, and the iterator that gets the children of a composite node. You cannot use the same method to do both things. (And even if you could, it would be bad style.) So I introduce the method childIterator to do the latter iteration. Once you see the need for two distinct methods, the code is pretty straightforward to write, and hopefully straightforward to read.

Anyway, I taught an OOP course here at Boston College using the HeadFirst design Patterns book. It's a great book. But the Composite Iterator chapter is very badly written and wrong in several places. The URL for my course is http://www.cs.bc.edu/~sciore/courses/cs353/coverage.html My explanation of the problem and solution is towards the end of the lecture notes for class #23. My code appears in the "Menu Iterator" handout from that class.

Comments on that class or any others are appreciated.

Ed
Anand Kane
Greenhorn

Joined: Mar 15, 2005
Posts: 10
Hi All

I wrote this simple composite iterator code. Hope this serves some purpose for someone.

Regards
- Anand

Jan Cumps
Bartender

Joined: Dec 20, 2006
Posts: 2501
    
    8

Welcome to JavaRanch, Andy.


OCUP UML fundamental and ITIL foundation
youtube channel
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: Head First Design Patterns Composite Iterator