import tester.Tester;

 
/*
                           ......................................................................................
                           :                                                                                    :
                           v                                                                                    :
        +---------------------------+                                                                           :
        | IListVisitor<R, T>        |                                                                           :
        +---------------------------+                                                                           :
        | <R> forMT()               |                                                                           :
        | <R> forCons(Cons<T> that) |                                                                           :
        +---------------------------+                                                                           :
                / \                                                                                             :
                ---                                                                                             :
                 |                                                                                              :
     ---------------------------------------------------------------------------                                :
     |                                    |                                    |                                :
+----------------------------------+ +-------------------------------+ +-------------------------------------+  :
| OccursVisitor<T>  R:Integer      | | SubstVisito<T>  R:IList       | | RemtVisitor<T>  R:IList             |  :
+----------------------------------+ +-------------------------------+ +-------------------------------------+  :
| T item                           | | T rem                         | | Object rem                          |  :
+----------------------------------+ | T add                         | +-------------------------------------+  :
| R forMT(){                       | +-------------------------------+ | R forMT(){                          |  :
|   return new Integer(0);}        | | R forMT(){                    | |   return new Integer(0);}           |  :
|                                  | |   return new MT<T>();}        | |                                     |  :
| R forCons(Cons that){            | |                               | | R forCons(Cons that){               |  :
|  if (that.first.equals(item))    | | R forCons(Cons that){         | |  if (that.first.equals(rem)){       |  :
|   return new Integer(((Integer)  | |  if (that.first.equals(rem)){ | |   return that.rest.accept(this);    |  :
|     (that.rest.accept(this)))    | |   that.first = add;           | |  else{                              |  :
|        .intValue() + 1);         | |   that.rest.accept(this);     | |   return new Top(that.t,            |  :
|  else                            | |   return that;  }             | |    (IList)that.rest.accept(this));} |  :
|   return that.rest.accept(this); | |  else{                        | | }                                   |  :
| }                                | |   that.rest.accept(this);     | +-------------------------------------+  :
+----------------------------------+ |   return that;} }             |                                          :
                                     +-------------------------------+                                          :  
                                                                                                                :
         +-----------------------------------------------+                                                      :
         | IList<T>                                      |<---------------------+                               :
         +-----------------------------------------------+                      |                               :
         | abstract <R> R accept(IListVisitor<R, T> ask) |.......................................................
         +-----------------------------------------------+                      |
                           / \                                                  |
                           ---                                                  |
                            |                                                   |
              -------------------------------------                             |
              |                                   |                             |
    +----------------------------------+  +----------------------------------+  |
    | MT<T>                            |  | Cons<T>                          |  |
    +----------------------------------+  +----------------------------------+  |
    | <R> R  accept(IListVisitor ask){ |  | T     first                      |  |
    |   return ask.forBot();}          |  | IList rest                       |--+    
    +----------------------------------+  +-+--------------------------------+
                                          | <R> R  accept(IListVisitor ask){ |
                                          |   return ask.forTop();}          |
                                          +----------------------------------+
*/

interface IListVisitor<R, T>{
  R forMT();
  R forCons(Cons<T> that);
}

class OccursVisitorT<T>  implements IListVisitor<Integer, T>{
  
  T item;
  OccursVisitorT(T item){
    this.item = item;
  }
  
  public Integer forMT(){
    return new Integer(0);
  }
  
  public Integer forCons(Cons<T> that){
    if (that.first.equals(item))
      return new Integer(((Integer)(that.rest.accept(this))).intValue() + 1);
    else
      return (Integer)that.rest.accept(this);
  }
}

class SubstVisitorT<T>  implements IListVisitor<IList<T>, T>{
  
  T rem;
  T add;
  
  SubstVisitorT(T rem, T add){
    this.rem = rem;
    this.add = add;
  }
  
  public IList forMT(){
    return new MT<T>();
  }
  
  public IList<T> forCons(Cons<T> that){
    if (that.first.equals(rem)){
      that.first = add;
      that.rest.accept(this);
      return (IList<T>)that; 
    }
    else{
      that.rest.accept(this);
      return that;
    }
  }
}

