00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015 #ifndef ORDERED_VECTOR_H
00016 #define ORDERED_VECTOR_H
00017 #ifdef CPPPARSER // hack around this for interigate...
00018
00019
00020
00021
00022
00023
00024 template<class Key, class Compare = less<int> > class ov_multiset
00025 {
00026 };
00027
00028 template<class Key, class Compare = less<int> > class ov_set
00029 {
00030 };
00031
00032 template<class Key, class Compare = less<int> > class ordered_vector
00033 {
00034 };
00035
00036 #else // cppparser
00037
00038
00039 #include "pandabase.h"
00040
00041 #include "pvector.h"
00042 #include "pset.h"
00043 #include "pnotify.h"
00044 #include <algorithm>
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059 #define KEY_TYPE key_type_0
00060 #define VALUE_TYPE value_type_0
00061 #define REFERENCE reference_0
00062 #define CONST_REFERENCE const_reference_0
00063 #define KEY_COMPARE key_compare_0
00064 #define VALUE_COMPARE value_compare_0
00065 #define ITERATOR iterator_0
00066 #define CONST_ITERATOR const_iterator_0
00067 #define REVERSE_ITERATOR reverse_iterator_0
00068 #define CONST_REVERSE_ITERATOR const_reverse_iterator_0
00069 #define DIFFERENCE_TYPE difference_type_0
00070 #define SIZE_TYPE size_type_0
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108 template<class Key, class Compare = less<Key> >
00109 class ordered_vector {
00110 private:
00111 typedef pvector<Key> Vector;
00112
00113 public:
00114
00115 typedef Key KEY_TYPE;
00116 typedef Key VALUE_TYPE;
00117 typedef Key &REFERENCE;
00118 typedef const Key &CONST_REFERENCE;
00119 typedef Compare KEY_COMPARE;
00120 typedef Compare VALUE_COMPARE;
00121
00122
00123
00124
00125 typedef TYPENAME Vector::iterator ITERATOR;
00126 typedef TYPENAME Vector::const_iterator CONST_ITERATOR;
00127 typedef TYPENAME Vector::reverse_iterator REVERSE_ITERATOR;
00128 typedef TYPENAME Vector::const_reverse_iterator CONST_REVERSE_ITERATOR;
00129
00130 typedef TYPENAME Vector::difference_type DIFFERENCE_TYPE;
00131 typedef TYPENAME Vector::size_type SIZE_TYPE;
00132
00133
00134
00135
00136 typedef KEY_TYPE key_type;
00137 typedef VALUE_TYPE value_type;
00138 typedef REFERENCE reference;
00139 typedef CONST_REFERENCE const_reference;
00140 typedef KEY_COMPARE key_compare;
00141 typedef VALUE_COMPARE value_compare;
00142 typedef ITERATOR iterator;
00143 typedef CONST_ITERATOR const_iterator;
00144 typedef REVERSE_ITERATOR reverse_iterator;
00145 typedef CONST_REVERSE_ITERATOR const_reverse_iterator;
00146 typedef DIFFERENCE_TYPE difference_type;
00147 typedef SIZE_TYPE size_type;
00148
00149 public:
00150
00151
00152 INLINE ordered_vector(TypeHandle type_handle = ov_set_type_handle);
00153 INLINE ordered_vector(const Compare &compare,
00154 TypeHandle type_handle = ov_set_type_handle);
00155 INLINE ordered_vector(const ordered_vector<Key, Compare> ©);
00156 INLINE ordered_vector<Key, Compare> &operator = (const ordered_vector<Key, Compare> ©);
00157 INLINE ~ordered_vector();
00158
00159
00160 INLINE ITERATOR begin();
00161 INLINE ITERATOR end();
00162 INLINE REVERSE_ITERATOR rbegin();
00163 INLINE REVERSE_ITERATOR rend();
00164
00165 INLINE CONST_ITERATOR begin() const;
00166 INLINE CONST_ITERATOR end() const;
00167 INLINE CONST_REVERSE_ITERATOR rbegin() const;
00168 INLINE CONST_REVERSE_ITERATOR rend() const;
00169
00170
00171 INLINE reference operator [] (SIZE_TYPE n);
00172 INLINE const_reference operator [] (SIZE_TYPE n) const;
00173
00174
00175 INLINE SIZE_TYPE size() const;
00176 INLINE SIZE_TYPE max_size() const;
00177 INLINE bool empty() const;
00178
00179
00180 INLINE bool operator == (const ordered_vector<Key, Compare> &other) const;
00181 INLINE bool operator != (const ordered_vector<Key, Compare> &other) const;
00182
00183 INLINE bool operator < (const ordered_vector<Key, Compare> &other) const;
00184 INLINE bool operator > (const ordered_vector<Key, Compare> &other) const;
00185 INLINE bool operator <= (const ordered_vector<Key, Compare> &other) const;
00186 INLINE bool operator >= (const ordered_vector<Key, Compare> &other) const;
00187
00188
00189 ITERATOR insert_unique(ITERATOR position, const VALUE_TYPE &key);
00190 ITERATOR insert_nonunique(ITERATOR position, const VALUE_TYPE &key);
00191 INLINE pair<ITERATOR, bool> insert_unique(const VALUE_TYPE &key);
00192 INLINE ITERATOR insert_nonunique(const VALUE_TYPE &key);
00193 INLINE ITERATOR insert_unverified(ITERATOR position, const VALUE_TYPE &key);
00194
00195
00196 INLINE ITERATOR erase(ITERATOR position);
00197 INLINE SIZE_TYPE erase(const KEY_TYPE &key);
00198 INLINE void erase(ITERATOR first, ITERATOR last);
00199 INLINE void clear();
00200
00201
00202 INLINE ITERATOR find(const KEY_TYPE &key);
00203 INLINE CONST_ITERATOR find(const KEY_TYPE &key) const;
00204 INLINE ITERATOR find_particular(const KEY_TYPE &key);
00205 INLINE CONST_ITERATOR find_particular(const KEY_TYPE &key) const;
00206 INLINE SIZE_TYPE count(const KEY_TYPE &key) const;
00207
00208 INLINE ITERATOR lower_bound(const KEY_TYPE &key);
00209 INLINE CONST_ITERATOR lower_bound(const KEY_TYPE &key) const;
00210 INLINE ITERATOR upper_bound(const KEY_TYPE &key);
00211 INLINE CONST_ITERATOR upper_bound(const KEY_TYPE &key) const;
00212 INLINE pair<ITERATOR, ITERATOR> equal_range(const KEY_TYPE &key);
00213 INLINE pair<CONST_ITERATOR, CONST_ITERATOR> equal_range(const KEY_TYPE &key) const;
00214
00215
00216 INLINE void swap(ordered_vector<Key, Compare> &other);
00217 INLINE void reserve(SIZE_TYPE n);
00218 INLINE void sort_unique();
00219 INLINE void sort_nonunique();
00220 bool verify_list_unique() const;
00221 bool verify_list_nonunique() const;
00222
00223 INLINE void push_back(const VALUE_TYPE &key);
00224 INLINE void pop_back();
00225
00226 private:
00227 INLINE ITERATOR nci(CONST_ITERATOR i);
00228 INLINE ITERATOR find_insert_position(ITERATOR first, ITERATOR last,
00229 const KEY_TYPE &key);
00230 ITERATOR r_find_insert_position(ITERATOR first, ITERATOR last,
00231 const KEY_TYPE &key);
00232 CONST_ITERATOR r_find(CONST_ITERATOR first, CONST_ITERATOR last,
00233 CONST_ITERATOR not_found,
00234 const KEY_TYPE &key) const;
00235 CONST_ITERATOR r_find_particular(CONST_ITERATOR first, CONST_ITERATOR last,
00236 CONST_ITERATOR not_found,
00237 const KEY_TYPE &key) const;
00238 SIZE_TYPE r_count(CONST_ITERATOR first, CONST_ITERATOR last,
00239 const KEY_TYPE &key) const;
00240 CONST_ITERATOR r_lower_bound(CONST_ITERATOR first, CONST_ITERATOR last,
00241 const KEY_TYPE &key) const;
00242 CONST_ITERATOR r_upper_bound(CONST_ITERATOR first, CONST_ITERATOR last,
00243 const KEY_TYPE &key) const;
00244 pair<CONST_ITERATOR, CONST_ITERATOR>
00245 r_equal_range(CONST_ITERATOR first, CONST_ITERATOR last,
00246 const KEY_TYPE &key) const;
00247
00248
00249
00250 class EquivalentTest {
00251 public:
00252
00253
00254
00255
00256 INLINE EquivalentTest(const Compare &compare) :
00257 _compare(compare) { }
00258 INLINE bool operator () (const KEY_TYPE &a, const KEY_TYPE &b) {
00259 nassertr(!_compare(b, a), false);
00260 return !_compare(a, b);
00261 }
00262
00263 Compare _compare;
00264 };
00265
00266 Compare _compare;
00267 Vector _vector;
00268 };
00269
00270
00271
00272
00273
00274
00275
00276 template<class Key, class Compare = less<Key> >
00277 class ov_set : public ordered_vector<Key, Compare> {
00278 public:
00279 typedef TYPENAME ordered_vector<Key, Compare>::ITERATOR ITERATOR;
00280 typedef TYPENAME ordered_vector<Key, Compare>::VALUE_TYPE VALUE_TYPE;
00281
00282 INLINE ov_set(TypeHandle type_handle = ov_set_type_handle);
00283 INLINE ov_set(const Compare &compare,
00284 TypeHandle type_handle = ov_set_type_handle);
00285 INLINE ov_set(const ov_set<Key, Compare> ©);
00286 INLINE ov_set<Key, Compare> &operator = (const ov_set<Key, Compare> ©);
00287
00288 INLINE ITERATOR insert(ITERATOR position, const VALUE_TYPE &key0);
00289 INLINE pair<ITERATOR, bool> insert(const VALUE_TYPE &key0);
00290
00291 INLINE void sort();
00292 INLINE bool verify_list() const;
00293 };
00294
00295
00296
00297
00298
00299
00300
00301 template<class Key, class Compare = less<Key> >
00302 class ov_multiset : public ordered_vector<Key, Compare> {
00303 public:
00304 typedef TYPENAME ordered_vector<Key, Compare>::ITERATOR ITERATOR;
00305 typedef TYPENAME ordered_vector<Key, Compare>::VALUE_TYPE VALUE_TYPE;
00306
00307 INLINE ov_multiset(TypeHandle type_handle = ov_set_type_handle);
00308 INLINE ov_multiset(const Compare &compare,
00309 TypeHandle type_handle = ov_set_type_handle);
00310 INLINE ov_multiset(const ov_multiset<Key, Compare> ©);
00311 INLINE ov_multiset<Key, Compare> &operator = (const ov_multiset<Key, Compare> ©);
00312
00313 INLINE ITERATOR insert(ITERATOR position, const VALUE_TYPE &key);
00314 INLINE ITERATOR insert(const VALUE_TYPE &key);
00315
00316 INLINE void sort();
00317 INLINE bool verify_list() const;
00318 };
00319
00320 #include "ordered_vector.I"
00321 #include "ordered_vector.T"
00322 #endif // cppparser ..
00323 #endif