import tester.*;

// to represent a list of Strings
interface ILoS{
  
  // produce a list from this list that is sorted in the given order
  public ILoS sort();
  
  // insert the given book into this list sorted in the given order
  // producing a sorted list
  public ILoS insert(String s);  
}

//to represent an empty list of Strings
class MtLoS implements ILoS{
  MtLoS(){}

  // produce a list from this list that is sorted in the given order
  public ILoS sort(){
    return this;
  }

  // insert the given String into this list sorted in the given order
  // producing a sorted list
  public ILoS insert(String s){
    return new ConsLoS(s, this);
  }
}

//to represent an empty list of Strings
class ConsLoS implements ILoS{
  String first;
  ILoS rest;

  ConsLoS(String first, ILoS rest){
    this.first = first;
    this.rest = rest;
  }

  /* TEMPLATE:
FIELDS:
... this.first ...    -- String
... this.rest ...     -- ILoS

METHODS:
... this.sort() ...         -- ILoS(sorted)
... this.insert(String) ... -- ILoS(sorted)

METHODS FOR FIELDS:
... this.rest.sort() ...         -- ILoS(sorted)
... this.trest.insert(String) ... -- ILoS(sorted)
   */

  // produce a list from this list that is sorted in the given order
  public ILoS sort(){
    return this.rest.sort().insert(this.first);
  }

  // insert the given String into this list sorted in the given order
  // producing a sorted list
  public ILoS insert(String s){
    if (s.compareTo(this.first) < 0)
      return new ConsLoS(s, this);
    else
      return new ConsLoS(this.first, this.rest.insert(s));
  }
}


// examples and tests for lists of books
class ExamplesString{
  ExamplesString(){}
  
  
  ILoS mtlos = new MtLoS();
  ILoS l1 = new ConsLoS("hi", this.mtlos);
  ILoS l2 = new ConsLoS("hello", new ConsLoS("bye", this.mtlos));
  ILoS slist = new ConsLoS("ciao", new ConsLoS("aloha", this.l2));
  
  ILoS sortedSlist = 
      new ConsLoS("aloha", 
          new ConsLoS("bye",
              new ConsLoS("ciao",
                  new ConsLoS("hello", 
                      new ConsLoS("hi", this.mtlos)))));
 
  // test sort(ICompareBooks order);
  boolean testSortBooks(Tester t){
    return
    t.checkExpect(this.mtlos.sort(), this.mtlos) &&
    t.checkExpect(this.l1.sort(), this.l1) &&
    t.checkExpect(this.l2.sort(), this.sortedSlist);
  }
  
  // test insert(Book b, ICompareBooks order);
  boolean testInsertBooks(Tester t){
    return
    t.checkExpect(this.mtlos.insert("hi"), this.l1) && 
    t.checkExpect(this.l1.insert("aloha"), new ConsLoS("aloha", this.l1)) &&
    t.checkExpect(this.l1.insert("hello"),
        new ConsLoS("hello", new ConsLoS("hi", this.mtlos))) &&
    t.checkExpect(this.sortedSlist.insert("adieu"), 
      new ConsLoS("adieu",
        new ConsLoS("aloha", 
            new ConsLoS("bye",
                new ConsLoS("ciao",
                    new ConsLoS("hello", 
                        new ConsLoS("hi", this.mtlos))))))) &&
                        
    t.checkExpect(this.sortedSlist.insert("ahoy"), 
      new ConsLoS("aloha",
        new ConsLoS("ahoy", 
          new ConsLoS("bye",
            new ConsLoS("ciao",
              new ConsLoS("hello", 
                new ConsLoS("hi", this.mtlos))))))) &&

    t.checkExpect(this.sortedSlist.insert("goodbye"), 
      new ConsLoS("aloha", 
          new ConsLoS("bye",
            new ConsLoS("ciao",
              new ConsLoS("hello", 
                new ConsLoS("hi", 
                    new ConsLoS("goodbye",
                        this.mtlos)))))));
    }  
}