package algs33;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac SplayBST.java
 *  Execution:    java SplayBST
 *
 *  Splay tree. Supports splay-insert, -search, and -delete.
 *  Splays on every operation, regardless of the presence of the associated
 *  key prior to that operation.
 *
 *  Written by Josh Israel.
 *
 *************************************************************************/


public class XSplayBST<K extends Comparable<? super K>, V>  {

  private Node<K,V> root;   // root of the BST

  // BST helper node data type
  private static class Node<K,V> {
    public final K key;          // key
    public V value;        // associated data
    public Node<K,V> left, right;   // left and right subtrees

    public Node(K key, V value) {
      this.key   = key;
      this.value = value;
    }
  }

  public boolean contains(K key) {
    return (get(key) != null);
  }

  // return value associated with the given key
  // if no such value, return null
  public V get(K key) {
    root = splay(root, key);
    int cmp = key.compareTo(root.key);
    if (cmp == 0) return root.value;
    else          return null;
  }

  /* ***********************************************************************
   *  splay insertion
   *************************************************************************/
  public void put(K key, V value) {
    // splay key to root
    if (root == null) {
      root = new Node<>(key, value);
      return;
    }

    root = splay(root, key);

    int cmp = key.compareTo(root.key);

    // Insert new node at root
    if (cmp < 0) {
      Node<K,V> n = new Node<>(key, value);
      n.left = root.left;
      n.right = root;
      root.left = null;
      root = n;
    }

    // Insert new node at root
    else if (cmp > 0) {
      Node<K,V> n = new Node<>(key, value);
      n.right = root.right;
      n.left = root;
      root.right = null;
      root = n;
    }

    // It was a duplicate key. Simply replace the value
    else if (cmp == 0) {
      root.value = value;
    }

  }

  /* ***********************************************************************
   *  splay deletion
   *************************************************************************/
  /* This splays the key, then does a slightly modified Hibbard deletion on
   * the root (if it is the node to be deleted; if it is not, the key was
   * not in the tree). The modification is that rather than swapping the
   * root (call it node A) with its successor, it's successor (call it Node<K,V> B)
   * is moved to the root position by splaying for the deletion key in A's
   * right subtree. Finally, A's right child is made the new root's right
   * child.
   */
  public void remove(K key) {
    if (root == null) return; // empty tree

    root = splay(root, key);

    int cmp = key.compareTo(root.key);

    if (cmp == 0) {
      if (root.left == null) {
        root = root.right;
      }
      else {
        Node<K,V> x = root.right;
        root = root.left;
        splay(root, key);
        root.right = x;
      }
    }

    // else: it wasn't in the tree to remove
  }


  /* **********************************************************************
   * splay function
   * **********************************************************************/
  // splay key in the tree rooted at Node<K,V> h. If a node with that key exists,
  //   it is splayed to the root of the tree. If it does not, the last node
  //   along the search path for the key is splayed to the root.
  private Node<K,V> splay(Node<K,V> h, K key) {
    if (h == null) return null;

    int cmp1 = key.compareTo(h.key);

    if (cmp1 < 0) {
      // key not in tree, so we're done
      if (h.left == null) {
        return h;
      }
      int cmp2 = key.compareTo(h.left.key);
      if (cmp2 < 0) {
        h.left.left = splay(h.left.left, key);
        h = rotateRight(h);
      }
      else if (cmp2 > 0) {
        h.left.right = splay(h.left.right, key);
        if (h.left.right != null)
          h.left = rotateLeft(h.left);
      }

      if (h.left == null) return h;
      else                return rotateRight(h);
    }

    else if (cmp1 > 0) {
      // key not in tree, so we're done
      if (h.right == null) {
        return h;
      }

      int cmp2 = key.compareTo(h.right.key);
      if (cmp2 < 0) {
        h.right.left  = splay(h.right.left, key);
        if (h.right.left != null)
          h.right = rotateRight(h.right);
      }
      else if (cmp2 > 0) {
        h.right.right = splay(h.right.right, key);
        h = rotateLeft(h);
      }

      if (h.right == null) return h;
      else                 return rotateLeft(h);
    }

    else return h;
  }


  /* ***********************************************************************
   *  helper functions
   *************************************************************************/

  // height of tree (empty tree height = 0)
  public int height() { return height(root); }
  private int height(Node<K,V> x) {
    if (x == null) return 0;
    return 1 + Math.max(height(x.left), height(x.right));
  }


  public int size() {
    return size(root);
  }

  private int size(Node<K,V> x) {
    if (x == null) return 0;
    else return (1 + size(x.left) + size(x.right));
  }

  // right rotate
  private Node<K,V> rotateRight(Node<K,V> h) {
    Node<K,V> x = h.left;
    h.left = x.right;
    x.right = h;
    return x;
  }

  // left rotate
  private Node<K,V> rotateLeft(Node<K,V> h) {
    Node<K,V> x = h.right;
    h.right = x.left;
    x.left = h;
    return x;
  }

  // test client
  public static void main(String[] args) {
    XSplayBST<Integer, Integer> st1 = new XSplayBST<>();
    st1.put(5, 5);
    st1.put(9, 9);
    st1.put(13, 13);
    st1.put(11, 11);
    st1.put(1, 1);


    XSplayBST<String, String> st = new XSplayBST<>();
    st.put("www.cs.princeton.edu", "128.112.136.11");
    st.put("www.cs.princeton.edu", "128.112.136.12");
    st.put("www.cs.princeton.edu", "128.112.136.13");
    st.put("www.princeton.edu",    "128.112.128.15");
    st.put("www.yale.edu",         "130.132.143.21");
    st.put("www.simpsons.com",     "209.052.165.60");
    StdOut.println("The size 0 is: " + st.size());
    st.remove("www.yale.edu");
    StdOut.println("The size 1 is: " + st.size());
    st.remove("www.princeton.edu");
    StdOut.println("The size 2 is: " + st.size());
    st.remove("non-member");
    StdOut.println("The size 3 is: " + st.size());
    StdOut.println(st.get("www.cs.princeton.edu"));
    StdOut.println("The size 4 is: " + st.size());
    StdOut.println(st.get("www.yale.com"));
    StdOut.println("The size 5 is: " + st.size());
    StdOut.println(st.get("www.simpsons.com"));
    StdOut.println("The size 6 is: " + st.size());
    StdOut.println();
  }

}