/*******************************************************************************
 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
 * in Industry THTH ry.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *     VTT Technical Research Centre of Finland - initial API and implementation
 *******************************************************************************/
package org.simantics.utils.datastructures;

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

/**
 * Segment consists of a start and a end value. Both start and end are inclusive.  
 * 
 * @See {@link SegmentSet}
 * @author Toni Kalajainen
 */
public final class Segment implements Comparable<Segment>, Serializable, Cloneable {

	public static final Segment ALL = new Segment(-Double.MAX_VALUE, Double.MAX_VALUE);
	public static final Segment[] NO_RANGES = new Segment[0];
	
    /**
     * Define serial version of this class
	 */
	private static final long serialVersionUID = 2979572023736175492L;

	/** start Data */
    private double start;

    /** end Data */
    private double end;

    /**
     * Create a new segment at a single value
     *  
     * @param value value
     * @return segment
     */
    public static Segment at(double value)
    {
   		return new Segment(value, value);
    }
    
    /**
     * Create the segment between two values
     *  
     * @param d1 value 1
     * @param d2 value 2
     * @return segment
     */
    public static Segment of(double d1, double d2)
    {
    	if (d1<d2) 
    		return new Segment(d1, d2);
    	else
    		return new Segment(d2, d1);
    }
    
    /**
     * Create a segment. Start and end are included.
     * Start value must be smaller that end value.
     * 
     * @param start the start time
     * @param end the end time
     */
    public Segment(double start, double end) {
    	if (start>end)
    		throw new IllegalArgumentException("Start is after end");
    	this.start = start;
    	this.end = end;
    }
    
    /**
     * Create single point
     * 
     * @param data Data point 
     */
    public Segment(double data) {
        start = data;
        end = data;
    }
    
    /**
     * Create as segment.
     * @param data
     */
    public Segment(double[] data) {
    	assert(data.length ==2);
    	start = data[0];
    	end = data[1];
    	if (start>end)
    		throw new IllegalArgumentException("Start is after end");
    	
    }

    /**
     * Get the end Data
     * 
     * @return the end Data
     */
    public double getEnd() {
        return end;
    }

    /**
     * Get the start Data
     * 
     * @return the Data
     */
    public double getStart() {
        return start;
    }

    /**
     * Get the length of the Data
     * 
     * @return the length
     */
    public double getLength() {
        return end - start;
    }

    public Segment createWithNewStart(double newStartData) {
        return new Segment(newStartData, end);
    }

    public Segment createWithNewEnd(double newEndData) {
        return new Segment(start, newEndData);
    }

    /**
     * Creates a one element array
     * 
     * @return the 1-element array
     */
    public Segment[] toArray() {
        Segment[] array = new Segment[1];
        array[0] = this;
        return array;
    }
    
    /**
     * Tests wheter this segment contains value
     * 
     * @param value the value
     * @return true if the value is within the segment
     */
    public boolean contains(double value) {
        return (value>=start && value<=end);
    }
    
    /**
     * Tests whether this segment fully contains s
     * 
     * @param s segment
     * @return Returns true if this segment contains s
     */
    public boolean contains(Segment s) {
        return (start<=s.start && end>=s.end);
    }
    
    /**
     * Tests whether s intersects or is parallel to this segment.
     * 
     * @param s segment
     * @return true if the two segments intersect or are parallel
     */
    public boolean parallelWith(Segment s) {
        if (s.start > this.end) return false;
        if (s.end < this.start) return false;
        return true;
    }

    /**
     * Tests whether s intersects with this segment
     *  
     * @param s segment
     * @return true if they intersect 
     */
    public boolean intersects(Segment s) {
        if (s.start >= this.end) return false;
        if (s.end <= this.start) return false;
        return true;
    }
    
    /**
     * Extends the segment with another.
     *  
     * @param s other segment
     * @return new segment containing both segments
     */
    public Segment extendWith(Segment s) {
    	if (contains(s)) return this;
    	if (s.contains(this)) return s;
        double newStart = this.start;
        if (s.start<newStart) newStart = s.start;
        double newEnd = this.end;
        if (s.end>newEnd) newEnd = s.end;
        return new Segment(newStart, newEnd);
    }
    
