package hep.aida.ref.function;

/*
 * RangeSet.java
 *
 * Created on September, 2002, 3:23 PM
 */

import hep.aida.*;
import hep.aida.ext.IRange;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 *
 * This class handles multiple ranges along one axis.
 * Overlapping ranges are merged in one bigger range.
 *
 * @author Tony Johnson, Victor Serbo, Max Turri
 *
 */
public class RangeSet implements IRangeSet {
    
    private static Pattern pattern = Pattern.compile("\\s*\\(\\s*([\\-?|\\+?]?\\d*.?\\d*)\\s*,\\s*([\\-?|\\+?]?\\d*.?\\d*)\\s*\\)\\s*");
    private ArrayList set;
    private boolean rangeChanged;
    private Random r = new Random();
    
    /**
     * Creates RangeSet with (-infinity, +infinity) valid interval, borders excluded
     */
    public RangeSet() {
        rangeChanged = true;
        set = new ArrayList();
        
        Range r = new Range();
        set.add(r);
    }
    
    /*
     * Creates RangeSet with a valid interval (xMin, xMax), borders excluded.
     */
    public RangeSet(double xMin, double xMax) {
        rangeChanged = true;
        set = new ArrayList();
        
        Range r = new Range(xMin, xMax);;
        set.add(r);
    }
    
    /*
     * Creates RangeSet with valid intervals:
     * (xMin[0], xMax[0]), (xMin[1], xMax[1]), ... , borders excluded.
     */
    public RangeSet(double[] xMin, double[] xMax) {
        buildRange(xMin, xMax);
    }
    
    /**
     * Create a RangeSet from a String.
     * Ranges can be specified as:
     * (,-9),(-1.,0.),(2.,3.),(5,)
     *
     */
    public RangeSet(String range) {

        Matcher matcher = pattern.matcher(range);
        int count = 0;
        while (matcher.find())
            count++;
        
        double[] xMax = new double[count];
        double[] xMin = new double[count];
        
        count = 0;
        while (matcher.find()) {
            String maxStr = matcher.group(2);
            if ( maxStr.equals("") )
                xMax[count] = Double.POSITIVE_INFINITY;
            else
                xMax[count] = Double.parseDouble(maxStr);
            
            

            String minStr = matcher.group(1);
            if ( minStr.equals("") )
                xMin[count] = Double.NEGATIVE_INFINITY;
            else
                xMin[count] = Double.parseDouble(minStr);
            
            count++;
        }
        buildRange(xMin, xMax);
    }

    private void buildRange(double[] xMin, double[] xMax) {
        rangeChanged = true;
        if (xMin.length != xMax.length)
            throw new IllegalArgumentException("xMin and xMax arrays must have the same size.");
        set = new ArrayList();
        
        Range r = new Range(xMin[0], xMax[0]);
        set.add(r);
        if (xMin.length > 1)
            for (int i=1; i<xMin.length; i++) { include(xMin[i], xMax[i]); }
    }
    
    
    public double  PLUS_INF() { return Double.POSITIVE_INFINITY; }
    
    public double MINUS_INF() { return Double.NEGATIVE_INFINITY; }
    
    /** Returns current number of disjoint ranges (non-overlapping intervals) */
    public int size() { return set.size(); }
    
    public double length() {
        if ( size() == 0 ) throw new RuntimeException("No length for this Range set");
        double length = 0;
        for (int i=0; i<size(); i++) length += ((Range) set.get(i)).upperBound() - ((Range) set.get(i)).lowerBound();
        return length;
    }
    
    public double generatePoint() {
        //        double rnd = r.nextDouble();
        double rnd = Math.random();
        double l = length();
        double pl = 0;
        for (int i=0; i<size(); i++) {
            double rub = ((Range) set.get(i)).upperBound();
            double rlb = ((Range) set.get(i)).lowerBound();
            pl += rub - rlb;
            if ( rnd < pl/l )
                return rlb + ((pl/l)-rnd)*l;
        }
        throw new RuntimeException("Problem with generating a point in the RangeSet");
    }
    
    
    /** Return array of lower or upper Bounds for the current set of ranges */
    public double[] lowerBounds() {
        if (size() == 0) return null;
        
        double[] tmp = new double[size()];
        for (int i=0; i<size(); i++) tmp[i] = ((Range) set.get(i)).lowerBound();
        return tmp;
    }
    public double[] upperBounds() {
        if (size() == 0) return null;
        
        double[] tmp = new double[size()];
        for (int i=0; i<size(); i++) tmp[i] = ((Range) set.get(i)).upperBound();
        return tmp;
    }
    
