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:
Serializable
,AddressableHeap<K,
V>
- Direct Known Subclasses:
BigIntegerRadixAddressableHeap
,DoubleRadixAddressableHeap
,IntegerRadixAddressableHeap
,LongRadixAddressableHeap
abstract class AbstractRadixAddressableHeap<K,V>
extends Object
implements AddressableHeap<K,V>, Serializable
Base abstract implementation of an addressable radix heap.
-
Nested Class Summary
Nested ClassesNested classes/interfaces inherited from interface org.jheaps.AddressableHeap
AddressableHeap.Handle<K,
V> -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected AbstractRadixAddressableHeap<K,
V>.Node[] The buckets as lists.protected AbstractRadixAddressableHeap<K,
V>.Node The current minimum value (cached)protected static final int
Denotes that a key does not belong to a bucketprotected K
Last deleted key.protected K
Maximum key allowedprotected K
Minimum key allowedprivate static final long
protected long
Number of elements -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
Clear all the elements of the heap.Comparator<? super K>
Always returnsnull
since this heap uses the natural ordering of its keys.protected abstract int
Compares its two arguments for order.protected int
computeBucket
(K key, K minKey) Compute the bucket of a key based on a minimum key.Delete and return an element with the minimum key.private void
findAndCacheMinimum
(int firstBucket) Helper method for finding and caching the minimum.findMin()
Find an element with the minimum key.Insert a new element into the heap with a null value.Insert a new element into the heap.boolean
isEmpty()
Returnstrue
if this heap is empty.protected abstract int
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 Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
EMPTY
protected static final int EMPTYDenotes that a key does not belong to a bucket- See Also:
-
buckets
The buckets as lists. -
size
protected long sizeNumber of elements -
lastDeletedKey
Last deleted key. This value is used to distribute elements in the buckets. Should be initialized with theminKey
value. -
currentMin
The current minimum value (cached) -
minKey
Minimum key allowed -
maxKey
Maximum key allowed
-
-
Constructor Details
-
AbstractRadixAddressableHeap
AbstractRadixAddressableHeap()Constructor
-
-
Method Details
-
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
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:
IllegalArgumentException
- if the key is nullIllegalArgumentException
- if the key is less than the minimum allowed keyIllegalArgumentException
- if the key is more than the maximum allowed keyIllegalArgumentException
- if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
-
insert
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:
IllegalArgumentException
- if the key is nullIllegalArgumentException
- if the key is less than the minimum allowed keyIllegalArgumentException
- if the key is more than the maximum allowed keyIllegalArgumentException
- if the key is less than the last deleted key (or the minimum key allowed if no key has been deleted)
-
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
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
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
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
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
-