import java.io.*;
import java.util.ArrayList;
import java.util.Scanner;

class RBT {

    private final int RED = 0;
    private final int BLACK = 1;

    private class Node {
        String key = "";
        String translations;
        int color = BLACK;
        Node left = nil;
        Node right = nil;
        Node parent = nil;

        Node(String key, String translations) {
            this.key = key;
            this.translations = translations;
        }
    }

    private final Node nil = new Node("", null);
    private Node root = nil;

    public void printTree(Node node) {
        if (node == nil)
            return;

        printTree(node.left);

        if (node.color == RED)
            System.out.print("Red " + node.key + " Parent: " + node.parent.key + "\n");
        else
            System.out.print("Black " + node.key + " Parent: " + node.parent.key + "\n");

        printTree(node.right);
    }

    public void printTree(Node node, PrintWriter fileOut) {
        if (node == nil)
            return;

        printTree(node.left, fileOut);

        fileOut.print(node.key + " ");
        fileOut.print(node.translations);
        fileOut.println();

        printTree(node.right, fileOut);
    }

    public void printTreeBinary(Node node, FileOutputStream file) throws IOException{

        if(node == nil)
            return;

        printTreeBinary(node.left, file);

        String result = "";
        result += node.translations.length();
        result +=  node.translations;

        String bytes = node.key.length()+node.key+result;
        byte[] buffer = bytes.getBytes();
        file.write(buffer);

        printTreeBinary(node.right, file);
    }

    private Node findNode(Node findNode, Node node) {
        if (root.key.equals(nil))
            return null;

        if (findNode.key.compareTo(node.key) < 0) {
            if (node.left != nil)
                return findNode(findNode, node.left);
        } else if (findNode.key.compareTo(node.key) > 0) {
            if (node.right != nil)
                return findNode(findNode, node.right);
        } else if (findNode.key.equals(node.key)) {
            return node;
        }

        return null;
    }

    private void insert(Node node) {
        Node temp = root;

        if (root == nil) {
            root = node;
            node.color = BLACK;
            node.parent = nil;
        } else {
            node.color = RED;
            while (true) {
                if (node.key.compareTo(temp.key) < 0) {
                    if (temp.left == nil) {
                        temp.left = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.left;
                    }
                } else if (node.key.compareTo(temp.key) >= 0) {
                    if (temp.right == nil) {
                        temp.right = node;
                        node.parent = temp;
                        break;
                    } else
                        temp = temp.right;
                }
            }
            fixTree(node);
        }
    }

    private void fixTree(Node node) {
        while (node.parent.color == RED) {
            Node uncle = nil;
            if (node.parent == node.parent.parent.left) {
                uncle = node.parent.parent.right;

                if (uncle != nil && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                    continue;
                }

                if (node == node.parent.right) {
                    node = node.parent;
                    leftRotate(node);
                }

                node.parent.color = BLACK;
                node.parent.parent.color = RED;

                rightRotate(node.parent.parent);
            } else {
                uncle = node.parent.parent.left;

                if (uncle != nil && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                    continue;
                }

                if (node == node.parent.left) {
                    node = node.parent;
                    rightRotate(node);
                }

                node.parent.color = BLACK;
                node.parent.parent.color = RED;

                leftRotate(node.parent.parent);
            }
        }
        root.color = BLACK;
    }

    void leftRotate(Node node) {
        if (node.parent != nil) {
            if (node == node.parent.left)
                node.parent.left = node.right;
            else
                node.parent.right = node.right;

            node.right.parent = node.parent;
            node.parent = node.right;

            if (node.right.left != nil)
                node.right.left.parent = node;

            node.right = node.right.left;
            node.parent.left = node;
        } else {
            Node right = root.right;
            root.right = right.left;
            right.left.parent = root;
            root.parent = right;
            right.left = root;
            right.parent = nil;
            root = right;
        }
    }

    void rightRotate(Node node) {
        if (node.parent != nil) {
            if (node == node.parent.left)
                node.parent.left = node.left;
            else
                node.parent.right = node.left;

            node.left.parent = node.parent;
            node.parent = node.left;

            if (node.left.right != nil)
                node.left.right.parent = node;

            node.left = node.left.right;
            node.parent.right = node;
        } else {
            Node left = root.left;
            root.left = root.left.right;
            left.right.parent = root;
            root.parent = left;
            left.right = root;
            left.parent = nil;
            root = left;
        }
    }

    void changeNodes(Node target, Node with){
        if(target.parent == nil)
            root = with;
        else if(target == target.parent.left)
            target.parent.left = with;
        else
            target.parent.right = with;

        with.parent = target.parent;
    }

