001: // ============================================================================
002: // $Id: Algorithms.java,v 1.43 2006/12/05 04:48:17 davidahall Exp $
003: // Copyright (c) 2003-2005 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 use this
007: // file except in compliance with the License. You should have received a copy
008: // of the the License along with this file: if not, a copy of the License is
009: // available from Sun Microsystems, Inc.
010: //
011: // http://www.sun.com/cddl/cddl.html
012: //
013: // From time to time, the license steward (initially Sun Microsystems, Inc.) may
014: // publish revised and/or new versions of the License. You may not use,
015: // distribute, or otherwise make this file available under subsequent versions
016: // of the License.
017: //
018: // Alternatively, the contents of this file may be used under the terms of the
019: // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
020: // case the provisions of the LGPL are applicable instead of those above. If you
021: // wish to allow use of your version of this file only under the terms of the
022: // LGPL, and not to allow others to use your version of this file under the
023: // terms of the CDDL, indicate your decision by deleting the provisions above
024: // and replace them with the notice and other provisions required by the LGPL.
025: // If you do not delete the provisions above, a recipient may use your version
026: // of this file under the terms of either the CDDL or the LGPL.
027: //
028: // This library is distributed in the hope that it will be useful,
029: // but WITHOUT ANY WARRANTY; without even the implied warranty of
030: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
031: // ============================================================================
032: package net.sf.jga.util;
033:
034: import java.util.Collection;
035: import java.util.Comparator;
036: import java.util.Iterator;
037: import java.util.List;
038: import java.util.ListIterator;
039: import net.sf.jga.algorithms.Find;
040: import net.sf.jga.algorithms.Filter;
041: import net.sf.jga.algorithms.Merge;
042: import net.sf.jga.algorithms.Summarize;
043: import net.sf.jga.algorithms.Transform;
044: import net.sf.jga.algorithms.Unique;
045: import net.sf.jga.fn.BinaryFunctor;
046: import net.sf.jga.fn.UnaryFunctor;
047: import net.sf.jga.fn.algorithm.ForEach;
048: import net.sf.jga.fn.arithmetic.Arithmetic;
049: import net.sf.jga.fn.arithmetic.ArithmeticFactory;
050: import net.sf.jga.fn.arithmetic.Plus;
051: import net.sf.jga.fn.comparison.EqualTo;
052: import net.sf.jga.fn.comparison.Equality;
053: import net.sf.jga.fn.comparison.NotEqualTo;
054: import net.sf.jga.fn.logical.BinaryNegate;
055: import net.sf.jga.fn.logical.UnaryNegate;
056:
057: /**
058: * Facade for the Algorithms adapted from STL, defined to work primarily with
059: * collections. These algorithms are adapted from STL, with modifications to be
060: * consistent with typical java practice. For example, typical STL algorithms
061: * are defined with pairs of iterators defining a half-open range over some
062: * implied collection. It works in C++ because the STL iterators can be compared
063: * for equality. Java iterators are not guaranteed to be comparable to each
064: * other by contract, so the same signatures wouldn't work.
065: * <p>
066: * Typically, where an STL algorithm would take a pair of iterators, we'll take
067: * a collection. Where an STL algorithm would return an iterator, we'll return
068: * an iterator. Note that it will always be java.lang.Iterator when using
069: * this class: for some of the more powerful uses, use the Iterators class,
070: * which will often return an implementation of Iterator that is tailored for
071: * the semantics of the algorithm that was called.
072: * <p>
073: * The algorithms in this class and the same set of algorithms in the Iterators
074: * class will always return the same results when called with identical
075: * arguments.
076: * <p>
077: * Copyright © 2003-2005 David A. Hall
078: *
079: * @author <a href="mailto:davidahall@users.sf.net">David A. Hall</a>
080: */
081:
082: public class Algorithms {
083:
084: // ----------------------------------------------------------------------
085: // Finding algorithms
086: // ----------------------------------------------------------------------
087:
088: /**
089: * Finds an arbitrary value in a collection using the equals() method.
090: * @return an iterator from the collection whose next() [if it hasNext()]
091: * will return the first instance of the value. If the value is not in the
092: * collection, then the returned iterator's hasNext() will report false.
093: * @deprecated use Find.find() instead
094: */
095: static public <T> Iterator<T> find(
096: Collection<? extends T> collection, T value) {
097: return Find.find(collection, value);
098: }
099:
100: /**
101: * Finds an arbitrary value in a collection using the given Equality
102: * operator.
103: * @return an iterator from the collection whose next() [if it hasNext()]
104: * will return the first instance of the value. If the value is not in the
105: * collection, then the returned iterator's hasNext() will report false.
106: * @deprecated use Find.find() instead
107: */
108: static public <T> Iterator<T> find(
109: Collection<? extends T> collection, T value, Equality<T> eq) {
110: return Find.find(collection, value, eq);
111: }
112:
113: /**
114: * Finds a value in a collection for which the given function returns TRUE.
115: * @return an iterator from the collection whose next() [if it hasNext()]
116: * will return the first instance of the value. If the value is not in the
117: * collection, then the returned iterator's hasNext() will report false.
118: * @deprecated use Find.find() instead
119: */
120: static public <T> Iterator<T> find(
121: Collection<? extends T> collection,
122: UnaryFunctor<T, Boolean> fn) {
123: return Find.find(collection, fn);
124: }
125:
126: // ----------------------------------------------------------------------
127: // Counting algorithms
128: // ----------------------------------------------------------------------
129:
130: /**
131: * Counts the number of occurrences of value in the collection, using the
132: * equals() method of the value
133: * @return the number of instances found
134: * @deprecated use Summarize.count(Iterable,T)
135: */
136: static public <T> long count(Collection<? extends T> collection,
137: T value) {
138: return Summarize.count(collection, value);
139: }
140:
141: /**
142: * Counts the number of occurrences of value in the collection, using the
143: * given equality operator.
144: * @return the number of instances found
145: * @deprectaed use Summarize.count(Iterable,Equality,T)
146: */
147: static public <T> long count(Collection<? extends T> collection,
148: Equality<T> eq, T value) {
149: return Summarize.count(collection, eq, value);
150: }
151:
152: /**
153: * Counts the items in the collection for which the given function returns
154: * true.
155: * @return the number of instances found
156: * @deprecated use Summarize.count(Iterable,UnaryFunctor)
157: */
158: static public <T> long count(Collection<? extends T> collection,
159: UnaryFunctor<T, Boolean> eq) {
160: return Summarize.count(collection, eq);
161: }
162:
163: // ----------------------------------------------------------------------
164: // Adjacent Find algorithms
165: // ----------------------------------------------------------------------
166:
167: /**
168: * Finds adjacent pairs of equivalent values in a collection using the
169: * equals() method.
170: * @return an iterator from the collection whose next() [if it hasNext()]
171: * will return the first of a pair of adjacent values. If no pair of values
172: * exists in the collection, then the returned iterator's hasNext() will
173: * report false.
174: * @deprecated use Find.findAdjacent(Iterable) instead
175: */
176: static public <T> Iterator<T> findAdjacent(
177: Collection<? extends T> collection) {
178: return Find.findAdjacent(collection);
179: }
180:
181: /**
182: * Finds adjacent pairs of equivalent values in a collection for which the
183: * given function returns TRUE.
184: * @return an iterator from the collection whose next() [if it hasNext()]
185: * will return the first of a pair of adjacent values. If no pair of values
186: * exists in the collection, then the returned iterator's hasNext() will
187: * report false.
188: * @deprecated use Find.findAdjacnet(Iterable, BinaryFunctor) instead
189: */
190: static public <T> Iterator<T> findAdjacent(
191: Collection<? extends T> c, BinaryFunctor<T, T, Boolean> bf) {
192: return Find.findAdjacent(c, bf);
193: }
194:
195: // ----------------------------------------------------------------------
196: // FindElement algorithms
197: // ----------------------------------------------------------------------
198:
199: /**
200: * Finds any value from the given collection using the collection's contains() method.
201: * @return an iterator from the first collection whose next() [if it hasNext()] will return
202: * the first instance of any value found in the second collection. If no such value is
203: * found in the first collection, then the returned iterator's hasNext() will report false.
204: * @deprecated use Find.findElement(Iterable,Collection) instead
205: */
206: static public <T> Iterator<T> findElement(
207: Collection<? extends T> c, Collection<? extends T> desired) {
208: return Find.findElement(c, desired);
209: }
210:
211: /**
212: * Finds any value from the given collection using the given functor to determine equivalence.
213: * Each item in the first collection will be compared to every item in the second collection
214: * using the given functor, stopping when the first collection is exhausted or when any
215: * pair returns TRUE.
216: * @return an iterator from the first collection whose next() [if it hasNext()] will return
217: * the first instance of any value in the second collection, where equivelency is determined
218: * by the given functor. If no such value is found in the first collection, then the returned
219: * iterator's hasNext() will report false.
220: * @deprecated use Find.findElement(Iterable,Collection,BinaryFunctor) instead
221: */
222: static public <T> Iterator<T> findElement(
223: Collection<? extends T> c, Collection<? extends T> desired,
224: BinaryFunctor<T, T, Boolean> fn) {
225: return Find.findElement(c, desired, fn);
226: }
227:
228: // ----------------------------------------------------------------------
229: // SequenceMatch algorithms
230: // ----------------------------------------------------------------------
231:
232: /**
233: * Finds the given pattern in the collection using the equals method.
234: * @return an iterator from the first collection whose next() [if it
235: * hasNext()] will return the first element of a sequence that matches
236: * the entire contents of the second collection. If no such match is
237: * found in the first collection, then the returned iterator's hasNext()
238: * will report false. If the pattern is empty, then the iterator points
239: * to the first element in the collection.
240: * @deprecated use Find.findSequence(Iterable,Collection) instead
241: */
242: static public <T> Iterator<T> match(Collection<? extends T> c,
243: Collection<? extends T> pattern) {
244: return Find.findSequence(c, pattern);
245: }
246:
247: /**
248: * Finds the given pattern in the collection using the given functor
249: * to determine equivalence.
250: * @return an iterator from the first collection whose next() [if it
251: * hasNext()] will return the first element of a sequence that matches
252: * the entire contents of the second collection. If no such match is
253: * found in the first collection, then the returned iterator's hasNext()
254: * will report false. If the pattern is empty, then the iterator points
255: * to the first element in the collection.
256: * @deprecated use Find.findSequence(Iterable,Collection,BinaryFunctor) instead
257: */
258: static public <T> Iterator<T> match(Collection<? extends T> c,
259: Collection<? extends T> pattern,
260: BinaryFunctor<T, T, Boolean> eq) {
261: return Find.findSequence(c, pattern, eq);
262: }
263:
264: /**
265: * Finds the point at which two collections differ, using NotEqualTo.
266: * @return an iterator from the first collection whose next() [if it
267: * hasNext()] will return the first element in the collection that does
268: * not equal the corresponding element in the pattern. If the pattern
269: * matches the collection but is longer, than the returned iterator's
270: * hasNext() will report false. If the pattern is empty, then the iterator
271: * points to the first element in the collection.
272: * @deprecated use Find.findMismatch(Iterable,Collection) instead
273: */
274: static public <T> Iterator<T> mismatch(Collection<? extends T> c,
275: Collection<? extends T> pattern) {
276: return Find.findMismatch(c, pattern);
277: }
278:
279: /**
280: * Finds the point at which two collections differ, using the given functor
281: * @return an iterator from the first collection whose next() [if it
282: * hasNext()] will return the first element in the collection for which the
283: * given function returns TRUE when given the element and the correspondind
284: * element in the pattern. If the pattern matches the collection but is
285: * longer, than the returned iterator's hasNext() will report false. If the
286: * pattern is empty, then the iterator points to the first element in the
287: * collection.
288: * @deprecated use Find.findMismatch(Iterable,Pattern,BinaryFunctor) instead
289: */
290: static public <T> Iterator<T> mismatch(Collection<? extends T> c,
291: Collection<? extends T> pattern,
292: BinaryFunctor<T, T, Boolean> neq) {
293: return Find.findMismatch(c, pattern, neq);
294: }
295:
296: // ----------------------------------------------------------------------
297: // FindRepeated algorithms
298: // ----------------------------------------------------------------------
299:
300: /**
301: * Finds arbitrary length runs of a given value in a collection using the
302: * equals() method. Runs of length zero are well-defined: every iteration
303: * begins with a run of length zero of all possible values.
304: * @return an iterator from the collection whose next() [if it hasNext()]
305: * will return the first of n adjacent instances of value. If no run of
306: * values of the requested length exist in the collection, then the returned
307: * iterator's hasNext() will report false.
308: * @deprecated use Find.findRepeated(Iterable,int,T) instead
309: */
310: static public <T> Iterator<T> findRepeated(
311: Collection<? extends T> c, int n, T value) {
312: return Find.findRepeated(c, n, value);
313: }
314:
315: /**
316: * Finds arbitrary length runs of a given value in a collection using the
317: * given Equality operator. Runs of length zero are well-defined: every
318: * iteration begins with a run of length zero of all possible values.
319: * @return an iterator from the collection whose next() [if it hasNext()]
320: * will return the first of n adjacent instances of value. If no run of
321: * values of the requested length exist in the collection, then the returned
322: * iterator's hasNext() will report false.
323: * @deprecated use Find.findRepeated(Iterable,int,T,Equality) instead
324: */
325: static public <T> Iterator<T> findRepeated(
326: Collection<? extends T> c, int n, T value, Equality<T> eq) {
327: return Find.findRepeated(c, n, value, eq);
328: }
329:
330: /**
331: * Finds arbitrary length runs of values in a collection for which the given
332: * functor returns TRUE. Runs of length zero are well-defined: every
333: * iteration begins with a run of length zero of all possible values.
334: * @return an iterator from the collection whose next() [if it hasNext()]
335: * will return the first of n adjacent instances of value. If no run of
336: * values of the requested length exist in the collection, then the returned
337: * iterator's hasNext() will report false.
338: * @deprecated use Find.findRepeated(Iterable,int,T,UnaryFunctor) instead
339: */
340: static public <T> Iterator<T> findRepeated(
341: Collection<? extends T> c, int n,
342: UnaryFunctor<T, Boolean> eq) {
343: return Find.findRepeated(c, n, eq);
344: }
345:
346: // ----------------------------------------------------------------------
347: // ForEach algorithms
348: // ----------------------------------------------------------------------
349:
350: /**
351: * Applies the given UnaryFunctor to every element in the collection, and
352: * returns the Functor. This is useful when the Functor gathers information
353: * on each successive call.
354: * @return the functor, after it has been called once for every element
355: */
356: static public <T, R> UnaryFunctor<T, R> forEach(
357: Collection<? extends T> c, UnaryFunctor<T, R> fn) {
358: new ForEach<T, R>(fn).fn(c.iterator());
359: return fn;
360: }
361:
362: // ----------------------------------------------------------------------
363: // Collection Equality algorithms
364: // ----------------------------------------------------------------------
365:
366: /**
367: * Returns true if the two collections are equal.
368: * @return true if the two collections are equal
369: */
370: static public <T> boolean equal(Collection<? extends T> c1,
371: Collection<? extends T> c2) {
372: return new EqualTo<Collection<? extends T>>().p(c1, c2);
373: }
374:
375: /**
376: * Returns true if the two collections are equal, using the given comparator
377: * to compare the elements in each collection
378: * @return true if the two collections are equal.
379: */
380: static public <T> boolean equal(Collection<? extends T> c1,
381: Collection<? extends T> c2, Comparator<T> comp) {
382: return Iterators.equal(c1.iterator(), c2.iterator(), comp);
383: }
384:
385: /**
386: * Returns true if the two collections are equal, using the given functor
387: * to compare the elements in each collection. The functor is expected to
388: * evaluate its two argments and return true if they are "equal", therefore
389: * this method returns true if the iterations contain the same number of
390: * elements and if the functor returns true for all pairs of elements.
391: * @return true if the two collections are equal
392: */
393: static public <T> boolean equal(Collection<? extends T> c1,
394: Collection<? extends T> c2, BinaryFunctor<T, T, Boolean> eq) {
395: return Iterators.equal(c1.iterator(), c2.iterator(), eq);
396: }
397:
398: // ----------------------------------------------------------------------
399: // Collection Comparison algorithms
400: // ----------------------------------------------------------------------
401:
402: /**
403: * Returns true if the first collection is lexically less than the second,
404: * using the default comparison operation to compare the elements in each
405: * collection.
406: * @return true if c1 < c2
407: */
408: static public <T extends Comparable/*@*/<? super T>/*@*/> boolean lessThan(
409: Collection<? extends T> c1, Collection<? extends T> c2) {
410: return Iterators.lessThan(c1.iterator(), c2.iterator());
411: }
412:
413: /**
414: * Returns true if the first collection is lexically less than the second,
415: * using the given comparator to compare the elements in each collection.
416: * @return true if c1 < c2
417: */
418: static public <T> boolean lessThan(Collection<? extends T> c1,
419: Collection<? extends T> c2, Comparator<T> comp) {
420: return Iterators.lessThan(c1.iterator(), c2.iterator(), comp);
421: }
422:
423: /**
424: * Returns true if the first collection is lexically less than the second,
425: * using the given operator to compare the elements in each collection. The
426: * first is less than the second if it is not longer than the second and if
427: * the first corresponding element that is not equal is less.
428: * @return true if c1 < c2
429: */
430: static public <T> boolean lessThan(Collection<? extends T> c1,
431: Collection<? extends T> c2, BinaryFunctor<T, T, Boolean> lt) {
432: return Iterators.lessThan(c1.iterator(), c2.iterator(), lt);
433: }
434:
435: // ----------------------------------------------------------------------
436: // Minimum/Maximum algorithms
437: // ----------------------------------------------------------------------
438:
439: /**
440: * Finds the position of the minimum value in a collection using the natural
441: * ordering of the collection's elements.
442: * @return an iterator from the collection whose next() [if it hasNext()]
443: * will return the first instance of the minimum value in the collection.
444: * If the collection is empty, then the returned iterator's hasNext() will
445: * report false.
446: */
447: static public <T extends Comparable/*@*/<? super T>/*@*/> Iterator<T> minimum(
448: Collection<? extends T> c) {
449: return Find.find(c, Summarize.min(c));
450: }
451:
452: /**
453: * Finds the position of the minimum value in a collection using the given
454: * comparator.
455: * @return an iterator from the collection whose next() [if it hasNext()]
456: * will return the first instance of the minimum value in the collection.
457: * If the collection is empty, then the returned iterator's hasNext() will
458: * report false.
459: */
460: static public <T> Iterator<T> minimum(Collection<? extends T> c,
461: Comparator<T> comp) {
462: return Find.find(c, Summarize.min(c, comp));
463: }
464:
465: /**
466: * Finds the position of the minimum value in a collection using the given
467: * functor to compare elements. The functor is presumed to return the lesser
468: * of its two arguments.
469: * @return an iterator from the collection whose next() [if it hasNext()]
470: * will return the first instance of the minimum value in the collection.
471: * If the collection is empty, then the returned iterator's hasNext() will
472: * report false.
473: */
474: static public <T> Iterator<T> minimum(Collection<? extends T> c,
475: BinaryFunctor<T, T, T> bf) {
476: return Find.find(c, Summarize.min(c, bf));
477: }
478:
479: /**
480: * Finds the minimum value in a collection using the natural ordering of
481: * the collection's elements.
482: * @return the minimum value found in the collection
483: * @deprecated use Summarize.min(Iterable)
484: */
485: static public <T extends Comparable/*@*/<? super T>/*@*/> T minimumValue(
486: Collection<? extends T> c) {
487: return Summarize.min(c);
488: }
489:
490: /**
491: * Finds the minimum value in a collection using the given comparator.
492: * @return the minimum value found in the collection
493: * @deprecated use Summarize.min(Iterable,Comparator)
494: */
495: static public <T> T minimumValue(Collection<? extends T> c,
496: Comparator<T> comp) {
497: return Summarize.min(c, comp);
498: }
499:
500: /**
501: * Finds the minimum value in a collection using the given functor to
502: * compare elements. The functor is presumed to return the lesser of
503: * its two arguments.
504: * @return the minimum value found in the collection
505: * @deprecated use Summarize.min(Iterable,BinaryFunctor)
506: */
507: static public <T> T minimumValue(Collection<? extends T> c,
508: BinaryFunctor<T, T, T> bf) {
509: return Summarize.min(c, bf);
510: }
511:
512: /**
513: * Finds the position of the maximum value in a collection using the natural
514: * ordering of the collection's elements.
515: * @return an iterator from the collection whose next() [if it hasNext()]
516: * will return the first instance of the maximum value in the collection.
517: * If the collection is empty, then the returned iterator's hasNext() will
518: * report false.
519: */
520: static public <T extends Comparable/*@*/<? super T>/*@*/> Iterator<T> maximum(
521: Collection<? extends T> c) {
522: return Find.find(c, Summarize.max(c));
523: }
524:
525: /**
526: * Finds the position of the maximum value in a collection using the given
527: * comparator.
528: * @return an iterator from the collection whose next() [if it hasNext()]
529: * will return the first instance of the maximum value in the collection.
530: * If the collection is empty, then the returned iterator's hasNext() will
531: * report false.
532: */
533: static public <T> Iterator<T> maximum(Collection<? extends T> c,
534: Comparator<T> comp) {
535: return Find.find(c, Summarize.max(c, comp));
536: }
537:
538: /**
539: * Finds the position of the maximum value in a collection using the given
540: * functor to compare elements. The functor is presumed to return the
541: * greater of its two arguments.
542: * @return an iterator from the collection whose next() [if it hasNext()]
543: * will return the first instance of the maximum value in the collection.
544: * If the collection is empty, then the returned iterator's hasNext() will
545: * report false.
546: */
547: static public <T> Iterator<T> maximum(Collection<? extends T> c,
548: BinaryFunctor<T, T, T> bf) {
549: return Find.find(c, Summarize.max(c, bf));
550: }
551:
552: /**
553: * Finds the maximum value in a collection using the natural ordering of
554: * the collection's elements.
555: * @return the maximum value found in the collection
556: * @deprecated use Summarize.max(Iterable)
557: */
558: static public <T extends Comparable/*@*/<? super T>/*@*/> T maximumValue(
559: Collection<? extends T> c) {
560: return Summarize.max(c);
561: }
562:
563: /**
564: * Finds the maximum value in a collection using the given comparator.
565: * @return the maximum value found in the collection
566: * @deprecated use Summarize.max(Iterable,Comparator)
567: */
568: static public <T> T maximumValue(Collection<? extends T> c,
569: Comparator<T> comp) {
570: return Summarize.max(c, comp);
571: }
572:
573: /**
574: * Finds the maximum value in a collection using the given functor to
575: * compare elements. The functor is presumed to return the greater of
576: * its two arguments.
577: * @return the maximum value found in the collection
578: * @deprecated use Summarize(Iterable,BinaryFunctor)
579: */
580: static public <T> T maximumValue(Collection<? extends T> c,
581: BinaryFunctor<T, T, T> fn) {
582: return Summarize.max(c, fn);
583: }
584:
585: // ----------------------------------------------------------------------
586: // Accumulate algorithms
587: // ----------------------------------------------------------------------
588:
589: /**
590: * Adds each number in the collection, returning the sum.
591: * @return the final sum. If the collection is empty, then zero is
592: * returned
593: * @deprecated use Summarize.sum(Class,Iterable)
594: */
595: static public <T extends Number> T accumulate(Class<T> type,
596: Collection<T> c) {
597: return Summarize.sum(type, c);
598: }
599:
600: /**
601: * Applies the binary functor to each number in the collection, returning
602: * the final result. Along with each number is passed the result of the
603: * previous call of the functor (or zero for the first call to the functor).
604: * The elements in the collection are always passed in the 2nd postion.
605: * @return the final result. If the collection is empty, then zero is
606: * returned
607: * @deprecated use Summarize.accumulate(Iterable,BinaryFunctor) or
608: * Summarize.accumulate(Iterable,T,BinaryFunctor), passing an
609: * appropriate starting value (typically 0 or 1).
610: */
611: static public <T extends Number> T accumulate(Class<T> type,
612: Collection<T> c, BinaryFunctor<T, T, T> fn) {
613: Arithmetic<T> _math = ArithmeticFactory.getArithmetic(type);
614: if (_math == null) {
615: throw new IllegalArgumentException();
616: }
617:
618: return Summarize.accumulate(c, _math.zero(), fn);
619: }
620:
621: /**
622: * Applies the binary functor to each element in the collection, returning
623: * the final result. Along with each element is passed the result of the
624: * previous call of the functor (or the initial value for the first call
625: * to the functor). The elements in the collection are always passed in the
626: * 2nd postion.
627: * @return the final result. If the collection is empty, then the initial
628: * value is returned
629: * @deprecated use Summarize.accumulate(Iterable,T,BinaryFunctor)
630: */
631: static public <T> T accumulate(Collection<T> c, T initial,
632: BinaryFunctor<T, T, T> fn) {
633: return Summarize.accumulate(c, initial, fn);
634: }
635:
636: // ----------------------------------------------------------------------
637: // Transform algorithms
638: // ----------------------------------------------------------------------
639:
640: /**
641: * Applies the UnaryFunctor to each element in the list, and replaces
642: * each element with the result. This method would, in an ideal world,
643: * belong in the Collections class, as its signature is more like the
644: * algorithm methods in that class than in Algorithms.
645: */
646: static public <T> void transform(List<T> lin, UnaryFunctor<T, T> uf) {
647: // NOTE: can't be covariant, as it both reads from the list and writes
648: // to it (effectively)
649: ListIterator<T> liter = lin.listIterator();
650: while (liter.hasNext()) {
651: liter.set(uf.fn(liter.next()));
652: }
653: }
654:
655: /**
656: * Applies the UnaryFunctor to each element in the input collection, and
657: * appends the result to the output collection. The output collection will
658: * generally grow as a result of this operation (in contrast with the STL
659: * transform operation, which will not by itself change the size of the
660: * output collection)
661: * @deprecated use Transform.transform(Iterable,UnaryFunctor,Collection)
662: */
663: static public <T, R> Collection<? super R> transformCopy(
664: Collection<? extends T> cin, Collection<? super R> cout,
665: UnaryFunctor<T, R> uf) {
666: return Transform.transform(cin, uf, cout);
667: }
668:
669: /**
670: * Applies the BinaryFunctor to corresponding elements of the two input
671: * collections, and appends the result to the output collection. The
672: * output collection will generally grow as a result of this operation (in
673: * contrast with the STL transform operation, which will not by itself
674: * change the size of the output collection)
675: * @deprecated use Transform.transform(Iterable,Iterable,BinaryFunctor,Collection)
676: */
677: static public <T1, T2, R> Collection<? super R> transformCopy(
678: Collection<? extends T1> c1, Collection<? extends T2> c2,
679: Collection<? super R> cout, BinaryFunctor<T1, T2, R> bf) {
680: return Transform.transform((Collection<T1>) c1,
681: (Collection<T2>) c2, bf, cout);
682: }
683:
684: // ----------------------------------------------------------------------
685: // replaceAll algorithms
686: // ----------------------------------------------------------------------
687:
688: /**
689: * Tests each element in the list, and replaces elements that pass with
690: * the given value. This method would, in an ideal world, belong in the
691: * Collections class, as its signature is more like the algorithm methods
692: * in that class than in Algorithms.
693: */
694: static public <T> void replaceAll(List<T> lin,
695: UnaryFunctor<T, Boolean> uf, T value) {
696: // NOTE: can't be covariant, as it both reads from the list and writes
697: // to it (effectively)
698: ListIterator<T> liter = lin.listIterator();
699: while (liter.hasNext()) {
700: if (uf.fn(liter.next()).booleanValue()) {
701: liter.set(value);
702: }
703: }
704: }
705:
706: /**
707: * Copies each element in the input collection to the output collection,
708: * except that those elements that pass the given test are replaced with the
709: * constant value.
710: * @deprecated use Transform.replace(Iterable,UnaryFunctor,T,Collection)
711: */
712: static public <T, R> Collection<? super T> replaceAllCopy(
713: Collection<? extends T> cin, Collection<? super T> cout,
714: UnaryFunctor<T, Boolean> test, T value) {
715: return Transform.replace(cin, test, value, cout);
716: }
717:
718: // ----------------------------------------------------------------------
719: // filter algorithms
720: // ----------------------------------------------------------------------
721:
722: /**
723: * removes all instances of the given element from the list
724: */
725: static public <T> void removeAll(List<? extends T> lin, T value) {
726: removeAll(lin, new EqualTo<T>().bind2nd(value));
727: }
728:
729: /**
730: * removes all instances of the given element from the list
731: */
732: static public <T> void removeAll(List<? extends T> lin, T value,
733: Equality<T> eq) {
734: removeAll(lin, eq.bind2nd(value));
735: }
736:
737: /**
738: * removes all elements from the list for which the functor returns TRUE
739: */
740: static public <T> void removeAll(List<? extends T> lin,
741: UnaryFunctor<T, Boolean> uf) {
742: ListIterator<? extends T> liter = lin.listIterator();
743: while (liter.hasNext()) {
744: if (uf.fn(liter.next()).booleanValue()) {
745: liter.remove();
746: }
747: }
748: }
749:
750: /**
751: * Copies each element in the input collection except those equal to the
752: * given value to the output collection,
753: * @deprecated use Fitler.remove(Iterable,T,Collection);
754: */
755: static public <T> Collection<? super T> removeAllCopy(
756: Collection<? extends T> cin, Collection<? super T> cout,
757: T value) {
758: return Filter.remove(cin, value, cout);
759: }
760:
761: /**
762: * Copies each element in the input collection except those equal to the
763: * given value (using the given Equality operator) to the output collection,
764: * @deprecated use Filter.remove(Iterable,T,Equality,Collection);
765: */
766: static public <T> Collection<? super T> removeAllCopy(
767: Collection<? extends T> cin, Collection<? super T> cout,
768: T value, Equality<T> eq) {
769: return Filter.remove(cin, value, eq, cout);
770: }
771:
772: /**
773: * Copies each element in the input collection except those for which the
774: * given function returns TRUE to the output collection.
775: * @deprecated use Filter.remove(Iterable,UnaryFunctor,Collection)
776: */
777: static public <T> Collection<? super T> removeAllCopy(
778: Collection<? extends T> cin, Collection<? super T> cout,
779: UnaryFunctor<T, Boolean> pred) {
780: return Filter.remove(cin, pred, cout);
781: }
782:
783: // ----------------------------------------------------------------------
784: // unique algorithms
785: // ----------------------------------------------------------------------
786:
787: /**
788: * removes all adjacent duplicate values in the given list, using equals()
789: * to compare adjacent elements
790: */
791: static public <T> void unique(List<? extends T> lin) {
792: unique(lin, new EqualTo<T>());
793: }
794:
795: /**
796: * removes all adjacent duplicate values in the given list, using the given
797: * functor to compare adjacent elements
798: */
799: static public <T> void unique(List<? extends T> lin,
800: BinaryFunctor<T, T, Boolean> eq) {
801: ListIterator<? extends T> liter = lin.listIterator();
802:
803: T last = null;
804: // skip the first element, if there is one
805: if (liter.hasNext())
806: last = liter.next();
807:
808: while (liter.hasNext()) {
809: T next = liter.next();
810: if (eq.fn(last, next).booleanValue()) {
811: liter.remove();
812: } else {
813: last = next;
814: }
815: }
816: }
817:
818: /**
819: * Copies the elements from the input collection to the output collection,
820: * skipping adjacent duplicate elements.
821: * @deprecated use Unique.unique(Iterable,Collection)
822: */
823: static public <T, CT extends Collection<? super T>> CT uniqueCopy(
824: Collection<? extends T> cin, CT cout) {
825: return Unique.unique(cin, cout);
826: }
827:
828: /**
829: * Copies the elements from the input collection to the output collection,
830: * skipping adjacent duplicate elements.
831: * @deprecated use Unique.unique(Iterable,BinaryFunctor,Collection)
832: */
833: static public <T, CT extends Collection<? super T>> CT uniqueCopy(
834: Collection<? extends T> cin, CT cout,
835: BinaryFunctor<T, T, Boolean> eq) {
836: return Unique.unique(cin, eq, cout);
837: }
838:
839: // ----------------------------------------------------------------------
840: // merge algorithms
841: // ----------------------------------------------------------------------
842:
843: /**
844: * merges two collections, appending values to the output collection
845: * @deprecated use Merge.merge(Iterable,Iterable,Collection)
846: */
847: static public <T extends Comparable/*@*/<? super T>/*@*/> Collection<? super T> mergeCopy(
848: Collection<? extends T> cin1, Collection<? extends T> cin2,
849: Collection<? super T> cout) {
850: return Merge.merge(cin1, cin2, cout);
851: }
852:
853: /**
854: * merges two collections using the given comparator, appending values to
855: * the output collection
856: * @deprecated use Merge.merge(Iterable,Iterable,Comparator,Collection)
857: */
858: static public <T> Collection<? super T> mergeCopy(
859: Collection<? extends T> cin1, Collection<? extends T> cin2,
860: Collection<? super T> cout, Comparator<T> comp) {
861: return Merge.merge(cin1, cin2, comp, cout);
862: }
863:
864: // ----------------------------------------------------------------------
865: // utilities (deprecated: moved to CollectionUtils)
866: // ----------------------------------------------------------------------
867:
868: /**
869: * Adds all of the elements of the iterator to the collection. If necessary and possible,
870: * the collection will be enlarged: if enlarging the collection is not possible, then a
871: * runtime exception will be thrown. This is an augmentation of the
872: * Collection.addAll(Collection) API method.
873: * @returns true if the state of the collection was changed.
874: * @deprecated use CollectionUtils.addAll
875: */
876: static public <T> boolean addAll(Collection<? super T> cout,
877: Iterator<T> iter) {
878: return CollectionUtils.addAll(cout, iter);
879: }
880:
881: /**
882: * Adds all of the elements of the iterator to the collection and returns the collection.
883: * If necessary and possible, the collection will be enlarged: if enlarging the collection
884: * is not possible, then a runtime exception is thrown.
885: * @deprecated use CollectionUtils.append
886: */
887: static public <T, TCollection extends Collection<? super T>> TCollection append(
888: TCollection cout, Iterator<T> iter) {
889: return CollectionUtils.append(cout, iter);
890: }
891:
892: /**
893: * Adds all of the arguments to the collection and returns the collection. If necessary
894: * and possible, the collection will be enlarged: if enlarging the collection is not
895: * possible, then the runtime exception thrown. A similar method exists in Java 1.5,
896: * although it returns boolean rather than the collection.
897: * @deprecated use CollectionUtils.append
898: */
899: static public <T, TCollection extends Collection<? super T>> TCollection append(
900: TCollection cout, T... values) {
901: return CollectionUtils.append(cout, values);
902: }
903: }
|