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: * @see Collection 72: * @see Set 73: * @see HashSet 74: * @see LinkedHashSet 75: * @see Comparable 76: * @see Comparator 77: * @see Collections#synchronizedSortedSet(SortedSet) 78: * @see TreeMap 79: * @since 1.2 80: * @status updated to 1.4 81: */ 82: public class TreeSet extends AbstractSet 83: implements SortedSet, Cloneable, Serializable 84: { 85: /** 86: * Compatible with JDK 1.2. 87: */ 88: private static final long serialVersionUID = -2479143000061671589L; 89: 90: /** 91: * The SortedMap which backs this Set. 92: */ 93: // Not final because of readObject. This will always be one of TreeMap or 94: // TreeMap.SubMap, which both extend AbstractMap. 95: private transient SortedMap map; 96: 97: /** 98: * Construct a new TreeSet whose backing TreeMap using the "natural" 99: * ordering of keys. Elements that are not mutually comparable will cause 100: * ClassCastExceptions down the road. 101: * 102: * @see Comparable 103: */ 104: public TreeSet() 105: { 106: map = new TreeMap(); 107: } 108: 109: /** 110: * Construct a new TreeSet whose backing TreeMap uses the supplied 111: * Comparator. Elements that are not mutually comparable will cause 112: * ClassCastExceptions down the road. 113: * 114: * @param comparator the Comparator this Set will use 115: */ 116: public TreeSet(Comparator comparator) 117: { 118: map = new TreeMap(comparator); 119: } 120: 121: /** 122: * Construct a new TreeSet whose backing TreeMap uses the "natural" 123: * orering of the keys and which contains all of the elements in the 124: * supplied Collection. This runs in n*log(n) time. 125: * 126: * @param collection the new Set will be initialized with all 127: * of the elements in this Collection 128: * @throws ClassCastException if the elements of the collection are not 129: * comparable 130: * @throws NullPointerException if the collection is null 131: * @see Comparable 132: */ 133: public TreeSet(Collection collection) 134: { 135: map = new TreeMap(); 136: addAll(collection); 137: } 138: 139: /** 140: * Construct a new TreeSet, using the same key ordering as the supplied 141: * SortedSet and containing all of the elements in the supplied SortedSet. 142: * This constructor runs in linear time. 143: * 144: * @param sortedSet the new TreeSet will use this SortedSet's comparator 145: * and will initialize itself with all its elements 146: * @throws NullPointerException if sortedSet is null 147: */ 148: public TreeSet(SortedSet sortedSet) 149: { 150: map = new TreeMap(sortedSet.comparator()); 151: Iterator itr = sortedSet.iterator(); 152: ((TreeMap) map).putKeysLinear(itr, sortedSet.size()); 153: } 154: 155: /** 156: * This private constructor is used to implement the subSet() calls around 157: * a backing TreeMap.SubMap. 158: * 159: * @param backingMap the submap 160: */ 161: private TreeSet(SortedMap backingMap) 162: { 163: map = backingMap; 164: } 165: 166: /** 167: * Adds the spplied Object to the Set if it is not already in the Set; 168: * returns true if the element is added, false otherwise. 169: * 170: * @param obj the Object to be added to this Set 171: * @throws ClassCastException if the element cannot be compared with objects 172: * already in the set 173: */ 174: public boolean add(Object obj) 175: { 176: return map.put(obj, "") == null; 177: } 178: 179: /** 180: * Adds all of the elements in the supplied Collection to this TreeSet. 181: * 182: * @param c The collection to add 183: * @return true if the Set is altered, false otherwise 184: * @throws NullPointerException if c is null 185: * @throws ClassCastException if an element in c cannot be compared with 186: * objects already in the set 187: */ 188: public boolean addAll(Collection c) 189: { 190: boolean result = false; 191: int pos = c.size(); 192: Iterator itr = c.iterator(); 193: while (--pos >= 0) 194: result |= (map.put(itr.next(), "") == null); 195: return result; 196: } 197: 198: /** 199: * Removes all elements in this Set. 200: */ 201: public void clear() 202: { 203: map.clear(); 204: } 205: 206: /** 207: * Returns a shallow copy of this Set. The elements are not cloned. 208: * 209: * @return the cloned set 210: */ 211: public Object clone() 212: { 213: TreeSet copy = null; 214: try 215: { 216: copy = (TreeSet) super.clone(); 217: // Map may be either TreeMap or TreeMap.SubMap, hence the ugly casts. 218: copy.map = (SortedMap) ((AbstractMap) map).clone(); 219: } 220: catch (CloneNotSupportedException x) 221: { 222: // Impossible result. 223: } 224: return copy; 225: } 226: 227: /** 228: * Returns this Set's comparator. 229: * 230: * @return the comparator, or null if the set uses natural ordering 231: */ 232: public Comparator comparator() 233: { 234: return map.comparator(); 235: } 236: 237: /** 238: * Returns true if this Set contains the supplied Object, false otherwise. 239: * 240: * @param obj the Object to check for 241: * @return true if it is in the set 242: * @throws ClassCastException if obj cannot be compared with objects 243: * already in the set 244: */ 245: public boolean contains(Object obj) 246: { 247: return map.containsKey(obj); 248: } 249: 250: /** 251: * Returns the first (by order) element in this Set. 252: * 253: * @return the first element 254: * @throws NoSuchElementException if the set is empty 255: */ 256: public Object first() 257: { 258: return map.firstKey(); 259: } 260: 261: /** 262: * Returns a view of this Set including all elements less than 263: * <code>to</code>. The returned set is backed by the original, so changes 264: * in one appear in the other. The subset will throw an 265: * {@link IllegalArgumentException} for any attempt to access or add an 266: * element beyond the specified cutoff. The returned set does not include 267: * the endpoint; if you want inclusion, pass the successor element. 268: * 269: * @param to the (exclusive) cutoff point 270: * @return a view of the set less than the cutoff 271: * @throws ClassCastException if <code>to</code> is not compatible with 272: * the comparator (or is not Comparable, for natural ordering) 273: * @throws NullPointerException if to is null, but the comparator does not 274: * tolerate null elements 275: */ 276: public SortedSet headSet(Object to) 277: { 278: return new TreeSet(map.headMap(to)); 279: } 280: 281: /** 282: * Returns true if this Set has size 0, false otherwise. 283: * 284: * @return true if the set is empty 285: */ 286: public boolean isEmpty() 287: { 288: return map.isEmpty(); 289: } 290: 291: /** 292: * Returns in Iterator over the elements in this TreeSet, which traverses 293: * in ascending order. 294: * 295: * @return an iterator 296: */ 297: public Iterator iterator() 298: { 299: return map.keySet().iterator(); 300: } 301: 302: /** 303: * Returns the last (by order) element in this Set. 304: * 305: * @return the last element 306: * @throws NoSuchElementException if the set is empty 307: */ 308: public Object last() 309: { 310: return map.lastKey(); 311: } 312: 313: /** 314: * If the supplied Object is in this Set, it is removed, and true is 315: * returned; otherwise, false is returned. 316: * 317: * @param obj the Object to remove from this Set 318: * @return true if the set was modified 319: * @throws ClassCastException if obj cannot be compared to set elements 320: */ 321: public boolean remove(Object obj) 322: { 323: return map.remove(obj) != null; 324: } 325: 326: /** 327: * Returns the number of elements in this Set 328: * 329: * @return the set size 330: */ 331: public int size() 332: { 333: return map.size(); 334: } 335: 336: /** 337: * Returns a view of this Set including all elements greater or equal to 338: * <code>from</code> and less than <code>to</code> (a half-open interval). 339: * The returned set is backed by the original, so changes in one appear in 340: * the other. The subset will throw an {@link IllegalArgumentException} 341: * for any attempt to access or add an element beyond the specified cutoffs. 342: * The returned set includes the low endpoint but not the high; if you want 343: * to reverse this behavior on either end, pass in the successor element. 344: * 345: * @param from the (inclusive) low cutoff point 346: * @param to the (exclusive) high cutoff point 347: * @return a view of the set between the cutoffs 348: * @throws ClassCastException if either cutoff is not compatible with 349: * the comparator (or is not Comparable, for natural ordering) 350: * @throws NullPointerException if from or to is null, but the comparator 351: * does not tolerate null elements 352: * @throws IllegalArgumentException if from is greater than to 353: */ 354: public SortedSet subSet(Object from, Object to) 355: { 356: return new TreeSet(map.subMap(from, to)); 357: } 358: 359: /** 360: * Returns a view of this Set including all elements greater or equal to 361: * <code>from</code>. The returned set is backed by the original, so 362: * changes in one appear in the other. The subset will throw an 363: * {@link IllegalArgumentException} for any attempt to access or add an 364: * element beyond the specified cutoff. The returned set includes the 365: * endpoint; if you want to exclude it, pass in the successor element. 366: * 367: * @param from the (inclusive) low cutoff point 368: * @return a view of the set above the cutoff 369: * @throws ClassCastException if <code>from</code> is not compatible with 370: * the comparator (or is not Comparable, for natural ordering) 371: * @throws NullPointerException if from is null, but the comparator 372: * does not tolerate null elements 373: */ 374: public SortedSet tailSet(Object from) 375: { 376: return new TreeSet(map.tailMap(from)); 377: } 378: 379: /** 380: * Serializes this object to the given stream. 381: * 382: * @param s the stream to write to 383: * @throws IOException if the underlying stream fails 384: * @serialData the <i>comparator</i> (Object), followed by the set size 385: * (int), the the elements in sorted order (Object) 386: */ 387: private void writeObject(ObjectOutputStream s) throws IOException 388: { 389: s.defaultWriteObject(); 390: Iterator itr = map.keySet().iterator(); 391: int pos = map.size(); 392: s.writeObject(map.comparator()); 393: s.writeInt(pos); 394: while (--pos >= 0) 395: s.writeObject(itr.next()); 396: } 397: 398: /** 399: * Deserializes this object from the given stream. 400: * 401: * @param s the stream to read from 402: * @throws ClassNotFoundException if the underlying stream fails 403: * @throws IOException if the underlying stream fails 404: * @serialData the <i>comparator</i> (Object), followed by the set size 405: * (int), the the elements in sorted order (Object) 406: */ 407: private void readObject(ObjectInputStream s) 408: throws IOException, ClassNotFoundException 409: { 410: s.defaultReadObject(); 411: Comparator comparator = (Comparator) s.readObject(); 412: int size = s.readInt(); 413: map = new TreeMap(comparator); 414: ((TreeMap) map).putFromObjStream(s, size, false); 415: } 416: }