Package dsa.lab05.solutions

Class SortedArrayMap<Key extends Comparable<Key>,Value>

java.lang.Object

dsa.lab05.solutions.SortedArrayMap<Key,Value>

Type Parameters:

Key - the key type

Value - the value type

All Implemented Interfaces:

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

public class SortedArrayMap<Key extends Comparable<Key>,Value>
extends Object
implements OrderedMap<Key,Value>

A sorted array map.

Constructor Summary

Constructors

Constructor	Description
SortedArrayMap()	Construct an empty sorted array map.
SortedArrayMap(MapItem<Key,Value>... items)	Construct a sorted array map containing the given items.
SortedArrayMap(Iterable<MapItem<Key,Value>> items)	Construct a sorted array map containing the given items.
SortedArrayMap(Iterable<MapItem<Key,Value>> items, int size)	Construct a sorted array map containing the given items more efficiently than SortedArrayMap(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 a forward iterable that yields each item once.
MapItem<Key,Value>	max()	Get the item with the greatest key.
MapItem<Key,Value>	min()	Get the item with the least key.
MapItem<Key,Value>	next(Key key)	Get the item that would be the successor of one with the given key.
MapItem<Key,Value>	previous(Key key)	Get the item that would be the predecessor of one with the given key.
MapItem<Key,Value>	remove(Key key)	Remove and return the item with the given key.
Iterable<MapItem<Key,Value>>	reversed()	Get a reverse iterable that yields each item once.
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, values

Methods inherited from interface dsa.lab05.base.OrderedMap

keys, reversedKeys

Constructor Details

SortedArrayMap

public SortedArrayMap()

Construct an empty sorted array map.

SortedArrayMap

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

Construct a sorted array map containing the given items.

Parameters:

items - the items

SortedArrayMap

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

Construct a sorted array map containing the given items more efficiently than SortedArrayMap(Iterable).

Parameters:

items - the items

size - the number of items

Throws:

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

SortedArrayMap

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

Construct a sorted 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 extends Comparable<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 extends Comparable<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 extends Comparable<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 extends Comparable<Key>,Value>

Parameters:

key - the item's key

Returns:

the item

Throws:

NoSuchElementException - if key is not contained

previous

public MapItem<Key,Value> previous(Key key)

Description copied from interface: OrderedMap

Get the item that would be the predecessor of one with the given key.

The map may or may not contain an item with the given key.

Specified by:

previous in interface OrderedMap<Key extends Comparable<Key>,Value>

Parameters:

key - a key

Returns:

the previous item (by key), or null if there is none

next

public MapItem<Key,Value> next(Key key)

Description copied from interface: OrderedMap

Get the item that would be the successor of one with the given key.

The map may or may not contain an item with the given key.

Specified by:

next in interface OrderedMap<Key extends Comparable<Key>,Value>

Parameters:

key - a key

Returns:

the next item (by key), or null if there is none

min

public MapItem<Key,Value> min()

Description copied from interface: OrderedMap

Get the item with the least key.

Specified by:

min in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

the minimum item (by key), or null if there is none

max

public MapItem<Key,Value> max()

Description copied from interface: OrderedMap

Get the item with the greatest key.

Specified by:

max in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

the maximum item (by key), or null if there is none

items

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

Description copied from interface: OrderedMap

Get a forward iterable that yields each item once.

The items are iterated over in least-to-greatest order (by key).

Specified by:

items in interface Container<Key extends Comparable<Key>>

Specified by:

items in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

an iterable over the items

reversed

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

Description copied from interface: OrderedMap

Get a reverse iterable that yields each item once.

The items are iterated over in greatest-to-least order (by key).

Specified by:

reversed in interface OrderedMap<Key extends Comparable<Key>,Value>

Returns:

an iterable over the items