gov.sandia.cognition.collection
Class DynamicArrayMap<ValueType>

java.lang.Object
  extended by java.util.AbstractMap<Integer,ValueType>
      extended by gov.sandia.cognition.collection.DynamicArrayMap<ValueType>
Type Parameters:
ValueType - The value stored in the map.
All Implemented Interfaces:
CloneableSerializable, Serializable, Cloneable, Map<Integer,ValueType>, RandomAccess

@CodeReviews(reviews={@CodeReview(reviewer="Kevin R. Dixon",date="2008-02-08",changesNeeded=true,comments={"I like the added class comment describing the running times.  This may be sufficient.","However, I would still like to see running times on each accessor method. Please review."},response=@CodeReviewResponse(respondent="Justin Basilico",date="2008-02-18",moreChangesNeeded=false,comments="Added running times to each accessor method.")),@CodeReview(reviewer="Kevin R. Dixon",date="2006-07-18",changesNeeded=true,comments={"Non-standard use of direct-member access, instead of getters and setters. Please review.","Please add operation running times in class comments like Java does for its LinkedList, HashMap, etc.","In other news, I fixed some minor spacing and made some logical statements use parentheses to make their precedence clear."},response=@CodeReviewResponse(respondent="Justin Basilico",date="2006-09-22",moreChangesNeeded=false,comments="Added comment regarding lack of getters and setters"))})
public class DynamicArrayMap<ValueType>
extends AbstractMap<Integer,ValueType>
implements CloneableSerializable, RandomAccess

A DynamicArrayList is a class that implements a map from an integer to an Object type on top of an expanding array. It is optimized for use with continuous ranges of integer indices, so it does not do any hashing and instead grows the array to fit any index that is set in it. The keys must be non-negative integers. Passing any negative integer into the map will result in an exception being thrown. The running time of the operations in the class are what would be expected if one were operating on an ArrayList where space is always allocated for the highest key inserted. Access is done in constant time, usually setting will be constant time though if the setting is done beyond the end of the current array it will require addition so it will be time proportional to the size of the array. Iteration over the collection takes time proportional to the capacity of the array. Note that this implementation is not synchronized.

Since:
1.0
Author:
Justin Basilico
See Also:
Serialized Form

Nested Class Summary
 
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K,V>, AbstractMap.SimpleImmutableEntry<K,V>
 
Field Summary
static int DEFAULT_INITIAL_CAPACITY
          The default initial capacity is 10.
 
Constructor Summary
DynamicArrayMap()
          Creates a new instance of DynamicArrayMap.
DynamicArrayMap(DynamicArrayMap<? extends ValueType> other)
          Creates a new instance of DynamicArrayMap using the given mapping to copy into this map.
DynamicArrayMap(int initialCapacity)
          Creates a new instance of DynamicArrayMap with the given initial capacity.
 
Method Summary
 void clear()
           Runs in O(n).
 DynamicArrayMap<ValueType> clone()
          Creates a new clone (shallow copy) of this object.
 boolean containsKey(int key)
          Returns true if this is a valid key in the mapping.
 boolean containsKey(Object key)
           Runs in O(1).
 boolean containsValue(Object value)
           Runs in O(n).
 void ensureCapacity(int minCapacity)
          Ensures that the capacity of the underlying array can hold the given minimum capacity.
 Set<Map.Entry<Integer,ValueType>> entrySet()
           
 ValueType get(int key)
          Gets the value for the given key.
 ValueType get(Object key)
           Runs in O(1).
 boolean isEmpty()
           Runs in O(1).
 Set<Integer> keySet()
           
 ValueType put(Integer key, ValueType value)
           Runs in O(1) if the key is within the range already used, otherwise O(n) to expand the range.
 ValueType put(int key, ValueType value)
          Puts a value into the mapping.
 ValueType remove(int key)
          Removes the value for the given key from the mapping.
 ValueType remove(Object key)
           Runs in O(1).
 int size()
           Runs in O(1).
 Collection<ValueType> values()
           
 
Methods inherited from class java.util.AbstractMap
equals, hashCode, putAll, toString
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

DEFAULT_INITIAL_CAPACITY

public static final int DEFAULT_INITIAL_CAPACITY
The default initial capacity is 10.

See Also:
Constant Field Values
Constructor Detail

DynamicArrayMap

public DynamicArrayMap()
Creates a new instance of DynamicArrayMap. The default initial capacity is 10.


DynamicArrayMap