    /**
     * Extends this segment so that value is included.
     * 
     * @param value a value
     * @return new segment that includes the value
     */
    public Segment extendWith(double value) {
    	if (this.contains(value)) return this;
        return new Segment((value<start?value:start),(value>end?value:end));
    }
    
    /**
     * Create an intersection of this and s
     * 
     * @param s segment
     * @return the intersection
     */
    public Segment[] intersection(Segment s) {
        Segment list[] = new Segment[2];
        list[0] = this;
        list[1] = s;
        return Segment.intersection(list);
    }

    /**
     * Create an union of this and s
     * 
     * @param s segment
     * @return the union
     */
    public Segment[] union(Segment range) {
        Segment list[] = new Segment[2];
        list[0] = this;
        list[1] = range;
        return Segment.union(list);
    }

    /**
     * Create intersection
     * 
     * @param segments1 group of Data range
     * @param segments2 group of Data range
     * @return the intersection
     */
    public static Segment[] intersection(Segment segments1[],
            Segment segments2[]) {
        return intersection(concat(segments1, segments2));
    }
    
    /**
     * Create union
     * 
     * @param segments1 group of segments
     * @param segments2 group of segments
     * @return the union
     */
    public static Segment[] union(Segment segments1[], Segment segments2[]) {
        return union(concat(segments1, segments2));
    }
    
    /**
     * Returns difference of segments 
     * 
     * @param group
     * @param cutWith
     * @return
     */
    public static Segment[] difference(Segment group[], Segment cutWith) {
    	if (group.length==0) return group;
        
        List<Segment> result = new ArrayList<Segment>(group.length+2);
        for (Segment range : group) {
        	 // Cuts the range completely
             if (cutWith.start<=range.start && cutWith.end>=range.end) continue;
             // Doesn't cut the range at all
             if (cutWith.start>=range.end || cutWith.end<=range.start) {
                 result.add(range);
                 continue;
             }
             // Splits the range in half
             if (cutWith.start>range.start && cutWith.end<range.end) {
                 result.add(new Segment(range.start, cutWith.start));
                 result.add(new Segment(cutWith.end, range.end));
                 continue;
             }
             // cuts the range from one end
             if (cutWith.start<=range.start) {
                 result.add(new Segment(cutWith.end, range.end));
                 continue;
             }
             // cuts the range from one end
             if (cutWith.end>=range.end) {
                 result.add(new Segment(range.start, cutWith.start));
                 continue;
             }    
             
         }
         
        return (Segment[]) result.toArray(NO_RANGES);
    }
    
    /**
     * Returns difference of segments 
     * @param segments1
     * @param segments2
     * @return
     */
    public static Segment[] difference(Segment segments1[], Segment segments2[]) {
    	// TODO : this could be optimized (both arrays are sorted)
    	Segment temp[] = segments1;
    	for (Segment s : segments2)
    		temp = difference(temp, s);
    	return temp;
    }

    /**
     * Concate arrays 
     * 
     * @param array1 array
     * @param array2 array
     * @return the concatenation
     */
    public static Segment[] concat(Segment array1[], Segment array2[]) {
        Segment result[] = new Segment[array1.length + array2.length];
        System.arraycopy(array1, 0, result, 0, array1.length);
        System.arraycopy(array2, 0, result, array1.length, array2.length);
        return result;
    }

    /**
     * Create an intersection with another segment
     * 
     * @param s segment
     * @return null if no intersection, otherwise the intersection
     */
    Segment intersectWith(Segment s) {
        if (!intersects(s)) return null;
        double newStart = this.start;
        if (s.start>newStart) newStart = s.start;
        double newEnd = this.end;
        if (s.end<newEnd) newEnd = s.end;
        return new Segment(newStart, newEnd);        
    }    
    
