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