|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.core.ref.ArraySkipList
Inner classes inherited from class jdsl.core.api.InspectableDictionary |
InspectableDictionary.InvalidLocator |
Field Summary | |
static int |
DEFAULT_MAX_LEVEL
Default maximum level of node. |
Fields inherited from interface jdsl.core.api.InspectableOrderedDictionary |
BOUNDARY_VIOLATION |
Fields inherited from interface jdsl.core.api.InspectableDictionary |
NO_SUCH_KEY |
Constructor Summary | |
ArraySkipList(Comparator comparator)
Runs in O(1 + t) time where t is the time it takes to create the head node with (DEFAULT_MAX_LEVEL+1) forward links. |
|
ArraySkipList(Comparator comparator,
int maxLevel)
Runs in O(1 + t) time where t is the time it takes to create the head node with (DEFAULT_MAX_LEVEL+1) forward links. |
|
ArraySkipList(Comparator comparator,
int maxLevel,
long seed)
Runs in O(1 + t) time where t is the time it takes to create the head node with (maxLevel+1) forward links. |
Method Summary | |
Locator |
after(Locator locator)
Runs in O(1) time. |
Locator |
before(Locator locator)
Runs in O(1) time. |
Locator |
closestAfter(java.lang.Object key)
Runs in expected O(log n) time, where n is the number of elements. |
Locator |
closestBefore(java.lang.Object key)
Runs in expected O(log n) time, where n is the number of elements. |
boolean |
contains(Accessor a)
Runs in O(1) time. |
ObjectIterator |
elements()
Runs in O(n) time, where n is the number of elements. |
Locator |
find(java.lang.Object key)
Runs in expected O(log n) time, where n is the number of elements finds first node within skip list with key. |
LocatorIterator |
findAll(java.lang.Object key)
Runs in expected O(log n + m) time where n is the total number of elements and m is the number of elements with key value equal to key . |
Locator |
first()
Runs in O(1) time. |
Locator |
insert(java.lang.Object key,
java.lang.Object element)
Runs in expected O(log n) time, where n is the number of elements in the skip list. |
boolean |
isEmpty()
Runs in O(1) time. |
ObjectIterator |
keys()
Runs in O(n) time, where n is the number of elements. |
Locator |
last()
Runs in O(1) time. |
LocatorIterator |
locators()
Runs in O(n) time, where n is the number of elements. |
Container |
newContainer()
Runs in O(1 + t) time where t is the time it takes to create the head node. |
void |
remove(Locator locator)
Runs in expected O(log n) time, where n is the number of elements. |
LocatorIterator |
removeAll(java.lang.Object searchKey)
Runs in expected O(log n + k) where k is the number of duplicate keys and n is the number of elements. |
Locator |
removeKey(java.lang.Object key)
Runs in expected O(log n) time, where n is the number of elements. |
java.lang.Object |
replaceElement(Accessor a,
java.lang.Object newElement)
Runs in O(1) time. |
java.lang.Object |
replaceKey(Locator locator,
java.lang.Object key)
Runs in expected O(log n) time, where n is the number of elements. |
int |
size()
Runs in O(1) time. |
java.lang.String |
toString()
Runs in O(n) time, where n is the number of elements. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
public static final int DEFAULT_MAX_LEVEL
Constructor Detail |
public ArraySkipList(Comparator comparator, int maxLevel, long seed)
(maxLevel+1)
forward links.
An ideal value for maxLevel
would be.
log(N)
where N
is the total
number of elements expected.
Initializes head node.
Sets current level to 0, which is the minimum.comparator
- comparator to use.maxLevel
- highest level for any node.seed
- seed for random number generator.public ArraySkipList(Comparator comparator, int maxLevel)
(DEFAULT_MAX_LEVEL+1)
forward links.comparator
- comparator to use.maxLevel
- highest level for any node.public ArraySkipList(Comparator comparator)
(DEFAULT_MAX_LEVEL+1)
forward links.comparator
- comparator to use.Method Detail |
public Container newContainer()
newContainer
in interface Container
jdsl.core.api.Container
public java.lang.Object replaceElement(Accessor a, java.lang.Object newElement) throws InvalidAccessorException
replaceElement
in interface Container
jdsl.core.api.Container
a
- Accessor in this containernewElement
- to be stored at aInvalidAccessorException
- if a is null or does not
belong to this containerpublic boolean contains(Accessor a) throws InvalidAccessorException
contains
in interface InspectableContainer
jdsl.core.api.InspectableContainer
InvalidAccessorException
- if a is nullpublic int size()
size
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public boolean isEmpty()
isEmpty
in interface InspectableContainer
jdsl.core.api.InspectableContainer
true
if and only if the container is empty (holds
no elements)InspectableBinaryTree
public ObjectIterator elements()
elements
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public LocatorIterator locators()
locators
in interface InspectableKeyBasedContainer
jdsl.core.api.InspectableKeyBasedContainer
public ObjectIterator keys()
keys
in interface InspectableKeyBasedContainer
jdsl.core.api.InspectableKeyBasedContainer
public java.lang.Object replaceKey(Locator locator, java.lang.Object key) throws InvalidAccessorException, InvalidKeyException
replaceKey
in interface KeyBasedContainer
jdsl.core.api.KeyBasedContainer
loc
- the locator in the container whose key should be replacedkey
- the new key to associate with loc
.InvalidAccessorException
- If the locator is not valid
or is not contained by this containerInvalidKeyException
- If key
cannot be used
by this containerpublic Locator find(java.lang.Object key) throws InvalidKeyException
after()
.find
in interface InspectableDictionary
jdsl.core.api.InspectableDictionary
key
- The key mapped to search for.Locator
referring to the key-element pair
that was found, or NO_SUCH_KEY if it could not be found.InvalidKeyException
- if the specified key is not a valid
key in this container.InspectableDictionary.NO_SUCH_KEY
public LocatorIterator findAll(java.lang.Object key) throws InvalidKeyException
key
.
relies on find() returning first node in skip list containing key
.findAll
in interface InspectableDictionary
jdsl.core.api.InspectableDictionary
key
- The key to search for.InvalidKeyException
- if the specified key is not valid in
this containerpublic Locator closestBefore(java.lang.Object key) throws InvalidKeyException
closestBefore
in interface InspectableOrderedDictionary
jdsl.core.api.InspectableOrderedDictionary
key
- A valid key.key
. Note: If no such locator exists, the
returned locator will be BOUNDARY_VIOLATION.InvalidKeyException
- If key
is not of a
type accepted by this Container (For example: the key is not
comparable).public Locator closestAfter(java.lang.Object key) throws InvalidKeyException
closestAfter
in interface InspectableOrderedDictionary
jdsl.core.api.InspectableOrderedDictionary
key
- A valid key.key
. Note: If no such Locator exists, the
returned locator will be BOUNDARY_VIOLATION.InvalidKeyException
- If key
is not of a
type accepted by this Container (For example: the key is not
comparable).public Locator after(Locator locator) throws InvalidAccessorException
after
in interface InspectableOrderedDictionary
jdsl.core.api.InspectableOrderedDictionary
locator
- An abstract position in this Container.
locator
. Note: Will return the invalid
BOUNDARY_VIOLATION Locator if no such locator exists.InvalidAccessorException
- If locator
is
invalid (For example: It does not actually reference an element
within this Container).public Locator before(Locator locator) throws InvalidAccessorException
before
in interface InspectableOrderedDictionary
jdsl.core.api.InspectableOrderedDictionary
locator
- An abstract position in this Container.
locator
. Note: Will return the invalid
BOUNDARY_VIOLATION Locator if no such locator exists.InvalidAccessorException
- If locator
is
invalid (For example: It does not actually reference an element
within this Container).public Locator insert(java.lang.Object key, java.lang.Object element) throws InvalidKeyException
insert
in interface KeyBasedContainer
jdsl.core.api.KeyBasedContainer
key
- the key associated with the specified element.element
- the element to insert into the container.InvalidKeyException
- if key
cannot be used
by this containerpublic LocatorIterator removeAll(java.lang.Object searchKey) throws InvalidKeyException
key
.removeAll
in interface Dictionary
jdsl.core.api.Dictionary
key
- the key to search forInvalidKeyException
- if the specified key is not a
valid key in this containerpublic Locator removeKey(java.lang.Object key) throws InvalidKeyException
key
- key to remove from container.InvalidKeyException
- If the key is null or not compatible with container.public void remove(Locator locator) throws InvalidAccessorException
remove
in interface KeyBasedContainer
jdsl.core.api.KeyBasedContainer
loc
- a locator in the container to removeInvalidAccessorException
- if the locator is not valid or
is not contained by this containerpublic Locator first()
first
in interface InspectableOrderedDictionary
BOUNDARY_VIOLATION
if list is empty.public Locator last()
last
in interface InspectableOrderedDictionary
jdsl.core.api.InspectableOrderedDictionary
public java.lang.String toString()
toString
in class java.lang.Object
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |