001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: import java.io.IOException;
021: import java.io.ObjectInputStream;
022: import java.io.ObjectOutputStream;
023: import java.io.Serializable;
024:
025: /**
026: * TreeSet is an implementation of SortedSet. All optional operations are
027: * supported, adding and removing. The elements can be any objects which are
028: * comparable to each other either using their natural order or a specified
029: * Comparator.
030: *
031: * @since 1.2
032: */
033: public class TreeSet<E> extends AbstractSet<E> implements SortedSet<E>,
034: Cloneable, Serializable {
035:
036: private static final long serialVersionUID = -2479143000061671589L;
037:
038: private transient SortedMap<E, E> backingMap;
039:
040: private TreeSet(SortedMap<E, E> map) {
041: this .backingMap = map;
042: }
043:
044: /**
045: * Constructs a new empty instance of TreeSet which uses natural ordering.
046: *
047: */
048: public TreeSet() {
049: backingMap = new TreeMap<E, E>();
050: }
051:
052: /**
053: * Constructs a new instance of TreeSet which uses natural ordering and
054: * containing the unique elements in the specified collection.
055: *
056: * @param collection
057: * the collection of elements to add
058: *
059: * @exception ClassCastException
060: * when an element in the Collection does not implement the
061: * Comparable interface, or the elements in the Collection
062: * cannot be compared
063: */
064: public TreeSet(Collection<? extends E> collection) {
065: this ();
066: addAll(collection);
067: }
068:
069: /**
070: * Constructs a new empty instance of TreeSet which uses the specified
071: * Comparator.
072: *
073: * @param comparator
074: * the Comparator
075: */
076: public TreeSet(Comparator<? super E> comparator) {
077: backingMap = new TreeMap<E, E>(comparator);
078: }
079:
080: /**
081: * Constructs a new instance of TreeSet containing the elements in the
082: * specified SortedSet and using the same Comparator.
083: *
084: * @param set
085: * the SortedSet of elements to add
086: */
087: public TreeSet(SortedSet<E> set) {
088: this (set.comparator());
089: Iterator<E> it = set.iterator();
090: while (it.hasNext()) {
091: add(it.next());
092: }
093: }
094:
095: /**
096: * Adds the specified object to this TreeSet.
097: *
098: * @param object
099: * the object to add
100: * @return true when this TreeSet did not already contain the object, false
101: * otherwise
102: *
103: * @exception ClassCastException
104: * when the object cannot be compared with the elements in
105: * this TreeSet
106: * @exception NullPointerException
107: * when the object is null and the comparator cannot handle
108: * null
109: */
110: @Override
111: public boolean add(E object) {
112: return backingMap.put(object, object) == null;
113: }
114:
115: /**
116: * Adds the objects in the specified Collection to this TreeSet.
117: *
118: * @param collection
119: * the Collection of objects
120: * @return true if this TreeSet is modified, false otherwise
121: *
122: * @exception ClassCastException
123: * when an object in the Collection cannot be compared with
124: * the elements in this TreeSet
125: * @exception NullPointerException
126: * when an object in the Collection is null and the
127: * comparator cannot handle null
128: */
129: @Override
130: public boolean addAll(Collection<? extends E> collection) {
131: return super .addAll(collection);
132: }
133:
134: /**
135: * Removes all elements from this TreeSet, leaving it empty.
136: *
137: * @see #isEmpty
138: * @see #size
139: */
140: @Override
141: public void clear() {
142: backingMap.clear();
143: }
144:
145: /**
146: * Answers a new TreeSet with the same elements, size and comparator as this
147: * TreeSet.
148: *
149: * @return a shallow copy of this TreeSet
150: *
151: * @see java.lang.Cloneable
152: */
153: @SuppressWarnings("unchecked")
154: @Override
155: public Object clone() {
156: try {
157: TreeSet<E> clone = (TreeSet<E>) super .clone();
158: if (backingMap instanceof TreeMap) {
159: clone.backingMap = (SortedMap<E, E>) ((TreeMap<E, E>) backingMap)
160: .clone();
161: } else {
162: clone.backingMap = new TreeMap<E, E>(backingMap);
163: }
164: return clone;
165: } catch (CloneNotSupportedException e) {
166: return null;
167: }
168: }
169:
170: /**
171: * Answers the Comparator used to compare elements in this TreeSet.
172: *
173: * @return a Comparator or null if the natural ordering is used
174: */
175: public Comparator<? super E> comparator() {
176: return backingMap.comparator();
177: }
178:
179: /**
180: * Searches this TreeSet for the specified object.
181: *
182: * @param object
183: * the object to search for
184: * @return true if <code>object</code> is an element of this TreeSet,
185: * false otherwise
186: *
187: * @exception ClassCastException
188: * when the object cannot be compared with the elements in
189: * this TreeSet
190: * @exception NullPointerException
191: * when the object is null and the comparator cannot handle
192: * null
193: */
194: @Override
195: public boolean contains(Object object) {
196: return backingMap.containsKey(object);
197: }
198:
199: /**
200: * Answers the first element in this TreeSet.
201: *
202: * @return the first element
203: *
204: * @exception NoSuchElementException
205: * when this TreeSet is empty
206: */
207: public E first() {
208: return backingMap.firstKey();
209: }
210:
211: /**
212: * Answers a SortedSet of the specified portion of this TreeSet which
213: * contains elements less than the end element. The returned SortedSet is
214: * backed by this TreeSet so changes to one are reflected by the other.
215: *
216: * @param end
217: * the end element
218: * @return a subset where the elements are less than <code>end</code>
219: *
220: * @exception ClassCastException
221: * when the end object cannot be compared with the elements
222: * in this TreeSet
223: * @exception NullPointerException
224: * when the end object is null and the comparator cannot
225: * handle null
226: */
227: @SuppressWarnings("unchecked")
228: public SortedSet<E> headSet(E end) {
229: // Check for errors
230: Comparator<? super E> c = backingMap.comparator();
231: if (c == null) {
232: ((Comparable<E>) end).compareTo(end);
233: } else {
234: c.compare(end, end);
235: }
236: return new TreeSet<E>(backingMap.headMap(end));
237: }
238:
239: /**
240: * Answers if this TreeSet has no elements, a size of zero.
241: *
242: * @return true if this TreeSet has no elements, false otherwise
243: *
244: * @see #size
245: */
246: @Override
247: public boolean isEmpty() {
248: return backingMap.isEmpty();
249: }
250:
251: /**
252: * Answers an Iterator on the elements of this TreeSet.
253: *
254: * @return an Iterator on the elements of this TreeSet
255: *
256: * @see Iterator
257: */
258: @Override
259: public Iterator<E> iterator() {
260: return backingMap.keySet().iterator();
261: }
262:
263: /**
264: * Answers the last element in this TreeSet.
265: *
266: * @return the last element
267: *
268: * @exception NoSuchElementException
269: * when this TreeSet is empty
270: */
271: public E last() {
272: return backingMap.lastKey();
273: }
274:
275: /**
276: * Removes an occurrence of the specified object from this TreeSet.
277: *
278: * @param object
279: * the object to remove
280: * @return true if this TreeSet is modified, false otherwise
281: *
282: * @exception ClassCastException
283: * when the object cannot be compared with the elements in
284: * this TreeSet
285: * @exception NullPointerException
286: * when the object is null and the comparator cannot handle
287: * null
288: */
289: @Override
290: public boolean remove(Object object) {
291: return backingMap.remove(object) != null;
292: }
293:
294: /**
295: * Answers the number of elements in this TreeSet.
296: *
297: * @return the number of elements in this TreeSet
298: */
299: @Override
300: public int size() {
301: return backingMap.size();
302: }
303:
304: /**
305: * Answers a SortedSet of the specified portion of this TreeSet which
306: * contains elements greater or equal to the start element but less than the
307: * end element. The returned SortedSet is backed by this TreeSet so changes
308: * to one are reflected by the other.
309: *
310: * @param start
311: * the start element
312: * @param end
313: * the end element
314: * @return a subset where the elements are greater or equal to
315: * <code>start</code> and less than <code>end</code>
316: *
317: * @exception ClassCastException
318: * when the start or end object cannot be compared with the
319: * elements in this TreeSet
320: * @exception NullPointerException
321: * when the start or end object is null and the comparator
322: * cannot handle null
323: */
324: @SuppressWarnings("unchecked")
325: public SortedSet<E> subSet(E start, E end) {
326: Comparator<? super E> c = backingMap.comparator();
327: if (c == null) {
328: if (((Comparable<E>) start).compareTo(end) <= 0) {
329: return new TreeSet<E>(backingMap.subMap(start, end));
330: }
331: } else {
332: if (c.compare(start, end) <= 0) {
333: return new TreeSet<E>(backingMap.subMap(start, end));
334: }
335: }
336: throw new IllegalArgumentException();
337: }
338:
339: /**
340: * Answers a SortedSet of the specified portion of this TreeSet which
341: * contains elements greater or equal to the start element. The returned
342: * SortedSet is backed by this TreeSet so changes to one are reflected by
343: * the other.
344: *
345: * @param start
346: * the start element
347: * @return a subset where the elements are greater or equal to
348: * <code>start</code>
349: *
350: * @exception ClassCastException
351: * when the start object cannot be compared with the elements
352: * in this TreeSet
353: * @exception NullPointerException
354: * when the start object is null and the comparator cannot
355: * handle null
356: */
357: @SuppressWarnings("unchecked")
358: public SortedSet<E> tailSet(E start) {
359: // Check for errors
360: Comparator<? super E> c = backingMap.comparator();
361: if (c == null) {
362: ((Comparable<E>) start).compareTo(start);
363: } else {
364: c.compare(start, start);
365: }
366: return new TreeSet<E>(backingMap.tailMap(start));
367: }
368:
369: private void writeObject(ObjectOutputStream stream)
370: throws IOException {
371: stream.defaultWriteObject();
372: stream.writeObject(backingMap.comparator());
373: int size = backingMap.size();
374: stream.writeInt(size);
375: if (size > 0) {
376: Iterator<E> it = backingMap.keySet().iterator();
377: while (it.hasNext()) {
378: stream.writeObject(it.next());
379: }
380: }
381: }
382:
383: @SuppressWarnings("unchecked")
384: private void readObject(ObjectInputStream stream)
385: throws IOException, ClassNotFoundException {
386: stream.defaultReadObject();
387: TreeMap<E, E> map = new TreeMap<E, E>(
388: (Comparator<? super E>) stream.readObject());
389: int size = stream.readInt();
390: if (size > 0) {
391: TreeMap.Node<E, E> lastNode = null;
392: for (int i = 0; i < size; i++) {
393: E elem = (E) stream.readObject();
394: lastNode = map.addToLast(lastNode, elem, elem);
395: }
396: }
397: backingMap = map;
398: }
399: }
|