Panda3D
Loading...
Searching...
No Matches
ordered_vector.I
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file ordered_vector.I
10 * @author drose
11 * @date 2002-02-20
12 */
13
14/**
15 *
16 */
17template<class Key, class Compare, class Vector>
19ordered_vector(TypeHandle type_handle) :
20 _compare(Compare()),
21 _vector(type_handle)
22{
23}
24
25/**
26 *
27 */
28template<class Key, class Compare, class Vector>
30ordered_vector(const Compare &compare, TypeHandle type_handle) :
31 _compare(compare),
32 _vector(type_handle)
33{
34}
35
36/**
37 * Returns the iterator that marks the first element in the ordered vector.
38 */
39template<class Key, class Compare, class Vector>
44
45/**
46 * Returns the iterator that marks the end of the ordered vector.
47 */
48template<class Key, class Compare, class Vector>
53
54/**
55 * Returns the iterator that marks the first element in the ordered vector,
56 * when viewed in reverse order.
57 */
58template<class Key, class Compare, class Vector>
63
64/**
65 * Returns the iterator that marks the end of the ordered vector, when viewed
66 * in reverse order.
67 */
68template<class Key, class Compare, class Vector>
73
74/**
75 * Returns the iterator that marks the first element in the ordered vector.
76 */
77template<class Key, class Compare, class Vector>
82
83/**
84 * Returns the iterator that marks the end of the ordered vector.
85 */
86template<class Key, class Compare, class Vector>
91
92/**
93 * Returns the iterator that marks the first element in the ordered vector,
94 * when viewed in reverse order.
95 */
96template<class Key, class Compare, class Vector>
101
102/**
103 * Returns the iterator that marks the end of the ordered vector, when viewed
104 * in reverse order.
105 */
106template<class Key, class Compare, class Vector>
111
112/**
113 * Returns the iterator that marks the first element in the ordered vector.
114 */
115template<class Key, class Compare, class Vector>
120
121/**
122 * Returns the iterator that marks the end of the ordered vector.
123 */
124template<class Key, class Compare, class Vector>
129
130/**
131 * Returns the iterator that marks the first element in the ordered vector,
132 * when viewed in reverse order.
133 */
134template<class Key, class Compare, class Vector>
139
140/**
141 * Returns the iterator that marks the end of the ordered vector, when viewed
142 * in reverse order.
143 */
144template<class Key, class Compare, class Vector>
146crend() const {
147 return _vector.rend();
149
150/**
151 * Returns the nth element.
152 */
153template<class Key, class Compare, class Vector>
156 return _vector[n];
157}
158
159/**
160 * Returns the nth element.
161 */
162template<class Key, class Compare, class Vector>
165 return _vector[n];
168/**
169 * Returns a reference to the first element.
170 */
171template<class Key, class Compare, class Vector>
173front() {
174#ifdef _DEBUG
175 assert(!_vector.empty());
176#endif
177 return _vector[0];
178}
179
180/**
181 * Returns a const reference to the first element.
182 */
183template<class Key, class Compare, class Vector>
185front() const {
186#ifdef _DEBUG
187 assert(!_vector.empty());
188#endif
189 return _vector[0];
191
192/**
193 * Returns a reference to the first element.
194 */
195template<class Key, class Compare, class Vector>
198#ifdef _DEBUG
199 assert(!_vector.empty());
200#endif
201 return _vector[_vector.size() - 1];
202}
203
204/**
205 * Returns a const reference to the last element.
206 */
207template<class Key, class Compare, class Vector>
209back() const {
210#ifdef _DEBUG
211 assert(!_vector.empty());
212#endif
213 return _vector[_vector.size() - 1];
216/**
217 * Returns the number of elements in the ordered vector.
218 */
219template<class Key, class Compare, class Vector>
224
225/**
226 * Returns the maximum number of elements that can possibly be stored in an
227 * ordered vector.
228 */
229template<class Key, class Compare, class Vector>
234
235/**
236 * Returns true if the ordered vector is empty, false otherwise.
237 */
238template<class Key, class Compare, class Vector>
240empty() const {
241 return _vector.empty();
242}
243
244/**
245 * Returns true if the two ordered vectors are memberwise equivalent, false
246 * otherwise.
247 */
248template<class Key, class Compare, class Vector>
251 return _vector == other._vector;
252}
253
254/**
255 * Returns true if the two ordered vectors are not memberwise equivalent,
256 * false if they are.
257 */
258template<class Key, class Compare, class Vector>
261 return _vector != other._vector;
262}
263
264/**
265 * Returns true if this ordered vector sorts lexicographically before the
266 * other one, false otherwise.
267 */
268template<class Key, class Compare, class Vector>
271 return _vector < other._vector;
272}
273
274/**
275 * Returns true if this ordered vector sorts lexicographically after the other
276 * one, false otherwise.
277 */
278template<class Key, class Compare, class Vector>
281 return _vector > other._vector;
283
284/**
285 * Returns true if this ordered vector sorts lexicographically before the
286 * other one or is equivalent, false otherwise.
287 */
288template<class Key, class Compare, class Vector>
291 return _vector <= other._vector;
292}
293
294/**
295 * Returns true if this ordered vector sorts lexicographically after the other
296 * one or is equivalent, false otherwise.
297 */
298template<class Key, class Compare, class Vector>
301 return _vector >= other._vector;
302}
303
304
305/**
306 * Inserts the indicated key into the ordered vector, at the appropriate
307 * place. If there is already an element sorting equivalent to the key in the
308 * vector, the new key is not inserted.
309 *
310 * The return value is a pair, where the first component is the iterator
311 * referencing the new element (or the original element), and the second
312 * componet is true if the insert operation has taken place.
313 */
314template<class Key, class Compare, class Vector>
315INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, bool> ordered_vector<Key, Compare, Vector>::
317 TAU_PROFILE("ordered_vector::insert_unique(const value_type &)", " ", TAU_USER);
318 ITERATOR position = find_insert_position(begin(), end(), key);
319#ifdef NDEBUG
320 std::pair<ITERATOR, bool> bogus_result(end(), false);
321 nassertr(position >= begin() && position <= end(), bogus_result);
322#endif
323
324 // If there's already an equivalent key in the vector, it's at *(position -
325 // 1).
326 if (position != begin() && !_compare(*(position - 1), key)) {
327 std::pair<ITERATOR, bool> result(position - 1, false);
328 nassertr(!_compare(key, *(position - 1)), result);
329 return result;
330 }
331
332 ITERATOR result = _vector.insert(position, key);
333 return std::pair<ITERATOR, bool>(result, true);
334}
335
336/**
337 * Inserts the indicated key into the ordered vector, at the appropriate
338 * place. If there are already elements sorting equivalent to the key in the
339 * vector, the new value is inserted following them.
340 *
341 * The return value is the iterator referencing the new element.
342 */
343template<class Key, class Compare, class Vector>
346 TAU_PROFILE("ordered_vector::insert_nonunique(const value_type &)", " ", TAU_USER);
347 ITERATOR position = find_insert_position(begin(), end(), key);
348 nassertr(position >= begin() && position <= end(), end());
349
350 ITERATOR result = _vector.insert(position, key);
351 return result;
352}
353
354
355/**
356 * Inserts the indicated key into the ordered vector at the indicated place.
357 * The user is trusted to have already verified that this is the correct
358 * sorting position; no checks are made.
359 */
360template<class Key, class Compare, class Vector>
364 TAU_PROFILE("ordered_vector::insert_unverified(iterator, const value_type &)", " ", TAU_USER);
365 ITERATOR result = _vector.insert(position, key);
366 return result;
367}
368
369/**
370 * Removes the element indicated by the given iterator, and returns the next
371 * sequential iterator.
372 */
373template<class Key, class Compare, class Vector>
376 TAU_PROFILE("ordered_vector::erase(iterator)", " ", TAU_USER);
377 SIZE_TYPE count = position - begin();
378 _vector.erase(position);
379 return begin() + count;
380}
381
382/**
383 * Removes all elements matching the indicated key; returns the number of
384 * elements removed.
385 */
386template<class Key, class Compare, class Vector>
389 TAU_PROFILE("ordered_vector::erase(const key_type &)", " ", TAU_USER);
390 std::pair<ITERATOR, ITERATOR> result = equal_range(key);
391 SIZE_TYPE count = result.second - result.first;
392 erase(result.first, result.second);
393 return count;
394}
395
396/**
397 * Removes all elements indicated by the given iterator range.
398 */
399template<class Key, class Compare, class Vector>
403 TAU_PROFILE("ordered_vector::erase(iterator, iterator)", " ", TAU_USER);
404 _vector.erase(first, last);
405}
406
407/**
408 * Removes all elements from the ordered vector.
409 */
410template<class Key, class Compare, class Vector>
412clear() {
413 TAU_PROFILE("ordered_vector::clear()", " ", TAU_USER);
414 _vector.erase(_vector.begin(), _vector.end());
415}
416
417/**
418 * Searches for an element with the indicated key and returns its iterator if
419 * it is found, or end() if it is not. If there are multiple elements
420 * matching the key, the particular iterator returned is not defined.
421 */
422template<class Key, class Compare, class Vector>
425 TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
426 return nci(r_find(begin(), end(), end(), key));
427}
428
429/**
430 * Searches for an element with the indicated key and returns its iterator if
431 * it is found, or end() if it is not. If there are multiple elements
432 * matching the key, the particular iterator returned is not defined.
433 */
434template<class Key, class Compare, class Vector>
436find(const typename ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
437 TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
438 return r_find(begin(), end(), end(), key);
439}
440
441/**
442 * Searches for a particular element and returns its iterator if it is found,
443 * or end() if it is not.
444 *
445 * First, the Compare function is used to narrow down the range of elements
446 * the element might be located within; then the element is compared
447 * elementwise, via ==, until the exact matching element is found. If
448 * multiple matches exist within the vector, the particular iterator returned
449 * is not defined.
450 *
451 * The assumption is that == implies !Compare(a, b) and !Compare(b, a), but
452 * not necessarily the converse.
453 */
454template<class Key, class Compare, class Vector>
457 TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
458 return nci(r_find_particular(begin(), end(), end(), key));
459}
460
461/**
462 * Searches for a particular element and returns its iterator if it is found,
463 * or end() if it is not.
464 *
465 * First, the Compare function is used to narrow down the range of elements
466 * the element might be located within; then the element is compared
467 * elementwise, via ==, until the exact matching element is found. If
468 * multiple matches exist within the vector, the particular iterator returned
469 * is not defined.
470 */
471template<class Key, class Compare, class Vector>
474 TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
475 return r_find_particular(begin(), end(), end(), key);
476}
477
478/**
479 * Returns the number of elements that sort equivalent to the key that are in
480 * the vector.
481 */
482template<class Key, class Compare, class Vector>
484count(const key_type &key) const {
485 TAU_PROFILE("ordered_vector::count(const key_type &)", " ", TAU_USER);
486 return r_count(begin(), end(), key);
487}
488
489/**
490 * Returns the iterator for the first element not less than key, or end() if
491 * all elements are less than key.
492 */
493template<class Key, class Compare, class Vector>
496 TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
497 return nci(r_lower_bound(begin(), end(), key));
498}
499
500/**
501 * Returns the iterator for the first element not less than key, or end() if
502 * all elements are less than key.
503 */
504template<class Key, class Compare, class Vector>
507 TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
508 return r_lower_bound(begin(), end(), key);
509}
510
511/**
512 * Returns the iterator for the first element greater than key, or end() if no
513 * element is greater than key.
514 */
515template<class Key, class Compare, class Vector>
518 TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
519 return nci(r_upper_bound(begin(), end(), key));
520}
521
522/**
523 * Returns the iterator for the first element greater than key, or end() if no
524 * element is greater than key.
525 */
526template<class Key, class Compare, class Vector>
529 TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
530 return r_upper_bound(begin(), end(), key);
531}
532
533/**
534 * Returns the pair (lower_bound(key), upper_bound(key)).
535 */
536template<class Key, class Compare, class Vector>
537INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, typename ordered_vector<Key, Compare, Vector>::ITERATOR> ordered_vector<Key, Compare, Vector>::
539 TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
540 std::pair<typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR, typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR> result;
541 result = r_equal_range(begin(), end(), key);
542 return std::pair<typename ordered_vector<Key, Compare, Vector>::ITERATOR, typename ordered_vector<Key, Compare, Vector>::ITERATOR>(nci(result.first), nci(result.second));
543}
544
545/**
546 * Returns the pair (lower_bound(key), upper_bound(key)).
547 */
548template<class Key, class Compare, class Vector>
549INLINE std::pair<typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR, typename ordered_vector<Key, Compare, Vector>::CONST_ITERATOR> ordered_vector<Key, Compare, Vector>::
551 TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
552 return r_equal_range(begin(), end(), key);
553}
554
555/**
556 * Exchanges the contents of this vector and the other vector, in constant
557 * time (e.g., with a pointer swap).
558 */
559template<class Key, class Compare, class Vector>
562 TAU_PROFILE("ordered_vector::swap(ordered_vector &)", " ", TAU_USER);
563 _vector.swap(copy._vector);
564}
565
566/**
567 * Informs the vector of a planned change in size; ensures that the capacity
568 * of the vector is greater than or equal to n.
569 */
570template<class Key, class Compare, class Vector>
573 TAU_PROFILE("ordered_vector::reserve(size_type)", " ", TAU_USER);
574 _vector.reserve(n);
575}
576
577/**
578 * Ensures that the vector is properly sorted after a potentially damaging
579 * operation. This should not normally need to be called, unless the user has
580 * written to the vector using the non-const iterators or has called
581 * push_back().
582 *
583 * This flavor of sort also eliminates repeated elements.
584 */
585template<class Key, class Compare, class Vector>
587sort_unique() {
588 TAU_PROFILE("ordered_vector::sort_unique()", " ", TAU_USER);
589 sort(begin(), end(), _compare);
590 iterator new_end = unique(begin(), end(), EquivalentTest(_compare));
591 erase(new_end, end());
592}
593
594/**
595 * Ensures that the vector is properly sorted after a potentially damaging
596 * operation. This should not normally need to be called, unless the user has
597 * written to the vector using the non-const iterators or has called
598 * push_back().
599 */
600template<class Key, class Compare, class Vector>
603 TAU_PROFILE("ordered_vector::sort_nonunique()", " ", TAU_USER);
604 std::stable_sort(begin(), end(), _compare);
605}
606
607/**
608 * Adds the new element to the end of the vector without regard for proper
609 * sorting. This is a bad idea to do except to populate the vector the first
610 * time; be sure to call sort() after you have added all the elements.
611 */
612template<class Key, class Compare, class Vector>
614push_back(const value_type &key) {
615 TAU_PROFILE("ordered_vector::push_back()", " ", TAU_USER);
616 _vector.push_back(key);
617}
618
619/**
620 * Adds the new element to the end of the vector without regard for proper
621 * sorting. This is a bad idea to do except to populate the vector the first
622 * time; be sure to call sort() after you have added all the elements.
623 */
624template<class Key, class Compare, class Vector>
626push_back(value_type &&key) {
627 TAU_PROFILE("ordered_vector::push_back()", " ", TAU_USER);
628 _vector.push_back(std::move(key));
629}
630
631/**
632 * Removes the last element at the end of the vector.
633 */
634template<class Key, class Compare, class Vector>
636pop_back() {
637 TAU_PROFILE("ordered_vector::pop_back()", " ", TAU_USER);
638 _vector.pop_back();
639}
640
641/**
642 * Resizes the vector to contain n elements. This should not be used except
643 * to populate the vector for the first time.
644 */
645template<class Key, class Compare, class Vector>
647resize(SIZE_TYPE n) {
648 TAU_PROFILE("ordered_vector::resize()", " ", TAU_USER);
649 _vector.resize(n);
650}
651
652/**
653 * Resizes the vector to contain n elements. This should not be used except
654 * to populate the vector for the first time.
655 */
656template<class Key, class Compare, class Vector>
658resize(SIZE_TYPE n, const VALUE_TYPE &value) {
659 TAU_PROFILE("ordered_vector::resize()", " ", TAU_USER);
660 _vector.resize(n, value);
661}
662
663/**
664 * I.e. "non-const iterator". This function is used to typecast a const
665 * iterator to a non-const iterator for easy definition of const vs. non-
666 * const flavors of some of these methods.
667 */
668template<class Key, class Compare, class Vector>
671 return begin() + (i - begin());
672}
673
674/**
675 * Searches for the appropriate place in the ordered vector to insert the
676 * indicated key, and returns the corresponding iterator.
677 */
678template<class Key, class Compare, class Vector>
683 ITERATOR result = r_find_insert_position(first, last, key);
684 return result;
685}
686
687/**
688 *
689 */
690template<class Key, class Compare, class Vector>
692ov_set(TypeHandle type_handle) :
693 ordered_vector<Key, Compare, Vector>(type_handle)
694{
695}
696
697/**
698 *
699 */
700template<class Key, class Compare, class Vector>
702ov_set(const Compare &compare, TypeHandle type_handle) :
703 ordered_vector<Key, Compare, Vector>(compare, type_handle)
704{
705}
706
707/**
708 * Maps to insert_unique().
709 */
710template<class Key, class Compare, class Vector>
713 const typename ov_set<Key, Compare, Vector>::VALUE_TYPE &key) {
715}
716
717/**
718 * Maps to insert_unique().
719 */
720template<class Key, class Compare, class Vector>
721INLINE std::pair<typename ov_set<Key, Compare, Vector>::ITERATOR, bool> ov_set<Key, Compare, Vector>::
724}
725
726/**
727 * Maps to sort_unique().
728 */
729template<class Key, class Compare, class Vector>
734
735/**
736 * Maps to verify_list_unique().
737 */
738template<class Key, class Compare, class Vector>
743
744/**
745 *
746 */
747template<class Key, class Compare, class Vector>
749ov_multiset(TypeHandle type_handle) :
750 ordered_vector<Key, Compare, Vector>(type_handle)
751{
752}
753
754/**
755 *
756 */
757template<class Key, class Compare, class Vector>
759ov_multiset(const Compare &compare, TypeHandle type_handle) :
760 ordered_vector<Key, Compare, Vector>(compare, type_handle)
761{
762}
763
764/**
765 * Maps to insert_nonunique().
766 */
767template<class Key, class Compare, class Vector>
772}
773
774/**
775 * Maps to insert_nonunique().
776 */
777template<class Key, class Compare, class Vector>
781}
782
783/**
784 * Maps to sort_nonunique().
785 */
786template<class Key, class Compare, class Vector>
791
792/**
793 * Maps to verify_list_nonunique().
794 */
795template<class Key, class Compare, class Vector>
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
reference back()
Returns a reference to the first element.
void reserve(size_type_0 n)
Informs the vector of a planned change in size; ensures that the capacity of the vector is greater th...
reference front()
Returns a reference to the first element.
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
const_reverse_iterator_0 crbegin() const
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
const_iterator_0 cbegin() const
Returns the iterator that marks the first element in the ordered vector.
size_type_0 count(const key_type_0 &key) const
Returns the number of elements that sort equivalent to the key that are in the vector.
const_iterator_0 cend() const
Returns the iterator that marks the end of the ordered vector.
reverse_iterator_0 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
bool operator>=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one or is equivalent,...
bool operator!=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are not memberwise equivalent, false if they are.
bool operator==(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
void sort_unique()
Ensures that the vector is properly sorted after a potentially damaging operation.
bool operator<(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise.
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
bool operator>(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise.
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
void swap(ordered_vector< Key, Compare, Vector > &other)
Exchanges the contents of this vector and the other vector, in constant time (e.g....
bool operator<=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one or is equivalent,...
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
size_type_0 size() const
Returns the number of elements in the ordered vector.
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
const_reverse_iterator_0 crend() const
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
void pop_back()
Removes the last element at the end of the vector.
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
void clear()
Removes all elements from the ordered vector.
A specialization of ordered_vector that emulates a standard STL set: many copies of each element are ...
bool verify_list() const
Maps to verify_list_nonunique().
void sort()
Maps to sort_nonunique().
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
void sort()
Maps to sort_unique().
bool verify_list() const
Maps to verify_list_unique().