    /**
     * Create an difference with another segment
     * 
     * @param s segment
     * @return null if no intersection, otherwise the intersection
     */
    Segment differenceWith(Segment s) {
        if (!intersects(s)) return this;
        double newStart = this.start;
        double newEnd = this.end;
        if (s.start<newEnd) newEnd = s.start;
        if (s.end>newStart) newStart = s.end;
        if (newEnd < newStart)
        	return null;
        return new Segment(newStart, newEnd);        
    }  
    /**
     * Intersect a group of segments.
     * In the result contains all segments where 2 or more segments intersected
     * in the source group. 
     * 
     * @param group group of segments
     * @return intersection of segments. sorted array
     */
    public static Segment[] intersection(Segment group[]) {
        group = sort(group);
        int count = 0;
        Segment[] temp = new Segment[group.length];
        
        Segment base = group[0];
        for (int i=1; i<group.length; i++) {
            Segment r = group[i];
            // an intersection
            Segment is = base.intersectWith(r);
            if (is != null) temp[count++] = is;

            // extend our base
            if (r.parallelWith(base)) {
                base = base.extendWith(r);
            } else
            // Choose a new base
                base = r;
            
        }
        return resizeArray(temp, count);
    }

    /**
     * Create an union a group of segments
     * 
     * @param group group of segments 
     * @return incrementally sorted, non-intersecting array of segments
     */
    public static Segment[] union(Segment group[]) {
        if (group.length<=1) return group;
        group = sort(group);
        
        int count = 0;
        Segment[] temp = new Segment[group.length];
        
        Segment base = group[0];
        for (int i=1; i<group.length; i++) {
            Segment r = group[i];
            if (r.parallelWith(base))
                base = base.extendWith(r);
            else {
                temp[count++] = base;
                base = r;
            }               
        }
        temp[count++] = base;
        return resizeArray(temp, count);
    }

    /**
     * Resize an array
     * 
     * @param array the array
     * @param newLength new length of the array
     * @return new resized array
     */
    public static Segment[] resizeArray(Segment array[], int newLength) {
        int oldLength = array.length;
        if (oldLength==newLength) return array;
        
        Segment newArray[] = new Segment[newLength];            
        // Crop the array
        if (newLength<oldLength) 
            System.arraycopy(array, 0, newArray, 0, newLength);
        else
            System.arraycopy(array, 0, newArray, 0, oldLength);
        return newArray;
    }

    /**
     * Sort array by their start Datas
     * 
     * @param group group of segments to sort
     * @return incrementally sorted array of segments
     */
    public static Segment[] sort(Segment group[]) {
        Segment[] result = (Segment[]) group.clone();
        Arrays.sort(result, COMPARATOR);
        return result;
    }
    
    private static final Comparator<Segment> COMPARATOR = new Comparator<Segment>() {
        public int compare(Segment o1, Segment o2) {
            if (o1.start < o2.start)
                return -1;
            if (o1.start > o2.start)
                return 1;
            
            if (o1.end < o2.end)
                return -1;
            if (o1.end > o2.end)
                return 1;
            
            return 0;
        }
    }; 
    
    @Override
    public int hashCode() {
    	long bits = Double.doubleToLongBits(start);
    	int hash = (int)(bits ^ (bits >>> 32));
    	bits = Double.doubleToLongBits(end);
    	hash ^= (int)(bits ^ (bits >>> 32));
    	return hash;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Segment)) return false;
        Segment other = (Segment) obj;
        return (other.end == this.end) && (other.start == this.start);
    }

    /**
     * Segment start are compared. If they are equal, ends are compared.
     * Smallest value first.
     * 
     * @param other compare to
     * @return the compare value
     */
    public int compareTo(Segment other) {
        double diffrence = this.start - other.start;
        if (diffrence < 0)
            return -1;
        if (diffrence > 0)
            return 1;
        
        diffrence = this.end - other.end;
        if (diffrence < 0)
            return -1;
        if (diffrence > 0)
            return 1;
        return 0;
    }
    
    @Override
    public Segment clone() {
    	return new Segment(start, end);
    }
    
    public String toString() {
        return "["+start+".."+end+"]";
    }

    public static String toString(Segment array[]) {
    	return Arrays.toString(array);
    }
    
}