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