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. |
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.
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 BytescacheSize
- the size of the cache in BytesnodeSize
- 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 memorypageSize
- the size of a page in BytescacheSize
- the size of the cache in BytesnodeSize
- the size of a node in Bytes
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 adjustedlast
- 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 testedmax
- 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