import tester.Tester;

//Assignment 6
//Seo Minho
//ashera2
//Mayeux Jacob
//jakemayeux

// a generic list
interface IList<T> {

  //determines whether a list is sorted
  boolean isSorted(IComparator<T> comparator);

  // compares two items of a list
  boolean isSortedHelp(T given, IComparator<T> comparator);

  //produce a new list containing all elements from both lists
  IList<T> merge(IList<T> alist, IComparator<T> comparator);

  // return -1 if the first element comes first, 0 if the same
  // and 1 if the second element should come first
  int comesFirst(T given, IComparator<T> comparator);

  //produce a new list in alphabetical order
  IList<T> sort(IComparator<T> comparator);

  // rearrange two items in alphabetical order
  IList<T> sortHelp(T first, IComparator<T> comparator);

  // returns true if the two lists are the same
  boolean sameList(IList<T> alist, IComparator<T> comparator);

  // checks if the two non-empty lists have the same data
  boolean sameData(ConsList<T> alist, IComparator<T> comparator);

}

// generic empty list
class MtList<T> implements IList<T> {
  MtList() {}

  @Override
  public boolean isSorted(IComparator<T> comparator) {
    return true;
  }

  @Override
  public boolean isSortedHelp(T given, IComparator<T> comparator) {
    return true;
  }

  @Override
  public IList<T> merge(IList<T> alist, IComparator<T> comparator) {
    return alist;
  }

  @Override
  public int comesFirst(T given, IComparator<T> comparator) {
    return 1;
  }

  @Override
  public IList<T> sort(IComparator<T> comparator) {
    return this;
  }

  @Override
  public IList<T> sortHelp(T first, IComparator<T> comparator) {
    return new ConsList<T>(first, this);
  }

  @Override
  public boolean sameList(IList<T> alist, IComparator<T> comparator) {
    return false;
  }

  // compare two empty lists
  boolean sameList(MtList<T> alist, IComparator<T> comparator) {
    return true;
  }

  @Override
  public boolean sameData(ConsList<T> alist, IComparator<T> comparator) {
    return false;
  }

}

// generic cons list
class ConsList<T> implements IList<T> {
  T first;
  IList<T> rest;

  ConsList(T first, IList<T> rest) {
    this.first = first;
    this.rest = rest;
  }

  @Override
  public boolean isSorted(IComparator<T> comparator) {
    return this.rest.isSortedHelp(this.first, comparator);
  }

  @Override
  public boolean isSortedHelp(T given, IComparator<T> comparator) {
    if (comparator.compare(given, this.first) <= 0) {
      return this.isSorted(comparator);
    }
    else {
      return false;
    }
  }

  @Override
  public IList<T> merge(IList<T> alist, IComparator<T> comparator) {
    if (alist.comesFirst(this.first, comparator) <= 0) {
      return alist.merge(this, comparator);
    }
    else {
      return new ConsList<T>(this.first, alist.merge(this.rest, comparator));
    }
  }

  @Override
  public int comesFirst(T given, IComparator<T> comparator) {
    return comparator.compare(this.first, given);
  }

  @Override
  public IList<T> sort(IComparator<T> comparator) {
    return this.rest.sort(comparator).sortHelp(this.first, comparator);
  }

  @Override
  public IList<T> sortHelp(T given, IComparator<T> comparator) {
    if(comparator.compare(this.first, given) <= 0) {
      return new ConsList<T>(this.first, this.rest.sortHelp(given, comparator));
    }
    else {
      return new ConsList<T>(given, this);
    }
  }

  @Override
  public boolean sameList(IList<T> alist, IComparator<T> comparator) {
    return alist.sameData(this, comparator);
  }

  @Override
  public boolean sameData(ConsList<T> alist, IComparator<T> comparator) {
    return comparator.compare(this.first, alist.first) == 0
        && this.rest.sameList(alist.rest, comparator);
  }

}

// gerneric comparator
interface IComparator<T> {
  // Returns a negative number if t1 comes before t2 in this ordering
  // Returns zero              if t1 is the same as t2 in this ordering
  // Returns a positive number if t1 comes after t2 in this ordering
  int compare(T t1, T t2);
}

// compare the length of strings
class StringLengthCompGen implements IComparator<String> {

  @Override
  public int compare(String s1, String s2) {
    if (s1.length() < s2.length()) {
      return -1;
    }
    else if (s1.length() == s2.length()) {
      return 0;
    }
    else return 1;
  }
}

// compare lexicography of strings
class StringLexCompGen implements IComparator<String> {

  @Override
  public int compare(String s1, String s2) {
    if (s1.compareTo(s2) < 0) {
      return -1;
    }
    else if (s1.compareTo(s2) == 0) {
      return 0;
    }
    else {
      return 1;
    }
  }
}

