//5.1
/*
                            +------+                             
                            | Item |                             
                            +------+                             
                            +------+                             
                                |                                
                               / \                               
                               ---                               
                                |                                
          --------------------------------------------           
          |                    |                     |           
  +---------------+    +------------------+    +--------------------+  
  | IceCream      |    | Coffee           |    | Juice              |  
  +---------------+    +------------------+    +--------------------+  
  | String brand  |    | String brand     |    | String brand       |  
  | int weight    |    | int weight       |    | int weight         |  
  | int price     |    | int price        |    | int price          |  
  | String flavor |    | boolean caffeine |    | String flavor      |  
  +---------------+    +------------------+    | String packageType |  
                                               +--------------------+  

*/

// to decribe a store item
interface Item {
  // returns the brand of the given item
  String findBrand();

  // returns the price of the given item
  int findPrice();
}

// to describe an IceCream
class IceCream implements Item {
  String brand;
  int weight;
  int price;
  String flavor;

  IceCream(String brand, int weight, int price, String flavor) {
    this.brand = brand;
    this.weight = weight;
    this.price = price;
    this.flavor = flavor;
  }

  // returns the brand of the given IceCream
  String findBrand(){
    return this.brand;
  }
  
  // returns the price of the given IceCream
  int findPrice(){
    return this.price;
  }
}

// to decribe a Coffee
class Coffee implements Item {
  String brand;
  int weight;
  int price;
  boolean caffeine;

  Coffee(String brand, int weight, int price, boolean caffeine) {
    this.brand = brand;
    this.weight = weight;
    this.price = price;
    this.caffeine = caffeine;
  }

  // returns the brand of the given Coffee
  String findBrand(){
    return this.brand;
  }
  
  // returns the price of the given Coffee
  int findPrice(){
    return this.price;
  }
}

// to describe a Juice
class Juice implements Item {
  String brand;
  int weight;
  int price;
  String flavor;
  String packageType;

  Juice(String brand, int weight, int price, String flavor, 
                                             String packageType) 
    {
    this.brand = brand;
    this.weight = weight;
    this.price = price;
    this.flavor = flavor;
    this.packageType = packageType;
  }

  // returns the brand of the given Juice
  String findBrand(){
    return this.brand;
  }
  
  // returns the price of the given Juice
  int findPrice(){
    return this.price;
  }
}

/*
          +--------------+              
          | ShoppingList |<------------+
          +--------------+             |
          +--------------+             |
                  |                    |
                 / \                   |
                 ---                   |
                  |                    |
     --------------------              |
     |                  |              |
  +------+    +-------------------+    |
  | MTSL |    | ConsSL            |    |
  +------+    +-------------------+    |
  +------+    | Item first        |    |
              | ShoppingList rest |-+  |
              +-------------------+ |  |
                                    |  |
                                    +--+

*/

// to describe a shopping list
interface ShoppingList {
  // inserts the given item into a list according to brand name
  ShoppingList insertSL(Item that);

  // sorts a list by brand
  ShoppingList sortSL();

  // counts the number of items in a shopping list
  int howMany();

  // creates a list of only the brands of all items in the given shopping list
  LoS brandList();

  // returns the highest price of all prices on the shopping list
  int highestPrice();

  // counts the number of items in a shopping list
  int howManyAcc(int acc);

  // creates a list of only the brands of all items in the given shopping list
  LoS brandListAcc(LoS acc);

  // returns the highest price of all prices on the shopping list
  int highestPriceAcc(int acc);
}

// to describe an empty shopping list
class MTSL implements ShoppingList {

  MTSL() {
  }
  
  // inserts an item into the given shopping list by its brand name
  ShoppingList insertSL(Item that){
    return new ConsSL(that, this);
  }
  
  // orders the given shopping list by brand
  ShoppingList sortSL(){
    return this;
  }
  
  // counts the number of items in the given shopping list
  int howMany(){
    return 0;
  }
  
  // creates a list of only the brands of all items in the given shopping list
  LoS brandList(){
    return new MtLoS();
  }
  
  // returns the highest price of all prices on the shopping list
  int highestPrice(){
    return 0;
  }
  
  // counts the number of items in the given shopping list
  int howManyAcc(int acc){
    return acc;
  }

