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

import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
import java.io.Serializable;
import java.util.function.IntBinaryOperator;
import java.util.ArrayList;
import java.util.List;
import net.ranides.assira.collection.lists.IntArrayList;
import net.ranides.assira.collection.lists.IntList;

@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public class IntRMQTree extends AIntRMQList implements Serializable {
    
    private static final int NONE = Integer.MAX_VALUE;
    
    private static final long serialVersionUID = 1L;
    
    @SuppressFBWarnings("SE_BAD_FIELD")
    protected final IntBinaryOperator fold;
    
    @SuppressFBWarnings("SE_BAD_FIELD")
    protected final IntStrategy segmenter;

    public IntRMQTree(IntBinaryOperator fold) {
        this(new MemoryIntSegmenter(), fold);
    }
    
    public IntRMQTree(IntStrategy segmenter, IntBinaryOperator fold) {
        this.fold = fold;
        this.segmenter = segmenter;
    }
    
    @Override
    public int getInt(int index) {
        return segmenter.get(0, index);
    }

    @Override
    public int findInt(int begin, int end) {
        if(begin<0 || end<=begin || end>size()) {
            throw new IndexOutOfBoundsException();
        }
        return findInt(Integer.MAX_VALUE, 0, begin, end);
    }
    
    private int findInt(int last, int level, int b, int e) {
        if( b >= e ) {
            return last;
        }
        if(1 == b % 2) {
            last = foldInt(last, get(level, b));
            b += 1;
        }
        if(1 == e % 2) {
            last = foldInt(last, get(level, e-1));
            e -= 1;
        }

        return findInt(last, level+1, b/2, e/2);
    }
    
    private int get(int level, int index) {
        return segmenter.get(level, index);
    }

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

    @Override
    public boolean add(int value) {
        int r = 0;
        int current = value;
        while(true) {
            if ( 0 != segmenter.add(r, current) % 2 ) {
                return true;
            }
            current = foldList(r);
            r += 1;
        }
    }
    
    @Override
    public void add(int index, int value) {
        if(index != size()) {
            throw new UnsupportedOperationException(index + " " +size());
        }
        add(value);
    }
    
    private int foldInt(int v1, int v2) {
        return NONE == v1 ? v2 : NONE == v2 ? v2 : fold.applyAsInt(v1, v2);
    }
    
    private int foldList(int r) {
        int n = segmenter.size(r);
        return foldInt( segmenter.get(r, n-1), segmenter.get(r, n-2));
    }
    
    private static class MemoryIntSegmenter implements IntStrategy, Serializable {
        
        private static final long serialVersionUID = 1L;
        
        protected final List<IntList> data = new ArrayList<>();

        @Override
        public int get(int level, int index) {
            return data.get(level).getInt(index);
        }

        @Override
        public int add(int level, int value) {
            if(data.size() < level) {
                throw new IndexOutOfBoundsException();
            }
            if(data.size() == level) {
                data.add(new IntArrayList());
            }
            data.get(level).add(value);
            return data.get(level).size();
        }

        @Override
        public int size(int level) {
            if(data.size() <= level) {
                return 0;
            }
            return data.get(level).size();
        }
        
    }
    
    public interface IntStrategy {

        int get(int level, int index);

        int add(int level, int value);

        int size(int level);

    }
    
}
