interface Comparator{
  int compare(Object obj1, Object obj2);
}

/*
interface ISame{
    // determine whether the this objects represent the same information
    // as the given one
    boolean same(Object obj);
}
*/

// to represent a traversal of a data type 
interface Traversal{
   
   // produce the currently first object in the data set 
   Object current();

   // advance to the next element of the data set 
   Traversal advance();
   
   // are there more items to produce/advance over? 
   boolean hasMore();
}


// Represents a binary search tree
abstract public class ABST implements ISame, Traversal {
  
  // must establish at the beginning the mode for comparison
  Comparator c;
  
  // inserts an Object into this tree
  abstract ABST insert(Object obj);
  
  // removes an Object from this tree and returns the resulting tree
  abstract ABST remove(Object obj);
  
  // is this tree the same as the given object?
  abstract public boolean same(Object obj);

  // produce the currently first object in the data set 
  abstract public Object current();

  // advance to the next element of the data set 
  abstract public Traversal advance();
  
  // are there more items to produce/advance over? 
  abstract public boolean hasMore();
}


class BSTLeaf extends ABST {
  
  BSTLeaf(Comparator c){
    this.c = c;
  }

  // inserts an Object into this tree  
  ABST insert(Object obj) {
    return new BSTNode(obj, this, this);
  }

  // removes an Object from this tree and returns the resulting tree
  ABST remove(Object obj) {
    return this;
/*
    throw new UnsupportedOperationException(
        "Object cannot be removed from an empty tree");
*/
  }

  /*---- methods to compare equality --------------------*/
  // is this leaf the same as the given object?
  public boolean same(Object obj) {
    return obj instanceof BSTLeaf;
  }
  
  /*---- methods to implement Traversal -----------------*/
  // produce the currently first object in the data set 
  public Object current() {
    return this;
/*
    throw new UnsupportedOperationException(
    "No current Object in an empty tree");
*/
}

  // advance to the next element of the data set 
  public Traversal advance() {
    return this;
/*
    throw new UnsupportedOperationException(
    "Cannot advance in an empty tree");
*/
}
  
  // are there more items to produce/advance over? 
  public boolean hasMore() {
    return false;
  }
  
  public String toString() {return "n()";}

}



// import java.util.Comparator;

// represents an internal node in a binary search tree
class BSTNode extends ABST {
  
  Object data;
  ABST left;
  ABST right;
  
  BSTNode(Object data, ABST left, ABST right) {
    this.c = left.c;
    this.data = data;
    this.right = right;
    this.left = left;
  }

  // inserts an Object into this tree
  ABST insert(Object obj) {
    //
    // If o is to the left recur down the left
    //
    if (c.compare(obj, this.data) < 0) 
      return new BSTNode(this.data, this.left.insert(obj), this.right);
    //
    // If o is to the left recur down the left
    //    
    else if (c.compare(obj, this.data) > 0) 
      return new BSTNode(this.data, this.left, this.right.insert(obj));      
    //
    // If we've inserted this data we're done
    //
    else return this;
  }

  // removes an Object from this tree and returns the resulting tree
  ABST remove(Object obj) {
    //
    // If obj is before current data remove from the left subtree
    //    
    if (c.compare(obj, this.data) < 0) 
      return new BSTNode(this.data, this.left.remove(obj), this.right);
    //
    // If obj is after current data remove from the right subtree
       //    
    else if (c.compare(obj, this.data) > 0) 
      return new BSTNode(this.data, this.left, this.right.remove(obj));
    
    else 
      return removeRoot();
  }
  
  // produce a tree with the root removed from this tree
  ABST removeRoot(){
    // no right child -- retur left subtree
    if (this.right instanceof BSTLeaf) 
      return this.left;
    
    // no left child -- return right subtree
    else if (this.left instanceof BSTLeaf) 
      return this.right;
    
    // If both left and right have kids, find the first of the right subtree
    // and return a new node with that data and the following kids:
    //  - left:  untouched left
    //  - right: new node constructed of the left without the first value
    //
    else
      return new BSTNode(((BSTNode)this.right).findFirst(), 
                         this.left,
                         ((BSTNode)this.right).removeFirst());
  }
   
  // find the first item in this binary search tree
  Object findFirst() {
    if (this.left instanceof BSTLeaf) 
      return this.data;
    else
      return ((BSTNode)this.left).findFirst();
  }
  
  // produce the tree with the first node removed from this tree
  ABST removeFirst(){
    if (this.left instanceof BSTLeaf) 
      return this.right;
    else
      return new BSTNode(this.data,
                          ((BSTNode)this.left).removeFirst(),
                          this.right);
  }
  
  /*---- methods to compare equality --------------------*/
    // is this BSTNode the same as the given object?
  public boolean same(Object a) {
    if (!(a instanceof BSTNode)) 
      return false;
    else 
      return this.sameBSTNode((BSTNode) a);
   }
  
