Package org.jheaps.monotone
Class AbstractRadixAddressableHeap<K,V>
- java.lang.Object
-
- org.jheaps.monotone.AbstractRadixAddressableHeap<K,V>
-
- Type Parameters:
K
- the type of keys maintained by this heapV
- the type of values maintained by this heap
- All Implemented Interfaces:
java.io.Serializable
,AddressableHeap<K,V>
- Direct Known Subclasses:
BigIntegerRadixAddressableHeap
,DoubleRadixAddressableHeap
,IntegerRadixAddressableHeap
,LongRadixAddressableHeap
abstract class AbstractRadixAddressableHeap<K,V> extends java.lang.Object implements AddressableHeap<K,V>, java.io.Serializable
Base abstract implementation of an addressable radix heap.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
AbstractRadixAddressableHeap.Node
List Node-
Nested classes/interfaces inherited from interface org.jheaps.AddressableHeap
AddressableHeap.Handle<K,V>
-
-
Field Summary
Fields Modifier and Type Field Description protected AbstractRadixAddressableHeap.Node[]
buckets
The buckets as lists.protected AbstractRadixAddressableHeap.Node
currentMin
The current minimum value (cached)protected static int
EMPTY
Denotes that a key does not belong to a bucketprotected K
lastDeletedKey
Last deleted key.protected K
maxKey
Maximum key allowedprotected K
minKey
Minimum key allowedprivate static long
serialVersionUID
protected long
size
Number of elements
-
Constructor Summary
Constructors Constructor Description AbstractRadixAddressableHeap()
Constructor
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description void
clear()
Clear all the elements of the heap.java.util.Comparator<? super K>
comparator()
Always returnsnull
since this heap uses the natural ordering of its keys.protected abstract int
compare(K o1, K o2)
Compares its two arguments for order.protected int
computeBucket(K key, K minKey)
Compute the bucket of a key based on a minimum key.AddressableHeap.Handle<K,V>
deleteMin()
Delete and return an element with the minimum key.private void
findAndCacheMinimum(int firstBucket)
Helper method for finding and caching the minimum.AddressableHeap.Handle<K,V>
findMin()
Find an element with the minimum key.AddressableHeap.Handle<K,V>
insert(K key)
Insert a new element into the heap with a null value.AddressableHeap.Handle<K,V>
insert(K key, V value)
Insert a new element into the heap.boolean
isEmpty()
Returnstrue
if this heap is empty.protected abstract int
msd(K a, K b)
Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.long
size()
Returns the number of elements in the heap.
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
EMPTY
protected static final int EMPTY
Denotes that a key does not belong to a bucket- See Also:
- Constant Field Values
-
buckets
protected AbstractRadixAddressableHeap.Node[] buckets
The buckets as lists.
-
size
protected long size
Number of elements
-
lastDeletedKey
protected K lastDeletedKey
Last deleted key. This value is used to distribute elements in the buckets. Should be initialized with theminKey
value.
-
currentMin
protected AbstractRadixAddressableHeap.Node currentMin
The current minimum value (cached)
-
minKey
protected K minKey
Minimum key allowed
-
maxKey
protected K maxKey
Maximum key allowed
-
-
Method Detail
-
findMin
public AddressableHeap.Handle<K,V> findMin()
Find an element with the minimum key.- Specified by:
findMin
in interfaceAddressableHeap<K,V>
- Returns:
- a handle to an element with minimum key
-
insert
public AddressableHeap.Handle<K,V> insert(K key)
Insert a new element into the heap with a null value.- Specified by:
insert
in interfaceAddressableHeap<K,V>
- Parameters:
key
- the element's key- Returns:
- a handle for the newly added element
- Throws:
java.lang.IllegalArgumentException
- if the key is nulljava.lang.IllegalArgumentException
- if the key is less than the minimum allowed keyjava.lang.IllegalArgumentException
- if the key is more than the maximum allowed keyjava.lang.IllegalArgumentException
- if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
-
insert
public AddressableHeap.Handle<K,V> insert(K key, V value)
Insert a new element into the heap.- Specified by:
insert
in interfaceAddressableHeap<K,V>
- Parameters:
key
- the element's keyvalue
- the element's value- Returns:
- a handle for the newly added element
- Throws:
java.lang.IllegalArgumentException
- if the key is nulljava.lang.IllegalArgumentException
- if the key is less than the minimum allowed keyjava.lang.IllegalArgumentException
- if the key is more than the maximum allowed keyjava.lang.IllegalArgumentException
- if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
-
deleteMin
public AddressableHeap.Handle<K,V> deleteMin()
Delete and return an element with the minimum key. If multiple such elements exists, only one of them will be deleted. After the element is deleted the handle is invalidated and only methodAddressableHeap.Handle.getKey()
andAddressableHeap.Handle.getValue()
can be used. The cost of this operation is amortized O(logC) assuming the heap contains keys in the range [0, C] or equivalently [a, a+C].- Specified by:
deleteMin
in interfaceAddressableHeap<K,V>
- Returns:
- a handle to the deleted element with minimum key
-
isEmpty
public boolean isEmpty()
Returnstrue
if this heap is empty.- Specified by:
isEmpty
in interfaceAddressableHeap<K,V>
- Returns:
true
if this heap is empty,false
otherwise
-
size
public long size()
Returns the number of elements in the heap.- Specified by:
size
in interfaceAddressableHeap<K,V>
- Returns:
- the number of elements in the heap
-
clear
public void clear()
Clear all the elements of the heap. After calling this method all handles should be considered invalidated and the behavior of methodsAddressableHeap.Handle.decreaseKey(Object)
andAddressableHeap.Handle.delete()
is undefined.- Specified by:
clear
in interfaceAddressableHeap<K,V>
-
comparator
public java.util.Comparator<? super K> comparator()
Always returnsnull
since this heap uses the natural ordering of its keys.- Specified by:
comparator
in interfaceAddressableHeap<K,V>
- Returns:
null
since this heap uses the natural ordering of its keys
-
compare
protected abstract int compare(K o1, K o2)
Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.- Parameters:
o1
- the first object to be compared.o2
- the second object to be compared.- Returns:
- a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
-
computeBucket
protected int computeBucket(K key, K minKey)
Compute the bucket of a key based on a minimum key.- Parameters:
key
- the keyminKey
- the minimum key- Returns:
- the bucket where the key should go
-
msd
protected abstract int msd(K a, K b)
Compute the most significant digit which is different in the binary representation of two values, or -1 if numbers are equal.- Parameters:
a
- the first valueb
- the second value- Returns:
- the most significant digit which is different or -1 if numbers are equal
-
findAndCacheMinimum
private void findAndCacheMinimum(int firstBucket)
Helper method for finding and caching the minimum. Assumes that the heap contains at least one element.- Parameters:
firstBucket
- start looking for elements from this bucket
-
-