AbstractHeap (JUtil documentation)

java.lang.Object
- net.cscott.jutil.AbstractHeap<K,V>

All Implemented Interfaces:

Heap<K,V>

Direct Known Subclasses:

BinaryHeap, BinomialHeap, FibonacciHeap
```
public abstract class AbstractHeap<K,V>
extends java.lang.Object
implements Heap<K,V>
```
AbstractHeap provides a skeletal implementation of the Heap interface, to minimize the effort required to implement this interface.

Version:

$Id: AbstractHeap.java,v 1.6 2006-10-30 20:14:40 cananian Exp $

Author:

C. Scott Ananian

Constructor Summary

Constructors
Modifier Constructor and Description

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

Constructors
Modifier	Constructor and Description
`protected`	`AbstractHeap(java.util.Comparator<K> c)` Sole constructor, for invocation by subclass constructors.

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
Modifier and Type	Method and Description
`abstract void`	`clear()` Removes all entries from this `Heap`.
`java.util.Comparator<K>`	`comparator()` Returns the comparator used to compare keys in this `Heap`, or `null` if the keys' natural ordering is used.
`abstract void`	`decreaseKey(java.util.Map.Entry<K,V> me, K newkey)` Replace the key in the specified map entry with the specified smaller key.
`abstract void`	`delete(java.util.Map.Entry<K,V> me)` Remove the specified map entry from the mapping.
`abstract java.util.Collection<java.util.Map.Entry<K,V>>`	`entries()` Returns a collection view of all the `Map.Entry`s in this `Heap`.
`protected java.util.Comparator<java.util.Map.Entry<K,V>>`	`entryComparator()` Returns a comparator which can be used to compare `Map.Entry`s.
`boolean`	`equals(java.lang.Object o)` Compares the specified object with this heap for equality.
`java.util.Map.Entry<K,V>`	`extractMinimum()` Remove and return a map entry with minimal key.
`int`	`hashCode()` Returns the hash code for this heap.
`abstract java.util.Map.Entry<K,V>`	`insert(K key, V value)` Inserts a node with the specified key and value into the `Heap`.
`protected void`	`insert(java.util.Map.Entry<K,V> me)` This method should insert the specified `Map.Entry`, which is not currently in the `Heap`, into the `Heap`.
`boolean`	`isEmpty()` Returns `true` if this `Heap` has no more entries.
`protected java.util.Comparator<K>`	`keyComparator()` Returns the comparator used to compare keys in this `Heap`.
`abstract java.util.Map.Entry<K,V>`	`minimum()` Returns a mapping entry with minimal key.
`protected K`	`setKey(java.util.Map.Entry<K,V> me, K newkey)` This method should set the key for the specified `Map.Entry` to the given `newkey`.
`abstract int`	`size()` Returns the number of entries in this `Heap`.
`java.lang.String`	`toString()` Returns a string representation of this `Heap`.
`void`	`union(Heap<? extends K,? extends V> h)` Merges all of the mappings from the specified `Heap` into this `Heap`.
`void`	`updateKey(java.util.Map.Entry<K,V> me, K newkey)` Replace the key in the specified map entry with the specified key, which may be either larger or smaller than its current key.

Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait

- Constructor Detail
  - AbstractHeap
```
protected AbstractHeap(java.util.Comparator<K> c)
```
    Sole constructor, for invocation by subclass constructors.
- Method Detail
  - insert
```
public abstract java.util.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 java.util.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(java.util.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(java.util.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 java.util.Collection<java.util.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(java.util.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(java.util.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(java.util.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 java.util.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. The hash code for this heap will be one greater than the hash code for the Collection returned by Heap.entries().
    
    Specified by:
    
    hashCode in interface Heap<K,V>
    
    Overrides:
    
    hashCode in class java.lang.Object
  - equals
```
public boolean equals(java.lang.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 and the Collections returned by their Heap.entries() methods are equal using the equals() method of Collection.
    
    Specified by:
    
    equals in interface Heap<K,V>
    
    Overrides:
    
    equals in class java.lang.Object
  - toString
```
public java.lang.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 java.lang.Object
  - comparator
```
public java.util.Comparator<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 java.util.Comparator<K> keyComparator()
```
    Returns the comparator used to compare keys in this Heap. Will never return null.
  - entryComparator
```
protected java.util.Comparator<java.util.Map.Entry<K,V>> entryComparator()
```
    Returns a comparator which can be used to compare Map.Entrys. Will never return null.

Class AbstractHeap<K,V>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

AbstractHeap

Method Detail

insert

minimum

decreaseKey

delete

size

entries

clear

updateKey

insert

setKey

extractMinimum

union

isEmpty

hashCode

equals

toString

comparator

keyComparator

entryComparator