ch.ethz.mxquery.sms.btree
Class LeafArrayMap

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

public class LeafArrayMap
extends java.lang.Object

Helper for b-tree leaves. Has to be taylored to different key and value types manually as Generics would use Complex type (inefficent) instead of native types.

Constructor Summary

LeafArrayMap(int n)
Instantiates a Leaf Array Map

Method Summary

void	addAtPos(DeweyIdentifier key, LinguisticToken value, int pos) Adds the given mapping at the given position in this array.
int	binarySearch(java.util.Vector a, DeweyIdentifier key, int from, int to) This binary search method is modified to guarantee that, in the presence of duplicate keys, we will always return the first occurrence of a found key in the portion of the array being searched (from-to).
int	continueGet(int pos, DeweyIdentifier key, BtreePushOperator results)
int	continueScan(int pos, DeweyIdentifier highKey, BtreePushOperator results)
void	deleteAtPos(int i) Deletes the value and key at position i
int	get(DeweyIdentifier key, BtreePushOperator results) Gets the values for the specified key and pushes them in the given push operator.
int	getFirstKeyAfter(DeweyIdentifier key, int[] atPos)
int	getLastKeyBefore(DeweyIdentifier key, int[] atPos)
DeweyIdentifier	getMidKey()
int	queryRange(DeweyIdentifier lowKey, DeweyIdentifier highKey, BtreePushOperator results) Obtains all values mapped to the given key range in this array.
boolean	remove(DeweyIdentifier key, LinguisticToken value) Remove mappings with the given key.
int	size()
LeafArrayMap	split() Splits this map.
java.lang.String	toString()
boolean	tryAdd(DeweyIdentifier key, LinguisticToken value) Associates the given key with the given value in this array map, if the insertion point for the key may be found here.

Methods inherited from class java.lang.Object

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

Constructor Detail

LeafArrayMap

public LeafArrayMap(int n)

Instantiates a Leaf Array Map

Parameters:

n - the size of the LeafArrayMap

Method Detail

binarySearch

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

This binary search method is modified to guarantee that, in the presence of duplicate keys, we will always return the first occurrence of a found key in the portion of the array being searched (from-to).

Parameters:

a -

key -

from -

to -

Returns:

the position of the key

getMidKey

public DeweyIdentifier getMidKey()

split

public LeafArrayMap split()

Splits this map. The split operation will attempt to split this map in the middle key.

Returns:

the right node

tryAdd

public boolean tryAdd(DeweyIdentifier key,
                      LinguisticToken value)

Associates the given key with the given value in this array map, if the insertion point for the key may be found here. If that is not the case, the method will return true, indicating that the search for the insertion point should be continued on the next array.

Parameters:

key -

value -

Returns:

true if the search should continue

addAtPos

public void addAtPos(DeweyIdentifier key,
                     LinguisticToken value,
                     int pos)

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

Parameters:

key -

value -

pos -

get

public int get(DeweyIdentifier key,
               BtreePushOperator results)

Gets the values for the specified key and pushes them in the given push operator. If we have scanned until the last position of this array, then maybe more values can be found in the next array. This method returns true in this situation.

getFirstKeyAfter

public int getFirstKeyAfter(DeweyIdentifier key,
                            int[] atPos)

getLastKeyBefore

public int getLastKeyBefore(DeweyIdentifier key,
                            int[] atPos)

continueGet

public int continueGet(int pos,
                       DeweyIdentifier key,
                       BtreePushOperator results)

remove

public boolean remove(DeweyIdentifier key,
                      LinguisticToken value)

Remove mappings with the given key. If a value is given, then only a single mapping is removed. If BTreeConstants.ALL_MAPPINGS is given, then all mappings for the given key are removed. Returns true if removal must continue searching on the next leaf.

Parameters:

key -

value -

Returns:

true if the key was found, false otherwise

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

size

public int size()

queryRange

public int queryRange(DeweyIdentifier lowKey,
                      DeweyIdentifier highKey,
                      BtreePushOperator results)

Obtains all values mapped to the given key range in this array. If the search stops in the last position of the array, then this method returns true, flagging that continuing to the next array is necessary.

Parameters:

lowKey -

highKey -

results -

Returns:

the status of the search: CONTINUE_WITH_SCAN, CONTINUE_WITH_BINSEARCH

continueScan

public int continueScan(int pos,
                        DeweyIdentifier highKey,
                        BtreePushOperator results)

deleteAtPos

public void deleteAtPos(int i)

Deletes the value and key at position i

Parameters:

i - the position the key and value is deleted at