TreeSet.java revision adc854b798c1cfe3bfd4c27d68d5cee38ca617da
1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20 21import java.io.IOException; 22import java.io.ObjectInputStream; 23import java.io.ObjectOutputStream; 24import java.io.Serializable; 25 26/** 27 * TreeSet is an implementation of SortedSet. All optional operations (adding 28 * and removing) are supported. The elements can be any objects which are 29 * comparable to each other either using their natural order or a specified 30 * Comparator. 31 * 32 * @since Android 1.0 33 */ 34public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E>, Cloneable, 35 Serializable { 36 37 private static final long serialVersionUID = -2479143000061671589L; 38 39 private transient SortedMap<E, E> backingMap; 40 41 private TreeSet(SortedMap<E,E> map) { 42 this.backingMap = map; 43 } 44 45 /** 46 * Constructs a new empty instance of {@code TreeSet} which uses natural 47 * ordering. 48 * 49 * @since Android 1.0 50 */ 51 public TreeSet() { 52 backingMap = new TreeMap<E, E>(); 53 } 54 55 /** 56 * Constructs a new instance of {@code TreeSet} which uses natural ordering 57 * and containing the unique elements in the specified collection. 58 * 59 * @param collection 60 * the collection of elements to add. 61 * @throws ClassCastException 62 * when an element in the collection does not implement the 63 * Comparable interface, or the elements in the collection 64 * cannot be compared. 65 * @since Android 1.0 66 */ 67 public TreeSet(Collection<? extends E> collection) { 68 this(); 69 addAll(collection); 70 } 71 72 /** 73 * Constructs a new empty instance of {@code TreeSet} which uses the 74 * specified comparator. 75 * 76 * @param comparator 77 * the comparator to use. 78 * @since Android 1.0 79 */ 80 public TreeSet(Comparator<? super E> comparator) { 81 backingMap = new TreeMap<E, E>(comparator); 82 } 83 84 /** 85 * Constructs a new instance of {@code TreeSet} containing the elements of 86 * the specified SortedSet and using the same Comparator. 87 * 88 * @param set 89 * the SortedSet of elements to add. 90 * @since Android 1.0 91 */ 92 public TreeSet(SortedSet<E> set) { 93 this(set.comparator()); 94 Iterator<E> it = set.iterator(); 95 while (it.hasNext()) { 96 add(it.next()); 97 } 98 } 99 100 /** 101 * Adds the specified object to this {@code TreeSet}. 102 * 103 * @param object 104 * the object to add. 105 * @return {@code true} when this {@code TreeSet} did not already contain 106 * the object, {@code false} otherwise. 107 * @throws ClassCastException 108 * when the object cannot be compared with the elements in this 109 * {@code TreeSet}. 110 * @throws NullPointerException 111 * when the object is null and the comparator cannot handle 112 * null. 113 * @since Android 1.0 114 */ 115 @Override 116 public boolean add(E object) { 117 return backingMap.put(object, object) == null; 118 } 119 120 /** 121 * Adds the objects in the specified collection to this {@code TreeSet}. 122 * 123 * @param collection 124 * the collection of objects to add. 125 * @return {@code true} if this {@code TreeSet} was modified, {@code false} 126 * otherwise. 127 * @throws ClassCastException 128 * when an object in the collection cannot be compared with the 129 * elements in this {@code TreeSet}. 130 * @throws NullPointerException 131 * when an object in the collection is null and the comparator 132 * cannot handle null. 133 * @since Android 1.0 134 */ 135 @Override 136 public boolean addAll(Collection<? extends E> collection) { 137 return super.addAll(collection); 138 } 139 140 /** 141 * Removes all elements from this {@code TreeSet}, leaving it empty. 142 * 143 * @see #isEmpty 144 * @see #size 145 * @since Android 1.0 146 */ 147 @Override 148 public void clear() { 149 backingMap.clear(); 150 } 151 152 /** 153 * Returns a new {@code TreeSet} with the same elements, size and comparator 154 * as this {@code TreeSet}. 155 * 156 * @return a shallow copy of this {@code TreeSet}. 157 * @see java.lang.Cloneable 158 * @since Android 1.0 159 */ 160 @SuppressWarnings("unchecked") 161 @Override 162 public Object clone() { 163 try { 164 TreeSet<E> clone = (TreeSet<E>) super.clone(); 165 if (backingMap instanceof TreeMap) { 166 clone.backingMap = (SortedMap<E, E>) ((TreeMap<E, E>) backingMap).clone(); 167 } else { 168 clone.backingMap = new TreeMap<E, E>(backingMap); 169 } 170 return clone; 171 } catch (CloneNotSupportedException e) { 172 return null; 173 } 174 } 175 176 /** 177 * Returns the comparator used to compare elements in this {@code TreeSet}. 178 * 179 * @return a Comparator or null if the natural ordering is used 180 * @since Android 1.0 181 */ 182 public Comparator<? super E> comparator() { 183 return backingMap.comparator(); 184 } 185 186 /** 187 * Searches this {@code TreeSet} for the specified object. 188 * 189 * @param object 190 * the object to search for. 191 * @return {@code true} if {@code object} is an element of this 192 * {@code TreeSet}, {@code false} otherwise. 193 * @throws ClassCastException 194 * when the object cannot be compared with the elements in this 195 * {@code TreeSet}. 196 * @throws NullPointerException 197 * when the object is null and the comparator cannot handle 198 * null. 199 * @since Android 1.0 200 */ 201 @Override 202 public boolean contains(Object object) { 203 return backingMap.containsKey(object); 204 } 205 206 /** 207 * Returns the first element in this {@code TreeSet}. 208 * 209 * @return the first element. 210 * @throws NoSuchElementException 211 * when this {@code TreeSet} is empty. 212 * @since Android 1.0 213 */ 214 public E first() { 215 return backingMap.firstKey(); 216 } 217 218 /** 219 * Returns a SortedSet of the specified portion of this {@code TreeSet} 220 * which contains elements which are all less than the end element. The 221 * returned SortedSet is backed by this {@code TreeSet} so changes to one 222 * are reflected by the other. 223 * 224 * @param end 225 * the end element. 226 * @return a subset where the elements are less than {@code end} 227 * @throws ClassCastException 228 * when the end object cannot be compared with the elements in 229 * this {@code TreeSet}. 230 * @throws NullPointerException 231 * when the end object is null and the comparator cannot handle 232 * null. 233 * @since Android 1.0 234 */ 235 @SuppressWarnings("unchecked") 236 public SortedSet<E> headSet(E end) { 237 // Check for errors 238 Comparator<? super E> c = backingMap.comparator(); 239 if (c == null) { 240 ((Comparable<E>) end).compareTo(end); 241 } else { 242 c.compare(end, end); 243 } 244 return new TreeSet<E>(backingMap.headMap(end)); 245 } 246 247 /** 248 * Returns true if this {@code TreeSet} has no element, otherwise false. 249 * 250 * @return true if this {@code TreeSet} has no element. 251 * @see #size 252 * @since Android 1.0 253 */ 254 @Override 255 public boolean isEmpty() { 256 return backingMap.isEmpty(); 257 } 258 259 /** 260 * Returns an Iterator on the elements of this {@code TreeSet}. 261 * 262 * @return an Iterator on the elements of this {@code TreeSet}. 263 * @see Iterator 264 * @since Android 1.0 265 */ 266 @Override 267 public Iterator<E> iterator() { 268 return backingMap.keySet().iterator(); 269 } 270 271 /** 272 * Returns the last element in this {@code TreeSet}. The last element is 273 * the highest element. 274 * 275 * @return the last element. 276 * @throws NoSuchElementException 277 * when this {@code TreeSet} is empty. 278 * @since Android 1.0 279 */ 280 public E last() { 281 return backingMap.lastKey(); 282 } 283 284 /** 285 * Removes an occurrence of the specified object from this {@code TreeSet}. 286 * 287 * @param object 288 * the object to remove. 289 * @return {@code true} if this {@code TreeSet} was modified, {@code false} 290 * otherwise. 291 * @throws ClassCastException 292 * when the object cannot be compared with the elements in this 293 * {@code TreeSet}. 294 * @throws NullPointerException 295 * when the object is null and the comparator cannot handle 296 * null. 297 * @since Android 1.0 298 */ 299 @Override 300 public boolean remove(Object object) { 301 return backingMap.remove(object) != null; 302 } 303 304 /** 305 * Returns the number of elements in this {@code TreeSet}. 306 * 307 * @return the number of elements in this {@code TreeSet}. 308 * @since Android 1.0 309 */ 310 @Override 311 public int size() { 312 return backingMap.size(); 313 } 314 315 /** 316 * Returns a SortedSet of the specified portion of this {@code TreeSet} 317 * which contains elements greater or equal to the start element but less 318 * than the end element. The returned SortedSet is backed by this 319 * {@code TreeSet} so changes to one are reflected by the other. 320 * 321 * @param start 322 * the start element. 323 * @param end 324 * the end element (exclusive). 325 * @return a subset where the elements are greater or equal to {@code start} 326 * and less than {@code end} 327 * @throws ClassCastException 328 * when the start or end object cannot be compared with the 329 * elements in this {@code TreeSet}. 330 * @throws NullPointerException 331 * when the start or end object is null and the comparator 332 * cannot handle null. 333 * @since Android 1.0 334 */ 335 @SuppressWarnings("unchecked") 336 public SortedSet<E> subSet(E start, E end) { 337 Comparator<? super E> c = backingMap.comparator(); 338 if (c == null) { 339 if (((Comparable<E>) start).compareTo(end) <= 0) { 340 return new TreeSet<E>(backingMap.subMap(start, end)); 341 } 342 } else { 343 if (c.compare(start, end) <= 0) { 344 return new TreeSet<E>(backingMap.subMap(start, end)); 345 } 346 } 347 throw new IllegalArgumentException(); 348 } 349 350 /** 351 * Returns a SortedSet of the specified portion of this {@code TreeSet} 352 * which contains elements greater or equal to the start element. The 353 * returned SortedSet is backed by this {@code TreeSet} so changes to one 354 * are reflected by the other. 355 * 356 * @param start 357 * the start element. 358 * @return a subset where the elements are greater or equal to {@code start} 359 * @throws ClassCastException 360 * when the start object cannot be compared with the elements in 361 * this {@code TreeSet}. 362 * @throws NullPointerException 363 * when the start object is null and the comparator cannot 364 * handle null. 365 * @since Android 1.0 366 */ 367 @SuppressWarnings("unchecked") 368 public SortedSet<E> tailSet(E start) { 369 // Check for errors 370 Comparator<? super E> c = backingMap.comparator(); 371 if (c == null) { 372 ((Comparable<E>) start).compareTo(start); 373 } else { 374 c.compare(start, start); 375 } 376 return new TreeSet<E>(backingMap.tailMap(start)); 377 } 378 379 private void writeObject(ObjectOutputStream stream) throws IOException { 380 stream.defaultWriteObject(); 381 stream.writeObject(backingMap.comparator()); 382 int size = backingMap.size(); 383 stream.writeInt(size); 384 if (size > 0) { 385 Iterator<E> it = backingMap.keySet().iterator(); 386 while (it.hasNext()) { 387 stream.writeObject(it.next()); 388 } 389 } 390 } 391 392 @SuppressWarnings("unchecked") 393 private void readObject(ObjectInputStream stream) throws IOException, 394 ClassNotFoundException { 395 stream.defaultReadObject(); 396 TreeMap<E, E> map = new TreeMap<E, E>((Comparator<? super E>) stream.readObject()); 397 int size = stream.readInt(); 398 if (size > 0) { 399 E key = (E)stream.readObject(); 400 TreeMap.Entry<E,E> last = new TreeMap.Entry<E,E>(key,key); 401 map.root = last; 402 map.size = 1; 403 for (int i=1; i<size; i++) { 404 key = (E)stream.readObject(); 405 TreeMap.Entry<E,E> x = new TreeMap.Entry<E,E>(key,key); 406 x.parent = last; 407 last.right = x; 408 map.size++; 409 map.balance(x); 410 last = x; 411 } 412 } 413 backingMap = map; 414 } 415} 416