Revision as of 03:52, 26 June 2017

Notes

Procedure

Following the Maps/UnsortedArrayMap implementation mainly, here.

While we could have a general parent class, ArrayMap, what we do instead is to repeat our implementation of the ItemIterator utility class. A little bit of copy-pasta, but that's okay.

Next, we define the class itself, which still uses an ArrayList object to store data, but stores it in a sorted order. This makes insertions O(N) or O(log N), depending on the algorithm used.

Abstract map implementation notes

Code

Git link

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

This implements the Map ADT - see Maps/ADT.

Java implementation

Flags

@@ Line 2: / Line 2: @@
 ==Procedure==
+Following the [[Maps/UnsortedArrayMap]] implementation mainly, here.
+While we could have a general parent class, ArrayMap, what we do instead is to repeat our implementation of the ItemIterator utility class. A little bit of copy-pasta, but that's okay.
+Next, we define the class itself, which still uses an ArrayList object to store data, but stores it in a sorted order. This makes insertions O(N) or O(log N), depending on the algorithm used.
 ==Abstract map implementation notes==

Maps/SortedArrayMap: Difference between revisions

From charlesreid1