001: //////////////////////////////////////////////////////////////////////////////
002: // Clirr: compares two versions of a java library for binary compatibility
003: // Copyright (C) 2003 - 2005 Lars Kühne
004: //
005: // This library is free software; you can redistribute it and/or
006: // modify it under the terms of the GNU Lesser General Public
007: // License as published by the Free Software Foundation; either
008: // version 2.1 of the License, or (at your option) any later version.
009: //
010: // This library is distributed in the hope that it will be useful,
011: // but WITHOUT ANY WARRANTY; without even the implied warranty of
012: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: // Lesser General Public License for more details.
014: //
015: // You should have received a copy of the GNU Lesser General Public
016: // License along with this library; if not, write to the Free Software
017: // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: //////////////////////////////////////////////////////////////////////////////
019:
020: package net.sf.clirr.core.internal;
021:
022: import java.util.Collection;
023: import java.util.Comparator;
024: import java.util.Arrays;
025: import java.util.NoSuchElementException;
026:
027: /**
028: * This is an iterator that walks a pair of collections, returning
029: * matching pairs from the set.
030: * <p>
031: * When an element is present in the left set but there is no equal object
032: * in the right set, the pair (leftobj, null) is returned.
033: * <p>
034: * When an element is present in the right set but there is no equal object
035: * in the left set, the pair (null, rightobj) is returned.
036: * <p>
037: * When an element in one set has an equal element in the other set, the
038: * pair (leftobj, rightobj) is returned.
039: * <p>
040: * Note that the phrase "pair is returned" above actually means that the
041: * getLeft and getRight methods on the iterator return those objects; the
042: * pair is "conceptual" rather than a physical Pair instance. This avoids
043: * instantiating an object to represent the pair for each step of the
044: * iterator which would not be efficient.
045: * <p>
046: * Note also that elements from the sets are always returned in the order
047: * defined by the provided comparator.
048: *
049: * @author Simon Kitching.
050: */
051:
052: public final class CoIterator {
053: private Object[] left;
054: private Object[] right;
055:
056: private int leftIndex;
057: private int rightIndex;
058:
059: private Object currLeft;
060: private Object currRight;
061:
062: private Comparator comparator;
063:
064: /**
065: * Iterate over the two collections, using the provided comparator.
066: * <p>
067: * The collections are not modified by this iterator.
068: *
069: * @param comparator is used to compare elements from the two collections.
070: * If null, then the objects in the collections are expected to implement
071: * the Comparable interface.
072: */
073: public CoIterator(Comparator comparator, Collection left,
074: Collection right) {
075: this .comparator = comparator;
076: this .left = left.toArray();
077: this .right = right.toArray();
078:
079: Arrays.sort(this .left, comparator);
080: Arrays.sort(this .right, comparator);
081: }
082:
083: /**
084: * Iterate over the objects in the two arrays, using the provided comparator.
085: * <p>
086: * The arrays are not modified by this iterator. In particular, the
087: * iterator returns the elements in ascending order, but the actual
088: * arrays passed in here are cloned so that they are not modified.
089: *
090: * @param comparator is used to compare elements from the two collections.
091: * If null, then the objects in the collections are expected to implement
092: * the Comparable interface.
093: */
094: public CoIterator(Comparator comparator, Object[] left,
095: Object[] right) {
096: this .comparator = comparator;
097: this .left = (Object[]) left.clone();
098: this .right = (Object[]) right.clone();
099:
100: Arrays.sort(this .left, comparator);
101: Arrays.sort(this .right, comparator);
102: }
103:
104: /**
105: * Indicates whether there are any more elements to be returned.
106: */
107: public boolean hasNext() {
108: return (leftIndex < left.length) || (rightIndex < right.length);
109: }
110:
111: /**
112: * Moves this iterator object to refer to the next "pair" of objects.
113: * <p>
114: * Note that unlike the standard java.util.Iterator, this method does
115: * not return anything; it simply modifies which objects will be
116: * returned by the getLeft and getRight methods.
117: *
118: * @throws java.util.NoSuchElementException if this is called when hasNext would
119: * report false (this is standard iterator behaviour).
120: */
121: public void next() {
122: boolean haveLeft = leftIndex < left.length;
123: boolean haveRight = rightIndex < right.length;
124:
125: if (!haveLeft && !haveRight) {
126: currLeft = null;
127: currRight = null;
128: throw new NoSuchElementException();
129: }
130:
131: int order;
132:
133: if (haveLeft && !haveRight) {
134: order = -1;
135: } else if (!haveLeft && haveRight) {
136: order = +1;
137: } else if (comparator != null) {
138: order = comparator.compare(left[leftIndex],
139: right[rightIndex]);
140: } else {
141: Comparable c1 = (Comparable) left[leftIndex];
142: order = c1.compareTo(right[rightIndex]);
143: }
144:
145: if (order < 0) {
146: currLeft = left[leftIndex];
147: currRight = null;
148: ++leftIndex;
149: } else if (order > 0) {
150: currLeft = null;
151: currRight = right[rightIndex];
152: ++rightIndex;
153: } else {
154: currLeft = left[leftIndex];
155: currRight = right[rightIndex];
156: ++leftIndex;
157: ++rightIndex;
158: }
159: }
160:
161: /**
162: * Return an object from the "left" collection specified to this object's
163: * constructor. When the iterator has selected an element in the "right"
164: * collection for which there is no corresponding element in the left
165: * collection, then this will return null.
166: */
167: public Object getLeft() {
168: return currLeft;
169: }
170:
171: /**
172: * See getLeft.
173: */
174: public Object getRight() {
175: return currRight;
176: }
177: }
|