ValueType - The value stored in the map.@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 java.util.AbstractMap<java.lang.Integer,ValueType> implements CloneableSerializable, java.util.RandomAccess
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.| Modifier and Type | Field and Description |
|---|---|
static int |
DEFAULT_INITIAL_CAPACITY
The default initial capacity is 10.
|
| Constructor and Description |
|---|
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.
|
| Modifier and Type | Method and Description |
|---|---|
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(java.lang.Object key)
Runs in O(1).
|
boolean |
containsValue(java.lang.Object value)
Runs in O(n).
|
void |
ensureCapacity(int minCapacity)
Ensures that the capacity of the underlying array can hold the given
minimum capacity.
|
java.util.Set<java.util.Map.Entry<java.lang.Integer,ValueType>> |
entrySet() |
ValueType |
get(int key)
Gets the value for the given key.
|
ValueType |
get(java.lang.Object key)
Runs in O(1).
|
boolean |
isEmpty()
Runs in O(1).
|
java.util.Set<java.lang.Integer> |
keySet() |
ValueType |
put(java.lang.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(java.lang.Object key)
Runs in O(1).
|
int |
size()
Runs in O(1).
|
java.util.Collection<ValueType> |
values() |
public static final int DEFAULT_INITIAL_CAPACITY
public DynamicArrayMap()
public DynamicArrayMap(int initialCapacity)
initialCapacity - The initial capacity of the underlying array. It
must be positive.public DynamicArrayMap(DynamicArrayMap<? extends ValueType> other)
other - The other mapping to do a shallow copy of.public DynamicArrayMap<ValueType> clone()
clone in interface CloneableSerializableclone in class java.util.AbstractMap<java.lang.Integer,ValueType>public void clear()
public boolean containsKey(java.lang.Object key)
public boolean containsKey(int key)
key - integer to search for in the mappingpublic boolean containsValue(java.lang.Object value)
public void ensureCapacity(int minCapacity)
minCapacity - The minimum capacity to ensure.public java.util.Set<java.util.Map.Entry<java.lang.Integer,ValueType>> entrySet()
public ValueType get(java.lang.Object key)
public ValueType get(int key)
key - The key to look up.public boolean isEmpty()
public java.util.Set<java.lang.Integer> keySet()
public ValueType put(java.lang.Integer key, ValueType value)
public ValueType put(int key, ValueType value)
key - The non-negative key.value - The new value for the key.public ValueType remove(java.lang.Object key)
public ValueType remove(int key)
key - The key to remove from the mapping.public int size()