    boolean delete(Node z){
        if( (z = findNode(z, root)) == null)
            return false;

        Node x;
        Node y = z;
        int y_original_color = y.color;

        if(z.left == nil){
            x = z.right;
            changeNodes(z, z.right);
        }else if(z.right == nil){
            x = z.left;
            changeNodes(z, z.left);
        }else{
            y = treeMinimum(z.right);
            y_original_color = y.color;
            x = y.right;
            if(y.parent == z)
                x.parent = y;
            else{
                changeNodes(y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }
            changeNodes(z, y);
            y.left = z.left;
            y.left.parent = y;
            y.color = z.color;
        }
        if(y_original_color == BLACK)
            deleteFixUp(x);
        return true;
    }

    void deleteFixUp(Node x){
        while(x!=root && x.color == BLACK){
            if(x == x.parent.left){
                Node w = x.parent.right;
                if(w.color == RED){
                    w.color = BLACK;
                    x.parent.color = RED;
                    leftRotate(x.parent);
                    w = x.parent.right;
                }
                if(w.left.color == BLACK && w.right.color == BLACK){
                    w.color = RED;
                    x = x.parent;
                    continue;
                }
                else if(w.right.color == BLACK){
                    w.left.color = BLACK;
                    w.color = RED;
                    rightRotate(w);
                    w = x.parent.right;
                }
                if(w.right.color == RED){
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.right.color = BLACK;
                    leftRotate(x.parent);
                    x = root;
                }
            }else{
                Node w = x.parent.left;
                if(w.color == RED){
                    w.color = BLACK;
                    x.parent.color = RED;
                    rightRotate(x.parent);
                    w = x.parent.left;
                }
                if(w.right.color == BLACK && w.left.color == BLACK){
                    w.color = RED;
                    x = x.parent;
                    continue;
                }
                else if(w.left.color == BLACK){
                    w.right.color = BLACK;
                    w.color = RED;
                    leftRotate(w);
                    w = x.parent.left;
                }
                if(w.left.color == RED){
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.left.color = BLACK;
                    rightRotate(x.parent);
                    x = root;
                }
            }
        }
        x.color = BLACK;
    }

    Node treeMinimum(Node node){
        while(node.left != nil)
            node = node.left;
        return node;
    }

    public void functionality() throws IOException{
        Scanner fileIn = new Scanner (new FileReader("plikwejsciowy.txt"));
        PrintWriter fileOut = new PrintWriter("plikwyjsciowy.txt");
        Scanner scanner = new Scanner(System.in);
        Scanner scanLines = new Scanner(System.in);
        FileInputStream inputStream = new FileInputStream("andrzej.dat");


        String item, line, word;
        Node node;
        int choice;
        boolean ifTrue = true;

        while(fileIn.hasNext()){
            line = fileIn.nextLine();
            String[] split = line.split(" ");
            item = split[0];
            String stringArray = "";
            for(int i = 1; i < split.length; i++)
                stringArray += split[i] + " ";

            node = new Node(item, stringArray);
            insert(node);
        }

        printTree(root);

        menu();
        while(ifTrue == true) {
            choice = scanner.nextInt();
            switch (choice) {
                case 1:
                    word = scanner.next();
                    node = new Node(word, null);

                    if (findNode(node, root) != null) {
                        System.out.println("Word " + node.key + " found! Here are translations:");
                        node = findNode(node, root);
                        System.out.println(node.translations);
                    }
                    else
                        System.out.println("Sorry, word " + node.key + " not found!");
                    break;

                case 2:
                    word = scanner.next();
                    node = new Node(word, null);
                    System.out.print("\nDeleting item " + word);

                    if (delete(node))
                        System.out.println(": deleted!\n\n");
                    else
                        System.out.println(": does not exist!\n\n");

                    printTree(root);
                    break;

                case 3:
                    word = scanLines.nextLine();
                    String[] split = word.split(" ");
                    String tempList = "";

                    for(int i = 1; i < split.length; i++)
                        tempList += split[i] + " ";

                    node = new Node(split[0], tempList);
                    insert(node);

                    printTree(root);
                    break;

                case 4:
                    printTree(root, fileOut);
                    break;

                case 5:
                    FileOutputStream outputStream = new FileOutputStream("andrzej.dat");
                    printTreeBinary(root, outputStream);
                    outputStream.close();
                    break;

                case 7:
                    printTree(root);
                    break;

                default:
                    ifTrue = false;
                    break;
            }
        }

        fileIn.close();
        fileOut.close();
    }

    public static void menu(){
        System.out.println("\n1 - Find word with translations\n"
                + "2 - Delete word\n"
                + "3 - Insert word with translations (in one line)\n"
                + "4 - Save dictionary to a file\n"
                + "5 - Save dictionary to a binary file\n"
                + "6 - Read from binary file\n"
                + "7 - Print tree\n"
                + "Any other to quit\n");
    }

    public static void main(String[] args) throws IOException{
        RBT dictionary_rbt = new RBT();
        dictionary_rbt.functionality();
    }
}