View Javadoc

1   //////////////////////////////////////////////////////////////////////////////
2   // Clirr: compares two versions of a java library for binary compatibility
3   // Copyright (C) 2003 - 2005  Lars Kühne
4   //
5   // This library is free software; you can redistribute it and/or
6   // modify it under the terms of the GNU Lesser General Public
7   // License as published by the Free Software Foundation; either
8   // version 2.1 of the License, or (at your option) any later version.
9   //
10  // This library is distributed in the hope that it will be useful,
11  // but WITHOUT ANY WARRANTY; without even the implied warranty of
12  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13  // Lesser General Public License for more details.
14  //
15  // You should have received a copy of the GNU Lesser General Public
16  // License along with this library; if not, write to the Free Software
17  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
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 }