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

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