    /**
     * Set the range from xMin to xMax
     * This method first does "excludeAll", then "includeRange"
     */
    /*
    public void setRange(double xMin, double xMax) {
        rangeChanged = true;
        set = new ArrayList();
     
        Range r = new Range(xMin, xMax);
        set.add(r);
    }
     */
    
    /**
     * Additive include/exclude of the range in given axis.
     */
    public void include(double xMin, double xMax) {
        rangeChanged = true;
        if (xMin > xMax)
            throw new IllegalArgumentException("xMax must be bigger tnan xMin.");
        
        int r1 = -1;
        int r2 = -1;
        boolean range1 = true;
        boolean range2 = true;
        double min = Double.NaN;
        double max = Double.NaN;
        
        // No ranges added before
        if (set.size() == 0) {
            set.add(new Range(xMin, xMax));
            return;
        }
        
        // New range cover all valid intervals or more
        if (((Range) set.get(set.size()-1)).upperBound()<=xMax && ((Range) set.get(0)).lowerBound()>=xMin) {
            //setRange(xMin, xMax);
            excludeAll();
            include(xMin, xMax);
            return;
        }
        
        // New range is above highest valid point
        if (((Range) set.get(set.size()-1)).upperBound()<xMin) {
            set.add(new Range(xMin, xMax));
            return;
        }
        
        // New range is below lowest valid point
        if (((Range) set.get(0)).lowerBound()>xMax) {
            insert(0, new Range(xMin, xMax));
            return;
        }
        
        // All other cases
        range1 = true;
        r1 = inRange(xMin);
        if (r1<0) {
            range1 = false;
            r1 = inGap(xMin);
            min = xMin;
        } else {
            min = ((Range) set.get(r1)).lowerBound();
        }
        
        range2 = true;
        r2 = inRange(xMax);
        if (r2<0) {
            range2 = false;
            r2 = inGap(xMax);
            max = xMax;
        } else {
            max = ((Range) set.get(r2)).upperBound();
        }
        
        // New range is inside one of existing ranges - do nothing
        if (range1 && range2 && (r1 == r2)) return;
        
        // New range edges fall in the gap between existing ranges
        if (!range1 && !range2 && (r1 == r2)) {
            insert(r1, new Range(min, max));
            return;
        }
        
        // New range bridges several ranges - replace them with one big range
        if (range2) {
            remove(r1, r2);
            insert(r1, new Range(min, max));
            return;
        } else if (!range2) {
            remove(r1, r2-1);
            insert(r1, new Range(min, max));
            return;
        }
    }
    
    public void exclude(double xMin, double xMax) {
        rangeChanged = true;
        if (xMin > xMax)
            throw new IllegalArgumentException("xMax must be bigger than xMin.");
        
        int r1 = -1;
        int r2 = -1;
        boolean range1 = true;
        boolean range2 = true;
        double min = Double.NaN;
        double max = Double.NaN;
        
        // No ranges added before - everything is already excluded, do nothing
        if (set.size() == 0) {
            return;
        }
        
        // Exclude range cover all valid intervals or more - exclude all
        if (((Range) set.get(set.size()-1)).upperBound()<=xMax && ((Range) set.get(0)).lowerBound()>=xMin) {
            excludeAll();
            return;
        }
        
        // New exclude range is above highest valid point - do nothing
        if (((Range) set.get(set.size()-1)).upperBound()<xMin) {
            return;
        }
        
        // New exclude range is below lowest valid point - do nothing
        if (((Range) set.get(0)).lowerBound()>xMax) {
            return;
        }
        
        // All other cases
        range1 = true;
        r1 = inRange(xMin);
        if (r1<0) {
            range1 = false;
            r1 = inGap(xMin);
            min = xMin;
        } else {
            min = ((Range) set.get(r1)).lowerBound();
        }
        
        range2 = true;
        r2 = inRange(xMax);
        if (r2<0) {
            range2 = false;
            r2 = inGap(xMax);
            max = xMax;
        } else {
            max = ((Range) set.get(r2)).upperBound();
        }
        
        //  New exclude range starts and ends in the gap
        if (!range1 && !range2) {
            if (r1 == r2) return;
            else {
                remove(r1, r2-1);
                return;
            }
        } else {
            // New exclude range starts on the valid include range
            if (range1) {
                insert(r1, new Range(min, xMin));
                r1++;
                r2++;
            }
            // New exclude range ends on the valid include range
            if (range2) {
                insert(r2+1, new Range(xMax, max));
            } else r2--;
            
            remove(r1, r2);
            
        }
        
    }
    