  // is this BSTNode the same as the given BSTNode?
  boolean sameBSTNode(BSTNode that){
    return this.data.equals(that.data) && 
           this.left.same(that.left) && 
           this.right.same(that.right);
  }
  
  /*---- methods to implement Traversal -----------------*/
  // produce the currently first object in the data set 
  public Object current() {
    return findFirst();
  }

  // advance to the next element of the data set 
  public Traversal advance() {
    return this.removeFirst();
  }
  
  // are there more items to produce/advance over? 
  public boolean hasMore() {
    return true;
  }
  
  /*---- method to allow pretty printing ----------------*/
  public String toString() {
    return "n(".concat(this.data.toString()).concat(", ").concat(
                  this.left.toString()).concat(", ").concat(
                  this.right.toString()).concat(")");
  }
}


interface ILoObject extends ISame{}

class MTLoObject implements ILoObject{
  MTLoObject() {}

  int size(){ return 0; }

  boolean contains (Object that){
    return false;
  }

  // is this the same as the given object?
  public boolean same(Object obj){ return obj instanceof MTLoObject; }
}

class ConsLoObject implements ILoObject{
  Object first;
  ILoObject rest;

  ConsLoObject(Object first, ILoObject rest){
    this.first = first;
    this.rest = rest;
  }

/* TEMPLATE:
... this.first ...                   -- Object
... this.rest ...                    -- ILoObject
... this.rest.mm() ...               -- nnn
*/

  // is this the same as the given object?
  public boolean same(Object obj){ 
    if (obj instanceof ConsLoObject)
      return this.sameConsLoObject(((ConsLoObject)obj));
    else
      return false;
  }

  // is this the same as the given ConsLoObject?
  boolean sameConsLoObject(ConsLoObject that){ 
    return //((ISame)this.first).same(that.first) &&
           this.first.equals(that.first) &&
           this.rest.same(that.rest);
  }

}


class StringComparator implements Comparator{
  StringComparator(){}
  
  public int compare(Object obj1, Object obj2){
    return ((String)obj1).compareTo((String)obj2);
  }
}


class Examples {
    
  Examples () {}
 
  // data definitions
  ABST leaf = new BSTLeaf(new StringComparator());
  
  ABST tree = new BSTNode("b", 
                          new BSTNode("a", leaf, leaf),
                          new BSTNode("c", leaf, leaf));   

  
 
 /*------------- algorithms that consume traversals -----------*/
  // count the elements in the data set given by the traversal
  int count(Traversal tr){
    if (tr.hasMore())
      return 1 + count(tr.advance());
    else
      return 0;
  }
 
  // find the given string in the data set given by the traversal
  boolean find(Traversal tr, String s){
    if (tr.hasMore())
      if (((String)tr.current()).equals(s))
        return true;
      else
        return find(tr.advance(),s);
    else
      return false;
  }
 
  // produce a list of objects by removing the given string
  // from the data set given by the traversal
  ILoObject remove(Traversal tr, String s){
    if (tr.hasMore())
      if (((String)tr.current()).equals(s))
        return remove(tr.advance(), s);
      else
        return new ConsLoObject(tr.current(), remove(tr.advance(),s));
    else
      return new MTLoObject();
  }

  // test methods for count in Examples class
  boolean testCountABST1 = count(leaf) == 0;
  boolean testCountABST2 = count(tree) == 3;
  
  // test methods for find in Examples class
  boolean testFindABST1 = find(leaf, "a") == false;
  boolean testFindABST2 = find(tree, "a") == true;
  boolean testFindABST3 = find(tree, "d") == false;
  
  // test methods for remove in Examples class
  boolean testRemoveABST1 = remove(tree, "a").same(new ConsLoObject("b", 
                                                   new ConsLoObject("c", new MTLoObject())));
  boolean testRemoveABST2 = remove(tree, "b").same(new ConsLoObject("a", 
                                                   new ConsLoObject("c", new MTLoObject())));
  boolean testRemoveABST3 = remove(leaf, "a").same(new MTLoObject());
  
  public static void main(String argv[]){
     Examples e = new Examples();
     System.out.println("testCountABST1: " + e.testCountABST1);
     System.out.println("testCountABST2: " + e.testCountABST2);

     System.out.println("testFindABST1: " + e.testFindABST1);
     System.out.println("testFindABST2: " + e.testFindABST1);
     System.out.println("testFindABST3: " + e.testFindABST1);

     System.out.println("testRemoveABST1: " + e.testRemoveABST1);
     System.out.println("testRemoveABST2: " + e.testRemoveABST2);
     System.out.println("testRemoveABST3: " + e.testRemoveABST3);
 }
 
}