| Frames | No Frames |
1: /* TreeSet.java -- a class providing a TreeMap-backed SortedSet 2: Copyright (C) 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.util; 40: 41: import java.io.IOException; 42: import java.io.ObjectInputStream; 43: import java.io.ObjectOutputStream; 44: import java.io.Serializable; 45: 46: /** 47: * This class provides a TreeMap-backed implementation of the SortedSet 48: * interface. The elements will be sorted according to their <i>natural 49: * order</i>, or according to the provided <code>Comparator</code>.<p> 50: * 51: * Most operations are O(log n), but there is so much overhead that this 52: * makes small sets expensive. Note that the ordering must be <i>consistent 53: * with equals</i> to correctly implement the Set interface. If this 54: * condition is violated, the set is still well-behaved, but you may have 55: * suprising results when comparing it to other sets.<p> 56: * 57: * This implementation is not synchronized. If you need to share this between 58: * multiple threads, do something like:<br> 59: * <code>SortedSet s 60: * = Collections.synchronizedSortedSet(new TreeSet(...));</code><p> 61: * 62: * The iterators are <i>fail-fast</i>, meaning that any structural 63: * modification, except for <code>remove()</code> called on the iterator 64: * itself, cause the iterator to throw a 65: * <code>ConcurrentModificationException</code> rather than exhibit 66: * non-deterministic behavior. 67: * 68: * @author Jon Zeppieri 69: * @author Bryce McKinlay 70: * @author Eric Blake (ebb9@email.byu.edu) 71: * @author Tom Tromey (tromey@redhat.com) 72: * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 73: * @see Collection 74: * @see Set 75: * @see HashSet 76: * @see LinkedHashSet 77: * @see Comparable 78: * @see Comparator 79: * @see Collections#synchronizedSortedSet(SortedSet) 80: * @see TreeMap 81: * @since 1.2 82: * @status updated to 1.6 83: */ 84: public class TreeSet<T> extends AbstractSet<T> 85: implements NavigableSet<T>, Cloneable, Serializable 86: { 87: /** 88: * Compatible with JDK 1.2. 89: */ 90: private static final long serialVersionUID = -2479143000061671589L; 91: 92: /** 93: * The NavigableMap which backs this Set. 94: */ 95: // Not final because of readObject. This will always be one of TreeMap or 96: // TreeMap.SubMap, which both extend AbstractMap. 97: private transient NavigableMap<T, String> map; 98: 99: /** 100: * Construct a new TreeSet whose backing TreeMap using the "natural" 101: * ordering of keys. Elements that are not mutually comparable will cause 102: * ClassCastExceptions down the road. 103: * 104: * @see Comparable 105: */ 106: public TreeSet() 107: { 108: map = new TreeMap<T, String>(); 109: } 110: 111: /** 112: * Construct a new TreeSet whose backing TreeMap uses the supplied 113: * Comparator. Elements that are not mutually comparable will cause 114: * ClassCastExceptions down the road. 115: * 116: * @param comparator the Comparator this Set will use 117: */ 118: public TreeSet(Comparator<? super T> comparator) 119: { 120: map = new TreeMap<T, String>(comparator); 121: } 122: 123: /** 124: * Construct a new TreeSet whose backing TreeMap uses the "natural" 125: * orering of the keys and which contains all of the elements in the 126: * supplied Collection. This runs in n*log(n) time. 127: * 128: * @param collection the new Set will be initialized with all 129: * of the elements in this Collection 130: * @throws ClassCastException if the elements of the collection are not 131: * comparable 132: * @throws NullPointerException if the collection is null 133: * @see Comparable 134: */ 135: public TreeSet(Collection<? extends T> collection) 136: { 137: map = new TreeMap<T, String>(); 138: addAll(collection); 139: } 140: 141: /** 142: * Construct a new TreeSet, using the same key ordering as the supplied 143: * SortedSet and containing all of the elements in the supplied SortedSet. 144: * This constructor runs in linear time. 145: * 146: * @param sortedSet the new TreeSet will use this SortedSet's comparator 147: * and will initialize itself with all its elements 148: * @throws NullPointerException if sortedSet is null 149: */ 150: public TreeSet(SortedSet<T> sortedSet) 151: { 152: Iterator<T> itr; 153: 154: map = new TreeMap<T, String> 155: ((Comparator<? super T>)sortedSet.comparator()); 156: itr = ((SortedSet<T>) sortedSet).iterator(); 157: ((TreeMap<T, String>) map).putKeysLinear(itr, sortedSet.size()); 158: } 159: 160: /** 161: * This private constructor is used to implement the subSet() calls around 162: * a backing TreeMap.SubMap. 163: * 164: * @param backingMap the submap 165: */ 166: private TreeSet(NavigableMap<T,String> backingMap) 167: { 168: map = backingMap; 169: } 170: 171: /** 172: * Adds the spplied Object to the Set if it is not already in the Set; 173: * returns true if the element is added, false otherwise. 174: * 175: * @param obj the Object to be added to this Set 176: * @throws ClassCastException if the element cannot be compared with objects 177: * already in the set 178: */ 179: public boolean add(T obj) 180: { 181: return map.put(obj, "") == null; 182: } 183: 184: /** 185: * Adds all of the elements in the supplied Collection to this TreeSet. 186: * 187: * @param c The collection to add 188: * @return true if the Set is altered, false otherwise 189: * @throws NullPointerException if c is null 190: * @throws ClassCastException if an element in c cannot be compared with 191: * objects already in the set 192: */ 193: public boolean addAll(Collection<? extends T> c) 194: { 195: boolean result = false; 196: int pos = c.size(); 197: Iterator<? extends T> itr = c.iterator(); 198: while (--pos >= 0) 199: result |= (map.put(itr.next(), "") == null); 200: return result; 201: } 202: 203: /** 204: * Removes all elements in this Set. 205: */ 206: public void clear() 207: { 208: map.clear(); 209: } 210: 211: /** 212: * Returns a shallow copy of this Set. The elements are not cloned. 213: * 214: * @return the cloned set 215: */ 216: public Object clone() 217: { 218: TreeSet<T> copy = null; 219: try 220: { 221: copy = (TreeSet<T>) super.clone(); 222: // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts. 223: copy.map = (NavigableMap<T, String>) ((AbstractMap<T, String>) map).clone(); 224: } 225: catch (CloneNotSupportedException x) 226: { 227: // Impossible result. 228: } 229: return copy; 230: } 231: 232: /** 233: * Returns this Set's comparator. 234: * 235: * @return the comparator, or null if the set uses natural ordering 236: */ 237: public Comparator<? super T> comparator() 238: { 239: return map.comparator(); 240: } 241: 242: /** 243: * Returns true if this Set contains the supplied Object, false otherwise. 244: * 245: * @param obj the Object to check for 246: * @return true if it is in the set 247: * @throws ClassCastException if obj cannot be compared with objects 248: * already in the set 249: */ 250: public boolean contains(Object obj) 251: { 252: return map.containsKey(obj); 253: } 254: 255: /** 256: * Returns the first (by order) element in this Set. 257: * 258: * @return the first element 259: * @throws NoSuchElementException if the set is empty 260: */ 261: public T first() 262: { 263: return map.firstKey(); 264: } 265: 266: /** 267: * Returns a view of this Set including all elements less than 268: * <code>to</code>. The returned set is backed by the original, so changes 269: * in one appear in the other. The subset will throw an 270: * {@link IllegalArgumentException} for any attempt to access or add an 271: * element beyond the specified cutoff. The returned set does not include 272: * the endpoint; if you want inclusion, pass the successor element or 273: * call {@link #headSet(T,boolean)}. This call is equivalent to 274: * <code>headSet(to, false)</code>. 275: * 276: * @param to the (exclusive) cutoff point 277: * @return a view of the set less than the cutoff 278: * @throws ClassCastException if <code>to</code> is not compatible with 279: * the comparator (or is not Comparable, for natural ordering) 280: * @throws NullPointerException if to is null, but the comparator does not 281: * tolerate null elements 282: */ 283: public SortedSet<T> headSet(T to) 284: { 285: return headSet(to, false); 286: } 287: 288: /** 289: * Returns a view of this Set including all elements less than 290: * (or equal to, if <code>inclusive</code> is true) <code>to</code>. 291: * The returned set is backed by the original, so changes 292: * in one appear in the other. The subset will throw an 293: * {@link IllegalArgumentException} for any attempt to access or add an 294: * element beyond the specified cutoff. 295: * 296: * @param to the cutoff point 297: * @param inclusive true if <code>to</code> should be included. 298: * @return a view of the set for the specified range. 299: * @throws ClassCastException if <code>to</code> is not compatible with 300: * the comparator (or is not Comparable, for natural ordering) 301: * @throws NullPointerException if to is null, but the comparator does not 302: * tolerate null elements 303: */ 304: public NavigableSet<T> headSet(T to, boolean inclusive) 305: { 306: return new TreeSet<T>(map.headMap(to, inclusive)); 307: } 308: 309: /** 310: * Returns true if this Set has size 0, false otherwise. 311: * 312: * @return true if the set is empty 313: */ 314: public boolean isEmpty() 315: { 316: return map.isEmpty(); 317: } 318: 319: /** 320: * Returns in Iterator over the elements in this TreeSet, which traverses 321: * in ascending order. 322: * 323: * @return an iterator 324: */ 325: public Iterator<T> iterator() 326: { 327: return map.keySet().iterator(); 328: } 329: 330: /** 331: * Returns the last (by order) element in this Set. 332: * 333: * @return the last element 334: * @throws NoSuchElementException if the set is empty 335: */ 336: public T last() 337: { 338: return map.lastKey(); 339: } 340: 341: /** 342: * If the supplied Object is in this Set, it is removed, and true is 343: * returned; otherwise, false is returned. 344: * 345: * @param obj the Object to remove from this Set 346: * @return true if the set was modified 347: * @throws ClassCastException if obj cannot be compared to set elements 348: */ 349: public boolean remove(Object obj) 350: { 351: return map.remove(obj) != null; 352: } 353: 354: /** 355: * Returns the number of elements in this Set 356: * 357: * @return the set size 358: */ 359: public int size() 360: { 361: return map.size(); 362: } 363: 364: /** 365: * Returns a view of this Set including all elements greater or equal to 366: * <code>from</code> and less than <code>to</code> (a half-open interval). 367: * The returned set is backed by the original, so changes in one appear in 368: * the other. The subset will throw an {@link IllegalArgumentException} 369: * for any attempt to access or add an element beyond the specified cutoffs. 370: * The returned set includes the low endpoint but not the high; if you want 371: * to reverse this behavior on either end, pass in the successor element 372: * or call {@link #subSet(T,boolean,T,boolean)}. This is equivalent to 373: * calling <code>subSet(from,true,to,false)</code>. 374: * 375: * @param from the (inclusive) low cutoff point 376: * @param to the (exclusive) high cutoff point 377: * @return a view of the set between the cutoffs 378: * @throws ClassCastException if either cutoff is not compatible with 379: * the comparator (or is not Comparable, for natural ordering) 380: * @throws NullPointerException if from or to is null, but the comparator 381: * does not tolerate null elements 382: * @throws IllegalArgumentException if from is greater than to 383: */ 384: public SortedSet<T> subSet(T from, T to) 385: { 386: return subSet(from, true, to, false); 387: } 388: 389: /** 390: * Returns a view of this Set including all elements greater than (or equal to, 391: * if <code>fromInclusive</code> is true</code> <code>from</code> and less than 392: * (or equal to, if <code>toInclusive</code> is true) <code>to</code>. 393: * The returned set is backed by the original, so changes in one appear in 394: * the other. The subset will throw an {@link IllegalArgumentException} 395: * for any attempt to access or add an element beyond the specified cutoffs. 396: * 397: * @param from the low cutoff point 398: * @param fromInclusive true if <code>from</code> should be included. 399: * @param to the high cutoff point 400: * @param toInclusive true if <code>to</code> should be included. 401: * @return a view of the set for the specified range. 402: * @throws ClassCastException if either cutoff is not compatible with 403: * the comparator (or is not Comparable, for natural ordering) 404: * @throws NullPointerException if from or to is null, but the comparator 405: * does not tolerate null elements 406: * @throws IllegalArgumentException if from is greater than to 407: */ 408: public NavigableSet<T> subSet(T from, boolean fromInclusive, 409: T to, boolean toInclusive) 410: { 411: return new TreeSet<T>(map.subMap(from, fromInclusive, 412: to, toInclusive)); 413: } 414: 415: /** 416: * Returns a view of this Set including all elements greater or equal to 417: * <code>from</code>. The returned set is backed by the original, so 418: * changes in one appear in the other. The subset will throw an 419: * {@link IllegalArgumentException} for any attempt to access or add an 420: * element beyond the specified cutoff. The returned set includes the 421: * endpoint; if you want to exclude it, pass in the successor element 422: * or call {@link #tailSet(T,boolean)}. This is equivalent to calling 423: * <code>tailSet(from, true)</code>. 424: * 425: * @param from the (inclusive) low cutoff point 426: * @return a view of the set above the cutoff 427: * @throws ClassCastException if <code>from</code> is not compatible with 428: * the comparator (or is not Comparable, for natural ordering) 429: * @throws NullPointerException if from is null, but the comparator 430: * does not tolerate null elements 431: */ 432: public SortedSet<T> tailSet(T from) 433: { 434: return tailSet(from, true); 435: } 436: 437: /** 438: * Returns a view of this Set including all elements greater (or equal to, 439: * if <code>inclusive</code> is true) <code>from</code>. The returned set 440: * is backed by the original, so changes in one appear in the other. The 441: * subset will throw an {@link IllegalArgumentException} for any attempt 442: * to access or add an element beyond the specified cutoff. 443: * 444: * @param from the low cutoff point. 445: * @param inclusive true if <code>from</code> should be included. 446: * @return a view of the set for the specified range. 447: * @throws ClassCastException if <code>from</code> is not compatible with 448: * the comparator (or is not Comparable, for natural ordering) 449: * @throws NullPointerException if from is null, but the comparator 450: * does not tolerate null elements 451: */ 452: public NavigableSet<T> tailSet(T from, boolean inclusive) 453: { 454: return new TreeSet<T>(map.tailMap(from, inclusive)); 455: } 456: 457: /** 458: * Serializes this object to the given stream. 459: * 460: * @param s the stream to write to 461: * @throws IOException if the underlying stream fails 462: * @serialData the <i>comparator</i> (Object), followed by the set size 463: * (int), the the elements in sorted order (Object) 464: */ 465: private void writeObject(ObjectOutputStream s) throws IOException 466: { 467: s.defaultWriteObject(); 468: Iterator<T> itr = map.keySet().iterator(); 469: int pos = map.size(); 470: s.writeObject(map.comparator()); 471: s.writeInt(pos); 472: while (--pos >= 0) 473: s.writeObject(itr.next()); 474: } 475: 476: /** 477: * Deserializes this object from the given stream. 478: * 479: * @param s the stream to read from 480: * @throws ClassNotFoundException if the underlying stream fails 481: * @throws IOException if the underlying stream fails 482: * @serialData the <i>comparator</i> (Object), followed by the set size 483: * (int), the the elements in sorted order (Object) 484: */ 485: private void readObject(ObjectInputStream s) 486: throws IOException, ClassNotFoundException 487: { 488: s.defaultReadObject(); 489: Comparator<? super T> comparator = (Comparator<? super T>) s.readObject(); 490: int size = s.readInt(); 491: map = new TreeMap<T, String>(comparator); 492: ((TreeMap<T, String>) map).putFromObjStream(s, size, false); 493: } 494: 495: /** 496: * Returns the least or lowest element in the set greater than or 497: * equal to the given element, or <code>null</code> if there is 498: * no such element. 499: * 500: * @param e the element relative to the returned element. 501: * @return the least element greater than or equal 502: * to the given element, or <code>null</code> if there is 503: * no such element. 504: * @throws ClassCastException if the specified element can not 505: * be compared with those in the map. 506: * @throws NullPointerException if the element is <code>null</code> 507: * and this set either uses natural 508: * ordering or a comparator that does 509: * not permit null elements. 510: * @since 1.6 511: */ 512: public T ceiling(T e) 513: { 514: return map.ceilingKey(e); 515: } 516: 517: /** 518: * Returns an iterator over the elements of this set in descending 519: * order. This is equivalent to calling 520: * <code>descendingSet().iterator()</code>. 521: * 522: * @return an iterator over the elements in descending order. 523: * @since 1.6 524: */ 525: public Iterator<T> descendingIterator() 526: { 527: return descendingSet().iterator(); 528: } 529: 530: /** 531: * Returns a view of the set in reverse order. The descending set 532: * is backed by the original set, so that changes affect both sets. 533: * Any changes occurring to either set while an iteration is taking 534: * place (with the exception of a {@link Iterator#remove()} operation) 535: * result in undefined behaviour from the iteration. The ordering 536: * of the descending set is the same as for a set with a 537: * {@link Comparator} given by {@link Collections#reverseOrder()}, 538: * and calling {@link #descendingSet()} on the descending set itself 539: * results in a view equivalent to the original set. 540: * 541: * @return a reverse order view of the set. 542: * @since 1.6 543: */ 544: public NavigableSet<T> descendingSet() 545: { 546: return map.descendingKeySet(); 547: } 548: 549: /** 550: * Returns the greatest or highest element in the set less than or 551: * equal to the given element, or <code>null</code> if there is 552: * no such element. 553: * 554: * @param e the element relative to the returned element. 555: * @return the greatest element less than or equal 556: * to the given element, or <code>null</code> if there is 557: * no such element. 558: * @throws ClassCastException if the specified element can not 559: * be compared with those in the map. 560: * @throws NullPointerException if the element is <code>null</code> 561: * and this set either uses natural 562: * ordering or a comparator that does 563: * not permit null elements. 564: * @since 1.6 565: */ 566: public T floor(T e) 567: { 568: return map.floorKey(e); 569: } 570: 571: /** 572: * Returns the least or lowest element in the set strictly greater 573: * than the given element, or <code>null</code> if there is 574: * no such element. 575: * 576: * @param e the element relative to the returned element. 577: * @return the least element greater than 578: * the given element, or <code>null</code> if there is 579: * no such element. 580: * @throws ClassCastException if the specified element can not 581: * be compared with those in the map. 582: * @throws NullPointerException if the element is <code>null</code> 583: * and this set either uses natural 584: * ordering or a comparator that does 585: * not permit null elements. 586: * @since 1.6 587: */ 588: public T higher(T e) 589: { 590: return map.higherKey(e); 591: } 592: 593: /** 594: * Returns the greatest or highest element in the set strictly less 595: * than the given element, or <code>null</code> if there is 596: * no such element. 597: * 598: * @param e the element relative to the returned element. 599: * @return the greatest element less than 600: * the given element, or <code>null</code> if there is 601: * no such element. 602: * @throws ClassCastException if the specified element can not 603: * be compared with those in the map. 604: * @throws NullPointerException if the element is <code>null</code> 605: * and this set either uses natural 606: * ordering or a comparator that does 607: * not permit null elements. 608: * @since 1.6 609: */ 610: public T lower(T e) 611: { 612: return map.lowerKey(e); 613: } 614: 615: /** 616: * Removes and returns the least or lowest element in the set, 617: * or <code>null</code> if the map is empty. 618: * 619: * @return the removed first element, or <code>null</code> if the 620: * map is empty. 621: * @since 1.6 622: */ 623: public T pollFirst() 624: { 625: return map.pollFirstEntry().getKey(); 626: } 627: 628: /** 629: * Removes and returns the greatest or highest element in the set, 630: * or <code>null</code> if the map is empty. 631: * 632: * @return the removed last element, or <code>null</code> if the 633: * map is empty. 634: * @since 1.6 635: */ 636: public T pollLast() 637: { 638: return map.pollLastEntry().getKey(); 639: } 640: 641: }