import java.util.*;

/**
 * To represent a functional iterator
 * @author Viera K. Proulx
 * @version 2013-10-03
 **/
interface Traversal<T> {
  
  /** is the data collection empty? */
  public boolean isEmpty();
  
  /** generate the next element of the data collection */
  public T getFirst();
  
  /** produce the functional iterator for the rest of the data collection */
  public Traversal<T> getRest();
}

/**
 * To implement functional iterator over recursively built list
 * of <code>String</code>s
 * @author Viera K. Proulx
 * @version 2013-10-03
 **/
interface ILoS extends Traversal<String>{
  
  /** is the data collection empty? */
  public boolean isEmpty();
  
  /** generate the next element of the data collection */
  public String getFirst();
  
  /** produce the functional iterator for the rest of the data collection */
  public Traversal<String> getRest();
}

/**
 * to represent an empty list of <code>String</code>s
 */
class MtLoS implements ILoS {
  MtLoS() {}

  /** is the list empty? */
  public boolean isEmpty() {
    return true;
  }
  
  /** cannot generate the next element of the empty list */
  public String getFirst(){
    throw new NoSuchElementException("no first element available");
  }
  
  /** cannot produce the functional iterator for the rest of the empty list */
  public Traversal<String> getRest(){
    throw new NoSuchElementException("no more elements to generate");
  }
}

/**
 * to represent a nonempty list of <code>String</code>s
 */
class ConsLoS implements ILoS {
  /** the first element of the list */
  String first;
  /** the rest of the list */
  ILoS rest;
  
  /** standard complete constructor */
  ConsLoS(String first, ILoS rest) {
    this.first = first;
    this.rest = rest;
  }
  
  /** is the list empty? */
  public boolean isEmpty(){
    return false;
  }
  
  /** generate the next element of the nonempty list */
  public String getFirst(){
    return this.first;
  }
  
  /** produce the functional iterator for the rest of the nonempty list */
  public Traversal<String> getRest(){
    return this.rest;
  }
}

/**
 * To implement functional iterator over an <code>ArrayList</code>
 * of <code>String</code>s
 * @author Viera K. Proulx
 * @version 2013-10-03
 **/
class ArrayListTraversal implements Traversal<String> {
  
  /** the <code>ArrayList</code> for generating the data */
  private ArrayList<String> arlist;
  
  /** index for the next element to generate */
  private int next;

  /**
   * Produce an functional iterator that generates the given next element
   * from the given <code>ArrayList</code>
   * @param arlist the given <code>ArrayList</code>
   * @param next the index for the next element to generate
   */
  private ArrayListTraversal(ArrayList<String> arlist, int next) {
    this.arlist = arlist;
    this.next = next;
  }
  
  /**
   * Produce an functional iterator that generates the elements
   * from the given <code>ArrayList</code>
   * @param arlist the given <code>ArrayList</code>
   */
  public ArrayListTraversal(ArrayList<String> arlist) {
    this(arlist, 0);
  }
  
  /** 
   * Did we reach the end of the given <code>ArrayList</code>?
   * @return true if no more elements are available to generate
   */
  public boolean isEmpty(){
    return this.next == arlist.size();
  }
  
  /**
   * Produce the next element of the <code>ArrayList</code> we are traversing.
   * Throw <code>NoSuchElementException</code> if no more elements are 
   * available.
   * @return the next element of the <code>ArrayList</code>
   */
  public String getFirst(){
    if (this.isEmpty()) {
      throw new NoSuchElementException();
    }
    else {
      return this.arlist.get(next);
    }
  }
  
  /**
   * Produce an functional iterator that generates the elements
   * from the remaining part of our <code>ArrayList</code>.
   * Throw <code>NoSuchElementException</code> if no more elements are 
   * available in our <code>ArrayList</code>.
   * @return the desired functional iterator
   */
  public Traversal<String> getRest(){
    return new ArrayListTraversal(this.arlist, this.next + 1);
  }
}
 
/**
 * Examples and tests for the functional iterators for recursively built
 * lists and for <code>ArrayList</code>
 * @author Viera K. Proulx vkp
 * @version 2013-10-03
 */
class ExamplesTraversals {
  
  public static void main(String[] argv) {

    // recursively built list to iterate over
    ILoS mtlos = new MtLoS();  
    ILoS slist = 
        new ConsLoS("hello",
            new ConsLoS("bye",
                new ConsLoS("aloha",
                    new ConsLoS("ciao",
                        new ConsLoS("ahoy", mtlos)))));
  
    // ArrayList to iterate over
    ArrayList<String> arlist = 
        new ArrayList<String>(Arrays.asList(
                              "hello",
                              "bye",
                              "aloha",
                              "ciao",
                              "ahoy"));
    
    // first functional iterator over recursively built list
    Traversal<String> tr1 = slist;
    // second functional iterator over recursively built list
    Traversal<String> tr2 = slist;
    
    // first functional iterator over ArrayList
    Traversal<String> ar1 = new ArrayListTraversal(arlist);
    // second functional iterator over ArrayList
    Traversal<String> ar2 = new ArrayListTraversal(arlist);

    // repeat invoking the getFirst method - should produce the same result
    System.out.println(tr1.getFirst() + " should be hello");
    System.out.println(tr1.getFirst() + " should again be hello");
    System.out.println(tr2.getFirst() + " should be hello");
    System.out.println(tr1.getFirst() + " should be hello");

    // repeat invoking the getFirst method - should produce the same result
    System.out.println(ar1.getFirst() + " should be hello");
    System.out.println(ar1.getFirst() + " should again be hello");
    System.out.println(ar2.getFirst() + " should be hello");
    System.out.println(ar1.getFirst() + " should be hello");

    // tr3 advances to the next item in tr1, but tr1 stays the same
    Traversal<String> tr3 = tr1.getRest();
    System.out.println(tr3.getFirst() + " should be bye");
    System.out.println(tr1.getFirst() + " should be hello");

    // ar3 advances to the next item in ar1, but ar1 stays the same
    Traversal<String> ar3 = ar1.getRest();
    System.out.println(ar3.getFirst() + " should be bye");
    System.out.println(ar1.getFirst() + " should be hello");

    // design a loop that uses the functional iterator over recursive list
    // notice that we mutate the object that represents the iterator
    int i = 0;
    for (Traversal<String> tr = slist; !tr.isEmpty(); tr = tr.getRest()) {
      System.out.println("#" + i + ": " + tr.getFirst());
      i = i + 1;
    }

    // design a loop that uses the functional iterator over ArrayList
    // notice that we mutate the object that represents the iterator
    i = 0;
    for (Traversal<String> ar = slist; !ar.isEmpty(); ar = ar.getRest()) {
      System.out.println("#" + i + ": " + ar.getFirst());
      i = i + 1;
    }
    
    // we keep replacing tr2 by the one that looks at the next item
    Traversal<String> oldTr = tr2;
    tr2 = tr2.getRest();
    System.out.println(tr2.getFirst() + " should be bye");
    tr2 = tr2.getRest();
    System.out.println(tr2.getFirst() + " should be aloha");
    // but the oldTr did not change
    System.out.println(oldTr.getFirst() + " should be hello");
    
    // we keep replacing ar2 by the one that looks at the next item
    Traversal<String> oldAr = ar2;
    ar2 = ar2.getRest();
    System.out.println(ar2.getFirst() + " should be bye");
    ar2 = ar2.getRest();
    System.out.println(tr2.getFirst() + " should be aloha");
    // but the oldAr did not change
    System.out.println(oldAr.getFirst() + " should be hello");    
  }                        
}