--- /dev/null
+/*******************************************************************************\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
Code Review / simantics / platform.git / blobdiff