/*
           +------+              
           | ILoN |<------------+
           +------+             |
           +------+             |
             / \                |
             ---                |
              |                 |
      ----------------          |
      |              |          |
  +-------+    +-----------+    |
  | MTLoN |    | ConsLoN   |    |
  +-------+    +-----------+    |
  +-------+    | int first |    |
               | ILoN rest |----+ 
               +-----------+ 

*/

// to represent a list fo numbers
interface ILoN {
/*
  // ** DRAFT TEMPLATE ** Edit as needed.
  // purpose statement 
  abstract ??? mmm();
*/

  // produce a sorted list of numbers from this list of numbers
  ILoN sort();

  // produce a sorted list by inserting the given number 
  // into this sorted list of numbers
  ILoN insert(int num);

  // is this the same list as the given list
  boolean same(ILoN that);

  // is this the same empty list as the given empty list
  boolean sameMTLoN(MTLoN that);

  // is this the same nonempty list as the given nonempty list
  boolean sameConsLoN(ConsLoN that);
}

// to represent an empty list of numbers
class MTLoN implements ILoN {

  MTLoN() {
  }

  // produce a sorted list of numbers from this list of numbers
  ILoN sort(){ return this; }

  // produce a sorted list by inserting the given number 
  // into this sorted list of numbers
  ILoN insert(int num){
    return new ConsLoN(num, this);
  }


  // is this the same list as the given list
  boolean same(ILoN that){ return that.sameMTLoN(this); }

  // is this the same empty list as the given empty list
  boolean sameMTLoN(MTLoN that){ return true; }

  // is this the same nonempty list as the given nonempty list
  boolean sameConsLoN(ConsLoN that){ return false; }
}

// to represent a nonempty list of numbers
class ConsLoN implements ILoN {
  int first;
  ILoN rest;

  ConsLoN(int first, ILoN rest) {
    this.first = first;
    this.rest = rest;
  }

/*
  TEMPLATE:
  ... this.first ...                         -- int
  ... this.rest ...                          -- ILoN
  ... this.rest.sort() ...                   -- [ILoN (sorted)] 
  ... this.rest.sort().insert(..int..) ...   -- [ILoN (sorted)] 
*/

  // produce a sorted list of numbers from this list of numbers
  ILoN sort(){
    return this.rest.sort().insert(this.first);
  }

/*
  TEMPLATE:
  ... this.first ...                  -- int
  ... this.rest ...                   -- [ILoN (sorted)] 
  ... this.rest.insert(..int..) ...   -- [ILoN (sorted)] 
*/
  // produce a sorted list by inserting the given number 
  // into this sorted list of numbers
  ILoN insert(int num){
    if (num < this.first)
      return new ConsLoN(num, this);
    else
      return new ConsLoN(this.first, this.rest.insert(num));
  }


  // is this the same list as the given list
  boolean same(ILoN that){ return that.sameConsLoN(this); }

  // is this the same empty list as the given empty list
  boolean sameMTLoN(MTLoN that){ return false; }

  // is this the same nonempty list as the given nonempty list
  boolean sameConsLoN(ConsLoN that){ 
    return this.first == that.first &&
           this.rest.same(that.rest);
  }
}

class Examples {
  Examples() {}

/*
(equal? empty (sort empty))
(equal? (list 2 4 6 8) (sort (list 4 8 2 6)))

(equal? (list 2) (insert empty 2))
(equal? (list 2 4 6 8) (insert (list 4 6 8) 2))
(equal? (list 2 4 6 8) (insert (list 2 6 8) 4))
(equal? (list 2 4 6 8) (insert (list 2 4 6) 8))
*/

ILoN empty = new MTLoN();
ILoN sList = new ConsLoN(2,
             new ConsLoN(4,
             new ConsLoN(6,
             new ConsLoN(8, this.empty))));

ILoN aList = new ConsLoN(4,
             new ConsLoN(8,
             new ConsLoN(2,
             new ConsLoN(6, this.empty))));

ILoN list1 = new ConsLoN(4,
             new ConsLoN(6,
             new ConsLoN(8, this.empty)));

ILoN list2 = new ConsLoN(2,
             new ConsLoN(6,
             new ConsLoN(8, this.empty)));

ILoN list3 = new ConsLoN(2,
             new ConsLoN(4,
             new ConsLoN(6, this.empty)));

// tests for the sort method
boolean testSort1 = this.empty.same(this.empty.sort());
boolean testSort2 = this.sList.same(this.aList.sort());

// tests for the insert method
boolean testInsert1 = (new ConsLoN(2, this.empty)).same(this.empty.insert(2));
boolean testInsert2 = this.sList.same(this.list1.insert(2));
boolean testInsert3 = this.sList.same(this.list2.insert(4));
boolean testInsert4 = this.sList.same(this.list3.insert(8));






}