0001: // ============================================================================
0002: // $Id: Find.java,v 1.3 2006/12/16 16:48:58 davidahall Exp $
0003: // Copyright (c) 2005 David A. Hall
0004: // ============================================================================
0005: // The contents of this file are subject to the Common Development and
0006: // Distribution License (CDDL), Version 1.0 (the License); you may not use this
0007: // file except in compliance with the License. You should have received a copy
0008: // of the the License along with this file: if not, a copy of the License is
0009: // available from Sun Microsystems, Inc.
0010: //
0011: // http://www.sun.com/cddl/cddl.html
0012: //
0013: // From time to time, the license steward (initially Sun Microsystems, Inc.) may
0014: // publish revised and/or new versions of the License. You may not use,
0015: // distribute, or otherwise make this file available under subsequent versions
0016: // of the License.
0017: //
0018: // Alternatively, the contents of this file may be used under the terms of the
0019: // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
0020: // case the provisions of the LGPL are applicable instead of those above. If you
0021: // wish to allow use of your version of this file only under the terms of the
0022: // LGPL, and not to allow others to use your version of this file under the
0023: // terms of the CDDL, indicate your decision by deleting the provisions above
0024: // and replace them with the notice and other provisions required by the LGPL.
0025: // If you do not delete the provisions above, a recipient may use your version
0026: // of this file under the terms of either the CDDL or the LGPL.
0027: //
0028: // This library is distributed in the hope that it will be useful,
0029: // but WITHOUT ANY WARRANTY; without even the implied warranty of
0030: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
0031: // ============================================================================
0032:
0033: package net.sf.jga.algorithms;
0034:
0035: import java.util.Arrays;
0036: import java.util.Collection;
0037: import java.util.Comparator;
0038: import java.util.Iterator;
0039: import java.util.NoSuchElementException;
0040: import net.sf.jga.fn.BinaryFunctor;
0041: import net.sf.jga.fn.UnaryFunctor;
0042: import net.sf.jga.fn.algorithm.ElementOf;
0043: import net.sf.jga.fn.comparison.EqualTo;
0044: import net.sf.jga.fn.comparison.Equality;
0045: import net.sf.jga.fn.comparison.NotEqualTo;
0046: import net.sf.jga.util.EmptyIterator;
0047: import net.sf.jga.util.FindIterator;
0048: import net.sf.jga.util.LookAheadIterator;
0049:
0050: import static net.sf.jga.fn.comparison.ComparisonFunctors.*;
0051: import static net.sf.jga.util.ArrayUtils.*;
0052:
0053: /**
0054: * Algorithms that return an iterator pointing at the first/next element of the input
0055: * that meets some condition.
0056: */
0057:
0058: public class Find {
0059:
0060: // ============
0061: // Arrays
0062: // ============
0063:
0064: /**
0065: * Finds an arbitrary value in the array using the equals() method.
0066: * @return an iterator whose next() [if it hasNext()]
0067: * will return the first instance of the value. If the value is not in the
0068: * array, then the returned iterator's hasNext() will report false.
0069: */
0070: static public <T> Iterator<T> find(T[] ts, T value) {
0071: return find(iterate(ts), equalTo(value));
0072: }
0073:
0074: /**
0075: * Finds an arbitrary value in the array using the given Comparator.
0076: * @return an iterator whose next() [if it hasNext()]
0077: * will return the first instance of the value. If the value is not in the
0078: * array, then the returned iterator's hasNext() will report false.
0079: */
0080: static public <T> Iterator<T> find(T[] ts, T value,
0081: Comparator<? super T> comp) {
0082: return find(iterate(ts), equalTo(comp, value));
0083: }
0084:
0085: /**
0086: * Finds an arbitrary value in the array using the given Equality operator.
0087: * @return an iterator whose next() [if it hasNext()]
0088: * will return the first instance of the value. If the value is not in the
0089: * array, then the returned iterator's hasNext() will report false.
0090: */
0091: static public <T> Iterator<T> find(T[] ts, T value, Equality<T> eq) {
0092: return find(iterate(ts), equalTo(eq, value));
0093: }
0094:
0095: /**
0096: * Finds a value in the input for which the given function returns TRUE.
0097: * @return an iterator whose next() [if it hasNext()]
0098: * will return the first instance of such a value. If no such value is in the
0099: * array, then the returned iterator's hasNext() will report false.
0100: */
0101: static public <T> Iterator<T> find(T[] ts,
0102: UnaryFunctor<T, Boolean> fn) {
0103: return find(iterate(ts), fn);
0104: }
0105:
0106: /**
0107: * Finds first/next element in the array that is also in the values array.
0108: * @return an iterator whose next() [if it hasNext()] will return the first instance of any
0109: * element found in the array of values. If no such element is found then the returned
0110: * iterator's hasNext() will report false.
0111: */
0112: static public <T> Iterator<T> findElement(T[] ts, T[] values) {
0113: return find(iterate(ts), elementOf(values));
0114: }
0115:
0116: /**
0117: * Finds first/next element in the array that is also in the collection of values, using
0118: * the collection's contains() method.
0119: * @return an iterator whose next() [if it hasNext()] will return the first instance of any
0120: * element found in the collection of values. If no such element is found then the returned
0121: * iterator's hasNext() will report false.
0122: */
0123: static public <T> Iterator<T> findElement(T[] ts,
0124: Collection<? extends T> values) {
0125: return find(iterate(ts), elementOf(values));
0126: }
0127:
0128: /**
0129: * Finds first/next element in the array that is also in the values array, using
0130: * the given Comparator to compare values.
0131: * @return an iterator whose next() [if it hasNext()] will return the first instance of any
0132: * element found in the array of values. If no such element is found then the returned
0133: * iterator's hasNext() will report false.
0134: */
0135: static public <T> Iterator<T> findElement(T[] ts, T[] values,
0136: Comparator<? super T> comp) {
0137: return find(iterate(ts), elementOf(values, comp));
0138: }
0139:
0140: /**
0141: * Finds first/next element in the array that is also in the values collection, using
0142: * the given functor to compare values.
0143: * @return an iterator whose next() [if it hasNext()] will return the first instance of any
0144: * element found in collection of values. If no such value is found then the returned
0145: * iterator's hasNext() will report false.
0146: */
0147: static public <T> Iterator<T> findElement(T[] ts,
0148: Collection<? extends T> values, Comparator<? super T> comp) {
0149: return find(iterate(ts), elementOf(values, comp));
0150: }
0151:
0152: /**
0153: * Finds first/next element in the array that is also in the values array, using
0154: * the given functor to compare values.
0155: * @return an iterator whose next() [if it hasNext()] will return the first instance of any
0156: * element found in the array of values. If no such element is found then the returned
0157: * iterator's hasNext() will report false.
0158: */
0159: static public <T> Iterator<T> findElement(T[] ts, T[] values,
0160: BinaryFunctor<T, T, Boolean> bf) {
0161: return find(iterate(ts), elementOf(values, bf));
0162: }
0163:
0164: /**
0165: * Finds first/next element in the input that is in the values collection, using
0166: * the given functor to compare values.
0167: * @return an iterator whose next() [if it hasNext()] will return the first instance of any
0168: * element found in collection of values. If no such value is found then the returned
0169: * iterator's hasNext() will report false.
0170: */
0171: static public <T> Iterator<T> findElement(T[] ts,
0172: Collection<? extends T> values,
0173: BinaryFunctor<T, T, Boolean> bf) {
0174: return find(iterate(ts), elementOf(values, bf));
0175: }
0176:
0177: /**
0178: * Locates the first/next pair of adjacent elements in the array that
0179: * are the same value, using the equals() method.
0180: * @return an iterator whose next() [if it hasNext()] points to the first of
0181: * a pair of adjacent equivalent values. If no such pair exists, then the
0182: * iterator's hasNext() will be false.
0183: */
0184: static public <T> Iterator<T> findAdjacent(T[] ts) {
0185: return findAdjacent(iterate(ts), new EqualTo<T>());
0186: }
0187:
0188: /**
0189: * Locates the first/next pair of adjacent elements in the array that
0190: * are the same value, using the given comparator.
0191: * @return an iterator whose next() [if it hasNext()] points to the first of
0192: * a pair of adjacent equivalent values. If no such pair exists, then the
0193: * iterator's hasNext() will be false.
0194: */
0195: static public <T> Iterator<T> findAdjacent(T[] ts,
0196: Comparator<? super T> comp) {
0197: return findAdjacent(iterate(ts), new EqualTo<T>(comp));
0198: }
0199:
0200: /**
0201: * Locates the first/next pair of adjacent elements in the array that
0202: * are the same value, using the given functor. The functor should return
0203: * TRUE when two values are to be considered equal.
0204: * @return an iterator whose next() [if it hasNext()] points to the first of
0205: * a pair of adjacent equivalent values. If no such pair exists, then the
0206: * iterator's hasNext() will be false.
0207: */
0208: static public <T> Iterator<T> findAdjacent(T[] ts,
0209: BinaryFunctor<T, T, Boolean> eq) {
0210: return findAdjacent(iterate(ts), eq);
0211: }
0212:
0213: /**
0214: * Finds first/next arbitrary length run of a given value in the input. Runs of length zero
0215: * are well-defined: every input begins with a run of length zero of all possible values.
0216: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0217: * the first of n adjacent instances of value. If no run of values of the requested length
0218: * exist in the iteration, then the returned iterator's hasNext() will report false.
0219: */
0220: static public <T> Iterator<T> findRepeated(T[] ts, int count,
0221: T value) {
0222: return findRepeated(iterate(ts), count, equalTo(value));
0223: }
0224:
0225: /**
0226: * Finds first/next arbitrary length run of a given value in the input using the given
0227: * comparator. Runs of length zero are well-defined: every input begins with
0228: * a run of length zero of all possible values.
0229: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0230: * the first of n adjacent instances of value. If no run of values of the requested length
0231: * exist in the iteration, then the returned iterator's hasNext() will report false.
0232: */
0233: static public <T> Iterator<T> findRepeated(T[] ts, int count,
0234: T value, Comparator<? super T> comp) {
0235: return findRepeated(iterate(ts), count, equalTo(comp, value));
0236: }
0237:
0238: /**
0239: * Finds first/next arbitrary length run of a given value in the input using the given
0240: * equality function. Runs of length zero are well-defined: every input begins with
0241: * a run of length zero of all possible values.
0242: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0243: * the first of n adjacent instances of value. If no run of values of the requested length
0244: * exist in the iteration, then the returned iterator's hasNext() will report false.
0245: */
0246: static public <T> Iterator<T> findRepeated(T[] ts, int count,
0247: T value, Equality<T> eq) {
0248: return findRepeated(iterate(ts), count, equalTo(eq, value));
0249: }
0250:
0251: /**
0252: * Finds first/next arbitrary length run of elements in the input for which the
0253: * given function returns TRUE. Runs of length zero are well-defined: every
0254: * input begins with a run of length zero of all possible values.
0255: * @return an iterator based on the given iterator whose next() [if it
0256: * hasNext()] will return the first of n adjacent instances of value. If no
0257: * run of values of the requested length exist in the iteration, then the
0258: * returned iterator's hasNext() will report false.
0259: */
0260: static public <T> Iterator<T> findRepeated(T[] ts, int count,
0261: UnaryFunctor<T, Boolean> eq) {
0262: return findRepeated(iterate(ts), count, eq);
0263: }
0264:
0265: /**
0266: * Finds the given pattern in the input using the equals method.
0267: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0268: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0269: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0270: */
0271: static public <T> Iterator<T> findSequence(T[] ts, T[] pattern) {
0272: return findSequence(iterate(ts), Arrays.asList(pattern),
0273: new EqualTo<T>());
0274: }
0275:
0276: /**
0277: * Finds the given pattern in the input using the equals method.
0278: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0279: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0280: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0281: */
0282: static public <T> Iterator<T> findSequence(T[] ts,
0283: Collection<? extends T> pattern) {
0284: return findSequence(iterate(ts), pattern, new EqualTo<T>());
0285: }
0286:
0287: /**
0288: * Finds the given pattern in the input using the given comparator to determine equivalence.
0289: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0290: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0291: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0292: */
0293: static public <T> Iterator<T> findSequence(T[] ts, T[] pattern,
0294: Comparator<? super T> comp) {
0295: return findSequence(iterate(ts), Arrays.asList(pattern),
0296: new EqualTo<T>(comp));
0297: }
0298:
0299: /**
0300: * Finds the given pattern in the input using the given comparator to determine equivalence.
0301: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0302: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0303: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0304: */
0305: static public <T> Iterator<T> findSequence(T[] ts,
0306: Collection<? extends T> pattern, Comparator<T> comp) {
0307: return findSequence(iterate(ts), pattern, new EqualTo<T>(comp));
0308: }
0309:
0310: /**
0311: * Finds the given pattern in the input using the given functor to determine equivalence.
0312: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0313: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0314: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0315: */
0316: static public <T> Iterator<T> findSequence(T[] ts, T[] pattern,
0317: BinaryFunctor<T, T, Boolean> fn) {
0318: return findSequence(iterate(ts), Arrays.asList(pattern), fn);
0319: }
0320:
0321: /**
0322: * Finds the given pattern in the input using the given functor to determine equivalence.
0323: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0324: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0325: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0326: */
0327: static public <T> Iterator<T> findSequence(T[] ts,
0328: Collection<? extends T> pattern,
0329: BinaryFunctor<T, T, Boolean> fn) {
0330: return findSequence(iterate(ts), pattern, fn);
0331: }
0332:
0333: /**
0334: * Finds the point at which the array differs from the pattern.
0335: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0336: * does not match the corresponding element in the pattern. If the pattern matches the array
0337: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0338: * the array but is shorter, the returned iterator will point at the next element in the array
0339: * after the length of the pattern.
0340: */
0341: static public <T> Iterator<T> findMismatch(T[] ts, T[] pattern) {
0342: return findMismatch(iterate(ts), Arrays.asList(pattern),
0343: new NotEqualTo<T>());
0344: }
0345:
0346: /**
0347: * Finds the point at which the array differs from the pattern.
0348: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0349: * does not match the corresponding element in the pattern. If the pattern matches the array
0350: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0351: * the array but is shorter, the returned iterator will point at the next element in the array
0352: * after the length of the pattern.
0353: */
0354: static public <T> Iterator<T> findMismatch(T[] ts,
0355: Collection<? extends T> pattern) {
0356: return findMismatch(iterate(ts), pattern, new NotEqualTo<T>());
0357: }
0358:
0359: /**
0360: * Finds the point at which the array differs from the pattern, using the given comparator to
0361: * determine the mismatch.
0362: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0363: * does not match the corresponding element in the pattern. If the pattern matches the array
0364: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0365: * the array but is shorter, the returned iterator will point at the next element in the array
0366: * after the length of the pattern.
0367: */
0368: static public <T> Iterator<T> findMismatch(T[] ts, T[] pattern,
0369: Comparator<? super T> comp) {
0370: return findMismatch(iterate(ts), Arrays.asList(pattern),
0371: new NotEqualTo<T>(comp));
0372: }
0373:
0374: /**
0375: * Finds the point at which the array differs from the pattern, using the given comparator to
0376: * determine the mismatch.
0377: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0378: * does not match the corresponding element in the pattern. If the pattern matches the array
0379: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0380: * the array but is shorter, the returned iterator will point at the next element in the array
0381: * after the length of the pattern.
0382: */
0383: static public <T> Iterator<T> findMismatch(T[] ts,
0384: Collection<? extends T> pattern, Comparator<? super T> comp) {
0385: return findMismatch(iterate(ts), pattern, new NotEqualTo<T>(
0386: comp));
0387: }
0388:
0389: /**
0390: * Finds the point at which the array differs from the pattern, using the given functor to
0391: * determine the mismatch. The functor should return TRUE if a given pair of elements does
0392: * not match.
0393: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0394: * does not match the corresponding element in the pattern. If the pattern matches the array
0395: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0396: * the array but is shorter, the returned iterator will point at the next element in the array
0397: * after the length of the pattern.
0398: */
0399: static public <T> Iterator<T> findMismatch(T[] ts, T[] pattern,
0400: BinaryFunctor<T, T, Boolean> neq) {
0401: return findMismatch(iterate(ts), Arrays.asList(pattern), neq);
0402: }
0403:
0404: /**
0405: * Finds the point at which the array differs from the pattern, using the given functor to
0406: * determine the mismatch. The functor should return TRUE if a given pair of elements does
0407: * not match.
0408: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0409: * does not match the corresponding element in the pattern. If the pattern matches the array
0410: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0411: * the array but is shorter, the returned iterator will point at the next element in the array
0412: * after the length of the pattern.
0413: */
0414: static public <T> Iterator<T> findMismatch(T[] ts,
0415: Collection<? extends T> pattern,
0416: BinaryFunctor<T, T, Boolean> neq) {
0417: return findMismatch(iterate(ts), pattern, neq);
0418: }
0419:
0420: // ============
0421: // Iterables
0422: // ============
0423:
0424: /**
0425: * Finds an arbitrary value in the input using the equals() method.
0426: * @return an iterator whose next() [if it hasNext()]
0427: * will return the first instance of the value. If the value is not in the
0428: * input, then the returned iterator's hasNext() will report false.
0429: */
0430: static public <T> Iterator<T> find(Iterable<? extends T> iter,
0431: T value) {
0432: return find(iter, equalTo(value));
0433: }
0434:
0435: /**
0436: * Finds an arbitrary value in the input using the given Comparator.
0437: * @return an iterator whose next() [if it hasNext()]
0438: * will return the first instance of the value. If the value is not in the
0439: * input, then the returned iterator's hasNext() will report false.
0440: */
0441: static public <T> Iterator<T> find(Iterable<? extends T> iter,
0442: T value, Comparator<? super T> comp) {
0443: return find(iter, equalTo(comp, value));
0444: }
0445:
0446: /**
0447: * Finds an arbitrary value in the input using the given Equality operator.
0448: * @return an iterator whose next() [if it hasNext()]
0449: * will return the first instance of the value. If the value is not in the
0450: * input, then the returned iterator's hasNext() will report false.
0451: */
0452: static public <T> Iterator<T> find(Iterable<? extends T> iter,
0453: T value, Equality<T> eq) {
0454: return find(iter, equalTo(eq, value));
0455: }
0456:
0457: /**
0458: * Finds a value in the input for which the given function returns TRUE.
0459: * @return an iterator whose next() [if it hasNext()]
0460: * will return the first instance of the value. If the value is not in the
0461: * input, then the returned iterator's hasNext() will report false.
0462: */
0463: static public <T> Iterator<T> find(Iterable<? extends T> iter,
0464: UnaryFunctor<T, Boolean> fn) {
0465: return find(iter.iterator(), fn);
0466: }
0467:
0468: /**
0469: * Finds first/next value in the input that is an element of the given array.
0470: * @return an iterator whose next() [if it hasNext()] will return
0471: * the first instance of any element found in the array of values. If no such element is
0472: * found then the returned iterator's hasNext() will report false.
0473: */
0474: static public <T> Iterator<T> findElement(
0475: Iterable<? extends T> iter, T[] values) {
0476: return find(iter.iterator(), elementOf(values));
0477: }
0478:
0479: /**
0480: * Finds first/next value in the input that is an element of the given collection, using
0481: * the collection's contains() method.
0482: * @return an iterator whose next() [if it hasNext()] will return
0483: * the first instance of any element found in the collection of values. If no such element
0484: * is found then the returned iterator's hasNext() will report false.
0485: */
0486: static public <T> Iterator<T> findElement(
0487: Iterable<? extends T> iter, Collection<? extends T> values) {
0488: return find(iter.iterator(), elementOf(values));
0489: }
0490:
0491: /**
0492: * Finds first/next value in the input that is an element of the given array, using
0493: * the given Comparator to compare values.
0494: * @return an iterator whose next() [if it hasNext()] will return
0495: * the first instance of any element found in the array of values. If no such element is
0496: * found then the returned iterator's hasNext() will report false.
0497: */
0498: static public <T> Iterator<T> findElement(
0499: Iterable<? extends T> iter, T[] values,
0500: Comparator<? super T> comp) {
0501: return find(iter.iterator(), elementOf(values, comp));
0502: }
0503:
0504: /**
0505: * Finds first/next value in the input that is an element of the given collection, using
0506: * the given functor to compare values.
0507: * @return an iterator whose next() [if it hasNext()] will return
0508: * the first instance of any element found in collection of values. If no such value is
0509: * found then the returned iterator's hasNext() will report false.
0510: */
0511: static public <T> Iterator<T> findElement(
0512: Iterable<? extends T> iter, Collection<? extends T> values,
0513: Comparator<? super T> comp) {
0514: return find(iter.iterator(), elementOf(values, comp));
0515: }
0516:
0517: /**
0518: * Finds first/next value in the input that is an element of the given array, using
0519: * the given functor to compare values.
0520: * @return an iterator whose next() [if it hasNext()] will return
0521: * the first instance of any element found in the array of values. If no such element is
0522: * found then the returned iterator's hasNext() will report false.
0523: */
0524: static public <T> Iterator<T> findElement(
0525: Iterable<? extends T> iter, T[] values,
0526: BinaryFunctor<T, T, Boolean> bf) {
0527: return find(iter.iterator(), elementOf(values, bf));
0528: }
0529:
0530: /**
0531: * Finds first/next value in the input that is an element of the given collection, using
0532: * the given functor to compare values.
0533: * @return an iterator whose next() [if it hasNext()] will return
0534: * the first instance of any element found in collection of values. If no such value is
0535: * found then the returned iterator's hasNext() will report false.
0536: */
0537: static public <T> Iterator<T> findElement(
0538: Iterable<? extends T> iter, Collection<? extends T> values,
0539: BinaryFunctor<T, T, Boolean> bf) {
0540: return find(iter.iterator(), elementOf(values, bf));
0541: }
0542:
0543: /**
0544: * Locates the first/next pair of adjacent elements in the input that
0545: * are the same value, using the equals() method.
0546: * @return an iterator whose next() [if it hasNext()] points to the first of
0547: * a pair of adjacent equivalent values. If no such pair exists, then the
0548: * iterator's hasNext() will be false.
0549: */
0550: static public <T> Iterator<T> findAdjacent(
0551: Iterable<? extends T> iter) {
0552: return findAdjacent(iter, new EqualTo<T>());
0553: }
0554:
0555: /**
0556: * Locates the first/next pair of adjacent elements in the input that
0557: * are the same value, using the given comparator.
0558: * @return an iterator whose next() [if it hasNext()] points to the first of
0559: * a pair of adjacent equivalent values. If no such pair exists, then the
0560: * iterator's hasNext() will be false.
0561: */
0562: static public <T> Iterator<T> findAdjacent(
0563: Iterable<? extends T> iter, Comparator<? super T> comp) {
0564: return findAdjacent(iter, new EqualTo<T>(comp));
0565: }
0566:
0567: /**
0568: * Locates the first/next pair of adjacent elements in the input that
0569: * are the same value, using the given functor. The functor should return
0570: * TRUE when two values are to be considered equal.
0571: * @return an iterator whose next() [if it hasNext()] points to the first of
0572: * a pair of adjacent equivalent values. If no such pair exists, then the
0573: * iterator's hasNext() will be false.
0574: */
0575: static public <T> Iterator<T> findAdjacent(
0576: Iterable<? extends T> iter, BinaryFunctor<T, T, Boolean> eq) {
0577: return findAdjacent(iter.iterator(), eq);
0578: }
0579:
0580: /**
0581: * Finds first/next arbitrary length run of a given value in the input. Runs of length zero
0582: * are well-defined: every input begins with a run of length zero of all possible values.
0583: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0584: * the first of n adjacent instances of value. If no run of values of the requested length
0585: * exist in the iteration, then the returned iterator's hasNext() will report false.
0586: */
0587: static public <T> Iterator<T> findRepeated(
0588: Iterable<? extends T> iter, int count, T value) {
0589: return findRepeated(iter.iterator(), count, equalTo(value));
0590: }
0591:
0592: /**
0593: * Finds first/next arbitrary length run of a given value in the input using the given
0594: * comparator. Runs of length zero are well-defined: every input begins with
0595: * a run of length zero of all possible values.
0596: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0597: * the first of n adjacent instances of value. If no run of values of the requested length
0598: * exist in the iteration, then the returned iterator's hasNext() will report false.
0599: */
0600: static public <T> Iterator<T> findRepeated(
0601: Iterable<? extends T> iter, int count, T value,
0602: Comparator<? super T> comp) {
0603: return findRepeated(iter.iterator(), count,
0604: equalTo(comp, value));
0605: }
0606:
0607: /**
0608: * Finds first/next arbitrary length run of a given value in the input using the given
0609: * equality function. Runs of length zero are well-defined: every input begins with
0610: * a run of length zero of all possible values.
0611: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0612: * the first of n adjacent instances of value. If no run of values of the requested length
0613: * exist in the iteration, then the returned iterator's hasNext() will report false.
0614: */
0615: static public <T> Iterator<T> findRepeated(
0616: Iterable<? extends T> iter, int count, T value,
0617: Equality<T> eq) {
0618: return findRepeated(iter.iterator(), count, equalTo(eq, value));
0619: }
0620:
0621: /**
0622: * Finds first/next arbitrary length run of elements in the input for which the
0623: * given function returns TRUE. Runs of length zero are well-defined: every
0624: * input begins with a run of length zero of all possible values.
0625: * @return an iterator based on the given iterator whose next() [if it
0626: * hasNext()] will return the first of n adjacent instances of value. If no
0627: * run of values of the requested length exist in the iteration, then the
0628: * returned iterator's hasNext() will report false.
0629: */
0630: static public <T> Iterator<T> findRepeated(
0631: Iterable<? extends T> iter, int count,
0632: UnaryFunctor<T, Boolean> eq) {
0633: return findRepeated(iter.iterator(), count, eq);
0634: }
0635:
0636: /**
0637: * Finds the given pattern in the input using the equals method.
0638: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0639: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0640: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0641: */
0642: static public <T> Iterator<T> findSequence(
0643: Iterable<? extends T> iter, T[] pattern) {
0644: return findSequence(iter.iterator(), Arrays.asList(pattern),
0645: new EqualTo<T>());
0646: }
0647:
0648: /**
0649: * Finds the given pattern in the input using the equals method.
0650: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0651: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0652: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0653: */
0654: static public <T> Iterator<T> findSequence(
0655: Iterable<? extends T> iter, Collection<? extends T> pattern) {
0656: return findSequence(iter.iterator(), pattern, new EqualTo<T>());
0657: }
0658:
0659: /**
0660: * Finds the given pattern in the input using the given comparator to determine equivalence.
0661: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0662: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0663: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0664: */
0665: static public <T> Iterator<T> findSequence(
0666: Iterable<? extends T> iter, T[] pattern,
0667: Comparator<? super T> comp) {
0668: return findSequence(iter.iterator(), Arrays.asList(pattern),
0669: new EqualTo<T>(comp));
0670: }
0671:
0672: /**
0673: * Finds the given pattern in the input using the given comparator to determine equivalence.
0674: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0675: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0676: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0677: */
0678: static public <T> Iterator<T> findSequence(
0679: Iterable<? extends T> iter,
0680: Collection<? extends T> pattern, Comparator<T> comp) {
0681: return findSequence(iter.iterator(), pattern, new EqualTo<T>(
0682: comp));
0683: }
0684:
0685: /**
0686: * Finds the given pattern in the input using the given functor to determine equivalence.
0687: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0688: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0689: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0690: */
0691: static public <T> Iterator<T> findSequence(
0692: Iterable<? extends T> iter, T[] pattern,
0693: BinaryFunctor<T, T, Boolean> fn) {
0694: return findSequence(iter.iterator(), Arrays.asList(pattern), fn);
0695: }
0696:
0697: /**
0698: * Finds the given pattern in the input using the given functor to determine equivalence.
0699: * @return an iterator whose next() [if it hasNext()] will return the first element of a
0700: * sequence that matches the pattern. If no such match is found, then the returned iterator's
0701: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
0702: */
0703: static public <T> Iterator<T> findSequence(
0704: Iterable<? extends T> iter,
0705: Collection<? extends T> pattern,
0706: BinaryFunctor<T, T, Boolean> fn) {
0707: return findSequence(iter.iterator(), pattern, fn);
0708: }
0709:
0710: /**
0711: * Finds the point at which the input differs from the pattern.
0712: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0713: * does not match the corresponding element in the pattern. If the pattern matches the array
0714: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0715: * the array but is shorter, the returned iterator will point at the next element in the array
0716: * after the length of the pattern.
0717: */
0718: static public <T> Iterator<T> findMismatch(
0719: Iterable<? extends T> iter, T[] pattern) {
0720: return findMismatch(iter.iterator(), Arrays.asList(pattern),
0721: new NotEqualTo<T>());
0722: }
0723:
0724: /**
0725: * Finds the point at which the input differs from the pattern.
0726: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0727: * does not match the corresponding element in the pattern. If the pattern matches the input
0728: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0729: * the input but is shorter, the returned iterator will point at the next element in the input
0730: * after the length of the pattern.
0731: */
0732: static public <T> Iterator<T> findMismatch(
0733: Iterable<? extends T> iter, Collection<? extends T> pattern) {
0734: return findMismatch(iter.iterator(), pattern,
0735: new NotEqualTo<T>());
0736: }
0737:
0738: /**
0739: * Finds the point at which the input differs from the pattern, using the given comparator to
0740: * determine the mismatch.
0741: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0742: * does not match the corresponding element in the pattern. If the pattern matches the array
0743: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0744: * the array but is shorter, the returned iterator will point at the next element in the array
0745: * after the length of the pattern.
0746: */
0747: static public <T> Iterator<T> findMismatch(
0748: Iterable<? extends T> iter, T[] pattern,
0749: Comparator<? super T> comp) {
0750: return findMismatch(iter.iterator(), Arrays.asList(pattern),
0751: new NotEqualTo<T>(comp));
0752: }
0753:
0754: /**
0755: * Finds the point at which the input differs from the pattern, using the given comparator to
0756: * determine the mismatch.
0757: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0758: * does not match the corresponding element in the pattern. If the pattern matches the input
0759: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0760: * the input but is shorter, the returned iterator will point at the next element in the input
0761: * after the length of the pattern.
0762: */
0763: static public <T> Iterator<T> findMismatch(
0764: Iterable<? extends T> iter,
0765: Collection<? extends T> pattern, Comparator<? super T> comp) {
0766: return findMismatch(iter.iterator(), pattern,
0767: new NotEqualTo<T>(comp));
0768: }
0769:
0770: /**
0771: * Finds the point at which the input differs from the pattern, using the given functor to
0772: * determine the mismatch. The functor should return TRUE if a given pair of elements does
0773: * not match.
0774: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0775: * does not match the corresponding element in the pattern. If the pattern matches the array
0776: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0777: * the array but is shorter, the returned iterator will point at the next element in the array
0778: * after the length of the pattern.
0779: */
0780: static public <T> Iterator<T> findMismatch(
0781: Iterable<? extends T> iter, T[] pattern,
0782: BinaryFunctor<T, T, Boolean> neq) {
0783: return findMismatch(iter.iterator(), Arrays.asList(pattern),
0784: neq);
0785: }
0786:
0787: /**
0788: * Finds the point at which the input differs from the pattern, using the given functor to
0789: * determine the mismatch. The functor should return TRUE if a given pair of elements does
0790: * not match.
0791: * @return an iterator based whose next() [if it hasNext()] will return the first element which
0792: * does not match the corresponding element in the pattern. If the pattern matches the array
0793: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
0794: * the array but is shorter, the returned iterator will point at the next element in the array
0795: * after the length of the pattern.
0796: */
0797: static public <T> Iterator<T> findMismatch(
0798: Iterable<? extends T> iter,
0799: Collection<? extends T> pattern,
0800: BinaryFunctor<T, T, Boolean> neq) {
0801: return findMismatch(iter.iterator(), pattern, neq);
0802: }
0803:
0804: // ============
0805: // Iterators
0806: // ============
0807:
0808: /**
0809: * Finds an arbitrary value in the input using the equals() method.
0810: * @return an iterator whose next() [if it hasNext()]
0811: * will return the first instance of the value. If the value is not in the
0812: * input, then the returned iterator's hasNext() will report false.
0813: */
0814: static public <T> Iterator<T> find(Iterator<? extends T> iterator,
0815: T value) {
0816: return find(iterator, equalTo(value));
0817: }
0818:
0819: /**
0820: * Finds an arbitrary value in the input using the given Comparator.
0821: * @return an iterator whose next() [if it hasNext()]
0822: * will return the first instance of the value. If the value is not in the
0823: * input, then the returned iterator's hasNext() will report false.
0824: */
0825: static public <T> Iterator<T> find(Iterator<? extends T> iterator,
0826: T value, Comparator<? super T> comp) {
0827: return find(iterator, equalTo(comp, value));
0828: }
0829:
0830: /**
0831: * Finds an arbitrary value in the input using the given Equality operator.
0832: * @return an iterator whose next() [if it hasNext()]
0833: * will return the first instance of the value. If the value is not in the
0834: * input, then the returned iterator's hasNext() will report false.
0835: */
0836: static public <T> Iterator<T> find(Iterator<? extends T> iterator,
0837: T value, Equality<T> eq) {
0838: return find(iterator, equalTo(eq, value));
0839: }
0840:
0841: /**
0842: * Finds a value in the input for which the given function returns TRUE.
0843: * @return an iterator whose next() [if it hasNext()]
0844: * will return the first instance of such a value. If no such value is in the
0845: * input, then the returned iterator's hasNext() will report false.
0846: */
0847: static public <T> Iterator<T> find(Iterator<? extends T> iterator,
0848: UnaryFunctor<T, Boolean> eq) {
0849: FindIterator<T> finder = finder(iterator);
0850: finder.findNext(eq);
0851: return finder;
0852: }
0853:
0854: /**
0855: * Finds first/next value in the input that is an element of the given array.
0856: * @return an iterator whose next() [if it hasNext()] will return
0857: * the first instance of any element found in the array of values. If no such element is
0858: * found then the returned iterator's hasNext() will report false.
0859: */
0860: static public <T> Iterator<T> findElement(
0861: Iterator<? extends T> iterator, T[] values) {
0862: return find(iterator, elementOf(values));
0863: }
0864:
0865: /**
0866: * Finds first/next value in the input that is an element of the given collection, using
0867: * the collection's contains() method.
0868: * @return an iterator whose next() [if it hasNext()] will return
0869: * the first instance of any element found in the collection of values. If no such element
0870: * is found then the returned iterator's hasNext() will report false.
0871: */
0872: static public <T> Iterator<T> findElement(
0873: Iterator<? extends T> iterator,
0874: Collection<? extends T> values) {
0875: return find(iterator, elementOf(values));
0876: }
0877:
0878: /**
0879: * Finds first/next value in the input that is an element of the given array, using
0880: * the given Comparator to compare values.
0881: * @return an iterator whose next() [if it hasNext()] will return
0882: * the first instance of any element found in the array of values. If no such element is
0883: * found then the returned iterator's hasNext() will report false.
0884: */
0885: static public <T> Iterator<T> findElement(
0886: Iterator<? extends T> iterator, T[] values,
0887: Comparator<? super T> comp) {
0888: return find(iterator, elementOf(values, comp));
0889: }
0890:
0891: /**
0892: * Finds first/next value in the input that is an element of the given collection, using
0893: * the given functor to compare values.
0894: * @return an iterator whose next() [if it hasNext()] will return
0895: * the first instance of any element found in collection of values. If no such value is
0896: * found then the returned iterator's hasNext() will report false.
0897: */
0898: static public <T> Iterator<T> findElement(
0899: Iterator<? extends T> iterator,
0900: Collection<? extends T> values, Comparator<? super T> comp) {
0901: return find(iterator, elementOf(values, comp));
0902: }
0903:
0904: /**
0905: * Finds first/next value in the input that is an element of the given array, using
0906: * the given functor to compare values.
0907: * @return an iterator whose next() [if it hasNext()] will return
0908: * the first instance of any element found in the array of values. If no such element is
0909: * found then the returned iterator's hasNext() will report false.
0910: */
0911: static public <T> Iterator<T> findElement(
0912: Iterator<? extends T> iterator, T[] values,
0913: BinaryFunctor<T, T, Boolean> bf) {
0914: return find(iterator, elementOf(values, bf));
0915: }
0916:
0917: /**
0918: * Finds first/next value in the input that is an element of the given collection, using
0919: * the given functor to compare values.
0920: * @return an iterator whose next() [if it hasNext()] will return
0921: * the first instance of any element found in collection of values. If no such value is
0922: * found then the returned iterator's hasNext() will report false.
0923: */
0924: static public <T> Iterator<T> findElement(
0925: Iterator<? extends T> iterator,
0926: Collection<? extends T> values,
0927: BinaryFunctor<T, T, Boolean> bf) {
0928: return find(iterator, elementOf(values, bf));
0929: }
0930:
0931: /**
0932: * Locates the first/next pair of adjacent elements in an iteration that
0933: * are the same value, using the equals() method.
0934: * @return an iterator whose next() [if it hasNext()] points to the first of
0935: * a pair of adjacent equivalent values. If no such pair exists, then the
0936: * iterator's hasNext() will be false.
0937: */
0938: static public <T> Iterator<T> findAdjacent(
0939: Iterator<? extends T> iterator) {
0940: return findAdjacent(iterator, new EqualTo<T>());
0941: }
0942:
0943: /**
0944: * Locates the first/next pair of adjacent elements in an iteration that
0945: * are the same value, using the given comparator.
0946: * @return an iterator whose next() [if it hasNext()] points to the first of
0947: * a pair of adjacent equivalent values. If no such pair exists, then the
0948: * iterator's hasNext() will be false.
0949: */
0950: static public <T> Iterator<T> findAdjacent(
0951: Iterator<? extends T> iterator, Comparator<? super T> comp) {
0952: return findAdjacent(iterator, new EqualTo<T>(comp));
0953: }
0954:
0955: /**
0956: * Locates the first/next pair of adjacent elements in an iteration that
0957: * are the same value, using the given functor. The functor should return
0958: * TRUE when two values are to be considered equal.
0959: * @return an iterator whose next() [if it hasNext()] points to the first of
0960: * a pair of adjacent equivalent values. If no such pair exists, then the
0961: * iterator's hasNext() will be false.
0962: */
0963: static public <T> Iterator<T> findAdjacent(
0964: Iterator<? extends T> iterator,
0965: BinaryFunctor<T, T, Boolean> eq) {
0966: // return early If the input iterator is finished,
0967: if (!iterator.hasNext()) {
0968: return lookAhead(iterator, 1);
0969: }
0970:
0971: LookAheadIterator<T> lai = lookAhead(iterator, 2);
0972: while (lai.hasNextPlus(2)) {
0973: T arg1 = lai.peek(1);
0974: T arg2 = lai.peek(2);
0975: if (eq.fn(arg1, arg2)) {
0976: return lai;
0977: }
0978:
0979: lai.next();
0980: }
0981:
0982: // didn't find anything, so we advance our working iterator off the end
0983: // and return it.
0984: lai.next();
0985: return lai;
0986: }
0987:
0988: /**
0989: * Finds first/next arbitrary length run of a given value in an iteration. Runs of length zero
0990: * are well-defined: every iteration begins with a run of length zero of all possible values.
0991: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
0992: * the first of n adjacent instances of value. If no run of values of the requested length
0993: * exist in the iteration, then the returned iterator's hasNext() will report false.
0994: */
0995: static public <T> Iterator<T> findRepeated(
0996: Iterator<? extends T> iterator, int count, T value) {
0997: return findRepeated(iterator, count, equalTo(value));
0998: }
0999:
1000: /**
1001: * Finds first/next arbitrary length run of a given value in an iteration using the given
1002: * comparator. Runs of length zero are well-defined: every iteration begins with
1003: * a run of length zero of all possible values.
1004: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
1005: * the first of n adjacent instances of value. If no run of values of the requested length
1006: * exist in the iteration, then the returned iterator's hasNext() will report false.
1007: */
1008: static public <T> Iterator<T> findRepeated(
1009: Iterator<? extends T> iterator, int count, T value,
1010: Comparator<? super T> comp) {
1011: return findRepeated(iterator, count, equalTo(comp, value));
1012: }
1013:
1014: /**
1015: * Finds first/next arbitrary length run of a given value in an iteration using the given
1016: * equality function. Runs of length zero are well-defined: every iteration begins with
1017: * a run of length zero of all possible values.
1018: * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
1019: * the first of n adjacent instances of value. If no run of values of the requested length
1020: * exist in the iteration, then the returned iterator's hasNext() will report false.
1021: */
1022: static public <T> Iterator<T> findRepeated(
1023: Iterator<? extends T> iterator, int count, T value,
1024: Equality<T> eq) {
1025: return findRepeated(iterator, count, equalTo(eq, value));
1026: }
1027:
1028: /**
1029: * Finds first/next arbitrary length run of elements in an iteration for which the
1030: * given function returns TRUE. Runs of length zero are well-defined: every
1031: * iteration begins with a run of length zero of all possible values.
1032: * @return an iterator based on the given iterator whose next() [if it
1033: * hasNext()] will return the first of n adjacent instances of value. If no
1034: * run of values of the requested length exist in the iteration, then the
1035: * returned iterator's hasNext() will report false.
1036: */
1037: static public <T> Iterator<T> findRepeated(
1038: Iterator<? extends T> iterator, int count,
1039: UnaryFunctor<T, Boolean> eq) {
1040: if (!iterator.hasNext() || count == 0) {
1041: return new LookAheadIterator<T>(iterator, 1);
1042: }
1043:
1044: LookAheadIterator<T> lai = lookAhead(iterator, count);
1045:
1046: OUTER: while (lai.hasNextPlus(count)) {
1047:
1048: // ... examine the contents of the look ahead buffer ...
1049: for (int i = 1; i <= count; ++i) {
1050: T arg = lai.peek(i);
1051:
1052: // ... and if we find something in the buffer that isn't
1053: // 'equal', then we'll advance past that point in the iterator
1054: // and try again
1055: if (!eq.fn(arg)) {
1056: for (int j = i; j > 0; --j) {
1057: lai.next();
1058: }
1059:
1060: continue OUTER;
1061: }
1062: }
1063:
1064: // If we safely got off the end of the INNER loop, then we must
1065: // have found the point we're looking for.
1066: return lai;
1067: }
1068:
1069: // didn't find anything, make an iterator that will return false.
1070: return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
1071: }
1072:
1073: /**
1074: * Finds the given pattern in the input using the equals method.
1075: * @return an iterator whose next() [if it hasNext()] will return the first element of a
1076: * sequence that matches the pattern. If no such match is found, then the returned iterator's
1077: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
1078: */
1079: static public <T> Iterator<T> findSequence(
1080: Iterator<? extends T> iterator, T[] pattern) {
1081: return findSequence(iterator, Arrays.asList(pattern),
1082: new EqualTo<T>());
1083: }
1084:
1085: /**
1086: * Finds the given pattern in the input using the equals method.
1087: * @return an iterator whose next() [if it hasNext()] will return the first element of a
1088: * sequence that matches the pattern. If no such match is found, then the returned iterator's
1089: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
1090: */
1091: static public <T> Iterator<T> findSequence(
1092: Iterator<? extends T> iterator,
1093: Collection<? extends T> pattern) {
1094: return findSequence(iterator, pattern, new EqualTo<T>());
1095: }
1096:
1097: /**
1098: * Finds the given pattern in the input using the given comparator to determine equivalence.
1099: * @return an iterator whose next() [if it hasNext()] will return the first element of a
1100: * sequence that matches the pattern. If no such match is found, then the returned iterator's
1101: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
1102: */
1103: static public <T> Iterator<T> findSequence(
1104: Iterator<? extends T> iterator, T[] pattern,
1105: Comparator<? super T> comp) {
1106: return findSequence(iterator, Arrays.asList(pattern),
1107: new EqualTo<T>(comp));
1108: }
1109:
1110: /**
1111: * Finds the given pattern in the collection using the given comparator to determine equivalence.
1112: * @return an iterator whose next() [if it hasNext()] will return the first element of a
1113: * sequence that matches the pattern. If no such match is found, then the returned iterator's
1114: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
1115: */
1116: static public <T> Iterator<T> findSequence(
1117: Iterator<? extends T> iterator,
1118: Collection<? extends T> pattern, Comparator<T> comp) {
1119: return findSequence(iterator, pattern, new EqualTo<T>(comp));
1120: }
1121:
1122: /**
1123: * Finds the given pattern in the collection using the given functor to determine equivalence.
1124: * @return an iterator whose next() [if it hasNext()] will return the first element of a
1125: * sequence that matches the pattern. If no such match is found, then the returned iterator's
1126: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
1127: */
1128: static public <T> Iterator<T> findSequence(
1129: Iterator<? extends T> iterator, T[] pattern,
1130: BinaryFunctor<T, T, Boolean> fn) {
1131: return findSequence(iterator, Arrays.asList(pattern), fn);
1132: }
1133:
1134: /**
1135: * Finds the given pattern in the collection using the given functor to determine equivalence.
1136: * @return an iterator whose next() [if it hasNext()] will return the first element of a
1137: * sequence that matches the pattern. If no such match is found, then the returned iterator's
1138: * hasNext() will report false. If the pattern is empty, then the iterator will not be advanced.
1139: */
1140: static public <T> Iterator<T> findSequence(
1141: Iterator<? extends T> iterator,
1142: Collection<? extends T> pattern,
1143: BinaryFunctor<T, T, Boolean> fn) {
1144: // return early if the input iterator is already finished,
1145: int length = pattern.size();
1146: if (!iterator.hasNext() || length == 0) {
1147: return lookAhead(iterator, 1);
1148: }
1149:
1150: LookAheadIterator<T> lai = lookAhead(iterator, length);
1151:
1152: // So long as the LookAhead has enough room for the repeat count to
1153: // possibly fit, ...
1154:
1155: OUTER: while (lai.hasNextPlus(length)) {
1156: int idx = 1;
1157:
1158: // ... examine the contents of the look ahead buffer ...
1159: for (T obj : pattern) {
1160:
1161: // ... and if we find something in the buffer that isn't
1162: // 'equal', then advance the look ahead
1163: if (!fn.fn(obj, lai.peek(idx))) {
1164: lai.next();
1165: continue OUTER;
1166: }
1167:
1168: ++idx;
1169: }
1170:
1171: // If we safely got off the end of the INNER loop, then we must
1172: // have found the point we're looking for.
1173: return lai;
1174: }
1175:
1176: // didn't find anything, make an iterator that will return false.
1177: return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
1178: }
1179:
1180: /**
1181: * Finds the point at which the input differs from the pattern.
1182: * @return an iterator based whose next() [if it hasNext()] will return the first element which
1183: * does not match the corresponding element in the pattern. If the pattern matches the array
1184: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
1185: * the array but is shorter, the returned iterator will point at the next element in the array
1186: * after the length of the pattern. If the pattern is empty, no input will be consumed.
1187: */
1188: static public <T> Iterator<T> findMismatch(
1189: Iterator<? extends T> iterator, T[] pattern) {
1190: return findMismatch(iterator, Arrays.asList(pattern),
1191: new NotEqualTo<T>());
1192: }
1193:
1194: /**
1195: * Finds the point at which the input differs from the pattern.
1196: * @return an iterator based whose next() [if it hasNext()] will return the first element which
1197: * does not match the corresponding element in the pattern. If the pattern matches the input
1198: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
1199: * the input but is shorter, the returned iterator will point at the next element in the input
1200: * after the length of the pattern. If the pattern is empty, no input will be consumed.
1201: */
1202: static public <T> Iterator<T> findMismatch(
1203: Iterator<? extends T> iterator,
1204: Collection<? extends T> pattern) {
1205: return findMismatch(iterator, pattern, new NotEqualTo<T>());
1206: }
1207:
1208: /**
1209: * Finds the point at which the input differs from the pattern, using the given comparator to
1210: * determine the mismatch.
1211: * @return an iterator based whose next() [if it hasNext()] will return the first element which
1212: * does not match the corresponding element in the pattern. If the pattern matches the array
1213: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
1214: * the array but is shorter, the returned iterator will point at the next element in the array
1215: * after the length of the pattern. If the pattern is empty, no input will be consumed.
1216: */
1217: static public <T> Iterator<T> findMismatch(
1218: Iterator<? extends T> iterator, T[] pattern,
1219: Comparator<? super T> comp) {
1220: return findMismatch(iterator, Arrays.asList(pattern),
1221: new NotEqualTo<T>(comp));
1222: }
1223:
1224: /**
1225: * Finds the point at which the input differs from the pattern, using the given comparator to
1226: * determine the mismatch.
1227: * @return an iterator based whose next() [if it hasNext()] will return the first element which
1228: * does not match the corresponding element in the pattern. If the pattern matches the input
1229: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
1230: * the input but is shorter, the returned iterator will point at the next element in the input
1231: * after the length of the pattern. If the pattern is empty, no input will be consumed.
1232: */
1233: static public <T> Iterator<T> findMismatch(
1234: Iterator<? extends T> iterator,
1235: Collection<? extends T> pattern, Comparator<? super T> comp) {
1236: return findMismatch(iterator, pattern, new NotEqualTo<T>(comp));
1237: }
1238:
1239: /**
1240: * Finds the point at which the input differs from the pattern, using the given functor to
1241: * determine the mismatch. The functor should return TRUE if a given pair of elements does
1242: * not match.
1243: * @return an iterator based whose next() [if it hasNext()] will return the first element which
1244: * does not match the corresponding element in the pattern. If the pattern matches the array
1245: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
1246: * the array but is shorter, the returned iterator will point at the next element in the array
1247: * after the length of the pattern. If the pattern is empty, no input will be consumed.
1248: */
1249: static public <T> Iterator<T> findMismatch(
1250: Iterator<? extends T> iterator, T[] pattern,
1251: BinaryFunctor<T, T, Boolean> neq) {
1252: return findMismatch(iterator, Arrays.asList(pattern), neq);
1253: }
1254:
1255: /**
1256: * Finds the point at which the input differs from the pattern, using the given functor to
1257: * determine the mismatch. The functor should return TRUE if a given pair of elements does
1258: * not match.
1259: * @return an iterator based whose next() [if it hasNext()] will return the first element which
1260: * does not match the corresponding element in the pattern. If the pattern matches the array
1261: * but is longer, the returned iterator's hasNext() will report false. If the pattern matches
1262: * the array but is shorter, the returned iterator will point at the next element in the array
1263: * after the length of the pattern. If the pattern is empty, no input will be consumed.
1264: */
1265: static public <T> Iterator<T> findMismatch(
1266: Iterator<? extends T> iterator,
1267: Collection<? extends T> pattern,
1268: BinaryFunctor<T, T, Boolean> neq) {
1269: LookAheadIterator<? extends T> patternIter = new LookAheadIterator<T>(
1270: pattern.iterator());
1271: LookAheadIterator<T> lai = lookAhead(iterator, 1);
1272: while (lai.hasNextPlus(1) && patternIter.hasNextPlus(1)) {
1273: T arg1 = lai.peek(1);
1274: T arg2 = patternIter.peek(1);
1275: if (neq.fn(arg1, arg2)) {
1276: return lai;
1277: }
1278:
1279: lai.next();
1280: patternIter.next();
1281: }
1282:
1283: return lai;
1284: }
1285:
1286: // ==============
1287: // Implementation
1288: // ==============
1289:
1290: static public <T> UnaryFunctor<T, Boolean> elementOf(T[] values) {
1291: return new ElementOf<T>().bind2nd(Arrays.asList(values));
1292: }
1293:
1294: static public <T> UnaryFunctor<T, Boolean> elementOf(
1295: Collection<? extends T> values) {
1296: return new ElementOf<T>().bind2nd(values);
1297: }
1298:
1299: static public <T> UnaryFunctor<T, Boolean> elementOf(T[] values,
1300: Comparator<? super T> comp) {
1301: return new ElementOf<T>(new EqualTo<T>(comp)).bind2nd(Arrays
1302: .asList(values));
1303: }
1304:
1305: static public <T> UnaryFunctor<T, Boolean> elementOf(
1306: Collection<? extends T> values, Comparator<? super T> comp) {
1307: return new ElementOf<T>(new EqualTo<T>(comp)).bind2nd(values);
1308: }
1309:
1310: static public <T> UnaryFunctor<T, Boolean> elementOf(T[] values,
1311: BinaryFunctor<T, T, Boolean> bf) {
1312: return new ElementOf<T>(bf).bind2nd(Arrays.asList(values));
1313: }
1314:
1315: static public <T> UnaryFunctor<T, Boolean> elementOf(
1316: Collection<? extends T> values,
1317: BinaryFunctor<T, T, Boolean> bf) {
1318: return new ElementOf<T>(bf).bind2nd(values);
1319: }
1320:
1321: static private <T> FindIterator<T> finder(
1322: Iterator<? extends T> iterator) {
1323: if (iterator instanceof FindIterator)
1324: return (FindIterator<T>) iterator;
1325:
1326: return new FindIterator(iterator);
1327: }
1328:
1329: static private <T> LookAheadIterator<T> lookAhead(
1330: Iterator<? extends T> iterator, int size) {
1331: if (iterator instanceof LookAheadIterator) {
1332: LookAheadIterator<T> lai = (LookAheadIterator<T>) iterator;
1333: if (lai.getMaxPeekSize() >= size)
1334: return lai;
1335: }
1336:
1337: return new LookAheadIterator(iterator, size);
1338: }
1339: }
|