Class Search


  • public class Search
    extends java.lang.Object
    The search class provides binary searching on arrays. This is used to support searching arrays with duplicate values which the Java library binary search does not support.
    • Constructor Summary

      Constructors 
      Constructor Description
      Search()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static int binary​(int[] cols, int[] vals, Searchable data)
      Binary search on a collection of values in columns in a table.
      static int binary​(int col, int val, int lo, int hi, boolean findlow, Searchable arr)
      Binary searches for a value and returns the index to it.
      static int binary​(int col, int val, Searchable data)
      Helper function that acts like Search.binary(int[], int[], Searchable) but takes a single int for cols and vals to search just one column.
      static <T> T s​(T a, T b)
      Function used in swapping variables in one line.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • Search

        public Search()
    • Method Detail

      • s

        public static <T> T s​(T a,
                              T b)
        Function used in swapping variables in one line. Swapping should be done as follows: int a = 5; int b = 7; a = s(b, b = a); // now a = 7 and b = 5. Generic function provided that the variables to be swapped are the same type.
      • binary

        public static int binary​(int col,
                                 int val,
                                 int lo,
                                 int hi,
                                 boolean findlow,
                                 Searchable arr)
        Binary searches for a value and returns the index to it. Works on any given array that implements the ArraySearch interface. Note that the array must be sorted. Duplicate values may be included, in which case the 'findlow' parameter determines which end of the continuous block of values to search. If the search value is unique in the array then 'findlow' does not affect the returned index.
        Parameters:
        col - The column in the array to search, it should be an integer value.
        val - The value to be searched for.
        lo - The starting low index to begin searching from. This is included in the search.
        hi - The ending high index to end searching in. This index is EXCLUDED in the search, with the value below it being searched.
        findlow - True if the binary search should find the lowest value if there are duplicates, False if the binary search should find the highest value if there are duplicates.
        arr - The array object to be searched. This array object must implement the ArraySearch interface.
        Returns:
        The lowest/highest index to the value.
      • binary

        public static int binary​(int col,
                                 int val,
                                 Searchable data)
        Helper function that acts like Search.binary(int[], int[], Searchable) but takes a single int for cols and vals to search just one column. Internally it wraps directly to the raw binary search function.
      • binary

        public static int binary​(int[] cols,
                                 int[] vals,
                                 Searchable data)
        Binary search on a collection of values in columns in a table. This does not assume any relation between the columns, only that columns subsequently searched are sorted by value across the interval being searched. In practice this means that the data should be sorted by the first column, then the second column, then the third column etc. This function can search an arbitrary number of columns, including duplicate values. When searching the last column, if duplicate values are found the binary search will return the index of the lowest value.
        Parameters:
        cols - Array of column indicies to search in. cols[0] is searched first, then cols[1], then cols[2] etc.
        vals - Array of values to be searched for in their corresponding columns at the indices in cols. This array should be the same length as cols.
        data - An object implementing Searchable which holds the data to be searched.
        Returns:
        The index of the row that matches all the values in vals. Returns -1 if the value was not found or if cols and vals did not have equal lengths.