/*
 * @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 net.ranides.assira.collection.IntComparator;
import net.ranides.assira.collection.lists.IntList;
import net.ranides.assira.math.MathUtils;

@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public class IntRMQTable extends AIntRMQList implements Serializable {
    
    private static final long serialVersionUID = 1L;
    
    protected final IntComparator cmp;
    
    protected final IntList data;
    
    protected final int[][] spdata;

    public IntRMQTable(IntComparator cmp, IntList 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 int size() {
        return data.size();
    }

    @Override
    public int getInt(int index) {
        return data.get(index);
    }
    
    @Override
    public int findInt(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]);
    }

    private int minIndex(int i1, int i2) {
        int v1 = data.getInt(i1);
        int v2 = data.getInt(i2);
        return cmp.compare(v1, v2) < 0 ? i1 : i2;
    }
    
    private int minValue(int i1, int i2) {
        int v1 = data.getInt(i1);
        int v2 = data.getInt(i2);
        return cmp.compare(v1, v2) < 0 ? v1 : v2;
    }

}
