Class Dictionary

java.lang.Object
  |
  +--Dictionary

public class Dictionary

extends java.lang.Object

implements java.lang.Cloneable

This class implements the dictionary ADT using a singly linked list. The dictionary ADT consists of a set of ordered pairs (K,I). The key K is unique but the information portion I need not be. This implementation stores K and I as java Strings. This implementation attempts to improve on the average case run-time that would normally be associated with a linked implementation. It uses a heuristic-- a rule that results in behavior that may not be exactly predictable, but which there is reason to believe will be good in general. The heuristic employed is called the Move-to-Front Heuristic: after each successful search, move the item that was sought to the front of the list.

Constructor Summary

Dictionary()
The constructor initializes an empty dictionary.

Method Summary

java.lang.Object	clone() This method makes a copy of the dictionary and returns a reference to the user of the class.
boolean	delete(SetElement x) This method deletes the ordered pair (K,I) represented by the parameter x.
void	insert(SetElement x) This method inserts the new element x (or, replaces an existing one) in the dictionary.
boolean	isEmpty() This method returns true if the dictionary is empty and false otherwise.
SetElement	lookUp(SetElement x) This method searches the dictionary for the key K found in the parameter x.
static void	main(java.lang.String[] a) Test drive the class Dictionary.
java.lang.String	toString() This method returns a Java String representing the current state of the dictionary object.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Dictionary

public Dictionary()

The constructor initializes an empty dictionary.

Method Detail

isEmpty

public boolean isEmpty()

This method returns true if the dictionary is empty and false otherwise.

delete

public boolean delete(SetElement x)

This method deletes the ordered pair (K,I) represented by the parameter x. If the key K is not found in the dictionary then delete returns false. Otherwise, it removes the (K,I) pair and returns true.

insert

public void insert(SetElement x)

This method inserts the new element x (or, replaces an existing one) in the dictionary. Search to see if the set element represented by x = (K,I) already exists in the dictionary. If K is present in the list, replace the information portion I with the information part of x. The old information associated with the key K is lost. If K is not present in the list, create a new node for the (K,I) pair and place this new node at the front of the list. The method takes care to first make a Java clone of its parameter x. This prevents the class user from breaking encapsulation. If we made the mistake of simply storing the value of x (which is pointing to the object holding (K,I)) in the list then the user would have access to it (afterall, the user gave us x in the first place). In any case, the accessed node is moved to the front of the list.

lookUp

public SetElement lookUp(SetElement x)

This method searches the dictionary for the key K found in the parameter x. Search to see if the set element represented by x = already exists in the dictionary. If K is in the dictionary then return a reference to a new(K,I) pair with the key portion K and data portion I identical to that which was found in the list. This requires the use of Java's cloning mechanism so that encapsulation is not broken. If we made the mistake of returning a reference to the existing node then the class user could directly access the node. That would render our move-to-front heuristic useless and would prevent us from making future changes to this code without running the risk of breaking client code. If the key K is not in the set return null. If the key K is in the set, move the node to the front of the list.

clone

public java.lang.Object clone()

This method makes a copy of the dictionary and returns a reference to the user of the class.

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

This method returns a Java String representing the current state of the dictionary object.

Overrides:

toString in class java.lang.Object

main

public static void main(java.lang.String[] a)

Test drive the class Dictionary.