import brs.*;
import brs.visitor.*;
import ordering.*;

/**
* A concrete IDictionary immplemented as a binary search tree.
* @author D. X. Nguyen - Copyright 2000 - All rights reserved.
*/
public class BSTDictionary implements IDictionary {
    private BiTree _bst;
    private IVisitor _inserter;
    private IVisitor _deleter;
    private IVisitor _finder;

    /**
     * Key/Value Pair to be stored in dictionary.
     */
    private static class KeyValPair  {
        public Object key;
        public Object val;

        public KeyValPair (Object key, Object val) {
             this.key = key;
             this.val = val;
        }

        public String toString ()  {
            return "(" + key + "," + val + ")";
        }
    }

    /**
     * Ordering for KeyValPair.
     */
    private static class OrderKeyVal extends AOrder  {
        private AOrder _orderKey;

        private OrderKeyVal(AOrder orderKey)  {
            _orderKey = orderKey;
        }

        public boolean lt(Object x, Object y) {
            return _orderKey.lt(((KeyValPair)x).key,  ((KeyValPair)y).key);
        }

        public boolean eq (Object x, Object y)  {
            return _orderKey.eq (((KeyValPair)x).key,  ((KeyValPair)y).key);
        }
    }

    public BSTDictionary(AOrder order)  {
        _bst = new BiTree ();
        AOrder ordKV = new OrderKeyVal (order);
        _inserter = new BSTInserter (ordKV );
        _deleter = new BSTDeleter (ordKV);
        _finder = new BSTFinder (ordKV);
    }

    public void store (Object key, Object val) {
        _bst.execute (_inserter, new KeyValPair (key, val));
    }

    /**
    * Returns the object associated with key if key is in this dictionary,
    * null otherwise.
    */
    public Object retrieve(Object key) {
        BiTree bt = (BiTree)_bst.execute(_finder, new KeyValPair (key, null));
        if (null == bt) {
            return null;
        }
        return ((KeyValPair)bt.getRootDat()).val;
    }

    /**
    * returns the object associated with key if key is in this dictionary,
    * null otherwise.
    * afterwards, calling retrieve (key) will return null.
     */
    public Object remove (Object key) {
        BiTree bt = (BiTree)_bst.execute(_finder, new KeyValPair (key, null));
        if (null == bt) {
            return null;
        }
        KeyValPair result = (KeyValPair)bt.getRootDat();
        bt.execute(_deleter, result);
        return result.val;
    }

    public String toString () {
        return _bst.toString();
    }
}