package jdsl.dictionary;

import jdsl.Key;
import jdsl.Decorable;
import jdsl.DecorableKeyManager;

import jdsl.Locator;
import jdsl.InvalidLocatorException;

import jdsl.Position;
import jdsl.InvalidPositionException;

import jdsl.Comparator;
import jdsl.InvalidKeyException;

import jdsl.tree.BinaryTree;
import jdsl.tree.Searchable;


public class Dictionary {

    static final Locator NO_SUCH_KEY = new Locator( ) {

	public Object element( ) {
	    throw new InvalidLocatorException("Invalid Locator");
	}

	public Object key( ) {
	    throw new InvalidLocatorException("Invalid Locator");
	}
    };


    class Loc implements Locator {
	
	Position   position;

	Object     element;
	Comparable key;

	public Object element( ) {
	    return element;
	}

	public Object key( ) {
	    return key;
	}


	Loc(Comparable key     , 
	    Object     element , 
	    Position   position) {
	    
	    this.key      = key;
	    this.element  = element;
	    this.position = position;
	}
	    
    }




    Key locator_key;

    private final Loc getLocator(Position pos) {
	try {
	    return (Loc) ((Decorable) pos).getComponent(locator_key);
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not a decorable Position");
	}
    }

    private final void setLocator(Position pos, Loc locator) {
	try {
	    ((Decorable) pos).insertComponent(locator_key, locator);
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not a decorable Position");
	}
    }


    BinaryTree tree;

    public Dictionary(BinaryTree tree) {
	this.tree        = tree;
	this.locator_key = ((DecorableKeyManager) tree).requestKey( );
	
    }

    
    public Locator insertItem(Comparable key, Object item) {

	Position trapse = ((Searchable) tree).findExternal(key);
	Position parent = tree.expandExternal(trapse);

	Loc locator     = new Loc(key   ,
				  item  ,
				  parent);
	
	// store key, _not_ locator
	tree.replace(parent, key);
	setLocator(parent, locator);

	return locator;
    }
    
    public Locator findItem(Comparable key) {
	Position trapse = ((Searchable) tree).findFirst(key);

	return (tree.isExternal(trapse)) ? 
	    NO_SUCH_KEY       : 
	    getLocator(trapse);
    }

    public Object removeItem(Comparable key) {
	Position trapse  = ((Searchable) tree).findFirst(key);
	Loc      locator = getLocator(trapse);

	if      (tree.isExternal(tree.leftChild( trapse)))
	    tree.removeAboveExternal(tree.leftChild( trapse));
	else if (tree.isExternal(tree.rightChild(trapse)))
	    tree.removeAboveExternal(tree.rightChild(trapse));
	else {

	    Position parent = tree.rightChild(trapse);
	    Position child  = tree.leftChild(parent);

	    while (tree.isInternal(child)) {
		parent = child;
		child  = tree.leftChild(child);
	    }

	    tree.swap(trapse, parent);

	    Loc two = getLocator(parent);
	    setLocator(trapse, two);

	    tree.removeAboveExternal(child);
	}

	return locator.element;
    }
}