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 OOP principles - comparators, iterables, and encapsulation
• Composition design pattern for utility classes
• How to use binary search to find keys in an ArrayList containing composite objects

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.

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).