/*
 * Copyright 2004-2019 H2 Group. Multiple-Licensed under the MPL 2.0,
 * and the EPL 1.0 (http://h2database.com/html/license.html).
 * Initial Developer: H2 Group
 */
package org.h2.tools;

import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import org.h2.util.StringUtils;

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).
/**
 * 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).
 */
public class MultiDimension implements Comparator<long[]> {

    private static final MultiDimension INSTANCE = new MultiDimension();

    protected MultiDimension() {
        // don't allow construction by normal code
        // but allow tests
    }

    
Get the singleton.
Returns:
the singleton/**
     * Get the singleton.
     *
     * @return the singleton
     */
    public static MultiDimension getInstance() {
        return INSTANCE;
    }

    
Normalize a value so that it is between the minimum and maximum for the
given number of dimensions.
Params:
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)/**
     * Normalize a value so that it is between the minimum and maximum for the
     * given number of dimensions.
     *
     * @param dimensions the number of dimensions
     * @param value the value (must be in the range min..max)
     * @param min the minimum value
     * @param max the maximum value (must be larger than min)
     * @return the normalized value in the range 0..getMaxValue(dimensions)
     */
    public int normalize(int dimensions, double value, double min, double max) {
        if (value < min || value > max) {
            throw new IllegalArgumentException(min + "<" + value + "<" + max);
        }
        double x = (value - min) / (max - min);
        return (int) (x * getMaxValue(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.
Params:
dimensions – the number of dimensions
Returns:
the maximum value/**
     * 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.
     *
     * @param dimensions the number of dimensions
     * @return the maximum value
     */
    public int getMaxValue(int dimensions) {
        if (dimensions < 2 || dimensions > 32) {
            throw new IllegalArgumentException(Integer.toString(dimensions));
        }
        int bitsPerValue = getBitsPerValue(dimensions);
        return (int) ((1L << bitsPerValue) - 1);
    }

    private static int getBitsPerValue(int dimensions) {
        return Math.min(31, 64 / dimensions);
    }

    
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.
Params:
values – the multi-dimensional value
Returns:
the scalar value/**
     * 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.
     *
     * @param values the multi-dimensional value
     * @return the scalar value
     */
    public long interleave(int... values) {
        int dimensions = values.length;
        long max = getMaxValue(dimensions);
        int bitsPerValue = getBitsPerValue(dimensions);
        long x = 0;
        for (int i = 0; i < dimensions; i++) {
            long k = values[i];
            if (k < 0 || k > max) {
                throw new IllegalArgumentException(0 + "<" + k + "<" + max);
            }
            for (int b = 0; b < bitsPerValue; b++) {
                x |= (k & (1L << b)) << (i + (dimensions - 1) * b);
            }
        }
        return x;
    }

    
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.
Params:
x – the value of the first dimension, normalized
y – the value of the second dimension, normalized
Returns:
the scalar value/**
     * 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.
     *
     * @param x the value of the first dimension, normalized
     * @param y the value of the second dimension, normalized
     * @return the scalar value
     */
    public long interleave(int x, int y) {
        if (x < 0) {
            throw new IllegalArgumentException(0 + "<" + x);
        }
        if (y < 0) {
            throw new IllegalArgumentException(0 + "<" + y);
        }
        long z = 0;
        for (int i = 0; i < 32; i++) {
            z |= (x & (1L << i)) << i;
            z |= (y & (1L << i)) << (i + 1);
        }
        return z;
    }

    
Gets one of the original multi-dimensional values from a scalar value.
Params:
dimensions – the number of dimensions
scalar – the scalar value
dim – the dimension of the returned value (starting from 0)
Returns:
the value/**
     * Gets one of the original multi-dimensional values from a scalar value.
     *
     * @param dimensions the number of dimensions
     * @param scalar the scalar value
     * @param dim the dimension of the returned value (starting from 0)
     * @return the value
     */
    public int deinterleave(int dimensions, long scalar, int dim) {
        int bitsPerValue = getBitsPerValue(dimensions);
        int value = 0;
        for (int i = 0; i < bitsPerValue; i++) {
            value |= (scalar >> (dim + (dimensions - 1) * i)) & (1L << i);
        }
        return value;
    }

    
Generates an optimized multi-dimensional range query. The query contains
parameters. It can only be used with the H2 database.
Params:
table – the table name
columns – the list of columns
scalarColumn – the column name of the computed scalar column
Returns:
the query/**
     * Generates an optimized multi-dimensional range query. The query contains
     * parameters. It can only be used with the H2 database.
     *
     * @param table the table name
     * @param columns the list of columns
     * @param scalarColumn the column name of the computed scalar column
     * @return the query
     */
    public String generatePreparedQuery(String table, String scalarColumn,
            String[] columns) {
        StringBuilder buff = new StringBuilder("SELECT D.* FROM ");
        StringUtils.quoteIdentifier(buff, table).
            append(" D, TABLE(_FROM_ BIGINT=?, _TO_ BIGINT=?) WHERE ");
        StringUtils.quoteIdentifier(buff, scalarColumn).
            append(" BETWEEN _FROM_ AND _TO_");
        for (String col : columns) {
            buff.append(" AND ");
            StringUtils.quoteIdentifier(buff, col).
                append("+1 BETWEEN ?+1 AND ?+1");
        }
        return buff.toString();
    }

    
Executes a prepared query that was generated using generatePreparedQuery.
Params:
prep – the prepared statement
min – the lower values
max – the upper values
Returns:
the result set/**
     * Executes a prepared query that was generated using generatePreparedQuery.
     *
     * @param prep the prepared statement
     * @param min the lower values
     * @param max the upper values
     * @return the result set
     */
    public ResultSet getResult(PreparedStatement prep, int[] min, int[] max)
            throws SQLException {
        long[][] ranges = getMortonRanges(min, max);
        int len = ranges.length;
        Long[] from = new Long[len];
        Long[] to = new Long[len];
        for (int i = 0; i < len; i++) {
            from[i] = ranges[i][0];
            to[i] = ranges[i][1];
        }
        prep.setObject(1, from);
        prep.setObject(2, to);
        len = min.length;
        for (int i = 0, idx = 3; i < len; i++) {
            prep.setInt(idx++, min[i]);
            prep.setInt(idx++, max[i]);
        }
        return prep.executeQuery();
    }

    
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.
Params:
min – the minimum value
max – the maximum value
Returns:
the list of ranges (low, high pairs)/**
     * Gets a list of ranges to be searched for a multi-dimensional range query
     * where min &lt;= value &lt;= 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.
     *
     * @param min the minimum value
     * @param max the maximum value
     * @return the list of ranges (low, high pairs)
     */
    private long[][] getMortonRanges(int[] min, int[] max) {
        int len = min.length;
        if (max.length != len) {
            throw new IllegalArgumentException(len + "=" + max.length);
        }
        for (int i = 0; i < len; i++) {
            if (min[i] > max[i]) {
                int temp = min[i];
                min[i] = max[i];
                max[i] = temp;
            }
        }
        int total = getSize(min, max, len);
        ArrayList<long[]> list = new ArrayList<>();
        addMortonRanges(list, min, max, len, 0);
        combineEntries(list, total);
        return list.toArray(new long[0][]);
    }

    private static int getSize(int[] min, int[] max, int len) {
        int size = 1;
        for (int i = 0; i < len; i++) {
            int diff = max[i] - min[i];
            size *= diff + 1;
        }
        return size;
    }

    
Combine entries if the size of the list is too large.
Params:
list – list of pairs(low, high)
total – product of the gap lengths/**
     * Combine entries if the size of the list is too large.
     *
     * @param list list of pairs(low, high)
     * @param total product of the gap lengths
     */
    private void combineEntries(ArrayList<long[]> list, int total) {
        Collections.sort(list, this);
        for (int minGap = 10; minGap < total; minGap += minGap / 2) {
            for (int i = 0; i < list.size() - 1; i++) {
                long[] current = list.get(i);
                long[] next = list.get(i + 1);
                if (current[1] + minGap >= next[0]) {
                    current[1] = next[1];
                    list.remove(i + 1);
                    i--;
                }
            }
            int searched = 0;
            for (long[] range : list) {
                searched += range[1] - range[0] + 1;
            }
            if (searched > 2 * total || list.size() < 100) {
                break;
            }
        }
    }

    @Override
    public int compare(long[] a, long[] b) {
        return a[0] > b[0] ? 1 : -1;
    }

    private void addMortonRanges(ArrayList<long[]> list, int[] min, int[] max,
            int len, int level) {
        if (level > 100) {
            throw new IllegalArgumentException(Integer.toString(level));
        }
        int largest = 0, largestDiff = 0;
        long size = 1;
        for (int i = 0; i < len; i++) {
            int diff = max[i] - min[i];
            if (diff < 0) {
                throw new IllegalArgumentException(Integer.toString(diff));
            }
            size *= diff + 1;
            if (size < 0) {
                throw new IllegalArgumentException(Long.toString(size));
            }
            if (diff > largestDiff) {
                largestDiff = diff;
                largest = i;
            }
        }
        long low = interleave(min), high = interleave(max);
        if (high < low) {
            throw new IllegalArgumentException(high + "<" + low);
        }
        long range = high - low + 1;
        if (range == size) {
            long[] item = { low, high };
            list.add(item);
        } else {
            int middle = findMiddle(min[largest], max[largest]);
            int temp = max[largest];
            max[largest] = middle;
            addMortonRanges(list, min, max, len, level + 1);
            max[largest] = temp;
            temp = min[largest];
            min[largest] = middle + 1;
            addMortonRanges(list, min, max, len, level + 1);
            min[largest] = temp;
        }
    }

    private static int roundUp(int x, int blockSizePowerOf2) {
        return (x + blockSizePowerOf2 - 1) & (-blockSizePowerOf2);
    }

    private static int findMiddle(int a, int b) {
        int diff = b - a - 1;
        if (diff == 0) {
            return a;
        }
        if (diff == 1) {
            return a + 1;
        }
        int scale = 0;
        while ((1 << scale) < diff) {
            scale++;
        }
        scale--;
        int m = roundUp(a + 2, 1 << scale) - 1;
        if (m <= a || m >= b) {
            throw new IllegalArgumentException(a + "<" + m + "<" + b);
        }
        return m;
    }

}