bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/Segment.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007, 2010 Association for Decentralized Information Management
   3  * in Industry THTH ry.
   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
   8  *
   9  * Contributors:
  10  *     VTT Technical Research Centre of Finland - initial API and implementation
  11  *******************************************************************************/
  12 package org.simantics.utils.datastructures;
  13
  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;
  19
  20 /**
  21  * Segment consists of a start and a end value. Both start and end are inclusive.
  22  *
  23  * @See {@link SegmentSet}
  24  * @author Toni Kalajainen
  25  */
  26 public final class Segment implements Comparable<Segment>, Serializable, Cloneable {
  27
  28         public static final Segment ALL = new Segment(-Double.MAX_VALUE, Double.MAX_VALUE);
  29         public static final Segment[] NO_RANGES = new Segment[0];
  30
  31     /**
  32      * Define serial version of this class
  33          */
  34         private static final long serialVersionUID = 2979572023736175492L;
  35
  36         /** start Data */
  37     private double start;
  38
  39     /** end Data */
  40     private double end;
  41
  42     /**
  43      * Create a new segment at a single value
  44      *
  45      * @param value value
  46      * @return segment
  47      */
  48     public static Segment at(double value)
  49     {
  50                 return new Segment(value, value);
  51     }
  52
  53     /**
  54      * Create the segment between two values
  55      *
  56      * @param d1 value 1
  57      * @param d2 value 2
  58      * @return segment
  59      */
  60     public static Segment of(double d1, double d2)
  61     {
  62         if (d1<d2)
  63                 return new Segment(d1, d2);
  64         else
  65                 return new Segment(d2, d1);
  66     }
  67
  68     /**
  69      * Create a segment. Start and end are included.
  70      * Start value must be smaller that end value.
  71      *
  72      * @param start the start time
  73      * @param end the end time
  74      */
  75     public Segment(double start, double end) {
  76         if (start>end)
  77                 throw new IllegalArgumentException("Start is after end");
  78         this.start = start;
  79         this.end = end;
  80     }
  81
  82     /**
  83      * Create single point
  84      *
  85      * @param data Data point
  86      */
  87     public Segment(double data) {
  88         start = data;
  89         end = data;
  90     }
  91
  92     /**
  93      * Create as segment.
  94      * @param data
  95      */
  96     public Segment(double[] data) {
  97         assert(data.length ==2);
  98         start = data[0];
  99         end = data[1];
 100         if (start>end)
 101                 throw new IllegalArgumentException("Start is after end");
 102
 103     }
 104
 105     /**
 106      * Get the end Data
 107      *
 108      * @return the end Data
 109      */
 110     public double getEnd() {
 111         return end;
 112     }
 113
 114     /**
 115      * Get the start Data
 116      *
 117      * @return the Data
 118      */
 119     public double getStart() {
 120         return start;
 121     }
 122
 123     /**
 124      * Get the length of the Data
 125      *
 126      * @return the length
 127      */
 128     public double getLength() {
 129         return end - start;
 130     }
 131
 132     public Segment createWithNewStart(double newStartData) {
 133         return new Segment(newStartData, end);
 134     }
 135
 136     public Segment createWithNewEnd(double newEndData) {
 137         return new Segment(start, newEndData);
 138     }
 139
 140     /**
 141      * Creates a one element array
 142      *
 143      * @return the 1-element array
 144      */
 145     public Segment[] toArray() {
 146         Segment[] array = new Segment[1];
 147         array[0] = this;
 148         return array;
 149     }
 150
 151     /**
 152      * Tests wheter this segment contains value
 153      *
 154      * @param value the value
 155      * @return true if the value is within the segment
 156      */
 157     public boolean contains(double value) {
 158         return (value>=start && value<=end);
 159     }
 160
 161     /**
 162      * Tests whether this segment fully contains s
 163      *
 164      * @param s segment
 165      * @return Returns true if this segment contains s
 166      */
 167     public boolean contains(Segment s) {
 168         return (start<=s.start && end>=s.end);
 169     }
 170
 171     /**
 172      * Tests whether s intersects or is parallel to this segment.
 173      *
 174      * @param s segment
 175      * @return true if the two segments intersect or are parallel
 176      */
 177     public boolean parallelWith(Segment s) {
 178         if (s.start > this.end) return false;
 179         if (s.end < this.start) return false;
 180         return true;
 181     }
 182
 183     /**
 184      * Tests whether s intersects with this segment
 185      *
 186      * @param s segment
 187      * @return true if they intersect
 188      */
 189     public boolean intersects(Segment s) {
 190         if (s.start >= this.end) return false;
 191         if (s.end <= this.start) return false;
 192         return true;
 193     }
 194
 195     /**
 196      * Extends the segment with another.
 197      *
 198      * @param s other segment
 199      * @return new segment containing both segments
 200      */
 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);
 209     }
 210
 211     /**
 212      * Extends this segment so that value is included.
 213      *
 214      * @param value a value
 215      * @return new segment that includes the value
 216      */
 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));
 220     }
 221
 222     /**
 223      * Create an intersection of this and s
 224      *
 225      * @param s segment
 226      * @return the intersection
 227      */
 228     public Segment[] intersection(Segment s) {
 229         Segment list[] = new Segment[2];
 230         list[0] = this;
 231         list[1] = s;
 232         return Segment.intersection(list);
 233     }
 234
 235     /**
 236      * Create an union of this and s
 237      *
 238      * @param s segment
 239      * @return the union
 240      */
 241     public Segment[] union(Segment range) {
 242         Segment list[] = new Segment[2];
 243         list[0] = this;
 244         list[1] = range;
 245         return Segment.union(list);
 246     }
 247
 248     /**
 249      * Create intersection
 250      *
 251      * @param segments1 group of Data range
 252      * @param segments2 group of Data range
 253      * @return the intersection
 254      */
 255     public static Segment[] intersection(Segment segments1[],
 256             Segment segments2[]) {
 257         return intersection(concat(segments1, segments2));
 258     }
 259
 260     /**
 261      * Create union
 262      *
 263      * @param segments1 group of segments
 264      * @param segments2 group of segments
 265      * @return the union
 266      */
 267     public static Segment[] union(Segment segments1[], Segment segments2[]) {
 268         return union(concat(segments1, segments2));
 269     }
 270
 271     /**
 272      * Returns difference of segments
 273      *
 274      * @param group
 275      * @param cutWith
 276      * @return
 277      */
 278     public static Segment[] difference(Segment group[], Segment cutWith) {
 279         if (group.length==0) return group;
 280
 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) {
 287                  result.add(range);
 288                  continue;
 289              }
 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));
 294                  continue;
 295              }
 296              // cuts the range from one end
 297              if (cutWith.start<=range.start) {
 298                  result.add(new Segment(cutWith.end, range.end));
 299                  continue;
 300              }
 301              // cuts the range from one end
 302              if (cutWith.end>=range.end) {
 303                  result.add(new Segment(range.start, cutWith.start));
 304                  continue;
 305              }
 306
 307          }
 308
 309         return (Segment[]) result.toArray(NO_RANGES);
 310     }
 311
 312     /**
 313      * Returns difference of segments
 314      * @param segments1
 315      * @param segments2
 316      * @return
 317      */
 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);
 323         return temp;
 324     }
 325
 326     /**
 327      * Concate arrays
 328      *
 329      * @param array1 array
 330      * @param array2 array
 331      * @return the concatenation
 332      */
 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);
 337         return result;
 338     }
 339
 340     /**
 341      * Create an intersection with another segment
 342      *
 343      * @param s segment
 344      * @return null if no intersection, otherwise the intersection
 345      */
 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);
 353     }
 354
 355     /**
 356      * Create an difference with another segment
 357      *
 358      * @param s segment
 359      * @return null if no intersection, otherwise the intersection
 360      */
 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)
 368                 return null;
 369         return new Segment(newStart, newEnd);
 370     }
 371     /**
 372      * Intersect a group of segments.
 373      * In the result contains all segments where 2 or more segments intersected
 374      * in the source group.
 375      *
 376      * @param group group of segments
 377      * @return intersection of segments. sorted array
 378      */
 379     public static Segment[] intersection(Segment group[]) {
 380         group = sort(group);
 381         int count = 0;
 382         Segment[] temp = new Segment[group.length];
 383
 384         Segment base = group[0];
 385         for (int i=1; i<group.length; i++) {
 386             Segment r = group[i];
 387             // an intersection
 388             Segment is = base.intersectWith(r);
 389             if (is != null) temp[count++] = is;
 390
 391             // extend our base
 392             if (r.parallelWith(base)) {
 393                 base = base.extendWith(r);
 394             } else
 395             // Choose a new base
 396                 base = r;
 397
 398         }
 399         return resizeArray(temp, count);
 400     }
 401
 402     /**
 403      * Create an union a group of segments
 404      *
 405      * @param group group of segments
 406      * @return incrementally sorted, non-intersecting array of segments
 407      */
 408     public static Segment[] union(Segment group[]) {
 409         if (group.length<=1) return group;
 410         group = sort(group);
 411
 412         int count = 0;
 413         Segment[] temp = new Segment[group.length];
 414
 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);
 420             else {
 421                 temp[count++] = base;
 422                 base = r;
 423             }
 424         }
 425         temp[count++] = base;
 426         return resizeArray(temp, count);
 427     }
 428
 429     /**
 430      * Resize an array
 431      *
 432      * @param array the array
 433      * @param newLength new length of the array
 434      * @return new resized array
 435      */
 436     public static Segment[] resizeArray(Segment array[], int newLength) {
 437         int oldLength = array.length;
 438         if (oldLength==newLength) return array;
 439
 440         Segment newArray[] = new Segment[newLength];
 441         // Crop the array
 442         if (newLength<oldLength)
 443             System.arraycopy(array, 0, newArray, 0, newLength);
 444         else
 445             System.arraycopy(array, 0, newArray, 0, oldLength);
 446         return newArray;
 447     }
 448
 449     /**
 450      * Sort array by their start Datas
 451      *
 452      * @param group group of segments to sort
 453      * @return incrementally sorted array of segments
 454      */
 455     public static Segment[] sort(Segment group[]) {
 456         Segment[] result = (Segment[]) group.clone();
 457         Arrays.sort(result, COMPARATOR);
 458         return result;
 459     }
 460
 461     private static final Comparator<Segment> COMPARATOR = new Comparator<Segment>() {
 462         public int compare(Segment o1, Segment o2) {
 463             if (o1.start < o2.start)
 464                 return -1;
 465             if (o1.start > o2.start)
 466                 return 1;
 467
 468             if (o1.end < o2.end)
 469                 return -1;
 470             if (o1.end > o2.end)
 471                 return 1;
 472
 473             return 0;
 474         }
 475     };
 476
 477     @Override
 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));
 483         return hash;
 484     }
 485
 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);
 490     }
 491
 492     /**
 493      * Segment start are compared. If they are equal, ends are compared.
 494      * Smallest value first.
 495      *
 496      * @param other compare to
 497      * @return the compare value
 498      */
 499     public int compareTo(Segment other) {
 500         double diffrence = this.start - other.start;
 501         if (diffrence < 0)
 502             return -1;
 503         if (diffrence > 0)
 504             return 1;
 505
 506         diffrence = this.end - other.end;
 507         if (diffrence < 0)
 508             return -1;
 509         if (diffrence > 0)
 510             return 1;
 511         return 0;
 512     }
 513
 514     @Override
 515     public Segment clone() {
 516         return new Segment(start, end);
 517     }
 518
 519     public String toString() {
 520         return "["+start+".."+end+"]";
 521     }
 522
 523     public static String toString(Segment array[]) {
 524         return Arrays.toString(array);
 525     }
 526
 527 }
 528