Package net.cscott.jutil

Class AbstractHeap<K,V>

java.lang.Object
net.cscott.jutil.AbstractHeap<K,V>
All Implemented Interfaces:
Iterable<Map.Entry<K,V>>, Heap<K,V>
Direct Known Subclasses:
BinaryHeap, BinomialHeap, FibonacciHeap
public abstract class AbstractHeap<K,V> extends Object implements Heap<K,V>
AbstractHeap provides a skeletal implementation of the Heap interface, to minimize the effort required to implement this interface.
Author:
C. Scott Ananian <cananian@alumni.princeton.edu>

  • Constructor Details

    • AbstractHeap

      protected AbstractHeap(Comparator<? super K> c)
      Sole constructor, for invocation by subclass constructors.

  • Method Details

    • insert

      public abstract Map.Entry<K,V> insert(K key, V value)
      Description copied from interface: Heap
      Inserts a node with the specified key and value into the Heap. Returns the generated Map.Entry which may be stored and eventually passed back to decreaseKey() or delete to remove this node.
      Specified by:
      insert in interface Heap<K,V>

    • minimum

      public abstract Map.Entry<K,V> minimum()
      Description copied from interface: Heap
      Returns a mapping entry with minimal key.
      Specified by:
      minimum in interface Heap<K,V>

    • decreaseKey

      public abstract void decreaseKey(Map.Entry<K,V> me, K newkey)
      Description copied from interface: Heap
      Replace the key in the specified map entry with the specified smaller key.
      Specified by:
      decreaseKey in interface Heap<K,V>

    • delete

      public abstract void delete(Map.Entry<K,V> me)
      Description copied from interface: Heap
      Remove the specified map entry from the mapping.
      Specified by:
      delete in interface Heap<K,V>

    • size

      public abstract int size()
      Description copied from interface: Heap
      Returns the number of entries in this Heap.
      Specified by:
      size in interface Heap<K,V>

    • entries

      public abstract Collection<Map.Entry<K,V>> entries()
      Description copied from interface: Heap
      Returns a collection view of all the Map.Entrys in this Heap.
      Specified by:
      entries in interface Heap<K,V>

    • clear

      public abstract void clear()
      Description copied from interface: Heap
      Removes all entries from this Heap.
      Specified by:
      clear in interface Heap<K,V>

    • updateKey

      public void updateKey(Map.Entry<K,V> me, K newkey)
      Description copied from interface: Heap
      Replace the key in the specified map entry with the specified key, which may be either larger or smaller than its current key.
      Specified by:
      updateKey in interface Heap<K,V>

    • insert

      protected void insert(Map.Entry<K,V> me)
      This method should insert the specified Map.Entry, which is not currently in the Heap, into the Heap. Implementation is optional, but it is required if you use the default implementation of updateKey().

    • setKey

      protected K setKey(Map.Entry<K,V> me, K newkey)
      This method should set the key for the specified Map.Entry to the given newkey. Implementation is optional, but it is required if you use the default implementation of updateKey().

    • extractMinimum

      public Map.Entry<K,V> extractMinimum()
      Description copied from interface: Heap
      Remove and return a map entry with minimal key.
      Specified by:
      extractMinimum in interface Heap<K,V>

    • union

      public void union(Heap<? extends K,? extends V> h)
      Description copied from interface: Heap
      Merges all of the mappings from the specified Heap into this Heap. Note that duplicates are permitted. After calling union(), the Heap passed in as an argument will be empty.

      Note that usually efficient implementations of this method require that the Heap argument be from the same implementation as this. (That is, they must both be binomial heaps, or both fibonacci heaps, etc.)

      Specified by:
      union in interface Heap<K,V>

    • isEmpty

      public boolean isEmpty()
      Description copied from interface: Heap
      Returns true if this Heap has no more entries.
      Specified by:
      isEmpty in interface Heap<K,V>

    • hashCode

      public int hashCode()
      Description copied from interface: Heap
      Returns the hash code for this heap: one greater than the sum of the hash codes of its entries.
      Specified by:
      hashCode in interface Heap<K,V>
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object o)
      Description copied from interface: Heap
      Compares the specified object with this heap for equality. Returns true iff the given object is also a Heap with the same entries, in any order: each key-value pair is in both heaps the same number of times. The heaps' comparators are not compared.
      Specified by:
      equals in interface Heap<K,V>
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Description copied from interface: Heap
      Returns a string representation of this Heap.
      Specified by:
      toString in interface Heap<K,V>
      Overrides:
      toString in class Object

    • comparator

      public Comparator<? super K> comparator()
      Returns the comparator used to compare keys in this Heap, or null if the keys' natural ordering is used.
      Specified by:
      comparator in interface Heap<K,V>

    • keyComparator

      protected Comparator<? super K> keyComparator()
      Returns the comparator used to compare keys in this Heap. Will never return null.

    • entryComparator

      protected Comparator<Map.Entry<K,V>> entryComparator()
      Returns a comparator which can be used to compare Map.Entrys. Will never return null.