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