Environment for
DeveLoping
KDD-Applications
Supported by Index-Structures

de.lmu.ifi.dbs.elki.utilities.heap
Class PersistentHeap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.utilities.heap.PersistentHeap<K,V>
Type Parameters:
K - Key type
V - Value type
All Implemented Interfaces:
Heap<K,V>, Serializable

public class PersistentHeap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
extends Object
implements Heap<K,V>

Persistent implementation of a heap-based priority queue. The heap is organized according to the natural order of the stored objects. Elements stored in this heap must be instances of PersistentHeapNode<\code> (@see PersistentHeapNode).

This persistent heap has nodes which are instances of Deap<\code>, i.e. the nodes of this heap are again heaps, more precisely a special implementation of MinMaxHeap. The actual elements are stored in those deaps. Only one path of deaps from the root to the last leaf of this heap is cached in main memory, the rest of the nodes is written to disk. The cache path can change during insert / remove operations.

Author:
Elke Achtert
See Also:
Serialized Form

Field Summary
private  Deap<K,V>[] cachePath
          The actual path of this heap in main memory.
private  PageFile<Deap<K,V>> file
          The file storing the elements of this heap.
private  int height
          The actual height of this heap.
private static Logging logger
           
private  int maxCacheSize
          The maximum number of deaps in the cache, corresponds to the maximum height of this heap.
private  int maxDeapIndex
          The maximum index of a deap in this heap (corresponds to the maximum number of deaps - 1)
private  int maxDeapSize
          The maximum size of a deap.
private  int numDeaps
          The actual number of Deaps in this heap.
private  int numElements
          The number of elements in this heap.
private  int pageSize
          The size of a page (deap) in Bytes.
private static long serialVersionUID
          Serial version number.
 
Constructor Summary
PersistentHeap(int pageSize, int cacheSize, int nodeSize)
          Creates a new persistent heap with the specified parameters.
PersistentHeap(String fileName, int pageSize, int cacheSize, int nodeSize)
          Creates a new persistent heap with the specified parameters.
 
Method Summary
 void addNode(HeapNode<K,V> node)
          Adds a node to this heap.
private  void adjust(Deap<K,V> parent, Deap<K,V> last)
          Adjusts the entries of the specified parent with its sons.
private  void adjustFirstDeap()
          Adjusts the first deap recursively with its sons.
private  int cacheIndex(int index)
          Returns the cache index of the specified index if the index would be in cache.
 void close()
          Closes this persistent heap.
private  Deap<K,V> createNewLastDeap()
          Creates and returns a new deap as last element of the cache path.
private  void fill(Deap<K,V> deap)
           
 void flowUp(int index)
          Moves up a node at the specified index until it satisfies the heaporder.
 Integer[] getCacheIndizes()
          Returns an array of the indices of the deaps in the cache.
private  Deap<K,V> getDeap(int index)
          Returns the deap with the specified index.
private  Deap<K,V> getFirstDeap()
          Returns the first deap in the cache path.
 Integer getIndexOf(V value)
          Returns the current index of the specified value in this heap.
private  Deap<K,V> getLastDeap()
          Returns the last deap in the cache path.
 long getLogicalPageAccess()
          Returns the logical read I/O-access of this heap.
 HeapNode<K,V> getMinNode()
          Retrieves and removes the minimum node of this heap.
 HeapNode<K,V> getNodeAt(int index)
          Returns the node at the specified index.
 long getPhysicalReadAccess()
          Returns the physical read I/O-access of this heap.
 long getPhysicalWriteAccess()
          Returns the physical write I/O-access of this heap.
private  boolean hasChildren(Deap<K,V> deap)
          Returns true if the specified deap has children, false otherwise.
private  void heapify(Deap<K,V> deap)
          Re-establishes the heaporder: while minimum of the specified deap is greater than maximum of its parent the minimum will be moved up and the maximum will be moved down.
private  boolean heapify(Deap<K,V> min, Deap<K,V> max)
          Re-establishes the heap order: while minimum of the specified max is greater than maximum of the specified min the minimum will be moved up and the maximum will be moved down.
private  boolean inCache(Deap<K,V> deap)
          Returns true if the specified deap is in the cache, false otherwise.
private  boolean inCache(int index)
          Returns true if the deap with the specified index is in the cache, false otherwise.
private  void insertParentToCache(Deap<K,V> deap)
          Inserts recursively the parent of the specified deap into cache.
 boolean isEmpty()
          Indicates whether this heap is empty.
private  boolean isLast(Deap<K,V> deap)
          Returns true if the specified deap is the last deap of this heap, false otherwise.
private  boolean isRoot(Deap<K,V> deap)
          Returns true, if the specified deap is the root of this heap, false otherwise.
private  Deap<K,V> leftChild(Deap<K,V> deap)
          Returns the left child of the specified deap in this heap.
