Package org.h2.tools

Class MultiDimension

  • All Implemented Interfaces:
    java.util.Comparator<long[]>

    public class MultiDimension
    extends java.lang.Object
    implements java.util.Comparator<long[]>
    A tool to help an application execute multi-dimensional range queries. The algorithm used is database independent, the only requirement is that the engine supports a range index (for example b-tree).
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected MultiDimension()  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void addMortonRanges​(java.util.ArrayList<long[]> list, int[] min, int[] max, int len, int level)  
      private void combineEntries​(java.util.ArrayList<long[]> list, int total)
      Combine entries if the size of the list is too large.
      int compare​(long[] a, long[] b)  
      int deinterleave​(int dimensions, long scalar, int dim)
      Gets one of the original multi-dimensional values from a scalar value.
      private static int findMiddle​(int a, int b)  
      java.lang.String generatePreparedQuery​(java.lang.String table, java.lang.String scalarColumn, java.lang.String[] columns)
      Generates an optimized multi-dimensional range query.
      private static int getBitsPerValue​(int dimensions)  
      static MultiDimension getInstance()
      Get the singleton.
      int getMaxValue​(int dimensions)
      Get the maximum value for the given dimension count.
      private long[][] getMortonRanges​(int[] min, int[] max)
      Gets a list of ranges to be searched for a multi-dimensional range query where min <= value <= max.
      java.sql.ResultSet getResult​(java.sql.PreparedStatement prep, int[] min, int[] max)
      Executes a prepared query that was generated using generatePreparedQuery.
      private static int getSize​(int[] min, int[] max, int len)  
      long interleave​(int... values)
      Convert the multi-dimensional value into a one-dimensional (scalar) value.
      long interleave​(int x, int y)
      Convert the two-dimensional value into a one-dimensional (scalar) value.
      int normalize​(int dimensions, double value, double min, double max)
      Normalize a value so that it is between the minimum and maximum for the given number of dimensions.
      private static int roundUp​(int x, int blockSizePowerOf2)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.util.Comparator

        equals, reversed, thenComparing, thenComparing, thenComparing, thenComparingDouble, thenComparingInt, thenComparingLong
    • Constructor Detail

      • MultiDimension

        protected MultiDimension()
    • Method Detail

      • getInstance

        public static MultiDimension getInstance()
        Get the singleton.
        Returns:
        the singleton
      • normalize

        public int normalize​(int dimensions,
                             double value,
                             double min,
                             double max)
        Normalize a value so that it is between the minimum and maximum for the given number of dimensions.
        Parameters:
        dimensions - the number of dimensions
        value - the value (must be in the range min..max)
        min - the minimum value
        max - the maximum value (must be larger than min)
        Returns:
        the normalized value in the range 0..getMaxValue(dimensions)
      • getMaxValue

        public int getMaxValue​(int dimensions)
        Get the maximum value for the given dimension count. For two dimensions, each value must contain at most 32 bit, for 3: 21 bit, 4: 16 bit, 5: 12 bit, 6: 10 bit, 7: 9 bit, 8: 8 bit.
        Parameters:
        dimensions - the number of dimensions
        Returns:
        the maximum value
      • getBitsPerValue

        private static int getBitsPerValue​(int dimensions)
      • interleave

        public long interleave​(int... values)
        Convert the multi-dimensional value into a one-dimensional (scalar) value. This is done by interleaving the bits of the values. Each values must be between 0 (including) and the maximum value for the given number of dimensions (getMaxValue, excluding). To normalize values to this range, use the normalize function.
        Parameters:
        values - the multi-dimensional value
        Returns:
        the scalar value
      • interleave

        public long interleave​(int x,
                               int y)
        Convert the two-dimensional value into a one-dimensional (scalar) value. This is done by interleaving the bits of the values. Each values must be between 0 (including) and the maximum value for the given number of dimensions (getMaxValue, excluding). To normalize values to this range, use the normalize function.
        Parameters:
        x - the value of the first dimension, normalized
        y - the value of the second dimension, normalized
        Returns:
        the scalar value
      • deinterleave

        public int deinterleave​(int dimensions,
                                long scalar,
                                int dim)
        Gets one of the original multi-dimensional values from a scalar value.
        Parameters:
        dimensions - the number of dimensions
        scalar - the scalar value
        dim - the dimension of the returned value (starting from 0)
        Returns:
        the value
      • generatePreparedQuery

        public java.lang.String generatePreparedQuery​(java.lang.String table,
                                                      java.lang.String scalarColumn,
                                                      java.lang.String[] columns)
        Generates an optimized multi-dimensional range query. The query contains parameters. It can only be used with the H2 database.
        Parameters:
        table - the table name
        columns - the list of columns
        scalarColumn - the column name of the computed scalar column
        Returns:
        the query
      • getResult

        public java.sql.ResultSet getResult​(java.sql.PreparedStatement prep,
                                            int[] min,
                                            int[] max)
                                     throws java.sql.SQLException
        Executes a prepared query that was generated using generatePreparedQuery.
        Parameters:
        prep - the prepared statement
        min - the lower values
        max - the upper values
        Returns:
        the result set
        Throws:
        java.sql.SQLException - on failure
      • getMortonRanges

        private long[][] getMortonRanges​(int[] min,
                                         int[] max)
        Gets a list of ranges to be searched for a multi-dimensional range query where min <= value <= max. In most cases, the ranges will be larger than required in order to combine smaller ranges into one. Usually, about double as many points will be included in the resulting range.
        Parameters:
        min - the minimum value
        max - the maximum value
        Returns:
        the list of ranges (low, high pairs)
      • getSize

        private static int getSize​(int[] min,
                                   int[] max,
                                   int len)
      • combineEntries

        private void combineEntries​(java.util.ArrayList<long[]> list,
                                    int total)
        Combine entries if the size of the list is too large.
        Parameters:
        list - list of pairs(low, high)
        total - product of the gap lengths
      • compare

        public int compare​(long[] a,
                           long[] b)
        Specified by:
        compare in interface java.util.Comparator<long[]>
      • addMortonRanges

        private void addMortonRanges​(java.util.ArrayList<long[]> list,
                                     int[] min,
                                     int[] max,
                                     int len,
                                     int level)
      • roundUp

        private static int roundUp​(int x,
                                   int blockSizePowerOf2)
      • findMiddle

        private static int findMiddle​(int a,
                                      int b)