/** Generic merge for sorted sequences. */
public abstract class Merger {
  private Object a, b; 	                // current elements in A and B
  private ObjectIterator iterA, iterB;  // iterators for A and B
  /** Generic merge template method */
  public void merge(Sequence A, Sequence B, Comparator comp, Sequence C) {
    iterA = A.elements();
    iterB = B.elements();
    boolean aExists = advanceA();  // Boolean test if there is a current a
    boolean bExists = advanceB();  // Boolean test if there is a current b
    while (aExists && bExists) {   // Main loop for merging a and b
      if (comp.isLessThan(a, b)) {
        aIsLess(a, C);  aExists = advanceA();
      }
      else if (comp.isEqualTo(a, b)) {
        bothAreEqual(a, b, C);
        aExists = advanceA();  bExists = advanceB();
      } else {
        bIsLess(b, C);  bExists = advanceB();
      }
    }
    while (aExists) { aIsLess(a, C); aExists = advanceA(); }
    while (bExists) { bIsLess(b, C); bExists = advanceB(); }
  }
  // auxiliary methods to be specialized by subclasses
  protected void aIsLess(Object a, Sequence C) { }
  protected void bothAreEqual(Object a, Object b, Sequence C) { }
  protected void bIsLess(Object b, Sequence C) { }
  // helper methods
  private boolean advanceA() {
    if (iterA.hasNext()) {
      a = iterA.nextObject(); 
      return true;
    }
    return false;
  }
  private boolean advanceB() {
    if (iterB.hasNext()) {
      b = iterB.nextObject();
      return true;
    }
    return false;
  }  
}