Maps/OOP

Notes

This page describes the application of object oriented principles to the Maps / Dictionaries data type.

• Start by describing the inheritance diagram
• Then describe the use of language features - comparators, iterables
• OOP principles like enapsulation, composition design pattern, utility classes
• How to use binary search to find keys in an ArrayList containing composite objects using a custom Comparator object

Inheritance Diagram

The top-level base class is the Map interface class, which defines public behaviors that Map objects must expose.

The next level down is the Abstract Map class, which defines a few private behaviors and some utility classes.

The SortedArrayMap and UnsortedArrayMap share quite a bit of code and should probably inherit from an ArrayMap base class, but they do not. They fulfill all the requirements of the Maps/ADT Maps abstract data type.

Map interface

The Map interface is an ADT defining the public methods Map types must expose. Here is what it does:

• Define abstract methods for size, isEmpty, get, put, remove, key/value set iterators

Link on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/hash/Map.java

Here it is in its entirety:

import java.util.Iterator;

/** 
 * Formal Map ADT Interface.
 *
 * This defines an interface for any map types.
 */
public interface Map<K,V> {

	/** Get the size of the map. */
	int size();

	/** Returns true of there are no elements left in the map. */
	boolean isEmpty();

	/** Get the item corresponding to key. */
	V get(K key);

	/** Put the key value pair into the map. */
	void put(K key, V value);

	/** Remove the item corresponding to key k into the map. */
	V remove(K key);


	// Note: we cannot define entrySet to get iterator over items,
	// because we do not have definition of Items class.


	/** keySet is an iterable wrapping entrySet. */
	Iterable<K> keySet();

	/** valueSet is an iterable wrapping entrySet. */
	Iterable<V> valueSet();
}

AbstractMap abstract class

The AbstractMap class does a few things:

• Defines a MapItem object that allows for arranging information by key
• Defines a KeyIterator class that wraps the keys in the key-item ArrayList
• Defines a KeyIterable class that wraps the KeyIterator class
• Defines a ValueIterator class that wraps the values in the value-item ArrayList
• Defines a ValueIterable class that wraps the ValueIterator class
• Provides an abstract method to generate an Iterable over all key-value items
• Provides a concrete method to generate an iterator over the key set (returns the KeyIterable object defined above)
• Provides a concrete method to generate an iterator over the value set (returns the ValueIterable object defined above)

Array map class

The base behavior here would be, defining the private field (ArrayList) that stores the key-value items, and define some of the other behavior that follows from that concrete implementation (size, iterators, etc.)

Unsorted

To implement the map using an unsorted array of key-value pairs, the add method becomes very simple - we just stick the value at the end. The remove method is only slightly more complicated - we perform a sequential search to find the element of interest, remove it, and move the last item in the array to the open slot.

Sorted

To implement the map using a sorted array of key-value pairs, we need to be able to translate between the type the user passes (the key type) and the type of objects in the array (key-value item type). Once we have a way of directly comparing the key and the key-value items, we can use the binary search function from the Collections class to find where in the ArrayList the key is located (or where it should be inserted, if it is not already in the list).