00001 /* 00002 * TreeMap.hpp 00003 * 00004 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved. 00005 * 00006 * Oracle is a registered trademarks of Oracle Corporation and/or its 00007 * affiliates. 00008 * 00009 * This software is the confidential and proprietary information of Oracle 00010 * Corporation. You shall not disclose such confidential and proprietary 00011 * information and shall use it only in accordance with the terms of the 00012 * license agreement you entered into with Oracle. 00013 * 00014 * This notice may not be removed or altered. 00015 */ 00016 #ifndef COH_TREE_MAP_HPP 00017 #define COH_TREE_MAP_HPP 00018 00019 #include "coherence/lang.ns" 00020 00021 #include "coherence/util/AbstractMap.hpp" 00022 #include "coherence/util/Comparator.hpp" 00023 #include "coherence/util/Map.hpp" 00024 #include "coherence/util/SortedMap.hpp" 00025 00026 COH_OPEN_NAMESPACE2(coherence,util) 00027 00028 00029 /** 00030 * A tree map implementation. Stored as an AVL tree. Implementation is based on 00031 * the public domain implementation by Julienne Walker. This implementation is 00032 * not thread-safe. 00033 * 00034 * @see <a href="http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx"> 00035 * Implementation by Julienne Walker</a> 00036 * 00037 * @author tb 2009.02.22 00038 */ 00039 class COH_EXPORT TreeMap 00040 : public cloneable_spec<TreeMap, 00041 extends<AbstractMap>, 00042 implements<SortedMap> > 00043 { 00044 friend class factory<TreeMap>; 00045 00046 // ----- constructors --------------------------------------------------- 00047 00048 protected: 00049 /** 00050 * @internal 00051 */ 00052 TreeMap(); 00053 00054 /** 00055 * @internal 00056 */ 00057 TreeMap(Comparator::View vComparator); 00058 00059 /** 00060 * @internal 00061 */ 00062 TreeMap(const TreeMap& that); 00063 00064 /** 00065 * @internal 00066 */ 00067 virtual ~TreeMap(); 00068 00069 00070 // ----- Map interface -------------------------------------------------- 00071 00072 public: 00073 /** 00074 * {@inheritDoc} 00075 */ 00076 virtual size32_t size() const; 00077 00078 /** 00079 * {@inheritDoc} 00080 */ 00081 virtual bool isEmpty() const; 00082 00083 /** 00084 * {@inheritDoc} 00085 */ 00086 virtual bool containsKey(Object::View vKey) const; 00087 00088 /** 00089 * {@inheritDoc} 00090 */ 00091 virtual Object::Holder get(Object::View vKey) const; 00092 00093 /** 00094 * {@inheritDoc} 00095 */ 00096 using Map::get; 00097 00098 /** 00099 * {@inheritDoc} 00100 */ 00101 virtual Object::Holder put(Object::View vKey, Object::Holder ohValue); 00102 00103 /** 00104 * {@inheritDoc} 00105 */ 00106 virtual Object::Holder remove(Object::View vKey); 00107 00108 /** 00109 * {@inheritDoc} 00110 */ 00111 virtual void clear(); 00112 00113 /** 00114 * {@inheritDoc} 00115 */ 00116 virtual Set::View entrySet() const; 00117 00118 /** 00119 * {@inheritDoc} 00120 */ 00121 virtual Set::Handle entrySet(); 00122 00123 00124 // ----- Sorted Map interface ------------------------------------------- 00125 00126 public: 00127 /** 00128 * {@inheritDoc} 00129 */ 00130 virtual Comparator::View comparator() const; 00131 00132 /** 00133 * {@inheritDoc} 00134 */ 00135 virtual Object::View firstKey() const; 00136 00137 /** 00138 * {@inheritDoc} 00139 */ 00140 virtual Object::View lastKey() const; 00141 00142 /** 00143 * {@inheritDoc} 00144 */ 00145 virtual SortedMap::Handle headMap(Object::View vToKey); 00146 00147 /** 00148 * {@inheritDoc} 00149 */ 00150 virtual SortedMap::View headMap(Object::View vToKey) const; 00151 00152 /** 00153 * {@inheritDoc} 00154 */ 00155 virtual SortedMap::Handle subMap(Object::View vFromKey, 00156 Object::View vToKey); 00157 00158 /** 00159 * {@inheritDoc} 00160 */ 00161 virtual SortedMap::View subMap(Object::View vFromKey, 00162 Object::View vToKey) const; 00163 00164 /** 00165 * {@inheritDoc} 00166 */ 00167 virtual SortedMap::Handle tailMap(Object::View vFromKey); 00168 00169 /** 00170 * {@inheritDoc} 00171 */ 00172 virtual SortedMap::View tailMap(Object::View vFromKey) const; 00173 00174 00175 // ----- inner class: Node ---------------------------------------------- 00176 00177 public: 00178 /** 00179 * An AVL tree node. This class is used only within the 00180 * TreeMap class and its derivations. 00181 */ 00182 class COH_EXPORT Node 00183 : public cloneable_spec<Node, 00184 extends<Object>, 00185 implements<Map::Entry> > 00186 { 00187 friend class factory<Node>; 00188 00189 // ----- constructors ------------------------------------------- 00190 00191 protected: 00192 /** 00193 * @internal 00194 */ 00195 Node(Object::View ovKey); 00196 00197 /** 00198 * @internal 00199 */ 00200 Node(const Node& that); 00201 00202 // ----- Node interface ----------------------------------------- 00203 00204 protected: 00205 /** 00206 * Adopt a child node 00207 * 00208 * @param hChild the child to adopt 00209 * @param fLeft the position of the child 00210 */ 00211 virtual void adopt(Node::Handle hChild, bool fLeft); 00212 00213 /** 00214 * Get the value associated with the node. 00215 * 00216 * @return the value associated with the node. 00217 */ 00218 virtual Object::Holder getValue() const; 00219 00220 /** 00221 * Set the value associated with the node. 00222 * 00223 * @param ohValue the value assocaited with the node 00224 * 00225 * @return the old value associated with the node 00226 */ 00227 virtual Object::Holder setValue(Object::Holder ohValue); 00228 00229 /** 00230 * Determine if this node is a part of a 2-3-4 leaf node 00231 * (i.e. at least one NULL child). 00232 * 00233 * @return true if this node is a leaf 00234 */ 00235 virtual bool isLeaf() const; 00236 00237 /** 00238 * Unlink this element and all sub elements. 00239 */ 00240 virtual void dissolve(); 00241 00242 // ----- Map::Entry interface ----------------------------------- 00243 00244 public: 00245 /** 00246 * Return the key corresponding to this entry. 00247 * 00248 * @return the key corresponding to this entry 00249 */ 00250 virtual Object::View getKey() const; 00251 00252 /** 00253 * Return the value corresponding to this entry. 00254 * 00255 * @return the value corresponding to this entry 00256 */ 00257 virtual Object::Holder getValue(); 00258 00259 // ----- Object interface --------------------------------------- 00260 00261 public: 00262 /** 00263 * {@inheritDoc} 00264 */ 00265 virtual void toStream(std::ostream& out) const; 00266 00267 /** 00268 * {@inheritDoc} 00269 */ 00270 virtual void onInit(); 00271 00272 // ----- data members ------------------------------------------- 00273 00274 public: 00275 /** 00276 * The key of the node. The key, once set, is considered 00277 * immutable. 00278 */ 00279 FinalView<Object> f_vKey; 00280 00281 /** 00282 * The value of the node. 00283 */ 00284 MemberHolder<Object> m_ohValue; 00285 00286 /** 00287 * The AVL balance factor of the sub-tree. 00288 */ 00289 int32_t nBalance; 00290 00291 /** 00292 * The parent of this node. 00293 */ 00294 MemberHandle<Node> m_hParent; 00295 00296 /** 00297 * The left child of this node. 00298 */ 00299 MemberHandle<Node> m_hLeft; 00300 00301 /** 00302 * The right child of this node. 00303 */ 00304 MemberHandle<Node> m_hRight; 00305 00306 // ----- friends -------------------------------------------- 00307 00308 friend class TreeMap; 00309 }; 00310 00311 00312 // ----- helper methods ------------------------------------------------- 00313 00314 public: 00315 /** 00316 * Remove the specified node from the tree. 00317 * 00318 * The supplied node must be part of the tree. 00319 * 00320 * @param hNode the node to remove 00321 */ 00322 virtual void removeNode(Node::Handle hNode); 00323 00324 /** 00325 * Determine if Node is the head of the tree. 00326 * 00327 * @param vNode the node to compare to the head of the tree 00328 * 00329 * @return true if the passed in Node is the head of the tree 00330 */ 00331 virtual bool isHead(Node::View vNode) const; 00332 00333 /** 00334 * Return an Iterator over this tree map. 00335 * 00336 * @return an Iterator over this tree map 00337 */ 00338 virtual Iterator::Handle iterator() const; 00339 00340 /** 00341 * Return an Iterator over this tree map. 00342 * 00343 * @return an Iterator over this tree map 00344 */ 00345 virtual Muterator::Handle iterator(); 00346 00347 /** 00348 * Compare two Objects. If both Objects are comparable with this tree 00349 * map's Comparator, return < 0, 0 or > 0 if the first Object is less 00350 * than, equal to, or greater than the second Object. 00351 * 00352 * @param v1 the first object to compare 00353 * @param v2 the second object to compare 00354 * 00355 * @return < 0, 0 or > 0 if the first Object is less than, 00356 * equal to, or greater than the second Object 00357 */ 00358 virtual int32_t compare(Object::View v1, Object::View v2) const; 00359 00360 /** 00361 * Find the specified key and return its node. 00362 * 00363 * @param vKey the key to look for 00364 * 00365 * @return the node containing the index or NULL if the index is not 00366 * in the TreeMap 00367 */ 00368 virtual Node::Handle find(Object::View vKey) const; 00369 00370 /** 00371 * Get the head node. 00372 * 00373 * @return this tree map's head node 00374 */ 00375 virtual Node::Handle getHeadNode() const; 00376 00377 protected: 00378 00379 /** 00380 * Replace one node with another. 00381 * 00382 * @param hNodeA the node to be unlinked 00383 * @param hNodeB the node to be linked in nodeA's place; may be NULL 00384 * 00385 * @return nodeB's new parent 00386 */ 00387 virtual Node::Handle replace(Node::Handle hNodeA, 00388 Node::Handle hNodeB); 00389 00390 /** 00391 * Rotate a node in a given direction. 00392 * 00393 * @param hNode the node to rotate 00394 * @param fLeft the rotation direction 00395 * 00396 * @return the node's new parent (former child) 00397 */ 00398 virtual Node::Handle rotate(Node::Handle hNode, bool fLeft); 00399 00400 /** 00401 * Double rotate a node in a given direction. 00402 * 00403 * @param hNode the node to rotate 00404 * @param fLeft the final rotation direction 00405 * 00406 * @return the node's new parent (former grand child) 00407 */ 00408 virtual Node::Handle doubleRotate(Node::Handle hNode, 00409 bool fLeft); 00410 00411 /** 00412 * Adjust the balance factor of a node and its descendants prior to a 00413 * double rotation. 00414 * 00415 * @param hNode the node which was rotated 00416 * @param hChild the child to adjust 00417 * @param nBal the balance adjustment 00418 */ 00419 virtual void adjustDoubleBalance(Node::Handle hNode, 00420 Node::Handle hChild, int32_t nBal); 00421 00422 /** 00423 * Find the point at which a Node with the specified index would be 00424 * inserted. 00425 * 00426 * If the tree is empty then null is returned. If the index already 00427 * exists then the existing Node is returned, otherwise the Node which 00428 * will be the parent of the new Node is returned. 00429 * 00430 * @param ovKey the key of the new node 00431 * 00432 * @return NULL, node, or parent 00433 */ 00434 virtual Node::Handle findInsertionPoint(Object::View ovKey) const; 00435 00436 /** 00437 * Insert a node into a tree and re-balance. 00438 * 00439 * @param hParent the location at which to insert the node 00440 * @param hChild the node to insert 00441 */ 00442 virtual void balancedInsertion(Node::Handle hParent, 00443 Node::Handle hChild); 00444 00445 /** 00446 * Re-balance the tree following the removal of a node. 00447 * 00448 * @param hPruned the node whose sub-tree shrunk 00449 * @param fPrunedLeft the side on which the sub-tree shrunk 00450 */ 00451 virtual void balancePostRemove(Node::Handle hPruned, 00452 bool fPrunedLeft); 00453 00454 /** 00455 * Create a new Node 00456 * 00457 * @param vKey the key of the new Node 00458 * @param ohValue the value of the new Node 00459 * 00460 * @return the newly instantiated Node 00461 */ 00462 virtual Node::Handle instantiateNode(Object::View vKey, 00463 Object::Holder ohValue); 00464 00465 00466 // ----- data members --------------------------------------------------- 00467 00468 protected: 00469 /** 00470 * The number of nodes in the tree. This can be determined by 00471 * iterating through the tree, but by keeping the size cached, certain 00472 * operations that need the size of the tree up front are much more 00473 * efficient. 00474 */ 00475 size32_t m_nSize; 00476 00477 /** 00478 * The first node of the tree (or NULL if the tree is empty). The 00479 * first node is referred to as the "head" or the "root" node. 00480 */ 00481 mutable MemberHandle<Node> m_hHead; 00482 00483 /** 00484 * The comparator used to maintain order in this tree map, or 00485 * NULL if it uses the natural ordering of its keys. 00486 */ 00487 FinalView<Comparator> f_vComparator; 00488 }; 00489 00490 COH_CLOSE_NAMESPACE2 00491 00492 #endif // COH_TREE_MAP_HPP