View Javadoc

1   /*
2    * Copyright (c) 2003-2008 by Cosylab d. d.
3    *
4    * This file is part of Java-Common.
5    *
6    * Java-Common is free software: you can redistribute it and/or modify
7    * it under the terms of the GNU General Public License as published by
8    * the Free Software Foundation, either version 3 of the License, or
9    * (at your option) any later version.
10   *
11   * Java-Common is distributed in the hope that it will be useful,
12   * but WITHOUT ANY WARRANTY; without even the implied warranty of
13   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   * GNU General Public License for more details.
15   *
16   * You should have received a copy of the GNU General Public License
17   * along with Java-Common.  If not, see <http://www.gnu.org/licenses/>.
18   */
19  
20  package com.cosylab.util;
21  
22  import java.util.Iterator;
23  import java.util.LinkedList;
24  
25  /**
26   * Iterator for tree-like structures.
27   * 
28   * @author Klemen Zagar, Cosylab
29   */
30  public abstract class TreeIterator<T, U> implements Iterator<T> {
31  	private final LinkedList<U> queue = new LinkedList<U>();
32  
33  	private final Order order;
34  
35  	private Iterator<T> currentIterator = null;
36  
37  	private U currentNode = null;
38  
39  	public enum Order {
40  		BreadthFirst,
41  		DepthFirst
42  	};
43  
44  	/**
45  	 * Construct a tree iterator over a nested iterator structure.
46  	 * 
47  	 * @param root
48  	 *        Iterator through root-level elements.
49  	 * @param order
50  	 *        Order of iteration over children.
51  	 */
52  	public TreeIterator(U root, Order order) {
53  		this.queue.add(root);
54  		this.order = order;
55  	}
56  
57  	/*
58  	 * (non-Javadoc)
59  	 * 
60  	 * @see java.util.Iterator#hasNext()
61  	 */
62  	public boolean hasNext() {
63  		return getCurrentIterator().hasNext();
64  	}
65  
66  	/**
67  	 * @return
68  	 */
69  	private Iterator<T> getCurrentIterator() {
70  		if (this.currentIterator != null) {
71  			if (this.currentIterator.hasNext()) {
72  				return this.currentIterator;
73  			}
74  			this.currentIterator = null;
75  		}
76  		do {
77  			do {
78  				if (this.queue.isEmpty()) {
79  					return new NoElementsIterator<T>();
80  				}
81  				this.currentNode = this.queue.removeFirst();
82  				if (this.currentNode != null) {
83  					this.currentIterator = getIterator(this.currentNode);
84  				}
85  			} while (this.currentIterator == null);
86  
87  			Iterator<U> iter = getChildren(this.currentNode);
88  			while (iter.hasNext()) {
89  				if (this.order == Order.BreadthFirst) {
90  					this.queue.add(iter.next());
91  				} else {
92  					this.queue.push(iter.next());
93  				}
94  			}
95  		} while (!this.currentIterator.hasNext());
96  
97  		return this.currentIterator;
98  	}
99  
100 	/*
101 	 * (non-Javadoc)
102 	 * 
103 	 * @see java.util.Iterator#next()
104 	 */
105 	public T next() {
106 		return getCurrentIterator().next();
107 	}
108 
109 	/*
110 	 * (non-Javadoc)
111 	 * 
112 	 * @see java.util.Iterator#remove()
113 	 */
114 	public void remove() {
115 		getCurrentIterator().remove();
116 	}
117 
118 	protected abstract Iterator<U> getChildren(U obj);
119 
120 	protected abstract Iterator<T> getIterator(U obj);
121 }
122 
123 /* __oOo__ */