|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--java.util.AbstractMap | +--com.tagtraum.perf.datastructures.SkipList
Realization of a SkipList. Note that this is not a complete realization of the Map
interface,
some methods aren't supported.
A SkipList is an alternative to a balanced tree like TreeMap
. As this implementation is
slower than the standard TreeMap
it serves only educational/demonstrational purposes.
Nested Class Summary |
Nested classes inherited from class java.util.Map |
java.util.Map.Entry |
Constructor Summary | |
SkipList()
Constructs a new skip list with a capacity of 101 entries. |
|
SkipList(int capacity)
Constructs a new skip list optimized for the given capacity. |
|
SkipList(int capacity,
float probability)
Constructs a new skip list optimized for the given capacity and probability. |
Method Summary | |
void |
clear()
|
java.util.Comparator |
comparator()
Returns the comparator used to order this map, or null if this map uses its keys' natural order. |
boolean |
containsKey(java.lang.Object key)
|
boolean |
containsValue(java.lang.Object value)
|
java.util.Set |
entrySet()
Not supported. |
java.lang.Object |
firstKey()
Returns the first (lowest) key currently in this sorted map. |
java.lang.Object |
get(java.lang.Object key)
|
java.util.SortedMap |
headMap(java.lang.Object toKey)
Not supported. |
boolean |
isEmpty()
|
java.lang.Object |
lastKey()
|
java.lang.Object |
put(java.lang.Object key,
java.lang.Object value)
|
java.lang.Object |
remove(java.lang.Object key)
|
int |
size()
Returns the number of key-value mappings in this map. |
java.util.SortedMap |
subMap(java.lang.Object fromKey,
java.lang.Object toKey)
Not supported. |
java.util.SortedMap |
tailMap(java.lang.Object fromKey)
Not supported. |
Methods inherited from class java.util.AbstractMap |
clone, equals, hashCode, keySet, putAll, toString, values |
Methods inherited from class java.lang.Object |
finalize, getClass, notify, notifyAll, wait, wait, wait |
Constructor Detail |
public SkipList()
public SkipList(int capacity)
public SkipList(int capacity, float probability)
Method Detail |
public java.lang.Object get(java.lang.Object key)
get
in interface java.util.Map
get
in class java.util.AbstractMap
public java.lang.Object put(java.lang.Object key, java.lang.Object value)
put
in interface java.util.Map
put
in class java.util.AbstractMap
public java.lang.Object remove(java.lang.Object key)
remove
in interface java.util.Map
remove
in class java.util.AbstractMap
public int size()
size
in interface java.util.Map
size
in class java.util.AbstractMap
public java.lang.Object firstKey()
java.util.NoSuchElementException
- Map is empty.public java.lang.Object lastKey()
public java.util.Comparator comparator()
public boolean isEmpty()
isEmpty
in interface java.util.Map
isEmpty
in class java.util.AbstractMap
public boolean containsKey(java.lang.Object key)
containsKey
in interface java.util.Map
containsKey
in class java.util.AbstractMap
public void clear()
clear
in interface java.util.Map
clear
in class java.util.AbstractMap
public boolean containsValue(java.lang.Object value)
containsValue
in interface java.util.Map
containsValue
in class java.util.AbstractMap
public java.util.Set entrySet()
entrySet
in interface java.util.Map
entrySet
in class java.util.AbstractMap
public java.util.SortedMap subMap(java.lang.Object fromKey, java.lang.Object toKey)
public java.util.SortedMap headMap(java.lang.Object toKey)
public java.util.SortedMap tailMap(java.lang.Object fromKey)
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |