// Arup Guha
// Started around 9/1/2026, this implementation is as of 9/8/2026
// Splay Tree Implementation (this only has insert and search)

import java.util.*;

public class SplayTree<T extends Comparable<T>> {
        
    private class Node {
        
		T data;
		Node left;
		Node right;
		Node par;

		// Creates a new Node storing a single value and 2 null kids.
        Node(T val) {	
			data = val;
			left = null;
			right = null;
			par = null;
        }
		
		// For debugging, should always print in order.
		// Allows me to see the shape of the tree with parent info.
		public void inorder() {
			if (left != null) left.inorder();
			System.out.print(data);
			if (par != null) System.out.println(" and par is "+par.data);
			else System.out.println(" and par is null");
			if (right != null) right.inorder();
		}
		
		// Also allows me to see the shape of the tree w/inorder, for debugging.
		public void preorder() {
			System.out.println(data);
			if (left != null) left.preorder();
			if (right != null) right.preorder();
		}
		
    }

    private Node root;

	// Empty tree.
	public SplayTree() {
		root = null;
	}

    // Insert val into this 2-4 tree.
    public void insert(T val) {
		
		// Easy case.
		if (root == null) {
			root = new Node(val);
			return;
		}
	
		// For my loop.
		Node tmp = root;
		while (tmp != null) {
			
			// Base case left...
			if (tmp.left == null && val.compareTo(tmp.data) < 0) {
				tmp.left = new Node(val);
				tmp.left.par = tmp;
				splay(tmp.left);
				return;
			}
			
			// Base case right.
			if (tmp.right == null && val.compareTo(tmp.data) >= 0) {
				tmp.right = new Node(val);
				tmp.right.par = tmp;
				splay(tmp.right);
				return;
			}
			
			// Recurse.
			if (val.compareTo(tmp.data) < 0) 
				tmp = tmp.left;
			else
				tmp = tmp.right;
		}
    }
	
	public void splay(Node curN) {
		
		// Made it to the top.
		if (curN.par == null) return;
		
		// Only one more level to go.
		if (curN.par == root) {
			
			// current node is left child.
			if (root.left == curN) {
				
				// If this thing's null, we don't have to do these things.
				if (curN.right != null) {
					curN.right.par = root;
					root.left = curN.right;
				}
				
				// If it is null, then this becomes null.
				else
					root.left = null;
				
				// curN goes to root, it's right will be the old root.
				curN.right = root;
				root.par = curN;
			}
			
			// current node is right child.
			else {
				
				// If this thing's null, we don't have to do these things.
				if (curN.left != null) {
					curN.left.par = root;
					root.right = curN.left;
				}
				
				// If it is null, then this becomes null.
				else
					root.right = null;
				
				// curN goes to root, it's right will be the old root.
				curN.left = root;
				root.par = curN;
			}
			
			// Now, we change our root.
			root = curN;
			root.par = null;
			return;
				
		} // Splay one level case.
		
		// Set these up.
		Node mypar = curN.par;
		Node gramps = mypar.par;
		Node oldGramps = gramps;
		
		/*** Just separate out the four cases. ***/
		if (gramps.left == mypar && mypar.left == curN) {
			
			// First redo the current node's parent and the link from that parent.
			curN.par = gramps.par;
			if (gramps.par != null) {
				if (gramps.par.left == gramps)
					gramps.par.left = curN;
				else
					gramps.par.right = curN;
			}
			
			// Now redo the other two parent links.
			gramps.par = mypar;
			mypar.par = curN;
			
			// Then reset these parents, if necessary.
			if (curN.right != null) curN.right.par = mypar;
			if (mypar.right != null) mypar.right.par = gramps;
			
			// This is at the lowest level.
			gramps.left = mypar.right;
			
			// Middle level.
			mypar.left = curN.right;
			mypar.right = gramps;
			
			// Top level.
			curN.right = mypar;
			
			// Update root if necessary.
			if (oldGramps == root) root = curN;
		}
		
		// right right case.
		else if (gramps.right == mypar && mypar.right == curN) {
			
			// This is the same as the left, left case.
			curN.par = gramps.par;
			if (gramps.par != null) {
				if (gramps.par.left == gramps)
					gramps.par.left = curN;
				else
					gramps.par.right = curN;
			}
			gramps.par = mypar;
			mypar.par = curN;
			
			// Then reset these parents, if necessary.
			if (curN.left != null) curN.left.par = mypar;
			if (mypar.left != null) mypar.left.par = gramps;
			
			// lowest level.
			gramps.right = mypar.left;
			
			// middle level.
			mypar.right = curN.left;
			mypar.left = gramps;
			
			// Top level.
			curN.left = mypar;
			
			// Reset root if necessary.
			if (oldGramps == root) root = curN;
		}
		
		// left-right case.
		else if (gramps.left == mypar && mypar.right == curN) {
			
			// First do parents.
			curN.par = gramps.par;
			if (gramps.par != null) {
				if (gramps.par.left == gramps)
					gramps.par.left = curN;
				else
					gramps.par.right = curN;
			}
			gramps.par = curN;
			mypar.par = curN;
			
			// Then reset these parents, if necessary.
			if (curN.left != null) curN.left.par = mypar;
			if (curN.right != null) curN.right.par = gramps;
			
			// middle level.
			mypar.right = curN.left;
			gramps.left = curN.right;
			
			// Top level.
			curN.left = mypar;
			curN.right = gramps;
			
			// Reset root if necessary.
			if (oldGramps == root) root = curN;
		}
		
		// Last case (gramps.right, mypar.left)
		else {
			
			// First do parents.
			curN.par = gramps.par;
			if (gramps.par != null) {
				if (gramps.par.left == gramps)
					gramps.par.left = curN;
				else
					gramps.par.right = curN;
			}
			gramps.par = curN;
			mypar.par = curN;
			
			// Then these parents.
			if (curN.left != null) curN.left.par = gramps;
			if (curN.right != null) curN.right.par = mypar;
			
			// middle level.
			gramps.right = curN.left;
			mypar.left = curN.right;
			
			// top level
			curN.left = gramps;
			curN.right = mypar;
			
			// Reset root if necessary.
			if (oldGramps == root) root = curN;
		}
		
		// We have to splay all the way to the top.
		if (curN != root) splay(curN);
	}
	
