Panda3D
 All Classes Functions Variables Enumerations
ordered_vector.I
1 // Filename: ordered_vector.I
2 // Created by: drose (20Feb02)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 
16 ////////////////////////////////////////////////////////////////////
17 // Function: ordered_vector::Constructor
18 // Access: Public
19 // Description:
20 ////////////////////////////////////////////////////////////////////
21 template<class Key, class Compare, class Vector>
23 ordered_vector(TypeHandle type_handle) :
24  _compare(Compare()),
25  _vector(type_handle)
26 {
27 }
28 
29 ////////////////////////////////////////////////////////////////////
30 // Function: ordered_vector::Constructor
31 // Access: Public
32 // Description:
33 ////////////////////////////////////////////////////////////////////
34 template<class Key, class Compare, class Vector>
36 ordered_vector(const Compare &compare, TypeHandle type_handle) :
37  _compare(compare),
38  _vector(type_handle)
39 {
40 }
41 
42 ////////////////////////////////////////////////////////////////////
43 // Function: ordered_vector::Copy Constructor
44 // Access: Public
45 // Description:
46 ////////////////////////////////////////////////////////////////////
47 template<class Key, class Compare, class Vector>
50  _compare(copy._compare),
51  _vector(copy._vector)
52 {
53 }
54 
55 ////////////////////////////////////////////////////////////////////
56 // Function: ordered_vector::Copy Assignment Operator
57 // Access: Public
58 // Description:
59 ////////////////////////////////////////////////////////////////////
60 template<class Key, class Compare, class Vector>
63  _compare = copy._compare;
64  _vector = copy._vector;
65  return *this;
66 }
67 
68 ////////////////////////////////////////////////////////////////////
69 // Function: ordered_vector::Destructor
70 // Access: Public
71 // Description:
72 ////////////////////////////////////////////////////////////////////
73 template<class Key, class Compare, class Vector>
76 }
77 
78 ////////////////////////////////////////////////////////////////////
79 // Function: ordered_vector::begin
80 // Access: Public
81 // Description: Returns the iterator that marks the first element in
82 // the ordered vector.
83 ////////////////////////////////////////////////////////////////////
84 template<class Key, class Compare, class Vector>
86 begin() {
87  return _vector.begin();
88 }
89 
90 ////////////////////////////////////////////////////////////////////
91 // Function: ordered_vector::end
92 // Access: Public
93 // Description: Returns the iterator that marks the end of the
94 // ordered vector.
95 ////////////////////////////////////////////////////////////////////
96 template<class Key, class Compare, class Vector>
98 end() {
99  return _vector.end();
100 }
101 
102 ////////////////////////////////////////////////////////////////////
103 // Function: ordered_vector::rbegin
104 // Access: Public
105 // Description: Returns the iterator that marks the first element in
106 // the ordered vector, when viewed in reverse order.
107 ////////////////////////////////////////////////////////////////////
108 template<class Key, class Compare, class Vector>
111  return _vector.rbegin();
112 }
113 
114 ////////////////////////////////////////////////////////////////////
115 // Function: ordered_vector::rend
116 // Access: Public
117 // Description: Returns the iterator that marks the end of the
118 // ordered vector, when viewed in reverse order.
119 ////////////////////////////////////////////////////////////////////
120 template<class Key, class Compare, class Vector>
122 rend() {
123  return _vector.rend();
124 }
125 
126 ////////////////////////////////////////////////////////////////////
127 // Function: ordered_vector::begin
128 // Access: Public
129 // Description: Returns the iterator that marks the first element in
130 // the ordered vector.
131 ////////////////////////////////////////////////////////////////////
132 template<class Key, class Compare, class Vector>
134 begin() const {
135  return _vector.begin();
136 }
137 
138 ////////////////////////////////////////////////////////////////////
139 // Function: ordered_vector::end
140 // Access: Public
141 // Description: Returns the iterator that marks the end of the
142 // ordered vector.
143 ////////////////////////////////////////////////////////////////////
144 template<class Key, class Compare, class Vector>
146 end() const {
147  return _vector.end();
148 }
149 
150 ////////////////////////////////////////////////////////////////////
151 // Function: ordered_vector::rbegin
152 // Access: Public
153 // Description: Returns the iterator that marks the first element in
154 // the ordered vector, when viewed in reverse order.
155 ////////////////////////////////////////////////////////////////////
156 template<class Key, class Compare, class Vector>
158 rbegin() const {
159  return _vector.rbegin();
160 }
161 
162 ////////////////////////////////////////////////////////////////////
163 // Function: ordered_vector::rend
164 // Access: Public
165 // Description: Returns the iterator that marks the end of the
166 // ordered vector, when viewed in reverse order.
167 ////////////////////////////////////////////////////////////////////
168 template<class Key, class Compare, class Vector>
170 rend() const {
171  return _vector.rend();
172 }
173 
174 ////////////////////////////////////////////////////////////////////
175 // Function: ordered_vector::operator []
176 // Access: Public
177 // Description: Returns the nth element.
178 ////////////////////////////////////////////////////////////////////
179 template<class Key, class Compare, class Vector>
182  return _vector[n];
183 }
184 
185 ////////////////////////////////////////////////////////////////////
186 // Function: ordered_vector::operator []
187 // Access: Public
188 // Description: Returns the nth element.
189 ////////////////////////////////////////////////////////////////////
190 template<class Key, class Compare, class Vector>
193  return _vector[n];
194 }
195 
196 ////////////////////////////////////////////////////////////////////
197 // Function: ordered_vector::size
198 // Access: Public
199 // Description: Returns the number of elements in the ordered vector.
200 ////////////////////////////////////////////////////////////////////
201 template<class Key, class Compare, class Vector>
203 size() const {
204  return _vector.size();
205 }
206 
207 ////////////////////////////////////////////////////////////////////
208 // Function: ordered_vector::max_size
209 // Access: Public
210 // Description: Returns the maximum number of elements that can
211 // possibly be stored in an ordered vector.
212 ////////////////////////////////////////////////////////////////////
213 template<class Key, class Compare, class Vector>
215 max_size() const {
216  return _vector.max_size();
217 }
218 
219 ////////////////////////////////////////////////////////////////////
220 // Function: ordered_vector::empty
221 // Access: Public
222 // Description: Returns true if the ordered vector is empty, false
223 // otherwise.
224 ////////////////////////////////////////////////////////////////////
225 template<class Key, class Compare, class Vector>
227 empty() const {
228  return _vector.empty();
229 }
230 
231 ////////////////////////////////////////////////////////////////////
232 // Function: ordered_vector::operator ==
233 // Access: Public
234 // Description: Returns true if the two ordered vectors are
235 // memberwise equivalent, false otherwise.
236 ////////////////////////////////////////////////////////////////////
237 template<class Key, class Compare, class Vector>
240  return _vector == other._vector;
241 }
242 
243 ////////////////////////////////////////////////////////////////////
244 // Function: ordered_vector::operator !=
245 // Access: Public
246 // Description: Returns true if the two ordered vectors are not
247 // memberwise equivalent, false if they are.
248 ////////////////////////////////////////////////////////////////////
249 template<class Key, class Compare, class Vector>
252  return _vector != other._vector;
253 }
254 
255 ////////////////////////////////////////////////////////////////////
256 // Function: ordered_vector::operator <
257 // Access: Public
258 // Description: Returns true if this ordered vector sorts
259 // lexicographically before the other one, false
260 // otherwise.
261 ////////////////////////////////////////////////////////////////////
262 template<class Key, class Compare, class Vector>
265  return _vector < other._vector;
266 }
267 
268 ////////////////////////////////////////////////////////////////////
269 // Function: ordered_vector::operator >
270 // Access: Public
271 // Description: Returns true if this ordered vector sorts
272 // lexicographically after the other one, false
273 // otherwise.
274 ////////////////////////////////////////////////////////////////////
275 template<class Key, class Compare, class Vector>
278  return _vector > other._vector;
279 }
280 
281 ////////////////////////////////////////////////////////////////////
282 // Function: ordered_vector::operator <=
283 // Access: Public
284 // Description: Returns true if this ordered vector sorts
285 // lexicographically before the other one or is
286 // equivalent, false otherwise.
287 ////////////////////////////////////////////////////////////////////
288 template<class Key, class Compare, class Vector>
291  return _vector <= other._vector;
292 }
293 
294 ////////////////////////////////////////////////////////////////////
295 // Function: ordered_vector::operator >=
296 // Access: Public
297 // Description: Returns true if this ordered vector sorts
298 // lexicographically after the other one or is
299 // equivalent, false otherwise.
300 ////////////////////////////////////////////////////////////////////
301 template<class Key, class Compare, class Vector>
304  return _vector >= other._vector;
305 }
306 
307 
308 ////////////////////////////////////////////////////////////////////
309 // Function: ordered_vector::insert_unique
310 // Access: Public
311 // Description: Inserts the indicated key into the ordered vector, at
312 // the appropriate place. If there is already an element
313 // sorting equivalent to the key in the vector, the new
314 // key is not inserted.
315 //
316 // The return value is a pair, where the first component
317 // is the iterator referencing the new element (or the
318 // original element), and the second componet is true if
319 // the insert operation has taken place.
320 ////////////////////////////////////////////////////////////////////
321 template<class Key, class Compare, class Vector>
322 INLINE pair<TYPENAME ordered_vector<Key, Compare, Vector>::ITERATOR, bool> ordered_vector<Key, Compare, Vector>::
324  TAU_PROFILE("ordered_vector::insert_unique(const value_type &)", " ", TAU_USER);
325  ITERATOR position = find_insert_position(begin(), end(), key);
326 #ifdef NDEBUG
327  pair<ITERATOR, bool> bogus_result(end(), false);
328  nassertr(position >= begin() && position <= end(), bogus_result);
329 #endif
330 
331  // If there's already an equivalent key in the vector, it's at
332  // *(position - 1).
333  if (position != begin() && !_compare(*(position - 1), key)) {
334  pair<ITERATOR, bool> result(position - 1, false);
335  nassertr(!_compare(key, *(position - 1)), result);
336  return result;
337  }
338 
339  ITERATOR result = _vector.insert(position, key);
340  return pair<ITERATOR, bool>(result, true);
341 }
342 
343 ////////////////////////////////////////////////////////////////////
344 // Function: ordered_vector::insert_nonunique
345 // Access: Public
346 // Description: Inserts the indicated key into the ordered vector, at
347 // the appropriate place. If there are already elements
348 // sorting equivalent to the key in the vector, the new
349 // value is inserted following them.
350 //
351 // The return value is the iterator referencing the new
352 // element.
353 ////////////////////////////////////////////////////////////////////
354 template<class Key, class Compare, class Vector>
357  TAU_PROFILE("ordered_vector::insert_nonunique(const value_type &)", " ", TAU_USER);
358  ITERATOR position = find_insert_position(begin(), end(), key);
359  nassertr(position >= begin() && position <= end(), end());
360 
361  ITERATOR result = _vector.insert(position, key);
362  return result;
363 }
364 
365 
366 ////////////////////////////////////////////////////////////////////
367 // Function: ordered_vector::insert_unverified
368 // Access: Public
369 // Description: Inserts the indicated key into the ordered vector at
370 // the indicated place. The user is trusted to have
371 // already verified that this is the correct sorting
372 // position; no checks are made.
373 ////////////////////////////////////////////////////////////////////
374 template<class Key, class Compare, class Vector>
378  TAU_PROFILE("ordered_vector::insert_unverified(iterator, const value_type &)", " ", TAU_USER);
379  ITERATOR result = _vector.insert(position, key);
380  return result;
381 }
382 
383 ////////////////////////////////////////////////////////////////////
384 // Function: ordered_vector::erase, with iterator
385 // Access: Public
386 // Description: Removes the element indicated by the given iterator,
387 // and returns the next sequential iterator.
388 ////////////////////////////////////////////////////////////////////
389 template<class Key, class Compare, class Vector>
392  TAU_PROFILE("ordered_vector::erase(iterator)", " ", TAU_USER);
393  SIZE_TYPE count = position - begin();
394  _vector.erase(position);
395  return begin() + count;
396 }
397 
398 ////////////////////////////////////////////////////////////////////
399 // Function: ordered_vector::erase, with key
400 // Access: Public
401 // Description: Removes all elements matching the indicated key;
402 // returns the number of elements removed.
403 ////////////////////////////////////////////////////////////////////
404 template<class Key, class Compare, class Vector>
407  TAU_PROFILE("ordered_vector::erase(const key_type &)", " ", TAU_USER);
408  pair<ITERATOR, ITERATOR> result = equal_range(key);
409  SIZE_TYPE count = result.second - result.first;
410  erase(result.first, result.second);
411  return count;
412 }
413 
414 ////////////////////////////////////////////////////////////////////
415 // Function: ordered_vector::erase, a range
416 // Access: Public
417 // Description: Removes all elements indicated by the given iterator
418 // range.
419 ////////////////////////////////////////////////////////////////////
420 template<class Key, class Compare, class Vector>
424  TAU_PROFILE("ordered_vector::erase(iterator, iterator)", " ", TAU_USER);
425  _vector.erase(first, last);
426 }
427 
428 ////////////////////////////////////////////////////////////////////
429 // Function: ordered_vector::clear
430 // Access: Public
431 // Description: Removes all elements from the ordered vector.
432 ////////////////////////////////////////////////////////////////////
433 template<class Key, class Compare, class Vector>
435 clear() {
436  TAU_PROFILE("ordered_vector::clear()", " ", TAU_USER);
437  _vector.erase(_vector.begin(), _vector.end());
438 }
439 
440 ////////////////////////////////////////////////////////////////////
441 // Function: ordered_vector::find
442 // Access: Public
443 // Description: Searches for an element with the indicated key and
444 // returns its iterator if it is found, or end() if it
445 // is not. If there are multiple elements matching the
446 // key, the particular iterator returned is not defined.
447 ////////////////////////////////////////////////////////////////////
448 template<class Key, class Compare, class Vector>
451  TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
452  return nci(r_find(begin(), end(), end(), key));
453 }
454 
455 ////////////////////////////////////////////////////////////////////
456 // Function: ordered_vector::find
457 // Access: Public
458 // Description: Searches for an element with the indicated key and
459 // returns its iterator if it is found, or end() if it
460 // is not. If there are multiple elements matching the
461 // key, the particular iterator returned is not defined.
462 ////////////////////////////////////////////////////////////////////
463 template<class Key, class Compare, class Vector>
465 find(const TYPENAME ordered_vector<Key, Compare, Vector>::KEY_TYPE &key) const {
466  TAU_PROFILE("ordered_vector::find(const key_type &)", " ", TAU_USER);
467  return r_find(begin(), end(), end(), key);
468 }
469 
470 ////////////////////////////////////////////////////////////////////
471 // Function: ordered_vector::find_particular
472 // Access: Public
473 // Description: Searches for a particular element and returns its
474 // iterator if it is found, or end() if it is not.
475 //
476 // First, the Compare function is used to narrow down
477 // the range of elements the element might be located
478 // within; then the element is compared elementwise, via
479 // ==, until the exact matching element is found. If
480 // multiple matches exist within the vector, the
481 // particular iterator returned is not defined.
482 //
483 // The assumption is that == implies !Compare(a, b) and
484 // !Compare(b, a), but not necessarily the converse.
485 ////////////////////////////////////////////////////////////////////
486 template<class Key, class Compare, class Vector>
489  TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
490  return nci(r_find_particular(begin(), end(), end(), key));
491 }
492 
493 ////////////////////////////////////////////////////////////////////
494 // Function: ordered_vector::find_particular
495 // Access: Public
496 // Description: Searches for a particular element and returns its
497 // iterator if it is found, or end() if it is not.
498 //
499 // First, the Compare function is used to narrow down
500 // the range of elements the element might be located
501 // within; then the element is compared elementwise, via
502 // ==, until the exact matching element is found. If
503 // multiple matches exist within the vector, the
504 // particular iterator returned is not defined./
505 ////////////////////////////////////////////////////////////////////
506 template<class Key, class Compare, class Vector>
509  TAU_PROFILE("ordered_vector::find_particular(const key_type &)", " ", TAU_USER);
510  return r_find_particular(begin(), end(), end(), key);
511 }
512 
513 ////////////////////////////////////////////////////////////////////
514 // Function: ordered_vector::count
515 // Access: Public
516 // Description: Returns the number of elements that sort equivalent
517 // to the key that are in the vector.
518 ////////////////////////////////////////////////////////////////////
519 template<class Key, class Compare, class Vector>
521 count(const key_type &key) const {
522  TAU_PROFILE("ordered_vector::count(const key_type &)", " ", TAU_USER);
523  return r_count(begin(), end(), key);
524 }
525 
526 ////////////////////////////////////////////////////////////////////
527 // Function: ordered_vector::lower_bound
528 // Access: Public
529 // Description: Returns the iterator for the first element not less
530 // than key, or end() if all elements are less than key.
531 ////////////////////////////////////////////////////////////////////
532 template<class Key, class Compare, class Vector>
535  TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
536  return nci(r_lower_bound(begin(), end(), key));
537 }
538 
539 ////////////////////////////////////////////////////////////////////
540 // Function: ordered_vector::lower_bound
541 // Access: Public
542 // Description: Returns the iterator for the first element not less
543 // than key, or end() if all elements are less than key.
544 ////////////////////////////////////////////////////////////////////
545 template<class Key, class Compare, class Vector>
548  TAU_PROFILE("ordered_vector::lower_bound(const key_type &)", " ", TAU_USER);
549  return r_lower_bound(begin(), end(), key);
550 }
551 
552 ////////////////////////////////////////////////////////////////////
553 // Function: ordered_vector::upper_bound
554 // Access: Public
555 // Description: Returns the iterator for the first element greater
556 // than key, or end() if no element is greater than
557 // key.
558 ////////////////////////////////////////////////////////////////////
559 template<class Key, class Compare, class Vector>
562  TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
563  return nci(r_upper_bound(begin(), end(), key));
564 }
565 
566 ////////////////////////////////////////////////////////////////////
567 // Function: ordered_vector::upper_bound
568 // Access: Public
569 // Description: Returns the iterator for the first element greater
570 // than key, or end() if no element is greater than
571 // key.
572 ////////////////////////////////////////////////////////////////////
573 template<class Key, class Compare, class Vector>
576  TAU_PROFILE("ordered_vector::upper_bound(const key_type &)", " ", TAU_USER);
577  return r_upper_bound(begin(), end(), key);
578 }
579 
580 ////////////////////////////////////////////////////////////////////
581 // Function: ordered_vector::equal_range
582 // Access: Public
583 // Description: Returns the pair (lower_bound(key), upper_bound(key)).
584 ////////////////////////////////////////////////////////////////////
585 template<class Key, class Compare, class Vector>
586 INLINE pair<TYPENAME ordered_vector<Key, Compare, Vector>::ITERATOR, TYPENAME ordered_vector<Key, Compare, Vector>::ITERATOR> ordered_vector<Key, Compare, Vector>::
588  TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
589  pair<TYPENAME ordered_vector<Key, Compare, Vector>::CONST_ITERATOR, TYPENAME ordered_vector<Key, Compare, Vector>::CONST_ITERATOR> result;
590  result = r_equal_range(begin(), end(), key);
591  return pair<TYPENAME ordered_vector<Key, Compare, Vector>::ITERATOR, TYPENAME ordered_vector<Key, Compare, Vector>::ITERATOR>(nci(result.first), nci(result.second));
592 }
593 
594 ////////////////////////////////////////////////////////////////////
595 // Function: ordered_vector::equal_range
596 // Access: Public
597 // Description: Returns the pair (lower_bound(key), upper_bound(key)).
598 ////////////////////////////////////////////////////////////////////
599 template<class Key, class Compare, class Vector>
600 INLINE pair<TYPENAME ordered_vector<Key, Compare, Vector>::CONST_ITERATOR, TYPENAME ordered_vector<Key, Compare, Vector>::CONST_ITERATOR> ordered_vector<Key, Compare, Vector>::
602  TAU_PROFILE("ordered_vector::equal_range(const key_type &)", " ", TAU_USER);
603  return r_equal_range(begin(), end(), key);
604 }
605 
606 ////////////////////////////////////////////////////////////////////
607 // Function: ordered_vector::swap
608 // Access: Public
609 // Description: Exchanges the contents of this vector and the other
610 // vector, in constant time (e.g., with a pointer swap).
611 ////////////////////////////////////////////////////////////////////
612 template<class Key, class Compare, class Vector>
615  TAU_PROFILE("ordered_vector::swap(ordered_vector &)", " ", TAU_USER);
616  _vector.swap(copy._vector);
617 }
618 
619 ////////////////////////////////////////////////////////////////////
620 // Function: ordered_vector::reserve
621 // Access: Public
622 // Description: Informs the vector of a planned change in size;
623 // ensures that the capacity of the vector is greater
624 // than or equal to n.
625 ////////////////////////////////////////////////////////////////////
626 template<class Key, class Compare, class Vector>
629  TAU_PROFILE("ordered_vector::reserve(size_type)", " ", TAU_USER);
630  _vector.reserve(n);
631 }
632 
633 ////////////////////////////////////////////////////////////////////
634 // Function: ordered_vector::sort_unique
635 // Access: Public
636 // Description: Ensures that the vector is properly sorted after a
637 // potentially damaging operation. This should not
638 // normally need to be called, unless the user has
639 // written to the vector using the non-const iterators
640 // or has called push_back().
641 //
642 // This flavor of sort also eliminates repeated
643 // elements.
644 ////////////////////////////////////////////////////////////////////
645 template<class Key, class Compare, class Vector>
648  TAU_PROFILE("ordered_vector::sort_unique()", " ", TAU_USER);
649  sort(begin(), end(), _compare);
650  iterator new_end = unique(begin(), end(), EquivalentTest(_compare));
651  erase(new_end, end());
652 }
653 
654 ////////////////////////////////////////////////////////////////////
655 // Function: ordered_vector::sort_nonunique
656 // Access: Public
657 // Description: Ensures that the vector is properly sorted after a
658 // potentially damaging operation. This should not
659 // normally need to be called, unless the user has
660 // written to the vector using the non-const iterators
661 // or has called push_back().
662 ////////////////////////////////////////////////////////////////////
663 template<class Key, class Compare, class Vector>
666  TAU_PROFILE("ordered_vector::sort_nonunique()", " ", TAU_USER);
667  stable_sort(begin(), end(), _compare);
668 }
669 
670 ////////////////////////////////////////////////////////////////////
671 // Function: ordered_vector::push_back
672 // Access: Public
673 // Description: Adds the new element to the end of the vector without
674 // regard for proper sorting. This is a bad idea to do
675 // except to populate the vector the first time; be sure
676 // to call sort() after you have added all the elements.
677 ////////////////////////////////////////////////////////////////////
678 template<class Key, class Compare, class Vector>
680 push_back(const value_type &key) {
681  TAU_PROFILE("ordered_vector::push_back()", " ", TAU_USER);
682  _vector.push_back(key);
683 }
684 
685 ////////////////////////////////////////////////////////////////////
686 // Function: ordered_vector::pop_back
687 // Access: Public
688 // Description: Removes the last element at the end of the vector.
689 ////////////////////////////////////////////////////////////////////
690 template<class Key, class Compare, class Vector>
693  TAU_PROFILE("ordered_vector::pop_back()", " ", TAU_USER);
694  _vector.pop_back();
695 }
696 
697 ////////////////////////////////////////////////////////////////////
698 // Function: ordered_vector::nci
699 // Access: Private
700 // Description: I.e. "non-const iterator". This function is used to
701 // typecast a const iterator to a non-const iterator for
702 // easy definition of const vs. non-const flavors of
703 // some of these methods.
704 ////////////////////////////////////////////////////////////////////
705 template<class Key, class Compare, class Vector>
708  return begin() + (i - begin());
709 }
710 
711 ////////////////////////////////////////////////////////////////////
712 // Function: ordered_vector::find_insert_position
713 // Access: Private
714 // Description: Searches for the appropriate place in the ordered
715 // vector to insert the indicated key, and returns the
716 // corresponding iterator.
717 ////////////////////////////////////////////////////////////////////
718 template<class Key, class Compare, class Vector>
723  ITERATOR result = r_find_insert_position(first, last, key);
724  return result;
725 }
726 
727 ////////////////////////////////////////////////////////////////////
728 // Function: ov_set::Constructor
729 // Access: Public
730 // Description:
731 ////////////////////////////////////////////////////////////////////
732 template<class Key, class Compare, class Vector>
734 ov_set(TypeHandle type_handle) :
735  ordered_vector<Key, Compare, Vector>(type_handle)
736 {
737 }
738 
739 ////////////////////////////////////////////////////////////////////
740 // Function: ov_set::Constructor
741 // Access: Public
742 // Description:
743 ////////////////////////////////////////////////////////////////////
744 template<class Key, class Compare, class Vector>
746 ov_set(const Compare &compare, TypeHandle type_handle) :
747  ordered_vector<Key, Compare, Vector>(compare, type_handle)
748 {
749 }
750 
751 ////////////////////////////////////////////////////////////////////
752 // Function: ov_set::Copy Constructor
753 // Access: Public
754 // Description:
755 ////////////////////////////////////////////////////////////////////
756 template<class Key, class Compare, class Vector>
759  ordered_vector<Key, Compare, Vector>(copy)
760 {
761 }
762 
763 ////////////////////////////////////////////////////////////////////
764 // Function: ov_set::Copy Assignment Operator
765 // Access: Public
766 // Description:
767 ////////////////////////////////////////////////////////////////////
768 template<class Key, class Compare, class Vector>
772  return *this;
773 }
774 
775 ////////////////////////////////////////////////////////////////////
776 // Function: ov_set::insert
777 // Access: Public
778 // Description: Maps to insert_unique().
779 ////////////////////////////////////////////////////////////////////
780 template<class Key, class Compare, class Vector>
783  const TYPENAME ov_set<Key, Compare, Vector>::VALUE_TYPE &key) {
785 }
786 
787 ////////////////////////////////////////////////////////////////////
788 // Function: ov_set::insert
789 // Access: Public
790 // Description: Maps to insert_unique().
791 ////////////////////////////////////////////////////////////////////
792 template<class Key, class Compare, class Vector>
793 INLINE pair<TYPENAME ov_set<Key, Compare, Vector>::ITERATOR, bool> ov_set<Key, Compare, Vector>::
796 }
797 
798 ////////////////////////////////////////////////////////////////////
799 // Function: ov_set::sort
800 // Access: Public
801 // Description: Maps to sort_unique().
802 ////////////////////////////////////////////////////////////////////
803 template<class Key, class Compare, class Vector>
805 sort() {
807 }
808 
809 ////////////////////////////////////////////////////////////////////
810 // Function: ov_set::verify_list
811 // Access: Public
812 // Description: Maps to verify_list_unique().
813 ////////////////////////////////////////////////////////////////////
814 template<class Key, class Compare, class Vector>
816 verify_list() const {
818 }
819 
820 ////////////////////////////////////////////////////////////////////
821 // Function: ov_multiset::Constructor
822 // Access: Public
823 // Description:
824 ////////////////////////////////////////////////////////////////////
825 template<class Key, class Compare, class Vector>
827 ov_multiset(TypeHandle type_handle) :
828  ordered_vector<Key, Compare, Vector>(type_handle)
829 {
830 }
831 
832 ////////////////////////////////////////////////////////////////////
833 // Function: ov_multiset::Constructor
834 // Access: Public
835 // Description:
836 ////////////////////////////////////////////////////////////////////
837 template<class Key, class Compare, class Vector>
839 ov_multiset(const Compare &compare, TypeHandle type_handle) :
840  ordered_vector<Key, Compare, Vector>(compare, type_handle)
841 {
842 }
843 
844 ////////////////////////////////////////////////////////////////////
845 // Function: ov_multiset::Copy Constructor
846 // Access: Public
847 // Description:
848 ////////////////////////////////////////////////////////////////////
849 template<class Key, class Compare, class Vector>
852  ordered_vector<Key, Compare, Vector>(copy)
853 {
854 }
855 
856 ////////////////////////////////////////////////////////////////////
857 // Function: ov_multiset::Copy Assignment Operator
858 // Access: Public
859 // Description:
860 ////////////////////////////////////////////////////////////////////
861 template<class Key, class Compare, class Vector>
865  return *this;
866 }
867 
868 ////////////////////////////////////////////////////////////////////
869 // Function: ov_multiset::insert
870 // Access: Public
871 // Description: Maps to insert_nonunique().
872 ////////////////////////////////////////////////////////////////////
873 template<class Key, class Compare, class Vector>
876  const TYPENAME ov_multiset<Key, Compare, Vector>::VALUE_TYPE &key) {
878 }
879 
880 ////////////////////////////////////////////////////////////////////
881 // Function: ov_multiset::insert
882 // Access: Public
883 // Description: Maps to insert_nonunique().
884 ////////////////////////////////////////////////////////////////////
885 template<class Key, class Compare, class Vector>
889 }
890 
891 ////////////////////////////////////////////////////////////////////
892 // Function: ov_multiset::sort
893 // Access: Public
894 // Description: Maps to sort_nonunique().
895 ////////////////////////////////////////////////////////////////////
896 template<class Key, class Compare, class Vector>
898 sort() {
900 }
901 
902 ////////////////////////////////////////////////////////////////////
903 // Function: ov_multiset::verify_list
904 // Access: Public
905 // Description: Maps to verify_list_nonunique().
906 ////////////////////////////////////////////////////////////////////
907 template<class Key, class Compare, class Vector>
909 verify_list() const {
911 }
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...
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
bool verify_list() const
Maps to verify_list_unique().
void pop_back()
Removes the last element at the end of the vector.
bool operator==(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
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...
void sort_unique()
Ensures that the vector is properly sorted after a potentially damaging operation.
void clear()
Removes all elements from the ordered vector.
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
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.
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...
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
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...
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
void swap(ordered_vector< Key, Compare, Vector > &other)
Exchanges the contents of this vector and the other vector, in constant time (e.g., with a pointer swap).
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...
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
bool verify_list() const
Maps to verify_list_nonunique().
void sort()
Maps to sort_nonunique().
void sort()
Maps to sort_unique().
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
A specialization of ordered_vector that emulates a standard STL set: many copies of each element are ...
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 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order...
size_type_0 size() const
Returns the number of elements in the ordered vector.
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:85
bool operator<(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise...