A recurring theme in computing is the problem of storage/retrieval/removal of data. One way to store data is to associate it with a key at storage time and use the key for data retrieval and removal. Such a storage is called a dictionary and can be conceptualized as a mapping from set of objects called "keys" to another set of objects called "values". Java provides an abstract class called Dictionary and an interface called Map to model this abstract container structure. (Note: The Dictionary class in Java is deprecated.)
Here we model of the dictionary concept in a fashion analogous to that of a restricted access container (RAC). We view a dictionary as a container of (key, value) pairs.
package genDict;
/**
* Represents a (key, value) pair stored in a dictionary,
* where key is a Comparable.
* @since 03/15/05
*/
public class DictPair<K, V> implements Comparable<DictPair> {
private K _key; // a Comparable
private V _value;
/**
* Initializes this DictPair to a given (key, value) pair.
*/
public DictPair(K key, V value) {
_key = key;
_value = value;
}
/**
* Compares the key of this DictPair against the key of the
* other DictPair.
* @param other a DictPair
*/
public int compareTo(DictPair other) {
return ((Comparable)_key).compareTo(other._key);
}
/**
* Returns the key of this DictPair.
*/
public K getKey() {
return _key;
}
/**
* Returns the value of this DictPair.
*/
public V getValue() {
return _value;
}
/**
* Shows "(", followed by the String representation of the key, followed by
* a ",", followed by the String representation of the associcated value,
* followed by a ")".
*/
public String toString() {
return "(" + _key + "," + _value +
")";
}
}
package genDict;
import java.lang.*;
import genListFW.*;
/*
* Defines an interface for a simple dictionary.
*/
public interface IDictionary<K, V> {
/**
* Clears the contents of the dictionary leaving it empty.
*/
public void clear();
/**
* Returns true if the dictionary is empty and false otherwise.
* Non OO!
* How can we eliminate this check?
*/
public boolean isEmpty();
/**
* Returns true if the dictionary is full and false otherwise.
*/
public boolean isFull();
/**
* Returns an IList of DictPairs corresponding to the entire
* contents of the dictionary.
* @param lf a factory to manufacture IList objects.
*/
public IList< DictPair<K, V> > elements(IListFactory<
DictPair<K, V> > lf);
/**
* Returns the DictPair with the given key. If there is not
* a DictPair with the given key, returns null.
*
* Returns a DictPair rather than the value alone so that
* the user can distinguish between not finding the key and
* finding the pair (key, null).
*/
public DictPair<K, V> lookup(K key);
/**
* Inserts the given key and value. If the given key is already
* in the dictionary, the given value replaces the key's old
* value.
*/
public void insert(K key, V value);
/**
* Removes the DictPair with the given key and returns it.
* If there is not a DictPair with the given key, returns
* null.
*/
public DictPair<K, V> remove(K key);
}
package genDict;
import genLRS.*;
import genListFW.*;
import genListFW.factory.*;
/**
* An implementation of IDictionary using a generic LRStruct to hold the
* DictPairs.
*/
public class DictLRS<K, V> implements IDictionary<K, V> {
/**
* Visitor to check for emptiness.
* Need only one for all DictLRS.
* Non OO!
*/
private static IAlgo<DictPair<K, V>, Boolean, Object> IsEmpty
= new IAlgo<DictPair<K, V>, Boolean, Object>() {
public Boolean emptyCase(LRStruct host, Object... nu) {
return Boolean.TRUE;
}
public Boolean nonEmptyCase(LRStruct host, Object... nu) {
return Boolean.FALSE;
}
};
/*
* A list of DictPairs ordered by key
*/
private LRStruct< DictPair<K, V> > _lrs = new LRStruct< DictPair<K, V> >();
/**
* Clears the contents of the dictionary leaving it empty.
*
* Implemented by replacing the existing LRStruct with a new,
* empty one.
*/
public void clear() {
_lrs = new LRStruct< DictPair<K, V> >();
}
/**
* Returns true if the dictionary is empty and false otherwise.
* Implemented as a visitor to LRStruct.
*/
public boolean isEmpty() {
return _lrs.execute(IsEmpty);
}
/**
* Returns false always.
*/
public boolean isFull() {
return false;
}
/**
* Returns an IList of DictPairs corresponding to the entire
* contents of the dictionary.
*
* Implemented as a visitor to LRStruct.
*/
public IList< DictPair<K, V> > elements(final IListFactory< DictPair<K, V> > lf)
{
return _lrs.execute(new IAlgo< DictPair<K, V>, IList< DictPair<K, V> >, Object
>() {
public IList< DictPair<K, V> > emptyCase(LRStruct<? extends DictPair<K, V> >
host, Object... nu) {
return lf.makeEmptyList();
}
public IList< DictPair<K, V> > nonEmptyCase(LRStruct<?extends DictPair<K, V> >
host, Object... nu) {
return lf.makeNEList(host.getFirst(),
(IList< DictPair<K, V> >)host.getRest().execute(this));
}
});
}
/**
* Returns the DictPair with the given key. If there is not
* a DictPair with the given key, returns null.
*
* Returns a DictPair rather than the value alone so that
* the user can distinguish between not finding the key and
* finding the pair (key, null).
*
* Implemented as a visitor to LRStruct.
*/
public DictPair<K, V> lookup(K key) {
return _lrs.execute(new IAlgo< DictPair<K, V>, DictPair<K, V>, K>() {
public DictPair<K, V> emptyCase(LRStruct<? extends DictPair<K, V> > host, K...
nu) {
return null;
}
public DictPair<K, V> nonEmptyCase(LRStruct<? extends DictPair<K, V> > host,
K... input) {
DictPair<K, V> first = host.getFirst();
int result = ((Comparable)first.getKey()).compareTo(input[0]);
if (result > 0) // host > input
return null;
else if (result == 0) // host == input
return first;
else // host < input
return host.getRest().execute(this, input[0]);
}
}, key);
}
/**
* 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 as a visitor to LRStruct that inserts the key and
* value in order.
*/
public void insert(K key, V value) {
_lrs.execute(new IAlgo<DictPair<K, V>, Object, DictPair >() {
public Object emptyCase(LRStruct<? extends DictPair<K, V> > host, DictPair...
input) {
return ((LRStruct<DictPair<K, V> >)host).insertFront(input[0]);
}
public Object nonEmptyCase(LRStruct<? extends DictPair<K, V> > host, DictPair...
input) {
DictPair<K, V> first = host.getFirst();
int result = first.compareTo(input[0]);
if (result > 0) // host > input
return ((LRStruct<DictPair<K, V> >)host).insertFront(input[0]);
else if (result == 0) // key == input
return ((LRStruct<DictPair<K, V> >)host).setFirst(input[0]);
else // host < input
return host.getRest().execute(this, input[0]);
}
}, new DictPair(key, value));
}
/**
* Removes the DictPair with the given key and returns it.
* If there is not a DictPair with the given key, returns
* null.
*
* Implemented as a visitor to LRStruct.
*/
public DictPair<K, V> remove(K key) {
return _lrs.execute(new IAlgo<
DictPair<K, V>, DictPair<K, V>, K>() {
public
DictPair<K, V> emptyCase(LRStruct<? extends DictPair<K, V> > host, K... nu) {
return null;
}
public
DictPair<K, V> nonEmptyCase(LRStruct<? extends DictPair<K, V> > host, K...
input) {
DictPair<K, V> first = host.getFirst();
int result = ((Comparable)first.getKey()).compareTo(input[0]);
if (result > 0) // host > input
return null;
else if (result == 0) { // host == input
host.removeFront();
return first;
} else // host < input
return host.getRest().execute(this, input[0]);
}
}, key);
}
/**
* Delegates the conversion to the LRStruct toString().
*/
public String toString() {
return _lrs.toString();
}
}
package genDict;
import brs.*;
import brs.visitor.*;
import java.util.*;
import genListFW.*;
import genListFW.factory.*;
/**
* An implementation of IDictionary using a BiTree to hold the
* DictionaryPairs.
* @since 03/17/05.
*/
public class DictBT<K, V> implements IDictionary<K, V> {
/**
* 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... nu) {
return
Boolean.TRUE;
}
public Object nonEmptyCase(BiTree
host, Object... nu) {
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)).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 DictPairs
* are returned in the order defined by Comparable's compareTo().
*
* Implemented as a visitor to BiTree.
*/
public IList< DictPair<K, V> > elements(final IListFactory<
DictPair<K, V> > lf) {
return (IList<DictPair<K, V>>)_bt.execute(new
IVisitor() {
public Object
emptyCase(BiTree host, Object... input) {
return input[0];
}
public Object
nonEmptyCase(BiTree host, Object... input) {
/*
* Construct the partial list consisting of the host and
* its right subtree.
*/
IList< DictPair<K, V> > l = lf.makeNEList((DictPair<K, V>)host.getRootDat(),
(IList< DictPair<K, V> >)host.getRightSubTree().execute(this, input[0]));
/*
* Pass the partial list to the left subtree and return
* the list given by the left subtree.
*/
return host.getLeftSubTree().execute(this, l);
}
}, lf.makeEmptyList());
}
/**
* Returns the DictPair with the given key. If there is not
* a DictPair with the given key, returns null.
*
* Returns a DictPair 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 DictPair<K, V> lookup(K key) {
BiTree result = (BiTree)_bt.execute(_finder, new DictPair(key, null));
return (DictPair<K, V>)result.execute(new IVisitor() {
public Object emptyCase(BiTree host, Object... nu) {
return null;
}
public Object nonEmptyCase(BiTree host, Object... nu) {
return host.getRootDat();
}
});
}
/**
* 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(K key, V value) {
_bt.execute(_inserter, new
DictPair(key, value));
}
/**
* Removes the DictPair with the given key and returns it.
* If there is not a DictPair with the given key, returns
* false.
*
* Implemented using BiTree's visitor BSTDeleter. Thus, we must
* pass (key, null) rather than key.
*/
public DictPair<K, V> remove(K key) {
return (DictPair<K, V>)_bt.execute(_deleter,
new DictPair(key, null));
}
/**
* Delegates the conversion to the BiTree toString().
*/
public String toString() {
return _bt.toString();
}
}