import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.Random;
import java.util.Comparator;
import java.util.Collections;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Search {
	public static void main(String[] args) {
		// Read in file contents (title+description)
		List<String> desc;
		try {
			desc = Util.readFile(args[0]);
		} catch (IOException e) {
			System.err.println("Couldn't read file! " + e.getMessage());
			return;
		}

		// Creates a new search tree with a comparator compairing Films
		AVLTree<Film> tree = new AVLTree<Film>(new FilmComperator());

		// Insert the films into the tree and count how many were successfully inserted
		// (i.e. weed out duplicate keys)
		int size = 0;
		for (String d : desc) {
			String title = d.split("\t")[0];
			String description = d.split("\t")[1];
			Film f = new Film(title, description);
			boolean inserted = tree.insert(f);
			if (inserted)
				size++;
		}
		// Compare logarithm and depth of search tree
		System.out.println("log2(" + size + ") = " + Math.log(size) / Math.log(2));
		System.out.println("depth = " + tree.depth());

		// Read in file contents (titles to search)
		List<String> needles;
		try {
			needles = Util.readFile(args[1]);
		} catch (IOException e) {
			System.err.println("Couldn't read file! " + e.getMessage());
			return;
		}

		// Search the given titles in the tree
		List<String> output = new ArrayList<String>();
		for (String needle : needles) {
			Film f = tree.search(new Film(needle, ""));
			String out = f == null ? " --- NOT FOUND ---" : f.toString();
			output.add(out);
		}

		// Write output file
		try {
			Util.writeFile(args[2], output.stream().collect(Collectors.joining("\n")));
		} catch (IOException e) {
			System.err.println("Couldn't write file! " + e.getMessage());
			return;
		}
	}

	private static class Util {
		@SuppressWarnings("unchecked")
		static List<String> readFile(String file) throws IOException {
			BufferedReader reader = new BufferedReader(new FileReader(file));
			List<?> contents = reader.lines().collect(Collectors.toList());
			reader.close();
			return (List<String>) contents;
		}

		static void writeFile(String file, String contents) throws IOException {
			BufferedWriter writer = new BufferedWriter(new FileWriter(file));
			writer.write(contents);
			writer.close();
		}
	}
}

class FilmComperator implements Comparator<Film> {
	@Override
	public int compare(Film s1, Film s2) {
		return s1.getTitle().compareTo(s2.getTitle());
	}
}

class Film {
	private String description;
	private String title;

	public Film(String title, String desc) {
		this.title = title;
		this.description = desc;
	}

	public String getTitle() {
		return this.title;
	}

	public String getDescription() {
		return this.description;
	}

	@Override
	public String toString() {
		return this.title + "\t" + this.description;
	}
}

// A search tree
class AVLTree<T> {
	private Comparator<T> comparator;
	public Node<T> root; // Is null if the tree is empty

	public AVLTree(Comparator<T> comp) {
		this.comparator = comp;
		this.root = null;
	}

	// Returns true if the value was successfully inserted
	public boolean insert(T data) {
		if (this.root == null) {
			this.root = new Node<T>(data, null, this.comparator, this);
			return true;
		}
		return this.root.insert(data);
	}

	// Returns the value belonging to the given key, or null if not found
	public T search(T data) {
		if (this.root == null) {
			return null;
		}
		return this.root.search(data);
	}

	// Computes the depth of the search tree
	public int depth() {
		if (this.root == null) {
			return -1;
		}
		return this.root.depth();
	}
}

// A node of the search tree
class Node<T> {
	private Comparator<T> comp;
	private Node<T> parent; // Can be null
	private Node<T> left; // Can be null
	private Node<T> right; // Can be null
	private AVLTree<T> tree;
	private T data;

	public Node(T data, Node<T> parent, Comparator<T> comparator, AVLTree<T> tree) {
		this.comp = comparator;
		this.parent = parent;
		this.left = null;
		this.right = null;
		this.data = data;
		this.tree = tree;
	}

	// Returns true if the value was successfully inserted
	public boolean insert(T data) {
		int c = this.comp.compare(data, this.data);
		if (c < 0) {
			if (this.left == null) {
				this.left = new Node<T>(data, this, this.comp, tree);
				return true;
			} else {
				boolean tmp = this.left.insert(data);
				this.correctBalance();
				return tmp;
			}
		} else if (c > 0) {
			if (this.right == null) {
				this.right = new Node<T>(data, this, this.comp, tree);
				return true;
			} else {
				boolean tmp = this.right.insert(data);
				this.correctBalance();
				return tmp;
			}
		}
		return false;
	}

	// Returns the value belonging to the given key, or null if not found
	public T search(T data) {
		int c = this.comp.compare(data, this.data);
		if (c < 0) {
			if (this.left == null) {
				return null;
			}
			return this.left.search(data);
		}
		if (c > 0) {
			if (this.right == null) {
				return null;
			}
			return this.right.search(data);
		}
		return this.data;
	}

	public int depth() {
		boolean l0 = this.left == null;
		boolean r0 = this.right == null;
		if (r0 && l0) {
			return 0;
		}
		if (r0) {
			return 1 + this.left.depth();
		}
		if (l0) {
			return 1 + this.right.depth();
		}
		int d_left = this.left.depth();
		int d_right = this.right.depth();
		return 1 + Math.max(d_left, d_right);
	}

	private void correctBalance() {
		if (this.getBalance() > 1) {
			leftRotation();
		} else if (this.getBalance() < -1) {
			rightRotation();
		}
	}

	private int getBalance() {
		if (this.left != null && this.right != null) {
			return this.right.depth() - this.left.depth();
		} else if (this.left != null && this.right == null) {
			return 0 - this.left.depth();
		} else if (this.left == null && this.right != null) {
			return this.right.depth();
		} else {
			return 0;
		}
	}

	private void rightRotation() {
        boolean isLeft = true;
        Node<T> pp = null;
        if(this.parent != null) {
            isLeft = this.parent.left == this;
            pp = this.parent;
        }
        else {
            tree.root = this.left;
        }

        Node<T> t2 = this.left.right;
        Node<T> r = this.left;

        r.right = null;
        this.left = t2;
        r.parent = pp;
        if(t2 != null) t2.parent = this;
        r.right = this;
        this.parent = r;
        if(pp != null) {
            if(isLeft) pp.left = r;
            else pp.right = r;
        }
	}

	private void leftRotation() {
		boolean isLeft = true;
		Node<T> pp =null;
		if (this.parent != null) {
			isLeft = this.parent.left == this;
			pp = this.parent;
		} else {
			tree.root = this.right;
		}
		Node<T> t2 = this.right.left;
		Node<T> r = this.right;

		r.left = null;
		this.right = t2;
		r.parent = pp;
		if (t2 != null)	t2.parent = this;
		r.left = this;
		this.parent = r;
		if (pp != null) {
			if (isLeft)
				pp.left = r;
			else
				pp.right = r;
		}
	}
}