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