1 /*******************************************************************************
2 * Copyright (c) 2007, 2010 Association for Decentralized Information Management
4 * All rights reserved. This program and the accompanying materials
5 * are made available under the terms of the Eclipse Public License v1.0
6 * which accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * VTT Technical Research Centre of Finland - initial API and implementation
11 *******************************************************************************/
12 package org.simantics.utils.datastructures;
14 import java.io.Serializable;
15 import java.util.ArrayList;
16 import java.util.Arrays;
17 import java.util.Comparator;
18 import java.util.List;
21 * Segment consists of a start and a end value. Both start and end are inclusive.
23 * @See {@link SegmentSet}
24 * @author Toni Kalajainen
26 public final class Segment implements Comparable<Segment>, Serializable, Cloneable {
28 public static final Segment ALL = new Segment(-Double.MAX_VALUE, Double.MAX_VALUE);
29 public static final Segment[] NO_RANGES = new Segment[0];
32 * Define serial version of this class
34 private static final long serialVersionUID = 2979572023736175492L;
43 * Create a new segment at a single value
48 public static Segment at(double value)
50 return new Segment(value, value);
54 * Create the segment between two values
60 public static Segment of(double d1, double d2)
63 return new Segment(d1, d2);
65 return new Segment(d2, d1);
69 * Create a segment. Start and end are included.
70 * Start value must be smaller that end value.
72 * @param start the start time
73 * @param end the end time
75 public Segment(double start, double end) {
77 throw new IllegalArgumentException("Start is after end");
85 * @param data Data point
87 public Segment(double data) {
96 public Segment(double[] data) {
97 assert(data.length ==2);
101 throw new IllegalArgumentException("Start is after end");
108 * @return the end Data
110 public double getEnd() {
119 public double getStart() {
124 * Get the length of the Data
128 public double getLength() {
132 public Segment createWithNewStart(double newStartData) {
133 return new Segment(newStartData, end);
136 public Segment createWithNewEnd(double newEndData) {
137 return new Segment(start, newEndData);
141 * Creates a one element array
143 * @return the 1-element array
145 public Segment[] toArray() {
146 Segment[] array = new Segment[1];
152 * Tests wheter this segment contains value
154 * @param value the value
155 * @return true if the value is within the segment
157 public boolean contains(double value) {
158 return (value>=start && value<=end);
162 * Tests whether this segment fully contains s
165 * @return Returns true if this segment contains s
167 public boolean contains(Segment s) {
168 return (start<=s.start && end>=s.end);
172 * Tests whether s intersects or is parallel to this segment.
175 * @return true if the two segments intersect or are parallel
177 public boolean parallelWith(Segment s) {
178 if (s.start > this.end) return false;
179 if (s.end < this.start) return false;
184 * Tests whether s intersects with this segment
187 * @return true if they intersect
189 public boolean intersects(Segment s) {
190 if (s.start >= this.end) return false;
191 if (s.end <= this.start) return false;
196 * Extends the segment with another.
198 * @param s other segment
199 * @return new segment containing both segments
201 public Segment extendWith(Segment s) {
202 if (contains(s)) return this;
203 if (s.contains(this)) return s;
204 double newStart = this.start;
205 if (s.start<newStart) newStart = s.start;
206 double newEnd = this.end;
207 if (s.end>newEnd) newEnd = s.end;
208 return new Segment(newStart, newEnd);
212 * Extends this segment so that value is included.
214 * @param value a value
215 * @return new segment that includes the value
217 public Segment extendWith(double value) {
218 if (this.contains(value)) return this;
219 return new Segment((value<start?value:start),(value>end?value:end));
223 * Create an intersection of this and s
226 * @return the intersection
228 public Segment[] intersection(Segment s) {
229 Segment list[] = new Segment[2];
232 return Segment.intersection(list);
236 * Create an union of this and s
241 public Segment[] union(Segment range) {
242 Segment list[] = new Segment[2];
245 return Segment.union(list);
249 * Create intersection
251 * @param segments1 group of Data range
252 * @param segments2 group of Data range
253 * @return the intersection
255 public static Segment[] intersection(Segment segments1[],
256 Segment segments2[]) {
257 return intersection(concat(segments1, segments2));
263 * @param segments1 group of segments
264 * @param segments2 group of segments
267 public static Segment[] union(Segment segments1[], Segment segments2[]) {
268 return union(concat(segments1, segments2));
272 * Returns difference of segments
278 public static Segment[] difference(Segment group[], Segment cutWith) {
279 if (group.length==0) return group;
281 List<Segment> result = new ArrayList<Segment>(group.length+2);
282 for (Segment range : group) {
283 // Cuts the range completely
284 if (cutWith.start<=range.start && cutWith.end>=range.end) continue;
285 // Doesn't cut the range at all
286 if (cutWith.start>=range.end || cutWith.end<=range.start) {
290 // Splits the range in half
291 if (cutWith.start>range.start && cutWith.end<range.end) {
292 result.add(new Segment(range.start, cutWith.start));
293 result.add(new Segment(cutWith.end, range.end));
296 // cuts the range from one end
297 if (cutWith.start<=range.start) {
298 result.add(new Segment(cutWith.end, range.end));
301 // cuts the range from one end
302 if (cutWith.end>=range.end) {
303 result.add(new Segment(range.start, cutWith.start));
309 return (Segment[]) result.toArray(NO_RANGES);
313 * Returns difference of segments
318 public static Segment[] difference(Segment segments1[], Segment segments2[]) {
319 // TODO : this could be optimized (both arrays are sorted)
320 Segment temp[] = segments1;
321 for (Segment s : segments2)
322 temp = difference(temp, s);
329 * @param array1 array
330 * @param array2 array
331 * @return the concatenation
333 public static Segment[] concat(Segment array1[], Segment array2[]) {
334 Segment result[] = new Segment[array1.length + array2.length];
335 System.arraycopy(array1, 0, result, 0, array1.length);
336 System.arraycopy(array2, 0, result, array1.length, array2.length);
341 * Create an intersection with another segment
344 * @return null if no intersection, otherwise the intersection
346 Segment intersectWith(Segment s) {
347 if (!intersects(s)) return null;
348 double newStart = this.start;
349 if (s.start>newStart) newStart = s.start;
350 double newEnd = this.end;
351 if (s.end<newEnd) newEnd = s.end;
352 return new Segment(newStart, newEnd);
356 * Create an difference with another segment
359 * @return null if no intersection, otherwise the intersection
361 Segment differenceWith(Segment s) {
362 if (!intersects(s)) return this;
363 double newStart = this.start;
364 double newEnd = this.end;
365 if (s.start<newEnd) newEnd = s.start;
366 if (s.end>newStart) newStart = s.end;
367 if (newEnd < newStart)
369 return new Segment(newStart, newEnd);
372 * Intersect a group of segments.
373 * In the result contains all segments where 2 or more segments intersected
374 * in the source group.
376 * @param group group of segments
377 * @return intersection of segments. sorted array
379 public static Segment[] intersection(Segment group[]) {
382 Segment[] temp = new Segment[group.length];
384 Segment base = group[0];
385 for (int i=1; i<group.length; i++) {
386 Segment r = group[i];
388 Segment is = base.intersectWith(r);
389 if (is != null) temp[count++] = is;
392 if (r.parallelWith(base)) {
393 base = base.extendWith(r);
399 return resizeArray(temp, count);
403 * Create an union a group of segments
405 * @param group group of segments
406 * @return incrementally sorted, non-intersecting array of segments
408 public static Segment[] union(Segment group[]) {
409 if (group.length<=1) return group;
413 Segment[] temp = new Segment[group.length];
415 Segment base = group[0];
416 for (int i=1; i<group.length; i++) {
417 Segment r = group[i];
418 if (r.parallelWith(base))
419 base = base.extendWith(r);
421 temp[count++] = base;
425 temp[count++] = base;
426 return resizeArray(temp, count);
432 * @param array the array
433 * @param newLength new length of the array
434 * @return new resized array
436 public static Segment[] resizeArray(Segment array[], int newLength) {
437 int oldLength = array.length;
438 if (oldLength==newLength) return array;
440 Segment newArray[] = new Segment[newLength];
442 if (newLength<oldLength)
443 System.arraycopy(array, 0, newArray, 0, newLength);
445 System.arraycopy(array, 0, newArray, 0, oldLength);
450 * Sort array by their start Datas
452 * @param group group of segments to sort
453 * @return incrementally sorted array of segments
455 public static Segment[] sort(Segment group[]) {
456 Segment[] result = (Segment[]) group.clone();
457 Arrays.sort(result, COMPARATOR);
461 private static final Comparator<Segment> COMPARATOR = new Comparator<Segment>() {
462 public int compare(Segment o1, Segment o2) {
463 if (o1.start < o2.start)
465 if (o1.start > o2.start)
478 public int hashCode() {
479 long bits = Double.doubleToLongBits(start);
480 int hash = (int)(bits ^ (bits >>> 32));
481 bits = Double.doubleToLongBits(end);
482 hash ^= (int)(bits ^ (bits >>> 32));
486 public boolean equals(Object obj) {
487 if (!(obj instanceof Segment)) return false;
488 Segment other = (Segment) obj;
489 return (other.end == this.end) && (other.start == this.start);
493 * Segment start are compared. If they are equal, ends are compared.
494 * Smallest value first.
496 * @param other compare to
497 * @return the compare value
499 public int compareTo(Segment other) {
500 double diffrence = this.start - other.start;
506 diffrence = this.end - other.end;
515 public Segment clone() {
516 return new Segment(start, end);
519 public String toString() {
520 return "["+start+".."+end+"]";
523 public static String toString(Segment array[]) {
524 return Arrays.toString(array);