import java.io.*;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Algorithmen, Ws07/08 Daniel Huson und Regula Rupp
 * <p/>
 * Uebungsaufgabe BinarySearchTree
 */
public class BinarySearchTree {
    static String AUTHOR = "YOUR_NAME_HERE_PLEASE";

    // Aufgabe 1:

    /**
     * constructor
     */
    public BinarySearchTree() {

    }

    /**
     * insert a element and its key
     *
     * @param key
     * @pram element
     */
    public void insert(Object element, int key) {

    }

    /**
     * delete an element with the given key key
     *
     * @param key
     */
    public void delete(int key) {

    }

    /**
     * search for an element with the given key
     *
     * @param key
     * @return object or null
     */
    public Object search(int key) {
        return null;
    }

    /**
     * get successor  key
     *
     * @param key
     * @return successor
     */
    public int getSuccessor(int key) {
        return 0;
    }

    /**
     * get predecessor key
     *
     * @param key
     * @return predecessor
     */
    public int getPredecessor(int key) {
        return 0;
    }

    /**
     * get minimum key
     *
     * @return minimum key
     */
    public int getMinimum() {
        return 0;
    }

    /**
     * get maximum key
     *
     * @return maximum key
     */
    public int getMaximum() {
        return 0;
    }

    /**
     * print the tree to System.out
     */
    public void print() {
        System.out.println("tree:");
    }

    // Aufgabe 2:

    /**
     * find all occurrences of a key using getPredecessor and getSuccessor
     *
     * @param key
     * @return list of all occurrences (empty list, if none found)
     */
    private java.util.List searchAll(int key) {
        return new LinkedList();
    }

    // ========= ab hier bitte nichts aendern ============

    /**
     * run the binary search tree program. Usage:  java BinarySearchTree [inputfile]
     *
     * @param args
     * @throws java.io.IOException
     */
    public static void main(String[] args) throws IOException {
        System.err.println("BinaySearchTree by " + AUTHOR);
        System.err.println("Commands:\n" +
                "\tInsert: insert <key>*\n" +
                "\tDelete: delete <key>*\n" +
                "\tSearch: search <key>*\n" +
                "\tSearch for all: all <key>*\n" +
                "\tSuccessor: succ <key>*\n" +
                "\tPredecessor: pred <key>*\n" +
                "\tMinimum: min\n" +
                "\tMaximum: max\n" +
                "\tPrint tree: print\n" +
                "\tQuit: quit\n");

        BinarySearchTree binarySearchTree = new BinarySearchTree();

        BufferedReader r = new BufferedReader(args.length >= 1 ? new FileReader(new File(args[0])) : new InputStreamReader(System.in));

        System.out.print("> ");
        System.out.flush();
        String aLine;
        while ((aLine = r.readLine()) != null) {
            aLine = aLine.trim();
            if (aLine != null && aLine.length() > 0 && !aLine.startsWith("#")) {
                StringTokenizer st = new StringTokenizer(aLine);
                if (st.hasMoreTokens()) {
                    String command = st.nextToken();

                    if (" insert delete search all succ pred min max print quit ".indexOf(" " + command + " ") == -1)
                        System.err.println("Error: Unknown command: " + command);
                    else if (command.equals("min")) {
                        System.out.println(binarySearchTree.getMinimum());
                    } else if (command.equals("max")) {
                        System.out.println(binarySearchTree.getMaximum());
                    } else if (command.equals("print")) {
                        binarySearchTree.print();
                    } else if (command.equals("quit")) {
                        System.exit(0);
                    }
                        while (st.hasMoreTokens()) {
                            try{
                            if (command.equals("insert")) {
                                int key = Integer.parseInt(st.nextToken());
                                binarySearchTree.insert("element_" + key, key);
                            } else if (command.equals("delete")) {
                                int key = Integer.parseInt(st.nextToken());
                                binarySearchTree.delete(key);
                            } else if (command.equals("search")) {
                                int key = Integer.parseInt(st.nextToken());
                                System.out.println("Search(" + key + "): " + binarySearchTree.search(key));
                            } else if (command.equals("all")) {
                                int key = Integer.parseInt(st.nextToken());
                                java.util.List result = binarySearchTree.searchAll(key);
                                for (Iterator it = result.iterator(); it.hasNext();)
                                    System.out.print(" " + it.next());
                                System.out.println();
                            } else if (command.equals("succ")) {
                                int key = Integer.parseInt(st.nextToken());
                                System.out.println(binarySearchTree.getSuccessor(key));
                            } else if (command.equals("pred")) {
                                int key = Integer.parseInt(st.nextToken());
                                System.out.println(binarySearchTree.getPredecessor(key));
                            } else {
                                System.err.println("Error: Unexpected argument: " + st.nextToken());
                                break;
                            }
                            }
                            catch(Exception ex)
                            {
                                System.err.println("Error: "+ex);
                            }
                        }
                }
            }
            System.out.print("> ");
            System.out.flush();
        }
    }
}