import tester.Tester;

//-------------------------------------------------------------------------------------------------

//-------------------------------------------------------------------------------------------------

//Representation for a Book

class Book {
    String title;
    String author;
    int price;

    Book(String title, String author, int price) {
        this.title = title;
        this.author = author;
        this.price = price;
    }

}

//-------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------
//Interface for any compare function object
interface IComparator<T> {
    // apply function that lets you compare books by either
    // title, author, or price
    int apply(T data, T item);
}

//-------------------------------------------------------------------------------------------------
class BooksByTitle implements IComparator<Book> {
    // compares books by title lexicographically
    public int apply(Book b1, Book b2) {
        return b1.title.compareTo(b2.title);
    }
}
//-------------------------------------------------------------------------------------------------
class BooksByAuthor implements IComparator<Book> {
    //compares books by author lexicographically
    public int apply(Book b1, Book b2) {
        return b1.author.compareTo(b2.title);
    }
}
//-------------------------------------------------------------------------------------------------
class BooksByPrice implements IComparator<Book> {
    // compares books by price (cheapest comes first)
    public int apply(Book b1, Book b2) {
        return (b1.price - b2.price);
    }
}
//-------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------
//Abstract Binary Search Tree
abstract class ABST<T> {
    IComparator<T> order;

    ABST(IComparator<T> order) {
        this.order = order;
    }
    //Inserting new item according to current IComparator
    abstract ABST<T> insert(T item);
    //Getting leftmost item of tree
    abstract Node<T> getLeftMost();
    //Helper for getLeftMost
    abstract Node<T> getLeftMostHelper(Node<T> n);
    abstract ABST<T> getRight();
    abstract boolean isLeaf();
    abstract boolean sameTree(ABST<T> t);
    abstract boolean sameLeaf(Leaf<T> t);
    abstract boolean sameNode(Node<T> t);
    abstract boolean sameData(ABST<T> t);
    abstract boolean sameDataLeaf(Leaf<T> t);
    abstract boolean sameDataNode(Node<T> t);
}

//-------------------------------------------------------------------------------------------------
//Representation for a leaf
class Leaf<T> extends ABST<T> {
    Leaf(IComparator<T> order) {
        super(order);
    }

  //Inserts item according to current order
    public ABST<T> insert(T item) {
        return new Node<T>(this.order, item, new Leaf<T>(this.order), new Leaf<T>(this.order));
    }
    //Getting leftmost item of tree
    public Node<T> getLeftMost() {
        throw new RuntimeException("No leftmost item of an empty tree");
    }
    //Helper for getLeftMost
    public Node<T> getLeftMostHelper(Node<T> n) {
        return n;
    }
    //Returns all of tree but the leftmost
    public ABST<T> getRight() {
        throw new RuntimeException("No right of an empty tree");
    }
    //Sees if a given tree is a leaf
    public boolean isLeaf() {
        return true;
    }
    //Compares two trees
    public boolean sameTree(ABST<T> t) {
        return t.sameLeaf(this);
    }
    //Compares two leaves
    public boolean sameLeaf(Leaf<T> that) {
        return true;
    }
    //Returns false, as no leaf and node are equal
    public boolean sameNode(Node<T> that) {
        return false;
    }
    public boolean sameData(ABST<T> that) {
        return that.sameDataLeaf(this);
    }
    public boolean sameDataLeaf(Leaf<T> that) {
        return true;
    }
    public boolean sameDataNode(Node<T> that) {
        return false;
    }
}
//-------------------------------------------------------------------------------------------------
//Representation for a node
class Node<T> extends ABST<T> {
    T data;
    ABST<T> left;
    ABST<T> right;

    //Constructor
    Node(IComparator<T> order, T data, ABST<T> left, ABST<T> right) {
        super(order);
        this.data = data;
        this.left = left;
        this.right = right;
    }