private  int level(int index)
          Returns the level of the specified index in this heap.
private  Deap<K,V> nodeBefore(Deap<K,V> deap)
          Returns the deap before the specified deap.
private  Deap<K,V> parentInCache(Deap<K,V> deap)
          Returns the parent of the specified deap in the cache.
private  int parentIndex(Deap<K,V> deap)
          Returns the index of the parent of the specified deap in this heap.
private  int parentIndex(int index)
          Returns the index of the parent of the deap with the specified index in this heap.
 void resetIOAccess()
          Resets the I/O-Access of this heap.
private  Deap<K,V> rightChild(Deap<K,V> deap)
          Returns the right child of the specified deap in this heap.
private  void shrinkCache()
          Shrinks the cache, i.e. removes the last deap from the cache.
 int size()
          Returns the size of this heap.
 String toString()
          Returns a string representation of this heap.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

serialVersionUID

private static final long serialVersionUID
Serial version number.

See Also:
Constant Field Values

logger

private static Logging logger

file

private final PageFile<Deap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>> file
The file storing the elements of this heap.


pageSize

private final int pageSize
The size of a page (deap) in Bytes.


numElements

private int numElements
The number of elements in this heap.


maxCacheSize

private final int maxCacheSize
The maximum number of deaps in the cache, corresponds to the maximum height of this heap.


maxDeapIndex

private final int maxDeapIndex
The maximum index of a deap in this heap (corresponds to the maximum number of deaps - 1)


maxDeapSize

private final int maxDeapSize
The maximum size of a deap.


height

private int height
The actual height of this heap.


numDeaps

private int numDeaps
The actual number of Deaps in this heap.


cachePath

private Deap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>[] cachePath
The actual path of this heap in main memory. This array consists of one path from root to the last leaf.

Constructor Detail

PersistentHeap

public PersistentHeap(int pageSize,
                      int cacheSize,
                      int nodeSize)
Creates a new persistent heap with the specified parameters. The heap will be hold in main memory, the i/o-accesses are only simulated.

Parameters:
pageSize - the size of a page in Bytes
cacheSize - the size of the cache in Bytes
nodeSize - the size of a node in Bytes

PersistentHeap

public PersistentHeap(String fileName,
                      int pageSize,
                      int cacheSize,
                      int nodeSize)
Creates a new persistent heap with the specified parameters.

Parameters:
fileName - the name of the file storing the heap, if this parameter is null, the heap will be hold in main memory
pageSize - the size of a page in Bytes
cacheSize - the size of the cache in Bytes
nodeSize - the size of a node in Bytes
Method Detail

addNode

public void addNode(HeapNode<K,V> node)
Adds a node to this heap.

Specified by:
addNode in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Parameters:
node - the node to be added

getMinNode

public HeapNode<K,V> getMinNode()
Retrieves and removes the minimum node of this heap. If the heap is empty, null will be returned.

Specified by:
getMinNode in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Returns:
the minimum node of this heap, null in case of emptiness

isEmpty

public boolean isEmpty()
Indicates whether this heap is empty.

Specified by:
isEmpty in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Returns:
true if this heap is empty, false otherwise

getIndexOf

public Integer getIndexOf(V value)
Returns the current index of the specified value in this heap.

Specified by:
getIndexOf in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Parameters:
value - the value for which the index should be returned
Returns:
the current index of the specified value in this heap

getNodeAt

public HeapNode<K,V> getNodeAt(int index)
Returns the node at the specified index.

Specified by:
getNodeAt in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Parameters:
index - the index of the node to be returned
Returns:
the node at the specified index

flowUp

public void flowUp(int index)
Moves up a node at the specified index until it satisfies the heaporder.

Specified by:
flowUp in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Parameters:
index - the index of the node to be moved up.

size

public int size()
Returns the size of this heap.

Specified by:
size in interface Heap<K extends Comparable<K> & Serializable,V extends Identifiable & Serializable>
Returns:
the size of this heap

close

public void close()
Closes this persistent heap.


toString

public String toString()
Returns a string representation of this heap.

Overrides:
toString in class Object
Returns:
a string representation of this heap

getPhysicalReadAccess

public long getPhysicalReadAccess()
Returns the physical read I/O-access of this heap.

Returns:
the I/O-Access of this heap

getPhysicalWriteAccess

public long getPhysicalWriteAccess()
Returns the physical write I/O-access of this heap.

Returns:
the I/O-Access of this heap

getLogicalPageAccess

public long getLogicalPageAccess()
Returns the logical read I/O-access of this heap.

Returns:
the I/O-Access of this heap

resetIOAccess

public void resetIOAccess()
Resets the I/O-Access of this heap.


getLastDeap

private Deap<K,V> getLastDeap()
Returns the last deap in the cache path.

