/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.rmq;

import java.io.Serializable;
import java.util.Comparator;
import java.util.List;
import net.ranides.assira.math.MathUtils;

@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public class RMQTable<T> extends ARMQList<T> implements Serializable {
    
    private static final long serialVersionUID = 1L;
    
    protected final Comparator<? super T> cmp;
    
    protected final List<T> data;
    
    protected final int[][] spdata;

    public RMQTable(Comparator<? super T> cmp, List<T> input) {
        int N = input.size();
        int L = MathUtils.log2floor(N) + 1;
        this.cmp = cmp;
        this.data = input;
        this.spdata = new int[N][L];

        for(int i=0; i<N; i++) {
            spdata[i][0] = i;
        }
        for(int j=1; (1<<j)<=N; j++) {
            for(int i=0; i + (1<<j)-1 < N; i++) {
                spdata[i][j] = minIndex(spdata[i][j - 1], spdata[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    
    @Override
    public T find(int begin, int end) {
        if(begin<0 || end<=begin || end>size()) {
            throw new IndexOutOfBoundsException();
        }
        end--;
        int k = MathUtils.log2floor(end-begin+1);
        return minValue(spdata[begin][k], spdata[end - (1<<k) +1 ][k]);
    }

    @Override
    public int size() {
        return data.size();
    }

    @Override
    public T get(int index) {
        return data.get(index);
    }

    private int minIndex(int i1, int i2) {
        T var1 = data.get(i1);
        T var2 = data.get(i2);
        return cmp.compare(var1, var2) < 0 ? i1 : i2;
    }
    
    private T minValue(int i1, int i2) {
        T var1 = data.get(i1);
        T var2 = data.get(i2);
        return cmp.compare(var1, var2) < 0 ? var1 : var2;
    }

}