//examples class of strings
class ExamplesStringsGen {

IList<String> empty = new MtList<String>();
IList<Integer> emptyInt = new MtList<Integer>();
IList<Boolean> emptyBoo = new MtList<Boolean>();

IList<String> easy = new ConsList<String>("bb",
   new ConsList<String>("ccc", empty));

IList<Integer> easy2 = new ConsList<Integer>(1,
   new ConsList<Integer>(4,
       new ConsList<Integer>(3,
           new ConsList<Integer>(2, emptyInt))));

IList<Boolean> easy3 = new ConsList<Boolean>(true,
   new ConsList<Boolean>(true,
       new ConsList<Boolean>(false, emptyBoo)));

IList<String> easy4 = new ConsList<String>("c", empty);

IList<String> easy5 = new ConsList<String>("a",
   new ConsList<String>("b",
       new ConsList<String>("a", empty)));

IList<String> easy6 = new ConsList<String>("a",
    new ConsList<String>("aba",
        new ConsList<String>("ab", empty)));

IComparator<String> lex = new StringLexCompGen();

IComparator<String> length = new StringLengthCompGen();

  // to test compare method
  boolean testCompare(Tester t){
    return
        t.checkExpect(lex.compare("a", "b"), -1)
        && t.checkExpect(lex.compare("b", "a"), 1)
        && t.checkExpect(lex.compare("a", "a"), 0)
        && t.checkExpect(length.compare("aa", "b"), 1)
        && t.checkExpect(length.compare("a", "bb"), -1);
  }

  //to test is sorted method
  boolean testIsSorted(Tester t){
    return
        t.checkExpect(easy.isSorted(lex), true)
        && t.checkExpect(easy.isSorted(length), true)
        && t.checkExpect(easy5.isSorted(lex), false);
  }

  //to test is sorted help method
  boolean testIsSortedHelp(Tester t){
    return
        t.checkExpect(easy.isSortedHelp("b", lex), true)
        && t.checkExpect(easy.isSortedHelp("a", lex), true)
        && t.checkExpect(easy.isSortedHelp("a", length), true)
        && t.checkExpect(easy.isSortedHelp("aaa", length), false);
  }

  //to test merge method
  boolean testMerge(Tester t){
    return
        t.checkExpect(easy.merge(easy4, lex), new ConsList<String> ("bb",
            new ConsList<String>("c",
                new ConsList<String>("ccc", empty))))
        && t.checkExpect(easy.merge(easy4, length),  new ConsList<String> ("c",
            new ConsList<String>("bb",
                new ConsList<String>("ccc", empty))));
  }

  // to test comes first method
  boolean testComesFirst(Tester t) {
    return t.checkExpect(easy.comesFirst("a", lex), 1)
        && t.checkExpect(easy.comesFirst("dddd", length), -1)
        && t.checkExpect(easy.comesFirst("bb", lex), 0);
  }


  //to test sort method
  boolean testSort(Tester t){
    return
        t.checkExpect(easy.sort(lex), easy)
        && t.checkExpect(easy.sort(length), easy)
        && t.checkExpect(easy6.sort(length), new ConsList<String> ("a",
            new ConsList<String> ("ab",
                new ConsList<String> ("aba", empty))));
  }

  //to test sort help method
  boolean testSortHelp(Tester t){
    return
        t.checkExpect(easy.sortHelp("a", lex), new ConsList<String> ("a",
            new ConsList<String>("bb",
                new ConsList<String>("ccc", empty))))
        && t.checkExpect(easy.sortHelp("aaa", length), new ConsList<String> ("bb",
            new ConsList<String> ("ccc",
                new ConsList<String> ("aaa", empty))));
  }

//  //to test same list method
//  boolean testSameList(Tester t){
//    return
//        t.checkExpect(easy.sameList(easy, lex), true)
//        && t.checkExpect(easy.sameList(empty, length), false)
//        && t.checkExpect(empty.sameList(easy4, lex), false)
//        && t.checkExpect(easy.sameList(easy4, length), false)
//        && t.checkExpect(easy5.sameList(easy5, lex), true);
//  }
//
//  //to test same data method
//  boolean testSameData(Tester t){
//    return
//        t.checkExpect(easy.sameData(new ConsList<String>("ccc",
//            new ConsList<String> ("bb", empty)), lex), false)
//        && t.checkExpect(easy.sameData(new ConsList<String>("bb",
//            new ConsList<String> ("ccc", empty)), lex), true)
//        && t.checkExpect(easy4.sameData(new ConsList<String> ("a", empty), length), false);
//  }
}