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 heap

V - 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 bucket
protected K	lastDeletedKey	Last deleted key.
protected K	maxKey	Maximum key allowed
protected K	minKey	Minimum key allowed
private static long	serialVersionUID
protected long	size	Number of elements

Constructor Summary

Constructors

Constructor	Description
AbstractRadixAddressableHeap()	Constructor

Method Summary

Modifier and Type	Method	Description
void	clear()	Clear all the elements of the heap.
java.util.Comparator<? super K>	comparator()	Always returns null 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()	Returns true 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 the minKey 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

Constructor Detail

AbstractRadixAddressableHeap

AbstractRadixAddressableHeap()

Constructor

Method Detail

findMin

public AddressableHeap.Handle<K,V> findMin()

Find an element with the minimum key.

Specified by:

findMin in interface AddressableHeap<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 interface AddressableHeap<K,V>

Parameters:

key - the element's key

Returns:

a handle for the newly added element

Throws:

java.lang.IllegalArgumentException - if the key is null

java.lang.IllegalArgumentException - if the key is less than the minimum allowed key

java.lang.IllegalArgumentException - if the key is more than the maximum allowed key

java.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 interface AddressableHeap<K,V>

Parameters:

key - the element's key

value - the element's value

Returns:

a handle for the newly added element

Throws:

java.lang.IllegalArgumentException - if the key is null

java.lang.IllegalArgumentException - if the key is less than the minimum allowed key

java.lang.IllegalArgumentException - if the key is more than the maximum allowed key

java.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 method AddressableHeap.Handle.getKey() and AddressableHeap.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 interface AddressableHeap<K,V>

Returns:

a handle to the deleted element with minimum key

isEmpty

public boolean isEmpty()

Returns true if this heap is empty.

Specified by:

isEmpty in interface AddressableHeap<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 interface AddressableHeap<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 methods AddressableHeap.Handle.decreaseKey(Object) and AddressableHeap.Handle.delete() is undefined.

Specified by:

clear in interface AddressableHeap<K,V>

comparator

public java.util.Comparator<? super K> comparator()

Always returns null since this heap uses the natural ordering of its keys.

Specified by:

comparator in interface AddressableHeap<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 key

minKey - 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 value

b - 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