/*
 * @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.BinaryOperator;
import java.util.ArrayList;
import java.util.List;

@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public class RMQTree<T> extends ARMQList<T> implements Serializable {
    
    private static final long serialVersionUID = 1L;
    
    @SuppressFBWarnings("SE_BAD_FIELD")
    protected final BinaryOperator<T> fold;
    
    @SuppressFBWarnings("SE_BAD_FIELD")
    protected final Strategy<T> segmenter;
    
    public RMQTree(BinaryOperator<T> function) {
        this(new MemorySegmenter<>(), function);
    }
    
    public RMQTree(Strategy<T> segmenter, BinaryOperator<T> fold) {
        this.fold = fold;
        this.segmenter = segmenter;
    }
    
    @Override
    public T get(int index) {
        return segmenter.get(0, index);
    }

    @Override
    public T find(int begin, int end) {
        if(begin<0 || end<=begin || end>size()) {
            throw new IndexOutOfBoundsException();
        }
        return find(null, 0, begin, end);
    }
    
    private T find(T last, int level, int b, int e) {
        if( b >= e ) {
            return last;
        }
        if(1 == b % 2) {
            last = fold(last, segmenter.get(level,b));
            b += 1;
        }
        if(1 == e % 2) {
            last = fold(last, segmenter.get(level,e-1));
            e -= 1;
        }

        return find(last, level+1, b/2, e/2);
    }
    
    @Override
    public int size() {
        return segmenter.size(0);
    }

    @Override
    public boolean add(T value) {
        int r = 0;
        T current = value;
        while(true) {
            if ( 0 != segmenter.add(r, current) % 2 ) {
                return true;
            }
            current = foldList(r);
            r += 1;
        }
    }
    
    protected T fold(T value1, T value2) {
        return null == value1 ? value2 : null == value2 ? null : fold.apply(value1, value2);
    }
    
    protected T foldList(int r) {
        int n = segmenter.size(r);
        return fold( segmenter.get(r, n-1), segmenter.get(r, n-2));
    }
    
    private static class MemorySegmenter<T> implements Strategy<T>, Serializable {
        
        private static final long serialVersionUID = 1L;
        
        private final List<List<T>> data = new ArrayList<>();

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

        @Override
        public int add(int level, T value) {
            if(data.size() < level) {
                throw new IndexOutOfBoundsException();
            }
            if(data.size() == level) {
                data.add(new ArrayList<>());
            }
            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 Strategy<T> {

        T get(int level, int index);

        int add(int level, T value);

        int size(int level);

    }
    
}
