Clover coverage report - PLT Utilities Test Coverage (plt-20120304-r5436)
Coverage timestamp: Sat Mar 3 2012 22:01:56 CST
Overview   Package   File
    FRAMES   NO FRAMES  
file stats: LOC: 366   Methods: 33
NCLOC: 181   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
ExternallySortedSet.java 0% 0% 0% 0%
coverage
 1    /*BEGIN_COPYRIGHT_BLOCK*
 2   
 3    PLT Utilities BSD License
 4   
 5    Copyright (c) 2007-2010 JavaPLT group at Rice University
 6    All rights reserved.
 7   
 8    Developed by: Java Programming Languages Team
 9    Rice University
 10    http://www.cs.rice.edu/~javaplt/
 11   
 12    Redistribution and use in source and binary forms, with or without modification, are permitted
 13    provided that the following conditions are met:
 14   
 15    - Redistributions of source code must retain the above copyright notice, this list of conditions
 16    and the following disclaimer.
 17    - Redistributions in binary form must reproduce the above copyright notice, this list of
 18    conditions and the following disclaimer in the documentation and/or other materials provided
 19    with the distribution.
 20    - Neither the name of the JavaPLT group, Rice University, nor the names of the library's
 21    contributors may be used to endorse or promote products derived from this software without
 22    specific prior written permission.
 23   
 24    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
 25    IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 26    FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS AND
 27    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 28    DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 29    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 30    IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 31    OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 32   
 33    *END_COPYRIGHT_BLOCK*/
 34   
 35    package edu.rice.cs.plt.collect;
 36   
 37    import java.util.*;
 38    import edu.rice.cs.plt.iter.SizedIterable;
 39   
 40    /**
 41    * <p>A container class that <em>almost</em> implements the {@link java.util.SortedSet} interface;
 42    * the difference is that {@code add()} takes two parameters -- an element, along with a
 43    * corresponding {@link Comparable} that will be used to sort the set. Thus, the set is not
 44    * sorted based on any operations defined for the element type; rather, it is sorted according
 45    * to an external {@code orderBy} value. The {@code subSet()}, etc., methods are also adjusted
 46    * to take in {@code orderBy} values rather than set elements.</p>
 47    *
 48    * <p>The result is a set that works essentially like a {@link java.util.TreeSet}
 49    * of {@link edu.rice.cs.plt.tuple.Pair}s in which one of the Pair elements is a Comparable,
 50    * and for which a Comparator is correctly defined. One significant difference is that this
 51    * implementation does not return {@code true} for the expression {@code add(1, 1) && add(1, 2)},
 52    * while the explicit Pair implementation would (assuming the Set were initially empty).</p>
 53    *
 54    * <p>Note: the implementation relies heavily on hashing, so good performance is
 55    * dependent on elements of the set having an efficient {@code hashCode()} implementation.</p>
 56    */
 57    public class ExternallySortedSet<T, C extends Comparable<? super C>> implements SizedIterable<T> {
 58   
 59    /**
 60    * The sorted set of elements. Note that operations involving elements
 61    * <em>not</em> in {@ink #_orderByMap} should not be allowed, since the comparator
 62    * will not be able to handle such elements.
 63    */
 64    private final SortedSet<T> _set;
 65   
 66    /**
 67    * Maps elements to their corresponding {@code orderBy} value. Guaranteed to be defined
 68    * for <em>at least</em> every element of {@link #_set}.
 69    */
 70    private final Map<T, C> _orderByMap;
 71   
 72    /** May be {@code null}, indicating no bound. */
 73    private final C _lowerBound;
 74   
 75    /** May be {@code null}, indicating no bound. */
 76    private final C _upperBound;
 77   
 78    /** Creates an empty set. */
 79  0 public ExternallySortedSet() {
 80  0 _set = new TreeSet<T>(new Comparator<T>() {
 81    // Assumes that t1 and t2 are keys in _orderByMap.
 82  0 public int compare(T t1, T t2) {
 83  0 return _orderByMap.get(t1).compareTo(_orderByMap.get(t2));
 84    }
 85    });
 86   
 87  0 _orderByMap = new HashMap<T, C>();
 88  0 _lowerBound = null;
 89  0 _upperBound = null;
 90    }
 91   
 92    /** Creates a set with the specified fields. */
 93  0 private ExternallySortedSet(SortedSet<T> set, Map<T, C> orderByMap, C lowerBound,
 94    C upperBound) {
 95  0 _set = set;
 96  0 _orderByMap = orderByMap;
 97  0 _lowerBound = lowerBound;
 98  0 _upperBound = upperBound;
 99    }
 100   
 101  0 public boolean isEmpty() { return _set.isEmpty(); }
 102   
 103  0 public int size() { return _set.size(); }
 104   
 105  0 public int size(int bound) {
 106  0 int result = _set.size();
 107  0 return result <= bound ? result : bound;
 108    }
 109   
 110  0 public boolean isInfinite() { return false; }
 111   
 112  0 public boolean hasFixedSize() { return false; }
 113   
 114  0 public boolean isStatic() { return false; }
 115   
 116  0 public boolean contains(Object element) {
 117    // We can only call _set.contains() if a mapping is defined.
 118  0 return _orderByMap.containsKey(element) && _set.contains(element);
 119    }
 120   
 121    /**
 122    * @return An Iterator over the elements of the set in their sorted order. The
 123    * iterator supports {@link Iterator#remove()}.
 124    */
 125  0 public Iterator<T> iterator() {
 126  0 final Iterator<T> setI = _set.iterator();
 127  0 return new Iterator<T>() {
 128    private T _last = null;
 129   
 130  0 public boolean hasNext() { return setI.hasNext(); }
 131   
 132  0 public T next() {
 133  0 _last = setI.next();
 134  0 return _last;
 135    }
 136   
 137  0 public void remove() {
 138  0 if (_last == null) { throw new IllegalStateException(); }
 139    else {
 140  0 setI.remove();
 141  0 _orderByMap.remove(_last);
 142  0 _last = null;
 143    }
 144    }
 145   
 146    };
 147    }
 148   
 149    /**
 150    * @return An array of the set elements in their sorted order. As in the {@link Set} interface,
 151    * changes to the array will not be reflected in the set.
 152    */
 153  0 public Object[] toArray() { return _set.toArray(); }
 154   
 155    /**
 156    * @return An array of the set elements in their sorted order. As in the {@link Set} interface,
 157    * changes to the array will not be reflected in the set.
 158    */
 159  0 public <S> S[] toArray(S[] a) { return _set.toArray(a); }
 160   
 161    /**
 162    * Add {@code element} to the set, sorted by {@code orderBy}.
 163    * @return {@code true} iff {@code element} was not already in the set and could be added.
 164    * @throws IllegalArgumentException if {@code this} is a subset of a larger set, and the
 165    * element being added is outside the specified bounds.
 166    * @throws NullPointerException if {@code element} is {@code null}
 167    */
 168  0 public boolean add(T element, C orderBy) {
 169  0 if (element == null) { throw new NullPointerException(); }
 170    else {
 171  0 assertInBounds(orderBy);
 172  0 if (contains(element)) { return false; }
 173    else {
 174  0 _orderByMap.put(element, orderBy);
 175  0 _set.add(element);
 176  0 return true;
 177    }
 178    }
 179    }
 180   
 181    /**
 182    * Removes the element specified from the set.
 183    * @return {@code true} iff the set contained {@code element}.
 184    */
 185  0 public boolean remove(Object element) {
 186  0 if (contains(element)) {
 187  0 _set.remove(element);
 188  0 _orderByMap.remove(element);
 189  0 return true;
 190    }
 191  0 else { return false; }
 192    }
 193   
 194    /**
 195    * @return {@code true} iff the set contains each of the elements in {@code i}.
 196    */
 197  0 public boolean containsAll(Iterable<?> i) {
 198  0 for (Object o : i) { if (! contains(o)) { return false; } }
 199  0 return true;
 200    }
 201   
 202    /**
 203    * Add every element of {@code s} to this set (if it is not already present).
 204    * @return {@code true} iff the operation modified this set.
 205    */
 206  0 public boolean addAll(ExternallySortedSet<? extends T, ? extends C> s) {
 207  0 if ((_lowerBound == null ||
 208    (s._lowerBound != null && _lowerBound.compareTo(s._lowerBound) <= 0)) &&
 209    (_upperBound == null ||
 210    (s._upperBound != null && _upperBound.compareTo(s._upperBound) >= 0))) {
 211   
 212  0 return uncheckedAddAll(s);
 213    }
 214    else {
 215  0 return checkedAddAll(s);
 216    }
 217    }
 218   
 219    /** Add the elements by invoking {@link #add} on each one. */
 220  0 private boolean checkedAddAll(ExternallySortedSet<? extends T, ? extends C> s) {
 221  0 boolean result = false;
 222  0 for (T t : s) {
 223    // "|" instead of "||" to avoid short-circuit
 224  0 result = result | add(t, s._orderByMap.get(t));
 225    }
 226  0 return result;
 227    }
 228   
 229    /**
 230    * Add the elements without calling {@link #add} on each one, by simply taking the union
 231    * of the two data structures. This avoids a bounds check on each element. Assumes that each
 232    * element of {@code s} is within this set's bounds.
 233    */
 234  0 private boolean uncheckedAddAll(ExternallySortedSet<? extends T, ? extends C> s) {
 235  0 for (Map.Entry<? extends T, ? extends C> e : s._orderByMap.entrySet()) {
 236  0 if (! _orderByMap.containsKey(e.getKey())) { _orderByMap.put(e.getKey(), e.getValue()); }
 237    }
 238  0 boolean result = _set.addAll(s._set);
 239  0 return result;
 240    }
 241   
 242    /**
 243    * Removes every element of this set that is not in {@code c}.
 244    * @return {@code true} iff the operation modified this set.
 245    */
 246  0 public boolean retainAll(Collection<?> c) {
 247  0 boolean result = false;
 248  0 for (Iterator<T> i = iterator(); i.hasNext(); ) {
 249  0 T t = i.next();
 250  0 if (! c.contains(t)) { i.remove(); result = true; }
 251    }
 252  0 return result;
 253    }
 254   
 255    /**
 256    * Removes every element of this set that is not in {@code s}.
 257    * @return {@code true} iff the operation modified this set.
 258    */
 259  0 public boolean retainAll(ExternallySortedSet<?, ?> s) {
 260  0 boolean result = false;
 261  0 for (Iterator<T> i = iterator(); i.hasNext(); ) {
 262  0 T t = i.next();
 263  0 if (! s.contains(t)) { i.remove(); result = true; }
 264    }
 265  0 return result;
 266    }
 267   
 268    /**
 269    * Removes every element of this set that is in {@code c}.
 270    * @return {@code true} iff the operation modified this set.
 271    */
 272  0 public boolean removeAll(Iterable<?> i) {
 273  0 boolean result = false;
 274    // "|" instead of "||" to avoid short-circuit
 275  0 for (Object o : i) { result = result | remove(o); }
 276  0 return result;
 277    }
 278   
 279    /**
 280    * Removes every element of this set.
 281    */
 282  0 public void clear() {
 283    // We can't clear the map, because it might contain mappings outside the range of this set.
 284  0 for (T t : _set) { _orderByMap.remove(t); }
 285  0 _set.clear();
 286    }
 287   
 288    /**
 289    * @return A set containing every element in this set sorted from {@code from} (inclusive)
 290    * to {@code to} (exclusive). The result is backed by this set and bounded by
 291    * {@code from} and {@code to}; changes to either {@code this} or the result are
 292    * reflected by both.
 293    * @throws IllegalArgumentException if {@code from} or {@code to} is outside this set's bounds
 294    */
 295  0 public ExternallySortedSet<T, C> subSet(C from, C to) {
 296  0 assertInBounds(from);
 297  0 assertInBounds(to);
 298  0 T fromElement = firstAt(from);
 299  0 T toElement = firstAt(to);
 300   
 301  0 SortedSet<T> subSet;
 302  0 if (fromElement == null) {
 303  0 if (toElement == null) { subSet = _set; }
 304  0 else { subSet = _set.headSet(toElement); }
 305    }
 306  0 else if (toElement == null) { subSet = _set.tailSet(fromElement); }
 307  0 else { subSet = _set.subSet(fromElement, toElement); }
 308   
 309  0 return new ExternallySortedSet<T, C>(subSet, _orderByMap, from, to);
 310    }
 311   
 312    /**
 313    * @return A set containing every element in this set sorted before {@code to} (exclusive).
 314    * The result is backed by this set, so changes to either are reflected by both.
 315    * @throws IllegalArgumentException if {@code to} is outside this set's bounds
 316    */
 317  0 public ExternallySortedSet<T, C> headSet(C to) {
 318  0 assertInBounds(to);
 319  0 T toElement = firstAt(to);
 320  0 SortedSet<T> subSet;
 321  0 if (toElement == null) { subSet = _set; }
 322  0 else { subSet = _set.headSet(toElement); }
 323  0 return new ExternallySortedSet<T, C>(subSet, _orderByMap, null, to);
 324    }
 325   
 326    /**
 327    * @return A set containing every element in this set sorted after {@code from} (inclusive).
 328    * The result is backed by this set, so changes to either are reflected by both.
 329    * @throws IllegalArgumentException if {@code from} is outside this set's bounds
 330    */
 331  0 public ExternallySortedSet<T, C> tailSet(C from) {
 332  0 assertInBounds(from);
 333  0 T fromElement = firstAt(from);
 334  0 SortedSet<T> subSet;
 335  0 if (fromElement == null) { subSet = _set; }
 336  0 else { subSet = _set.tailSet(fromElement); }
 337  0 return new ExternallySortedSet<T, C>(subSet, _orderByMap, from, null);
 338    }
 339   
 340  0 public T first() { return _set.first(); }
 341   
 342  0 public T last() { return _set.last(); }
 343   
 344    /**
 345    * @return The first element in the set ordered at or after {@code c}, or {@code null} if
 346    * there is no such element.
 347    */
 348  0 private T firstAt(C c) {
 349  0 _orderByMap.put(null, c); // We *don't* put null in _set.
 350  0 SortedSet<T> resultSet = _set.tailSet(null);
 351  0 T result = null;
 352  0 if (! resultSet.isEmpty()) { result = resultSet.first(); }
 353  0 _orderByMap.remove(null);
 354  0 return result;
 355    }
 356   
 357  0 private void assertInBounds(C c) {
 358  0 if (_lowerBound != null && c.compareTo(_lowerBound) < 0) {
 359  0 throw new IllegalArgumentException(c + " is < this set's lower bound: " + _lowerBound);
 360    }
 361  0 if (_upperBound != null && c.compareTo(_upperBound) >= 0) {
 362  0 throw new IllegalArgumentException(c + " is >= this set's upper bound: " + _upperBound);
 363    }
 364    }
 365   
 366    }
 
CloverReport generated by Clover Code Coverage v1.3.14
Sat Mar 3 2012 22:01:57 CST.		   Open Source License registered to the DrJava Project. This license of Clover is provided to support the development of DrJava only.