Returns:
the last deap in the cache path

getFirstDeap

private Deap<K,V> getFirstDeap()
Returns the first deap in the cache path.

Returns:
the first deap in the cache path

createNewLastDeap

private Deap<K,V> createNewLastDeap()
Creates and returns a new deap as last element of the cache path.

Returns:
a new deap as last element of the cache path

level

private int level(int index)
Returns the level of the specified index in this heap.

Parameters:
index - the index for which the level should be returned
Returns:
the level of the specified index in this heap

insertParentToCache

private void insertParentToCache(Deap<K,V> deap)
Inserts recursively the parent of the specified deap into cache.

Parameters:
deap - the deap for which the parent should be inserted into cache

isRoot

private boolean isRoot(Deap<K,V> deap)
Returns true, if the specified deap is the root of this heap, false otherwise.

Parameters:
deap - the deap to be tested for root
Returns:
true, if the specified deap is the root of this heap, false otherwise

parentIndex

private int parentIndex(Deap<K,V> deap)
Returns the index of the parent of the specified deap in this heap.

Parameters:
deap - the deap for which the parent index should be returned
Returns:
the index of the parent of the specified deap in this heap

parentIndex

private int parentIndex(int index)
Returns the index of the parent of the deap with the specified index in this heap.

Parameters:
index - the index of the deap for which the parent index should be returned
Returns:
the index of the parent of the deap with the specified index

getCacheIndizes

public Integer[] getCacheIndizes()
Returns an array of the indices of the deaps in the cache.

Returns:
an array of the indices of the deaps in the cache

parentInCache

private Deap<K,V> parentInCache(Deap<K,V> deap)
Returns the parent of the specified deap in the cache.

Parameters:
deap - a deap in this heap
Returns:
the parent of the specified deap in the cache

adjustFirstDeap

private void adjustFirstDeap()
Adjusts the first deap recursively with its sons.


adjust

private void adjust(Deap<K,V> parent,
                    Deap<K,V> last)
Adjusts the entries of the specified parent with its sons.

Parameters:
parent - the parent to be adjusted
last - the last deap of this heap

shrinkCache

private void shrinkCache()
Shrinks the cache, i.e. removes the last deap from the cache.


nodeBefore

private Deap<K,V> nodeBefore(Deap<K,V> deap)
Returns the deap before the specified deap.

Parameters:
deap - a deap in this heap
Returns:
the deap before the specified deap

fill

private void fill(Deap<K,V> deap)
Parameters:
deap -

heapify

private void heapify(Deap<K,V> deap)
Re-establishes the heaporder: while minimum of the specified deap is greater than maximum of its parent the minimum will be moved up and the maximum will be moved down.

Parameters:
deap - the deap to be tested

heapify

private boolean heapify(Deap<K,V> min,
                        Deap<K,V> max)
Re-establishes the heap order: while minimum of the specified max is greater than maximum of the specified min the minimum will be moved up and the maximum will be moved down.

Parameters:
min - the minimum deap to be tested
max - the maximum deap to be tested

inCache

private boolean inCache(Deap<K,V> deap)
Returns true if the specified deap is in the cache, false otherwise.

Parameters:
deap - the deap to be tested
Returns:
true if the specified deap is in the cache, false otherwise

inCache

private boolean inCache(int index)
Returns true if the deap with the specified index is in the cache, false otherwise.

Parameters:
index - the index of the deap to be tested
Returns:
true if the deap with the specified index is in the cache, false otherwise

cacheIndex

private int cacheIndex(int index)
Returns the cache index of the specified index if the index would be in cache.

Parameters:
index - the index of the element
Returns:
the cache index

getDeap

private Deap<K,V> getDeap(int index)
Returns the deap with the specified index. If the deap is not in cache it will be read from file.

Parameters:
index - the index of the deap to be returned
Returns:
the deap with the specified index

isLast

private boolean isLast(Deap<K,V> deap)
Returns true if the specified deap is the last deap of this heap, false otherwise.

Parameters:
deap - the deap to be tested
Returns:
true if the specified deap is the last deap of this heap, false otherwise

hasChildren

private boolean hasChildren(Deap<K,V> deap)
Returns true if the specified deap has children, false otherwise.

Parameters:
deap - the deap to be tested
Returns:
true if the specified deap has children, false otherwise

leftChild

private Deap<K,V> leftChild(Deap<K,V> deap)
Returns the left child of the specified deap in this heap.

Parameters:
deap - a deap in this heap
Returns:
the left child of the specified deap in this heap

rightChild

private Deap<K,V> rightChild(Deap<K,V> deap)
Returns the right child of the specified deap in this heap.

Parameters:
deap - a deap in this heap
Returns:
the right child of the specified deap in this heap

Release 0.2.1 (2009-07-13_1605)