import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Queue;
 
public class Tree<T extends Comparable<T>> implements Iterable<T> {
    class Node<T extends Comparable<T>> {
        List<T> vals = new ArrayList<T>();
        List<Node<T>> children = new ArrayList<Node<T>>();
 
        boolean isLeaf() { return children.size() == 0; } 
        boolean is4Node() { return vals.size() == 3; }
 
        Node(T x) {
            vals.add(x);
        }
        
        Node(T x, Node<T> left, Node<T> right) {
            vals.add(x);
            children.add(left);
            children.add(right);
            children.add(null); // hack
        }
 
        public String toString() {
            String answer = "[";
            for (int i=0; i<vals.size(); i++) {
                if (i != 0) answer += ", ";
                if (children.size() != 0)
                    answer += children.get(i).toString();
                answer += vals.get(i);
            }
            if (children.size() != 0)
                answer += children.get(children.size()-2).toString();
            return answer + "]";
        }
 
        
        void getVals(List<T> iteratorList) {
            for (int i=0; i<vals.size(); i++) {
                if (children.size() != 0)
                    children.get(i).getVals(iteratorList);
                iteratorList.add(vals.get(i));
            }
            if (children.size() != 0)
                children.get(children.size()-2).getVals(iteratorList);
        }
 
        
        boolean add(T val) {
            if (isLeaf())
                return addToLeaf(val);
            else return addToInterior(val);
        }
        
        
        boolean addToLeaf(T x) {
            int cmp;
            // size is 1 for a 2-node, or 2 for a 3-node
            for (int i = 0; i < vals.size(); i++) {
                cmp = x.compareTo(vals.get(i));
                if (cmp == 0) return false;
                else if (cmp < 0) {
                    vals.add(i,x);
                    return true;
                }
            }
            vals.add(x);
            return true;
        }
        
        boolean addToInterior(T x) { 
            int cmp;
            // size is 1 for a 2-node, or 2 for a 3-node
            for (int i = 0; i <= vals.size(); i++) {
                if (i == vals.size()) cmp = -1; // hack because there is no vals[2]
                else cmp = x.compareTo(vals.get(i));
                if (cmp == 0) return false;
                else if (cmp < 0) {
                    boolean retVal = children.get(i).add(x);
                    if (children.get(i).is4Node())
                        childIs4Node(i);
                    return retVal;
                }
            }
            return false;  // unreachable  -- just for compiler
        }
        
        // the ith child is a 4-node
        void childIs4Node(int i) {
            System.out.println("childIs4Node " + i);
            System.out.println(this);
            Node<T> the4Node = children.get(i);
            System.out.println(the4Node);
            
            if (i == 2)
                vals.add(children.get(i).vals.get(1));
            else vals.add(i, children.get(i).vals.get(1));
            Node<T> newChild1, newChild2;
            if (children.get(i).isLeaf()) {
                newChild1 = new Node<T>(children.get(i).vals.get(0));
                newChild2 = new Node<T>(children.get(i).vals.get(2));
            }
            else {
                newChild1 = new Node<T>(children.get(i).vals.get(0),
                                        children.get(i).children.get(0),
                                        children.get(i).children.get(1));
                newChild2 = new Node<T>(children.get(i).vals.get(2),
                                        children.get(i).children.get(2),
                                        children.get(i).children.get(3));
            }
            children.remove(the4Node);
            children.add(i, newChild2);
            children.add(i, newChild1);
        }
    }
 
    Node<T> root;
    
    public Tree() {
        root = null;
    }
    
    // TwoThreeTree add
    public boolean add(T val) {
        if (root == null) {
            root = new Node<T>(val);
            return true;
        }
        else {
            boolean isNew = root.add(val);
            
            if (root.vals.size() == 3) {
                System.out.println("Split " + val);
                Node<T> left, right;
                if (root.isLeaf()) {
                    left = new Node<T>(root.vals.get(0));
                    right = new Node<T>(root.vals.get(2));
                }
                else {
                    left = new Node<T>(root.vals.get(0), 
                                       root.children.get(0),
                                       root.children.get(1));
                    right = new Node<T>(root.vals.get(2),
                                        root.children.get(2),
                                        root.children.get(3));
                }
                root = new Node<T>(root.vals.get(1), left, right);
            }
            return isNew;
        }
    }
 
    
    public Iterator<T> iterator() {
        List<T> vals = new ArrayList<T>();
        if (root != null) root.getVals(vals);
        return vals.iterator();
    }
    
    
    public static void main(String[ ] args) {
        Tree<Integer> set = new Tree<Integer>();
        System.out.println("add 4 " + set.add(4));
        System.out.println("add 6 " + set.add(6));
        System.out.println("add 13 " + set.add(13));
        System.out.println("add 19 " + set.add(19));
        System.out.println("add 20 " + set.add(20));
        System.out.println("add 34 " + set.add(34));
        System.out.println("add 29 " + set.add(29));
        System.out.println("add 100 " + set.add(100));
        System.out.println("add 130" + set.add(130));
        System.out.println("add 8" + set.add(8));
        System.out.println("add 15" + set.add(15));
        
        System.out.println("Print " + set.root);
        System.out.println();
    }
}