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