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 }