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:
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.

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • EMPTY

      protected static final int EMPTY
      Denotes that a key does not belong to a bucket
      See Also:

    • buckets

      protected AbstractRadixAddressableHeap<K,V>.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<K,V>.Node currentMin
      The current minimum value (cached)

    • minKey

      protected K minKey
      Minimum key allowed

    • maxKey

      protected K maxKey
      Maximum key allowed

  • Constructor Details

    • AbstractRadixAddressableHeap

      AbstractRadixAddressableHeap()
      Constructor

  • Method Details

    • 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:
      IllegalArgumentException - if the key is null
      IllegalArgumentException - if the key is less than the minimum allowed key
      IllegalArgumentException - if the key is more than the maximum allowed key
      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:
      IllegalArgumentException - if the key is null
      IllegalArgumentException - if the key is less than the minimum allowed key
      IllegalArgumentException - if the key is more than the maximum allowed key
      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 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