Panda3D
Loading...
Searching...
No Matches
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 ..
22template<class Key, class Compare = std::less<int>, class Vector = pvector<Key> > class ov_multiset
23{
24};
25
26template<class Key, class Compare = std::less<int>, class Vector = pvector<Key> > class ov_set
27{
28};
29
30template<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 */
94template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key> >
96public:
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
132public:
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
220private:
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 */
268template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key> >
269class ov_set : public ordered_vector<Key, Compare, Vector> {
270public:
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 */
289template<class Key, class Compare = std::less<Key>, class Vector = pvector<Key> >
290class ov_multiset : public ordered_vector<Key, Compare, Vector> {
291public:
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
TypeHandle is the identifier used to differentiate C++ class types.
Definition typeHandle.h:81
This template class presents an interface similar to the STL set or multiset (and ov_set and ov_multi...
reference back()
Returns a reference to the first element.
void reserve(size_type_0 n)
Informs the vector of a planned change in size; ensures that the capacity of the vector is greater th...
reference front()
Returns a reference to the first element.
size_type_0 max_size() const
Returns the maximum number of elements that can possibly be stored in an ordered vector.
const_reverse_iterator_0 crbegin() const
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
const_iterator_0 cbegin() const
Returns the iterator that marks the first element in the ordered vector.
size_type_0 count(const key_type_0 &key) const
Returns the number of elements that sort equivalent to the key that are in the vector.
const_iterator_0 cend() const
Returns the iterator that marks the end of the ordered vector.
reverse_iterator_0 rend()
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
bool operator>=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one or is equivalent,...
bool operator!=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are not memberwise equivalent, false if they are.
bool operator==(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if the two ordered vectors are memberwise equivalent, false otherwise.
void sort_unique()
Ensures that the vector is properly sorted after a potentially damaging operation.
bool operator<(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one, false otherwise.
iterator_0 begin()
Returns the iterator that marks the first element in the ordered vector.
bool operator>(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically after the other one, false otherwise.
void push_back(const value_type_0 &key)
Adds the new element to the end of the vector without regard for proper sorting.
reverse_iterator_0 rbegin()
Returns the iterator that marks the first element in the ordered vector, when viewed in reverse order...
void swap(ordered_vector< Key, Compare, Vector > &other)
Exchanges the contents of this vector and the other vector, in constant time (e.g....
bool operator<=(const ordered_vector< Key, Compare, Vector > &other) const
Returns true if this ordered vector sorts lexicographically before the other one or is equivalent,...
void sort_nonunique()
Ensures that the vector is properly sorted after a potentially damaging operation.
size_type_0 size() const
Returns the number of elements in the ordered vector.
bool empty() const
Returns true if the ordered vector is empty, false otherwise.
iterator_0 end()
Returns the iterator that marks the end of the ordered vector.
const_reverse_iterator_0 crend() const
Returns the iterator that marks the end of the ordered vector, when viewed in reverse order.
void pop_back()
Removes the last element at the end of the vector.
iterator_0 insert_unverified(iterator_0 position, const value_type_0 &key)
Inserts the indicated key into the ordered vector at the indicated place.
void clear()
Removes all elements from the ordered vector.
A specialization of ordered_vector that emulates a standard STL set: many copies of each element are ...
bool verify_list() const
Maps to verify_list_nonunique().
void sort()
Maps to sort_nonunique().
A specialization of ordered_vector that emulates a standard STL set: one copy of each element is allo...
void sort()
Maps to sort_unique().
bool verify_list() const
Maps to verify_list_unique().
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.