/* UtilLib - Copyright (c) 2006-2020 Vincent Calame - Exemole
 * Logiciel libre donné sous triple licence :
 * 1) selon les termes de la CeCILL V2
 * 2) selon les termes de l’EUPL V.1.1
 * 3) selon les termes de la GNU GPLv3
 * Voir le fichier licences.txt
 */


package net.mapeadores.util.primitives;

import java.util.AbstractList;
import java.util.RandomAccess;


/**
 *
 * @author Vincent Calame
 */
public class Ranges extends AbstractList<Range> implements RandomAccess {

    private int size = 0;
    private Range[] rangeArray = new Range[2];
    private int globalMin = Range.MAXIMUM;
    private int globalMax = Range.MINIMUM;

    public Ranges() {
    }

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

    @Override
    public Range get(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException();
        }
        return rangeArray[index];
    }

    public int getGlobalMin() {
        return globalMin;
    }

    public int getGlobalMax() {
        return globalMax;
    }

    public boolean contains(int value) {
        if ((value < globalMin) || (value > globalMax)) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            if (rangeArray[i].contains(value)) {
                return true;
            }
        }
        return false;
    }

    /**
     *
     * @throws IllegalArgumentException si range est nul
     */
    public void addRange(Range range) {
        if (range == null) {
            throw new IllegalArgumentException("range is null");
        }
        if (size == 0) {
            rangeArray[0] = range;
            globalMin = range.min();
            globalMax = range.max();
            size = 1;
            return;
        }
        if (range.min() == (globalMax + 1)) {
            rangeArray[size - 1] = rangeArray[size - 1].union(range);
            globalMax = range.max();
        } else if (range.min() > globalMax) {
            checkLength();
            rangeArray[size] = range;
            size++;
            globalMax = range.max();
        } else if (range.max() == (globalMin - 1)) {
            rangeArray[0] = rangeArray[0].union(range);
            if (size > 1) {
                mergeFollowing(0);
            }
            globalMin = range.min();
        } else if (range.max() < globalMin) {
            checkLength();
            System.arraycopy(rangeArray, 0, rangeArray, 1, size);
            rangeArray[0] = range;
            globalMin = range.min();
            size++;
        } else {
            globalMin = Math.min(globalMin, range.min());
            globalMax = Math.max(globalMax, range.max());
            mergeRanges(range);
        }
    }

    private void mergeRanges(Range range) {
        int nearestIndex = -1;
        for (int i = 0; i < size; i++) {
            Range current = rangeArray[i];
            if (current.intersects(range) || current.isNeighbour(range)) {
                Range union = current.union(range);
                if (union.equals(current)) {
                    return;
                }
                rangeArray[i] = union;
                if (i < (size - 1)) {
                    mergeFollowing(i);
                }
                return;
            } else {
                if (current.max() < range.min()) {
                    nearestIndex = i;
                }
            }
        }
        nearestIndex = nearestIndex + 1;
        int nvlength = (size == rangeArray.length) ? size * 2 : rangeArray.length;
        Range[] temp = new Range[nvlength];
        System.arraycopy(rangeArray, 0, temp, 0, nearestIndex);
        temp[nearestIndex] = range;
        System.arraycopy(rangeArray, nearestIndex, temp, nearestIndex + 1, (size - nearestIndex));
        rangeArray = temp;
        size++;
    }

    private void mergeFollowing(int index) {
        int length = 0;
        Range start = rangeArray[index];
        for (int i = index + 1; i < size; i++) {
            Range current = rangeArray[i];
            if (current.intersects(start) || current.isNeighbour(start)) {
                length++;
                start = start.union(current);
            } else {
                break;
            }
        }
        if (length > 0) {
            rangeArray[index] = start;
            for (int i = index + length + 1; i < size; i++) {
                rangeArray[i - length] = rangeArray[i];
            }
            for (int i = size - length; i < size; i++) {
                rangeArray[i] = null;
            }
            size = size - length;
        }
    }

    private void checkLength() {
        if (size == rangeArray.length) {
            Range[] nv = new Range[size * 2];
            System.arraycopy(rangeArray, 0, nv, 0, size);
            rangeArray = nv;
        }
    }

}
