Data Structures Homework 5, Fall 1999

Due: Fri, Oct 29, 12 PM using turnin

Absolutely no late submissions accepted since solutions will be posted soon after the deadline.

In this project, you will implement a locator dictionary ADT using AVL trees. You will then modify your checked list class in the puzzle to use the AVL tree ADT. Construct a concrete class, AVLDictionary, which implements the following interface:

public interface LocatorDictionary {
 public int size();
 public boolean isEmpty();
 public Locator find(Object k); // Return locator for item (k',e) w/ k=k'
 public Locator insert(Object k, Object o); // Insert (k,o), get back locator
 public Object remove(Locator l); // Remove item at locator l
 public Object replaceKey(Locator l, Object k); // Replace key at locator l
 public Object replaceElement(Locator l, Object k); // Replace element at locator l
}

Your class should have a constructor that accepts a Comparator object and builds an initially-empty AVL tree.

Your locator should support the following interface:

public interface Locator {
 public Object key(); // Return the key for this locator
 public Object element(); // Return the element for this locator
 public Object containter(); // Return the container this locator is in
}

You will need to implement this interface with a concrete class with a name like AVLLocator.

Some students have asked to use the Position interface instead of the Locator interface. This is okay with me as well. Using the Locator Interface will require you to replace all instances of Position with Locator in the files that you may be reusing from hw4. If you use the Position class, this is not necessary. Notice that the Position and Locator interfaces are almost identical, except for a key method that can be called from the element class if you use the Position interface.

The comparator interface is:

public interface Comparator {

   boolean isLess(Object a, Object b);
   boolean isLessOrEqual(Object a, Object b);
   boolean areEqual(Object a, Object b);
   boolean isGreater(Object a, Object b);
   boolean isGreaterOrEqual(Object a, Object b);

}

Use the rest of the classes from the solution to the previous homework for implementing and testing solution to this homework.

The board itself is a key for searching in the AVL tree.. you can convert the board into a string and use the following comparators. The comparator interface is:

public interface Comparator {

   boolean isLessThan(Object a, Object b);
   boolean isLessThanOrEqualTo(Object a, Object b);
   boolean isEqualTo(Object a, Object b);
   boolean isGreaterThan(Object a, Object b);
   boolean isGreaterThanOrEqualTo(Object a, Object b);
   boolean isComparable(Object a);

}

and the string comparator class is

public class StringComparator implements Comparator {

   boolean isLessThan(Object a, Object b) {
      return ((String)b).compareTo((String)a) < 0;
   }

   boolean isLessThanOrEqualTo(Object a, Object b) {
      return ((String)b).compareTo((String)a) <= 0;
   }

   boolean isEqualTo(Object a, Object b) {
      return ((String)b).compareTo((String)a) == 0;
   }

   boolean isGreaterThan(Object a, Object b) {
      return ((String)b).compareTo((String)a) > 0;
   }

   boolean isGreaterThanOrEqualTo(Object a, Object b) {
      return ((String)b).compareTo((String)a) >= 0;
   }
   boolean isComparable(Object a) {
	if(a == null)
	  return false;
	else {
		try {
			String i1 = (String) a;
		} catch(ClassCastException e) {
			return false;
		}
	}
	return true;
   }
}