ch.ethz.mxquery.sms.btree
Class InternalNodeArrayMap

java.lang.Object
  ch.ethz.mxquery.sms.btree.InternalNodeArrayMap

Direct Known Subclasses:

InternalNodeArrayOffsetMap

public class InternalNodeArrayMap
extends java.lang.Object

Helper for b-tree nodes. This is a typed version similar to LeafArrayMap. Generics not used due to inefficient use of complex types in Java 5.

Constructor Summary

InternalNodeArrayMap(int n)
Initiates the InternalNodeArrayMap

Method Summary

void	addAtPos(DeweyIdentifier key, int pos, BTreeNode rightNode) Adds the given mapping at the given position in this array.
int	binarySearch(java.util.Vector a, DeweyIdentifier key, int from, int to)
boolean	delete(DeweyIdentifier key) Returns false if key was not found.
void	deleteAtPos(int pos) Deletes the key-node mapping at the given position.
BTreeNode	get(DeweyIdentifier key) Returns the node corresponding to the interval in which the provided key falls.
int	getIntervalPosition(DeweyIdentifier key) Obtains the position in the nodes array that represents the interval in which the provided key falls.
DeweyIdentifier	getMidKey()
void	put(DeweyIdentifier key, BTreeNode rightNode) Puts the given key to rightNode association in the node array map.
int	size()
InternalNodeArrayMap	split() Splits this map, keeps entries from 0 to (mid-1) and returns a new map with entries from (mid+1) to (currentSize-1).
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

InternalNodeArrayMap

public InternalNodeArrayMap(int n)

Initiates the InternalNodeArrayMap

Method Detail

binarySearch

public int binarySearch(java.util.Vector a,
                        DeweyIdentifier key,
                        int from,
                        int to)

getMidKey

public DeweyIdentifier getMidKey()

split

public InternalNodeArrayMap split()

Splits this map, keeps entries from 0 to (mid-1) and returns a new map with entries from (mid+1) to (currentSize-1). The key mid is no longer present in either map and thus should be promoted.

Returns:

the right node map

put

public void put(DeweyIdentifier key,
                BTreeNode rightNode)

Puts the given key to rightNode association in the node array map.

Parameters:

key -

rightNode -

get

public BTreeNode get(DeweyIdentifier key)

Returns the node corresponding to the interval in which the provided key falls.

Parameters:

key -

Returns:

the node for this key

getIntervalPosition

public int getIntervalPosition(DeweyIdentifier key)

Obtains the position in the nodes array that represents the interval in which the provided key falls.

Parameters:

key -

Returns:

the position if found, -1 otherwise

delete

public boolean delete(DeweyIdentifier key)

Returns false if key was not found. This method does not touch the left-most node in the array map, as the left-most node property of having keys smaller than the key of the left-most key will be kept if that key is deleted.

Parameters:

key -

Returns:

true if found, false if not

deleteAtPos

public void deleteAtPos(int pos)

Deletes the key-node mapping at the given position.

Parameters:

pos -

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

size

public int size()

addAtPos

public void addAtPos(DeweyIdentifier key,
                     int pos,
                     BTreeNode rightNode)

Adds the given mapping at the given position in this array.

Parameters:

key -

rightNode -

pos -