KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sf > jga > algorithms > Unique


1 // ============================================================================
2
// $Id: Unique.java,v 1.4 2006/12/05 04:45:44 davidahall Exp $
3
// Copyright (c) 2006 David A. Hall
4
// ============================================================================
5
// The contents of this file are subject to the Common Development and
6
// Distribution License (CDDL), Version 1.0 (the License); you may not
7
// use this file except in compliance with the License.
8
//
9
// From time to time, the license steward (initially Sun Microsystems,
10
// Inc.), and may publish revised and/or new versions of this License.
11
// You may not use, distribute, or otherwise make this file available
12
// under subsequent versions of the License.
13
//
14
// You should have received a copy of the the License along with this
15
// file: if not, a copy of the License is available at
16
//
17
// http://www.sun.com/cddl/cddl.html
18
//
19
// Alternatively, the contents of this file may be used under the terms of the
20
// GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
21
// case the provisions of the LGPL are applicable instead of those above. If you
22
// wish to allow use of your version of this file only under the terms of the
23
// LGPL, and not to allow others to use your version of this file under the
24
// terms of the CDDL, indicate your decision by deleting the provisions above
25
// and replace them with the notice and other provisions required by the LGPL.
26
// If you do not delete the provisions above, a recipient may use your version
27
// of this file under the terms of either the CDDL or the LGPL.
28
//
29
// This library is distributed in the hope that it will be useful,
30
// but WITHOUT ANY WARRANTY; without even the implied warranty of
31
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
32
// ============================================================================
33

34 package net.sf.jga.algorithms;
35
36 import java.util.Collection JavaDoc;
37 import java.util.Comparator JavaDoc;
38 import java.util.Iterator JavaDoc;
39 import java.util.NoSuchElementException JavaDoc;
40 import net.sf.jga.fn.BinaryFunctor;
41 import net.sf.jga.fn.comparison.EqualTo;
42 import net.sf.jga.util.ArrayUtils;
43
44 import static net.sf.jga.util.ArrayUtils.*;
45 import static net.sf.jga.util.CollectionUtils.*;
46
47 /**
48  * Algorithms that eliminate successive duplicate entries from a collection, iteration,
49  * or iterable resource.
50  * <p>
51  * Copyright &copy; 2006 David A. Hall
52  */

