00001 /* 00002 * AbstractSparseArray.hpp 00003 * 00004 * Copyright (c) 2000, 2014, 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_ABSTRACT_SPARSE_ARRAY_HPP 00017 #define COH_ABSTRACT_SPARSE_ARRAY_HPP 00018 00019 #include "coherence/lang.ns" 00020 00021 #include "coherence/util/AbstractLongArray.hpp" 00022 00023 COH_OPEN_NAMESPACE2(coherence,util) 00024 00025 00026 /** 00027 * A data structure resembling an array indexed by long values, stored as an 00028 * AVL tree. Implementation is based on the public domain implementation by 00029 * Julienne Walker. This implementation is not thread-safe. 00030 * 00031 * @see <a href="http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx"> 00032 * Implementation by Julienne Walker</a> 00033 * 00034 * @author js 2008.04.25 00035 */ 00036 class COH_EXPORT AbstractSparseArray 00037 : public abstract_spec<AbstractSparseArray, 00038 extends<AbstractLongArray> > 00039 { 00040 // ----- constructors --------------------------------------------------- 00041 00042 protected: 00043 /** 00044 * @internal 00045 */ 00046 AbstractSparseArray(); 00047 00048 /** 00049 * @internal 00050 */ 00051 AbstractSparseArray(const AbstractSparseArray& that); 00052 00053 /** 00054 * @internal 00055 */ 00056 virtual ~AbstractSparseArray(); 00057 00058 00059 // ----- LongArray interface -------------------------------------------- 00060 00061 public: 00062 /** 00063 * {@inheritDoc} 00064 */ 00065 virtual Object::Holder get(int64_t lIndex) const; 00066 00067 /** 00068 * {@inheritDoc} 00069 */ 00070 virtual Object::Holder set(int64_t lIndex, Object::Holder ohValue); 00071 00072 /** 00073 * {@inheritDoc} 00074 */ 00075 virtual bool exists(int64_t lIndex) const; 00076 00077 /** 00078 * {@inheritDoc} 00079 */ 00080 virtual Object::Holder remove(int64_t lIndex); 00081 00082 /** 00083 * {@inheritDoc} 00084 */ 00085 virtual void clear(); 00086 00087 /** 00088 * {@inheritDoc} 00089 */ 00090 virtual size32_t getSize() const; 00091 00092 /** 00093 * {@inheritDoc} 00094 */ 00095 virtual LongArrayIterator::Handle iterator(); 00096 00097 /** 00098 * {@inheritDoc} 00099 */ 00100 virtual LongArrayIterator::Handle iterator() const; 00101 00102 /** 00103 * {@inheritDoc} 00104 */ 00105 virtual LongArrayIterator::Handle iterator(int64_t lIndex); 00106 00107 /** 00108 * {@inheritDoc} 00109 */ 00110 virtual LongArrayIterator::Handle iterator(int64_t lIndex) const; 00111 00112 /** 00113 * {@inheritDoc} 00114 */ 00115 virtual int64_t getFirstIndex() const; 00116 00117 /** 00118 * {@inheritDoc} 00119 */ 00120 virtual int64_t getLastIndex() const; 00121 00122 00123 // ----- inner class: Node ---------------------------------------------- 00124 00125 public: 00126 /** 00127 * An AVL tree node. This class is used only within the 00128 * AbstractSparseArray class and its derivations. 00129 */ 00130 class COH_EXPORT Node 00131 : public abstract_spec<Node> 00132 { 00133 // ----- constructors ------------------------------------------- 00134 00135 protected: 00136 /** 00137 * @internal 00138 */ 00139 Node(int64_t lKey); 00140 00141 /** 00142 * @internal 00143 */ 00144 Node(const Node& that); 00145 00146 00147 // ----- Node interface ----------------------------------------- 00148 00149 public: 00150 /** 00151 * Adopt a child node 00152 * 00153 * @param hChild the child to adopt 00154 * @param fLeft the position of the child 00155 */ 00156 virtual void adopt(Node::Handle hChild, bool fLeft); 00157 00158 /** 00159 * Get the value associated with the node. 00160 * 00161 * @return the value associated with the node. 00162 */ 00163 virtual Object::Holder getValue() const = 0; 00164 00165 /** 00166 * Set the value associated with the node. 00167 * 00168 * @param ohValue the value assocaited with the node 00169 * 00170 * @return the old value associated with the node 00171 */ 00172 virtual Object::Holder setValue(Object::Holder ohValue) = 0; 00173 00174 /** 00175 * Determine if this node is a part of a 2-3-4 leaf node 00176 * (i.e. at least one NULL child). 00177 * 00178 * @return true if this node is a leaf 00179 */ 00180 virtual bool isLeaf() const; 00181 00182 /** 00183 * Return true iff the node is linked to other nodes. 00184 * 00185 * @return true iff the node has a parent or children 00186 */ 00187 virtual bool isLinked() const; 00188 00189 /** 00190 * Unlink this element and all sub elements. 00191 */ 00192 virtual void dissolve(); 00193 00194 // ----- Object interface --------------------------------------- 00195 00196 public: 00197 /** 00198 * {@inheritDoc} 00199 */ 00200 virtual void toStream(std::ostream& out) const; 00201 00202 /** 00203 * {@inheritDoc} 00204 */ 00205 virtual void onInit(); 00206 00207 // ----- data members ------------------------------------------- 00208 00209 public: 00210 /** 00211 * The key of the node. The key, once set, is considered 00212 * immutable. 00213 */ 00214 int64_t key; 00215 00216 /** 00217 * The AVL balance factor of the sub-tree. 00218 */ 00219 int32_t balance; 00220 00221 /** 00222 * The parent of this node. 00223 */ 00224 MemberHandle<Node> parent; 00225 00226 /** 00227 * The left child of this node. 00228 */ 00229 MemberHandle<Node> left; 00230 00231 /** 00232 * The right child of this node. 00233 */ 00234 MemberHandle<Node> right; 00235 }; 00236 00237 00238 // ----- helper methods ------------------------------------------------- 00239 00240 public: 00241 /** 00242 * Remove the specified node from the tree. 00243 * 00244 * The supplied node must be part of the tree. 00245 * 00246 * @param hNode the node to remove 00247 */ 00248 virtual void remove(Node::Handle hNode); 00249 00250 /** 00251 * Determine if Node is the head of the tree. 00252 * 00253 * @param vNode the node to compare to the head of the tree 00254 * 00255 * @return true if the passed in Node is the head of the tree 00256 */ 00257 virtual bool isHead(Node::View vNode) const; 00258 00259 protected: 00260 /** 00261 * Find the specified key and return its node. 00262 * 00263 * @param lIndex the long index to look for in the SparseArray 00264 * 00265 * @return the node containing the index or NULL if the index is not 00266 * in the SparseArray 00267 */ 00268 virtual Node::Handle find(int64_t lIndex) const; 00269 00270 /** 00271 * Replace one node with another. 00272 * 00273 * @param hNodeA the node to be unlinked 00274 * @param hNodeB the node to be linked in nodeA's place; may be NULL 00275 * 00276 * @return nodeB's new parent 00277 */ 00278 virtual Node::Handle replace(Node::Handle hNodeA, 00279 Node::Handle hNodeB); 00280 00281 /** 00282 * Rotate a node in a given direction. 00283 * 00284 * @param hNode the node to rotate 00285 * @param fLeft the rotation direction 00286 * 00287 * @return the node's new parent (former child) 00288 */ 00289 virtual Node::Handle rotate(Node::Handle hNode, bool fLeft); 00290 00291 /** 00292 * Double rotate a node in a given direction. 00293 * 00294 * @param hNode the node to rotate 00295 * @param fLeft the final rotation direction 00296 * 00297 * @return the node's new parent (former grand child) 00298 */ 00299 virtual Node::Handle doubleRotate(Node::Handle hNode, 00300 bool fLeft); 00301 00302 /** 00303 * Adjust the balance factor of a node and its descendants prior to a 00304 * double rotation. 00305 * 00306 * @param hNode the node which was rotated 00307 * @param hChild the child to adjust 00308 * @param nBal the balance adjustment 00309 */ 00310 virtual void adjustDoubleBalance(Node::Handle hNode, 00311 Node::Handle hChild, int32_t nBal); 00312 00313 /** 00314 * Find the point at which a Node with the specified index would be 00315 * inserted. 00316 * 00317 * If the tree is empty then NULL is returned. If the index already 00318 * exists then the existing Node is returned, otherwise the Node which 00319 * will be the parent of the new Node is returned. 00320 * 00321 * @param lIndex the index of the new node 00322 * 00323 * @return NULL, node, or parent 00324 */ 00325 virtual Node::Handle findInsertionPoint(int64_t lIndex) const; 00326 00327 /** 00328 * Insert a node into a tree and re-balance. 00329 * 00330 * @param hParent the location at which to insert the node 00331 * @param hChild the node to insert 00332 */ 00333 virtual void balancedInsertion(Node::Handle hParent, 00334 Node::Handle hChild); 00335 00336 /** 00337 * Re-balance the tree following the removal of a node. 00338 * 00339 * @param hPruned the node whose sub-tree shrunk 00340 * @param fPrunedLeft the side on which the sub-tree shrunk 00341 */ 00342 virtual void balancePostRemove(Node::Handle hPruned, 00343 bool fPrunedLeft); 00344 00345 /** 00346 * Create a new Node 00347 * 00348 * @param lKey the key of the new Node 00349 * @param ohValue the value of the new Node 00350 * 00351 * @return the newly instantiated Node 00352 */ 00353 virtual Node::Handle instantiateNode(int64_t lKey, 00354 Object::Holder ohValue) = 0; 00355 00356 00357 // ----- data members --------------------------------------------------- 00358 00359 protected: 00360 /** 00361 * The number of nodes in the tree. This can be determined by 00362 * iterating through the tree, but by keeping the size cached, certain 00363 * operations that need the size of the tree up front are much more 00364 * efficient. 00365 */ 00366 size32_t m_nSize; 00367 00368 /** 00369 * The first node of the tree (or NULL if the tree is empty). The 00370 * first node is referred to as the "head" or the "root" node. 00371 */ 00372 mutable MemberHandle<Node> m_hHead; 00373 }; 00374 00375 COH_CLOSE_NAMESPACE2 00376 00377 #endif // COH_ABSTRACT_SPARSE_ARRAY_HPP