Package com.mckoi.database

Class InsertSearch

java.lang.Object

com.mckoi.database.SelectableScheme

com.mckoi.database.CollatedBaseSearch

com.mckoi.database.InsertSearch

public final class InsertSearch
extends CollatedBaseSearch

This is a SelectableScheme similar in some ways to the binary tree. When a new row is added, it is inserted into a sorted list of rows. We can then use this list to select out the sorted list of elements.

This requires less memory than the BinaryTree, however it is not as fast. Even though, it should still perform fairly well on medium size data sets. On large size data sets, insert and remove performance may suffer.

This object retains knowledge of all set elements unlike BlindSearch which has no memory overhead.

Performance should be very comparable to BinaryTree for sets that aren't altered much.

Author:

Tobias Downer

Field Summary

Fields inherited from class com.mckoi.database.SelectableScheme

EMPTY_LIST, ONE_LIST

Constructor Summary

Constructors

Constructor	Description
InsertSearch(TableDataSource table, int column)	The Constructor.
InsertSearch(TableDataSource table, int column, IntegerVector vec)	Constructor sets the scheme with a pre-sorted list.

Method Summary

Modifier and Type	Method	Description
protected IntegerVector	addRangeToSet(int start, int end, IntegerVector ivec)	Adds the set indexes to the list that represent the range of values between the start (inclusive) and end offset (inclusive) given.
SelectableScheme	copy(TableDataSource table, boolean immutable)	Returns an exact copy of this scheme including any optimization information.
void	dispose()	Disposes this scheme.
protected TObject	firstInCollationOrder()	Returns the first value of this column (in collated order).
void	insert(int row)	Inserts a row into the list.
protected TObject	lastInCollationOrder()	Returns the last value of this column (in collated order).
void	readFrom(java.io.InputStream in)	Reads the entire state of the scheme from the input stream.
void	remove(int row)	Removes a row from the list.
protected int	searchFirst(TObject val)	Finds the position in the collated set of the first value in the column equal to the given value.
protected int	searchLast(TObject val)	Finds the position in the collated set of the last value in the column equal to the given value.
IntegerVector	selectAll()	The select operations for this scheme.
protected int	setSize()	The size of the set (the number of rows in this column).
void	writeTo(java.io.OutputStream out)	Writes the entire state of the scheme to the output stream.

Methods inherited from class com.mckoi.database.CollatedBaseSearch

selectRange, selectRange

Methods inherited from class com.mckoi.database.SelectableScheme

Debug, getCellContents, getColumn, getSubsetScheme, getSystem, getTable, internalOrderIndexSet, isImmutable, selectAllNonNull, selectBetween, selectEqual, selectFirst, selectGreater, selectGreaterOrEqual, selectLast, selectLess, selectLessOrEqual, selectNotEqual, selectNotFirst, selectNotLast, setImmutable, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

InsertSearch

public InsertSearch(TableDataSource table,
                    int column)

The Constructor.

InsertSearch

public InsertSearch(TableDataSource table,
                    int column,
                    IntegerVector vec)

Constructor sets the scheme with a pre-sorted list. The Vector 'vec' should not be used again after this is called. 'vec' must be sorted from low key to high key.

Method Detail

insert

public void insert(int row)

Inserts a row into the list. This will always be thread safe, table changes cause a write lock which prevents reads while we are writing to the table.

Overrides:

insert in class CollatedBaseSearch

remove

public void remove(int row)

Removes a row from the list. This will always be thread safe, table changes cause a write lock which prevents reads while we are writing to the table.

Overrides:

remove in class CollatedBaseSearch

readFrom

public void readFrom(java.io.InputStream in)
              throws java.io.IOException

Reads the entire state of the scheme from the input stream. Throws an exception if the scheme is not empty.

Overrides:

readFrom in class CollatedBaseSearch

Throws:

java.io.IOException

writeTo

public void writeTo(java.io.OutputStream out)
             throws java.io.IOException

Writes the entire state of the scheme to the output stream.

Overrides:

writeTo in class CollatedBaseSearch

Throws:

java.io.IOException

copy

public SelectableScheme copy(TableDataSource table,
                             boolean immutable)

Returns an exact copy of this scheme including any optimization information. The copied scheme is identical to the original but does not share any parts. Modifying any part of the copied scheme will have no effect on the original and vice versa.

Specified by:

copy in class SelectableScheme

dispose

public void dispose()

Disposes this scheme.

Overrides:

dispose in class CollatedBaseSearch

searchFirst

protected int searchFirst(TObject val)

Description copied from class: CollatedBaseSearch

Finds the position in the collated set of the first value in the column equal to the given value. If the value is not to be found in the column, it returns -(insert_position + 1).

Specified by:

searchFirst in class CollatedBaseSearch

searchLast

protected int searchLast(TObject val)

Description copied from class: CollatedBaseSearch

Finds the position in the collated set of the last value in the column equal to the given value. If the value is not to be found in the column, it returns -(insert_position + 1).

Specified by:

searchLast in class CollatedBaseSearch

setSize

protected int setSize()

Description copied from class: CollatedBaseSearch

The size of the set (the number of rows in this column).

Overrides:

setSize in class CollatedBaseSearch

firstInCollationOrder

protected TObject firstInCollationOrder()

Description copied from class: CollatedBaseSearch

Returns the first value of this column (in collated order). For example, if the column contains (1, 4, 8} then '1' is returned.

Overrides:

firstInCollationOrder in class CollatedBaseSearch

lastInCollationOrder

protected TObject lastInCollationOrder()

Description copied from class: CollatedBaseSearch

Returns the last value of this column (in collated order). For example, if the column contains (1, 4, 8} then '8' is returned.

Overrides:

lastInCollationOrder in class CollatedBaseSearch

addRangeToSet

protected IntegerVector addRangeToSet(int start,
                                      int end,
                                      IntegerVector ivec)

Description copied from class: CollatedBaseSearch

Adds the set indexes to the list that represent the range of values between the start (inclusive) and end offset (inclusive) given.

Overrides:

addRangeToSet in class CollatedBaseSearch

selectAll

public IntegerVector selectAll()

The select operations for this scheme.

Overrides:

selectAll in class CollatedBaseSearch