Maps/UnsortedArrayMap

Notes

The unsorted array map is an implementation of a map that uses an unsorted array list to store the map items.

This map has terrible performance, and is purely implemented for illustrative reasons.

Procedure

Notes for implementation procedure in Java.

Start by defining, on paper, what the map ADT is going to look like. See Maps/ADT.

Define the Map interface class that establishes the basic PUBLIC functionality all Map objects must provide.

Define an AbstractMap abstract class that creates any utility classes (item or position classes, iterators, iterables) and any additional fields or methods (particularly PROTECTED) that should be implemented.

Define the UnsortedArrayMap class, the concrete implementation of the abstract map that utilizes an array list to store items in the map.

Abstract map implementation notes

The process of defining the abstract map:

• Needed to define a map item wrapper class, of course
• This is designed to take a K,V key value pair
• Also need to define four more classes:
• Two Iterators and two Iterables

Iterators vs Iterables - ?

• Map key Iterator object
• Map value Iterator object
• Map key Iterable object (?) - thought I understood this, but maybe not?
• Map value Iterable object (?)
• The Iterator objects are like mini-scanners.
• The Iterable objects just have an iterator() method and are what are actually returned.

entrySet:

• Note that the key and value sets use the entrySet method
• We aren't defining entrySet, just using it
• entrySet must be defined in our concrete class
• This means we have three total Iterators and three total Iterables

More iterators vs iterables:

• Iterable just says, I return an Iterator. it is part of the core language.
• Iterator has to be defined for each container.

Exceptions:

• NoSuchElementException
• UnsupportedOperationException
• Don't forget to check for size!
• Especially if you are not wraapping someone else's iterator

Ordering of class declaration and undeclared class declarations

• I could not use MapItem class undefined in the Map interface (most generic of all)
• MapItem class was actually protected and lived in AbstractMap class
• Therefore, we had to hold off declaring an abstract MapItem iterator until the AbstractMap class, not the Map interface

Code

Git link

The unsorted array implementation of a map is at git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/hash/UnsortedArrayMap.java

This implements the Map ADT - see Maps/ADT.

Java implementation

The class below, as with most classes, is organized as follows:

• Start with main method to illustrate the usage of the class, and test its functionality
• Include any utility classes that this concrete class will use (in particular, a way to iterate over key-value pairs)
• The class implementation (the array list)

The code for this concrete implementation starts with a main method that briefly shows how to use this:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;


/**
 * Unsorted Array Map.
 *
 * A concrete implementation of the map type that stores
 * key-value items in an arraylist. 
 *
 * This class is terribly inefficient, requiring O(N) lookups each time.
 */
public class UnsortedArrayMap<K,V> extends AbstractMap<K,V> {

	public static void main(String[] args) { 
		UnsortedArrayMap<String,String> m = new UnsortedArrayMap<>();
		m.put("WAT","monkey");
		m.put("WHO","tree");
		m.put("WHY","sticks");
		System.out.println(m.size());
		System.out.println(m.get("WHO"));
	}