53
54 public class Unique {
55     
56     // ============
57
// Arrays
58
// ============
59

60     /**
61      * Returns the elements of the array, skipping duplicate entries. This version uses T.equals()
62      * to test for equality.
63      */

64     static public <T> Iterable JavaDoc<T> unique(T[] ts) {
65         return new UniqueIterable<T>(iterable(ts));
66     }
67
68     
69     /**
70      * Returns the elements of the array, skipping duplicate entries as determined by the given
71      * comparator.
72      */

73     static public <T> Iterable JavaDoc<T> unique(T[] ts, Comparator JavaDoc<? super T> comp) {
74         return new UniqueIterable<T>(iterable(ts), comp);
75     }
76
77     
78     /**
79      * Returns the elements of the array, skipping duplicate entries as determined by the given
80      * predicate. The predicate should return true when the adjacent items are the same.
81      */

82     static public <T> Iterable JavaDoc<T> unique(T[] ts, BinaryFunctor<T,T,Boolean JavaDoc> eq) {
83         return new UniqueIterable<T>(iterable(ts), eq);
84     }
85     
86     // ============
87
// Iterables
88
// ============
89

90     /**
91      * Returns the contents of the input, skipping duplicate entries. This version uses T.equals()
92      * to test for equality.
93      */

94     static public <T> Iterable JavaDoc<T> unique(Iterable JavaDoc<? extends T> i) {
95         return new UniqueIterable<T>(i);
96     }
97
98     
99     /*
100      * Returns the contents of the input, skipping duplicate entries as determined by the given
101      * comparator.
102      */

103     static public <T> Iterable JavaDoc<T> unique(Iterable JavaDoc<? extends T> i, Comparator JavaDoc<? super T> comp) {
104         return new UniqueIterable<T>(i, comp);
105     }
106
107     
108     /*
109      * Returns the contents of the input, skipping duplicate entries as determined by the given
110      * predicate. The predicate should return true when the adjacent items are the same.
111      */

112     static public <T> Iterable JavaDoc<T> unique(Iterable JavaDoc<? extends T> i, BinaryFunctor<T,T,Boolean JavaDoc> eq) {
113         return new UniqueIterable<T>(i, eq);
114     }
115     
116     // ============
117
// Iterators
118
// ============
119

120     /**
121      * Returns the contents of the iterator, skipping duplicate entries. This version uses
122      * T.equals() to test for equality.
123      */

124     
125     static public <T> Iterator JavaDoc<T> unique(Iterator JavaDoc<? extends T> iterator) {
126         return new net.sf.jga.util.UniqueIterator<T>(iterator);
127     }
128
129     
130     /**
131      * Returns the contents of the iterator, skipping duplicate entries as determined by the given
132      * comparator.
133      */

134     
135     static public <T> Iterator JavaDoc<T>
136     unique(Iterator JavaDoc<? extends T> iterator, Comparator JavaDoc<? super T> comp) {
137         return new net.sf.jga.util.UniqueIterator<T>(iterator, comp);
138     }
139     
140
141     /**
142      * Returns the contents of the iterator, skipping duplicate entries as determined by the given
143      * predicate. The predicate should return true when the adjacent items are the same.
144      */

145     
146     static public <T> Iterator JavaDoc<T>
147     unique(Iterator JavaDoc<? extends T> iterator, BinaryFunctor<T,T,Boolean JavaDoc> eq) {
148         return new net.sf.jga.util.UniqueIterator<T>(iterator, eq);
149     }
150
151     // ============
152
// IterableCopy
153
// ============
154

155     /**
156      * Appends the contents of the input (skipping duplicate entries) to the output. This version
157      * uses T.equals() to test for equality.
158      */

159
160     static public <T, TCollection extends Collection JavaDoc<? super T>> TCollection
161     unique(Iterable JavaDoc<? extends T> lin, TCollection cout) {
162         return append(cout, unique(lin.iterator()));
163     }
164
165
166     /**
167      * Appends the contents of the input (skipping duplicate entries as determined by the given
168      * comparator) to the output.
169      */

170
171     static public <T, TCollection extends Collection JavaDoc<? super T>> TCollection
172     unique(Iterable JavaDoc<? extends T> lin, Comparator JavaDoc<? super T> comp, TCollection cout) {
173         return append(cout, unique(lin.iterator(), comp));
174     }
175
176
177     /**
178      * Appends the contents of the input (skipping duplicate entries as determined by the given
179      * predicate) to the output.
180      */

181
182     static public <T, TCollection extends Collection JavaDoc<? super T>> TCollection
183     unique(Iterable JavaDoc<? extends T> lin, BinaryFunctor<T,T,Boolean JavaDoc> eq, TCollection cout) {
184         return append(cout, unique(lin.iterator(), eq));
185     }
186
187
188     /**
189      * Produces iterators that will not return the same element twice in succession.
190      * <p>
191      * Copyright &copy; 2005 David A. Hall
192      */

193
194     static public class UniqueIterable<T> implements Iterable JavaDoc<T> {
195
196         // The contents
197
private Iterable JavaDoc<? extends T> _delegate;
198     
199         // The test
200
private BinaryFunctor<T,T,Boolean JavaDoc> _pred;
201
202         /**
203          * Builds a UniqueIterable for the given resource. It will use an EqualTo
204          * predicate by default.
205          * @throws IllegalArgumentException if the base iterable is null
206          */

207         public UniqueIterable(Iterable JavaDoc<? extends T> base) {
208             this(base, new EqualTo<T>());
209         }
210
211         /**
212          * Builds a UniqueIterable for the given base iterator, that uses the given Comparator
213          * @throws IllegalArgumentException if either argument is null
214          */

215         public UniqueIterable(Iterable JavaDoc<? extends T> base, Comparator JavaDoc<? super T> comp) {
216             this(base, new EqualTo<T>(comp));
217         }
218
219
220         /**
221          * Builds a UniqueIterable for the given base iterator that uses the given
222          * predicate to compare successive elements. The predicate should return
223          * TRUE if its first argument is equal to the second.
224          * @throws IllegalArgumentException if the base iterable is null
225          */

226
227         public UniqueIterable(Iterable JavaDoc<? extends T> base, BinaryFunctor<T,T,Boolean JavaDoc> pred) {
228             if (base == null)
229                 throw new IllegalArgumentException JavaDoc( "a base iterable is required");
230         
231             _delegate = base;
232             _pred = pred;
233         }
234
235         // - - - - - - - - - - -
236
// Iterable<T> interface
237
// - - - - - - - - - - -
238

239         public Iterator JavaDoc<T> iterator() {
240             return new net.sf.jga.util.UniqueIterator<T>(_delegate.iterator(), _pred); }
241     
242     }
243
244     
245     /**
246      * Iterator that will not return the same element twice in succession.
247      */

248
249     static public class UniqueIterator<T> implements Iterator JavaDoc<T> {
250         // The base iterator
251
private Iterator JavaDoc<? extends T> _base;
252
253         // The test for equality
254
private BinaryFunctor<T,T,Boolean JavaDoc> _eq;
255
256         // null at startup, TRUE if hasNext() has been called since last next()
257
private Boolean JavaDoc _testedNext;
258
259         // flag indicating that there is at least new element remaining
260
private boolean _hasNext;
261     
262         // previous item returned
263
private T _lastValue;
264
265         // next item to return
266
private T _nextValue;
267
268         /**
269          * Builds a UniqueIterator for the given base iterator, using a test based on the equals()
270          * method of type T.
271          */

272       
273         public UniqueIterator(Iterator JavaDoc<? extends T> base) {
274             this(base, new EqualTo<T>());
275         }
276
277         /**
278          * Builds a UniqueIterator for the given base iterator, using the given comparator.
279          */

280       
281         public UniqueIterator(Iterator JavaDoc<? extends T> base, Comparator JavaDoc<? super T> comp) {
282             this(base, new EqualTo<T>(comp));
283         }
284
285         /**
286          * Builds a UniqueIterator for the given base iterator that uses the given predicate to
287          * compare adjacent elements. The predicate should return true if the adjacent elements
288          * are the same.
289          * @throws IllegalArgumentException if either argument is null
290          */

291
292         public UniqueIterator(Iterator JavaDoc<? extends T> base, BinaryFunctor<T,T,Boolean JavaDoc> eq) {
293             if (base == null)
294                 throw new IllegalArgumentException JavaDoc("base iterator is required");
295
296             if (eq == null)
297                 throw new IllegalArgumentException JavaDoc("functor is required");
298
299             _base = base;
300             _eq = eq;
301         }
302
303         // - - - - - - - - - - -
304
// Iterator<T> interface
305
// - - - - - - - - - - -
306

307         public boolean hasNext() {
308             // make sure this isn't the first time through
309
if (_testedNext != null) {
310
311                 // make sure that we haven't already tested hasNext()
312
if (!_testedNext.booleanValue()) { // autounbox
313

314                     // first test since next() called
315
_testedNext = Boolean.TRUE;
316                     _hasNext = false; // in case we walk off the end
317
while (_base.hasNext()) {
318                         _nextValue = _base.next();
319                         if (_eq.fn(_lastValue, _nextValue).booleanValue()) { // autounbox
320
continue; // skip this value, try the next one
321
}
322                     
323                         _hasNext = true;
324                         break;
325                     }
326                 }
327             }
328             else {
329                 // this is the first time through -- can't call the functor with the
330
// first value (the first value may be null, so we can't take the
331
// chance that it equals the not yet initialized _lastValue member);
332

333                 _testedNext = Boolean.TRUE;
334                 _hasNext = _base.hasNext();
335                 if (_hasNext) {
336                     _nextValue = _base.next();
337                 }
338             }
339         
340             return _hasNext;
341
342         }
343
344         public T next() {
345             // make sure that hasNext() has been called
346
if (_testedNext == null || !_testedNext.booleanValue()) { // autounbox
347
hasNext();
348             }
349
350             // just in case the result of hasNext() has been ignored
351
if (!_hasNext)
352                 throw new NoSuchElementException JavaDoc();
353
354             //stash off the value being returned for future testing
355
_testedNext = Boolean.FALSE;
356             _lastValue = _nextValue;
357             return _nextValue;
358         }
359
360         public void remove() { throw new UnsupportedOperationException JavaDoc(); }
361     }
362 }
363
Popular Tags