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    }