Java > Open Source Codes > org > ozoneDB > collections > BaseTreeMapImpl


1 /*
2  * $Id: BaseTreeMapImpl.java,v 1.12.2.2 2004/01/15 22:02:37 per_nyfelt Exp $
3  * This file is based on TreeMap.java from GNU Classpath. Quote:
4
5 TreeMap.java -- a class providing a basic Red-Black Tree data structure,
6 mapping Object --> Object
7 Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
8
9 This file is part of GNU Classpath.
10
11 GNU Classpath is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2, or (at your option)
14 any later version.
15
16 GNU Classpath is distributed in the hope that it will be useful, but
17 WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with GNU Classpath; see the file COPYING. If not, write to the
23 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
24 02111-1307 USA.
25
26 Linking this library statically or dynamically with other modules is
27 making a combined work based on this library. Thus, the terms and
28 conditions of the GNU General Public License cover the whole
29 combination.
30
31 As a special exception, the copyright holders of this library give you
32 permission to link this library with independent modules to produce an
33 executable, regardless of the license terms of these independent
34 modules, and to copy and distribute the resulting executable under
35 terms of your choice, provided that you also meet, for each linked
36 independent module, the terms and conditions of the license of that
37 module. An independent module is a module which is not derived from
38 or based on this library. If you modify this library, you may extend
39 this exception to your version of the library, but you are not
40 obligated to do so. If you do not wish to do so, delete this
41 exception statement from your version.
42
43  * end quote.
44  *
45  * This file is licenced under the same conditions as its original (GPL +
46  * "special exception").
47  */
48
49 package org.ozoneDB.collections;
50
51 import java.util.Collection ;
52 import java.util.Comparator ;
53 import java.util.Iterator ;
54 import java.util.NoSuchElementException ;
55 import java.util.Map ;
56 import java.util.Set ;
57 import java.util.SortedMap ;
58 import java.util.TreeMap ;
59
60 /**
61  * <p>You are encouraged NOT to use this interface, but rather just use {@link
62  * OzoneTreeMap}, which does not contain the 'internal' methods, or even
63  * {@link java.util.SortedMap}, which does not have any ozone dependency at all</p>
64  * <p>This class functions as a sort of base class for ozone aware treemaps,
65  * were those treemaps themselves can implement if the nodes in the tree are
66  * ozone objects themselves or merely serializables.</p>
67  *
68  * This class provides a red-black tree implementation of the SortedMap
69  * interface. Elements in the Map will be sorted by either a user-provided
70  * Comparator object, or by the natural ordering of the keys.
71  *
72  * The algorithms are adopted from Corman, Leiserson, and Rivest's
73  * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n)
74  * insertion and deletion of elements. That being said, there is a large
75  * enough constant coefficient in front of that "log n" (overhead involved
76  * in keeping the tree balanced), that TreeMap may not be the best choice
77  * for small collections. If something is already sorted, you may want to
78  * just use a LinkedHashMap to maintain the order while providing O(1) access.
79  *
80  * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed
81  * only if a Comparator is used which can deal with them; natural ordering
82  * cannot cope with null. Null values are always allowed. Note that the
83  * ordering must be <i>consistent with equals</i> to correctly implement
84  * the Map interface. If this condition is violated, the map is still
85  * well-behaved, but you may have suprising results when comparing it to
86  * other maps.<p>
87  *
88  * This implementation is not synchronized. If you need to share this between
89  * multiple threads, do something like:<br>
90  * <code>SortedMap m
91  * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
92  *
93  * <p>The iterators are <i>fail-fast</i>, meaning that any structural
94  * modification, except for <code>remove()</code> called on the iterator
95  * itself, cause the iterator to throw a
96  * <code>ConcurrentModificationException</code> rather than exhibit
97  * non-deterministic behavior.</p>
98  *
99  * <p>Note that calling <code>iterator()</code> may result in the creation of
100  * an ozone object and thus in a write-action for the db. This is dependend
101  * of the implementation. Also, the first call to <code>entrySet()</code>,
102  * <code>keySet()</code> and <code>values()</code> also result in the creation
103  * of a new ozone object.</p>
104  *
105  * @author Jon Zeppieri
106  * @author Bryce McKinlay
107  * @author Eric Blake <ebb9@email.byu.edu>
108  * @author <a HREF="mailto:ozoneATmekenkampD0Tcom">Leo Mekenkamp (mind the anti-sp@m)</a> (adaptation for ozone)
109  * @see java.util.TreeMap
110  * @see java.util.Collections#synchronizedSortedMap(SortedMap)
111  */
112 public abstract class BaseTreeMapImpl extends AbstractOzoneMap implements BaseTreeMap, OzoneSortedMap, Cloneable {
113     // Implementation note:
114 // A red-black tree is a binary search tree with the additional properties
115 // that all paths to a leaf node visit the same number of black nodes,
116 // and no red node has red children. To avoid some null-pointer checks,
117 // we use the special node nil which is always black, has no relatives,
118 // and has key and value of null (but is not equal to a mapping of null).
119
120     private static final long serialVersionUID = 1L;
121
122     /**
123      * Sentinal node, used to avoid null checks for corner cases and make the
124      * delete rebalance code simpler. The rebalance code must never assign
125      * the parent, left, or right of nil, but may safely reassign the color
126      * to be black. This object must never be used as a key in a TreeMap, or
127      * it will break bounds checking of a SubMap.
128      */
129     static final BaseTreeMap.Node nilNode = new NilNode();
130
131     private static final class NilNode implements BaseTreeMap.Node {
132
133         private static final long serialVersionUID = 1L;
134
135         public int getColor() {
136             return BaseTreeMap.Node.BLACK;
137         }
138
139         public Object getKey() {
140             return null;
141         }
142
143         public BaseTreeMap.Node getLeft() {
144             return this;
145         }
146
147         public BaseTreeMap.Node getParent() {
148             return this;
149         }
150
151         public BaseTreeMap.Node getRight() {
152             return this;
153         }
154
155         public Object getValue() {
156             return null;
157         }
158
159         public boolean isNil() {
160             return true;
161         }
162
163         public void setColor(int color) {
164             if (color != BaseTreeMap.Node.BLACK) throw new UnsupportedOperationException ();
165         }
166
167         public void setLeft(BaseTreeMap.Node left) {
168             throw new UnsupportedOperationException ();
169         }
170
171         public void setParent(BaseTreeMap.Node parent) {
172             throw new UnsupportedOperationException ();
173         }
174
175         public void setRight(BaseTreeMap.Node right) {
176             throw new UnsupportedOperationException ();
177         }
178
179         public Object setValue(Object value) {
180             throw new UnsupportedOperationException ();
181         }
182
183         public void setKey(Object key) {
184             throw new UnsupportedOperationException ();
185         }
186
187         public boolean equals(Object o) {
188             return (o instanceof BaseTreeMap.Node) && ((BaseTreeMap.Node) o).isNil();
189         }
190     };
191
192     /**
193      * The root node of this TreeMap.
194      */
195     protected BaseTreeMap.Node root = nilNode;
196
197     /**
198      * The size of this TreeMap.
199      */
200     protected int size;
201
202     /**
203      * The cache for {@link #entrySet()}.
204      */
205     private Set entries;
206
207     /**
208      * Counts the number of modifications this TreeMap has undergone, used
209      * by Iterators to know when to throw ConcurrentModificationExceptions.
210      */
211     protected int modCount;
212
213     /**
214      * This TreeMap's comparator, or null for natural ordering.
215      * @serial the comparator ordering this tree, or null
216      */
217     private final Comparator comparator;
218
219     /**
220      * Instantiate a new TreeMap with no elements, using the keys' natural
221      * ordering to sort. All entries in the map must have a key which implements
222      * Comparable, and which are <i>mutually comparable</i>, otherwise map
223      * operations may throw a {@link ClassCastException}. Attempts to use
224      * a null key will throw a {@link NullPointerException}.
225      *
226      * @see Comparable
227      */
228     public BaseTreeMapImpl() {
229         this((Comparator ) null);
230     }
231
232     /**
233      * Instantiate a new TreeMap with no elements, using the provided comparator
234      * to sort. All entries in the map must have keys which are mutually
235      * comparable by the Comparator, otherwise map operations may throw a
236      * {@link ClassCastException}.
237      *
238      * @param c (comparator) the sort order for the keys of this map, or null
239      * for the natural order
240      */
241     public BaseTreeMapImpl(Comparator c) {
242         comparator = c;
243     }
244
245     /**
246      * Instantiate a new TreeMap, initializing it with all of the elements in
247      * the provided Map. The elements will be sorted using the natural
248      * ordering of the keys. This algorithm runs in n*log(n) time. All entries
249      * in the map must have keys which implement Comparable and are mutually
250      * comparable, otherwise map operations may throw a
251      * {@link ClassCastException}.
252      *
253      * @param map a Map, whose entries will be put into this TreeMap
254      * @throws ClassCastException if the keys in the provided Map are not
255      * comparable
256      * @throws NullPointerException if map is null
257      * @see Comparable
258      */
259     public BaseTreeMapImpl(Map map) {
260         this((Comparator ) null);
261         putAll(map);
262     }
263
264     /**
265      * Instantiate a new TreeMap, initializing it with all of the elements in
266      * the provided SortedMap. The elements will be sorted using the same
267      * comparator as in the provided SortedMap. This runs in linear time.
268      *
269      * @param sm a SortedMap, whose entries will be put into this TreeMap
270      * @throws NullPointerException if sm is null
271      */
272     public BaseTreeMapImpl(SortedMap sm) {
273         this(sm.comparator());
274         int pos = sm.size();
275         Iterator itr = sm.entrySet().iterator();
276
277         _org_ozoneDB_fabricateTree(pos);
278         BaseTreeMap.Node node = _org_ozoneDB_firstNode();
279
280         while (--pos >= 0) {
281             Map.Entry me = (Map.Entry ) itr.next();
282             node.setKey(me.getKey());
283             node.setValue(me.getValue());
284             node = _org_ozoneDB_successor(node);
285         }
286     }
287
288     public void onCreate() {
289         super.onCreate();
290     }
291
292     /**
293      * Clears the Map so it has no keys. This is O(1).
294      */
295     public void clear() {
296         if (size > 0) {
297             modCount++;
298             root = nilNode;
299             size = 0;
300         }
301     }
302
303     /**
304      * Returns a shallow clone of this TreeMap. The Map itself is cloned,
305      * but its contents are not.
306      *
307      * @return the clone
308      */
309     public Object clone() {
310         BaseTreeMap copy = emptyClone();
311 // try {
312 //// TODO: replace when FakeFactoryGenerator is ready
313 //// copy = BaseTreeMapImplFactory.getDefault().create(self());
314 // copy = (BaseTreeMap) database().createObject(BaseTreeMap.class, BaseTreeMap.class.getName(), new Object[] {self()});
315 // } catch (Exception e) {
316 // throw new RuntimeException(e);
317 // }
318 copy._org_ozoneDB_resetEntries();
319         copy._org_ozoneDB_fabricateTree(size);
320
321         BaseTreeMap.Node node = _org_ozoneDB_firstNode();
322         BaseTreeMap.Node cnode = copy._org_ozoneDB_firstNode();
323
324         while (!node.isNil()) {
325             cnode.setKey(node.getKey());
326             cnode.setValue(node.getValue());
327             node = _org_ozoneDB_successor(node);
328             cnode = copy._org_ozoneDB_successor(cnode);
329         }
330         return copy;
331     }
332
333     /**
334      * Return the comparator used to sort this map, or null if it is by
335      * natural order.
336      *
337      * @return the map's comparator
338      */
339     public Comparator comparator() {
340         return comparator;
341     }
342
343     /**
344      * Returns true if the map contains a mapping for the given key.
345      *
346      * @param key the key to look for
347      * @return true if the key has a mapping
348      * @throws ClassCastException if key is not comparable to map elements
349      * @throws NullPointerException if key is null and the comparator is not
350      * tolerant of nulls
351      */
352     public boolean containsKey(Object key) {
353         return !_org_ozoneDB_getNode(key).isNil();
354     }
355
356     /**
357      * Returns true if the map contains at least one mapping to the given value.
358      * This requires linear time.
359      *
360      * @param value the value to look for
361      * @return true if the value appears in a mapping
362      */
363     public boolean containsValue(Object value) {
364         BaseTreeMap.Node node = _org_ozoneDB_firstNode();
365         while (!node.isNil()) {
366             if (equals(value, node.getValue())) {
367                 return true;
368             }
369             node = _org_ozoneDB_successor(node);
370         }
371         return false;
372     }
373
374     /**
375      * Returns a "set view" of this TreeMap's entries. The set is backed by
376      * the TreeMap, so changes in one show up in the other. The set supports
377      * element removal, but not element addition.<p>
378      *
379      * Note that the iterators for all three views, from keySet(), entrySet(),
380      * and values(), traverse the TreeMap in sorted sequence.
381      *
382      * @return a set view of the entries
383      * @see #keySet()
384      * @see #values()
385      * @see java.util.Map.Entry
386      */
387     public Set entrySet() {
388         if (entries == null) {
389             return ((BaseTreeMap) self())._org_ozoneDB_entrySet();
390         }
391         return entries;
392     }
393
394     public Set _org_ozoneDB_entrySet() {
395         if (entries == null) {
396 // TODO: when FakeFactoryGenerator is finished replace with
397 // entries = BaseTreeMap_entrySetFactory.getDefault().create(self());
398 entries = (Set ) database().createObject(
399                     _BaseTreeMap_entrySet.class,
400                     new Class [] {BaseTreeMap.class},
401                     new Object [] {self()}
402             );
403         }
404         return entries;
405     }
406
407     /**
408      * Returns the first (lowest) key in the map.
409      *
410      * @return the first key
411      * @throws NoSuchElementException if the map is empty
412      */
413     public Object firstKey() {
414         if (root.isNil()) {
415             throw new NoSuchElementException ();
416         }
417         return _org_ozoneDB_firstNode().getKey();
418     }
419
420     /**
421      * Return the value in this TreeMap associated with the supplied key,
422      * or <code>null</code> if the key maps to nothing. NOTE: Since the value
423      * could also be null, you must use containsKey to see if this key
424      * actually maps to something.
425      *
426      * @param key the key for which to fetch an associated value
427      * @return what the key maps to, if present
428      * @throws ClassCastException if key is not comparable to elements in the map
429      * @throws NullPointerException if key is null but the comparator does not
430      * tolerate nulls
431      * @see #put(Object, Object)
432      * @see #containsKey(Object)
433      */
434     public Object get(Object key) {
435         // Exploit fact that nil.value == null.
436 return _org_ozoneDB_getNode(key).getValue();
437     }
438
439     /**
440      * Returns a view of this Map including all entries with keys less than
441      * <code>toKey</code>. The returned map is backed by the original, so changes
442      * in one appear in the other. The submap will throw an
443      * {@link IllegalArgumentException} for any attempt to access or add an
444      * element beyond the specified cutoff. The returned map does not include
445      * the endpoint; if you want inclusion, pass the successor element.
446      *
447      * @param toKey the (exclusive) cutoff point
448      * @return a view of the map less than the cutoff
449      * @throws ClassCastException if <code>toKey</code> is not compatible with
450      * the comparator (or is not Comparable, for natural ordering)
451      * @throws NullPointerException if toKey is null, but the comparator does not
452      * tolerate null elements
453      */
454     public SortedMap headMap(Object toKey) {
455 // TODO: replace when FakeFactoryGenerator is ready
456 // BaseTreeMapImpl_SubMapFactory.getDefault.create(self(), nil, toKey);
457 return (SortedMap ) database().createObject(
458                 _BaseTreeMap_SubMapImpl.class,
459                 new Class [] {BaseTreeMap.class, Object .class, Object .class},
460                 new Object [] {self(), nilNode, toKey}
461         );
462     }
463
464     /**
465      * Returns a "set view" of this TreeMap's keys. The set is backed by the
466      * TreeMap, so changes in one show up in the other. The set supports
467      * element removal, but not element addition.
468      *
469      * @return a set view of the keys
470      * @see #values()
471      * @see #entrySet()
472      */
473     public Set keySet() {
474         if (keys == null) {
475             // need to do this via a proxy, cause keySet() is not an update
476 // method, but _org_ozoneDB_keySet() is
477 return ((BaseTreeMap) self())._org_ozoneDB_keySet();
478         }
479         return keys;
480     }
481
482     public Set _org_ozoneDB_keySet() {
483         if (keys == null) {
484 // TODO: replace when FakeFactoryGenerator is ready
485 // BaseTreeMapImpl_SubMapFactory.getDefault.create(self(), nil, toKey);
486 keys = (Set ) database().createObject(
487                     _BaseTreeMap_keySet.class,
488                     new Class [] {BaseTreeMap.class},
489                     new Object [] {self()}
490             );
491
492         }
493         return keys;
494     }
495
496     /**
497      * Returns the last (highest) key in the map.
498      *
499      * @return the last key
500      * @throws NoSuchElementException if the map is empty
501      */
502     public Object lastKey() {
503         if (root.isNil()) {
504             throw new NoSuchElementException ("empty");
505         }
506         return lastNode().getKey();
507     }
508
509     /**
510      * Puts the supplied value into the Map, mapped by the supplied key.
511      * The value may be retrieved by any object which <code>equals()</code>
512      * this key. NOTE: Since the prior value could also be null, you must
513      * first use containsKey if you want to see if you are replacing the
514      * key's mapping.
515      *
516      * @param key the key used to locate the value
517      * @param value the value to be stored in the HashMap
518      * @return the prior mapping of the key, or null if there was none
519      * @throws ClassCastException if key is not comparable to current map keys
520      * @throws NullPointerException if key is null, but the comparator does
521      * not tolerate nulls
522      * @see #get(Object)
523      * @see Object#equals(Object)
524      */
525     public Object put(Object key, Object value) {
526         BaseTreeMap.Node current = root;
527         BaseTreeMap.Node parent = nilNode;
528         int comparison = 0;
529
530         // Find new node's parent.
531 while (!current.isNil()) {
532             parent = current;
533             comparison = _org_ozoneDB_compare(key, current.getKey());
534             if (comparison > 0) {
535                 current = current.getRight();
536             } else if (comparison < 0) {
537                 current = current.getLeft();
538             } else {// Key already in tree.
539 return current.setValue(value);
540             }
541         }
542
543         // Set up new node.
544 BaseTreeMap.Node n = newNode(key, value, BaseTreeMap.Node.RED);
545         n.setParent(parent);
546
547         // Insert node in tree.
548 modCount++;
549         size++;
550         if (parent.isNil()) {
551             // Special case inserting into an empty tree.
552 root = n;
553             return null;
554         }
555         if (comparison > 0) {
556             parent.setRight(n);
557         } else {
558             parent.setLeft(n);
559         }
560
561         // Rebalance after insert.
562 insertFixup(n);
563         return null;
564     }
565
566     /**
567      * Copies all elements of the given map into this hashtable. If this table
568      * already has a mapping for a key, the new mapping replaces the current
569      * one.
570      *
571      * @param m the map to be hashed into this
572      * @throws ClassCastException if a key in m is not comparable with keys
573      * in the map
574      * @throws NullPointerException if a key in m is null, and the comparator
575      * does not tolerate nulls
576      */
577     public void putAll(Map m) {
578         Iterator itr = m.entrySet().iterator();
579         int pos = m.size();
580         while (--pos >= 0) {
581             Map.Entry e = (Map.Entry ) itr.next();
582             put(e.getKey(), e.getValue());
583         }
584     }
585
586     /**
587      * Removes from the TreeMap and returns the value which is mapped by the
588      * supplied key. If the key maps to nothing, then the TreeMap remains
589      * unchanged, and <code>null</code> is returned. NOTE: Since the value
590      * could also be null, you must use containsKey to see if you are
591      * actually removing a mapping.
592      *
593      * @param key the key used to locate the value to remove
594      * @return whatever the key mapped to, if present
595      * @throws ClassCastException if key is not comparable to current map keys
596      * @throws NullPointerException if key is null, but the comparator does
597      * not tolerate nulls
598      */
599     public Object remove(Object key) {
600         BaseTreeMap.Node n = _org_ozoneDB_getNode(key);
601         if (n.isNil()) {
602             return null;
603         }
604         // Note: removeNode can alter the contents of n, so save value now.
605 Object result = n.getValue();
606         _org_ozoneDB_removeNode(n);
607         return result;
608     }
609
610     /**
611      * Returns the number of key-value mappings currently in this Map.
612      *
613      * @return the size
614      */
615     public int size() {
616         return size;
617     }
618
619     /**
620      * Returns a view of this Map including all entries with keys greater or
621      * equal to <code>fromKey</code> and less than <code>toKey</code> (a
622      * half-open interval). The returned map is backed by the original, so
623      * changes in one appear in the other. The submap will throw an
624      * {@link IllegalArgumentException} for any attempt to access or add an
625      * element beyond the specified cutoffs. The returned map includes the low
626      * endpoint but not the high; if you want to reverse this behavior on
627      * either end, pass in the successor element.
628      *
629      * @param fromKey the (inclusive) low cutoff point
630      * @param toKey the (exclusive) high cutoff point
631      * @return a view of the map between the cutoffs
632      * @throws ClassCastException if either cutoff is not compatible with
633      * the comparator (or is not Comparable, for natural ordering)
634      * @throws NullPointerException if fromKey or toKey is null, but the
635      * comparator does not tolerate null elements
636      * @throws IllegalArgumentException if fromKey is greater than toKey
637      */
638     public SortedMap subMap(Object fromKey, Object toKey) {
639 // TODO: replace when FakeFactoryGenerator is ready
640 // BaseTreeMapImpl_SubMapFactory.getDefault.create(self(), fromKey, toKey);
641 return (SortedMap ) database().createObject(
642                 _BaseTreeMap_SubMapImpl.class,
643                 new Class [] {BaseTreeMap.class, Object .class, Object .class},
644                 new Object [] {self(), fromKey, toKey}
645         );
646     }
647
648     /**
649      * Returns a view of this Map including all entries with keys greater or
650      * equal to <code>fromKey</code>. The returned map is backed by the
651      * original, so changes in one appear in the other. The submap will throw an
652      * {@link IllegalArgumentException} for any attempt to access or add an
653      * element beyond the specified cutoff. The returned map includes the
654      * endpoint; if you want to exclude it, pass in the successor element.
655      *
656      * @param fromKey the (inclusive) low cutoff point
657      * @return a view of the map above the cutoff
658      * @throws ClassCastException if <code>fromKey</code> is not compatible with
659      * the comparator (or is not Comparable, for natural ordering)
660      * @throws NullPointerException if fromKey is null, but the comparator
661      * does not tolerate null elements
662      */
663     public SortedMap tailMap(Object fromKey) {
664 // TODO: replace when FakeFactoryGenerator is ready
665 // BaseTreeMapImpl_SubMapFactory.getDefault.create(self(), fromKey, nil);
666 return (SortedMap ) database().createObject(
667                 _BaseTreeMap_SubMapImpl.class,
668                 new Class [] {BaseTreeMap.class, Object .class, Object .class},
669                 new Object [] {self(), fromKey, nilNode}
670         );
671     }
672
673     /**
674      * Returns a "collection view" (or "bag view") of this TreeMap's values.
675      * The collection is backed by the TreeMap, so changes in one show up
676      * in the other. The collection supports element removal, but not element
677      * addition.
678      *
679      * @return a bag view of the values
680      * @see #keySet()
681      * @see #entrySet()
682      */
683     public Collection values() {
684         if (values == null) {
685             return ((BaseTreeMap) self())._org_ozoneDB_values();
686         }
687         return values;
688     }
689
690     public Collection _org_ozoneDB_values() {
691         if (values == null) {
692 // TODO: replace when FakeFactoryGenerator is ready
693 // values = BaseTreeMapImpl_valuesFactory.getDefault.create(self());
694 values = (Collection ) database().createObject(
695                     _BaseTreeMap_values.class,
696                     new Class [] {BaseTreeMap.class},
697                     new Object [] {self()}
698             );
699         }
700         return values;
701     }
702
703     /**
704      * <p>DO NOT USE THIS METHOD DIRECTLY!</p><p>Must unfortunately be
705      * public because of the proxy structure ozone uses combined with the fact
706      * that java does not support protected or package methods in interfaces.
707      * This method needs to be callable from iterators, submaps, etc./p>
708      *
709      * @param o1 the first object
710      * @param o2 the second object
711      * @throws ClassCastException if o1 and o2 are not mutually comparable,
712      * or are not Comparable with natural ordering
713      * @throws NullPointerException if o1 or o2 is null with natural ordering
714      */
715     public final int _org_ozoneDB_compare(Object o1, Object o2) {
716         return comparator == null ? ((Comparable ) o1).compareTo(o2) : comparator.compare(o1, o2);
717     }
718
719     /**
720      * Maintain red-black balance after deleting a node.
721      *
722      * @param node the child of the node just deleted, possibly nil
723      * @param parent the parent of the node just deleted, never nil
724      */
725     private void deleteFixup(BaseTreeMap.Node node, BaseTreeMap.Node parent) {
726         // if (parent == nil)
727 // throw new InternalError();
728 // If a black node has been removed, we need to rebalance to avoid
729 // violating the "same number of black nodes on any path" rule. If
730 // node is red, we can simply recolor it black and all is well.
731 while (!node.equals(root) && (node.getColor() == BaseTreeMap.Node.BLACK)) {
732             if (node.equals(parent.getLeft())) {
733                 // Rebalance left side.
734 BaseTreeMap.Node sibling = parent.getRight();
735                 // if (sibling == nil)
736 // throw new InternalError();
737 if (sibling.getColor() == BaseTreeMap.Node.RED) {
738                     // Case 1: Sibling is red.
739 // Recolor sibling and parent, and rotate parent left.
740 sibling.setColor(BaseTreeMap.Node.BLACK);
741                     parent.setColor(BaseTreeMap.Node.RED);
742                     rotateLeft(parent);
743                     sibling = parent.getRight();
744                 }
745
746                 if ((sibling.getLeft().getColor() == BaseTreeMap.Node.BLACK) && (sibling.getRight().getColor() == BaseTreeMap.Node.BLACK)) {
747                     // Case 2: Sibling has no red children.
748 // Recolor sibling, and move to parent.
749 sibling.setColor(BaseTreeMap.Node.RED);
750                     node = parent;
751                     parent = parent.getParent();
752                 } else {
753                     if (sibling.getRight().getColor() == BaseTreeMap.Node.BLACK) {
754                         // Case 3: Sibling has red left child.
755 // Recolor sibling and left child, rotate sibling right.
756 sibling.getLeft().setColor(BaseTreeMap.Node.BLACK);
757                         sibling.setColor(BaseTreeMap.Node.RED);
758                         rotateRight(sibling);
759                         sibling = parent.getRight();
760                     }
761                     // Case 4: Sibling has red right child. Recolor sibling,
762 // right child, and parent, and rotate parent left.
763 sibling.setColor(parent.getColor());
764                     parent.setColor(BaseTreeMap.Node.BLACK);
765                     sibling.getRight().setColor(BaseTreeMap.Node.BLACK);
766                     rotateLeft(parent);
767                     node = root; // Finished.
768 }
769             } else {
770                 // Symmetric "mirror" of left-side case.
771 BaseTreeMap.Node sibling = parent.getLeft();
772                 // if (sibling == nil)
773 // throw new InternalError();
774 if (sibling.getColor() == BaseTreeMap.Node.RED) {
775                     // Case 1: Sibling is red.
776 // Recolor sibling and parent, and rotate parent right.
777 sibling.setColor(BaseTreeMap.Node.BLACK);
778                     parent.setColor(BaseTreeMap.Node.RED);
779                     rotateRight(parent);
780                     sibling = parent.getLeft();
781                 }
782
783                 if ((sibling.getRight().getColor() == BaseTreeMap.Node.BLACK) && (sibling.getLeft().getColor() == BaseTreeMap.Node.BLACK)) {
784                     // Case 2: Sibling has no red children.
785 // Recolor sibling, and move to parent.
786 sibling.setColor(BaseTreeMap.Node.RED);
787                     node = parent;
788                     parent = parent.getParent();
789                 } else {
790                     if (sibling.getLeft().getColor() == BaseTreeMap.Node.BLACK) {
791                         // Case 3: Sibling has red right child.
792 // Recolor sibling and right child, rotate sibling left.
793 sibling.getRight().setColor(BaseTreeMap.Node.BLACK);
794                         sibling.setColor(BaseTreeMap.Node.RED);
795                         rotateLeft(sibling);
796                         sibling = parent.getLeft();
797                     }
798                     // Case 4: Sibling has red left child. Recolor sibling,
799 // left child, and parent, and rotate parent right.
800 sibling.setColor(parent.getColor());
801                     parent.setColor(BaseTreeMap.Node.BLACK);
802                     sibling.getLeft().setColor(BaseTreeMap.Node.BLACK);
803                     rotateRight(parent);
804                     node = root; // Finished.
805 }
806             }
807         }
808         node.setColor(BaseTreeMap.Node.BLACK);
809     }
810
811     /**
812      * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
813      * public because of the proxy structure ozone uses combined with the fact
814      * that java does not support protected or package methods in interfaces.
815      * This method needs to be callable from iterators and submaps./p>
816      *
817      * Construct a perfectly balanced tree consisting of n "blank" nodes. This
818      * permits a tree to be generated from pre-sorted input in linear time.
819      *
820      * @param count the number of blank nodes, non-negative
821      */
822     public void _org_ozoneDB_fabricateTree(final int count) {
823         if (count == 0) {
824             return;
825         }
826
827         // We color every row of nodes black, except for the overflow nodes.
828 // I believe that this is the optimal arrangement. We construct the tree
829 // in place by temporarily linking each node to the next node in the row,
830 // then updating those links to the children when working on the next row.
831
832         // Make the root node.
833 root = newNode(null, null, BaseTreeMap.Node.BLACK);
834         size = count;
835         BaseTreeMap.Node row = root;
836         int rowsize;
837
838         // Fill each row that is completely full of nodes.
839 for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) {
840             BaseTreeMap.Node parent = row;
841             BaseTreeMap.Node last = null;
842             for (int i = 0; i < rowsize; i += 2) {
843                 BaseTreeMap.Node left = newNode(null, null, BaseTreeMap.Node.BLACK);
844                 BaseTreeMap.Node right = newNode(null, null, BaseTreeMap.Node.BLACK);
845                 left.setParent(parent);
846                 left.setRight(right);
847                 right.setParent(parent);
848                 parent.setLeft(left);
849                 BaseTreeMap.Node next = parent.getRight();
850                 parent.setRight(right);
851                 parent = next;
852                 if (last != null) {
853                     last.setRight(left);
854                 }
855                 last = right;
856             }
857             row = row.getLeft();
858         }
859
860         // Now do the partial final row in red.
861 int overflow = count - rowsize;
862         BaseTreeMap.Node parent = row;
863         int i;
864         for (i = 0; i < overflow; i += 2) {
865             BaseTreeMap.Node left = newNode(null, null, BaseTreeMap.Node.RED);
866             BaseTreeMap.Node right = newNode(null, null, BaseTreeMap.Node.RED);
867             left.setParent(parent);
868             right.setParent(parent);
869             parent.setLeft(left);
870             BaseTreeMap.Node next = parent.getRight();
871             parent.setRight(right);
872             parent = next;
873         }
874         // Add a lone left node if necessary.
875 if (i - overflow == 0) {
876             BaseTreeMap.Node left = newNode(null, null, BaseTreeMap.Node.RED);
877             left.setParent(parent);
878             parent.setLeft(left);
879             parent = parent.getRight();
880             left.getParent().setRight(nilNode);
881         }
882         // Unlink the remaining nodes of the previous row.
883 while (!parent.isNil()) {
884             BaseTreeMap.Node next = parent.getRight();
885             parent.setRight(nilNode);
886             parent = next;
887         }
888     }
889
890     /**
891      * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
892      * public because of the proxy structure ozone uses combined with the fact
893      * that java does not support protected or package methods in interfaces.
894      * This method needs to be callable from iterators and submaps./p>
895      *
896      * Returns the first sorted node in the map, or nil if empty. Package
897      * visible for use by nested classes.
898      *
899      * @return the first node
900      */
901     public final BaseTreeMap.Node _org_ozoneDB_firstNode() {
902         // Exploit fact that nil.left == nil.
903 BaseTreeMap.Node node = root;
904         while (!node.getLeft().isNil()) {
905             node = node.getLeft();
906         }
907         return node;
908     }
909
910     /**
911      * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
912      * public because of the proxy structure ozone uses combined with the fact
913      * that java does not support protected or package methods in interfaces.
914      * This method needs to be callable from iterators and submaps./p>
915      *
916      * Return the TreeMap.Node associated with key, or the nil node if no such
917      * node exists in the tree. Package visible for use by nested classes.
918      *
919      * @param key the key to search for
920      * @return the node where the key is found, or nil
921      */
922     public final BaseTreeMap.Node _org_ozoneDB_getNode(Object key) {
923         BaseTreeMap.Node current = root;
924         while (!current.isNil()) {
925             int comparison = _org_ozoneDB_compare(key, current.getKey());
926             if (comparison > 0) {
927                 current = current.getRight();
928             } else if (comparison < 0) {
929                 current = current.getLeft();
930             } else {
931                 return current;
932             }
933         }
934         return current;
935     }
936
937     /**
938      * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
939      * public because of the proxy structure ozone uses combined with the fact
940      * that java does not support protected or package methods in interfaces.
941      * This method needs to be callable from iterators and submaps./p>
942      *
943      * Find the "highest" node which is &lt; key. If key is nil, return last
944      * node. Package visible for use by nested classes.
945      *
946      * @param key the upper bound, exclusive
947      * @return the previous node
948      */
949     public final BaseTreeMap.Node _org_ozoneDB_highestLessThan(Object key) {
950         if ((key instanceof BaseTreeMap.Node) && ((BaseTreeMap.Node) key).isNil()) {
951             return lastNode();
952         }
953
954         BaseTreeMap.Node last = nilNode;
955         BaseTreeMap.Node current = root;
956         int comparison = 0;
957
958         while (!current.isNil()) {
959             last = current;
960             comparison = _org_ozoneDB_compare(key, current.getKey());
961             if (comparison > 0) {
962                 current = current.getRight();
963             } else if (comparison < 0) {
964                 current = current.getLeft();
965             } else {// Exact match.
966 return predecessor(last);
967             }
968         }
969         return comparison <= 0 ? predecessor(last) : last;
970     }
971
972     /**
973      * Maintain red-black balance after inserting a new node.
974      *
975      * @param n the newly inserted node
976      */
977     private void insertFixup(BaseTreeMap.Node n) {
978         // Only need to rebalance when parent is a BaseTreeMap.Node.RED node, and while at least
979 // 2 levels deep into the tree (ie: node has a grandparent). Remember
980 // that nil.color == BaseTreeMap.Node.BLACK.
981 while (n.getParent().getColor() == BaseTreeMap.Node.RED && !n.getParent().getParent().isNil()) {
982             if (n.getParent().equals(n.getParent().getParent().getLeft())) {
983                 BaseTreeMap.Node uncle = n.getParent().getParent().getRight();
984                 // Uncle may be nil, in which case it is BaseTreeMap.Node.BLACK.
985 if (uncle.getColor() == BaseTreeMap.Node.RED) {
986                     // Case 1. Uncle is BaseTreeMap.Node.RED: Change colors of parent, uncle,
987 // and grandparent, and move n to grandparent.
988 n.getParent().setColor(BaseTreeMap.Node.BLACK);
989                     uncle.setColor(BaseTreeMap.Node.BLACK);
990                     uncle.getParent().setColor(BaseTreeMap.Node.RED);
991                     n = uncle.getParent();
992                 } else {
993                     if (n.equals(n.getParent().getRight())) {
994                         // Case 2. Uncle is BaseTreeMap.Node.BLACK and x is right child.
995 // Move n to parent, and rotate n left.
996 n = n.getParent();
997                         rotateLeft(n);
998                     }
999                     // Case 3. Uncle is BaseTreeMap.Node.BLACK and x is left child.
1000 // Recolor parent, grandparent, and rotate grandparent right.
1001 n.getParent().setColor(BaseTreeMap.Node.BLACK);
1002                    n.getParent().getParent().setColor(BaseTreeMap.Node.RED);
1003                    rotateRight(n.getParent().getParent());
1004                }
1005            } else {
1006                // Mirror image of above code.
1007 BaseTreeMap.Node uncle = n.getParent().getParent().getLeft();
1008                // Uncle may be nil, in which case it is BaseTreeMap.Node.BLACK.
1009 if (uncle.getColor() == BaseTreeMap.Node.RED) {
1010                    // Case 1. Uncle is BaseTreeMap.Node.RED: Change colors of parent, uncle,
1011 // and grandparent, and move n to grandparent.
1012 n.getParent().setColor(BaseTreeMap.Node.BLACK);
1013                    uncle.setColor(BaseTreeMap.Node.BLACK);
1014                    uncle.getParent().setColor(BaseTreeMap.Node.RED);
1015                    n = uncle.getParent();
1016                } else {
1017                    if (n.equals(n.getParent().getLeft())) {
1018                        // Case 2. Uncle is BaseTreeMap.Node.BLACK and x is left child.
1019 // Move n to parent, and rotate n right.
1020 n = n.getParent();
1021                        rotateRight(n);
1022                    }
1023                    // Case 3. Uncle is BaseTreeMap.Node.BLACK and x is right child.
1024 // Recolor parent, grandparent, and rotate grandparent left.
1025 n.getParent().setColor(BaseTreeMap.Node.BLACK);
1026                    n.getParent().getParent().setColor(BaseTreeMap.Node.RED);
1027                    rotateLeft(n.getParent().getParent());
1028                }
1029            }
1030        }
1031        root.setColor(BaseTreeMap.Node.BLACK);
1032    }
1033
1034    /**
1035     * Returns the last sorted node in the map, or nil if empty.
1036     *
1037     * @return the last node
1038     */
1039    private BaseTreeMap.Node lastNode() {
1040        // Exploit fact that nil.right == nil.
1041 BaseTreeMap.Node node = root;
1042        while (!node.getRight().isNil()) {
1043            node = node.getRight();
1044        }
1045        return node;
1046    }
1047
1048    /**
1049     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
1050     * public because of the proxy structure ozone uses combined with the fact
1051     * that java does not support protected or package methods in interfaces.
1052     * This method needs to be callable from iterators and submaps./p>
1053     *
1054     * Find the "lowest" node which is &gt;= key. If key is nil, return either
1055     * nil or the first node, depending on the parameter first.
1056     * Package visible for use by nested classes.
1057     *
1058     * @param key the lower bound, inclusive
1059     * @param first true to return the first element instead of nil for nil key
1060     * @return the next node
1061     */
1062    public final BaseTreeMap.Node _org_ozoneDB_lowestGreaterThan(Object key, boolean first) {
1063        if ((key instanceof BaseTreeMap.Node) && ((BaseTreeMap.Node) key).isNil()) {
1064            return first ? _org_ozoneDB_firstNode() : nilNode;
1065        }
1066
1067        BaseTreeMap.Node last = nilNode;
1068        BaseTreeMap.Node current = root;
1069        int comparison = 0;
1070
1071        while (!current.isNil()) {
1072            last = current;
1073            comparison = _org_ozoneDB_compare(key, current.getKey());
1074            if (comparison > 0) {
1075                current = current.getRight();
1076            } else if (comparison < 0) {
1077                current = current.getLeft();
1078            } else {
1079                return current;
1080            }
1081        }
1082        return comparison > 0 ? _org_ozoneDB_successor(last) : last;
1083    }
1084
1085    /**
1086     * Return the node preceding the given one, or nil if there isn't one.
1087     *
1088     * @param node the current node, not nil
1089     * @return the prior node in sorted order
1090     */
1091    private BaseTreeMap.Node predecessor(BaseTreeMap.Node node) {
1092        if (!node.getLeft().isNil()) {
1093            node = node.getLeft();
1094            while (!node.getRight().isNil()) {
1095                node = node.getRight();
1096            }
1097            return node;
1098        }
1099
1100        BaseTreeMap.Node parent = node.getParent();
1101        // Exploit fact that nil.left == nil and node is non-nil.
1102 while (node.equals(parent.getLeft())) {
1103            node = parent;
1104            parent = node.getParent();
1105        }
1106        return parent;
1107    }
1108
1109    /**
1110     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
1111     * public because of the proxy structure ozone uses combined with the fact
1112     * that java does not support protected or package methods in interfaces.
1113     * This method needs to be callable from iterators and submaps./p>
1114     *
1115     * Construct a tree from sorted keys in linear time, with values of "".
1116     * Package visible for use by TreeSet.
1117     *
1118     * @param keys the iterator over the sorted keys
1119     * @param count the number of nodes to insert
1120     * @see java.util.TreeSet#TreeSet(java.util.SortedSet)
1121     */
1122    public final void _org_ozoneDB_putKeysLinear(Iterator keys, int count) {
1123        _org_ozoneDB_fabricateTree(count);
1124        BaseTreeMap.Node node = _org_ozoneDB_firstNode();
1125
1126        while (--count >= 0) {
1127            node.setKey(keys.next());
1128            node.setValue("");
1129            node = _org_ozoneDB_successor(node);
1130        }
1131    }
1132
1133    /**
1134     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
1135     * public because of the proxy structure ozone uses combined with the fact
1136     * that java does not support protected or package methods in interfaces.
1137     * This method needs to be callable from iterators and submaps./p>
1138     *
1139     * Remove node from tree. This will increment modCount and decrement size.
1140     * Node must exist in the tree. Package visible for use by nested classes.
1141     *
1142     * @param node the node to remove
1143     */
1144    public final void _org_ozoneDB_removeNode(BaseTreeMap.Node node) {
1145        BaseTreeMap.Node splice;
1146        BaseTreeMap.Node child;
1147
1148        modCount++;
1149        size--;
1150
1151        // Find splice, the node at the position to actually remove from the tree.
1152 if (node.getLeft().isNil()) {
1153            // Node to be deleted has 0 or 1 children.
1154 splice = node;
1155            child = node.getRight();
1156        } else if (node.getRight().isNil()) {
1157            // Node to be deleted has 1 child.
1158 splice = node;
1159            child = node.getLeft();
1160        } else {
1161            // Node has 2 children. Splice is node's predecessor, and we swap
1162 // its contents into node.
1163 splice = node.getLeft();
1164            while (!splice.getRight().isNil()) {
1165                splice = splice.getRight();
1166            }
1167            child = splice.getLeft();
1168            node.setKey(splice.getKey());
1169            node.setValue(splice.getValue());
1170        }
1171
1172        // Unlink splice from the tree.
1173 BaseTreeMap.Node parent = splice.getParent();
1174        if (!child.isNil()) {
1175            child.setParent(parent);
1176        }
1177        if (parent.isNil()) {
1178            // Special case for 0 or 1 node remaining.
1179 root = child;
1180            return;
1181        }
1182        if (splice.equals(parent.getLeft())) {
1183            parent.setLeft(child);
1184        } else {
1185            parent.setRight(child);
1186        }
1187
1188        if (splice.getColor() == BaseTreeMap.Node.BLACK) {
1189            deleteFixup(child, parent);
1190        }
1191    }
1192
1193    /**
1194     * Rotate node n to the left.
1195     *
1196     * @param node the node to rotate
1197     */
1198    private void rotateLeft(BaseTreeMap.Node node) {
1199        BaseTreeMap.Node child = node.getRight();
1200        // if (node == nil || child == nil)
1201 // throw new InternalError();
1202
1203        // Establish node.right link.
1204 node.setRight(child.getLeft());
1205        if (!child.getLeft().isNil()) {
1206            child.getLeft().setParent(node);
1207        }
1208
1209        // Establish child->parent link.
1210 child.setParent(node.getParent());
1211        if (!node.getParent().isNil()) {
1212            if (node.equals(node.getParent().getLeft())) {
1213                node.getParent().setLeft(child);
1214            } else {
1215                node.getParent().setRight(child);
1216            }
1217        } else {
1218            root = child;
1219        }
1220
1221        // Link n and child.
1222 child.setLeft(node);
1223        node.setParent(child);
1224    }
1225
1226    /**
1227     * Rotate node n to the right.
1228     *
1229     * @param node the node to rotate
1230     */
1231    private void rotateRight(BaseTreeMap.Node node) {
1232        BaseTreeMap.Node child = node.getLeft();
1233        // if (node == nil || child == nil)
1234 // throw new InternalError();
1235
1236        // Establish node.left link.
1237 node.setLeft(child.getRight());
1238        if (!child.getRight().isNil()) {
1239            child.getRight().setParent(node);
1240        }
1241
1242        // Establish child->parent link.
1243 child.setParent(node.getParent());
1244        if (!node.getParent().isNil()) {
1245            if (node.equals(node.getParent().getRight())) {
1246                node.getParent().setRight(child);
1247            } else {
1248                node.getParent().setLeft(child);
1249            }
1250        } else {
1251            root = child;
1252        }
1253
1254        // Link n and child.
1255 child.setRight(node);
1256        node.setParent(child);
1257    }
1258
1259    /**
1260     * <p>DO NOT USE THIS METHOD; for internal use only. Must unfortunately be
1261     * public because of the proxy structure ozone uses combined with the fact
1262     * that java does not support protected or package methods in interfaces.
1263     * This method needs to be callable from iterators and submaps./p>
1264     *
1265     * Return the node following the given one, or nil if there isn't one.
1266     * Package visible for use by nested classes.
1267     *
1268     * @param node the current node, not nil
1269     * @return the next node in sorted order
1270     */
1271    public final BaseTreeMap.Node _org_ozoneDB_successor(BaseTreeMap.Node node) {
1272        if (!node.getRight().isNil()) {
1273            node = node.getRight();
1274            while (!node.getLeft().isNil()) {
1275                node = node.getLeft();
1276            }
1277            return node;
1278        }
1279
1280        BaseTreeMap.Node parent = node.getParent();
1281        
1282        // Exploit fact that nil.right == nil and node is non-nil.
1283 // First test for identical nodes, because this method is also called
1284 // indirectly from readObject, so if one of these nodes contain an
1285 // OzoneProxy for an OzoneObject with overridden equals(), that proxy
1286 // will cause the object to be loaded when equals() is called. But if
1287 // that object is in the same cluster as this TreeMap, than the cluster
1288 // will get loaded while it is loading, causing endless recursion...
1289 while (node == parent.getRight() || node.equals(parent.getRight())) {
1290            node = parent;
1291            parent = parent.getParent();
1292        }
1293        return parent;
1294    }
1295
1296    /** <p>Returns a <code>SortedMap</code> that contains the same entries as this
1297     * persistent one; it is (by nature of the client-server enviromnent) always
1298     * a 'deep' copy of this <code>OzoneSortedMap</code>. I.e. the contents of
1299     * this <code>OzoneSortedMap</code> instance are always copied to the client
1300     * by use of serialization.</p>
1301     *
1302     */
1303    public SortedMap getClientSortedMap() {
1304        return getClientTreeMap();
1305    }
1306
1307    /** <p>Returns a <code>Map</code> that contains the same entries as this
1308     * persistent one; it is (by nature of the client-server enviromnent) always
1309     * a 'deep' copy of this <code>OzoneMap</code>. I.e. the contents of
1310     * this <code>OzoneMap</code> instance are always copied to the client
1311     * by use of serialization.</p>
1312     *
1313     */
1314    public Map getClientMap() {
1315        return getClientTreeMap();
1316    }
1317
1318    /** <p>Returns a <code>TreeMap</code> that contains the same entries as this
1319     * persistent one; it is (by nature of the client-server enviromnent) always
1320     * a 'deep' copy of this <code>OzoneTreeMap</code>. I.e. the contents of
1321     * this <code>OzoneTreeMap</code> instance are always copied to the client
1322     * by use of serialization.</p>
1323     *
1324     */
1325    public TreeMap getClientTreeMap() {
1326        // do not make use of TreeMap(SortedSet) because that one calls our
1327 // iterator() and we don't want that, because we want to use an internal
1328 // iterator for speed and possible read-only db
1329 TreeMap result = new TreeMap (comparator());
1330        for (Iterator i = ((OzoneSet) entrySet())._org_ozoneDB_internalIterator(); i.hasNext(); ) {
1331            Map.Entry entry = (Map.Entry ) i.next();
1332            result.put(entry.getKey(), entry.getValue());
1333        }
1334        return result;
1335    }
1336
1337    public void _org_ozoneDB_resetEntries() {
1338        this.entries = null;
1339    }
1340
1341    /** <p>DO NOT CALL THIS METHOD DIRECTLY.</p>
1342     * <p>This method is called by an <code>Iterator</code> to find out if this
1343     * collection has changed during the lifespan of that <code>Iterator</code></p>
1344     *
1345     */
1346    public int _org_ozoneDB_getModification() {
1347        return modCount;
1348    }
1349
1350    /** <p>Basically nothing more than a typecasted <code>HeadMap</code> method.
1351     * Because subsets are also <code>OzoneSortedMap</code>s, this method is
1352     * provided to do away with the need for a typecast.</p>
1353     *
1354     */
1355    public OzoneSortedMap ozoneHeadMap(Object toKey) {
1356        return (OzoneSortedMap) headMap(toKey);
1357    }
1358
1359    /** <p>Basically nothing more than a typecasted <code>SubMap</code> method.
1360     * Because subsets are also <code>OzoneSortedMap</code>s, this method is
1361     * provided to do away with the need for a typecast.</p>
1362     *
1363     */
1364    public OzoneSortedMap ozoneSubMap(Object fromKey, Object toKey) {
1365        return (OzoneSortedMap) subMap(fromKey, toKey);
1366    }
1367
1368    /** <p>Basically nothing more than a typecasted <code>TailMap</code> method.</p>
1369     * Because subsets are also <code>OzoneSortedMap</code>s, this method is
1370     * provided to do away with the need for a typecast.</p>
1371     *
1372     */
1373    public OzoneSortedMap ozoneTailMap(Object toKey) {
1374        return (OzoneSortedMap) tailMap(toKey);
1375    }
1376
1377    protected abstract BaseTreeMap.Node newNode(Object key, Object value, int color);
1378
1379    protected abstract BaseTreeMap emptyClone();
1380
1381}

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags