/*
                           ...............................................................................
                           :                                                                             :
                           v                                                                             :
        +-------------------------+                                                                      :
        | IPieVisitor             |                                                                      :
        +-------------------------+                                                                      :
        | Object forBot()         |                                                                      :
        | Object forTop(Top that) |                                                                      :
        +-------------------------+                                                                      :
                / \                                                                                      :
                ---                                                                                      :
                 |                                                                                       :
     ---------------------------------------------------------------------------                         :
     |                                    |                                    |                         :
+---------------------------------+  +---------------------------+  +---------------------------------+  :
| OccursVisitor                   |  | SubstVisitor              |  | RemtVisitor                     |  :
+---------------------------------+  +---------------------------+  +---------------------------------+  :
| Object o                        |  | Object n                  |  | Object o                        |  :
+---------------------------------+  | Object o                  |  +---------------------------------+  :
| Object forBot(){                |  +---------------------------+  | Object forBot(){                |  :
|   return new Integer(0);}       |  | Object forBot(){          |  |   return new Integer(0);}       |  :
|                                 |  |   return new Integer(0);} |  |                                 |  :
| Object forTop(Top that){        |  |                           |  | Object forTop(Top that) {       |  :
|  if (that.t.equals(o))          |  | Object forTop(Top that){  |  |  if (that.t.equals(o))          |  :
|   return new Integer(((Integer) |  |  if (that.t.equals(o)){   |  |   return that.r.accept(this);   |  :
|        (that.r.accept(this)))   |  |   that.t = n;             |  |  else                           |  :
|        .intValue() + 1);        |  |   that.r.accept(this);    |  |   return new Top(that.t,        |  :
|  else                           |  |   return that;  }         |  |    (APie)that.r.accept(this));} |  :
|   return that.r.accept(this);}  |  |  else{                    |  +---------------------------------+  :
+---------------------------------+  |   that.r.accept(this);    |                                       :
                                     |   return that;} }         |                                       :
                                     +---------------------------+                                       :  
                                                                                                         :
         +----------------------------------------+                                                      :
         | APie                                   |                                                      :
         +----------------------------------------+                                                      :
         | abstract Object accept(PieVisitor ask) |.......................................................
         +----------------------------------------+
                           / \
                           ---
                            |
              -------------------------------------
              |                                   |
    +---------------------------------+  +---------------------------------+
    | Bot                             |  | Top                             |
    +---------------------------------+  +---------------------------------+
    | Object accept(IPieVisitor ask){ |  | Object  t                       |
    |   return ask.forBot();}         |  | APie    r                       |    
    +---------------------------------+  +-+-------------------------------+
                                         | Object accept(IPieVisitor ask){ |
                                         |   return ask.forTop();}         |
                                         +---------------------------------+
*/
                  
import tester.*;

interface IPieMan{
  int addTop(Object t);
  int remTop(Object t);
  int substTop(Object n, Object o);
  int occTop(Object o);
}

class ManagePieMan implements IPieMan{
  Pie p = new Bot();

  public int addTop(Object t){
    p = new Top(t, p);
    return occTop(t);
  }

  public int remTop(Object t){
    p = (Pie)p.accept(new RemVisitor(t));
    return occTop(t);
  }

  public int substTop(Object n, Object o){
    p = (Pie)p.accept(new SubstVisitor(n, o));
    return occTop(n);
  }

  public int occTop(Object o){
    return ((Integer)p.accept(new OccursVisitor(o))).intValue();
  }
}

interface PieVisitor{
  Object forBot();
  Object forTop(Top that);
}

abstract class Pie{
  abstract Object accept(PieVisitor ask);
}

class Bot extends Pie{
  Object accept(PieVisitor ask){
    return ask.forBot();
  }
}

class Top extends Pie{
  Object t;
  Pie r;
  Top(Object t, Pie r){
    this.t = t;
    this.r = r;
  }

  Object accept(PieVisitor ask){
    return ask.forTop(this);
  }
}

class OccursVisitor implements PieVisitor{
  Object a;
  OccursVisitor(Object a){
    this.a = a;
  }

  public Object forBot(){
    return new Integer(0);
  }

  public Object forTop(Top that){
    if (that.t.equals(a))
      return new Integer(((Integer)(that.r.accept(this)))
                                      .intValue() + 1);
    else
      return that.r.accept(this);
  }
}

class SubstVisitor implements PieVisitor{
  Object n;
  Object o;
  SubstVisitor(Object n, Object o){
    this.n = n;
    this.o = o;
  }

  public Object forBot(){
    return new Bot();
  }

  public Object forTop(Top that){
    if (that.t.equals(o)){
      that.t = n;
      that.r.accept(this);
      return that;
    }
    else{
      that.r.accept(this);
      return that;
    }
  }
}

class RemVisitor implements PieVisitor{
  Object o;
  RemVisitor(Object o){
    this.o = o;
  }

  public Object forBot(){
    return new Bot();
  }

  public Object forTop(Top that){
    if (that.t.equals(o))
      return that.r.accept(this);
    else
      return new Top(that.t, (Pie)that.r.accept(this));
  }
}

class Examples{
    
  IPieMan makeACATM(){
    IPieMan tmp = new ManagePieMan();
    tmp.addTop("anchovy");
    tmp.addTop("cheese");
    tmp.addTop("anchovy");
    tmp.addTop("tuna");
    tmp.addTop("mushroom");
    return tmp;
  } 
  
  IPieMan makeCTM(){
    IPieMan tmp = new ManagePieMan();
    tmp.addTop("cheese");
    tmp.addTop("tuna");
    tmp.addTop("mushroom");
    return tmp;
  } 
  
  IPieMan makeOCTM(){
    IPieMan tmp = new ManagePieMan();
    tmp.addTop("olive");
    tmp.addTop("cheese");
    tmp.addTop("tuna");
    tmp.addTop("mushroom");
    return tmp;
  } 
  
  IPieMan makeOCOTM(){
    IPieMan tmp = new ManagePieMan();
    tmp.addTop("olive");
    tmp.addTop("cheese");
    tmp.addTop("olive");
    tmp.addTop("tuna");
    tmp.addTop("mushroom");
    return tmp;  
  }
  
  public void testAdd(Tester t){
    IPieMan tmp = makeCTM();
    t.checkExpect(tmp.addTop("olive"), 1);
    t.checkExpect(tmp.addTop("mushroom"), 2);
  }
  
  public void testRem(Tester t){
    IPieMan tmp = makeOCTM();
    t.checkExpect(tmp.remTop("olive"), 0);
    tmp = makeACATM();
    t.checkExpect(tmp.remTop("anchovy"), 0);
  }
  
  public void testSubst(Tester t){
    IPieMan tmp = makeOCOTM();
    t.checkExpect(tmp.substTop("anchovy", "olive"), 2);
    tmp = makeACATM();
    t.checkExpect(tmp.substTop("anchovy", "olive"), 2);
  }
  public void testOccur(Tester t){
    IPieMan tmp = makeOCOTM();
    t.checkExpect(tmp.occTop("mushroom"), 1);
    t.checkExpect(tmp.occTop("olive"), 2);
  }
}