-/*******************************************************************************\r
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
- * in Industry THTH ry.\r
- * All rights reserved. This program and the accompanying materials\r
- * are made available under the terms of the Eclipse Public License v1.0\r
- * which accompanies this distribution, and is available at\r
- * http://www.eclipse.org/legal/epl-v10.html\r
- *\r
- * Contributors:\r
- * VTT Technical Research Centre of Finland - initial API and implementation\r
- *******************************************************************************/\r
-package org.simantics.utils.datastructures;\r
-\r
-import java.io.Serializable;\r
-import java.util.ArrayList;\r
-import java.util.Arrays;\r
-import java.util.Comparator;\r
-import java.util.List;\r
-\r
-/**\r
- * Segment consists of a start and a end value. Both start and end are inclusive. \r
- * \r
- * @See {@link SegmentSet}\r
- * @author Toni Kalajainen\r
- */\r
-public final class Segment implements Comparable<Segment>, Serializable, Cloneable {\r
-\r
- public static final Segment ALL = new Segment(-Double.MAX_VALUE, Double.MAX_VALUE);\r
- public static final Segment[] NO_RANGES = new Segment[0];\r
- \r
- /**\r
- * Define serial version of this class\r
- */\r
- private static final long serialVersionUID = 2979572023736175492L;\r
-\r
- /** start Data */\r
- private double start;\r
-\r
- /** end Data */\r
- private double end;\r
-\r
- /**\r
- * Create a new segment at a single value\r
- * \r
- * @param value value\r
- * @return segment\r
- */\r
- public static Segment at(double value)\r
- {\r
- return new Segment(value, value);\r
- }\r
- \r
- /**\r
- * Create the segment between two values\r
- * \r
- * @param d1 value 1\r
- * @param d2 value 2\r
- * @return segment\r
- */\r
- public static Segment of(double d1, double d2)\r
- {\r
- if (d1<d2) \r
- return new Segment(d1, d2);\r
- else\r
- return new Segment(d2, d1);\r
- }\r
- \r
- /**\r
- * Create a segment. Start and end are included.\r
- * Start value must be smaller that end value.\r
- * \r
- * @param start the start time\r
- * @param end the end time\r
- */\r
- public Segment(double start, double end) {\r
- if (start>end)\r
- throw new IllegalArgumentException("Start is after end");\r
- this.start = start;\r
- this.end = end;\r
- }\r
- \r
- /**\r
- * Create single point\r
- * \r
- * @param data Data point \r
- */\r
- public Segment(double data) {\r
- start = data;\r
- end = data;\r
- }\r
- \r
- /**\r
- * Create as segment.\r
- * @param data\r
- */\r
- public Segment(double[] data) {\r
- assert(data.length ==2);\r
- start = data[0];\r
- end = data[1];\r
- if (start>end)\r
- throw new IllegalArgumentException("Start is after end");\r
- \r
- }\r
-\r
- /**\r
- * Get the end Data\r
- * \r
- * @return the end Data\r
- */\r
- public double getEnd() {\r
- return end;\r
- }\r
-\r
- /**\r
- * Get the start Data\r
- * \r
- * @return the Data\r
- */\r
- public double getStart() {\r
- return start;\r
- }\r
-\r
- /**\r
- * Get the length of the Data\r
- * \r
- * @return the length\r
- */\r
- public double getLength() {\r
- return end - start;\r
- }\r
-\r
- public Segment createWithNewStart(double newStartData) {\r
- return new Segment(newStartData, end);\r
- }\r
-\r
- public Segment createWithNewEnd(double newEndData) {\r
- return new Segment(start, newEndData);\r
- }\r
-\r
- /**\r
- * Creates a one element array\r
- * \r
- * @return the 1-element array\r
- */\r
- public Segment[] toArray() {\r
- Segment[] array = new Segment[1];\r
- array[0] = this;\r
- return array;\r
- }\r
- \r
- /**\r
- * Tests wheter this segment contains value\r
- * \r
- * @param value the value\r
- * @return true if the value is within the segment\r
- */\r
- public boolean contains(double value) {\r
- return (value>=start && value<=end);\r
- }\r
- \r
- /**\r
- * Tests whether this segment fully contains s\r
- * \r
- * @param s segment\r
- * @return Returns true if this segment contains s\r
- */\r
- public boolean contains(Segment s) {\r
- return (start<=s.start && end>=s.end);\r
- }\r
- \r
- /**\r
- * Tests whether s intersects or is parallel to this segment.\r
- * \r
- * @param s segment\r
- * @return true if the two segments intersect or are parallel\r
- */\r
- public boolean parallelWith(Segment s) {\r
- if (s.start > this.end) return false;\r
- if (s.end < this.start) return false;\r
- return true;\r
- }\r
-\r
- /**\r
- * Tests whether s intersects with this segment\r
- * \r
- * @param s segment\r
- * @return true if they intersect \r
- */\r
- public boolean intersects(Segment s) {\r
- if (s.start >= this.end) return false;\r
- if (s.end <= this.start) return false;\r
- return true;\r
- }\r
- \r
- /**\r
- * Extends the segment with another.\r
- * \r
- * @param s other segment\r
- * @return new segment containing both segments\r
- */\r
- public Segment extendWith(Segment s) {\r
- if (contains(s)) return this;\r
- if (s.contains(this)) return s;\r
- double newStart = this.start;\r
- if (s.start<newStart) newStart = s.start;\r
- double newEnd = this.end;\r
- if (s.end>newEnd) newEnd = s.end;\r
- return new Segment(newStart, newEnd);\r
- }\r
- \r
- /**\r
- * Extends this segment so that value is included.\r
- * \r
- * @param value a value\r
- * @return new segment that includes the value\r
- */\r
- public Segment extendWith(double value) {\r
- if (this.contains(value)) return this;\r
- return new Segment((value<start?value:start),(value>end?value:end));\r
- }\r
- \r
- /**\r
- * Create an intersection of this and s\r
- * \r
- * @param s segment\r
- * @return the intersection\r
- */\r
- public Segment[] intersection(Segment s) {\r
- Segment list[] = new Segment[2];\r
- list[0] = this;\r
- list[1] = s;\r
- return Segment.intersection(list);\r
- }\r
-\r
- /**\r
- * Create an union of this and s\r
- * \r
- * @param s segment\r
- * @return the union\r
- */\r
- public Segment[] union(Segment range) {\r
- Segment list[] = new Segment[2];\r
- list[0] = this;\r
- list[1] = range;\r
- return Segment.union(list);\r
- }\r
-\r
- /**\r
- * Create intersection\r
- * \r
- * @param segments1 group of Data range\r
- * @param segments2 group of Data range\r
- * @return the intersection\r
- */\r
- public static Segment[] intersection(Segment segments1[],\r
- Segment segments2[]) {\r
- return intersection(concat(segments1, segments2));\r
- }\r
- \r
- /**\r
- * Create union\r
- * \r
- * @param segments1 group of segments\r
- * @param segments2 group of segments\r
- * @return the union\r
- */\r
- public static Segment[] union(Segment segments1[], Segment segments2[]) {\r
- return union(concat(segments1, segments2));\r
- }\r
- \r
- /**\r
- * Returns difference of segments \r
- * \r
- * @param group\r
- * @param cutWith\r
- * @return\r
- */\r
- public static Segment[] difference(Segment group[], Segment cutWith) {\r
- if (group.length==0) return group;\r
- \r
- List<Segment> result = new ArrayList<Segment>(group.length+2);\r
- for (Segment range : group) {\r
- // Cuts the range completely\r
- if (cutWith.start<=range.start && cutWith.end>=range.end) continue;\r
- // Doesn't cut the range at all\r
- if (cutWith.start>=range.end || cutWith.end<=range.start) {\r
- result.add(range);\r
- continue;\r
- }\r
- // Splits the range in half\r
- if (cutWith.start>range.start && cutWith.end<range.end) {\r
- result.add(new Segment(range.start, cutWith.start));\r
- result.add(new Segment(cutWith.end, range.end));\r
- continue;\r
- }\r
- // cuts the range from one end\r
- if (cutWith.start<=range.start) {\r
- result.add(new Segment(cutWith.end, range.end));\r
- continue;\r
- }\r
- // cuts the range from one end\r
- if (cutWith.end>=range.end) {\r
- result.add(new Segment(range.start, cutWith.start));\r
- continue;\r
- } \r
- \r
- }\r
- \r
- return (Segment[]) result.toArray(NO_RANGES);\r
- }\r
- \r
- /**\r
- * Returns difference of segments \r
- * @param segments1\r
- * @param segments2\r
- * @return\r
- */\r
- public static Segment[] difference(Segment segments1[], Segment segments2[]) {\r
- // TODO : this could be optimized (both arrays are sorted)\r
- Segment temp[] = segments1;\r
- for (Segment s : segments2)\r
- temp = difference(temp, s);\r
- return temp;\r
- }\r
-\r
- /**\r
- * Concate arrays \r
- * \r
- * @param array1 array\r
- * @param array2 array\r
- * @return the concatenation\r
- */\r
- public static Segment[] concat(Segment array1[], Segment array2[]) {\r
- Segment result[] = new Segment[array1.length + array2.length];\r
- System.arraycopy(array1, 0, result, 0, array1.length);\r
- System.arraycopy(array2, 0, result, array1.length, array2.length);\r
- return result;\r
- }\r
-\r
- /**\r
- * Create an intersection with another segment\r
- * \r
- * @param s segment\r
- * @return null if no intersection, otherwise the intersection\r
- */\r
- Segment intersectWith(Segment s) {\r
- if (!intersects(s)) return null;\r
- double newStart = this.start;\r
- if (s.start>newStart) newStart = s.start;\r
- double newEnd = this.end;\r
- if (s.end<newEnd) newEnd = s.end;\r
- return new Segment(newStart, newEnd); \r
- } \r
- \r
- /**\r
- * Create an difference with another segment\r
- * \r
- * @param s segment\r
- * @return null if no intersection, otherwise the intersection\r
- */\r
- Segment differenceWith(Segment s) {\r
- if (!intersects(s)) return this;\r
- double newStart = this.start;\r
- double newEnd = this.end;\r
- if (s.start<newEnd) newEnd = s.start;\r
- if (s.end>newStart) newStart = s.end;\r
- if (newEnd < newStart)\r
- return null;\r
- return new Segment(newStart, newEnd); \r
- } \r
- /**\r
- * Intersect a group of segments.\r
- * In the result contains all segments where 2 or more segments intersected\r
- * in the source group. \r
- * \r
- * @param group group of segments\r
- * @return intersection of segments. sorted array\r
- */\r
- public static Segment[] intersection(Segment group[]) {\r
- group = sort(group);\r
- int count = 0;\r
- Segment[] temp = new Segment[group.length];\r
- \r
- Segment base = group[0];\r
- for (int i=1; i<group.length; i++) {\r
- Segment r = group[i];\r
- // an intersection\r
- Segment is = base.intersectWith(r);\r
- if (is != null) temp[count++] = is;\r
-\r
- // extend our base\r
- if (r.parallelWith(base)) {\r
- base = base.extendWith(r);\r
- } else\r
- // Choose a new base\r
- base = r;\r
- \r
- }\r
- return resizeArray(temp, count);\r
- }\r
-\r
- /**\r
- * Create an union a group of segments\r
- * \r
- * @param group group of segments \r
- * @return incrementally sorted, non-intersecting array of segments\r
- */\r
- public static Segment[] union(Segment group[]) {\r
- if (group.length<=1) return group;\r
- group = sort(group);\r
- \r
- int count = 0;\r
- Segment[] temp = new Segment[group.length];\r
- \r
- Segment base = group[0];\r
- for (int i=1; i<group.length; i++) {\r
- Segment r = group[i];\r
- if (r.parallelWith(base))\r
- base = base.extendWith(r);\r
- else {\r
- temp[count++] = base;\r
- base = r;\r
- } \r
- }\r
- temp[count++] = base;\r
- return resizeArray(temp, count);\r
- }\r
-\r
- /**\r
- * Resize an array\r
- * \r
- * @param array the array\r
- * @param newLength new length of the array\r
- * @return new resized array\r
- */\r
- public static Segment[] resizeArray(Segment array[], int newLength) {\r
- int oldLength = array.length;\r
- if (oldLength==newLength) return array;\r
- \r
- Segment newArray[] = new Segment[newLength]; \r
- // Crop the array\r
- if (newLength<oldLength) \r
- System.arraycopy(array, 0, newArray, 0, newLength);\r
- else\r
- System.arraycopy(array, 0, newArray, 0, oldLength);\r
- return newArray;\r
- }\r
-\r
- /**\r
- * Sort array by their start Datas\r
- * \r
- * @param group group of segments to sort\r
- * @return incrementally sorted array of segments\r
- */\r
- public static Segment[] sort(Segment group[]) {\r
- Segment[] result = (Segment[]) group.clone();\r
- Arrays.sort(result, COMPARATOR);\r
- return result;\r
- }\r
- \r
- private static final Comparator<Segment> COMPARATOR = new Comparator<Segment>() {\r
- public int compare(Segment o1, Segment o2) {\r
- if (o1.start < o2.start)\r
- return -1;\r
- if (o1.start > o2.start)\r
- return 1;\r
- \r
- if (o1.end < o2.end)\r
- return -1;\r
- if (o1.end > o2.end)\r
- return 1;\r
- \r
- return 0;\r
- }\r
- }; \r
- \r
- @Override\r
- public int hashCode() {\r
- long bits = Double.doubleToLongBits(start);\r
- int hash = (int)(bits ^ (bits >>> 32));\r
- bits = Double.doubleToLongBits(end);\r
- hash ^= (int)(bits ^ (bits >>> 32));\r
- return hash;\r
- }\r
-\r
- public boolean equals(Object obj) {\r
- if (!(obj instanceof Segment)) return false;\r
- Segment other = (Segment) obj;\r
- return (other.end == this.end) && (other.start == this.start);\r
- }\r
-\r
- /**\r
- * Segment start are compared. If they are equal, ends are compared.\r
- * Smallest value first.\r
- * \r
- * @param other compare to\r
- * @return the compare value\r
- */\r
- public int compareTo(Segment other) {\r
- double diffrence = this.start - other.start;\r
- if (diffrence < 0)\r
- return -1;\r
- if (diffrence > 0)\r
- return 1;\r
- \r
- diffrence = this.end - other.end;\r
- if (diffrence < 0)\r
- return -1;\r
- if (diffrence > 0)\r
- return 1;\r
- return 0;\r
- }\r
- \r
- @Override\r
- public Segment clone() {\r
- return new Segment(start, end);\r
- }\r
- \r
- public String toString() {\r
- return "["+start+".."+end+"]";\r
- }\r
-\r
- public static String toString(Segment array[]) {\r
- return Arrays.toString(array);\r
- }\r
- \r
-}\r
-\r
+/*******************************************************************************
+ * 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);
+ }
+
+}
+