Package dsa.lab04.solutions

Class ArrayMap<Key,Value>

java.lang.Object

dsa.lab04.solutions.ArrayMap<Key,Value>

Type Parameters:

Key - the key type

Value - the value type

All Implemented Interfaces:

Container<MapItem<Key,Value>>, Map<Key,Value>, Iterable<MapItem<Key,Value>>

public class ArrayMap<Key,Value>
extends Object
implements Map<Key,Value>

An (unsorted) array map.

A map implemented using a dynamic array of key-value items.

find(Key), insert(dsa.lab04.base.MapItem<Key, Value>) and remove(Key) are all O(n), where n is the size.

Constructor Summary

Constructors

Constructor	Description
ArrayMap()	Construct an empty array map.
ArrayMap(MapItem<Key,Value>... items)	Construct an array map containing the given items.
ArrayMap(Iterable<MapItem<Key,Value>> items)	Construct an array map containing the given items.
ArrayMap(Iterable<MapItem<Key,Value>> items, int size)	Construct an array map containing the given items more efficiently than ArrayMap(Iterable).

Method Summary

Modifier and Type	Method	Description
MapItem<Key,Value>	find(Key key)	Find the item with the given key.
void	insert(MapItem<Key,Value> item)	Insert the given item.
Iterable<MapItem<Key,Value>>	items()	Get an iterable that yields each item once.
MapItem<Key,Value>	remove(Key key)	Remove and return the item with the given key.
int	size()	Get the number of contained items.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface dsa.lab02.base.Container

contains, isEmpty, iterator

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from interface dsa.lab04.base.Map

containsKey, containsValue, get, insert, keys, values

Constructor Details

ArrayMap

public ArrayMap()

Construct an empty array map.

ArrayMap

public ArrayMap(Iterable<MapItem<Key,Value>> items)

Construct an array map containing the given items.

Parameters:

items - the items

ArrayMap

public ArrayMap(Iterable<MapItem<Key,Value>> items,
 int size)
         throws IllegalArgumentException

Construct an array map containing the given items more efficiently than ArrayMap(Iterable).

Parameters:

items - the items

size - the number of items

Throws:

IllegalArgumentException - if size != n (where n is items's size)

ArrayMap

@SafeVarargs
public ArrayMap(MapItem<Key,Value>... items)

Construct an array map containing the given items.

Parameters:

items - the items

Method Details

size

public int size()

Description copied from interface: Container

Get the number of contained items.

Specified by:

size in interface Container<Key>

Returns:

the size

find

public MapItem<Key,Value> find(Key key)
                        throws NoSuchElementException

Description copied from interface: Map

Find the item with the given key.

Specified by:

find in interface Map<Key,Value>

Parameters:

key - the item's key

Returns:

the item

Throws:

NoSuchElementException - if no item has key key

insert

public void insert(MapItem<Key,Value> item)

Description copied from interface: Map

Insert the given item.

If there's already an item with the same key, that item is replaced with this one.

This means that if the key was not already contained, the size is incremented, otherwise it isn't.

Specified by:

insert in interface Map<Key,Value>

Parameters:

item - the item

remove

public MapItem<Key,Value> remove(Key key)
                          throws NoSuchElementException

Description copied from interface: Map

Remove and return the item with the given key.

Decrements the size (assuming the item was actually in the map).

Specified by:

remove in interface Map<Key,Value>

Parameters:

key - the item's key

Returns:

the item

Throws:

NoSuchElementException - if key is not contained

items

public Iterable<MapItem<Key,Value>> items()

Description copied from interface: Container

Get an iterable that yields each item once.

Specified by:

items in interface Container<Key>

Returns:

an iterable over the items