    /**
     * Set full range in all axes.
     */
    public void includeAll() {
        rangeChanged = true;
        set = new ArrayList();
        
        Range r = new Range();
        set.add(r);
    }
    
    /**
     * Set empty range in all axes.
     */
    public void excludeAll() {
        rangeChanged = true;
        set = new ArrayList();
    }
    
    public boolean isInRange(double point) {
        if (set.size() == 0) return false;
        for (int i=0; i<set.size(); i++) {
            if (((Range) set.get(i)).isInRange(point)) return true;
        }
        return false;
    }
    
    private int inRange(double point) {
        //System.out.println("inRange  point="+point);
        if (set.size() == 0) return -1;
        for (int i=0; i<set.size(); i++) {
            if (((Range) set.get(i)).isInRange(point)) return i;
        }
        return -1;
    }
    
    private int inGap(double point) {
        //System.out.println("inGap    point="+point+"   set.size() = "+set.size());
        if (set.size() == 0) return -1;
        if (((Range) set.get(0)).lowerBound()>point) return 0;
        if (((Range) set.get(set.size()-1)).upperBound()<point) return set.size();
        for (int i=0; i<set.size()-1; i++) {
            //System.out.println("     upper: "+((Range) set.get(i)).upperBound());
            //System.out.println("     lower: "+((Range) set.get(i+1)).lowerBound());
            if (((Range) set.get(i)).upperBound()<point && ((Range) set.get(i+1)).lowerBound()>point) { return i+1; }
        }
        //System.out.println("     Gap End");
        return -1;
    }
    
    /*
     * Inserts Range into the specified position of the Set
     * Indexing runs [0, set.size()]
     */
    private void insert(int index, Range r) {
        if (index>set.size() || index<0 )
            throw new IllegalArgumentException("Wrong index: "+index+", Set size="+set.size());
        //System.out.println("insert1:Size: "+set.size()+" index="+index);
        if (index == set.size()) {
            set.add(r);
            return;
        }
        
        ArrayList tmp = new ArrayList();
        
        for (int i=0; i<set.size()+1; i++) {
            if      (i < index) tmp.add((Range) set.get(i));
            else if (i == index) tmp.add(r);
            else if (i > index) tmp.add((Range) set.get(i-1));
        }
        //System.out.println("insert2:Size: "+tmp.size());
        set = tmp;
    }
    
    /*
     * Removes ranges from the set, (index1 - index2), inclusive.
     * Indexing runs [0, set.size()-1]
     */
    private void remove(int index1, int index2) {
        //System.out.println("remove: Size: "+set.size()+" index1="+index1+",  index2="+index2);
        if (index1>index2 || index1>=set.size() || index2>=set.size() || index1<0 || index2<0)
            throw new IllegalArgumentException("Wrong index: index1="+index1+
                    ", index2="+index2+", Set size="+set.size());
        ArrayList tmp = new ArrayList();
        
        for (int i=0; i<set.size(); i++) if (i<index1 || i>index2) tmp.add((Range) set.get(i));
        
        //System.out.println("remove: Size: "+tmp.size());
        set = tmp;
    }
    
    // Test RangeSet here
    public static void main(String[] args) {
        RangeSet set = new RangeSet();
        
        set.print();
        
        set.excludeAll();
        set.print();
        
        set.include(5.5, 7.6);
        set.print();
        
        set.include(14.5, 17.6);
        set.print();
        
        set.include(9.5, 12.6);
        set.print();
        
        set.include(6.5, 10.6);
        set.print();
        
        set.include(1.5, 3.6);
        set.print();
        
        set.include(5.1, 18.6);
        set.print();
        
        System.out.println("\n ****************** Start Excluding ******************\n");
        
        set.exclude(14.2, 16.7);
        set.print();
        
        set.exclude(7.2, 10.3);
        set.print();
        
        set.exclude(4.9, 11.4);
        set.print();
        
        set.exclude(2.1, 12.1);
        set.print();
        
        set.exclude(17.0, 18.0);
        set.print();
        
    }
    
    private void print() {
        System.out.println("\n\n Size: "+set.size());
        for (int i=0; i<set.size(); i++) { System.out.println(i + "\t lowerBound = " + ((Range) set.get(i)).lowerBound() +
                ",\t upperBound = " + ((Range) set.get(i)).upperBound()); }
        System.out.println("");
        for (int i=0; i<20; i++) {
            System.out.println(i +"\t "+ isInRange(i*1.));
        }
    }
}