Panda3D
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) :
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>
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) :
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>
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 }
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
void pop_back()
Removes the last element at the end of the vector.
void sort_unique()
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.
void clear()
Removes all elements from the ordered vector.
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
bool verify_list() const
Maps to verify_list_unique().
bool verify_list() const
Maps to verify_list_nonunique().
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
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...
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 this ordered vector sorts lexicographically after the other one or is equivalent...
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 before the other one, false otherwise...
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
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 count(const key_type_0 &key) const
Returns the number of elements that sort equivalent to the key that are in the vector.
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...
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 or is equivalent...
bool operator>(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise...