import java.util.*;

public class MNode<E extends Comparable<E>> {
    private MTree<E> tree;
    private MNode<E> parent;
    private MNode<E> right;
    private ArrayList <Pair<E>> data;
    private int m; //capacity of the MNode
    
    public MNode(int m,MTree<E> tree){
	this.tree = tree;
	parent    = null;
	right     = null;
	this.m    = m;
	data      = new ArrayList<Pair<E>>(m+1); // one extra for overflow
    }
    
    public int getM(){return m;}
    public int size(){return data.size();}
    public ArrayList<Pair<E>> getData(){return data;}
    public Pair<E> getData(int i){return data.get(i);}
    public MNode<E> getParent(){return parent;}
    private void setParent(MNode<E> parent){this.parent = parent;}
    public MNode<E> getRight(){return right;}
    private void setRight(MNode<E> right){this.right = right;}

    private MNode<E> find(E e){
	if (isLeaf()) {System.out.println("found: "+ this); return this;}
	MNode<E> node = null;
	for (int i=0;i<size() && node == null;i++)
	    if (e.compareTo(data.get(i).getValue()) < 0) node =  data.get(i).getLeft().find(e);
	if (node == null) node = right.find(e);
	return node;
    }
    
    public void add(E e){
	Pair<E> p = new Pair<E>(e,null);
	if (size() == 0) data.add(p); else find(e).add(p);
    }

    private void add(Pair<E> p){
	System.out.print("add("+ p +") + ");
	for (Pair<E> x : data) System.out.print(x + " "); System.out.print(" -> ");
	int k = 0; // insertion point
	while(k < size() && data.get(k).getValue().compareTo(p.getValue())<0) k++;
	if (k < size()) data.add(k,p); else data.add(p);
	for (Pair<E> x : data) System.out.print(x + " "); System.out.println();
	if (size() == m) split();
    }

    private void add(Pair<E> p,MNode<E> node){
	System.out.print("add("+ p +") + ");
	for (Pair<E> x : data) System.out.print(x + " "); System.out.print(" -> ");
	int k = 0; // insertion point
	while(k < size() && data.get(k).getValue().compareTo(p.getValue())<0) k++;
	if (k < size()) {data.add(k,p);data.get(k+1).setLeft(node);} else {data.add(p); right = node;}
	for (Pair<E> x : data) System.out.print(x + " "); System.out.println();
	if (size() == m) split();
    }
    

    private void split() {
	System.out.println("Split: "+ this);
	MNode<E> u = parent;
	if (u == null){u = new MNode<E>(m,tree); tree.setRoot(u);}
	MNode<E> v = this;
	MNode<E> w = new MNode<E>(m,tree); // create a new node w
	Pair<E>  p1 = data.get(m-2);       // get second last element
	Pair<E>  p2 = data.get(m-1);       // get last pair in data
	w.add(p2);                         // overflow last pair into new node;
	w.setRight(v.getRight());
	w.setParent(u);                    // w's parent is u
	v.getData().remove(m-1);           // remove overflow element from v (this)
        v.getData().remove(m-2);           // remove second last element from v (this)
	v.setRight(p1.getLeft());          // p1 is now removed
	p1.setLeft(v);
	u.add(p1,w);
    }	

    public boolean isLeaf(){return data.get(0).getLeft() == null;}

    public String toString(){
	String s = "(";
	for (Pair<E> p : data){
	    if (p.getLeft() != null)s = s + p.getLeft();
	    s = s + p.getValue() + ",";
	}
	if (right != null) s = s + right;
	s = s + ")";
	return s;
    }
}