001: // ============================================================================
002: // $Id: Unique.java,v 1.4 2006/12/05 04:45:44 davidahall Exp $
003: // Copyright (c) 2006 David A. Hall
004: // ============================================================================
005: // The contents of this file are subject to the Common Development and
006: // Distribution License (CDDL), Version 1.0 (the License); you may not
007: // use this file except in compliance with the License.
008: //
009: // From time to time, the license steward (initially Sun Microsystems,
010: // Inc.), and may publish revised and/or new versions of this License.
011: // You may not use, distribute, or otherwise make this file available
012: // under subsequent versions of the License.
013: //
014: // You should have received a copy of the the License along with this
015: // file: if not, a copy of the License is available at
016: //
017: // http://www.sun.com/cddl/cddl.html
018: //
019: // Alternatively, the contents of this file may be used under the terms of the
020: // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
021: // case the provisions of the LGPL are applicable instead of those above. If you
022: // wish to allow use of your version of this file only under the terms of the
023: // LGPL, and not to allow others to use your version of this file under the
024: // terms of the CDDL, indicate your decision by deleting the provisions above
025: // and replace them with the notice and other provisions required by the LGPL.
026: // If you do not delete the provisions above, a recipient may use your version
027: // of this file under the terms of either the CDDL or the LGPL.
028: //
029: // This library is distributed in the hope that it will be useful,
030: // but WITHOUT ANY WARRANTY; without even the implied warranty of
031: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
032: // ============================================================================
033:
034: package net.sf.jga.algorithms;
035:
036: import java.util.Collection;
037: import java.util.Comparator;
038: import java.util.Iterator;
039: import java.util.NoSuchElementException;
040: import net.sf.jga.fn.BinaryFunctor;
041: import net.sf.jga.fn.comparison.EqualTo;
042: import net.sf.jga.util.ArrayUtils;
043:
044: import static net.sf.jga.util.ArrayUtils.*;
045: import static net.sf.jga.util.CollectionUtils.*;
046:
047: /**
048: * Algorithms that eliminate successive duplicate entries from a collection, iteration,
049: * or iterable resource.
050: * <p>
051: * Copyright © 2006 David A. Hall
052: */
053:
054: public class Unique {
055:
056: // ============
057: // Arrays
058: // ============
059:
060: /**
061: * Returns the elements of the array, skipping duplicate entries. This version uses T.equals()
062: * to test for equality.
063: */
064: static public <T> Iterable<T> unique(T[] ts) {
065: return new UniqueIterable<T>(iterable(ts));
066: }
067:
068: /**
069: * Returns the elements of the array, skipping duplicate entries as determined by the given
070: * comparator.
071: */
072: static public <T> Iterable<T> unique(T[] ts,
073: Comparator<? super T> comp) {
074: return new UniqueIterable<T>(iterable(ts), comp);
075: }
076:
077: /**
078: * Returns the elements of the array, skipping duplicate entries as determined by the given
079: * predicate. The predicate should return true when the adjacent items are the same.
080: */
081: static public <T> Iterable<T> unique(T[] ts,
082: BinaryFunctor<T, T, Boolean> eq) {
083: return new UniqueIterable<T>(iterable(ts), eq);
084: }
085:
086: // ============
087: // Iterables
088: // ============
089:
090: /**
091: * Returns the contents of the input, skipping duplicate entries. This version uses T.equals()
092: * to test for equality.
093: */
094: static public <T> Iterable<T> unique(Iterable<? extends T> i) {
095: return new UniqueIterable<T>(i);
096: }
097:
098: /*
099: * Returns the contents of the input, skipping duplicate entries as determined by the given
100: * comparator.
101: */
102: static public <T> Iterable<T> unique(Iterable<? extends T> i,
103: Comparator<? super T> comp) {
104: return new UniqueIterable<T>(i, comp);
105: }
106:
107: /*
108: * Returns the contents of the input, skipping duplicate entries as determined by the given
109: * predicate. The predicate should return true when the adjacent items are the same.
110: */
111: static public <T> Iterable<T> unique(Iterable<? extends T> i,
112: BinaryFunctor<T, T, Boolean> 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<T> unique(Iterator<? extends T> iterator) {
126: return new net.sf.jga.util.UniqueIterator<T>(iterator);
127: }
128:
129: /**
130: * Returns the contents of the iterator, skipping duplicate entries as determined by the given
131: * comparator.
132: */
133:
134: static public <T> Iterator<T> unique(
135: Iterator<? extends T> iterator, Comparator<? super T> comp) {
136: return new net.sf.jga.util.UniqueIterator<T>(iterator, comp);
137: }
138:
139: /**
140: * Returns the contents of the iterator, skipping duplicate entries as determined by the given
141: * predicate. The predicate should return true when the adjacent items are the same.
142: */
143:
144: static public <T> Iterator<T> unique(
145: Iterator<? extends T> iterator,
146: BinaryFunctor<T, T, Boolean> eq) {
147: return new net.sf.jga.util.UniqueIterator<T>(iterator, eq);
148: }
149:
150: // ============
151: // IterableCopy
152: // ============
153:
154: /**
155: * Appends the contents of the input (skipping duplicate entries) to the output. This version
156: * uses T.equals() to test for equality.
157: */
158:
159: static public <T, TCollection extends Collection<? super T>> TCollection unique(
160: Iterable<? extends T> lin, TCollection cout) {
161: return append(cout, unique(lin.iterator()));
162: }
163:
164: /**
165: * Appends the contents of the input (skipping duplicate entries as determined by the given
166: * comparator) to the output.
167: */
168:
169: static public <T, TCollection extends Collection<? super T>> TCollection unique(
170: Iterable<? extends T> lin, Comparator<? super T> comp,
171: TCollection cout) {
172: return append(cout, unique(lin.iterator(), comp));
173: }
174:
175: /**
176: * Appends the contents of the input (skipping duplicate entries as determined by the given
177: * predicate) to the output.
178: */
179:
180: static public <T, TCollection extends Collection<? super T>> TCollection unique(
181: Iterable<? extends T> lin, BinaryFunctor<T, T, Boolean> eq,
182: TCollection cout) {
183: return append(cout, unique(lin.iterator(), eq));
184: }
185:
186: /**
187: * Produces iterators that will not return the same element twice in succession.
188: * <p>
189: * Copyright © 2005 David A. Hall
190: */
191:
192: static public class UniqueIterable<T> implements Iterable<T> {
193:
194: // The contents
195: private Iterable<? extends T> _delegate;
196:
197: // The test
198: private BinaryFunctor<T, T, Boolean> _pred;
199:
200: /**
201: * Builds a UniqueIterable for the given resource. It will use an EqualTo
202: * predicate by default.
203: * @throws IllegalArgumentException if the base iterable is null
204: */
205: public UniqueIterable(Iterable<? extends T> base) {
206: this (base, new EqualTo<T>());
207: }
208:
209: /**
210: * Builds a UniqueIterable for the given base iterator, that uses the given Comparator
211: * @throws IllegalArgumentException if either argument is null
212: */
213: public UniqueIterable(Iterable<? extends T> base,
214: Comparator<? super T> comp) {
215: this (base, new EqualTo<T>(comp));
216: }
217:
218: /**
219: * Builds a UniqueIterable for the given base iterator that uses the given
220: * predicate to compare successive elements. The predicate should return
221: * TRUE if its first argument is equal to the second.
222: * @throws IllegalArgumentException if the base iterable is null
223: */
224:
225: public UniqueIterable(Iterable<? extends T> base,
226: BinaryFunctor<T, T, Boolean> pred) {
227: if (base == null)
228: throw new IllegalArgumentException(
229: "a base iterable is required");
230:
231: _delegate = base;
232: _pred = pred;
233: }
234:
235: // - - - - - - - - - - -
236: // Iterable<T> interface
237: // - - - - - - - - - - -
238:
239: public Iterator<T> iterator() {
240: return new net.sf.jga.util.UniqueIterator<T>(_delegate
241: .iterator(), _pred);
242: }
243:
244: }
245:
246: /**
247: * Iterator that will not return the same element twice in succession.
248: */
249:
250: static public class UniqueIterator<T> implements Iterator<T> {
251: // The base iterator
252: private Iterator<? extends T> _base;
253:
254: // The test for equality
255: private BinaryFunctor<T, T, Boolean> _eq;
256:
257: // null at startup, TRUE if hasNext() has been called since last next()
258: private Boolean _testedNext;
259:
260: // flag indicating that there is at least new element remaining
261: private boolean _hasNext;
262:
263: // previous item returned
264: private T _lastValue;
265:
266: // next item to return
267: private T _nextValue;
268:
269: /**
270: * Builds a UniqueIterator for the given base iterator, using a test based on the equals()
271: * method of type T.
272: */
273:
274: public UniqueIterator(Iterator<? extends T> base) {
275: this (base, new EqualTo<T>());
276: }
277:
278: /**
279: * Builds a UniqueIterator for the given base iterator, using the given comparator.
280: */
281:
282: public UniqueIterator(Iterator<? extends T> base,
283: Comparator<? super T> comp) {
284: this (base, new EqualTo<T>(comp));
285: }
286:
287: /**
288: * Builds a UniqueIterator for the given base iterator that uses the given predicate to
289: * compare adjacent elements. The predicate should return true if the adjacent elements
290: * are the same.
291: * @throws IllegalArgumentException if either argument is null
292: */
293:
294: public UniqueIterator(Iterator<? extends T> base,
295: BinaryFunctor<T, T, Boolean> eq) {
296: if (base == null)
297: throw new IllegalArgumentException(
298: "base iterator is required");
299:
300: if (eq == null)
301: throw new IllegalArgumentException(
302: "functor is required");
303:
304: _base = base;
305: _eq = eq;
306: }
307:
308: // - - - - - - - - - - -
309: // Iterator<T> interface
310: // - - - - - - - - - - -
311:
312: public boolean hasNext() {
313: // make sure this isn't the first time through
314: if (_testedNext != null) {
315:
316: // make sure that we haven't already tested hasNext()
317: if (!_testedNext.booleanValue()) { // autounbox
318:
319: // first test since next() called
320: _testedNext = Boolean.TRUE;
321: _hasNext = false; // in case we walk off the end
322: while (_base.hasNext()) {
323: _nextValue = _base.next();
324: if (_eq.fn(_lastValue, _nextValue)
325: .booleanValue()) { // autounbox
326: continue; // skip this value, try the next one
327: }
328:
329: _hasNext = true;
330: break;
331: }
332: }
333: } else {
334: // this is the first time through -- can't call the functor with the
335: // first value (the first value may be null, so we can't take the
336: // chance that it equals the not yet initialized _lastValue member);
337:
338: _testedNext = Boolean.TRUE;
339: _hasNext = _base.hasNext();
340: if (_hasNext) {
341: _nextValue = _base.next();
342: }
343: }
344:
345: return _hasNext;
346:
347: }
348:
349: public T next() {
350: // make sure that hasNext() has been called
351: if (_testedNext == null || !_testedNext.booleanValue()) { // autounbox
352: hasNext();
353: }
354:
355: // just in case the result of hasNext() has been ignored
356: if (!_hasNext)
357: throw new NoSuchElementException();
358:
359: //stash off the value being returned for future testing
360: _testedNext = Boolean.FALSE;
361: _lastValue = _nextValue;
362: return _nextValue;
363: }
364:
365: public void remove() {
366: throw new UnsupportedOperationException();
367: }
368: }
369: }
|