bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/SegmentSet.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.util.ArrayList;
  15 import java.util.Arrays;
  16 import java.util.Collection;
  17 import java.util.Iterator;
  18 import java.util.List;
  19
  20 /**
  21  * SegmentSet is a set of value segments.
  22  *
  23  * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
  24  */
  25 public class SegmentSet implements Iterable<Segment> {
  26
  27         public static final SegmentSet NONE = new SegmentSet();
  28
  29         /** incrementally sorted and non-intersecting, non-parallel array of segments */
  30         List<Segment> list = new ArrayList<Segment>();
  31
  32         /**
  33          * Create new segment set from double value pairs
  34          *
  35          * @param times even length array
  36          * @return
  37          */
  38         public static SegmentSet of(double...times)
  39         {
  40                 if (times==null || ((times.length & 1)==1))
  41                         throw new IllegalArgumentException();
  42                 SegmentSet result = new SegmentSet();
  43                 for (int i=0; i<times.length/2; i++)
  44                         result.add( Segment.of(times[i*2], times[i*2+1]) );
  45                 return result;
  46         }
  47
  48         /**
  49          * Create new set of ranges.
  50          */
  51         public SegmentSet() {
  52         }
  53
  54         /**
  55          * Create new set of ranges.
  56          */
  57         public SegmentSet(SegmentSet copyFrom) {
  58                 this.list.addAll(copyFrom.list);
  59         }
  60
  61         /**
  62          * Create new set of segments.
  63          */
  64         public SegmentSet(Collection<Segment> list) {
  65                 for (Segment r : list)
  66                         add(r);
  67         }
  68
  69         /**
  70          * Create new set of segments.
  71          *
  72          * @param segments initial segments
  73          */
  74         public SegmentSet(Segment...segments) {
  75                 for (Segment r : Segment.union(segments))
  76                         list.add(r);
  77         }
  78
  79         public boolean add(Segment...segments) {
  80                 boolean result = false;
  81                 for (Segment r : segments)
  82                         result |= add(r);
  83                 return result;
  84         }
  85
  86         /**
  87          * Add a segment set to this segment set
  88          *
  89          * @param set
  90          * @return true if the content changed
  91          */
  92         public boolean add(SegmentSet set) {
  93                 boolean result = false;
  94                 for (Segment r : set.list)
  95                         result |= add(r);
  96                 return result;
  97         }
  98
  99         /**
 100          * Get index of the segment that contains the given value.
 101          * If value is not included in the set, return as negative value the index
 102          * of the range the value is prior to.
 103          *  e.g.
 104          *    -1 before 0
 105          *    -2 before 1
 106          *
 107          * @return range index
 108          */
 109         int indexOf(double value) {
 110                 for (int i=0; i<list.size(); i++) {
 111                         Segment r = list.get(i);
 112                         if (r.contains(value)) return i;
 113                         if (r.getStart()>=value) return -i -1;
 114                 }
 115                 return -list.size()-1;
 116         }
 117
 118         /**
 119          * Get the segment the value is in.
 120          *
 121          * @param value
 122          * @return segment or null
 123          */
 124         public Segment getSegmentOf(double value)
 125         {
 126                 int index = indexOf(value);
 127                 if (index<0) return null;
 128                 return list.get(index);
 129         }
 130
 131         /**
 132          * Add segment range
 133          *
 134          * @param range
 135          * @return true if the content changed
 136          */
 137         public boolean add(Segment range) {
 138                 int startIndex = indexOf(range.getStart());
 139                 int endIndex = indexOf(range.getEnd());
 140
 141                 // The whole segment is already included in the set
 142                 if (startIndex>=0 && startIndex==endIndex) return false;
 143
 144                 // Doesn't intersect, add as is
 145                 if (startIndex<0 && startIndex==endIndex) {
 146                         list.add(-startIndex-1, range);
 147                         return true;
 148                 }
 149
 150                 // Intersects partially
 151                 double start = range.getStart();
 152                 double end = range.getEnd();
 153
 154                 // Extend the segment following the start position
 155                 if (startIndex<0) {
 156                         startIndex = -startIndex-1;
 157                 } else {
 158                         start = list.get(startIndex).getStart();
 159                 }
 160
 161                 // Extends the segment preceding the end position
 162                 if (endIndex<0) {
 163                         endIndex = -endIndex-2;
 164                 } else {
 165                         end = list.get(endIndex).getEnd();
 166                 }
 167
 168                 int segmentsToRemove = endIndex - startIndex;
 169                 for (int j=0; j<segmentsToRemove; j++)
 170                         list.remove(startIndex);
 171
 172                 if (start!=range.getStart() || end!=range.getEnd())
 173                         range = new Segment(start, end);
 174
 175                 list.set( startIndex, range );
 176                 return true;
 177         }
 178
 179         public boolean remove(Segment...ranges) {
 180                 boolean result = false;
 181                 for (Segment r : ranges)
 182                         result |= remove(r);
 183                 return result;
 184         }
 185
 186         public boolean remove(SegmentSet set) {
 187                 boolean result = false;
 188                 for (Segment r : set.list)
 189                         result |= remove(r);
 190                 return result;
 191         }
 192
 193         public boolean remove(Segment range) {
 194                 int startIndex = indexOf(range.getStart());
 195                 int endIndex = indexOf(range.getEnd());
 196
 197                 // Doesn't intersect
 198                 if (startIndex<0 && startIndex==endIndex) return false;
 199
 200                 // Move start to next segment
 201                 if (startIndex<0)
 202                         startIndex = -startIndex-1;
 203
 204                 // Move end to prev segment
 205                 if (endIndex<0)
 206                         endIndex = -endIndex-2;
 207
 208                 // Start position is in segment. Cut segment and move to next one
 209                 if (range.getStart()>list.get(startIndex).getStart()) {
 210                         Segment s = list.get(startIndex);
 211                         Segment newS = new Segment(s.getStart(), range.getStart());
 212                         list.set(startIndex, newS);
 213                         startIndex++;
 214
 215                         if (s.getEnd()>range.getEnd()) {
 216                                 newS = new Segment(range.getEnd(), s.getEnd());
 217                                 list.add(startIndex, newS);
 218                                 startIndex++;
 219                         }
 220                 }
 221
 222                 // End position is within segment, Cut it and move to prev one
 223                 if (range.getEnd()<list.get(endIndex).getEnd()) {
 224                         Segment s = list.get(endIndex);
 225                         s = new Segment(range.getEnd(), s.getEnd());
 226                         list.set(endIndex, s);
 227                         endIndex--;
 228                 }
 229
 230                 // Remove start if it is cut completely
 231                 while ( startIndex<=endIndex && range.contains( list.get(startIndex) ) ) {
 232                         list.remove(startIndex);
 233                         endIndex--;
 234                 }
 235                 return true;
 236         }
 237
 238         /**
 239          * Clips SegmentSet to given segment.
 240          * @param segment
 241          */
 242         public void clip(Segment segment) {
 243                 remove(new Segment(-Double.MAX_VALUE,segment.getStart()));
 244                 remove(new Segment(segment.getEnd(),Double.MAX_VALUE));
 245         }
 246
 247         /**
 248          * Tests whether s intersects
 249          *
 250          * @param s segmentset
 251          * @return true if s intersects with this segment set
 252          */
 253         public boolean intersects(SegmentSet set)
 254         {
 255                 for (Segment s : set.list)
 256                         if (intersects(s)) return true;
 257                 return false;
 258         }
 259
 260         /**
 261          * Tests whether s intersects
 262          *
 263          * @param s segment
 264          * @return true if s intersects with this segment set
 265          */
 266         public boolean intersects(Segment s)
 267         {
 268                 for (Segment localS : list)
 269                         if (localS.intersects(s)) return true;
 270                 return false;
 271         }
 272
 273         /**
 274          * Tests whether s is fully contained in this segment set.
 275          *
 276          * @param s segment
 277          * @return true if s is fully contained in this segment set
 278          */
 279         public boolean contains(Segment s)
 280         {
 281                 for (Segment localS : list)
 282                         if (localS.contains(s)) return true;
 283                 return false;
 284         }
 285
 286         /**
 287          * Tests whether the a values is included in the set.
 288          *
 289          * @param value
 290          * @return
 291          */
 292         public boolean contains(double value)
 293         {
 294                 return indexOf(value)>=0;
 295         }
 296
 297         /**
 298          * Get the min and max value
 299          *
 300          * @return boundaries or null
 301          */
 302         public Segment getBoundaries()
 303         {
 304                 if (list.isEmpty()) return null;
 305                 double start = list.get(0).getStart();
 306                 double end = list.get(list.size()-1).getEnd();
 307                 return new Segment(start, end);
 308         }
 309
 310         /**
 311          *
 312          * @return lower bound or null
 313          */
 314         public Double getLowerBound() {
 315                 if (list.isEmpty()) return null;
 316                 return list.get(0).getStart();
 317         }
 318
 319         /**
 320          *
 321          * @return upper bound or null
 322          */
 323         public Double getUpperBound() {
 324                 if (list.isEmpty()) return null;
 325                 return list.get(list.size()-1).getEnd();
 326         }
 327
 328         /**
 329          * Return incrementally sorted and non-intersecting array of segments.
 330          *
 331          * Note this method returns an internal state, it most not be modified.
 332          *
 333          * @return array
 334          */
 335         public Segment[] toArray() {
 336                 return list.toArray( new Segment[list.size()] );
 337         }
 338
 339     /**
 340      * Returns an iterator over the elements in this list in proper sequence.
 341      *
 342      * @return an iterator over the elements in this list in proper sequence.
 343      */
 344     public Iterator<Segment> iterator() {
 345         return list.iterator();
 346     }
 347
 348         @Override
 349         public String toString() {
 350                 return Arrays.toString( toArray() );
 351         }
 352
 353         public SegmentSet clone() {
 354                 return new SegmentSet(this);
 355         }
 356
 357 }
 358