1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package net.sf.clirr.core.internal;
21
22 import java.util.Collection;
23 import java.util.Comparator;
24 import java.util.Arrays;
25 import java.util.NoSuchElementException;
26
27 /***
28 * This is an iterator that walks a pair of collections, returning
29 * matching pairs from the set.
30 * <p>
31 * When an element is present in the left set but there is no equal object
32 * in the right set, the pair (leftobj, null) is returned.
33 * <p>
34 * When an element is present in the right set but there is no equal object
35 * in the left set, the pair (null, rightobj) is returned.
36 * <p>
37 * When an element in one set has an equal element in the other set, the
38 * pair (leftobj, rightobj) is returned.
39 * <p>
40 * Note that the phrase "pair is returned" above actually means that the
41 * getLeft and getRight methods on the iterator return those objects; the
42 * pair is "conceptual" rather than a physical Pair instance. This avoids
43 * instantiating an object to represent the pair for each step of the
44 * iterator which would not be efficient.
45 * <p>
46 * Note also that elements from the sets are always returned in the order
47 * defined by the provided comparator.
48 *
49 * @author Simon Kitching.
50 */
51
52 public final class CoIterator
53 {
54 private Object[] left;
55 private Object[] right;
56
57 private int leftIndex;
58 private int rightIndex;
59
60 private Object currLeft;
61 private Object currRight;
62
63 private Comparator comparator;
64
65 /***
66 * Iterate over the two collections, using the provided comparator.
67 * <p>
68 * The collections are not modified by this iterator.
69 *
70 * @param comparator is used to compare elements from the two collections.
71 * If null, then the objects in the collections are expected to implement
72 * the Comparable interface.
73 */
74 public CoIterator(Comparator comparator, Collection left, Collection right)
75 {
76 this.comparator = comparator;
77 this.left = left.toArray();
78 this.right = right.toArray();
79
80 Arrays.sort(this.left, comparator);
81 Arrays.sort(this.right, comparator);
82 }
83
84 /***
85 * Iterate over the objects in the two arrays, using the provided comparator.
86 * <p>
87 * The arrays are not modified by this iterator. In particular, the
88 * iterator returns the elements in ascending order, but the actual
89 * arrays passed in here are cloned so that they are not modified.
90 *
91 * @param comparator is used to compare elements from the two collections.
92 * If null, then the objects in the collections are expected to implement
93 * the Comparable interface.
94 */
95 public CoIterator(Comparator comparator, Object[] left, Object[] right)
96 {
97 this.comparator = comparator;
98 this.left = (Object[]) left.clone();
99 this.right = (Object[]) right.clone();
100
101 Arrays.sort(this.left, comparator);
102 Arrays.sort(this.right, comparator);
103 }
104
105 /***
106 * Indicates whether there are any more elements to be returned.
107 */
108 public boolean hasNext()
109 {
110 return (leftIndex < left.length) || (rightIndex < right.length);
111 }
112
113 /***
114 * Moves this iterator object to refer to the next "pair" of objects.
115 * <p>
116 * Note that unlike the standard java.util.Iterator, this method does
117 * not return anything; it simply modifies which objects will be
118 * returned by the getLeft and getRight methods.
119 *
120 * @throws java.util.NoSuchElementException if this is called when hasNext would
121 * report false (this is standard iterator behaviour).
122 */
123 public void next()
124 {
125 boolean haveLeft = leftIndex < left.length;
126 boolean haveRight = rightIndex < right.length;
127
128 if (!haveLeft && !haveRight)
129 {
130 currLeft = null;
131 currRight = null;
132 throw new NoSuchElementException();
133 }
134
135 int order;
136
137 if (haveLeft && !haveRight)
138 {
139 order = -1;
140 }
141 else if (!haveLeft && haveRight)
142 {
143 order = +1;
144 }
145 else if (comparator != null)
146 {
147 order = comparator.compare(left[leftIndex], right[rightIndex]);
148 }
149 else
150 {
151 Comparable c1 = (Comparable) left[leftIndex];
152 order = c1.compareTo(right[rightIndex]);
153 }
154
155 if (order < 0)
156 {
157 currLeft = left[leftIndex];
158 currRight = null;
159 ++leftIndex;
160 }
161 else if (order > 0)
162 {
163 currLeft = null;
164 currRight = right[rightIndex];
165 ++rightIndex;
166 }
167 else
168 {
169 currLeft = left[leftIndex];
170 currRight = right[rightIndex];
171 ++leftIndex;
172 ++rightIndex;
173 }
174 }
175
176 /***
177 * Return an object from the "left" collection specified to this object's
178 * constructor. When the iterator has selected an element in the "right"
179 * collection for which there is no corresponding element in the left
180 * collection, then this will return null.
181 */
182 public Object getLeft()
183 {
184 return currLeft;
185 }
186
187 /***
188 * See getLeft.
189 */
190 public Object getRight()
191 {
192 return currRight;
193 }
194 }