00001 /* 00002 * SortedBag.hpp 00003 * 00004 * Copyright (c) 2000, 2020, 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_SORTED_BAG_HPP 00017 #define COH_SORTED_BAG_HPP 00018 00019 #include "coherence/lang.ns" 00020 00021 #include "coherence/util/AbstractCollection.hpp" 00022 #include "coherence/util/AtomicCounter.hpp" 00023 #include "coherence/util/Comparator.hpp" 00024 #include "coherence/util/Map.hpp" 00025 #include "coherence/util/NavigableMap.hpp" 00026 00027 COH_OPEN_NAMESPACE2(coherence,util) 00028 00029 00030 /** 00031 * SortedBag is a <a href="http://en.wikipedia.org/wiki/Multiset"> 00032 * <i>multiset</i> or <i>bag</i></a> implementation that supports sorted traversal 00033 * of the contained elements and is optimized for insertions and removals. 00034 * 00035 * This implementation is not thread-safe and does not support NULL elements. 00036 * 00037 * @author rhl 2013.04.24 00038 */ 00039 class COH_EXPORT SortedBag 00040 : public class_spec<SortedBag, 00041 extends<AbstractCollection> > 00042 { 00043 friend class factory<SortedBag>; 00044 00045 // ----- handle definitions (needed for nested classes) ----------------- 00046 00047 public: 00048 typedef this_spec::Handle Handle; 00049 typedef this_spec::View View; 00050 typedef this_spec::Holder Holder; 00051 00052 00053 // ----- constructors --------------------------------------------------- 00054 00055 protected: 00056 /** 00057 * Default constructor. 00058 */ 00059 SortedBag(); 00060 00061 /** 00062 * Construct a SortedBag whose elements are to be ordered by the specified 00063 * comparator. 00064 * 00065 * @param vComparator the comparator to use to order the elements 00066 */ 00067 SortedBag(Comparator::View vComparator); 00068 00069 00070 private: 00071 /** 00072 * Blocked copy constructor. 00073 */ 00074 SortedBag(const SortedBag& that); 00075 00076 00077 // ----- accessors ------------------------------------------------------ 00078 00079 protected: 00080 /** 00081 * Return the internal navigable map holding the bag contents. 00082 * 00083 * @return the internal navigable map holding the bag contents 00084 */ 00085 virtual NavigableMap::Handle getInternalMap() const; 00086 00087 /** 00088 * Return the Comparator used to order the bag contents. 00089 * 00090 * @return the Comparator used to order the bag contents 00091 */ 00092 virtual Comparator::View getComparator() const; 00093 00094 /** 00095 * Return the nonce counter used to assign unique element ids. 00096 * 00097 * @return the nonce counter 00098 */ 00099 virtual AtomicCounter::Handle getNonceCounter(); 00100 00101 00102 // ----- AbstractCollection methods ------------------------------------- 00103 00104 public: 00105 /** 00106 * {@inheritDoc} 00107 */ 00108 virtual size32_t size() const; 00109 00110 /** 00111 * {@inheritDoc} 00112 */ 00113 virtual bool isEmpty() const; 00114 00115 /** 00116 * {@inheritDoc} 00117 */ 00118 virtual bool contains(Object::View vo) const; 00119 00120 /** 00121 * {@inheritDoc} 00122 */ 00123 virtual Iterator::Handle iterator() const; 00124 00125 /** 00126 * {@inheritDoc} 00127 */ 00128 virtual Muterator::Handle iterator(); 00129 00130 /** 00131 * {@inheritDoc} 00132 */ 00133 virtual bool add(Object::Holder oh); 00134 00135 /** 00136 * {@inheritDoc} 00137 */ 00138 virtual bool remove(Object::View v); 00139 00140 00141 // ----- SortedBag interface -------------------------------------------- 00142 00143 public: 00144 /** 00145 * Returns a view of the portion of this bag whose elements range 00146 * from <tt>vFrom</tt>, inclusive, to <tt>vTo</tt>, 00147 * exclusive. (If <tt>vFrom</tt> and <tt>vTo</tt> are 00148 * equal, the returned bag is empty.) The returned bag is backed 00149 * by this bag, so changes in the returned bag are reflected in 00150 * this bag, and vice-versa. The returned bag supports all 00151 * optional bag operations that this bag supports. 00152 * 00153 * The returned bag will throw an <tt>IllegalArgumentException</tt> 00154 * on an attempt to insert an element outside its range. 00155 * 00156 * @param vFrom low endpoint (inclusive) of the returned bag 00157 * @param vTo high endpoint (exclusive) of the returned bag 00158 * 00159 * @return a view of the portion of this bag whose elements range from 00160 * <tt>vFrom</tt>, inclusive, to <tt>vTo</tt>, exclusive 00161 * 00162 * @throws ClassCastException if <tt>vFrom</tt> and 00163 * <tt>vTo</tt> cannot be compared to one another using this 00164 * bag's comparator (or, if the bag has no comparator, using 00165 * natural ordering). Implementations may, but are not required 00166 * to, throw this exception if <tt>vFrom</tt> or 00167 * <tt>vTo</tt> cannot be compared to elements currently in 00168 * the bag. 00169 * @throws NullPointerException if <tt>vFrom</tt> or 00170 * <tt>vTo</tt> is NULL and this bag does not permit NULL 00171 * elements 00172 * @throws IllegalArgumentException if <tt>vFrom</tt> is 00173 * greater than <tt>vTo</tt>; or if this bag itself 00174 * has a restricted range, and <tt>vFrom</tt> or 00175 * <tt>vTo</tt> lies outside the bounds of the range 00176 */ 00177 virtual SortedBag::Handle subBag(Object::View vFrom, Object::View vTo); 00178 virtual SortedBag::View subBag(Object::View vFrom, Object::View vTo) const; 00179 00180 /** 00181 * Returns a view of the portion of this bag whose elements are 00182 * strictly less than <tt>vTo</tt>. The returned bag is 00183 * backed by this bag, so changes in the returned bag are 00184 * reflected in this bag, and vice-versa. The returned bag 00185 * supports all optional bag operations that this bag supports. 00186 * 00187 * The returned bag will throw an <tt>IllegalArgumentException</tt> 00188 * on an attempt to insert an element outside its range. 00189 * 00190 * @param vTo high endpoint (exclusive) of the returned bag 00191 * 00192 * @return a view of the portion of this bag whose elements are strictly 00193 * less than <tt>vTo</tt> 00194 * 00195 * @throws ClassCastException if <tt>vTo</tt> is not compatible 00196 * with this bag's comparator (or, if the bag has no comparator, 00197 * if <tt>vTo</tt> does not implement {@link Comparable}). 00198 * Implementations may, but are not required to, throw this 00199 * exception if <tt>vTo</tt> cannot be compared to elements 00200 * currently in the bag. 00201 * @throws NullPointerException if <tt>vTo</tt> is NULL and 00202 * this bag does not permit NULL elements 00203 * @throws IllegalArgumentException if this bag itself has a 00204 * restricted range, and <tt>vTo</tt> lies outside the 00205 * bounds of the range 00206 */ 00207 virtual SortedBag::Handle headBag(Object::View vTo); 00208 virtual SortedBag::View headBag(Object::View vTo) const; 00209 00210 /** 00211 * Returns a view of the portion of this bag whose elements are 00212 * greater than or equal to <tt>vFrom</tt>. The returned 00213 * bag is backed by this bag, so changes in the returned bag are 00214 * reflected in this bag, and vice-versa. The returned bag 00215 * supports all optional bag operations that this bag supports. 00216 * 00217 * The returned bag will throw an <tt>IllegalArgumentException</tt> 00218 * on an attempt to insert an element outside its range. 00219 * 00220 * @param vFrom low endpoint (inclusive) of the returned bag 00221 * 00222 * @return a view of the portion of this bag whose elements are greater 00223 * than or equal to <tt>vFrom</tt> 00224 * 00225 * @throws ClassCastException if <tt>vFrom</tt> is not compatible 00226 * with this bag's comparator (or, if the bag has no comparator, 00227 * if <tt>vFrom</tt> does not implement {@link Comparable}). 00228 * Implementations may, but are not required to, throw this 00229 * exception if <tt>vFrom</tt> cannot be compared to elements 00230 * currently in the bag. 00231 * @throws NullPointerException if <tt>vFrom</tt> is NULL 00232 * and this bag does not permit NULL elements 00233 * @throws IllegalArgumentException if this bag itself has a 00234 * restricted range, and <tt>vFrom</tt> lies outside the 00235 * bounds of the range 00236 */ 00237 virtual SortedBag::Handle tailBag(Object::View vFrom); 00238 virtual SortedBag::View tailBag(Object::View vFrom) const; 00239 00240 /** 00241 * Returns the first (lowest) element currently in this bag. 00242 * 00243 * @return the first (lowest) element currently in this bag 00244 * 00245 * @throws NoSuchElementException if this bag is empty 00246 */ 00247 virtual Object::Holder first() const; 00248 00249 /** 00250 * Returns the last (highest) element currently in this bag. 00251 * 00252 * @return the last (highest) element currently in this bag 00253 * 00254 * @throws NoSuchElementException if this bag is empty 00255 */ 00256 virtual Object::Holder last() const; 00257 00258 /** 00259 * Remove and return the least element in this bag, or NULL if empty. 00260 * 00261 * @return the removed first element of this bag, or NULL if empty 00262 */ 00263 virtual Object::Holder removeFirst(); 00264 00265 /** 00266 * Remove and return the greatest element in this bag, or NULL if empty. 00267 * 00268 * @return the removed last element of this bag, or NULL if empty 00269 */ 00270 virtual Object::Holder removeLast(); 00271 00272 00273 // ----- inner class: WrapperComparator --------------------------------- 00274 00275 public: 00276 /** 00277 * WrapperComparator is a Comparator implementation that is aware of 00278 * {@link UniqueElement} wrappers and will delegate the comparison of the 00279 * elements in both forms to the wrapped comparator. 00280 */ 00281 class COH_EXPORT WrapperComparator 00282 : public class_spec<WrapperComparator, 00283 extends<Object>, 00284 implements<Comparator> > 00285 { 00286 friend class factory<WrapperComparator>; 00287 00288 // ----- constructors ------------------------------------------- 00289 00290 protected: 00291 /** 00292 * @internal 00293 */ 00294 WrapperComparator(Comparator::View vComparator); 00295 00296 /** 00297 * @internal 00298 */ 00299 WrapperComparator(const WrapperComparator& that); 00300 00301 // ----- Comparator interface --------------------------------------- 00302 00303 public: 00304 /** 00305 * {@inheritDoc} 00306 */ 00307 virtual int32_t compare(Object::View v1, Object::View v2) const; 00308 00309 00310 // ----- data members ----------------------------------------------- 00311 00312 protected: 00313 /** 00314 * The underlying "logical" comparator. 00315 */ 00316 FinalView<Comparator> f_vComparator; 00317 }; 00318 00319 00320 // ----- inner class: UniqueElement ------------------------------------- 00321 00322 protected: 00323 /** 00324 * UniqueElement represents a unique instance of a logical element in the bag. 00325 */ 00326 class COH_EXPORT UniqueElement 00327 : public class_spec<UniqueElement, 00328 extends<Object>, 00329 implements<Comparable> > 00330 { 00331 friend class factory<UniqueElement>; 00332 00333 // ----- constructors ----------------------------------------------- 00334 00335 protected: 00336 /** 00337 * Create a UniqueElement to represent the specified element. 00338 * 00339 * @param hBag reference to the "outer this" 00340 * @param oh the element 00341 */ 00342 UniqueElement(SortedBag::Handle hBag, Object::Holder oh); 00343 00344 00345 // ----- Comparable interface --------------------------------------- 00346 00347 public: 00348 /** 00349 * {@inheritDoc} 00350 */ 00351 virtual int32_t compareTo(Object::View vThat) const; 00352 00353 00354 // ----- data members ----------------------------------------------- 00355 00356 protected: 00357 00358 /** 00359 * The unique "id" for this element. 00360 */ 00361 const int64_t f_nUniqueId; 00362 00363 /** 00364 * The "actual" element. 00365 */ 00366 FinalHolder<Object> f_ohElem; 00367 00368 /** 00369 * The handle to the "outer-this" SortedBag. 00370 */ 00371 WeakHandle<SortedBag> f_hBagOuter; 00372 00373 // ----- friends ---------------------------------------------------- 00374 00375 friend class SortedBag; 00376 }; 00377 00378 00379 // ----- inner class: ViewBag ------------------------------------------- 00380 00381 // forward declaration 00382 class ViewBag; 00383 00384 00385 // ----- helper methods ------------------------------------------------- 00386 00387 public: 00388 00389 /** 00390 * Unwrap the specified element (which could be a {@link UniqueElement 00391 * wrapped} or an "actual") element. 00392 * 00393 * @param o the element to unwrap 00394 * 00395 * @return the unwrapped element 00396 */ 00397 virtual Object::Holder unwrap(Object::View v) const; 00398 00399 protected: 00400 /** 00401 * Factory for the navigable internal map to use to hold the bag elements. 00402 * 00403 * @param comparator the comparator to use to sort the bag elements 00404 * 00405 * @return a navigable map 00406 */ 00407 virtual NavigableMap::Handle instantiateInternalMap(Comparator::View vComparator); 00408 00409 /** 00410 * Wrap the specified element to ensure uniqueness. 00411 * 00412 * @param oh the element to wrap 00413 * 00414 * @return a unique element representing the specified element 00415 */ 00416 virtual UniqueElement::View wrap(Object::Holder oh); 00417 00418 00419 // ----- data members --------------------------------------------------- 00420 00421 protected: 00422 /** 00423 * The nonce used to increment the unique element ids. 00424 */ 00425 mutable MemberHandle<AtomicCounter> m_hAtomicNonce; 00426 00427 /** 00428 * The comparator used to compare logical elements. 00429 */ 00430 MemberView<Comparator> m_vComparator; 00431 00432 /** 00433 * The internal navigable map holding the bag contents. 00434 */ 00435 mutable MemberHandle<NavigableMap> m_hMap; 00436 00437 friend class ViewBag; 00438 }; 00439 00440 00441 // ----- inner class: ViewBag ------------------------------------------- 00442 00443 /** 00444 * A range-limited view of the SortedBag. This view is backed by the 00445 * SortedBag, so any modifications made to it are visible to the underlying 00446 * bag, and vice-versa. 00447 */ 00448 class COH_EXPORT SortedBag::ViewBag 00449 : public class_spec<ViewBag, 00450 extends<SortedBag> > 00451 { 00452 friend class factory<SortedBag::ViewBag>; 00453 00454 // ----- constructors ----------------------------------------------- 00455 00456 protected: 00457 /** 00458 * Construct a view of the SortedBag, constrained to the range [ohFrom, ohTo). 00459 * 00460 * @param ohBag reference to the "outer this" 00461 * @param vFrom the "from" element (inclusive), or null 00462 * @param vTo the "to" element (exclusive), or null 00463 */ 00464 ViewBag(SortedBag::Holder ohBag, Object::View vFrom, Object::View vTo); 00465 00466 00467 // ----- SortedBag methods ------------------------------------------ 00468 00469 public: 00470 /** 00471 * {@inheritDoc} 00472 */ 00473 virtual bool add(Object::Holder oh); 00474 00475 /** 00476 * {@inheritDoc} 00477 */ 00478 virtual SortedBag::Handle subBag(Object::View vFrom, Object::View vTo); 00479 00480 /** 00481 * {@inheritDoc} 00482 */ 00483 virtual SortedBag::View subBag(Object::View vFrom, Object::View vTo) const; 00484 00485 /** 00486 * {@inheritDoc} 00487 */ 00488 virtual SortedBag::Handle headBag(Object::View vTo); 00489 00490 /** 00491 * {@inheritDoc} 00492 */ 00493 virtual SortedBag::View headBag(Object::View vTo) const; 00494 00495 /** 00496 * {@inheritDoc} 00497 */ 00498 virtual SortedBag::Handle tailBag(Object::View vFrom); 00499 00500 /** 00501 * {@inheritDoc} 00502 */ 00503 virtual SortedBag::View tailBag(Object::View vFrom) const; 00504 00505 00506 // ----- helper methods --------------------------------------------- 00507 00508 protected: 00509 /** 00510 * Check that the specified object is within the range of this view. 00511 * 00512 * @param v the object to check 00513 */ 00514 void checkRange(Object::View v) const; 00515 00516 00517 // ----- data members ----------------------------------------------- 00518 00519 protected: 00520 /** 00521 * The "outer this". 00522 */ 00523 FinalHolder<SortedBag> f_ohBag; 00524 00525 /** 00526 * The (inclusive) lower bound of this view. 00527 */ 00528 FinalView<Object> f_vFrom; 00529 00530 /** 00531 * The (exclusive) upper bound of this view. 00532 */ 00533 FinalView<Object> f_vTo; 00534 00535 // ----- friends ---------------------------------------------------- 00536 00537 friend class SortedBag; 00538 }; 00539 00540 COH_CLOSE_NAMESPACE2 00541 00542 #endif // COH_SORTED_BAG_HPP