Panda3D
ordered_vector.h
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.h
10  * @author drose
11  * @date 2002-02-20
12  */
13 
14 #ifndef ORDERED_VECTOR_H
15 #define ORDERED_VECTOR_H
16 #ifdef CPPPARSER // hack around this for interigate...
17 // ****** HACK allert *** this code is intended to tell interigate to not
18 // expand this class definition past basic names It drops the interigate
19 // memory foot pront and user time by a bunch on pc cygwin from 3 minutes to
20 // 17 seconds ?? really need to explore interigate to figure out what is going
21 // on ..
22 template<class Key, class Compare = std::less<int>, class Vector = pvector<Key> > class ov_multiset
23 {
24 };
25 
26 template<class Key, class Compare = std::less<int>, class Vector = pvector<Key> > class ov_set
27 {
28 };
29 
30 template<class Key, class Compare = std::less<int>, class Vector = pvector<Key> > class ordered_vector
31 {
32 };
33 
34 #else // cppparser
35 
36 
37 #include "pandabase.h"
38 
39 #include "pvector.h"
40 #include "pset.h"
41 #include "pnotify.h"
42 #include <algorithm>
43 
44 // There are some inheritance issues with template classes and typedef names.
45 // Template classes that inherit typedef names from their base class, which is
46 // also a template class, may confuse the typedef names with globally scoped
47 // template names. In particular, the local "iterator" type is easily
48 // confused with the std::iterator template class.
49 
50 // To work around this problem, as well as a problem in gcc 2.95.3 with
51 // value_type etc. not inheriting properly (even though we explicitly typedef
52 // them in the derived class), we rename the questionable typedefs here so
53 // that they no longer conflict with the global template classes.
54 
55 #define KEY_TYPE key_type_0
56 #define VALUE_TYPE value_type_0
57 #define REFERENCE reference_0
58 #define CONST_REFERENCE const_reference_0
59 #define KEY_COMPARE key_compare_0
60 #define VALUE_COMPARE value_compare_0
61 #define ITERATOR iterator_0
62 #define CONST_ITERATOR const_iterator_0
63 #define REVERSE_ITERATOR reverse_iterator_0
64 #define CONST_REVERSE_ITERATOR const_reverse_iterator_0
65 #define DIFFERENCE_TYPE difference_type_0
66 #define SIZE_TYPE size_type_0
67 
68 /**
69  * This template class presents an interface similar to the STL set or
70  * multiset (and ov_set and ov_multiset are implemented specifically, below),
71  * but it is implemented using a vector that is kept always in sorted order.
72  *
73  * In most cases, an ov_set or ov_multiset may be dropped in transparently in
74  * place of a set or multiset, but the implementation difference has a few
75  * implications:
76  *
77  * (1) The ov_multiset will maintain stability of order between elements that
78  * sort equally: they are stored in the order in which they were added, from
79  * back to front.
80  *
81  * (2) Insert and erase operations into the middle of the set can be slow,
82  * just as inserting into the middle of a vector can be slow. In fact,
83  * building up an ov_set by inserting elements one at a time is an n^2
84  * operation. On the other hand, building up an ov_set by adding elements to
85  * the end, one at time, is somewhat faster than building up a traditional
86  * set; and you can even add unsorted elements with push_back() and then call
87  * sort() when you're done, for a log(n) operation.
88  *
89  * (3) Iterators may not be valid for the life of the ordered_vector. If the
90  * vector reallocates itself, all iterators are invalidated.
91  *
92  * (4) Random access into the set is easy with the [] operator.
93  */
94 template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key> >
96 public:
97  // Typedefs
98  typedef Key KEY_TYPE;
99  typedef Key VALUE_TYPE;
100  typedef Key &REFERENCE;
101  typedef const Key &CONST_REFERENCE;
102  typedef Compare KEY_COMPARE;
103  typedef Compare VALUE_COMPARE;
104 
105  // Be careful when using the non-const iterators that you do not disturb the
106  // sorted order of the vector, or that if you do, you call sort() when you
107  // are done.
108  typedef typename Vector::iterator ITERATOR;
109  typedef typename Vector::const_iterator CONST_ITERATOR;
110  typedef typename Vector::reverse_iterator REVERSE_ITERATOR;
111  typedef typename Vector::const_reverse_iterator CONST_REVERSE_ITERATOR;
112 
113  typedef typename Vector::difference_type DIFFERENCE_TYPE;
114  typedef typename Vector::size_type SIZE_TYPE;
115 
116  // Since the #define symbols do not actually expand to the correct names, we
117  // have to re-typedef them so callers can reference them by their correct,
118  // lowercase names.
119  typedef KEY_TYPE key_type;
120  typedef VALUE_TYPE value_type;
121  typedef REFERENCE reference;
122  typedef CONST_REFERENCE const_reference;
123  typedef KEY_COMPARE key_compare;
124  typedef VALUE_COMPARE value_compare;
125  typedef ITERATOR iterator;
126  typedef CONST_ITERATOR const_iterator;
127  typedef REVERSE_ITERATOR reverse_iterator;
128  typedef CONST_REVERSE_ITERATOR const_reverse_iterator;
129  typedef DIFFERENCE_TYPE difference_type;
130  typedef SIZE_TYPE size_type;
131 
132 public:
133  // Constructors. We don't implement the whole slew of STL constructors here
134  // yet.
135  INLINE ordered_vector(TypeHandle type_handle = ov_set_type_handle);
136  INLINE ordered_vector(const Compare &compare,
137  TypeHandle type_handle = ov_set_type_handle);
138 
139  // Iterator access.
140  INLINE ITERATOR begin();
141  INLINE ITERATOR end();
142  INLINE REVERSE_ITERATOR rbegin();
143  INLINE REVERSE_ITERATOR rend();
144 
145  INLINE CONST_ITERATOR begin() const;
146  INLINE CONST_ITERATOR end() const;
147  INLINE CONST_REVERSE_ITERATOR rbegin() const;
148  INLINE CONST_REVERSE_ITERATOR rend() const;
149 
150  INLINE CONST_ITERATOR cbegin() const;
151  INLINE CONST_ITERATOR cend() const;
152  INLINE CONST_REVERSE_ITERATOR crbegin() const;
153  INLINE CONST_REVERSE_ITERATOR crend() const;
154 
155  // Random access.
156  INLINE reference operator [] (SIZE_TYPE n);
157  INLINE const_reference operator [] (SIZE_TYPE n) const;
158 
159  INLINE reference front();
160  INLINE const_reference front() const;
161 
162  INLINE reference back();
163  INLINE const_reference back() const;
164 
165  // Size information.
166  INLINE SIZE_TYPE size() const;
167  INLINE SIZE_TYPE max_size() const;
168  INLINE bool empty() const;
169 
170  // Equivalence and lexicographical comparisons.
171  INLINE bool operator == (const ordered_vector<Key, Compare, Vector> &other) const;
172  INLINE bool operator != (const ordered_vector<Key, Compare, Vector> &other) const;
173 
174  INLINE bool operator < (const ordered_vector<Key, Compare, Vector> &other) const;
175  INLINE bool operator > (const ordered_vector<Key, Compare, Vector> &other) const;
176  INLINE bool operator <= (const ordered_vector<Key, Compare, Vector> &other) const;
177  INLINE bool operator >= (const ordered_vector<Key, Compare, Vector> &other) const;
178 
179  // Insert operations.
180  ITERATOR insert_unique(ITERATOR position, const VALUE_TYPE &key);
181  ITERATOR insert_nonunique(ITERATOR position, const VALUE_TYPE &key);
182  INLINE std::pair<ITERATOR, bool> insert_unique(const VALUE_TYPE &key);
183  INLINE ITERATOR insert_nonunique(const VALUE_TYPE &key);
184  INLINE ITERATOR insert_unverified(ITERATOR position, const VALUE_TYPE &key);
185 
186  // Erase operations.
187  INLINE ITERATOR erase(ITERATOR position);
188  INLINE SIZE_TYPE erase(const KEY_TYPE &key);
189  INLINE void erase(ITERATOR first, ITERATOR last);
190  INLINE void clear();
191 
192  // Find operations.
193  INLINE ITERATOR find(const KEY_TYPE &key);
194  INLINE CONST_ITERATOR find(const KEY_TYPE &key) const;
195  INLINE ITERATOR find_particular(const KEY_TYPE &key);
196  INLINE CONST_ITERATOR find_particular(const KEY_TYPE &key) const;
197  INLINE SIZE_TYPE count(const KEY_TYPE &key) const;
198 
199  INLINE ITERATOR lower_bound(const KEY_TYPE &key);
200  INLINE CONST_ITERATOR lower_bound(const KEY_TYPE &key) const;
201  INLINE ITERATOR upper_bound(const KEY_TYPE &key);
202  INLINE CONST_ITERATOR upper_bound(const KEY_TYPE &key) const;
203  INLINE std::pair<ITERATOR, ITERATOR> equal_range(const KEY_TYPE &key);
204  INLINE std::pair<CONST_ITERATOR, CONST_ITERATOR> equal_range(const KEY_TYPE &key) const;
205 
206  // Special operations.
207  INLINE void swap(ordered_vector<Key, Compare, Vector> &other);
208  INLINE void reserve(SIZE_TYPE n);
209  INLINE void sort_unique();
210  INLINE void sort_nonunique();
211  bool verify_list_unique() const;
212  bool verify_list_nonunique() const;
213 
214  INLINE void push_back(const VALUE_TYPE &key);
215  INLINE void push_back(VALUE_TYPE &&key);
216  INLINE void pop_back();
217  INLINE void resize(SIZE_TYPE n);
218  INLINE void resize(SIZE_TYPE n, const VALUE_TYPE &value);
219 
220 private:
221  INLINE ITERATOR nci(CONST_ITERATOR i);
222  INLINE ITERATOR find_insert_position(ITERATOR first, ITERATOR last,
223  const KEY_TYPE &key);
224  ITERATOR r_find_insert_position(ITERATOR first, ITERATOR last,
225  const KEY_TYPE &key);
226  CONST_ITERATOR r_find(CONST_ITERATOR first, CONST_ITERATOR last,
227  CONST_ITERATOR not_found,
228  const KEY_TYPE &key) const;
229  CONST_ITERATOR r_find_particular(CONST_ITERATOR first, CONST_ITERATOR last,
230  CONST_ITERATOR not_found,
231  const KEY_TYPE &key) const;
232  SIZE_TYPE r_count(CONST_ITERATOR first, CONST_ITERATOR last,
233  const KEY_TYPE &key) const;
234  CONST_ITERATOR r_lower_bound(CONST_ITERATOR first, CONST_ITERATOR last,
235  const KEY_TYPE &key) const;
236  CONST_ITERATOR r_upper_bound(CONST_ITERATOR first, CONST_ITERATOR last,
237  const KEY_TYPE &key) const;
238  std::pair<CONST_ITERATOR, CONST_ITERATOR>
239  r_equal_range(CONST_ITERATOR first, CONST_ITERATOR last,
240  const KEY_TYPE &key) const;
241 
242  // This function object is used in sort_unique(). It returns true if two
243  // consecutive sorted elements are equivalent.
244  class EquivalentTest {
245  public:
246  // For some reason, VC++ won't allow us to define these bodies outside the
247  // class; they must be defined here. The error message is C3206: "member
248  // functions of nested classes of a template class cannot be defined
249  // outside the class".
250  INLINE EquivalentTest(const Compare &compare) :
251  _compare(compare) { }
252  INLINE bool operator () (const KEY_TYPE &a, const KEY_TYPE &b) {
253  nassertr(!_compare(b, a), false);
254  return !_compare(a, b);
255  }
256 
257  Compare _compare;
258  };
259 
260  Compare _compare;
261  Vector _vector;
262 };
263 
264 /**
265  * A specialization of ordered_vector that emulates a standard STL set: one
266  * copy of each element is allowed.
267  */
268 template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key> >
269 class ov_set : public ordered_vector<Key, Compare, Vector> {
270 public:
271  typedef typename ordered_vector<Key, Compare, Vector>::ITERATOR ITERATOR;
272  typedef typename ordered_vector<Key, Compare, Vector>::VALUE_TYPE VALUE_TYPE;
273 
274  INLINE ov_set(TypeHandle type_handle = ov_set_type_handle);
275  INLINE ov_set(const Compare &compare,
276  TypeHandle type_handle = ov_set_type_handle);
277 
278  INLINE ITERATOR insert(ITERATOR position, const VALUE_TYPE &key0);
279  INLINE std::pair<ITERATOR, bool> insert(const VALUE_TYPE &key0);
280 
281  INLINE void sort();
282  INLINE bool verify_list() const;
283 };
284 
285 /**
286  * A specialization of ordered_vector that emulates a standard STL set: many
287  * copies of each element are allowed.
288  */
289 template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key> >
290 class ov_multiset : public ordered_vector<Key, Compare, Vector> {
291 public:
292  typedef typename ordered_vector<Key, Compare, Vector>::ITERATOR ITERATOR;
293  typedef typename ordered_vector<Key, Compare, Vector>::VALUE_TYPE VALUE_TYPE;
294 
295  INLINE ov_multiset(TypeHandle type_handle = ov_set_type_handle);
296  INLINE ov_multiset(const Compare &compare,
297  TypeHandle type_handle = ov_set_type_handle);
298 
299  INLINE ITERATOR insert(ITERATOR position, const VALUE_TYPE &key);
300  INLINE ITERATOR insert(const VALUE_TYPE &key);
301 
302  INLINE void sort();
303  INLINE bool verify_list() const;
304 };
305 
306 #include "ordered_vector.I"
307 #include "ordered_vector.T"
308 #endif // cppparser ..
309 #endif
ordered_vector::size
size_type_0 size() const
Returns the number of elements in the ordered vector.
Definition: ordered_vector.I:221
ov_multiset
A specialization of ordered_vector that emulates a standard STL set: many copies of each element are ...
Definition: ordered_vector.h:290
ordered_vector::count
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.
Definition: ordered_vector.I:484
ov_multiset::verify_list
bool verify_list() const
Maps to verify_list_nonunique().
Definition: ordered_vector.I:797
ordered_vector::front
reference front()
Returns a reference to the first element.
Definition: ordered_vector.I:173
ov_set::sort
void sort()
Maps to sort_unique().
Definition: ordered_vector.I:731
ordered_vector::reserve
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...
Definition: ordered_vector.I:572
pandabase.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pvector.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
ordered_vector::operator<
bool operator<(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise.
Definition: ordered_vector.I:270
ordered_vector::empty
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
Definition: ordered_vector.I:240
ov_multiset::sort
void sort()
Maps to sort_nonunique().
Definition: ordered_vector.I:788
ordered_vector.I
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
ordered_vector::crbegin
const_reverse_iterator_0 crbegin() const
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
Definition: ordered_vector.I:136
ordered_vector::operator>=
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,...
Definition: ordered_vector.I:300
ov_set::verify_list
bool verify_list() const
Maps to verify_list_unique().
Definition: ordered_vector.I:740
ordered_vector::rbegin
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
Definition: ordered_vector.I:60
ordered_vector::operator==
bool operator==(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
Definition: ordered_vector.I:250
ordered_vector::max_size
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
Definition: ordered_vector.I:231
pnotify.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
ordered_vector::swap
void swap(ordered_vector< Key, Compare, Vector > &other)
Exchanges the contents of this vector and the other vector, in constant time (e.g....
Definition: ordered_vector.I:561
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
ordered_vector::crend
const_reverse_iterator_0 crend() const
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition: ordered_vector.I:146
ordered_vector::sort_nonunique
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
Definition: ordered_vector.I:602
ordered_vector::push_back
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
Definition: ordered_vector.I:614
ordered_vector::operator<=
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,...
Definition: ordered_vector.I:290
ordered_vector::sort_unique
void sort_unique()
Ensures that the vector is properly sorted after a potentially damaging operation.
Definition: ordered_vector.I:587
ordered_vector::back
reference back()
Returns a reference to the first element.
Definition: ordered_vector.I:197
ordered_vector::end
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
Definition: ordered_vector.I:50
ordered_vector
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
Definition: ordered_vector.h:95
ordered_vector::cend
const_iterator_0 cend() const
Returns the iterator that marks the end of the ordered vector.
Definition: ordered_vector.I:126
pset.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
ordered_vector::cbegin
const_iterator_0 cbegin() const
Returns the iterator that marks the first element in the ordered vector.
Definition: ordered_vector.I:117
ordered_vector::insert_unverified
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
Definition: ordered_vector.I:362
ov_set
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
Definition: ordered_vector.h:269
ordered_vector::operator>
bool operator>(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise.
Definition: ordered_vector.I:280
ordered_vector::pop_back
void pop_back()
Removes the last element at the end of the vector.
Definition: ordered_vector.I:636
ordered_vector::begin
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
Definition: ordered_vector.I:41
ordered_vector::clear
void clear()
Removes all elements from the ordered vector.
Definition: ordered_vector.I:412
ordered_vector::operator!=
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.
Definition: ordered_vector.I:260
ordered_vector::rend
reverse_iterator_0 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
Definition: ordered_vector.I:70