NodeTreeMapImpl


1   // You can redistribute this software and/or modify it under the terms of
2   // the Ozone Library License version 1 published by ozone-db.org.
3   //
4   // This file is
5   // Copyright (C) 2002-@year@ Leo Mekenkamp. All rights reserved.
6   // $Id: NodeTreeMapImpl.java,v 1.6 2003/11/27 15:55:11 leomekenkamp Exp $
7   
8   package org.ozoneDB.collections;
9   
10  import java.util.Comparator  ;
11  import java.util.Map  ;
12  import java.util.SortedMap  ;
13  
14  /**
15   * This class provides a red-black tree implementation of the SortedMap
16   * interface.  Elements in the Map will be sorted by either a user-provided
17   * Comparator object, or by the natural ordering of the keys.
18   *
19   * The algorithms are adopted from Corman, Leiserson, and Rivest's
20   * <i>Introduction to Algorithms.</i>  TreeMap guarantees O(log n)
21   * insertion and deletion of elements.  That being said, there is a large
22   * enough constant coefficient in front of that "log n" (overhead involved
23   * in keeping the tree balanced), that TreeMap may not be the best choice
24   * for small collections. If something is already sorted, you may want to
25   * just use a LinkedHashMap to maintain the order while providing O(1) access.
26   *
27   * TreeMap is a part of the JDK1.2 Collections API.  Null keys are allowed
28   * only if a Comparator is used which can deal with them; natural ordering
29   * cannot cope with null.  Null values are always allowed. Note that the
30   * ordering must be <i>consistent with equals</i> to correctly implement
31   * the Map interface. If this condition is violated, the map is still
32   * well-behaved, but you may have suprising results when comparing it to
33   * other maps.<p>
34   *
35   * This implementation is not synchronized. If you need to share this between
36   * multiple threads, do something like:<br>
37   * <code>SortedMap m
38   *       = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
39   *
40   * The iterators are <i>fail-fast</i>, meaning that any structural
41   * modification, except for <code>remove()</code> called on the iterator
42   * itself, cause the iterator to throw a
43   * <code>ConcurrentModificationException</code> rather than exhibit
44   * non-deterministic behavior.
45   *
46   * <p>Note that the first call to <code>entrySet()</code>, <code>keySet()</code>
47   * and <code>values()</code> result in the creation of a new ozone object.</p>
48   *
49   * @author Jon Zeppieri
50   * @author Bryce McKinlay
51   * @author Eric Blake <ebb9@email.byu.edu>
52   * @author <a HREF="mailto:ozoneATmekenkampD0Tcom">Leo Mekenkamp (mind the anti-sp@m)</a> (adaptation for ozone)
53   * @see java.util.TreeMap
54   * @see java.util.Collections#synchronizedSortedMap(SortedMap)
55   */
56  public class NodeTreeMapImpl extends BaseTreeMapImpl implements NodeTreeMap {
57      // Implementation note:
58      // A red-black tree is a binary search tree with the additional properties
59      // that all paths to a leaf node visit the same number of black nodes,
60      // and no red node has red children. To avoid some null-pointer checks,
61      // we use the special node nil which is always black, has no relatives,
62      // and has key and value of null (but is not equal to a mapping of null).
63  
64      private static final long serialVersionUID = 1L;
65  
66      /**
67       * Instantiate a new TreeMap with no elements, using the keys' natural
68       * ordering to sort. All entries in the map must have a key which implements
69       * Comparable, and which are <i>mutually comparable</i>, otherwise map
70       * operations may throw a {@link ClassCastException}. Attempts to use
71       * a null key will throw a {@link NullPointerException}.
72       *
73       * @see Comparable
74       */
75      public NodeTreeMapImpl() {
76      }
77  
78      /**
79       * Instantiate a new TreeMap with no elements, using the provided comparator
80       * to sort. All entries in the map must have keys which are mutually
81       * comparable by the Comparator, otherwise map operations may throw a
82       * {@link ClassCastException}.
83       *
84       * @param c (comparator) the sort order for the keys of this map, or null
85       *        for the natural order
86       */
87      public NodeTreeMapImpl(Comparator   c) {
88          super(c);
89      }
90  
91      /**
92       * Instantiate a new TreeMap, initializing it with all of the elements in
93       * the provided Map.  The elements will be sorted using the natural
94       * ordering of the keys. This algorithm runs in n*log(n) time. All entries
95       * in the map must have keys which implement Comparable and are mutually
96       * comparable, otherwise map operations may throw a
97       * {@link ClassCastException}.
98       *
99       * @param map a Map, whose entries will be put into this TreeMap
100      * @throws ClassCastException if the keys in the provided Map are not
101      *         comparable
102      * @throws NullPointerException if map is null
103      * @see Comparable
104      */
105     public NodeTreeMapImpl(Map   map) {
106         super(map);
107     }
108 
109     /**
110      * Instantiate a new TreeMap, initializing it with all of the elements in
111      * the provided SortedMap.  The elements will be sorted using the same
112      * comparator as in the provided SortedMap. This runs in linear time.
113      *
114      * @param sm a SortedMap, whose entries will be put into this TreeMap
115      * @throws NullPointerException if sm is null
116      */
117     public NodeTreeMapImpl(SortedMap   sm) {
118         super(sm); // super sm ??? LOL!
119     }
120 
121     protected BaseTreeMap emptyClone() {
122         // TODO: when FakeFactoryGenerator is finished replace with
123         // return FullTreeMapImplFactory.getDefault().create();
124         return (BaseTreeMap) database().createObject(NodeTreeMapImpl.class);
125     }
126 
127     protected BaseTreeMap.Node newNode(Object   key, Object   value, int color) {
128         // TODO: when FakeFactoryGenerator is finished replace with
129         // _NodeTreeMap_OzoneNode result return _NodeTreeMap_OzoneNodeImplFactory.getDefault().create(key, value, color);
130         _NodeTreeMap_OzoneNode result = (_NodeTreeMap_OzoneNode) database().createObject(
131                 _NodeTreeMap_OzoneNodeImpl.class,
132                 new Class  [] {Object  .class, Object  .class, int.class},
133                 new Object  [] {key, value, new Integer  (color)}
134         );
135         return result;
136     }
137 
138     public boolean _org_ozoneDB_alwaysUseInternalIterator() {
139         return true;
140     }
141     
142 }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags