package lab9;
import java.util.*;
/**
 * Implements a Map as a binary search tree of (key,value) pairs.
 * CSE131 Lab 9
 * @author
 * @version 1.0
 * Date:
 */
public class TreeMap<K extends Comparable<K>,V> implements Map<K,V> {

    TreeNode<K, V> root;

    public TreeMap() {
        root = new TreeNode<K,V>(null, null);
    }

    public void put(K key, V value) {
        TreeNode<K, V> newItem = new TreeNode<K, V>(key, value);
        TreeNode<K, V> pointer = root.left;

        if(root.left == null) {
            root.left = newItem;
            return;
        }

        while(true) {
            if(pointer.key.compareTo(key) == 0) {
                pointer.value = value;
                return;
            }

            else if(pointer.key.compareTo(key) < 0) {
                if(pointer.right == null) {
                    pointer.right = newItem;
                    return;
                }
                else
                    pointer = pointer.right;
            }

            else {
                if(pointer.left == null) {
                    pointer.left = newItem;
                    return;
                }
                else
                    pointer = pointer.left;
            }
        }
    }

    public V get(K key) {
        TreeNode<K, V> pointer = root.left;

        while(pointer != null) {
            if(pointer.key.compareTo(key) == 0) {
                if(pointer.deleted == false)
                    return pointer.value;
                else
                    throw new NoSuchElementException();
            }

            else if(pointer.key.compareTo(key) < 0)
                pointer = pointer.right;

            else
                pointer = pointer.left;
        }

        throw new NoSuchElementException();
    }

    public boolean contains(K key) {
        TreeNode<K, V> pointer = root.left;

        while(pointer != null) {
            if(pointer.key.compareTo(key) == 0) {
                if(pointer.deleted == true)
                    return false;
                else
                    return true;
            }

            else if(pointer.key.compareTo(key) < 0)
                pointer = pointer.right;

            else
                pointer = pointer.left;
        }

        return false;
    }

    public boolean remove(K key) {
        TreeNode<K, V> pointer = root;

        if(!contains(key))
            return false;

        while(pointer != null) {
            if(pointer.left.key.compareTo(key) == 0) {
                if(pointer.left.left == null && pointer.left.right == null) {
                    pointer.left = null;
                    return true;
                }
                else if(pointer.left.left == null ^ pointer.left.right ==  null) {
                    if(pointer.left.left == null) {
                        pointer.left = pointer.left.right;
                    }
                    else {
                        pointer.left = pointer.left.left;
                    }
                    return true;
                }
                else {
                    TreeNode<K, V> newPointer = pointer.left.left;
                    while(newPointer.left.right != null) {
                        newPointer = newPointer.right;
                    }
                    remove(newPointer.key);
                    pointer.left.key = newPointer.key;
                    pointer.left.value = newPointer.value;
                    return true;
                }
            }

            else if(pointer != root && pointer.right.key.compareTo(key) == 0) {
                if(pointer.right.left == null && pointer.right.right == null) {
                    pointer.right = null;
                    return true;
                }
                else if(pointer.right.left == null ^ pointer.right.right ==  null) {
                    if(pointer.right.left == null) {
                        pointer.right = pointer.right.right;
                    }
                    else {
                        pointer.right = pointer.right.left;
                    }
                    return true;
                }
                else {
                    TreeNode<K, V> newPointer = pointer.left.right;
                    while(newPointer.right.left != null) {
                        newPointer = newPointer.left;
                    }
                    remove(newPointer.key);
                    pointer.right.key = newPointer.key;
                    pointer.right.value = newPointer.value;
                    return true;
                }
            }

            else if(pointer != root && pointer.key.compareTo(key) < 0)
                pointer = pointer.right;

            else
                pointer = pointer.left;
        }

        return false;
    }

    public String toString() {
        return toStringHelper(root.left, "", "");
    }

    public String toStringHelper(TreeNode<K, V> node, String tabs, String helper) {
        if (node.right != null) {
            helper = helper + toStringHelper(node.right, tabs + "\t", "");
        }
        helper += tabs + "(" + node.key + ", " + node.value + ")\n";
        if (node.left != null) {
            helper = helper + toStringHelper(node.left, tabs + "\t", "");
        }
        return helper;
    }

}