CISC Tree Map

UML Class Diagram:

For this assignment, you will create a tree map using a binary search tree as its underlying data structure. The entries in the map will also serve as the nodes in the tree. The nodes will be ordered by the entry keys. Our tree map implements Java's "Map" interface.

CiscTreeMap

root : CiscEntry< K, V >

The entry/node at the root of the underlying binary search tree.

size : int

The number of elements in the CiscTreeMap.

retValue : V

A helper instance variable to store the appropriate return value for the put and remove methods. This allows the put and remove recursive helper methods to return CiscEntry objects so that the traversed tree branch is rebuilt as the recursion unwinds.

size() : int

The size method should return the number of elements in the map.

isEmpty() : boolean

The isEmtpy method should return true if map is empty, false otherwise.

clear() : void

This method should effectively empty the map of all entries.

containsKey(key : Object) : boolean

With the help of its recursive helper method, this method should return true if the provided key is present in the map, false otherwise. Your implementation should not evaluate more entries/nodes than necessary. This implementation will be similar to one in our binary search tree implementation.

containsValue(value : Object) : boolean

This method should return true if the provided value is present in the map, false otherwise. For simplicity's sake, it may use the values method.

get(key : Object) : V

With the help of its recursive helper method, this method should return the value associated with the provided key in the map. If the key is not present in the map, it should return null. Your implementation should not call the contains method and should not evaluate more entries/nodes than necessary.

put(key : Object, value : Object) : V

With the help of its recursive helper method, if the provided key is not already present in the map, this method should add a CiscEntry with the provided key and value to the appropriate location in the underlying binary search tree and return the provided value. If the key is already present, this method should replace the value associated with that key in the map and return the old value. Your implementation should not call the contains method. This implementation will be similar to one in our binary search tree implementation.

remove(key : Object) : V

With the help of its recursive helper method, this method should remove the entry/node found in the map with a key matching the parameter and return the value associated with that key. If the key is not present, this method should return null. This implementation should (in some circumstances) call the getMaxEntry recursive private helper method to find the entry containing the maximum key in a subtree to use when replacing a removed key and value. This implementation will be similar to one in our binary search tree implementation.

putAll(m : Map< ? extends K, ? extends V) : void

This method should add all entries in the provided map to this map. Your implementation may repeatedly call the put method.

keySet() : Set< K >

This method should create a new tree set, add all keys in the map to that tree set, and return that tree set. Your implementation may call the entrySet method.

values() : Collection< V >

This method should create a new ArrayList, add all values in the map (in any order) to that list, and return that list. Your implementation may call the entrySet method.

entrySet() : Set< Map.Entry< K, V >>

This method should create and return an instance of CiscEntrySet.

CiscEntrySet

This class should be private (CiscTreeMap clients don't need to create instances of it directly) and non-static (it needs to access CiscTreeMap internals).

size() : int

The size method should return the number of entries in the set.

iterator() : Iterator< Map.Entry< K, V>>

This method should create and return an instance of CiscEntrySetIterator.

CiscEntrySetIterator

This class should be private and non-static. Its implementation should be similar to the iterator implementation in our binary search tree.

stack : Stack< CiscEntry< K, V>>

The stack instance variable should be used to help keep track of unvisited entries/nodes in the tree. Its usage will be described in the descriptions for the Iterator< E > constructor and methods.

CiscEntrySetIterator(node : CiscEntry< K, V >)

Constructs a CiscEntrySetIterator to iterate over a CiscTreeMap instance using an in-order traversal. Creates a new stack and pushes its node parameter onto it, followed by all left children accessible from the parameter, resulting in the node containing the smallest key at the top of the stack.

hasNext() : boolean

Returns true if the iterator has yet to return all entries in the map, recognizable by a non-empty stack.

next() : CiscEntry< K, V >

Returns the next element, in order, in the map. The node at the top of the stack contains the value to return. If the node has right children, then more nodes need to be pushed onto the stack.

CiscEntry

key : K

This entry's/node's key.

value : V

This entry's/node's value.

left : CiscEntry< K, V>

A reference to the entry's/node's left child in the binary search tree (if it exists).

right : CiscEntry< K, V>

A reference to the entry's/node's right child in the binary search tree (if it exists).

CiscEntry(key : K, value : V)

Constructs an entry/node with the provided key and value with no children.

getKey() : K

Returns a reference to this entry's/node's key.

getValue() : V

Returns a reference to this entry's/node's value.

setValue(value : V) : V

Assigns this entry's/node's value to the provided value, and returns this entry's/node's previous value (which may have been null).