class RemVisitorT<T>  implements IListVisitor<IList<T>, T>{
  
  T rem;
  
  RemVisitorT(T rem){
    this.rem = rem;
  }
  
  public IList<T> forMT(){
    return new MT<T>();
  }
  
  public IList<T> forCons(Cons<T> that){
    if (that.first.equals(rem))
      return (IList<T>)that.rest.accept(this);
    else
      return new Cons<T>(that.first, (IList<T>)that.rest.accept(this));
  }
}

interface IList<T>{
  abstract <R> R accept(IListVisitor<R, T> ask);
}

class MT<T> implements IList<T>{
  MT(){}
  public <R> R  accept(IListVisitor<R, T> ask){
    return ask.forMT();
  }
}

class Cons<T> implements IList<T>{
  T     first;
  IList rest;
  
  Cons(T first, IList<T> rest){
    this.first = first;
    this.rest = rest;
  }
  
  public <R> R  accept(IListVisitor<R, T> ask){
    return ask.forCons(this);
  }  
}

interface IListMan<T>{
  int addItem(T item);
  int remItem(T rem);
  int substItem(T rem, T add);
  int occItem(T item);
}

class ManageIListMan<T> implements IListMan<T>{
  IList<T> alist = new MT<T>();

  public int addItem(T item){
    alist = new Cons<T>(item, alist);
    return occItem(item);
  }

  public int remItem(T rem){
    alist = (IList)alist.accept(new RemVisitorT(rem));
    return occItem(rem);
  }

  public int substItem(T rem, T add){
    alist = (IList)alist.accept(new SubstVisitorT(rem, add));
    return occItem(add);
  }

  public int occItem(T item){
    return ((Integer)alist.accept(new OccursVisitorT(item))).intValue();
  }
}


class ExamplesT{
    
  IListMan<String> makeACATM(){
    IListMan<String> tmp = new ManageIListMan<String>();
    tmp.addItem("anchovy");
    tmp.addItem("cheese");
    tmp.addItem("anchovy");
    tmp.addItem("tuna");
    tmp.addItem("mushroom");
    return tmp;
  } 
  
  IListMan<String> makeCTM(){
    IListMan<String> tmp = new ManageIListMan<String>();
    tmp.addItem("cheese");
    tmp.addItem("tuna");
    tmp.addItem("mushroom");
    return tmp;
  } 
  
  IListMan<String> makeOCTM(){
    IListMan<String> tmp = new ManageIListMan<String>();
    tmp.addItem("olive");
    tmp.addItem("cheese");
    tmp.addItem("tuna");
    tmp.addItem("mushroom");
    return tmp;
  } 
  
  IListMan<String> makeOCOTM(){
    IListMan<String> tmp = new ManageIListMan<String>();
    tmp.addItem("olive");
    tmp.addItem("cheese");
    tmp.addItem("olive");
    tmp.addItem("tuna");
    tmp.addItem("mushroom");
    return tmp;  
  }
  
  public void testAdd(Tester t){
    IListMan<String> tmp = makeCTM();
    t.checkExpect(tmp.addItem("olive"), 1);
    t.checkExpect(tmp.addItem("mushroom"), 2);
  }
  
  public void testRem(Tester t){
    IListMan<String> tmp = makeOCTM();
    t.checkExpect(tmp.remItem("olive"), 0);
    tmp = makeACATM();
    t.checkExpect(tmp.remItem("anchovy"), 0);
  }
  
  public void testSubst(Tester t){
    IListMan<String> tmp = makeOCOTM();
    t.checkExpect(tmp.substItem("anchovy", "olive"), 2);
    tmp = makeACATM();
    t.checkExpect(tmp.substItem("anchovy", "olive"), 2);
  }
  public void testOccur(Tester t){
    IListMan<String> tmp = makeOCOTM();
    t.checkExpect(tmp.occItem("mushroom"), 1);
    t.checkExpect(tmp.occItem("olive"), 2);
  }
}