package dict;

import brs.*;
import brs.visitor.*;
import java.util.*;
import listFW.*;
import listFW.factory.*;

/**
 * An implementation of IDictionary using a BiTree to hold the
 * DictionaryPairs.
 * @since 04/14/2004 fix lookup bug.
 */
public class DictBT implements IDictionary {

    /**
     * Visitor to check for emptiness.
     * Need only one for all DictBT.
     * Non OO!
     */
    private static IVisitor IsEmpty = new IVisitor() {
        public Object emptyCase(BiTree host, Object input) {
            return Boolean.TRUE;
        }

        public Object nonEmptyCase(BiTree host, Object input) {
            return Boolean.FALSE;
        }
    };

    /*
     * A binary tree of DictionaryPairs ordered by key
     */
    private BiTree _bt = new BiTree();

    /*
     * A trivial comparator for use by the binary search tree (BST)
     * visitors
     */
    private Comparator _comparator = new Comparator() {
        public int compare(Object x, Object y) {
            return ((Comparable)x).compareTo(y);
        }
    };

    /*
     * The visitors for basic binary search tree (BST) operations
     */
    private IVisitor _finder = new BSTFinder(_comparator);
    private IVisitor _inserter = new BSTInserter(_comparator);
    private IVisitor _deleter = new BSTDeleter(_comparator);

    /**
     * Clears the contents of the dictionary leaving it empty.
     *
     * Implemented by replacing the existing BiTree with a new,
     * empty one.
     */
    public void clear() {
        _bt = new BiTree();
    }

    /**
     * Returns true if the dictionary is empty and false otherwise.
     *
     * Implemented as a visitor to BiTree.
     */
    public boolean isEmpty() {
        return ((Boolean)_bt.execute(IsEmpty, null)).booleanValue();
    }

    /**
     * Returns false always.
     */
    public boolean isFull() {
        return false;
    }

    /**
     * Returns an IList of DictionaryPairs corresponding to the entire
     * contents of the dictionary.  Like DictLRS, the DictionaryPairs
     * are returned in the order defined by Comparable's compareTo().
     *
     * Implemented as a visitor to BiTree.
     */
    public IList elements(final IListFactory lf) {
        return (IList)_bt.execute(new IVisitor() {
            public Object emptyCase(BiTree host, Object input) {
                return input;
            }

            public Object nonEmptyCase(BiTree host, Object input) {
                /*
                 * Construct the partial list consisting of the host and
                 * its right subtree.
                 */
                IList l = lf.makeNEList(host.getRootDat(),
                                        (IList)host.getRightSubTree().execute(this, input));

                /*
                 * Pass the partial list to the left subtree and return
                 * the list given by the left subtree.
                 */
                return (IList)host.getLeftSubTree().execute(this, l);
            }
        }, lf.makeEmptyList());
    }

    /**
     * Returns the DictionaryPair with the given key.  If there is not
     * a DictionaryPair with the given key, returns null.
     *
     * Returns a DictionaryPair rather than the value alone so that
     * the user can distinguish between not finding the key and
     * finding the pair (key, null).
     *
     * Implemented using BiTree's visitor BSTFinder.  Thus, we must
     * pass (key, null) rather than key.  (What would happen if we didn't?)
     */
    public DictionaryPair lookup(Comparable key) {
        BiTree result = (BiTree)_bt.execute(_finder, new DictionaryPair(key, null));
        return (DictionaryPair)result.execute(new IVisitor() {
            public Object emptyCase(BiTree host, Object inp) {
                return null;
            }
            public Object nonEmptyCase(BiTree host, Object inp) {
                return host.getRootDat();
            }
        },null);
    }

    /**
     * Inserts the given key and value.  If the given key is already
     * in the dictionary, the given value replaces the key's old
     * value.
     *
     * Implemented using BiTree's visitor BSTInserter.
     */
    public void insert(Comparable key, Object value) {
        _bt.execute(_inserter, new DictionaryPair(key, value));
    }

    /**
     * Removes the DictionaryPair with the given key and returns it.
     * If there is not a DictionaryPair with the given key, returns
     * null.
     *
     * Implemented using BiTree's visitor BSTDeleter.  Thus, we must
     * pass (key, null) rather than key.
     */
    public DictionaryPair remove(Comparable key) {
        return (DictionaryPair)_bt.execute(_deleter,
                                           new DictionaryPair(key, null));
    }

    /**
     * Delegates the conversion to the BiTree toString().
     */
    public String toString() {
        return _bt.toString();
    }
}