Panda3D

ordered_vector.I

00001 // Filename: ordered_vector.I
00002 // Created by:  drose (20Feb02)
00003 //
00004 ////////////////////////////////////////////////////////////////////
00005 //
00006 // PANDA 3D SOFTWARE
00007 // Copyright (c) Carnegie Mellon University.  All rights reserved.
00008 //
00009 // All use of this software is subject to the terms of the revised BSD
00010 // license.  You should have received a copy of this license along
00011 // with this source code in a file named "LICENSE."
00012 //
00013 ////////////////////////////////////////////////////////////////////
00014 
00015 
00016 ////////////////////////////////////////////////////////////////////
00017 //     Function: ordered_vector::Constructor
00018 //       Access: Public
00019 //  Description: 
00020 ////////////////////////////////////////////////////////////////////
00021 template<class Key, class Compare>
00022 INLINE ordered_vector<Key, Compare>::
00023 ordered_vector(TypeHandle type_handle) :
00024   _compare(Compare()),
00025   _vector(type_handle)
00026 {
00027 }
00028 
00029 ////////////////////////////////////////////////////////////////////
00030 //     Function: ordered_vector::Constructor
00031 //       Access: Public
00032 //  Description: 
00033 ////////////////////////////////////////////////////////////////////
00034 template<class Key, class Compare>
00035 INLINE ordered_vector<Key, Compare>::
00036 ordered_vector(const Compare &compare, TypeHandle type_handle) :
00037   _compare(compare),
00038   _vector(type_handle)
00039 {
00040 }
00041 
00042 ////////////////////////////////////////////////////////////////////
00043 //     Function: ordered_vector::Copy Constructor
00044 //       Access: Public
00045 //  Description: 
00046 ////////////////////////////////////////////////////////////////////
00047 template<class Key, class Compare>
00048 INLINE ordered_vector<Key, Compare>::
00049 ordered_vector(const ordered_vector<Key, Compare> &copy) :
00050   _compare(copy._compare),
00051   _vector(copy._vector)
00052 {
00053 }
00054 
00055 ////////////////////////////////////////////////////////////////////
00056 //     Function: ordered_vector::Copy Assignment Operator
00057 //       Access: Public
00058 //  Description: 
00059 ////////////////////////////////////////////////////////////////////
00060 template<class Key, class Compare>
00061 INLINE ordered_vector<Key, Compare> &ordered_vector<Key, Compare>::
00062 operator = (const ordered_vector<Key, Compare> &copy) {
00063   _compare = copy._compare;
00064   _vector = copy._vector;
00065   return *this;
00066 }
00067 
00068 ////////////////////////////////////////////////////////////////////
00069 //     Function: ordered_vector::Destructor
00070 //       Access: Public
00071 //  Description: 
00072 ////////////////////////////////////////////////////////////////////
00073 template<class Key, class Compare>
00074 INLINE ordered_vector<Key, Compare>::
00075 ~ordered_vector() {
00076 }
00077 
00078 ////////////////////////////////////////////////////////////////////
00079 //     Function: ordered_vector::begin
00080 //       Access: Public
00081 //  Description: Returns the iterator that marks the first element in
00082 //               the ordered vector.
00083 ////////////////////////////////////////////////////////////////////
00084 template<class Key, class Compare>
00085 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00086 begin() {
00087   return _vector.begin();
00088 }
00089 
00090 ////////////////////////////////////////////////////////////////////
00091 //     Function: ordered_vector::end
00092 //       Access: Public
00093 //  Description: Returns the iterator that marks the end of the
00094 //               ordered vector.
00095 ////////////////////////////////////////////////////////////////////
00096 template<class Key, class Compare>
00097 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00098 end() {
00099   return _vector.end();
00100 }
00101 
00102 ////////////////////////////////////////////////////////////////////
00103 //     Function: ordered_vector::rbegin
00104 //       Access: Public
00105 //  Description: Returns the iterator that marks the first element in
00106 //               the ordered vector, when viewed in reverse order.
00107 ////////////////////////////////////////////////////////////////////
00108 template<class Key, class Compare>
00109 INLINE TYPENAME ordered_vector<Key, Compare>::REVERSE_ITERATOR ordered_vector<Key, Compare>::
00110 rbegin() {
00111   return _vector.rbegin();
00112 }
00113 
00114 ////////////////////////////////////////////////////////////////////
00115 //     Function: ordered_vector::rend
00116 //       Access: Public
00117 //  Description: Returns the iterator that marks the end of the
00118 //               ordered vector, when viewed in reverse order.
00119 ////////////////////////////////////////////////////////////////////
00120 template<class Key, class Compare>
00121 INLINE TYPENAME ordered_vector<Key, Compare>::REVERSE_ITERATOR ordered_vector<Key, Compare>::
00122 rend() {
00123   return _vector.rend();
00124 }
00125 
00126 ////////////////////////////////////////////////////////////////////
00127 //     Function: ordered_vector::begin
00128 //       Access: Public
00129 //  Description: Returns the iterator that marks the first element in
00130 //               the ordered vector.
00131 ////////////////////////////////////////////////////////////////////
00132 template<class Key, class Compare>
00133 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR ordered_vector<Key, Compare>::
00134 begin() const {
00135   return _vector.begin();
00136 }
00137 
00138 ////////////////////////////////////////////////////////////////////
00139 //     Function: ordered_vector::end
00140 //       Access: Public
00141 //  Description: Returns the iterator that marks the end of the
00142 //               ordered vector.
00143 ////////////////////////////////////////////////////////////////////
00144 template<class Key, class Compare>
00145 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR ordered_vector<Key, Compare>::
00146 end() const {
00147   return _vector.end();
00148 }
00149 
00150 ////////////////////////////////////////////////////////////////////
00151 //     Function: ordered_vector::rbegin
00152 //       Access: Public
00153 //  Description: Returns the iterator that marks the first element in
00154 //               the ordered vector, when viewed in reverse order.
00155 ////////////////////////////////////////////////////////////////////
00156 template<class Key, class Compare>
00157 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_REVERSE_ITERATOR ordered_vector<Key, Compare>::
00158 rbegin() const {
00159   return _vector.rbegin();
00160 }
00161 
00162 ////////////////////////////////////////////////////////////////////
00163 //     Function: ordered_vector::rend
00164 //       Access: Public
00165 //  Description: Returns the iterator that marks the end of the
00166 //               ordered vector, when viewed in reverse order.
00167 ////////////////////////////////////////////////////////////////////
00168 template<class Key, class Compare>
00169 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_REVERSE_ITERATOR ordered_vector<Key, Compare>::
00170 rend() const {
00171   return _vector.rend();
00172 }
00173 
00174 ////////////////////////////////////////////////////////////////////
00175 //     Function: ordered_vector::operator []
00176 //       Access: Public
00177 //  Description: Returns the nth element.
00178 ////////////////////////////////////////////////////////////////////
00179 template<class Key, class Compare>
00180 INLINE TYPENAME ordered_vector<Key, Compare>::REFERENCE ordered_vector<Key, Compare>::
00181 operator [] (TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE n) {
00182   return _vector[n];
00183 }
00184 
00185 ////////////////////////////////////////////////////////////////////
00186 //     Function: ordered_vector::operator []
00187 //       Access: Public
00188 //  Description: Returns the nth element.
00189 ////////////////////////////////////////////////////////////////////
00190 template<class Key, class Compare>
00191 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_REFERENCE ordered_vector<Key, Compare>::
00192 operator [] (TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE n) const {
00193   return _vector[n];
00194 }
00195 
00196 ////////////////////////////////////////////////////////////////////
00197 //     Function: ordered_vector::size
00198 //       Access: Public
00199 //  Description: Returns the number of elements in the ordered vector.
00200 ////////////////////////////////////////////////////////////////////
00201 template<class Key, class Compare>
00202 INLINE TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE ordered_vector<Key, Compare>::
00203 size() const {
00204   return _vector.size();
00205 }
00206 
00207 ////////////////////////////////////////////////////////////////////
00208 //     Function: ordered_vector::max_size
00209 //       Access: Public
00210 //  Description: Returns the maximum number of elements that can
00211 //               possibly be stored in an ordered vector.
00212 ////////////////////////////////////////////////////////////////////
00213 template<class Key, class Compare>
00214 INLINE TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE ordered_vector<Key, Compare>::
00215 max_size() const {
00216   return _vector.max_size();
00217 }
00218 
00219 ////////////////////////////////////////////////////////////////////
00220 //     Function: ordered_vector::empty
00221 //       Access: Public
00222 //  Description: Returns true if the ordered vector is empty, false
00223 //               otherwise.
00224 ////////////////////////////////////////////////////////////////////
00225 template<class Key, class Compare>
00226 INLINE bool ordered_vector<Key, Compare>::
00227 empty() const {
00228   return _vector.empty();
00229 }
00230 
00231 ////////////////////////////////////////////////////////////////////
00232 //     Function: ordered_vector::operator == 
00233 //       Access: Public
00234 //  Description: Returns true if the two ordered vectors are
00235 //               memberwise equivalent, false otherwise.
00236 ////////////////////////////////////////////////////////////////////
00237 template<class Key, class Compare>
00238 INLINE bool ordered_vector<Key, Compare>::
00239 operator == (const ordered_vector<Key, Compare> &other) const {
00240   return _vector == other._vector;
00241 }
00242 
00243 ////////////////////////////////////////////////////////////////////
00244 //     Function: ordered_vector::operator != 
00245 //       Access: Public
00246 //  Description: Returns true if the two ordered vectors are not
00247 //               memberwise equivalent, false if they are.
00248 ////////////////////////////////////////////////////////////////////
00249 template<class Key, class Compare>
00250 INLINE bool ordered_vector<Key, Compare>::
00251 operator != (const ordered_vector<Key, Compare> &other) const {
00252   return _vector != other._vector;
00253 }
00254 
00255 ////////////////////////////////////////////////////////////////////
00256 //     Function: ordered_vector::operator <
00257 //       Access: Public
00258 //  Description: Returns true if this ordered vector sorts
00259 //               lexicographically before the other one, false
00260 //               otherwise.
00261 ////////////////////////////////////////////////////////////////////
00262 template<class Key, class Compare>
00263 INLINE bool ordered_vector<Key, Compare>::
00264 operator < (const ordered_vector<Key, Compare> &other) const {
00265   return _vector < other._vector;
00266 }
00267 
00268 ////////////////////////////////////////////////////////////////////
00269 //     Function: ordered_vector::operator >
00270 //       Access: Public
00271 //  Description: Returns true if this ordered vector sorts
00272 //               lexicographically after the other one, false
00273 //               otherwise.
00274 ////////////////////////////////////////////////////////////////////
00275 template<class Key, class Compare>
00276 INLINE bool ordered_vector<Key, Compare>::
00277 operator > (const ordered_vector<Key, Compare> &other) const {
00278   return _vector > other._vector;
00279 }
00280 
00281 ////////////////////////////////////////////////////////////////////
00282 //     Function: ordered_vector::operator <=
00283 //       Access: Public
00284 //  Description: Returns true if this ordered vector sorts
00285 //               lexicographically before the other one or is
00286 //               equivalent, false otherwise.
00287 ////////////////////////////////////////////////////////////////////
00288 template<class Key, class Compare>
00289 INLINE bool ordered_vector<Key, Compare>::
00290 operator <= (const ordered_vector<Key, Compare> &other) const {
00291   return _vector <= other._vector;
00292 }
00293 
00294 ////////////////////////////////////////////////////////////////////
00295 //     Function: ordered_vector::operator >=
00296 //       Access: Public
00297 //  Description: Returns true if this ordered vector sorts
00298 //               lexicographically after the other one or is
00299 //               equivalent, false otherwise.
00300 ////////////////////////////////////////////////////////////////////
00301 template<class Key, class Compare>
00302 INLINE bool ordered_vector<Key, Compare>::
00303 operator >= (const ordered_vector<Key, Compare> &other) const {
00304   return _vector >= other._vector;
00305 }
00306 
00307 
00308 ////////////////////////////////////////////////////////////////////
00309 //     Function: ordered_vector::insert_unique
00310 //       Access: Public
00311 //  Description: Inserts the indicated key into the ordered vector, at
00312 //               the appropriate place.  If there is already an element
00313 //               sorting equivalent to the key in the vector, the new
00314 //               key is not inserted.
00315 //
00316 //               The return value is a pair, where the first component
00317 //               is the iterator referencing the new element (or the
00318 //               original element), and the second componet is true if
00319 //               the insert operation has taken place.
00320 ////////////////////////////////////////////////////////////////////
00321 template<class Key, class Compare>
00322 INLINE pair<TYPENAME ordered_vector<Key, Compare>::ITERATOR, bool> ordered_vector<Key, Compare>::
00323 insert_unique(const TYPENAME ordered_vector<Key, Compare>::VALUE_TYPE &key) {
00324   TAU_PROFILE("ordered_vector::insert_unique(const value_type &)", " ", TAU_USER);
00325   ITERATOR position = find_insert_position(begin(), end(), key);
00326 #ifdef NDEBUG
00327   pair<ITERATOR, bool> bogus_result(end(), false);
00328   nassertr(position >= begin() && position <= end(), bogus_result);
00329 #endif
00330 
00331   // If there's already an equivalent key in the vector, it's at
00332   // *(position - 1).
00333   if (position != begin() && !_compare(*(position - 1), key)) {
00334     pair<ITERATOR, bool> result(position - 1, false);
00335     nassertr(!_compare(key, *(position - 1)), result);
00336     return result;
00337   }
00338 
00339   ITERATOR result = _vector.insert(position, key);
00340   return pair<ITERATOR, bool>(result, true);
00341 }
00342 
00343 ////////////////////////////////////////////////////////////////////
00344 //     Function: ordered_vector::insert_nonunique
00345 //       Access: Public
00346 //  Description: Inserts the indicated key into the ordered vector, at
00347 //               the appropriate place.  If there are already elements
00348 //               sorting equivalent to the key in the vector, the new
00349 //               value is inserted following them.  
00350 //
00351 //               The return value is the iterator referencing the new
00352 //               element.
00353 ////////////////////////////////////////////////////////////////////
00354 template<class Key, class Compare>
00355 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00356 insert_nonunique(const TYPENAME ordered_vector<Key, Compare>::VALUE_TYPE &key) {
00357   TAU_PROFILE("ordered_vector::insert_nonunique(const value_type &)", " ", TAU_USER);
00358   ITERATOR position = find_insert_position(begin(), end(), key);
00359   nassertr(position >= begin() && position <= end(), end());
00360 
00361   ITERATOR result = _vector.insert(position, key);
00362   return result;
00363 }
00364 
00365 
00366 ////////////////////////////////////////////////////////////////////
00367 //     Function: ordered_vector::insert_unverified
00368 //       Access: Public
00369 //  Description: Inserts the indicated key into the ordered vector at
00370 //               the indicated place.  The user is trusted to have
00371 //               already verified that this is the correct sorting
00372 //               position; no checks are made.
00373 ////////////////////////////////////////////////////////////////////
00374 template<class Key, class Compare>
00375 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00376 insert_unverified(TYPENAME ordered_vector<Key, Compare>::ITERATOR position, 
00377                   const TYPENAME ordered_vector<Key, Compare>::VALUE_TYPE &key) {
00378   TAU_PROFILE("ordered_vector::insert_unverified(iterator, const value_type &)", " ", TAU_USER);
00379   ITERATOR result = _vector.insert(position, key);
00380   return result;
00381 }
00382 
00383 ////////////////////////////////////////////////////////////////////
00384 //     Function: ordered_vector::erase, with iterator
00385 //       Access: Public
00386 //  Description: Removes the element indicated by the given iterator,
00387 //               and returns the next sequential iterator.
00388 ////////////////////////////////////////////////////////////////////
00389 template<class Key, class Compare>
00390 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00391 erase(TYPENAME ordered_vector<Key, Compare>::ITERATOR position) {
00392   TAU_PROFILE("ordered_vector::erase(iterator)", " ", TAU_USER);
00393   SIZE_TYPE count = position - begin();
00394   _vector.erase(position);
00395   return begin() + count;
00396 }
00397 
00398 ////////////////////////////////////////////////////////////////////
00399 //     Function: ordered_vector::erase, with key
00400 //       Access: Public
00401 //  Description: Removes all elements matching the indicated key;
00402 //               returns the number of elements removed.
00403 ////////////////////////////////////////////////////////////////////
00404 template<class Key, class Compare>
00405 INLINE TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE ordered_vector<Key, Compare>::
00406 erase(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00407   TAU_PROFILE("ordered_vector::erase(const key_type &)", " ", TAU_USER);
00408   pair<ITERATOR, ITERATOR> result = equal_range(key);
00409   SIZE_TYPE count = result.second - result.first;
00410   erase(result.first, result.second);
00411   return count;
00412 }
00413 
00414 ////////////////////////////////////////////////////////////////////
00415 //     Function: ordered_vector::erase, a range
00416 //       Access: Public
00417 //  Description: Removes all elements indicated by the given iterator
00418 //               range.
00419 ////////////////////////////////////////////////////////////////////
00420 template<class Key, class Compare>
00421 INLINE void ordered_vector<Key, Compare>::
00422 erase(TYPENAME ordered_vector<Key, Compare>::ITERATOR first,
00423       TYPENAME ordered_vector<Key, Compare>::ITERATOR last) {
00424   TAU_PROFILE("ordered_vector::erase(iterator, iterator)", " ", TAU_USER);
00425   _vector.erase(first, last);
00426 }
00427 
00428 ////////////////////////////////////////////////////////////////////
00429 //     Function: ordered_vector::clear
00430 //       Access: Public
00431 //  Description: Removes all elements from the ordered vector.
00432 ////////////////////////////////////////////////////////////////////
00433 template<class Key, class Compare>
00434 INLINE void ordered_vector<Key, Compare>::
00435 clear() {
00436   TAU_PROFILE("ordered_vector::clear()", " ", TAU_USER);
00437   _vector.erase(_vector.begin(), _vector.end());
00438 }
00439 
00440 ////////////////////////////////////////////////////////////////////
00441 //     Function: ordered_vector::find
00442 //       Access: Public
00443 //  Description: Searches for an element with the indicated key and
00444 //               returns its iterator if it is found, or end() if it
00445 //               is not.  If there are multiple elements matching the
00446 //               key, the particular iterator returned is not defined.
00447 ////////////////////////////////////////////////////////////////////
00448 template<class Key, class Compare>
00449 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00450 find(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00451   TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
00452   return nci(r_find(begin(), end(), end(), key));
00453 }
00454 
00455 ////////////////////////////////////////////////////////////////////
00456 //     Function: ordered_vector::find
00457 //       Access: Public
00458 //  Description: Searches for an element with the indicated key and
00459 //               returns its iterator if it is found, or end() if it
00460 //               is not.  If there are multiple elements matching the
00461 //               key, the particular iterator returned is not defined.
00462 ////////////////////////////////////////////////////////////////////
00463 template<class Key, class Compare>
00464 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR ordered_vector<Key, Compare>::
00465 find(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) const {
00466   TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
00467   return r_find(begin(), end(), end(), key);
00468 }
00469 
00470 ////////////////////////////////////////////////////////////////////
00471 //     Function: ordered_vector::find_particular
00472 //       Access: Public
00473 //  Description: Searches for a particular element and returns its
00474 //               iterator if it is found, or end() if it is not.
00475 //
00476 //               First, the Compare function is used to narrow down
00477 //               the range of elements the element might be located
00478 //               within; then the element is compared elementwise, via
00479 //               ==, until the exact matching element is found.  If
00480 //               multiple matches exist within the vector, the
00481 //               particular iterator returned is not defined.
00482 //
00483 //               The assumption is that == implies !Compare(a, b) and
00484 //               !Compare(b, a), but not necessarily the converse.
00485 ////////////////////////////////////////////////////////////////////
00486 template<class Key, class Compare>
00487 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00488 find_particular(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00489   TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
00490   return nci(r_find_particular(begin(), end(), end(), key));
00491 }
00492 
00493 ////////////////////////////////////////////////////////////////////
00494 //     Function: ordered_vector::find_particular
00495 //       Access: Public
00496 //  Description: Searches for a particular element and returns its
00497 //               iterator if it is found, or end() if it is not.
00498 //
00499 //               First, the Compare function is used to narrow down
00500 //               the range of elements the element might be located
00501 //               within; then the element is compared elementwise, via
00502 //               ==, until the exact matching element is found.  If
00503 //               multiple matches exist within the vector, the
00504 //               particular iterator returned is not defined./
00505 ////////////////////////////////////////////////////////////////////
00506 template<class Key, class Compare>
00507 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR ordered_vector<Key, Compare>::
00508 find_particular(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) const {
00509   TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
00510   return r_find_particular(begin(), end(), end(), key);
00511 }
00512 
00513 ////////////////////////////////////////////////////////////////////
00514 //     Function: ordered_vector::count
00515 //       Access: Public
00516 //  Description: Returns the number of elements that sort equivalent
00517 //               to the key that are in the vector.
00518 ////////////////////////////////////////////////////////////////////
00519 template<class Key, class Compare>
00520 INLINE TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE ordered_vector<Key, Compare>::
00521 count(const key_type &key) const {
00522   TAU_PROFILE("ordered_vector::count(const key_type &)", " ", TAU_USER);
00523   return r_count(begin(), end(), key);
00524 }
00525 
00526 ////////////////////////////////////////////////////////////////////
00527 //     Function: ordered_vector::lower_bound
00528 //       Access: Public
00529 //  Description: Returns the iterator for the first element not less
00530 //               than key, or end() if all elements are less than key.
00531 ////////////////////////////////////////////////////////////////////
00532 template<class Key, class Compare>
00533 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00534 lower_bound(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00535   TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
00536   return nci(r_lower_bound(begin(), end(), key));
00537 }
00538 
00539 ////////////////////////////////////////////////////////////////////
00540 //     Function: ordered_vector::lower_bound
00541 //       Access: Public
00542 //  Description: Returns the iterator for the first element not less
00543 //               than key, or end() if all elements are less than key.
00544 ////////////////////////////////////////////////////////////////////
00545 template<class Key, class Compare>
00546 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR ordered_vector<Key, Compare>::
00547 lower_bound(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) const {
00548   TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
00549   return r_lower_bound(begin(), end(), key);
00550 }
00551 
00552 ////////////////////////////////////////////////////////////////////
00553 //     Function: ordered_vector::upper_bound
00554 //       Access: Public
00555 //  Description: Returns the iterator for the first element greater
00556 //               than key, or end() if no element is greater than
00557 //               key.
00558 ////////////////////////////////////////////////////////////////////
00559 template<class Key, class Compare>
00560 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00561 upper_bound(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00562   TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
00563   return nci(r_upper_bound(begin(), end(), key));
00564 }
00565 
00566 ////////////////////////////////////////////////////////////////////
00567 //     Function: ordered_vector::upper_bound
00568 //       Access: Public
00569 //  Description: Returns the iterator for the first element greater
00570 //               than key, or end() if no element is greater than
00571 //               key.
00572 ////////////////////////////////////////////////////////////////////
00573 template<class Key, class Compare>
00574 INLINE TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR ordered_vector<Key, Compare>::
00575 upper_bound(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) const {
00576   TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
00577   return r_upper_bound(begin(), end(), key);
00578 }
00579 
00580 ////////////////////////////////////////////////////////////////////
00581 //     Function: ordered_vector::equal_range
00582 //       Access: Public
00583 //  Description: Returns the pair (lower_bound(key), upper_bound(key)).
00584 ////////////////////////////////////////////////////////////////////
00585 template<class Key, class Compare>
00586 INLINE pair<TYPENAME ordered_vector<Key, Compare>::ITERATOR, TYPENAME ordered_vector<Key, Compare>::ITERATOR> ordered_vector<Key, Compare>::
00587 equal_range(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00588   TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
00589   pair<TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR, TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR> result;
00590   result = r_equal_range(begin(), end(), key);
00591   return pair<TYPENAME ordered_vector<Key, Compare>::ITERATOR, TYPENAME ordered_vector<Key, Compare>::ITERATOR>(nci(result.first), nci(result.second));
00592 }
00593 
00594 ////////////////////////////////////////////////////////////////////
00595 //     Function: ordered_vector::equal_range
00596 //       Access: Public
00597 //  Description: Returns the pair (lower_bound(key), upper_bound(key)).
00598 ////////////////////////////////////////////////////////////////////
00599 template<class Key, class Compare>
00600 INLINE pair<TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR, TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR> ordered_vector<Key, Compare>::
00601 equal_range(const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) const {
00602   TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
00603   return r_equal_range(begin(), end(), key);
00604 }
00605 
00606 ////////////////////////////////////////////////////////////////////
00607 //     Function: ordered_vector::swap
00608 //       Access: Public
00609 //  Description: Exchanges the contents of this vector and the other
00610 //               vector, in constant time (e.g., with a pointer swap).
00611 ////////////////////////////////////////////////////////////////////
00612 template<class Key, class Compare>
00613 INLINE void ordered_vector<Key, Compare>::
00614 swap(ordered_vector<Key, Compare> &copy) {
00615   TAU_PROFILE("ordered_vector::swap(ordered_vector &)", " ", TAU_USER);
00616   _vector.swap(copy._vector);
00617 }
00618 
00619 ////////////////////////////////////////////////////////////////////
00620 //     Function: ordered_vector::reserve
00621 //       Access: Public
00622 //  Description: Informs the vector of a planned change in size;
00623 //               ensures that the capacity of the vector is greater
00624 //               than or equal to n.
00625 ////////////////////////////////////////////////////////////////////
00626 template<class Key, class Compare>
00627 INLINE void ordered_vector<Key, Compare>::
00628 reserve(TYPENAME ordered_vector<Key, Compare>::SIZE_TYPE n) {
00629   TAU_PROFILE("ordered_vector::reserve(size_type)", " ", TAU_USER);
00630   _vector.reserve(n);
00631 }
00632 
00633 ////////////////////////////////////////////////////////////////////
00634 //     Function: ordered_vector::sort_unique
00635 //       Access: Public
00636 //  Description: Ensures that the vector is properly sorted after a
00637 //               potentially damaging operation.  This should not
00638 //               normally need to be called, unless the user has
00639 //               written to the vector using the non-const iterators
00640 //               or has called push_back().
00641 //
00642 //               This flavor of sort also eliminates repeated
00643 //               elements.
00644 ////////////////////////////////////////////////////////////////////
00645 template<class Key, class Compare>
00646 INLINE void ordered_vector<Key, Compare>::
00647 sort_unique() {
00648   TAU_PROFILE("ordered_vector::sort_unique()", " ", TAU_USER);
00649   sort(begin(), end(), _compare);
00650   iterator new_end = unique(begin(), end(), EquivalentTest(_compare));
00651   erase(new_end, end());
00652 }
00653 
00654 ////////////////////////////////////////////////////////////////////
00655 //     Function: ordered_vector::sort_nonunique
00656 //       Access: Public
00657 //  Description: Ensures that the vector is properly sorted after a
00658 //               potentially damaging operation.  This should not
00659 //               normally need to be called, unless the user has
00660 //               written to the vector using the non-const iterators
00661 //               or has called push_back().
00662 ////////////////////////////////////////////////////////////////////
00663 template<class Key, class Compare>
00664 INLINE void ordered_vector<Key, Compare>::
00665 sort_nonunique() {
00666   TAU_PROFILE("ordered_vector::sort_nonunique()", " ", TAU_USER);
00667   stable_sort(begin(), end(), _compare);
00668 }
00669 
00670 ////////////////////////////////////////////////////////////////////
00671 //     Function: ordered_vector::push_back
00672 //       Access: Public
00673 //  Description: Adds the new element to the end of the vector without
00674 //               regard for proper sorting.  This is a bad idea to do
00675 //               except to populate the vector the first time; be sure
00676 //               to call sort() after you have added all the elements.
00677 ////////////////////////////////////////////////////////////////////
00678 template<class Key, class Compare>
00679 INLINE void ordered_vector<Key, Compare>::
00680 push_back(const value_type &key) {
00681   TAU_PROFILE("ordered_vector::push_back()", " ", TAU_USER);
00682   _vector.push_back(key);
00683 }
00684 
00685 ////////////////////////////////////////////////////////////////////
00686 //     Function: ordered_vector::pop_back
00687 //       Access: Public
00688 //  Description: Removes the last element at the end of the vector.
00689 ////////////////////////////////////////////////////////////////////
00690 template<class Key, class Compare>
00691 INLINE void ordered_vector<Key, Compare>::
00692 pop_back() {
00693   TAU_PROFILE("ordered_vector::pop_back()", " ", TAU_USER);
00694   _vector.pop_back();
00695 }
00696 
00697 ////////////////////////////////////////////////////////////////////
00698 //     Function: ordered_vector::nci
00699 //       Access: Private
00700 //  Description: I.e. "non-const iterator".  This function is used to
00701 //               typecast a const iterator to a non-const iterator for
00702 //               easy definition of const vs. non-const flavors of
00703 //               some of these methods.
00704 ////////////////////////////////////////////////////////////////////
00705 template<class Key, class Compare>
00706 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00707 nci(TYPENAME ordered_vector<Key, Compare>::CONST_ITERATOR i) {
00708   return begin() + (i - begin());
00709 }
00710 
00711 ////////////////////////////////////////////////////////////////////
00712 //     Function: ordered_vector::find_insert_position
00713 //       Access: Private
00714 //  Description: Searches for the appropriate place in the ordered
00715 //               vector to insert the indicated key, and returns the
00716 //               corresponding iterator.
00717 ////////////////////////////////////////////////////////////////////
00718 template<class Key, class Compare>
00719 INLINE TYPENAME ordered_vector<Key, Compare>::ITERATOR ordered_vector<Key, Compare>::
00720 find_insert_position(TYPENAME ordered_vector<Key, Compare>::ITERATOR first,
00721                      TYPENAME ordered_vector<Key, Compare>::ITERATOR last,
00722                      const TYPENAME ordered_vector<Key, Compare>::KEY_TYPE &key) {
00723   ITERATOR result = r_find_insert_position(first, last, key);
00724   return result;
00725 }
00726 
00727 ////////////////////////////////////////////////////////////////////
00728 //     Function: ov_set::Constructor
00729 //       Access: Public
00730 //  Description: 
00731 ////////////////////////////////////////////////////////////////////
00732 template<class Key, class Compare>
00733 INLINE ov_set<Key, Compare>::
00734 ov_set(TypeHandle type_handle) :
00735   ordered_vector<Key, Compare>(type_handle)
00736 {
00737 }
00738 
00739 ////////////////////////////////////////////////////////////////////
00740 //     Function: ov_set::Constructor
00741 //       Access: Public
00742 //  Description: 
00743 ////////////////////////////////////////////////////////////////////
00744 template<class Key, class Compare>
00745 INLINE ov_set<Key, Compare>::
00746 ov_set(const Compare &compare, TypeHandle type_handle) :
00747   ordered_vector<Key, Compare>(compare, type_handle)
00748 {
00749 }
00750 
00751 ////////////////////////////////////////////////////////////////////
00752 //     Function: ov_set::Copy Constructor
00753 //       Access: Public
00754 //  Description: 
00755 ////////////////////////////////////////////////////////////////////
00756 template<class Key, class Compare>
00757 INLINE ov_set<Key, Compare>::
00758 ov_set(const ov_set<Key, Compare> &copy) :
00759   ordered_vector<Key, Compare>(copy)
00760 {
00761 }
00762 
00763 ////////////////////////////////////////////////////////////////////
00764 //     Function: ov_set::Copy Assignment Operator
00765 //       Access: Public
00766 //  Description: 
00767 ////////////////////////////////////////////////////////////////////
00768 template<class Key, class Compare>
00769 INLINE ov_set<Key, Compare> &ov_set<Key, Compare>::
00770 operator = (const ov_set<Key, Compare> &copy) {
00771   ordered_vector<Key, Compare>::operator = (copy);
00772   return *this;
00773 }
00774 
00775 ////////////////////////////////////////////////////////////////////
00776 //     Function: ov_set::insert
00777 //       Access: Public
00778 //  Description: Maps to insert_unique().
00779 ////////////////////////////////////////////////////////////////////
00780 template<class Key, class Compare>
00781 TYPENAME ov_set<Key, Compare>::ITERATOR ov_set<Key, Compare>::
00782 insert(TYPENAME ov_set<Key, Compare>::ITERATOR position, 
00783        const TYPENAME ov_set<Key, Compare>::VALUE_TYPE &key) {
00784   return ordered_vector<Key, Compare>::insert_unique(position, key);
00785 }
00786 
00787 ////////////////////////////////////////////////////////////////////
00788 //     Function: ov_set::insert
00789 //       Access: Public
00790 //  Description: Maps to insert_unique().
00791 ////////////////////////////////////////////////////////////////////
00792 template<class Key, class Compare>
00793 INLINE pair<TYPENAME ov_set<Key, Compare>::ITERATOR, bool> ov_set<Key, Compare>::
00794 insert(const TYPENAME ov_set<Key, Compare>::VALUE_TYPE &key) {
00795   return ordered_vector<Key, Compare>::insert_unique(key);
00796 }
00797 
00798 ////////////////////////////////////////////////////////////////////
00799 //     Function: ov_set::sort
00800 //       Access: Public
00801 //  Description: Maps to sort_unique().
00802 ////////////////////////////////////////////////////////////////////
00803 template<class Key, class Compare>
00804 INLINE void ov_set<Key, Compare>::
00805 sort() {
00806   ordered_vector<Key, Compare>::sort_unique();
00807 }
00808 
00809 ////////////////////////////////////////////////////////////////////
00810 //     Function: ov_set::verify_list
00811 //       Access: Public
00812 //  Description: Maps to verify_list_unique().
00813 ////////////////////////////////////////////////////////////////////
00814 template<class Key, class Compare>
00815 INLINE bool ov_set<Key, Compare>::
00816 verify_list() const {
00817   return ordered_vector<Key, Compare>::verify_list_unique();
00818 }
00819 
00820 ////////////////////////////////////////////////////////////////////
00821 //     Function: ov_multiset::Constructor
00822 //       Access: Public
00823 //  Description: 
00824 ////////////////////////////////////////////////////////////////////
00825 template<class Key, class Compare>
00826 INLINE ov_multiset<Key, Compare>::
00827 ov_multiset(TypeHandle type_handle) :
00828   ordered_vector<Key, Compare>(type_handle)
00829 {
00830 }
00831 
00832 ////////////////////////////////////////////////////////////////////
00833 //     Function: ov_multiset::Constructor
00834 //       Access: Public
00835 //  Description: 
00836 ////////////////////////////////////////////////////////////////////
00837 template<class Key, class Compare>
00838 INLINE ov_multiset<Key, Compare>::
00839 ov_multiset(const Compare &compare, TypeHandle type_handle) :
00840   ordered_vector<Key, Compare>(compare, type_handle)
00841 {
00842 }
00843 
00844 ////////////////////////////////////////////////////////////////////
00845 //     Function: ov_multiset::Copy Constructor
00846 //       Access: Public
00847 //  Description: 
00848 ////////////////////////////////////////////////////////////////////
00849 template<class Key, class Compare>
00850 INLINE ov_multiset<Key, Compare>::
00851 ov_multiset(const ov_multiset<Key, Compare> &copy) :
00852   ordered_vector<Key, Compare>(copy)
00853 {
00854 }
00855 
00856 ////////////////////////////////////////////////////////////////////
00857 //     Function: ov_multiset::Copy Assignment Operator
00858 //       Access: Public
00859 //  Description: 
00860 ////////////////////////////////////////////////////////////////////
00861 template<class Key, class Compare>
00862 INLINE ov_multiset<Key, Compare> &ov_multiset<Key, Compare>::
00863 operator = (const ov_multiset<Key, Compare> &copy) {
00864   ordered_vector<Key, Compare>::operator = (copy);
00865   return *this;
00866 }
00867 
00868 ////////////////////////////////////////////////////////////////////
00869 //     Function: ov_multiset::insert
00870 //       Access: Public
00871 //  Description: Maps to insert_nonunique().
00872 ////////////////////////////////////////////////////////////////////
00873 template<class Key, class Compare>
00874 TYPENAME ov_multiset<Key, Compare>::ITERATOR ov_multiset<Key, Compare>::
00875 insert(TYPENAME ov_multiset<Key, Compare>::ITERATOR position, 
00876        const TYPENAME ov_multiset<Key, Compare>::VALUE_TYPE &key) {
00877   return ordered_vector<Key, Compare>::insert_nonunique(position, key);
00878 }
00879 
00880 ////////////////////////////////////////////////////////////////////
00881 //     Function: ov_multiset::insert
00882 //       Access: Public
00883 //  Description: Maps to insert_nonunique().
00884 ////////////////////////////////////////////////////////////////////
00885 template<class Key, class Compare>
00886 INLINE TYPENAME ov_multiset<Key, Compare>::ITERATOR ov_multiset<Key, Compare>::
00887 insert(const TYPENAME ov_multiset<Key, Compare>::VALUE_TYPE &key) {
00888   return ordered_vector<Key, Compare>::insert_nonunique(key);
00889 }
00890 
00891 ////////////////////////////////////////////////////////////////////
00892 //     Function: ov_multiset::sort
00893 //       Access: Public
00894 //  Description: Maps to sort_nonunique().
00895 ////////////////////////////////////////////////////////////////////
00896 template<class Key, class Compare>
00897 INLINE void ov_multiset<Key, Compare>::
00898 sort() {
00899   ordered_vector<Key, Compare>::sort_nonunique();
00900 }
00901 
00902 ////////////////////////////////////////////////////////////////////
00903 //     Function: ov_multiset::verify_list
00904 //       Access: Public
00905 //  Description: Maps to verify_list_nonunique().
00906 ////////////////////////////////////////////////////////////////////
00907 template<class Key, class Compare>
00908 INLINE bool ov_multiset<Key, Compare>::
00909 verify_list() const {
00910   return ordered_vector<Key, Compare>::verify_list_nonunique();
00911 }
 All Classes Functions Variables Enumerations