pt.ua.base
Class HashTableChainingAssociativeArray<K,E>

java.lang.Object
  pt.ua.base.Listable<K>
      pt.ua.base.AssociativeArray<K,E>
          pt.ua.base.HashTableChainingAssociativeArray<K,E>

public class HashTableChainingAssociativeArray<K,E>
extends AssociativeArray<K,E>

Associative array module implemented with a closed address (chaining) hash table.
This type of associative memory does not allow the existence of several elements with the same key (key repetition).

invariant: AssociativeArray

This class follows DbC(tm) methodology. Where possible, contracts are implement with JML and native's Java assert.

Author:

Miguel Oliveira e Silva (mos@ua.pt)

Constructor Summary

HashTableChainingAssociativeArray()
Creates an empty associative array with an initial capacity of 1024 elements.

HashTableChainingAssociativeArray(int expectedDim)
Creates an empty associative array dimensioned for an expected number of elements.

Method Summary

void	clear() Empties the associative array.
AssociativeArray<K,E>	deepClone() Clones current list.
boolean	exists(K key) Checks if key exists in the associative array.
E	get(K key) Gets the element value associated with value key.
Array<K>	keysToArray() Extracts all keys to an array.
ImmutableList<K>	keysToList() Extracts all keys to an immutable list.
void	remove(K key) Removes key and its associated element value from the array.
void	set(K key, E elem) Associates value elem with value key.
int	size() The list total number of elements.

Methods inherited from class pt.ua.base.AssociativeArray

copy, isFull, isLimited, maxSize, toArray, toList

Methods inherited from class pt.ua.base.Listable

isEmpty

Methods inherited from class java.lang.Object

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

Constructor Detail

HashTableChainingAssociativeArray

public HashTableChainingAssociativeArray()

Creates an empty associative array with an initial capacity of 1024 elements.
This associative array has illimited capacity, and it will be internally resized (doubling its internal array length) whenever its load factor (size()/array.length) exceeds 80%.

ensures: isEmpty()

HashTableChainingAssociativeArray

public HashTableChainingAssociativeArray(int expectedDim)

Creates an empty associative array dimensioned for an expected number of elements.
This associative array has illimited capacity, but its internal array length will be defined only considering the expected number of elements, ensuring for this value that the load factor (size()/array.length) will not exceed 80%.

requires: expectedDim > 0

ensures: isEmpty()

Parameters:

expectedDim - expected associative array maximum number of elements

Method Detail

deepClone

public AssociativeArray<K,E> deepClone()

Description copied from class: Listable

Clones current list.

ensures: \result.size() == size()

Specified by:

deepClone in class AssociativeArray<K,E>

Returns:

a deep clone of current list

set

public void set(K key,
                E elem)

Description copied from class: AssociativeArray

Associates value elem with value key. If key did not exist, adds a new association, otherwise attaches existing key to a new element value.

requires: key != null

ensures: exists(key)
ensures: get(key) == elem
ensures: \old(exists(key)) ==> (size() == \old(size()))
ensures: \old(!exists(key)) ==> (size() == \old(size()) + 1)

Specified by:

set in class AssociativeArray<K,E>

Parameters:

key - the key

elem - the element

get

public E get(K key)

Description copied from class: AssociativeArray

Gets the element value associated with value key.

requires: key != null
requires: exists(key)

Specified by:

get in class AssociativeArray<K,E>

Parameters:

key - the key

Returns:

the element

remove

public void remove(K key)

Description copied from class: AssociativeArray

Removes key and its associated element value from the array.

requires: key != null
requires: exists(key)

ensures: !exists(key)
ensures: size() == \old(size()) - 1

Specified by:

remove in class AssociativeArray<K,E>

Parameters:

key - the key to be removed

exists

public boolean exists(K key)

Description copied from class: AssociativeArray

Checks if key exists in the associative array.

Specified by:

exists in class AssociativeArray<K,E>

Returns:

true if key exists, false otherwise

size

public int size()

Description copied from class: Listable

The list total number of elements.

Specified by:

size in class Listable<K>

Returns:

list's size

keysToArray

public Array<K> keysToArray()

Description copied from class: AssociativeArray

Extracts all keys to an array. Implements: AssociativeArray.toArray().

ensures: \result.size() == size()

Specified by:

keysToArray in class AssociativeArray<K,E>

Returns:

an array with all the associative array keys

keysToList

public ImmutableList<K> keysToList()

Description copied from class: AssociativeArray

Extracts all keys to an immutable list. Implements: AssociativeArray.toList().

ensures: \result.size == size()

Specified by:

keysToList in class AssociativeArray<K,E>

Returns:

an array with all the associative array keys

clear

public void clear()

Description copied from class: AssociativeArray

Empties the associative array.

ensures: isEmpty()

Specified by:

clear in class AssociativeArray<K,E>