/**
 * A class that implements two traversal-based algorithms,  
 * contains and countSuch.
 * 
 * @since 10 July 2008
 * @author Viera K. Proulx
 */

 class Algorithms {
   
   String match = "Hello";
   
  /** Produce a list of only strings that equal to match - from this list. */
   ILoString onlyMatch(ILoString slist){
    if (slist.isEmpty()){
        return new MTLoString();      
    }
    else {
      if (slist.getFirst().equals(match)){
          return new ConsLoString(slist.getFirst(), onlyMatch(slist.getRest()));      
      }
      else{
          return onlyMatch(slist.getRest());               
      }
    }
  } 

  /** Count how many strings in this list are equal to match. */
   int countSuch(ILoString slist){
    if (slist.isEmpty()){
        return 0;      
    }
    else {
      if (slist.getFirst().equals(match)){
          return 1 + countSuch(slist.getRest());        
      }
      else{
          return countSuch(slist.getRest());               
      }
    }
  } 
  
  /*
    Let us consided the if-else clause in each of these two methods.
    Each deals with the value of 'slist.getFirst()' 
    and the application of our method to 'slist.getrest()'.
    The outcome of this if-else clause matches the type as the method result
    
    Let us consider the following helper methods:
  */

   ILoString onlyMatchHelper(String first, ILoString rest){
     if (first.equals(match)){
       return new ConsLoString(first, rest);
     }
     else {
       return rest;
     }      
   }
 
  int countSuchHelper(String first, int acc){
    if (first.equals(match)){
      return 1 + acc;
    }
    else{
      return acc;
    }
  }

  /*
  We can now rewrite the two methods as follows:
  */
  /** Produce a list of only strings that equal to match  - from this list. */
   ILoString onlyMatch2(ILoString slist){
    if (slist.isEmpty()){
        return new MTLoString();      
    }
    else {
      return onlyMatchHelper(slist.getFirst(), onlyMatch2(slist.getRest()));      
    }
  } 

  /** Count how many strings in this list are equal to match . */
   int countSuch2(ILoString slist){
    if (slist.isEmpty()){
        return 0;      
    }
    else {
      return countSuchHelper(slist.getFirst(), countSuch2(slist.getRest()));        
    }
  } 
  
  
  /** 
    At this point the two methods are very similar.
    Let us analyze what are the parts that comprise this method:
  
     
  /*
    TEMPLATE - ANALYSIS: 
    --------------------
    ReturnType method-name(ILoString slist){
      if (slist.isEmpty()){
               +------------+
        return | BASE VALUE |;   
               +------------+   
      }
      else {
               +-------------------------------------------+
        return | HELPER(slist.getFirst(), slist.getRest()) |
               +-------------------------------------------+
      }
    } 
    
    ReturnType helper-name(String first, ILoString rest){
      ... first ...                          -- String
      ... method-name(rest) ...              -- ReturnType
    }
  */
  
  /*
    We can now convert it to the accumulator style as folows:
    
    ReturnType method-name(ILoString slist){
                                              +------------+
      return method-name-acc(ILoString slist, | BASE VALUE |); 
                                              +------------+
    }
    
    ReturnType method-name-acc(ILoString alist, ReturnType ACC){
      if (alist.isEmpty()){
        return ACC;
      }
      else{
        return method-name-acc (slist.rest(), 
                                +--------------------------------+
                                | HELPER(alist.getFirst(), ACC)) |;
                                +--------------------------------+
      }
    }
    
  /* Our two methods become: */
     
  
    /** Produce a list of only strings that equal to match  - from this list. */
   ILoString onlyMatch3(ILoString slist){
     return onlyMatchAcc(slist, new MTLoString());
   }

  /** Produce a list of only strings that equal to match  - from this list. */
   ILoString onlyMatchAcc(ILoString slist, ILoString acc){
     if (slist.isEmpty()){
       return acc;      
     }
     else {
       return onlyMatchAcc(slist.getRest(),
                           onlyMatchHelper(slist.getFirst(), acc));               
     }
   }
   

  /** Count how many strings in this list are equal to match . */
   int countSuch3(ILoString slist){
     return countSuchAcc(slist, 0);
   }

  /** Count how many strings in this list are equal to match . */
   int countSuchAcc(ILoString slist, int acc){
     if (slist.isEmpty()){
       return acc;      
     }
     else {
       return countSuchAcc(slist.getRest(), 
                           countSuchHelper(slist.getFirst(), acc));               
     }
   }
   
   /* Converting this to the imperative style using the Java 'while' loop
      is shown below. Write down the template for defining loops in this style.
   */
      
    /** Produce a list of only strings that equal to match  - from this list. */
   ILoString onlyMatch4(ILoString slist){
     
     ILoString acc = new MTLoString();
     
     while(!slist.isEmpty()){       
       acc = onlyMatchHelper(slist.getFirst(), acc);       
       slist = slist.getRest();
     }
     
     return acc;
   }   
 
     /** Produce a list of only strings that equal to match  - from this list. */
   int countSuch4(ILoString slist){
     
     int acc = 0;
     
     while(!slist.isEmpty()){       
       acc = countSuchHelper(slist.getFirst(), acc);       
       slist = slist.getRest();
     }
     
     return acc;
   }   
   
   /*
     Implement two new methods in the algorithms class - using all four styles:
     
     // is there a string in this list that equals to match?
     
     // does this list contain a given string?
     
   */


}

interface ILoString{
    
  boolean isEmpty();
    
  String getFirst();
  
  ILoString getRest();
}

class MTLoString implements ILoString{
  MTLoString(){}
  
  public boolean isEmpty(){
    return true;  }
    
  public String getFirst(){
    return null;
  }
  
  public ILoString getRest(){
    return null;
  }
}

class ConsLoString implements ILoString{
  String first;
  ILoString rest;
  
  ConsLoString(String first, ILoString rest){
    this.first = first;
    this.rest = rest;  
  }
  
  public boolean isEmpty(){
    return false;  }
    
  public String getFirst(){
    return this.first;
  }
  
  public ILoString getRest(){
    return this.rest;
  }
}

class Examples{
  Examples(){}
  
  Algorithms algo = new Algorithms();
  
  ILoString slist1 =
      new ConsLoString("Hello",
        new ConsLoString("Goodbye",
          new ConsLoString("Hello",
            new ConsLoString("Hi",
              new ConsLoString("Ahoy",
               new ConsLoString("Hello",
                 new MTLoString()))))));
                 
  ILoString slist2 =
      new ConsLoString("Hello",
        new ConsLoString("Hello",
          new ConsLoString("Hello",
            new MTLoString())));
                 
   boolean 
     test1 = (check algo.onlyMatch(slist1) expect this.slist2) &&
             (check algo.countSuch(slist1) expect 3);          


   boolean 
     test2 = (check algo.onlyMatch2(slist1) expect this.slist2) &&
             (check algo.countSuch2(slist1) expect 3);          
  
   boolean 
     test3 = (check algo.onlyMatch3(slist1) expect this.slist2) &&
             (check algo.countSuch3(slist1) expect 3);          

   boolean 
     test4 = (check algo.onlyMatch4(slist1) expect this.slist2) &&
             (check algo.countSuch4(slist1) expect 3);         
  
}