  // creates a list of only the brands of all items in the given shopping list
  LoS brandListAcc(LoS acc){
    return acc;
  }

  // returns the highest price of all prices on the shopping list
  int highestPriceAcc(int acc){
    return acc;
  }
}

// To describe a non-empty shopping list
class ConsSL implements ShoppingList {
  Item first;
  ShoppingList rest;

  ConsSL(Item first, ShoppingList rest) {
    this.first = first;
    this.rest = rest;
  }

  
  // inserts an item into the given shopping list by its brand name
  ShoppingList insertSL(Item that){
    if(that.findBrand().compareTo(this.first.findBrand()) < 0)
      return new ConsSL(that, this);
    else
      return new ConsSL(this.first, this.rest.insertSL(that));
  }
  
    // orders the given shopping list by brand
  ShoppingList sortSL(){
    return this.rest.sortSL().insertSL(this.first);
  }
  
    // counts the number of items in the given shopping list
  int howMany(){
    return 1 + this.rest.howMany();
  }
  
  // creates a list of only the brands of all items in the given shopping list
  LoS brandList(){
    return new ConsLoS(this.first.findBrand(), this.rest.brandList());
  }
  
  // returns the highest price of all prices on the shopping list
  int highestPrice(){
    if(this.first.findPrice() > this.rest.highestPrice())
      return this.first.findPrice();
    else
      return this.rest.highestPrice();
  }
  
    // counts the number of items in the given shopping list
  int howManyAcc(int acc){
    return this.rest.howManyAcc(acc + 1);
  }

  // creates a list of only the brands of all items in the given shopping list
  LoS brandListAcc(LoS acc){
    return this.rest.brandListAcc(new ConsLoS(this.first.findBrand(), acc));
  }

  // returns the highest price of all prices on the shopping list
  int highestPriceAcc(int acc){
    if(this.first.findPrice() > acc)
      return this.rest.highestPriceAcc(this.first.findPrice());
    else
      return this.rest.highestPriceAcc(acc);
  }
}

/*
             +-----+                
             | LoS |<--------------+
             +-----+               |
             +-----+               |
                |                  |
               / \                 |
               ---                 |
                |                  |
      -----------------            |
      |               |            |
  +-------+    +--------------+    |
  | MtLoS |    | ConsLoS      |    |
  +-------+    +--------------+    |
  +-------+    | String first |    |
               | LoS rest     |-+  |
               +--------------+ |  |
                                |  |
                                +--+

*/

// To describhe a list of strings
interface LoS {
}

// to describe an empty list of strings
class MtLoS implements LoS {

  MtLoS() {
  }
}

// to decribe a non-empty list of strings
class ConsLoS implements LoS {
  String first;
  LoS rest;

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



class Examples{
  Examples(){}
  
  Item icecream = new IceCream("Ben and Jerry's", 5, 7, "Vanilla");
  Item coffee = new Coffee("Folgers", 6, 9, false);
  Item juice = new Juice("Minute Maid", 3, 3, "Apple", "Bottle");
 
  ShoppingList mt = new MTSL();
  ShoppingList sl = new ConsSL(this.juice, new ConsSL(this.icecream, 
                               new ConsSL(this.coffee, this.mt)));
            
  boolean t1 = (check this.sl.sortSL()
    expect new ConsSL(this.icecream, new ConsSL(this.coffee, 
      new ConsSL(this.juice, this.mt))));
                                  
  boolean t2 = (check this.sl.howMany() expect 3);
  
  boolean t3 = (check this.sl.brandList() 
    expect new ConsLoS("Minute Maid", new ConsLoS("Ben and Jerry's", 
      new ConsLoS("Folgers", new MtLoS()))));
  
  boolean t4 = (check this.sl.highestPrice() expect 9);
  
  boolean t5 = (check this.sl.howManyAcc(0) expect 3);
  
  boolean t6 = (check this.sl.brandListAcc(new MtLoS())
    expect new ConsLoS("Folgers", new ConsLoS("Ben and Jerry's", 
      new ConsLoS("Minute Maid", new MtLoS()))));
  
  boolean t7 = (check this.sl.highestPriceAcc(0) expect 9);
  

}