X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FSegment.java;fp=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2FSegment.java;h=9dd9476e7a41f9ee13080c036847db1e1a3aed59;hb=0ae2b770234dfc3cbb18bd38f324125cf0faca07;hp=34e8345f1c4102ebc74b2704cc65e39e1be1440a;hpb=24e2b34260f219f0d1644ca7a138894980e25b14;p=simantics%2Fplatform.git

diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/Segment.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/Segment.java
index 34e8345f1..9dd9476e7 100644
--- a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/Segment.java
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/Segment.java
@@ -1,528 +1,528 @@
-/*******************************************************************************
- * 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);
-    }
-    
-}
-
+/*******************************************************************************
+ * 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);
+    }
+    
+}
+