1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
/*******************************************************************************
* Copyright (c) 2009 Oracle. All rights reserved.
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License v1.0, which accompanies this distribution
* and is available at http://www.eclipse.org/legal/epl-v10.html.
*
* Contributors:
* Oracle - initial API and implementation
******************************************************************************/
package org.eclipse.jpt.utility.internal.iterables;
import java.util.Arrays;
import java.util.Iterator;
import org.eclipse.jpt.utility.internal.StringTools;
import org.eclipse.jpt.utility.internal.iterators.GraphIterator;
/**
* A <code>GraphIterable</code> is similar to a {@link TreeIterable}
* except that it cannot be assumed that all nodes assume a strict tree
* structure. For instance, in a tree, a node cannot be a descendent of
* itself, but a graph may have a cyclical structure.
*
* A <code>GraphIterable</code> simplifies the traversal of a
* graph of objects, where the objects' protocol(s) provides
* a method for getting the next collection of nodes in the graph,
* (or <em>neighbors</em>), but does not provide a method for
* getting <em>all</em> of the nodes in the graph.
* (e.g. a neighbor can return his neighbors, and those neighbors
* can return their neighbors, which might also include the original
* neighbor, but you only want to visit the original neighbor once.)
* <p>
* If a neighbor has already been visited (determined by using
* {@link #equals(Object)}), that neighbor is not visited again,
* nor are the neighbors of that object.
* <p>
* It is up to the user of this class to ensure a <em>complete</em> graph.
* <p>
* To use, supply:<ul>
* <li> either the initial node of the graph or an {@link Iterable}
* of the initial collection of graph nodes
* <li> a {@link GraphIterator.MisterRogers} that tells who the neighbors are
* of each node
* (alternatively, subclass <code>GraphIterable</code>
* and override the {@link #neighbors(Object)} method)
* </ul>
* The {@link Iterator#remove()} operation is not supported. This behavior, if
* desired, must be implemented by the user of this class.
*
* @param <E> the type of elements returned by the iterable's iterator
*
* @see GraphIterator
*/
public class GraphIterable<E>
implements Iterable<E>
{
private final Iterable<? extends E> roots;
private final GraphIterator.MisterRogers<E> misterRogers;
/**
* Construct an iterable containing the nodes of a graph with the specified root
* and a default Mr. Rogers that calls back to the iterable.
* Use this constructor if you want to override the
* {@link #neighbors(Object)} method instead of building
* a {@link GraphIterator.MisterRogers}.
*/
public GraphIterable(E root) {
this(new SingleElementIterable<E>(root));
}
/**
* Construct an iterable containing the nodes of a graph
* with the specified root and Mr. Rogers.
*/
public GraphIterable(E root, GraphIterator.MisterRogers<E> misterRogers) {
this(new SingleElementIterable<E>(root), misterRogers);
}
/**
* Construct an iterable containing the nodes of a graph
* with the specified collection of roots
* and a default Mr. Rogers that calls back to the iterable.
* Use this constructor if you want to override the
* {@link #neighbors(Object)} method instead of building
* a {@link GraphIterator.MisterRogers}.
*/
public GraphIterable(E... roots) {
this(Arrays.asList(roots));
}
/**
* Construct an iterable containing the nodes of a graph
* with the specified roots and Mr. Rogers.
*/
public GraphIterable(E[] roots, GraphIterator.MisterRogers<E> misterRogers) {
this(Arrays.asList(roots), misterRogers);
}
/**
* Construct an iterable containing the nodes of a graph
* with the specified collection of roots
* and a default Mr. Rogers that calls back to the iterable.
* Use this constructor if you want to override the
* {@link #neighbors(Object)} method instead of building
* a {@link GraphIterator.MisterRogers}.
*/
public GraphIterable(Iterable<? extends E> roots) {
super();
this.roots = roots;
this.misterRogers = this.buildDefaultMisterRogers();
}
/**
* Construct an iterable containing the nodes of a graph
* with the specified roots and Mr. Rogers.
*/
public GraphIterable(Iterable<? extends E> roots, GraphIterator.MisterRogers<E> misterRogers) {
super();
this.roots = roots;
this.misterRogers = misterRogers;
}
protected GraphIterator.MisterRogers<E> buildDefaultMisterRogers() {
return new DefaultMisterRogers();
}
public Iterator<E> iterator() {
return new GraphIterator<E>(this.roots, this.misterRogers);
}
/**
* Return the immediate neighbors of the specified object.
* <p>
* This method can be overridden by a subclass as an
* alternative to building a {@link GraphIterator.MisterRogers}.
*/
protected Iterator<? extends E> neighbors(@SuppressWarnings("unused") E next) {
throw new RuntimeException("This method was not overridden."); //$NON-NLS-1$
}
@Override
public String toString() {
return StringTools.buildToStringFor(this, this.roots);
}
//********** default Mr. Rogers **********
protected class DefaultMisterRogers implements GraphIterator.MisterRogers<E> {
public Iterator<? extends E> neighbors(E node) {
return GraphIterable.this.neighbors(node);
}
}
}
|
