// TwoFingeredIntersect
// Implements a two fingered intersect over two sets of T's (some comparable
// type)
// (I would have liked to replace T by a generic argument T, but
// the compiler wasn't happy about it.)
// The intersection is returned in an ArrayList.
//
import java.util.Iterator; 
import java.util.ArrayList;

public class TwoFingeredIntersect<T extends Comparable<? super T>,
      U extends Iterable<T>,
      V extends Iterable<T>
    > {
                                 
   
// actual intersect method
 public ArrayList<T> intersect(U x, V y) {
     ArrayList<T> a = new ArrayList<T>();
     Iterator<T> uit = x.iterator();
     Iterator<T> vit = y.iterator();
     if (!uit.hasNext() || !vit.hasNext()) return a;
                                      // one of the lists is empty
     T i = uit.next();
     T j = vit.next();
     while (true) {
       if (i.compareTo(j) < 0) {
          if (! uit.hasNext()) return a;
          i = uit.next();
         }
       else if (i.compareTo(j) > 0) {
          if (! vit.hasNext()) return a;
          j = vit.next();
         }
       else {  // i and j are equal
          a.add(i);
          if ((! uit.hasNext()) || (! vit.hasNext())) return a;
          i = uit.next();
          j = vit.next();
         }
      } 
     }            
 }