	// Returns true iff val is in this SplayTree.
	public boolean search(T val) {
		
		Node cur = root;
		while (cur != null) {
		
			int tmp = val.compareTo(cur.data);
			
			// For splaying on fail case.
			Node saveme = cur;
			
			// Found it.
			if (tmp == 0) {
				splay(cur);
				return true;
			}
			
			// Go to the next level.
			if (tmp < 0) 
				cur = cur.left;
			else
				cur = cur.right;
					
			// If we didn't find it, we splay the parent.
			if (cur == null) 
				splay(saveme);
		}
		
		// Not found.
		return false;
	}
	
	// Wrapper for inorder traversal.
	public void inorder() {
		if (root != null)
			root.inorder();
		System.out.println("----------------");
	}
	
	// Wrapper for preorder traversal.
	public void preorder() {
		if (root != null)
			root.preorder();
		System.out.println("+++++++++++++++++");
	}
	
	// Put your tests here.
	public static void main(String[] args) {
		test5(1000000);
	}
	
	// This test shows up power of generic implementation.
	public static void test1() {
		
		// Put some stuff in.
		SplayTree<Pair> mine = new SplayTree<Pair>();
		mine.insert(new Pair(3, 5));
		mine.insert(new Pair(2, 9));
		mine.insert(new Pair(3, 4));
		mine.insert(new Pair(3, 12));
		mine.insert(new Pair(5, 1));
		mine.insert(new Pair(1, 12));
		mine.insert(new Pair(4, 3));
		mine.insert(new Pair(3, 8));
		mine.inorder();
		System.out.println();
		mine.preorder();
		System.out.println();
		
		// Search and print, should splay.
		System.out.println(mine.search(new Pair(3, 6)));
		mine.inorder();
		System.out.println();
		mine.preorder();
		System.out.println();
		
		// Same here.
		System.out.println(mine.search(new Pair(3, 4)));
		mine.inorder();
		System.out.println();
		mine.preorder();
		System.out.println();
		
		// And here.
		System.out.println(mine.search(new Pair(2, 8)));
		mine.inorder();
		System.out.println();
		mine.preorder();
		System.out.println();
		
		// And here.
		System.out.println(mine.search(new Pair(1, 12)));
		mine.inorder();
		System.out.println();
		mine.preorder();
		System.out.println();
	}
		
