public class SearchTree extends BinaryTree
   // The contents of a SearchTree are ordered
   // under a left to right infix traversal
 { public SearchTree(Object obj) { super(obj, empty, empty); }

   public SearchTree find(Object obj)                    // e.g. subt=t.find(x)
   // seek subtree, if any, which has obj at its root
    { if(this.isEmpty()) return this; // doubles as present/absent flag
      //else
      int comp = objCompareTo(this.obj, obj);
      if( comp > 0 )      return ((SearchTree)this.left).find(obj);
      else if( comp < 0 ) return ((SearchTree)this.right).find(obj);
      else /* found */  return this;
    }//find(...)

                   // a local Class, this default ScanAction has no nett effect
   protected class ScanAction
    { public SearchTree descend(Object obj, SearchTree t)       // descend(...)
       { return t.scan(obj, this); }
      public SearchTree found(SearchTree  t) { return t; }      // found(t)
      public SearchTree notFound(Object obj) { return empty; }  // notFound(x)
    }//ScanAction

   protected SearchTree scan(Object obj, ScanAction act)    // e.g. t.scan(...)
    { if(this.isEmpty()) return act.notFound(obj);
      //else
      int comp = objCompareTo(this.obj, obj);
      if( comp == 0) return act.found(this); // keys are equal
      //else
      if(comp > 0) this.left = act.descend(obj, (SearchTree)this.left);
      else         this.right= act.descend(obj, (SearchTree)this.right);
      return this;
    }//scan(...) traverse a tree seeking obj, possibly modifying the tree


   private class InsertScanAction extends ScanAction
    { public SearchTree notFound(Object obj) { return new SearchTree(obj); } }

   public SearchTree insert(Object obj)                     // e.g. t.insert(x)
    { return this.scan(obj, new InsertScanAction()); }


   class DeleteScanAction extends ScanAction
    { public SearchTree found(SearchTree t) // delete root of t
       { if(t.isLeaf()) return empty;
	 if(t.left.isEmpty()) return (SearchTree)t.right; // link out
	 if(t.right.isEmpty()) return (SearchTree)t.left; // link out
	 //else a full fork
	 t.obj = farLeft((SearchTree)t.right).obj; //copy least in right subt'
	 t.right = ((SearchTree)t.right).delete(t.obj); // & delete original
	 return t;
    }  }//DeleteScanAction

   private static SearchTree farLeft(SearchTree t) // left-most subtree of t
    { if( t.left.isEmpty() ) return t;
      /*else*/ return farLeft((SearchTree)t.left);
    }//farLeft(...)

   public SearchTree delete(Object obj)                   // e.g. t=t.delete(x)
    { return this.scan(obj, new DeleteScanAction()); }


   protected static class EmptySearchTree // NB no multiple inheritance
    extends SearchTree  implements EmptyBinaryTreeMarker // see BinaryTree
    { public EmptySearchTree() { super(null); }
      private void err(String s)
       { throw new RuntimeException("method " + s + " on SearchTree.empty"); }
      public Object     contents() { err("contents"); return null; }
      public BinaryTree left()     { err("left"); return null; }
      public BinaryTree right()    { err("right"); return null; }
      public Tree       subTree(int i) { err("subTree"); return null; }
      public int        fanOut()   { err("fanOut"); return 0; }
    }//EmptyTree

   public  static final SearchTree empty = new EmptySearchTree();


   protected static int objCompareTo(Object obj1, Object obj2) //order contents
    { if(obj1 == null)
	 if(obj2 == null) return 0;  else return 1;
      else if(obj2 == null) /* and obj1 is not */ return -1;
      // else neither is null ...
      Class c1 = obj1.getClass(), c2 = obj2.getClass();
      return obj1.toString().compareTo(obj2.toString());  // ie lexical, but...
      // ... really should use < etc. if are Number otherwise use
      // compareTo( ) if c1=c2 and has a c1.compareTo(c2) method,
      // and use the `key' field if obj has such a member field
      // but I'm tired
    }
 }//SearchTree

// L.Allison, Computer Science and Software Engineering, Monash University