Panda3D
|
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> ©) : 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> ©) { 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> ©) { 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> ©) : 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> ©) { 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> ©) : 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> ©) { 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 }