import java.util.*;

class ETable3 implements ETable
{
// Table class with Enumeration, data stored in ordered trees
// Enumeration implemented with stack

 Cell tree;

 public boolean delete(String key)
 {
  if(tree!=null)
     if(tree.left==null&&tree.right==null)
        {
         if(tree.item.equalKey(key))
            {
             tree=null;
             return true;
            }
         else
            return false;
        }
     else
        return delete(key,tree);
  else
     return false;
 }

 private static boolean delete(String key,Cell t)
 {
  if(t.item.lessThan(key))
     if(t.right.left==null&&t.right.right==null)
         if(t.right.item.equalKey(key))
            {
             t.right=null;
             return true;
            }
         else
            return false;
     else
        return delete(key,t.right);
  else if(!t.item.equals(key))
     if(t.left.left==null&&t.left.right==null)
        if(t.left.item.equalKey(key))
           {
            t.left=null;
            return true;
           }
        else
           return false;
    else
       return delete(key,t.left);
  else
     {
      if(t.left==null)
         {
          t.item=t.right.item;
          t.right=t.right.right;
         }
      else if(t.left.right==null)
         {
          t.item=t.left.item;
          t.left=t.left.left;
         }
      else
         t.item = removeRightmost(t.left);
      return true;
     }
 }

 private static KeyObject removeRightmost(Cell t)
 {
  if(t.right.right==null)
     {
      KeyObject rightmost = t.right.item;
      t.right = t.right.left;
      return rightmost;
     }
  else
     return removeRightmost(t.right);
 }

 public void add(KeyObject obj)
 {
  if(tree==null)
     tree = new Cell(obj,null,null);
  else
     add(obj,tree);
 }

 private static void add(KeyObject obj,Cell t)
 {
  if(t.item.lessThan(obj))
     if(t.right==null)
        t.right = new Cell(obj,null,null);
     else
        add(obj,t.right);
  else
     if(t.left==null)
        t.left = new Cell(obj,null,null);
     else
        add(obj,t.left);
 }

 public KeyObject retrieve(String key)
 {
  return retrieve(key,tree);
 }

 private static KeyObject retrieve(String key,Cell t)
 {
  if(t==null)
     return null;
  else if(t.item.equalKey(key))
     return t.item;
  else if(t.item.lessThan(key))
     return retrieve(key,t.right);
  else
     return retrieve(key,t.left);
 }

 public Enumeration getEnumeration()
 {
  return new MyEnumeration();
 }

 private static class Cell
 {
  KeyObject item;
  Cell left,right;
  
  Cell(KeyObject n,Cell l,Cell r)
  {
   item=n;
   left=l;
   right=r;
  }
 }

 private class MyEnumeration implements Enumeration
 {
  ECell stack;
  
  MyEnumeration()
  {
   if(tree==null)
     stack=null;
   else
     stack = new ECell(tree,null);
  }

  public boolean hasMoreElements()
  {
   return stack!=null;
  }

  public Object nextElement()
  {
   Cell t = stack.first;
   stack = stack.next;
   if(t.left!=null)
     stack = new ECell(t.left,stack);
   if(t.right!=null)
     stack = new ECell(t.right,stack);
   return t.item;
  }

  private class ECell
  {
   Cell first;
   ECell next;
   
   ECell(Cell f,ECell n)
   {
    first=f;
    next=n;
   }
  }
 }
}