	// This test helped me uncover my bug where I wasn't resetting the old
	// grandpa's parent's link.
	public static void test2() {
		int[] vals = {12,5,1,6,8,7,2,4,3,9,11,10};
		SplayTree<Integer> mine = new SplayTree<Integer>();
		for (int i=0; i<vals.length; i++) {
			mine.insert(vals[i]);
			mine.preorder();
			mine.inorder();
		}
	}
	
	// Another basic hard-coded test. Sort of redundant compare to 2.
	public static void test3() {
		
		SplayTree<Integer> mine = new SplayTree<Integer>();
		mine.insert(3);
		mine.preorder();
		mine.inorder();
		
		mine.insert(1);
		mine.preorder();
		mine.inorder();
		
		mine.insert(10);
		mine.preorder();
		mine.inorder();
		
		mine.insert(7);
		mine.preorder();
		mine.inorder();
		
		mine.insert(5);
		mine.preorder();
		mine.inorder();
		
		mine.insert(4);
		mine.preorder();
		mine.inorder();
		
		mine.insert(6);
		mine.preorder();
		mine.inorder();
		
		mine.insert(8);
		mine.preorder();
		mine.inorder();
		
		mine.insert(20);
		mine.preorder();
		mine.inorder();
	}
	
	// I was curious how slow/fast this thing was.
	public static void test4(int n) {
		
		// Make a randomized array of the values form 0 to n-1.
		int[] vals = new int[n];
		for (int i=0; i<n; i++) {
			vals[i] = i;
		}
		Random r = new Random();
		for (int i=0; i<10*n; i++) {
			int x = r.nextInt(n);
			int y = r.nextInt(n);
			int tmp = vals[x];
			vals[x] = vals[y];
			vals[y] = tmp;
		}
		
		// Insert in this order and time it.
		long t1 = System.currentTimeMillis();
		SplayTree<Integer> mine = new SplayTree<Integer>();
		for (int i=0; i<n; i++) {
			mine.insert(vals[i]);
		}
		long t2 = System.currentTimeMillis();
		
		// This do n random searches and time it again.
		for (int i=0; i<n; i++) {
			boolean tmp = mine.search(r.nextInt(n));
		}
		long t3 = System.currentTimeMillis();
		
		// Print results.
		System.out.println("Inserting took "+(t2-t1)+" ms.");
		System.out.println("Searching took "+(t3-t2)+" ms.");
	}
	
	// This is the same as test4, but with Java's built in TreeSet.
	public static void test5(int n) {
		
		// Same code as above.
		int[] vals = new int[n];
		for (int i=0; i<n; i++) {
			vals[i] = i;
		}
		Random r = new Random();
		for (int i=0; i<10*n; i++) {
			int x = r.nextInt(n);
			int y = r.nextInt(n);
			int tmp = vals[x];
			vals[x] = vals[y];
			vals[y] = tmp;
		}
		
		// Time insert.
		long t1 = System.currentTimeMillis();
		TreeSet<Integer> mine = new TreeSet<Integer>();
		for (int i=0; i<n; i++) {
			mine.add(vals[i]);
		}
		long t2 = System.currentTimeMillis();
		
		// And random searches.
		for (int i=0; i<n; i++) {
			boolean tmp = mine.contains(r.nextInt(n));
		}
		long t3 = System.currentTimeMillis();
		
		// Ta da!
		System.out.println("TreeSet Inserting took "+(t2-t1)+" ms.");
		System.out.println("TreeSet Searching took "+(t3-t2)+" ms.");
	}
}

// Simple class that implements Comparable so I can test that it works
// with generics.
class Pair implements Comparable<Pair>
{
	
	private int x;
	private int y;
	
	public Pair(int myx, int myy) {
		x = myx;
		y = myy;
	}
	
	public int compareTo(Pair other) {
		if (this.x != other.x) return this.x - other.x;
		return this.y - other.y;
	}
	
	public String toString() {
		return "("+x+", "+y+")";
	}
}