    //Inserts item according to current order
    public ABST<T> insert(T item) {
        if (this.order.apply(this.data, item) < 0) {
            return new Node<T>(this.order, this.data,
                new Node<T>(this.order, item, this.left, new Leaf<T>(this.order)), this.right);
        }
        else {
            return new Node<T>(this.order, this.data, this.left, this.right.insert(item));
        }
    }
  //Helper for getLeftMost
    public Node<T> getLeftMostHelper(Node<T> n) {
        return this.left.getLeftMostHelper(this);
  }
    //Getting leftmost item of tree
    public Node<T> getLeftMost() {
        return getLeftMostHelper(this);
}
    //Returns all of tree but the leftmost
    public Node<T> getRightHelper(Node<T> n, Node<T>n1) {
        return getRightHelper(this, n);
    }
  //Returns all of tree but the leftmost
    public ABST<T> getRight() {
        if(this.left.isLeaf())
            return this.left;
        else {
            return new Node<T>(this.order, this.data, this.left.getRight(), this.right);
        }

    }
    //Sees if node is a leaf(always false)
    public boolean isLeaf() {
        return false;
    }
    //Compares two trees
    public boolean sameTree(ABST<T> that) {
        return that.sameNode(this);
    }
    //Always fasle
    public boolean sameLeaf(Leaf<T> that) {
        return false;
    }
    //Compares two nodes
    public boolean sameNode(Node<T> that) {
        return this.order.apply(this.data, that.data) == 0;
    }
    public boolean sameData(ABST<T> that) {
        return that.sameDataNode(this);
    }
    public boolean sameDataLeaf(Leaf<T> that) {
        return false;
    }
    public boolean sameDataNode(Node<T> that) {
        return this.allIn(that) && that.allIn(this);
    }
    public boolean allIn(Node<T> that) {
        return this.data.in(that) && this.left.allIn(that) && this.right.allIn(that);

    }
}

//-------------------------------------------------------------------------------------------------
//-------------------------------------------------------------------------------------------------
//Examples class
class ABSTExamples {

    String razzaq = "Razzaq";
    //Book examples
    Book b1 = new Book("HTDP", razzaq, 7);
    Book b2 = new Book("Psychology", "Neil", 99);
    Book b3 = new Book("What is?", "Yudkovich", 44);
    Book b4 = new Book("Am I doing this right?", "Descartes", 44);
    Book b5 = new Book("HTDP", razzaq, 44);

    //ABST examples
    ABST<Book> t1 = new Leaf<Book>(new BooksByAuthor());
    ABST<Book> t2 = new Node<Book>(new BooksByAuthor(), b1, new Leaf<Book>(new BooksByAuthor()),
        new Leaf<Book>(new BooksByAuthor()));
    ABST<Book> t3 = new Node<Book>(new BooksByTitle(), b4, t2, t1);
    ABST<Book> t4 = new Node<Book>(new BooksByPrice(), b5, t3, t2);
    //Test for BooksByAuthor
    boolean testBooksByAuthor(Tester t) {
        return t.checkExpect((new BooksByAuthor().apply(this.b1, this.b2) > 0), true) &&
            t.checkExpect((new BooksByAuthor().apply(this.b1, this.b3) < 0), true) &&
            t.checkExpect((new BooksByAuthor().apply(this.b1,  this.b5) == 0), true);
    }
    //Test for BooksByTitle
    boolean testBooksByTitle(Tester t) {
        return t.checkExpect((new BooksByTitle().apply(this.b1, this.b2) < 0), true) &&
            t.checkExpect((new BooksByTitle().apply(this.b3, this.b2) > 0), true) &&
            t.checkExpect((new BooksByTitle().apply(this.b5, this.b1) == 0), true);
    }
    //Test for BooksByPrice
    boolean testBooksByPrice(Tester t) {
        return t.checkExpect((new BooksByPrice().apply(this.b1, this.b2) < 0), true) &&
            t.checkExpect((new BooksByPrice().apply(this.b3,  this.b1) > 0), true) &&
            t.checkExpect((new BooksByPrice().apply(this.b4, this.b5) == 0), true);
    }
    //Test for insert
    boolean testInsert(Tester t) {
        return t.checkExpect(t1.insert(b1),t2) &&
            t.checkExpect(t2.insert(b5), new Node<Book>(new BooksByAuthor(), b1,
                new Leaf<Book>(new BooksByAuthor()),
                new Node<Book>(new BooksByAuthor(), b5, new Leaf<Book>(new BooksByAuthor()),
                    new Leaf<Book>(new BooksByAuthor())))) &&
            t.checkExpect(t2.insert(b3), new Node<Book>(new BooksByAuthor(), b1,
                new Node<Book>(new BooksByAuthor(), b3, new Leaf<Book>(new BooksByAuthor()),
                    new Leaf<Book>(new BooksByAuthor())),
                    new Leaf<Book>(new BooksByAuthor()))) &&
            t.checkExpect(t2.insert(b4), new Node<Book>(new BooksByAuthor(), b1,
                new Leaf<Book>(new BooksByAuthor()),
                new Node<Book>(new BooksByAuthor(), b4, new Leaf<Book>(new BooksByAuthor()),
                    new Leaf<Book>(new BooksByAuthor()))));
    }
}