KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*
2  * $Id: FullTreeMapImpl.java,v 1.6 2003/11/27 15:55:11 leomekenkamp 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
52 import java.io.ObjectOutputStream JavaDoc;
53 import java.io.ObjectInputStream JavaDoc;
54 import java.io.IOException JavaDoc;
55 import java.util.Comparator JavaDoc;
56 import java.util.Map JavaDoc;
57 import java.util.SortedMap JavaDoc;
58 /**
59  * This class provides a red-black tree implementation of the SortedMap
60  * interface. Elements in the Map will be sorted by either a user-provided
61  * Comparator object, or by the natural ordering of the keys.
62  *
63  * The algorithms are adopted from Corman, Leiserson, and Rivest's
64  * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n)
65  * insertion and deletion of elements. That being said, there is a large
66  * enough constant coefficient in front of that "log n" (overhead involved
67  * in keeping the tree balanced), that TreeMap may not be the best choice
68  * for small collections. If something is already sorted, you may want to
69  * just use a LinkedHashMap to maintain the order while providing O(1) access.
70  *
71  * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed
72  * only if a Comparator is used which can deal with them; natural ordering
73  * cannot cope with null. Null values are always allowed. Note that the
74  * ordering must be <i>consistent with equals</i> to correctly implement
75  * the Map interface. If this condition is violated, the map is still
76  * well-behaved, but you may have suprising results when comparing it to
77  * other maps.<p>
78  *
79  * This implementation is not synchronized. If you need to share this between
80  * multiple threads, do something like:<br>
81  * <code>SortedMap m
82  * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
83  *
84  * The iterators are <i>fail-fast</i>, meaning that any structural
85  * modification, except for <code>remove()</code> called on the iterator
86  * itself, cause the iterator to throw a
87  * <code>ConcurrentModificationException</code> rather than exhibit
88  * non-deterministic behavior.
89  *
90  * <p>Note that the first call to <code>entrySet()</code>, <code>keySet()</code>
91  * and <code>values()</code> results in the creation of a new ozone object.</p>
92  *
93  * <p><b>NOTE:</b> Because of issues with implementing 2 Ozone objects that have
94  * to share non-Ozone objects, it can happen that a <code>FullXxx</code>
95  * instance is written to the backend-store while the <code>Iterator</code>
96  * remains in memory. If that happens you will receive a <code>ConcurrentModificationException</code>.
97  * If you receive such an exception and are completely sure that the collection
98  * has not been changed (objects added or removed from it) by another process,
99  * you should increase the memory available to the Ozone server, or decrease the
100  * time between successive calls on the methods of the iterator. It should be
101  * noted that there is no way to guarantee that an exception is thrown in this
102  * situation, just like there is no guarantee that an exception will be thrown
103  * when a 'regular' <code>java.util.Collection</code> is changed while an
104  * iterator is at the same time iterating over it. This is theory, but in the
105  * real world the changes of this happening are negligable.</code>
106  
107  </p>
108  *
109  * @author Jon Zeppieri
110  * @author Bryce McKinlay
111  * @author Eric Blake <ebb9@email.byu.edu>
112  * @author <a HREF="mailto:ozoneATmekenkampD0Tcom">Leo Mekenkamp (mind the anti-sp@m)</a> (adaptation for ozone)
113  * @see java.util.TreeMap
114  * @see java.util.Collections#synchronizedSortedMap(SortedMap)
115  */
116 public class FullTreeMapImpl extends BaseTreeMapImpl implements FullTreeMap {
117     // Implementation note:
118 // A red-black tree is a binary search tree with the additional properties
119 // that all paths to a leaf node visit the same number of black nodes,
120 // and no red node has red children. To avoid some null-pointer checks,
121 // we use the special node nil which is always black, has no relatives,
122 // and has key and value of null (but is not equal to a mapping of null).
123
124     private static final long serialVersionUID = 1L;
125
126     private class Node extends AbstractOzoneMap.AbstractNode implements BaseTreeMap.Node {
127
128         private static final long serialVersionUID = 1L;
129
130         private int color;
131
132         private BaseTreeMap.Node left = BaseTreeMapImpl.nilNode;
133
134         private BaseTreeMap.Node right = BaseTreeMapImpl.nilNode;
135
136         private BaseTreeMap.Node parent = BaseTreeMapImpl.nilNode;
137
138         public Node(Object JavaDoc key, Object JavaDoc value, int color) {
139             super(key, value);
140             setColor(color);
141         }
142
143         public void setRight(BaseTreeMap.Node right) {
144             this.right = right;
145         }
146
147         public void setParent(BaseTreeMap.Node parent) {
148             this.parent = parent;
149         }
150
151         public void setLeft(BaseTreeMap.Node left) {
152             this.left = left;
153         }
154
155         public void setColor(int color) {
156             this.color = color;
157         }
158
159         public BaseTreeMap.Node getRight() {
160             return right;
161         }
162
163         public BaseTreeMap.Node getParent() {
164             return parent;
165         }
166
167         public BaseTreeMap.Node getLeft() {
168             return left;
169         }
170
171         public int getColor() {
172             return color;
173         }
174
175         public boolean isNil() {
176             return false;
177         }
178
179     }
180
181     /**
182      * Instantiate a new TreeMap with no elements, using the keys' natural
183      * ordering to sort. All entries in the map must have a key which implements
184      * Comparable, and which are <i>mutually comparable</i>, otherwise map
185      * operations may throw a {@link ClassCastException}. Attempts to use
186      * a null key will throw a {@link NullPointerException}.
187      *
188      * @see Comparable
189      */
190     public FullTreeMapImpl() {
191     }
192
193     /**
194      * Instantiate a new TreeMap with no elements, using the provided comparator
195      * to sort. All entries in the map must have keys which are mutually
196      * comparable by the Comparator, otherwise map operations may throw a
197      * {@link ClassCastException}.
198      *
199      * @param c (comparator) the sort order for the keys of this map, or null
200      * for the natural order
201      */
202     public FullTreeMapImpl(Comparator JavaDoc c) {
203         super(c);
204     }
205
206     /**
207      * Instantiate a new TreeMap, initializing it with all of the elements in
208      * the provided Map. The elements will be sorted using the natural
209      * ordering of the keys. This algorithm runs in n*log(n) time. All entries
210      * in the map must have keys which implement Comparable and are mutually
211      * comparable, otherwise map operations may throw a
212      * {@link ClassCastException}.
213      *
214      * @param map a Map, whose entries will be put into this TreeMap
215      * @throws ClassCastException if the keys in the provided Map are not
216      * comparable
217      * @throws NullPointerException if map is null
218      * @see Comparable
219      */
220     public FullTreeMapImpl(Map JavaDoc map) {
221         super(map);
222     }
223
224     /**
225      * Instantiate a new TreeMap, initializing it with all of the elements in
226      * the provided SortedMap. The elements will be sorted using the same
227      * comparator as in the provided SortedMap. This runs in linear time.
228      *
229      * @param sm a SortedMap, whose entries will be put into this TreeMap
230      * @throws NullPointerException if sm is null
231      */
232     public FullTreeMapImpl(SortedMap JavaDoc sm) {
233         super(sm); // super sm ??? LOL!
234 }
235
236     protected BaseTreeMap emptyClone() {
237         // TODO: when FakeFactoryGenerator is finished replace with
238 // return FullTreeMapImplFactory.getDefault().create();
239 return (BaseTreeMap) database().createObject(FullTreeMapImpl.class);
240     }
241
242     protected BaseTreeMap.Node newNode(Object JavaDoc key, Object JavaDoc value, int color) {
243         BaseTreeMap.Node result = new Node(key, value, color);
244         return result;
245     }
246
247     /**
248      * Deserializes this object from the given stream.
249      *
250      * @param s the stream to read from
251      * @throws ClassNotFoundException if the underlying stream fails
252      * @throws IOException if the underlying stream fails
253      * @serialData the <i>size</i> (int), followed by key (Object) and value
254      * (Object) pairs in sorted order
255      */
256     private void readObject(ObjectInputStream JavaDoc s) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
257         root = nilNode;
258         s.defaultReadObject();
259         putFromObjStream(s, size, true);
260     }
261
262     /**
263      * @param s the stream to read from
264      * @param count the number of keys to read
265      * @param readValues true to read values, false to insert "" as the value
266      * @throws ClassNotFoundException if the underlying stream fails
267      * @throws IOException if the underlying stream fails
268      * @see #readObject(ObjectInputStream)
269      * @see java.util.TreeSet#readObject(ObjectInputStream)
270      */
271     private void putFromObjStream(ObjectInputStream JavaDoc s, int count, boolean readValues)
272             throws IOException JavaDoc, ClassNotFoundException JavaDoc {
273         _org_ozoneDB_fabricateTree(count);
274         BaseTreeMap.Node node = _org_ozoneDB_firstNode();
275
276         while (--count >= 0) {
277             node.setKey(s.readObject());
278             node.setValue(readValues ? s.readObject() : "");
279             node = _org_ozoneDB_successor(node);
280         }
281     }
282
283     /**
284      * Serializes this object to the given stream.
285      *
286      * @param s the stream to write to
287      * @throws IOException if the underlying stream fails
288      * @serialData the <i>size</i> (int), followed by key (Object) and value
289      * (Object) pairs in sorted order
290      */
291     private void writeObject(ObjectOutputStream JavaDoc s) throws IOException JavaDoc {
292         s.defaultWriteObject();
293
294         BaseTreeMap.Node node = _org_ozoneDB_firstNode();
295         while (!node.isNil()) {
296             s.writeObject(node.getKey());
297             s.writeObject(node.getValue());
298             node = _org_ozoneDB_successor(node);
299         }
300     }
301
302     public boolean _org_ozoneDB_alwaysUseInternalIterator() {
303         return false;
304     }
305     
306     /**
307      * Called automatically by Ozone. Increments the modification counter to
308      * make sure all <code>Iterator</code>s that were connected to a previous
309      * (memory) instance of this database object are invalidated.
310      */
311     public void onActivate() {
312         // TODO: FIXME: Aren't we taking a risk here? The javadocs for <code>ConcurrentModificationException</code>
313 // for instance clearly state that developers should not depend on that
314 // exception being thrown, probably because there is a "1 in 2^32 chance"
315 // that the internal mod counts for collection and iterator are the same
316 // while the collection has been changed. Actually this chance might be a
317 // lot smaller, since actually there have to be 2^32 operations on the
318 // collection and at the same time the iterator should go unused.
319 // Anyway, we <i>are</i> taking a risk here, albeit a small one, since
320 // for the modCount to be the same on an iterator and this collection
321 // we need either: 1) 0 changes on the collection and a roll-over on the
322 // high bits (probably Integer.MAX_VALUE times); or 2) Integer.MAX_VALUE
323 // changes for the low bits and Integer.MAX_VALUE - 1 writes for the high
324 // bits 3) any multiple of the above with a complete roll-over of the
325 // modCount. Since Java is not certified for use in nuclear installations,
326 // hart-monitoring machines, etc. I am willing to take this risk.
327 modCount += Integer.MAX_VALUE / 2;
328     }
329     
330 }
Popular Tags