001 /*--------------------------------------------------------------------------+ 002 $Id: RegionSet.java 28341 2010-06-16 18:12:55Z hummelb $ 003 | | 004 | Copyright 2005-2010 Technische Universitaet Muenchen | 005 | | 006 | Licensed under the Apache License, Version 2.0 (the "License"); | 007 | you may not use this file except in compliance with the License. | 008 | You may obtain a copy of the License at | 009 | | 010 | http://www.apache.org/licenses/LICENSE-2.0 | 011 | | 012 | Unless required by applicable law or agreed to in writing, software | 013 | distributed under the License is distributed on an "AS IS" BASIS, | 014 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | 015 | See the License for the specific language governing permissions and | 016 | limitations under the License. | 017 +--------------------------------------------------------------------------*/ 018 package edu.tum.cs.commons.region; 019 020 import java.util.ArrayList; 021 import java.util.Collection; 022 import java.util.Collections; 023 import java.util.Comparator; 024 import java.util.Iterator; 025 import java.util.List; 026 import java.util.Set; 027 import java.util.TreeSet; 028 029 import edu.tum.cs.commons.collections.CollectionUtils; 030 import edu.tum.cs.commons.string.StringUtils; 031 032 /** 033 * Set of {@link Region} objects. Allows tests for containment on the entire set 034 * of regions. 035 * 036 * @author Elmar Juergens 037 * @author hummelb 038 * @author $Author: hummelb $ 039 * 040 * @version $Revision: 28341 $ 041 * @levd.rating GREEN Hash: 0F1BFF347A1A8FDD1F8580C3D546435D 042 */ 043 public class RegionSet implements Set<Region> { 044 045 /** Name that is used if {@link RegionSet} is created without name */ 046 public static final String ANONYMOUS = "Anonymous"; 047 048 /** Name of this RegionSet */ 049 private final String name; 050 051 /** 052 * The size the map had when our internal structure was updated (or -1 to 053 * indicate a dirty state). We have to store the size rather than just a 054 * flag, as we do not catch remove calls in the iterator returned. But as 055 * you only can remove via an iterator we cannot be fooled by a sequence of 056 * add/remove calls, because we trap add in this class. 057 */ 058 private transient int cleanSize = -1; 059 060 /** The inner set we are delegating to. */ 061 private final Set<Region> inner = new TreeSet<Region>( 062 MemberComparator.INSTANCE); 063 064 /** List of start points of the merged regions. */ 065 private transient final List<Integer> mergedStart = new ArrayList<Integer>(); 066 067 /** List of end points of the merged regions. */ 068 private transient final List<Integer> mergedEnd = new ArrayList<Integer>(); 069 070 /** 071 * Creates a named {@link RegionSet}. 072 * 073 * @param name 074 * Name of this region set. 075 */ 076 public RegionSet(String name) { 077 this.name = name; 078 } 079 080 /** Creates an unnamed region set. */ 081 public RegionSet() { 082 name = ANONYMOUS; 083 } 084 085 /** Returns the name. */ 086 public String getName() { 087 return name; 088 } 089 090 /** 091 * Returns true if the position is contained in one of the {@link Region}s 092 * in the {@link RegionSet} 093 */ 094 public boolean contains(int position) { 095 int k = getMergedIndex(position); 096 return k >= 0 && position <= mergedEnd.get(k); 097 } 098 099 /** 100 * Tests whether all of the positions of the region are contained in the 101 * {@link RegionSet} 102 */ 103 public boolean contains(Region region) { 104 int k = getMergedIndex(region.getStart()); 105 return k >= 0 && region.getEnd() <= mergedEnd.get(k); 106 } 107 108 /** 109 * Returns the index of the merged region whose start position is before or 110 * at the given position (or -1 if no such region exists). 111 */ 112 private int getMergedIndex(int position) { 113 ensureMergedUpToDate(); 114 int k = Collections.binarySearch(mergedStart, position); 115 116 // exact match, so return 117 if (k >= 0) { 118 return k; 119 } 120 121 // get insertion point (see the JavaDoc of binarySearch for an 122 // explanation of the conversion) 123 int insertionPoint = -(k + 1); 124 125 // if it would be inserted at the beginning, there is no such index 126 if (insertionPoint == 0) { 127 return -1; 128 } 129 130 // otherwise, the index must be the one before the insertion point 131 return insertionPoint - 1; 132 } 133 134 /** 135 * Tests whether any of the positions in the region are contained in the 136 * {@link RegionSet}. 137 */ 138 public boolean containsAny(Region region) { 139 // if either start or end are in, it contains "any". 140 if (contains(region.getStart()) || contains(region.getEnd())) { 141 return true; 142 } 143 144 // now we know that start and end are not contained in an interval, so 145 // to have any point contained, there must be an interval which is 146 // completely contained in the given region. But this means that the 147 // binary search has to give different results for start and end. 148 int startIndex = Collections.binarySearch(mergedStart, region 149 .getStart()); 150 int endIndex = Collections.binarySearch(mergedStart, region.getEnd()); 151 return startIndex != endIndex; 152 } 153 154 /** Makes sure the merged regions lists are up to date. */ 155 private void ensureMergedUpToDate() { 156 if (inner.size() == cleanSize) { 157 return; 158 } 159 160 mergedStart.clear(); 161 mergedEnd.clear(); 162 163 int start = -1; 164 int end = -2; 165 for (Region r : inner) { 166 if (r.getStart() <= end + 1) { 167 end = Math.max(end, r.getEnd()); 168 } else { 169 if (start >= 0) { 170 mergedStart.add(start); 171 mergedEnd.add(end); 172 } 173 start = r.getStart(); 174 end = r.getEnd(); 175 } 176 } 177 178 if (start >= 0) { 179 mergedStart.add(start); 180 mergedEnd.add(end); 181 } 182 183 cleanSize = inner.size(); 184 } 185 186 /** 187 * Gets the number of positions contained in the RegionSet. This corresponds 188 * to the (non-overlapping) sum of the length of the regions. 189 */ 190 public int getPositionCount() { 191 ensureMergedUpToDate(); 192 int count = 0; 193 194 int size = mergedStart.size(); 195 for (int i = 0; i < size; ++i) { 196 count += mergedEnd.get(i) - mergedStart.get(i) + 1; 197 } 198 return count; 199 } 200 201 /** 202 * Returns last position in {@link RegionSet}. 203 * 204 * @throws IllegalStateException 205 * if {@link RegionSet} is empty 206 */ 207 public int getLastPosition() { 208 if (isEmpty()) { 209 throw new IllegalStateException("RegionSet is empty"); 210 } 211 212 ensureMergedUpToDate(); 213 return CollectionUtils.getLast(mergedEnd); 214 } 215 216 /** 217 * Returns first position in {@link RegionSet}. 218 * 219 * @throws IllegalStateException 220 * if {@link RegionSet} is empty 221 */ 222 public int getFirstPosition() { 223 if (isEmpty()) { 224 throw new IllegalStateException("RegionSet is empty"); 225 } 226 227 ensureMergedUpToDate(); 228 return mergedStart.get(0); 229 } 230 231 /** 232 * Creates a new {@link RegionSet} whose regions are a complement to this 233 * {@link RegionSet}. 234 * 235 * Inversion is relative to the interval [0, last position] 236 */ 237 public RegionSet createInverted(String name, int lastPosition) { 238 ensureMergedUpToDate(); 239 240 RegionSet inverted = new RegionSet(name); 241 int lastPos = 0; 242 int size = mergedStart.size(); 243 for (int i = 0; i < size; ++i) { 244 if (mergedStart.get(i) > lastPos) { 245 inverted.add(new Region(lastPos, mergedStart.get(i) - 1, name)); 246 } 247 lastPos = mergedEnd.get(i) + 1; 248 } 249 250 if (lastPos <= lastPosition) { 251 inverted.add(new Region(lastPos, lastPosition, name)); 252 } 253 254 return inverted; 255 } 256 257 /** 258 * Returns true if both {@link RegionSet}s contain the same positions and 259 * gaps. 260 */ 261 public boolean positionsEqual(RegionSet other) { 262 if (other == null) { 263 return false; 264 } 265 266 ensureMergedUpToDate(); 267 other.ensureMergedUpToDate(); 268 269 return mergedStart.equals(other.mergedStart) 270 && mergedEnd.equals(other.mergedEnd); 271 } 272 273 /** 274 * Comparator used for sorting the members of this set. Sorts ascending by 275 * start, then by end, then by name. 276 */ 277 private static class MemberComparator implements Comparator<Region> { 278 279 /** Unique instance of this comparator. */ 280 private final static MemberComparator INSTANCE = new MemberComparator(); 281 282 /** {@inheritDoc} */ 283 public int compare(Region region1, Region region2) { 284 int startDiff = region1.getStart() - region2.getStart(); 285 if (startDiff != 0) { 286 return startDiff; 287 } 288 289 int lengthDiff = region1.getLength() - region2.getLength(); 290 if (lengthDiff != 0) { 291 return lengthDiff; 292 } 293 294 return region1.getOrigin().compareTo(region2.getOrigin()); 295 } 296 } 297 298 /** {@inheritDoc} */ 299 @Override 300 public String toString() { 301 return "{" + StringUtils.concat(inner, ",") + "}"; 302 } 303 304 /** {@inheritDoc} */ 305 public boolean add(Region o) { 306 cleanSize = -1; 307 return inner.add(o); 308 } 309 310 /** {@inheritDoc} */ 311 public boolean addAll(Collection<? extends Region> c) { 312 cleanSize = -1; 313 return inner.addAll(c); 314 } 315 316 /** {@inheritDoc} */ 317 public void clear() { 318 cleanSize = -1; 319 inner.clear(); 320 } 321 322 /** {@inheritDoc} */ 323 public boolean contains(Object o) { 324 return inner.contains(o); 325 } 326 327 /** {@inheritDoc} */ 328 public boolean containsAll(Collection<?> c) { 329 return inner.containsAll(c); 330 } 331 332 /** {@inheritDoc} */ 333 @Override 334 public boolean equals(Object o) { 335 return inner.equals(o); 336 } 337 338 /** {@inheritDoc} */ 339 @Override 340 public int hashCode() { 341 return inner.hashCode(); 342 } 343 344 /** {@inheritDoc} */ 345 public boolean isEmpty() { 346 return inner.isEmpty(); 347 } 348 349 /** {@inheritDoc} */ 350 public Iterator<Region> iterator() { 351 return inner.iterator(); 352 } 353 354 /** {@inheritDoc} */ 355 public boolean remove(Object o) { 356 cleanSize = -1; 357 return inner.remove(o); 358 } 359 360 /** {@inheritDoc} */ 361 public boolean removeAll(Collection<?> c) { 362 cleanSize = -1; 363 return inner.removeAll(c); 364 } 365 366 /** {@inheritDoc} */ 367 public boolean retainAll(Collection<?> c) { 368 cleanSize = -1; 369 return inner.retainAll(c); 370 } 371 372 /** {@inheritDoc} */ 373 public int size() { 374 return inner.size(); 375 } 376 377 /** {@inheritDoc} */ 378 public Object[] toArray() { 379 return inner.toArray(); 380 } 381 382 /** {@inheritDoc} */ 383 public <T> T[] toArray(T[] a) { 384 return inner.toArray(a); 385 } 386 }