Find


1   // ============================================================================
2   // $Id: Find.java,v 1.3 2006/12/16 16:48:58 davidahall Exp $
3   // Copyright (c) 2005  David A. Hall
4   // ============================================================================
5   // The contents of this file are subject to the Common Development and
6   // Distribution License (CDDL), Version 1.0 (the License); you may not use this 
7   // file except in compliance with the License.  You should have received a copy
8   // of the the License along with this file: if not, a copy of the License is 
9   // available from Sun Microsystems, Inc.
10  //
11  // http://www.sun.com/cddl/cddl.html
12  //
13  // From time to time, the license steward (initially Sun Microsystems, Inc.) may
14  // publish revised and/or new versions of the License.  You may not use,  
15  // distribute, or otherwise make this file available under subsequent versions 
16  // of the License.
17  // 
18  // Alternatively, the contents of this file may be used under the terms of the 
19  // GNU Lesser General Public License Version 2.1 or later (the "LGPL"), in which
20  // case the provisions of the LGPL are applicable instead of those above. If you 
21  // wish to allow use of your version of this file only under the terms of the 
22  // LGPL, and not to allow others to use your version of this file under the 
23  // terms of the CDDL, indicate your decision by deleting the provisions above 
24  // and replace them with the notice and other provisions required by the LGPL. 
25  // If you do not delete the provisions above, a recipient may use your version 
26  // of this file under the terms of either the CDDL or the LGPL.
27  // 
28  // This library is distributed in the hope that it will be useful,
29  // but WITHOUT ANY WARRANTY; without even the implied warranty of
30  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
31  // ============================================================================
32  
33  package net.sf.jga.algorithms;
34  
35  import java.util.Arrays  ;
36  import java.util.Collection  ;
37  import java.util.Comparator  ;
38  import java.util.Iterator  ;
39  import java.util.NoSuchElementException  ;
40  import net.sf.jga.fn.BinaryFunctor;
41  import net.sf.jga.fn.UnaryFunctor;
42  import net.sf.jga.fn.algorithm.ElementOf;
43  import net.sf.jga.fn.comparison.EqualTo;
44  import net.sf.jga.fn.comparison.Equality;
45  import net.sf.jga.fn.comparison.NotEqualTo;
46  import net.sf.jga.util.EmptyIterator;
47  import net.sf.jga.util.FindIterator;
48  import net.sf.jga.util.LookAheadIterator;
49  
50  import static net.sf.jga.fn.comparison.ComparisonFunctors.*;
51  import static net.sf.jga.util.ArrayUtils.*;
52  
53  /**
54   * Algorithms that return an iterator pointing at the first/next element of the input
55   * that meets some condition.
56   */
57  
58  public class Find {
59      
60      // ============
61      // Arrays
62      // ============
63  
64      /**
65       * Finds an arbitrary value in the array using the equals() method.
66       * @return an iterator whose next() [if it hasNext()]
67       * will return the first instance of the value.  If the value is not in the
68       * array, then the returned iterator's hasNext() will report false.
69       */
70      static public <T> Iterator  <T> find(T[] ts, T value) {
71          return find(iterate(ts), equalTo(value));
72      }
73  
74      /**
75       * Finds an arbitrary value in the array using the given Comparator.
76       * @return an iterator whose next() [if it hasNext()]
77       * will return the first instance of the value.  If the value is not in the
78       * array, then the returned iterator's hasNext() will report false.
79       */
80      static public <T> Iterator  <T> find(T[] ts, T value, Comparator  <? super T> comp){
81          return find(iterate(ts), equalTo(comp, value));
82      }
83  
84      
85      /**
86       * Finds an arbitrary value in the array using the given Equality operator.
87       * @return an iterator whose next() [if it hasNext()]
88       * will return the first instance of the value.  If the value is not in the
89       * array, then the returned iterator's hasNext() will report false.
90       */
91      static public <T> Iterator  <T> find(T[] ts, T value, Equality<T> eq){
92          return find(iterate(ts), equalTo(eq, value));
93      }
94  
95      
96      /**
97       * Finds a value in the input for which the given function returns TRUE.
98       * @return an iterator whose next() [if it hasNext()]
99       * will return the first instance of such a value.  If no such value is in the
100      * array, then the returned iterator's hasNext() will report false.
101      */
102     static public <T> Iterator  <T> find(T[] ts, UnaryFunctor<T,Boolean  > fn) {
103         return find(iterate(ts), fn);
104     }
105  
106     /**
107      * Finds first/next element in the array that is also in the values array.
108      * @return an iterator whose next() [if it hasNext()] will return the first instance of any
109      * element found in the array of values.  If no such element is found then the returned
110      * iterator's hasNext() will report false.
111      */
112     static public <T> Iterator  <T> findElement(T[] ts, T[] values) {
113         return find(iterate(ts), elementOf(values));
114     }
115 
116     
117     /**
118      * Finds first/next element in the array that is also in the collection of values, using
119      * the collection's contains() method.
120      * @return an iterator whose next() [if it hasNext()] will return the first instance of any
121      * element found in the collection of values.  If no such element is found  then the returned
122      * iterator's hasNext() will report false.
123      */
124     static public <T> Iterator  <T> findElement(T[] ts, Collection  <? extends T> values) {
125         return find(iterate(ts), elementOf(values) );
126     }
127 
128     /**
129      * Finds first/next element in the array that is also in the values array, using
130      * the given Comparator to compare values.
131      * @return an iterator whose next() [if it hasNext()] will return the first instance of any
132      * element found in the array of values.  If no such element is found then the returned
133      * iterator's hasNext() will report false.
134      */
135     static public <T> Iterator  <T> findElement(T[] ts, T[] values, Comparator  <? super T> comp) {
136         return find(iterate(ts), elementOf(values, comp));
137     }
138 
139     
140     /**
141      * Finds first/next element in the array that is also in the values collection, using
142      * the given functor to compare values.
143      * @return an iterator whose next() [if it hasNext()] will return the first instance of any
144      * element found in collection of values.  If no such value is found then the returned
145      * iterator's hasNext() will report false.
146      */
147     static public <T> Iterator  <T>
148     findElement(T[] ts, Collection  <? extends T> values, Comparator  <? super T> comp) {
149         return find(iterate(ts), elementOf(values, comp));
150     }
151     
152     /**
153      * Finds first/next element in the array that is also in the values array, using
154      * the given functor to compare values.
155      * @return an iterator whose next() [if it hasNext()] will return the first instance of any
156      * element found in the array of values.  If no such element is found then the returned
157      * iterator's hasNext() will report false.
158      */
159     static public <T> Iterator  <T> findElement(T[] ts, T[] values, BinaryFunctor<T,T,Boolean  > bf) {
160         return find(iterate(ts), elementOf(values, bf));
161     }
162 
163     
164     /**
165      * Finds first/next element in the input that is in the values collection, using
166      * the given functor to compare values.
167      * @return an iterator whose next() [if it hasNext()] will return the first instance of any
168      * element found in collection of values.  If no such value is found then the returned
169      * iterator's hasNext() will report false.
170      */
171     static public <T> Iterator  <T>
172     findElement(T[] ts, Collection  <? extends T> values, BinaryFunctor<T,T,Boolean  > bf) {
173         return find(iterate(ts), elementOf(values, bf));
174     }
175     
176 
177     /**
178      * Locates the first/next pair of adjacent elements in the array that
179      * are the same value, using the equals() method.
180      * @return an iterator whose next() [if it hasNext()] points to the first of
181      * a pair of adjacent equivalent values.  If no such pair exists, then the
182      * iterator's hasNext() will be false.
183      */
184     static public <T> Iterator  <T> findAdjacent(T[] ts) {
185         return findAdjacent(iterate(ts), new EqualTo<T>());
186     }
187 
188     
189     /**
190      * Locates the first/next pair of adjacent elements in the array that
191      * are the same value, using the given comparator.
192      * @return an iterator whose next() [if it hasNext()] points to the first of
193      * a pair of adjacent equivalent values.  If no such pair exists, then the
194      * iterator's hasNext() will be false.
195      */
196     static public <T> Iterator  <T> findAdjacent(T[] ts, Comparator  <? super T> comp) {
197         return findAdjacent(iterate(ts), new EqualTo<T>(comp));
198     }
199 
200     
201     /**
202      * Locates the first/next pair of adjacent elements in the array that
203      * are the same value, using the given functor.  The functor should return
204      * TRUE when two values are to be considered equal.
205      * @return an iterator whose next() [if it hasNext()] points to the first of
206      * a pair of adjacent equivalent values.  If no such pair exists, then the
207      * iterator's hasNext() will be false.
208      */
209     static public <T> Iterator  <T> findAdjacent(T[] ts, BinaryFunctor<T,T,Boolean  > eq) {
210         return findAdjacent(iterate(ts), eq);
211     }
212 
213     
214     /**
215      * Finds first/next arbitrary length run of a given value in the input.  Runs of length zero
216      * are well-defined: every input begins with a run of length zero of all possible values.
217      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
218      * the first of n adjacent instances of value.  If no run of values of the requested length
219      * exist in the iteration, then the returned iterator's hasNext() will report false.
220      */
221     static public <T> Iterator  <T> findRepeated (T[] ts, int count, T value) {
222         return findRepeated(iterate(ts), count, equalTo(value));
223     }
224     
225     /**
226      * Finds first/next arbitrary length run of a given value in the input using the given
227      * comparator.  Runs of length zero are well-defined: every input begins with
228      * a run of length zero of all possible values.
229      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
230      * the first of n adjacent instances of value.  If no run of values of the requested length
231      * exist in the iteration, then the returned iterator's hasNext() will report false.
232      */
233     static public <T> Iterator  <T>
234     findRepeated (T[] ts, int count, T value, Comparator  <? super T> comp) {
235         return findRepeated(iterate(ts), count, equalTo(comp, value));
236     }
237     
238     /**
239      * Finds first/next arbitrary length run of a given value in the input using the given
240      * equality function.  Runs of length zero are well-defined: every input begins with
241      * a run of length zero of all possible values.
242      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
243      * the first of n adjacent instances of value.  If no run of values of the requested length
244      * exist in the iteration, then the returned iterator's hasNext() will report false.
245      */
246     static public <T> Iterator  <T> findRepeated (T[] ts, int count, T value, Equality<T> eq) {
247         return findRepeated(iterate(ts), count, equalTo(eq, value));
248     }
249     
250     /**
251      * Finds first/next arbitrary length run of elements in the input for which the
252      * given function returns TRUE.  Runs of length zero are well-defined: every
253      * input begins with a run of length zero of all possible values.
254      * @return an iterator based on the given iterator whose next() [if it
255      * hasNext()] will return the first of n adjacent instances of value.  If no
256      * run of values of the requested length exist in the iteration, then the
257      * returned iterator's hasNext() will report false.
258      */
259     static public <T> Iterator  <T> findRepeated (T[] ts, int count, UnaryFunctor<T,Boolean  > eq) {
260         return findRepeated(iterate(ts), count, eq);
261     }
262 
263     /**
264      * Finds the given pattern in the input using the equals method.
265      * @return an iterator whose next() [if it hasNext()] will return the first element of a
266      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
267      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
268      */
269     static public <T> Iterator  <T> findSequence(T[] ts, T[] pattern) {
270         return findSequence(iterate(ts), Arrays.asList(pattern), new EqualTo<T>());
271     }
272 
273     
274     /**
275      * Finds the given pattern in the input using the equals method.
276      * @return an iterator whose next() [if it hasNext()] will return the first element of a
277      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
278      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
279      */
280     static public <T> Iterator  <T> findSequence(T[] ts, Collection  <? extends T> pattern) {
281         return findSequence(iterate(ts), pattern, new EqualTo<T>());
282     }
283     
284     
285     /**
286      * Finds the given pattern in the input using the given comparator to determine equivalence.
287      * @return an iterator whose next() [if it hasNext()] will return the first element of a
288      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
289      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
290      */
291     static public <T> Iterator  <T> findSequence(T[] ts, T[] pattern, Comparator  <? super T> comp) {
292         return findSequence(iterate(ts), Arrays.asList(pattern), new EqualTo<T>(comp));
293     }
294     
295     
296     /**
297      * Finds the given pattern in the input using the given comparator to determine equivalence.
298      * @return an iterator whose next() [if it hasNext()] will return the first element of a
299      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
300      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
301      */
302     static public <T> Iterator  <T>
303     findSequence(T[] ts, Collection  <? extends T> pattern, Comparator  <T> comp) {
304         return findSequence(iterate(ts), pattern, new EqualTo<T>(comp));
305     }
306 
307     
308     /**
309      * Finds the given pattern in the input using the given functor to determine equivalence.
310      * @return an iterator whose next() [if it hasNext()] will return the first element of a
311      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
312      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
313      */
314     static public <T> Iterator  <T> findSequence(T[] ts, T[] pattern, BinaryFunctor<T,T,Boolean  > fn) {
315         return findSequence(iterate(ts), Arrays.asList(pattern), fn);
316     }
317     
318     
319     /**
320      * Finds the given pattern in the input using the given functor to determine equivalence.
321      * @return an iterator whose next() [if it hasNext()] will return the first element of a
322      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
323      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
324      */
325     static public <T> Iterator  <T>
326     findSequence(T[] ts, Collection  <? extends T> pattern, BinaryFunctor<T,T,Boolean  > fn) {
327         return findSequence(iterate(ts), pattern, fn);
328     }
329 
330     
331     /**
332      * Finds the point at which the array differs from the pattern.  
333      * @return an iterator based whose next() [if it hasNext()] will return the first element which
334      * does not match the corresponding element in the pattern.  If the pattern matches the array
335      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
336      * the array but is shorter, the returned iterator will point at the next element in the array
337      * after the length of the pattern.
338      */
339     static public <T> Iterator  <T> findMismatch(T[] ts, T[] pattern){
340         return findMismatch(iterate(ts), Arrays.asList(pattern), new NotEqualTo<T>());        
341     }
342     
343     /**
344      * Finds the point at which the array differs from the pattern.
345      * @return an iterator based whose next() [if it hasNext()] will return the first element which
346      * does not match the corresponding element in the pattern.  If the pattern matches the array
347      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
348      * the array but is shorter, the returned iterator will point at the next element in the array
349      * after the length of the pattern.
350      */
351     static public <T> Iterator  <T> findMismatch(T[] ts, Collection  <? extends T> pattern) {
352         return findMismatch(iterate(ts), pattern, new NotEqualTo<T>());
353     }
354     
355     /**
356      * Finds the point at which the array differs from the pattern, using the given comparator to
357      * determine the mismatch.  
358      * @return an iterator based whose next() [if it hasNext()] will return the first element which
359      * does not match the corresponding element in the pattern.  If the pattern matches the array
360      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
361      * the array but is shorter, the returned iterator will point at the next element in the array
362      * after the length of the pattern.
363      */
364     static public <T> Iterator  <T> findMismatch(T[] ts, T[] pattern, Comparator  <? super T> comp) {
365         return findMismatch(iterate(ts), Arrays.asList(pattern), new NotEqualTo<T>(comp));        
366     }
367     
368     /**
369      * Finds the point at which the array differs from the pattern, using the given comparator to
370      * determine the mismatch.  
371      * @return an iterator based whose next() [if it hasNext()] will return the first element which
372      * does not match the corresponding element in the pattern.  If the pattern matches the array
373      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
374      * the array but is shorter, the returned iterator will point at the next element in the array
375      * after the length of the pattern.
376      */
377     static public <T> Iterator  <T>
378     findMismatch(T[] ts, Collection  <? extends T> pattern, Comparator  <? super T> comp) {
379         return findMismatch(iterate(ts), pattern, new NotEqualTo<T>(comp));
380     }
381     
382     /**
383      * Finds the point at which the array differs from the pattern, using the given functor to
384      * determine the mismatch.  The functor should return TRUE if a given pair of elements does
385      * not match.
386      * @return an iterator based whose next() [if it hasNext()] will return the first element which
387      * does not match the corresponding element in the pattern.  If the pattern matches the array
388      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
389      * the array but is shorter, the returned iterator will point at the next element in the array
390      * after the length of the pattern.
391      */
392     static public <T> Iterator  <T> findMismatch(T[] ts, T[] pattern, BinaryFunctor<T,T,Boolean  > neq) {
393         return findMismatch(iterate(ts), Arrays.asList(pattern), neq);        
394     }
395     
396     /**
397      * Finds the point at which the array differs from the pattern, using the given functor to
398      * determine the mismatch.  The functor should return TRUE if a given pair of elements does
399      * not match.
400      * @return an iterator based whose next() [if it hasNext()] will return the first element which
401      * does not match the corresponding element in the pattern.  If the pattern matches the array
402      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
403      * the array but is shorter, the returned iterator will point at the next element in the array
404      * after the length of the pattern.
405      */
406     static public <T> Iterator  <T>
407     findMismatch(T[] ts, Collection  <? extends T> pattern, BinaryFunctor<T,T,Boolean  > neq) {
408         return findMismatch(iterate(ts), pattern, neq);
409     }                                       
410 
411     // ============
412     // Iterables
413     // ============
414     
415     /**
416      * Finds an arbitrary value in the input using the equals() method.
417      * @return an iterator whose next() [if it hasNext()]
418      * will return the first instance of the value.  If the value is not in the
419      * input, then the returned iterator's hasNext() will report false.
420      */
421     static public <T> Iterator  <T> find(Iterable  <? extends T> iter, T value) {
422         return find(iter, equalTo(value));
423     }
424 
425     /**
426      * Finds an arbitrary value in the input using the given Comparator.
427      * @return an iterator whose next() [if it hasNext()]
428      * will return the first instance of the value.  If the value is not in the
429      * input, then the returned iterator's hasNext() will report false.
430      */
431     static public <T> Iterator  <T>
432     find(Iterable  <? extends T> iter, T value, Comparator  <? super T> comp) {
433         return find(iter, equalTo(comp, value));
434     }
435 
436     
437     /**
438      * Finds an arbitrary value in the input using the given Equality operator.
439      * @return an iterator whose next() [if it hasNext()]
440      * will return the first instance of the value.  If the value is not in the
441      * input, then the returned iterator's hasNext() will report false.
442      */
443     static public <T> Iterator  <T> find(Iterable  <? extends T> iter, T value, Equality<T> eq) {
444         return find(iter, equalTo(eq, value));
445     }
446 
447     
448     /**
449      * Finds a value in the input for which the given function returns TRUE.
450      * @return an iterator whose next() [if it hasNext()]
451      * will return the first instance of the value.  If the value is not in the
452      * input, then the returned iterator's hasNext() will report false.
453      */
454     static public <T> Iterator  <T> find(Iterable  <? extends T> iter, UnaryFunctor<T,Boolean  > fn) {
455         return find(iter.iterator(), fn);
456     }
457 
458     
459     /**
460      * Finds first/next value in the input that is an element of the given array.
461      * @return an iterator whose next() [if it hasNext()] will return
462      * the first instance of any element found in the array of values.  If no such element is
463      * found then the returned iterator's hasNext() will report false.
464      */
465     static public <T> Iterator  <T> findElement(Iterable  <? extends T> iter, T[] values) {
466         return find(iter.iterator(), elementOf(values));
467     }
468 
469     
470     /**
471      * Finds first/next value in the input that is an element of the given collection, using
472      * the collection's contains() method.
473      * @return an iterator whose next() [if it hasNext()] will return
474      * the first instance of any element found in the collection of values.  If no such element
475      * is found  then the returned iterator's hasNext() will report false.
476      */
477     static public <T> Iterator  <T>
478     findElement(Iterable  <? extends T> iter, Collection  <? extends T> values) {
479         return find(iter.iterator(), elementOf(values) );
480     }
481 
482     /**
483      * Finds first/next value in the input that is an element of the given array, using
484      * the given Comparator to compare values.
485      * @return an iterator whose next() [if it hasNext()] will return
486      * the first instance of any element found in the array of values.  If no such element is
487      * found then the returned iterator's hasNext() will report false.
488      */
489     static public <T> Iterator  <T>
490     findElement(Iterable  <? extends T> iter, T[] values, Comparator  <? super T> comp) {
491         return find(iter.iterator(), elementOf(values, comp));
492     }
493 
494     
495     /**
496      * Finds first/next value in the input that is an element of the given collection, using
497      * the given functor to compare values.
498      * @return an iterator whose next() [if it hasNext()] will return
499      * the first instance of any element found in collection of values.  If no such value is
500      * found then the returned iterator's hasNext() will report false.
501      */
502     static public <T> Iterator  <T>
503     findElement(Iterable  <? extends T> iter, Collection  <? extends T> values,
504                 Comparator  <? super T> comp) {
505         return find(iter.iterator(), elementOf(values, comp));
506     }
507     
508     /**
509      * Finds first/next value in the input that is an element of the given array, using
510      * the given functor to compare values.
511      * @return an iterator whose next() [if it hasNext()] will return
512      * the first instance of any element found in the array of values.  If no such element is
513      * found then the returned iterator's hasNext() will report false.
514      */
515     static public <T> Iterator  <T>
516     findElement(Iterable  <? extends T> iter, T[] values, BinaryFunctor<T,T,Boolean  > bf) {
517         return find(iter.iterator(), elementOf(values, bf));
518     }
519 
520     
521     /**
522      * Finds first/next value in the input that is an element of the given collection, using
523      * the given functor to compare values.
524      * @return an iterator whose next() [if it hasNext()] will return
525      * the first instance of any element found in collection of values.  If no such value is
526      * found then the returned iterator's hasNext() will report false.
527      */
528     static public <T> Iterator  <T>
529     findElement(Iterable  <? extends T> iter, Collection  <? extends T> values,
530                 BinaryFunctor<T,T,Boolean  > bf)
531     {
532         return find(iter.iterator(), elementOf(values, bf));
533     }
534     
535     
536     /**
537      * Locates the first/next pair of adjacent elements in the input that
538      * are the same value, using the equals() method.
539      * @return an iterator whose next() [if it hasNext()] points to the first of
540      * a pair of adjacent equivalent values.  If no such pair exists, then the
541      * iterator's hasNext() will be false.
542      */
543     static public <T> Iterator  <T> findAdjacent(Iterable  <? extends T> iter) {
544         return findAdjacent(iter, new EqualTo<T>());
545     }
546 
547     
548     /**
549      * Locates the first/next pair of adjacent elements in the input that
550      * are the same value, using the given comparator.
551      * @return an iterator whose next() [if it hasNext()] points to the first of
552      * a pair of adjacent equivalent values.  If no such pair exists, then the
553      * iterator's hasNext() will be false.
554      */
555     static public <T> Iterator  <T>
556     findAdjacent(Iterable  <? extends T> iter, Comparator  <? super T> comp) {
557         return findAdjacent(iter, new EqualTo<T>(comp));
558     }
559 
560     
561     /**
562      * Locates the first/next pair of adjacent elements in the input that
563      * are the same value, using the given functor.  The functor should return
564      * TRUE when two values are to be considered equal.
565      * @return an iterator whose next() [if it hasNext()] points to the first of
566      * a pair of adjacent equivalent values.  If no such pair exists, then the
567      * iterator's hasNext() will be false.
568      */
569     static public <T> Iterator  <T>
570     findAdjacent(Iterable  <? extends T> iter, BinaryFunctor<T,T,Boolean  > eq) {
571         return findAdjacent(iter.iterator(), eq);
572     }
573     
574     /**
575      * Finds first/next arbitrary length run of a given value in the input.  Runs of length zero
576      * are well-defined: every input begins with a run of length zero of all possible values.
577      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
578      * the first of n adjacent instances of value.  If no run of values of the requested length
579      * exist in the iteration, then the returned iterator's hasNext() will report false.
580      */
581     static public <T> Iterator  <T> findRepeated (Iterable  <? extends T> iter, int count, T value) {
582         return findRepeated(iter.iterator(), count, equalTo(value));
583     }
584     
585     /**
586      * Finds first/next arbitrary length run of a given value in the input using the given
587      * comparator.  Runs of length zero are well-defined: every input begins with
588      * a run of length zero of all possible values.
589      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
590      * the first of n adjacent instances of value.  If no run of values of the requested length
591      * exist in the iteration, then the returned iterator's hasNext() will report false.
592      */
593     static public <T> Iterator  <T>
594     findRepeated (Iterable  <? extends T> iter, int count, T value, Comparator  <? super T> comp) {
595         return findRepeated(iter.iterator(), count, equalTo(comp, value));
596     }
597     
598     /**
599      * Finds first/next arbitrary length run of a given value in the input using the given
600      * equality function.  Runs of length zero are well-defined: every input begins with
601      * a run of length zero of all possible values.
602      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
603      * the first of n adjacent instances of value.  If no run of values of the requested length
604      * exist in the iteration, then the returned iterator's hasNext() will report false.
605      */
606     static public <T> Iterator  <T>
607     findRepeated (Iterable  <? extends T> iter, int count, T value, Equality<T> eq) {
608         return findRepeated(iter.iterator(), count, equalTo(eq, value));
609     }
610     
611     /**
612      * Finds first/next arbitrary length run of elements in the input for which the
613      * given function returns TRUE.  Runs of length zero are well-defined: every
614      * input begins with a run of length zero of all possible values.
615      * @return an iterator based on the given iterator whose next() [if it
616      * hasNext()] will return the first of n adjacent instances of value.  If no
617      * run of values of the requested length exist in the iteration, then the
618      * returned iterator's hasNext() will report false.
619      */
620     static public <T> Iterator  <T>
621     findRepeated (Iterable  <? extends T> iter, int count, UnaryFunctor<T,Boolean  > eq) {
622         return findRepeated(iter.iterator(), count, eq);
623     }
624 
625 
626     /**
627      * Finds the given pattern in the input using the equals method.
628      * @return an iterator whose next() [if it hasNext()] will return the first element of a
629      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
630      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
631      */
632     static public <T> Iterator  <T>
633     findSequence(Iterable  <? extends T> iter, T[] pattern) {
634         return findSequence(iter.iterator(), Arrays.asList(pattern), new EqualTo<T>());
635     }
636 
637     
638     /**
639      * Finds the given pattern in the input using the equals method.
640      * @return an iterator whose next() [if it hasNext()] will return the first element of a
641      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
642      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
643      */
644     static public <T> Iterator  <T>
645     findSequence(Iterable  <? extends T> iter, Collection  <? extends T> pattern) {
646         return findSequence(iter.iterator(), pattern, new EqualTo<T>());
647     }
648     
649     
650     /**
651      * Finds the given pattern in the input using the given comparator to determine equivalence.
652      * @return an iterator whose next() [if it hasNext()] will return the first element of a
653      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
654      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
655      */
656     static public <T> Iterator  <T>
657     findSequence(Iterable  <? extends T> iter, T[] pattern, Comparator  <? super T> comp) {
658         return findSequence(iter.iterator(), Arrays.asList(pattern), new EqualTo<T>(comp));
659     }
660     
661     
662     /**
663      * Finds the given pattern in the input using the given comparator to determine equivalence.
664      * @return an iterator whose next() [if it hasNext()] will return the first element of a
665      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
666      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
667      */
668     static public <T> Iterator  <T>
669     findSequence(Iterable  <? extends T> iter, Collection  <? extends T> pattern, Comparator  <T> comp) {
670         return findSequence(iter.iterator(), pattern, new EqualTo<T>(comp));
671     }
672 
673     
674     /**
675      * Finds the given pattern in the input using the given functor to determine equivalence.
676      * @return an iterator whose next() [if it hasNext()] will return the first element of a
677      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
678      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
679      */
680     static public <T> Iterator  <T>
681     findSequence(Iterable  <? extends T> iter, T[] pattern, BinaryFunctor<T,T,Boolean  > fn) {
682         return findSequence(iter.iterator(), Arrays.asList(pattern), fn);
683     }
684     
685     
686     /**
687      * Finds the given pattern in the input using the given functor to determine equivalence.
688      * @return an iterator whose next() [if it hasNext()] will return the first element of a
689      * sequence that matches the pattern.  If no such match is found, then the returned iterator's
690      * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
691      */
692     static public <T> Iterator  <T>
693     findSequence(Iterable  <? extends T> iter, Collection  <? extends T> pattern,
694                  BinaryFunctor<T,T,Boolean  > fn)
695     {
696         return findSequence(iter.iterator(), pattern, fn);
697     }
698 
699     
700     /**
701      * Finds the point at which the input differs from the pattern.  
702      * @return an iterator based whose next() [if it hasNext()] will return the first element which
703      * does not match the corresponding element in the pattern.  If the pattern matches the array
704      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
705      * the array but is shorter, the returned iterator will point at the next element in the array
706      * after the length of the pattern.
707      */
708     static public <T> Iterator  <T> findMismatch(Iterable  <? extends T> iter, T[] pattern) {
709         return findMismatch(iter.iterator(), Arrays.asList(pattern), new NotEqualTo<T>());        
710     }
711     
712     /**
713      * Finds the point at which the input differs from the pattern.
714      * @return an iterator based whose next() [if it hasNext()] will return the first element which
715      * does not match the corresponding element in the pattern.  If the pattern matches the input
716      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
717      * the input but is shorter, the returned iterator will point at the next element in the input
718      * after the length of the pattern.
719      */
720     static public <T> Iterator  <T>
721     findMismatch(Iterable  <? extends T> iter, Collection  <? extends T> pattern) {
722         return findMismatch(iter.iterator(), pattern, new NotEqualTo<T>());
723     }
724     
725     /**
726      * Finds the point at which the input differs from the pattern, using the given comparator to
727      * determine the mismatch.  
728      * @return an iterator based whose next() [if it hasNext()] will return the first element which
729      * does not match the corresponding element in the pattern.  If the pattern matches the array
730      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
731      * the array but is shorter, the returned iterator will point at the next element in the array
732      * after the length of the pattern.
733      */
734     static public <T> Iterator  <T>
735     findMismatch(Iterable  <? extends T> iter, T[] pattern, Comparator  <? super T> comp) {
736         return findMismatch(iter.iterator(), Arrays.asList(pattern), new NotEqualTo<T>(comp));        
737     }
738     
739     /**
740      * Finds the point at which the input differs from the pattern, using the given comparator to
741      * determine the mismatch.  
742      * @return an iterator based whose next() [if it hasNext()] will return the first element which
743      * does not match the corresponding element in the pattern.  If the pattern matches the input
744      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
745      * the input but is shorter, the returned iterator will point at the next element in the input
746      * after the length of the pattern.
747      */
748     static public <T> Iterator  <T>
749     findMismatch(Iterable  <? extends T> iter, Collection  <? extends T> pattern,
750                  Comparator  <? super T> comp) {
751         return findMismatch(iter.iterator(), pattern, new NotEqualTo<T>(comp));
752     }
753     
754     /**
755      * Finds the point at which the input differs from the pattern, using the given functor to
756      * determine the mismatch.  The functor should return TRUE if a given pair of elements does
757      * not match.
758      * @return an iterator based whose next() [if it hasNext()] will return the first element which
759      * does not match the corresponding element in the pattern.  If the pattern matches the array
760      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
761      * the array but is shorter, the returned iterator will point at the next element in the array
762      * after the length of the pattern.
763      */
764     static public <T> Iterator  <T>
765     findMismatch(Iterable  <? extends T> iter, T[] pattern, BinaryFunctor<T,T,Boolean  > neq) {
766         return findMismatch(iter.iterator(), Arrays.asList(pattern), neq);        
767     }
768     
769     /**
770      * Finds the point at which the input differs from the pattern, using the given functor to
771      * determine the mismatch.  The functor should return TRUE if a given pair of elements does
772      * not match.
773      * @return an iterator based whose next() [if it hasNext()] will return the first element which
774      * does not match the corresponding element in the pattern.  If the pattern matches the array
775      * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
776      * the array but is shorter, the returned iterator will point at the next element in the array
777      * after the length of the pattern.
778      */
779     static public <T> Iterator  <T>
780     findMismatch(Iterable  <? extends T> iter, Collection  <? extends T> pattern,
781                  BinaryFunctor<T,T,Boolean  > neq) {
782         return findMismatch(iter.iterator(), pattern, neq);
783     }                                       
784 
785     // ============
786     // Iterators
787     // ============
788 
789     /**
790      * Finds an arbitrary value in the input using the equals() method.
791      * @return an iterator whose next() [if it hasNext()]
792      * will return the first instance of the value.  If the value is not in the
793      * input, then the returned iterator's hasNext() will report false.
794      */
795     static public <T> Iterator  <T> find(Iterator  <? extends T> iterator, T value) {
796         return find(iterator, equalTo(value));
797     }
798 
799     /**
800      * Finds an arbitrary value in the input using the given Comparator.
801      * @return an iterator whose next() [if it hasNext()]
802      * will return the first instance of the value.  If the value is not in the
803      * input, then the returned iterator's hasNext() will report false.
804      */
805     static public <T> Iterator  <T>
806     find(Iterator  <? extends T> iterator, T value, Comparator  <? super T> comp) {
807         return find(iterator, equalTo(comp, value));
808     }
809 
810     
811     /**
812      * Finds an arbitrary value in the input using the given Equality operator.
813      * @return an iterator whose next() [if it hasNext()]
814      * will return the first instance of the value.  If the value is not in the
815      * input, then the returned iterator's hasNext() will report false.
816      */
817     static public <T> Iterator  <T> find(Iterator  <? extends T> iterator, T value, Equality<T> eq) {
818         return find(iterator, equalTo(eq, value));
819     }
820 
821     
822     /**
823      * Finds a value in the input for which the given function returns TRUE.
824      * @return an iterator whose next() [if it hasNext()]
825      * will return the first instance of such a value.  If no such value is in the
826      * input, then the returned iterator's hasNext() will report false.
827      */
828     static public <T> Iterator  <T> find(Iterator  <? extends T> iterator, UnaryFunctor<T,Boolean  > eq) {
829         FindIterator<T> finder = finder(iterator);
830         finder.findNext(eq);
831         return finder;
832     }
833 
834     
835     /**
836      * Finds first/next value in the input that is an element of the given array.
837      * @return an iterator whose next() [if it hasNext()] will return
838      * the first instance of any element found in the array of values.  If no such element is
839      * found then the returned iterator's hasNext() will report false.
840      */
841     static public <T> Iterator  <T> findElement(Iterator  <? extends T> iterator, T[] values) {
842         return find(iterator, elementOf(values));
843     }
844 
845     
846     /**
847      * Finds first/next value in the input that is an element of the given collection, using
848      * the collection's contains() method.
849      * @return an iterator whose next() [if it hasNext()] will return
850      * the first instance of any element found in the collection of values.  If no such element
851      * is found  then the returned iterator's hasNext() will report false.
852      */
853     static public <T> Iterator  <T>
854     findElement(Iterator  <? extends T> iterator, Collection  <? extends T> values) {
855         return find(iterator, elementOf(values));
856     }
857 
858     /**
859      * Finds first/next value in the input that is an element of the given array, using
860      * the given Comparator to compare values.
861      * @return an iterator whose next() [if it hasNext()] will return
862      * the first instance of any element found in the array of values.  If no such element is
863      * found then the returned iterator's hasNext() will report false.
864      */
865     static public <T> Iterator  <T>
866     findElement(Iterator  <? extends T> iterator, T[] values, Comparator  <? super T> comp) {
867         return find(iterator, elementOf(values, comp));
868     }
869 
870     
871     /**
872      * Finds first/next value in the input that is an element of the given collection, using
873      * the given functor to compare values.
874      * @return an iterator whose next() [if it hasNext()] will return
875      * the first instance of any element found in collection of values.  If no such value is
876      * found then the returned iterator's hasNext() will report false.
877      */
878     static public <T> Iterator  <T>
879     findElement(Iterator  <? extends T> iterator, Collection  <? extends T> values,
880                 Comparator  <? super T> comp) {
881         return find(iterator, elementOf(values, comp));
882     }
883     
884     /**
885      * Finds first/next value in the input that is an element of the given array, using
886      * the given functor to compare values.
887      * @return an iterator whose next() [if it hasNext()] will return
888      * the first instance of any element found in the array of values.  If no such element is
889      * found then the returned iterator's hasNext() will report false.
890      */
891     static public <T> Iterator  <T>
892     findElement(Iterator  <? extends T> iterator, T[] values, BinaryFunctor<T,T,Boolean  > bf) {
893         return find(iterator, elementOf(values, bf));
894     }
895 
896     
897     /**
898      * Finds first/next value in the input that is an element of the given collection, using
899      * the given functor to compare values.
900      * @return an iterator whose next() [if it hasNext()] will return
901      * the first instance of any element found in collection of values.  If no such value is
902      * found then the returned iterator's hasNext() will report false.
903      */
904     static public <T> Iterator  <T>
905     findElement(Iterator  <? extends T> iterator, Collection  <? extends T> values,
906                 BinaryFunctor<T,T,Boolean  > bf) {
907         return find(iterator, elementOf(values, bf));
908     }
909     
910     /**
911      * Locates the first/next pair of adjacent elements in an iteration that
912      * are the same value, using the equals() method.
913      * @return an iterator whose next() [if it hasNext()] points to the first of
914      * a pair of adjacent equivalent values.  If no such pair exists, then the
915      * iterator's hasNext() will be false.
916      */
917     static public <T> Iterator  <T> findAdjacent(Iterator  <? extends T> iterator) {
918         return findAdjacent(iterator, new EqualTo<T>());
919     }
920 
921     
922     /**
923      * Locates the first/next pair of adjacent elements in an iteration that
924      * are the same value, using the given comparator.
925      * @return an iterator whose next() [if it hasNext()] points to the first of
926      * a pair of adjacent equivalent values.  If no such pair exists, then the
927      * iterator's hasNext() will be false.
928      */
929     static public <T> Iterator  <T>
930     findAdjacent(Iterator  <? extends T> iterator, Comparator  <? super T> comp) {
931         return findAdjacent(iterator, new EqualTo<T>(comp));
932     }
933 
934     
935     /**
936      * Locates the first/next pair of adjacent elements in an iteration that
937      * are the same value, using the given functor.  The functor should return
938      * TRUE when two values are to be considered equal.
939      * @return an iterator whose next() [if it hasNext()] points to the first of
940      * a pair of adjacent equivalent values.  If no such pair exists, then the
941      * iterator's hasNext() will be false.
942      */
943     static public <T> Iterator  <T>
944     findAdjacent(Iterator  <? extends T> iterator, BinaryFunctor<T,T,Boolean  > eq) {
945         // return early If the input iterator is finished, 
946         if (!iterator.hasNext()) {
947             return lookAhead(iterator, 1);
948         }
949         
950         LookAheadIterator<T> lai = lookAhead(iterator, 2);
951         while (lai.hasNextPlus(2)) {
952             T arg1 = lai.peek(1);
953             T arg2 = lai.peek(2);
954             if (eq.fn(arg1, arg2)) {
955                 return lai;
956             }
957 
958             lai.next();
959         }
960 
961         // didn't find anything, so we advance our working iterator off the end
962         // and return it.
963         lai.next();
964         return lai;
965     }
966 
967     
968     /**
969      * Finds first/next arbitrary length run of a given value in an iteration.  Runs of length zero
970      * are well-defined: every iteration begins with a run of length zero of all possible values.
971      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
972      * the first of n adjacent instances of value.  If no run of values of the requested length
973      * exist in the iteration, then the returned iterator's hasNext() will report false.
974      */
975     static public <T> Iterator  <T>
976     findRepeated (Iterator  <? extends T> iterator, int count, T value) {
977         return findRepeated(iterator, count, equalTo(value));
978     }
979     
980     /**
981      * Finds first/next arbitrary length run of a given value in an iteration using the given
982      * comparator.  Runs of length zero are well-defined: every iteration begins with
983      * a run of length zero of all possible values.
984      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
985      * the first of n adjacent instances of value.  If no run of values of the requested length
986      * exist in the iteration, then the returned iterator's hasNext() will report false.
987      */
988     static public <T> Iterator  <T>
989     findRepeated (Iterator  <? extends T> iterator, int count, T value, Comparator  <? super T> comp) {
990         return findRepeated(iterator, count, equalTo(comp, value));
991     }
992     
993     /**
994      * Finds first/next arbitrary length run of a given value in an iteration using the given
995      * equality function.  Runs of length zero are well-defined: every iteration begins with
996      * a run of length zero of all possible values.
997      * @return an iterator based on the given iterator whose next() [if it hasNext()] will return
998      * the first of n adjacent instances of value.  If no run of values of the requested length
999      * exist in the iteration, then the returned iterator's hasNext() will report false.
1000     */
1001    static public <T> Iterator  <T>
1002    findRepeated (Iterator  <? extends T> iterator, int count, T value, Equality<T> eq) {
1003        return findRepeated(iterator, count, equalTo(eq, value));
1004    }
1005    
1006    /**
1007     * Finds first/next arbitrary length run of elements in an iteration for which the
1008     * given function returns TRUE.  Runs of length zero are well-defined: every
1009     * iteration begins with a run of length zero of all possible values.
1010     * @return an iterator based on the given iterator whose next() [if it
1011     * hasNext()] will return the first of n adjacent instances of value.  If no
1012     * run of values of the requested length exist in the iteration, then the
1013     * returned iterator's hasNext() will report false.
1014     */
1015    static public <T> Iterator  <T>
1016    findRepeated (Iterator  <? extends T> iterator, int count, UnaryFunctor<T,Boolean  > eq) {
1017        if (!iterator.hasNext() || count == 0) {
1018            return new LookAheadIterator<T>(iterator, 1);
1019        }
1020
1021        LookAheadIterator<T> lai = lookAhead(iterator, count);
1022        
1023    OUTER:
1024        while (lai.hasNextPlus(count)) {
1025
1026            // ... examine the contents of the look ahead buffer ...
1027            for (int i = 1; i <= count; ++i) {
1028                T arg = lai.peek(i);
1029                
1030                // ... and if we find something in the buffer that isn't
1031                // 'equal', then we'll advance past that point in the iterator
1032                // and try again
1033                if ( ! eq.fn(arg)) {
1034                    for (int j = i; j > 0; --j) {
1035                        lai.next();
1036                    }
1037
1038                    continue OUTER;
1039                }
1040            }
1041
1042            // If we safely got off the end of the INNER loop, then we must
1043            // have found the point we're looking for.
1044            return lai;
1045        }
1046
1047        // didn't find anything, make an iterator that will return false.
1048        return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
1049    }
1050
1051    /**
1052     * Finds the given pattern in the input using the equals method.
1053     * @return an iterator whose next() [if it hasNext()] will return the first element of a
1054     * sequence that matches the pattern.  If no such match is found, then the returned iterator's
1055     * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
1056     */
1057    static public <T> Iterator  <T> findSequence(Iterator  <? extends T> iterator, T[] pattern) {
1058        return findSequence(iterator, Arrays.asList(pattern), new EqualTo<T>());
1059    }
1060
1061    
1062    /**
1063     * Finds the given pattern in the input using the equals method.
1064     * @return an iterator whose next() [if it hasNext()] will return the first element of a
1065     * sequence that matches the pattern.  If no such match is found, then the returned iterator's
1066     * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
1067     */
1068    static public <T> Iterator  <T>
1069    findSequence(Iterator  <? extends T> iterator, Collection  <? extends T> pattern) {
1070        return findSequence(iterator, pattern, new EqualTo<T>());
1071    }
1072    
1073    
1074    /**
1075     * Finds the given pattern in the input using the given comparator to determine equivalence.
1076     * @return an iterator whose next() [if it hasNext()] will return the first element of a
1077     * sequence that matches the pattern.  If no such match is found, then the returned iterator's
1078     * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
1079     */
1080    static public <T> Iterator  <T>
1081    findSequence(Iterator  <? extends T> iterator, T[] pattern, Comparator  <? super T> comp) {
1082        return findSequence(iterator, Arrays.asList(pattern), new EqualTo<T>(comp));
1083    }
1084    
1085    
1086    /**
1087     * Finds the given pattern in the collection using the given comparator to determine equivalence.
1088     * @return an iterator whose next() [if it hasNext()] will return the first element of a
1089     * sequence that matches the pattern.  If no such match is found, then the returned iterator's
1090     * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
1091     */
1092    static public <T> Iterator  <T>
1093    findSequence(Iterator  <? extends T> iterator, Collection  <? extends T> pattern,
1094                 Comparator  <T> comp) {
1095        return findSequence(iterator, pattern, new EqualTo<T>(comp));
1096    }
1097
1098    
1099    /**
1100     * Finds the given pattern in the collection using the given functor to determine equivalence.
1101     * @return an iterator whose next() [if it hasNext()] will return the first element of a
1102     * sequence that matches the pattern.  If no such match is found, then the returned iterator's
1103     * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
1104     */
1105    static public <T> Iterator  <T>
1106    findSequence(Iterator  <? extends T> iterator, T[] pattern, BinaryFunctor<T,T,Boolean  > fn) {
1107        return findSequence(iterator, Arrays.asList(pattern), fn);
1108    }
1109    
1110    
1111    /**
1112     * Finds the given pattern in the collection using the given functor to determine equivalence.
1113     * @return an iterator whose next() [if it hasNext()] will return the first element of a
1114     * sequence that matches the pattern.  If no such match is found, then the returned iterator's
1115     * hasNext() will report false.  If the pattern is empty, then the iterator will not be advanced.
1116     */
1117    static public <T> Iterator  <T>
1118    findSequence(Iterator  <? extends T> iterator, Collection  <? extends T> pattern,
1119                 BinaryFunctor<T,T,Boolean  > fn) {
1120        // return early if the input iterator is already finished, 
1121        int length = pattern.size();
1122        if (!iterator.hasNext() || length == 0) {
1123            return lookAhead(iterator, 1);
1124        }
1125        
1126        LookAheadIterator<T> lai = lookAhead(iterator, length);
1127        
1128        // So long as the LookAhead has enough room for the repeat count to
1129        // possibly fit, ...
1130        
1131    OUTER:
1132        while (lai.hasNextPlus(length)) {
1133            int idx = 1;
1134            
1135            // ... examine the contents of the look ahead buffer ...
1136            for (T obj : pattern) {
1137                
1138                // ... and if we find something in the buffer that isn't
1139                // 'equal', then advance the look ahead
1140                if (!fn.fn(obj, lai.peek(idx))) {
1141                    lai.next();
1142                    continue OUTER;
1143                }
1144
1145                ++idx;
1146            }
1147            
1148            // If we safely got off the end of the INNER loop, then we must
1149            // have found the point we're looking for.
1150            return lai;
1151        }
1152
1153        // didn't find anything, make an iterator that will return false.
1154        return new LookAheadIterator<T>(new EmptyIterator<T>(), 1);
1155    }
1156
1157    
1158    /**
1159     * Finds the point at which the input differs from the pattern.  
1160     * @return an iterator based whose next() [if it hasNext()] will return the first element which
1161     * does not match the corresponding element in the pattern.  If the pattern matches the array
1162     * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
1163     * the array but is shorter, the returned iterator will point at the next element in the array
1164     * after the length of the pattern.  If the pattern is empty, no input will  be consumed.
1165     */
1166    static public <T> Iterator  <T> findMismatch(Iterator  <? extends T> iterator, T[] pattern) {
1167        return findMismatch(iterator, Arrays.asList(pattern), new NotEqualTo<T>());        
1168    }
1169    
1170    /**
1171     * Finds the point at which the input differs from the pattern.
1172     * @return an iterator based whose next() [if it hasNext()] will return the first element which
1173     * does not match the corresponding element in the pattern.  If the pattern matches the input
1174     * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
1175     * the input but is shorter, the returned iterator will point at the next element in the input
1176     * after the length of the pattern.  If the pattern is empty, no input will be consumed.
1177     */
1178    static public <T> Iterator  <T>
1179    findMismatch(Iterator  <? extends T> iterator, Collection  <? extends T> pattern) {
1180        return findMismatch(iterator, pattern, new NotEqualTo<T>());
1181    }
1182    
1183    /**
1184     * Finds the point at which the input differs from the pattern, using the given comparator to
1185     * determine the mismatch.  
1186     * @return an iterator based whose next() [if it hasNext()] will return the first element which
1187     * does not match the corresponding element in the pattern.  If the pattern matches the array
1188     * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
1189     * the array but is shorter, the returned iterator will point at the next element in the array
1190     * after the length of the pattern.  If the pattern is empty, no input will  be consumed.
1191     */
1192    static public <T> Iterator  <T>
1193    findMismatch(Iterator  <? extends T> iterator, T[] pattern, Comparator  <? super T> comp) {
1194        return findMismatch(iterator, Arrays.asList(pattern), new NotEqualTo<T>(comp));        
1195    }
1196    
1197    /**
1198     * Finds the point at which the input differs from the pattern, using the given comparator to
1199     * determine the mismatch.  
1200     * @return an iterator based whose next() [if it hasNext()] will return the first element which
1201     * does not match the corresponding element in the pattern.  If the pattern matches the input
1202     * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
1203     * the input but is shorter, the returned iterator will point at the next element in the input
1204     * after the length of the pattern.  If the pattern is empty, no input will be consumed.
1205     */
1206    static public <T> Iterator  <T>
1207    findMismatch(Iterator  <? extends T> iterator, Collection  <? extends T> pattern,
1208                 Comparator  <? super T> comp) {
1209        return findMismatch(iterator, pattern, new NotEqualTo<T>(comp));
1210    }
1211    
1212    /**
1213     * Finds the point at which the input differs from the pattern, using the given functor to
1214     * determine the mismatch.  The functor should return TRUE if a given pair of elements does
1215     * not match.
1216     * @return an iterator based whose next() [if it hasNext()] will return the first element which
1217     * does not match the corresponding element in the pattern.  If the pattern matches the array
1218     * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
1219     * the array but is shorter, the returned iterator will point at the next element in the array
1220     * after the length of the pattern.  If the pattern is empty, no input will  be consumed.
1221     */
1222    static public <T> Iterator  <T>
1223    findMismatch(Iterator  <? extends T> iterator, T[] pattern, BinaryFunctor<T,T,Boolean  > neq) {
1224        return findMismatch(iterator, Arrays.asList(pattern), neq);        
1225    }
1226    
1227    /**
1228     * Finds the point at which the input differs from the pattern, using the given functor to
1229     * determine the mismatch.  The functor should return TRUE if a given pair of elements does
1230     * not match.
1231     * @return an iterator based whose next() [if it hasNext()] will return the first element which
1232     * does not match the corresponding element in the pattern.  If the pattern matches the array
1233     * but is longer, the returned iterator's hasNext() will report false.  If the pattern matches
1234     * the array but is shorter, the returned iterator will point at the next element in the array
1235     * after the length of the pattern.  If the pattern is empty, no input will  be consumed.
1236     */
1237    static public <T> Iterator  <T>
1238    findMismatch(Iterator  <? extends T> iterator, Collection  <? extends T> pattern,
1239                 BinaryFunctor<T,T,Boolean  > neq) {
1240        LookAheadIterator<? extends T> patternIter = new LookAheadIterator<T>(pattern.iterator());
1241        LookAheadIterator<T> lai = lookAhead(iterator, 1);
1242        while (lai.hasNextPlus(1) && patternIter.hasNextPlus(1)) {
1243            T arg1 = lai.peek(1);
1244            T arg2 = patternIter.peek(1);
1245            if (neq.fn(arg1,arg2)) {
1246                return lai;
1247            }
1248            
1249            lai.next();
1250            patternIter.next();
1251        }
1252
1253        return lai;
1254    }                                       
1255
1256    // ==============
1257    // Implementation
1258    // ==============
1259
1260    static public <T> UnaryFunctor<T,Boolean  > elementOf(T[] values) {
1261        return new ElementOf<T>().bind2nd(Arrays.asList(values));
1262    }
1263    
1264    static public <T> UnaryFunctor<T,Boolean  > elementOf(Collection  <? extends T> values) {
1265        return new ElementOf<T>().bind2nd(values);
1266    }
1267    
1268    static public <T> UnaryFunctor<T,Boolean  > elementOf(T[] values, Comparator  <? super T> comp) {
1269        return new ElementOf<T>(new EqualTo<T>(comp)).bind2nd(Arrays.asList(values));
1270    }
1271    
1272    static public <T> UnaryFunctor<T,Boolean  >
1273    elementOf(Collection  <? extends T> values, Comparator  <? super T> comp) {
1274        return new ElementOf<T>(new EqualTo<T>(comp)).bind2nd(values);
1275    }
1276    
1277    static public <T> UnaryFunctor<T,Boolean  > elementOf(T[] values, BinaryFunctor<T,T,Boolean  > bf) {
1278        return new ElementOf<T>(bf).bind2nd(Arrays.asList(values));
1279    }
1280    
1281    static public <T> UnaryFunctor<T,Boolean  >
1282    elementOf(Collection  <? extends T> values, BinaryFunctor<T,T,Boolean  > bf) {
1283        return new ElementOf<T>(bf).bind2nd(values);
1284    }
1285    
1286    static private <T> FindIterator<T> finder(Iterator  <? extends T> iterator) {
1287        if (iterator instanceof FindIterator)
1288            return (FindIterator<T>) iterator;
1289
1290        return new FindIterator(iterator);
1291    }
1292
1293    static private <T> LookAheadIterator<T> lookAhead(Iterator  <? extends T> iterator, int size) {
1294        if (iterator instanceof LookAheadIterator) {
1295            LookAheadIterator<T> lai = (LookAheadIterator<T>) iterator;
1296            if (lai.getMaxPeekSize() >= size)
1297                return lai;
1298        }
1299        
1300        return new LookAheadIterator(iterator, size);
1301    }
1302}
1303
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags