/*
 * @author Ranides Atterwim {@literal <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 net.ranides.assira.generic.CompareUtils;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * RMQTree is mutable collection which solves RMQ problem in O(logN) time.
 *
 * It requires O(N) memory.
 * Adding elements requires O(logN) time.
 * Solving RMQ requires O(logN) time.
 *
 * @param <T> type of value
 */
@SuppressWarnings({
    "PMD.AvoidReassigningParameters"
})
public class RMQTree<T> extends ARMQList<T> implements Serializable {
    
    private static final long serialVersionUID = 1L;
    
    @SuppressFBWarnings("SE_BAD_FIELD")
    protected final Comparator<T> cmp;
    
    @SuppressFBWarnings("SE_BAD_FIELD")
    protected final MemorySegmenter<T> segmenter;

    /**
     * Creates empty list.
     *
     * @param cmp cmp
     */
    public RMQTree(Comparator<T> cmp) {
        this.cmp = cmp;
        this.segmenter = new MemorySegmenter<>();
    }
    
    @Override
    public T get(int index) {
        return segmenter.get(0, index);
    }

    /**
     * Finds minimum value for range: requires O(logN) time.
     *
     * @param begin begin
     * @param end   end
     * @return value
     */
    @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);
    }

    /**
     * Adds value into list. Requires O(logN) time.
     *
     * @param value value
     * @return true
     */
    @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;
        }
    }

    /**
     * Adds value into list. Only end of the list is supported. Requires O(logN) time.
     *
     * @param index index
     * @param value value
     */
    @Override
    public void add(int index, T value) {
        if(index != size()) {
            throw new UnsupportedOperationException(index + " " +size());
        }
        add(value);
    }
    
    private T fold(T value1, T value2) {
        return null == value1 ? value2 : null == value2 ? null : CompareUtils.higher(cmp, value1, value2);
    }

    private 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 Serializable {
        
        private static final long serialVersionUID = 1L;
        
        private final List<List<T>> data = new ArrayList<>();

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

        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();
        }

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

}