public DynamicArrayMap(int initialCapacity)
Creates a new instance of DynamicArrayMap with the given initial capacity.

Parameters:
initialCapacity - The initial capacity of the underlying array. It must be positive.

DynamicArrayMap

public DynamicArrayMap(DynamicArrayMap<? extends ValueType> other)
Creates a new instance of DynamicArrayMap using the given mapping to copy into this map.

Parameters:
other - The other mapping to do a shallow copy of.
Method Detail

clone

public DynamicArrayMap<ValueType> clone()
Creates a new clone (shallow copy) of this object. Runs in O(n).

Specified by:
clone in interface CloneableSerializable
Overrides:
clone in class AbstractMap<Integer,ValueType>
Returns:
A new clone (shallow copy) of this object.

clear

public void clear()
Runs in O(n).

Specified by:
clear in interface Map<Integer,ValueType>
Overrides:
clear in class AbstractMap<Integer,ValueType>

containsKey

public boolean containsKey(Object key)
Runs in O(1).

Specified by:
containsKey in interface Map<Integer,ValueType>
Overrides:
containsKey in class AbstractMap<Integer,ValueType>
Parameters:
key -
Returns:

containsKey

public boolean containsKey(int key)
Returns true if this is a valid key in the mapping. Runs in O(1).

Parameters:
key - integer to search for in the mapping
Returns:
True if this is a valid key in the mapping.

containsValue

public boolean containsValue(Object value)
Runs in O(n).

Specified by:
containsValue in interface Map<Integer,ValueType>
Overrides:
containsValue in class AbstractMap<Integer,ValueType>
Parameters:
value -
Returns:

ensureCapacity

public void ensureCapacity(int minCapacity)
Ensures that the capacity of the underlying array can hold the given minimum capacity. This means that a key up to the given value can be provided without the array being reallocated. Runs in O(n).

Parameters:
minCapacity - The minimum capacity to ensure.

entrySet

public Set<Map.Entry<Integer,ValueType>> entrySet()
Specified by:
entrySet in interface Map<Integer,ValueType>
Specified by:
entrySet in class AbstractMap<Integer,ValueType>

get

public ValueType get(Object key)
Runs in O(1).

Specified by:
get in interface Map<Integer,ValueType>
Overrides:
get in class AbstractMap<Integer,ValueType>
Parameters:
key -
Returns:
Throws:
NullPointerException - If the key is null.

get

public ValueType get(int key)
Gets the value for the given key. If there is no value, null is returned. Runs in O(1).

Parameters:
key - The key to look up.
Returns:
The value at the given key, if one exists. Otherwise null is returned.

isEmpty

public boolean isEmpty()
Runs in O(1).

Specified by:
isEmpty in interface Map<Integer,ValueType>
Overrides:
isEmpty in class AbstractMap<Integer,ValueType>
Returns:

keySet

public Set<Integer> keySet()
Specified by:
keySet in interface Map<Integer,ValueType>
Overrides:
keySet in class AbstractMap<Integer,ValueType>

put

public ValueType put(Integer key,
                     ValueType value)
Runs in O(1) if the key is within the range already used, otherwise O(n) to expand the range.

Specified by:
put in interface Map<Integer,ValueType>
Overrides:
put in class AbstractMap<Integer,ValueType>
Parameters:
key -
value -
Returns:
Throws:
NullPointerException - If the key is null.

put

public ValueType put(int key,
                     ValueType value)
Puts a value into the mapping. If the value it null, it removes the the entry from the mapping. Normally this operation runs in O(1), however if the value is not null and the given key is not in the current range then it will be O(n).

Parameters:
key - The non-negative key.
value - The new value for the key.
Returns:
The old value for the key. Null if no value was associated with the key.

remove

public ValueType remove(Object key)
Runs in O(1).

Specified by:
remove in interface Map<Integer,ValueType>
Overrides:
remove in class AbstractMap<Integer,ValueType>
Parameters:
key -
Returns:
Throws:
NullPointerException - If the key is null.

remove

public ValueType remove(int key)
Removes the value for the given key from the mapping. Runs in O(1).

Parameters:
key - The key to remove from the mapping.
Returns:
The value stored at the given key or null if no value was associated with the key.

size

public int size()
Runs in O(1).

Specified by:
size in interface Map<Integer,ValueType>
Overrides:
size in class AbstractMap<Integer,ValueType>
Returns:

values

public Collection<ValueType> values()
Specified by:
values in interface Map<Integer,ValueType>
Overrides:
values in class AbstractMap<Integer,ValueType>