BaseTreeSetImpl


1   /*
2    * $Id: BaseTreeSetImpl.java,v 1.10.2.1 2004/01/11 20:42:22 per_nyfelt Exp $
3    * This file is based on TreeSet.java from GNU Classpath. Quote:
4   
5   TreeSet.java -- a class providing a TreeMap-backed SortedSet
6   Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
7   
8   This file is part of GNU Classpath.
9   
10  GNU Classpath is free software; you can redistribute it and/or modify
11  it under the terms of the GNU General Public License as published by
12  the Free Software Foundation; either version 2, or (at your option)
13  any later version.
14  
15  GNU Classpath is distributed in the hope that it will be useful, but
16  WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  General Public License for more details.
19  
20  You should have received a copy of the GNU General Public License
21  along with GNU Classpath; see the file COPYING.  If not, write to the
22  Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
23  02111-1307 USA.
24  
25  Linking this library statically or dynamically with other modules is
26  making a combined work based on this library.  Thus, the terms and
27  conditions of the GNU General Public License cover the whole
28  combination.
29  
30  As a special exception, the copyright holders of this library give you
31  permission to link this library with independent modules to produce an
32  executable, regardless of the license terms of these independent
33  modules, and to copy and distribute the resulting executable under
34  terms of your choice, provided that you also meet, for each linked
35  independent module, the terms and conditions of the license of that
36  module.  An independent module is a module which is not derived from
37  or based on this library.  If you modify this library, you may extend
38  this exception to your version of the library, but you are not
39  obligated to do so.  If you do not wish to do so, delete this
40  exception statement from your version.
41  
42   * end quote.
43   *
44   * This file is licenced under the same conditions as its original (GPL +
45   * "special exception").
46   */
47  
48  package org.ozoneDB.collections;
49  
50  import java.io.Serializable  ;
51  import java.util.Collection  ;
52  import java.util.Comparator  ;
53  import java.util.Iterator  ;
54  import java.util.Set  ;
55  import java.util.SortedMap  ;
56  import java.util.SortedSet  ;
57  import java.util.TreeMap  ;
58  import java.util.TreeSet  ;
59  
60  /**
61   * This class provides a TreeMap-backed implementation of the SortedSet
62   * interface. The elements will be sorted according to their <i>natural
63   * order</i>, or according to the provided <code>Comparator</code>.<p>
64   *
65   * Most operations are O(log n), but there is so much overhead that this
66   * makes small sets expensive. Note that the ordering must be <i>consistent
67   * with equals</i> to correctly implement the Set interface. If this
68   * condition is violated, the set is still well-behaved, but you may have
69   * suprising results when comparing it to other sets.<p>
70   *
71   * This implementation is not synchronized. If you need to share this between
72   * multiple threads, do something like:<br>
73   * <code>SortedSet s
74   *       = Collections.synchronizedSortedSet(new TreeSet(...));</code><p>
75   *
76   * The iterators are <i>fail-fast</i>, meaning that any structural
77   * modification, except for <code>remove()</code> called on the iterator
78   * itself, cause the iterator to throw a
79   * <code>ConcurrentModificationException</code> rather than exhibit
80   * non-deterministic behavior.
81   *
82   * @author Jon Zeppieri
83   * @author Bryce McKinlay
84   * @author Eric Blake <ebb9@email.byu.edu>
85   * @author <a HREF="mailto:ozoneATmekenkampD0Tcom">Leo Mekenkamp (mind the anti-sp@m)</a> (adaptation for ozone)
86   * @see Collection
87   * @see Set
88   * @see java.util.HashSet
89   * @see java.util.LinkedHashSet
90   * @see Comparable
91   * @see Comparator
92   * @see java.util.Collections#synchronizedSortedSet(SortedSet)
93   * @see TreeMap
94   * @since 1.2
95   * status updated to 1.4
96   */
97  // public class TreeSet extends AbstractSet implements SortedSet, Cloneable, Serializable
98  public abstract class BaseTreeSetImpl extends AbstractOzoneSet implements BaseTreeSet, Cloneable  , Serializable   {
99  
100     private static final long serialVersionUID = 1L;
101 
102     /**
103      * The SortedMap which backs this Set.
104      */
105     // Not final because of readObject. This will always be one of TreeMap or
106     // TreeMap.SubMap, which both extend AbstractMap.
107     protected SortedMap   map;
108     private transient Object   ctorParam;
109 
110     /**
111      * Construct a new TreeSet whose backing TreeMap using the "natural"
112      * ordering of keys. Elements that are not mutually comparable will cause
113      * ClassCastExceptions down the road.
114      *
115      * @see Comparable
116      */
117     public BaseTreeSetImpl() {
118         ctorParam = null;
119     }
120 
121     /** Basically a hack to prevent creationg of yet another map which backs
122      * this BaseTreeSet but will be overwritten almost immediately by ctor
123      * FullTreeSetImpl(SortedMap backingMap, DoNotUse_SeeJavadoc x)
124      */
125     protected BaseTreeSetImpl(int ctorWithoutCreatingNewBackingMap) {
126         // does not match _any_ of the classes in onCreate()
127         ctorParam = System.out;
128     }
129 
130     /**
131      * Construct a new TreeSet whose backing TreeMap uses the supplied
132      * Comparator. Elements that are not mutually comparable will cause
133      * ClassCastExceptions down the road.
134      *
135      * @param comparator the Comparator this Set will use
136      */
137     public BaseTreeSetImpl(Comparator   comparator) {
138         ctorParam = comparator;
139     }
140 
141     /**
142      * Construct a new TreeSet whose backing TreeMap uses the "natural"
143      * orering of the keys and which contains all of the elements in the
144      * supplied Collection. This runs in n*log(n) time.
145      *
146      * @param collection the new Set will be initialized with all
147      *        of the elements in this Collection
148      * @throws ClassCastException if the elements of the collection are not
149      *         comparable
150      * @throws NullPointerException if the collection is null
151      * @see Comparable
152      */
153     public BaseTreeSetImpl(Collection   collection) {
154         ctorParam = collection;
155     }
156 
157     /**
158      * Construct a new TreeSet, using the same key ordering as the supplied
159      * SortedSet and containing all of the elements in the supplied SortedSet.
160      * This constructor runs in linear time.
161      *
162      * @param sortedSet the new TreeSet will use this SortedSet's comparator
163      *        and will initialize itself with all its elements
164      * @throws NullPointerException if sortedSet is null
165      */
166     public BaseTreeSetImpl(SortedSet   sortedSet) {
167         ctorParam = sortedSet;
168     }
169 
170     public void onCreate() {
171         if (ctorParam == null) {
172             map = newBackingMap();
173         } else if (ctorParam instanceof Comparator  ) {
174             map = newBackingMap((Comparator  ) ctorParam);
175         } else if (ctorParam instanceof OzoneSortedSet) {
176             OzoneSortedSet sortedSet = (OzoneSortedSet) ctorParam;
177             map = newBackingMap(sortedSet.comparator());
178             Iterator   i = sortedSet._org_ozoneDB_internalIterator();
179             ((BaseTreeMap) map)._org_ozoneDB_putKeysLinear(i, sortedSet.size());
180         } else if (ctorParam instanceof SortedSet  ) {
181             SortedSet   sortedSet = (SortedSet  ) ctorParam;
182             map = newBackingMap(sortedSet.comparator());
183             Iterator   i = sortedSet.iterator();
184             ((BaseTreeMap) map)._org_ozoneDB_putKeysLinear(i, sortedSet.size());
185         } else if (ctorParam instanceof Collection  ) {
186             map = newBackingMap();
187             addAll((Collection  ) ctorParam);
188         }
189         
190         // make sure the key set exists as an ozone object, so that it does
191         // not have to be created anymore
192         map.keySet();
193     }
194 
195     /**
196      * Adds the spplied Object to the Set if it is not already in the Set;
197      * returns true if the element is added, false otherwise.
198      *
199      * @param obj the Object to be added to this Set
200      * @throws ClassCastException if the element cannot be compared with objects
201      *         already in the set
202      */
203     public boolean add(Object   obj) {
204         return map.put(obj, "") == null;
205     }
206 
207     /**
208      * Adds all of the elements in the supplied Collection to this TreeSet.
209      *
210      * @param c The collection to add
211      * @return true if the Set is altered, false otherwise
212      * @throws NullPointerException if c is null
213      * @throws ClassCastException if an element in c cannot be compared with
214      *         objects already in the set
215      */
216     public boolean addAll(Collection   c) {
217         boolean result = false;
218         int pos = c.size();
219         Iterator   itr;
220         if (c instanceof OzoneCollection) {
221             itr = ((OzoneCollection) c)._org_ozoneDB_internalIterator();
222         } else {
223             itr = c.iterator();
224         }
225         while (--pos >= 0) {
226             result |= (map.put(itr.next(), "") == null);
227         }
228         return result;
229     }
230 
231     /**
232      * Removes all elements in this Set.
233      */
234     public void clear() {
235         map.clear();
236     }
237 
238     /**
239      * Returns this Set's comparator.
240      *
241      * @return the comparator, or null if the set uses natural ordering
242      */
243     public Comparator   comparator() {
244         return map.comparator();
245     }
246 
247     /**
248      * Returns true if this Set contains the supplied Object, false otherwise.
249      *
250      * @param obj the Object to check for
251      * @return true if it is in the set
252      * @throws ClassCastException if obj cannot be compared with objects
253      *         already in the set
254      */
255     public boolean contains(Object   obj) {
256         return map.containsKey(obj);
257     }
258 
259     /**
260      * Returns the first (by order) element in this Set.
261      *
262      * @return the first element
263      * @throws java.util.NoSuchElementException if the set is empty
264      */
265     public Object   first() {
266         return map.firstKey();
267     }
268 
269     /**
270      * Returns true if this Set has size 0, false otherwise.
271      *
272      * @return true if the set is empty
273      */
274     public boolean isEmpty() {
275         return map.isEmpty();
276     }
277 
278     /**
279      * Returns in Iterator over the elements in this TreeSet, which traverses
280      * in ascending order.
281      *
282      * @return an iterator
283      */
284     public Iterator   iterator() {
285         return map.keySet().iterator();
286     }
287 
288     public Iterator   _org_ozoneDB_internalIterator() {
289         return ((OzoneSet) map.keySet())._org_ozoneDB_internalIterator();
290     }
291         
292     /**
293      * Returns the last (by order) element in this Set.
294      *
295      * @return the last element
296      * @throws java.util.NoSuchElementException if the set is empty
297      */
298     public Object   last() {
299         return map.lastKey();
300     }
301 
302     /**
303      * If the supplied Object is in this Set, it is removed, and true is
304      * returned; otherwise, false is returned.
305      *
306      * @param obj the Object to remove from this Set
307      * @return true if the set was modified
308      * @throws ClassCastException if obj cannot be compared to set elements
309      */
310     public boolean remove(Object   obj) {
311         return map.remove(obj) != null;
312     }
313 
314     /**
315      * Returns the number of elements in this Set
316      *
317      * @return the set size
318      */
319     public int size() {
320         return map.size();
321     }
322 
323     /** <p>Returns a <code>Collection</code> that contains the same entries as this
324      * persistent one; it is (by nature of the client-server enviromnent) always
325      * a 'deep' copy of this <code>OzoneCollection</code>. I.e. the contents of
326      * this <code>OzoneCollection</code> instance are always copied to the client
327      * by use of serialization.<br/>
328      * Note that the difference of calling <code>iterator()</code>
329      * compared to <code>getClientCollection().iterator()</code> is that in
330      * the first case you go through the real collection on the server and in
331      * the second case you go through a local copy on the client side.</p>
332      * <p>Note that all subclasses of <code>OzoneCollection</code> (or
333      * <code>OzoneMap</code>) have <code>getClientXxx()</code> member functions
334      * that returns a collection of type <code>Xxx</code>; these simply return
335      * a typecasted result value from <code>getClientCollection()</code> or
336      * <code>getClientMap</code>.</p>
337      *
338      */
339     public Collection   getClientCollection() {
340         return getClientTreeSet();
341     }
342 
343     /** <p>Returns a <code>Set</code> that contains the same entries as this
344      * persistent one; it is (by nature of the client-server enviromnent) always
345      * a 'deep' copy of this <code>OzoneSet</code>. I.e. the contents of
346      * this <code>OzoneSet</code> instance are always copied to the client
347      * by use of serialization.</p>
348      * <p>Note that the difference of calling <code>iterator()</code>
349      * compared to <code>getClientSet().iterator()</code> is that in
350      * the first case you go through the real collection on the server and in
351      * the second case you go through a local copy on the client side.</p>
352      *
353      */
354     public Set   getClientSet() {
355         return getClientTreeSet();
356     }
357 
358     /** <p>Returns a <code>SortedSet</code> that contains the same entries as this
359      * persistent one; it is (by nature of the client-server enviromnent) always
360      * a 'deep' copy of this <code>OzoneSortedSet</code>. I.e. the contents of
361      * this <code>OzoneSortedSet</code> instance are always copied to the client
362      * by use of serialization.</p>
363      * <p>Note that the difference of calling <code>iterator()</code>
364      * compared to <code>getClientSortedSet().iterator()</code> is that in
365      * the first case you go through the real collection on the server and in
366      * the second case you go through a local copy on the client side.</p>
367      *
368      */
369     public SortedSet   getClientSortedSet() {
370         return getClientTreeSet();
371     }
372 
373     /** <p>Basically nothing more than a typecasted <code>HeadSet</code> method.
374      * Because subsets are also <code>OzoneSortedSet</code>s, this method is
375      * provided to do away with the need for a typecast.</p>
376      *
377      */
378     public OzoneSortedSet ozoneHeadSet(Object   toElement) {
379         return (OzoneSortedSet) headSet(toElement);
380     }
381 
382     /** <p>Basically nothing more than a typecasted <code>SubSet</code> method.
383      * Because subsets are also <code>OzoneSortedSet</code>s, this method is
384      * provided to do away with the need for a typecast.</p>
385      *
386      */
387     public OzoneSortedSet ozoneSubSet(Object   fromElement, Object   toElement) {
388         return (OzoneSortedSet) subSet(fromElement, toElement);
389     }
390 
391     /** <p>Basically nothing more than a typecasted <code>TailSet</code> method.</p>
392      * Because subsets are also <code>OzoneSortedSet</code>s, this method is
393      * provided to do away with the need for a typecast.</p>
394      *
395      */
396     public OzoneSortedSet ozoneTailSet(Object   toElement) {
397         return (OzoneSortedSet) tailSet(toElement);
398     }
399 
400     /** <p>Returns a <code>TreeSet</code> that contains the same entries as this
401      * persistent one; it is (by nature of the client-server enviromnent) always
402      * a 'deep' copy of this <code>OzoneTreeSet</code>. I.e. the contents of
403      * this <code>OzoneTreeSet</code> instance are always copied to the client
404      * by use of serialization.</p>
405      * <p>Note that the difference of calling <code>iterator()</code>
406      * compared to <code>getClientTreeSet().iterator()</code> is that in
407      * the first case you go through the real collection on the server and in
408      * the second case you go through a local copy on the client side.</p>
409      *
410      */
411     public TreeSet   getClientTreeSet() {
412         // do not make use of TreeSet(SortedSet) because that one calls our
413         // iterator() and we don't want that, because we want to use an internal
414         // iterator for speed and possible read-only db
415         TreeSet   result = new TreeSet  (comparator());
416         for (Iterator   i = _org_ozoneDB_internalIterator(); i.hasNext(); ) {
417             result.add(i.next());
418         }
419         return result;
420     }
421 
422     /** Returns a string representation of the object. In general, the
423      * <code>toString</code> method returns a string that
424      * "textually represents" this object. The result should
425      * be a concise but informative representation that is easy for a
426      * person to read.
427      * It is recommended that all subclasses override this method.
428      * <p>
429      * The <code>toString</code> method for class <code>Object</code>
430      * returns a string consisting of the name of the class of which the
431      * object is an instance, the at-sign character `<code>@</code>', and
432      * the unsigned hexadecimal representation of the hash code of the
433      * object. In other words, this method returns a string equal to the
434      * value of:
435      * <blockquote>
436      * <pre>
437      * getClass().getName() + '@' + Integer.toHexString(hashCode())
438      * </pre></blockquote>
439      *
440      * @return  a string representation of the object.
441      *
442      */
443     public String   toString() {
444         return (map == null) ? "[]" : super.toString();
445     }
446 
447     protected abstract SortedMap   newBackingMap();
448 
449     protected abstract SortedMap   newBackingMap(Comparator   comparator);
450 
451 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags