Class 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
    • 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
      • 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