Panda3D
|
00001 // Filename: ordered_vector.h 00002 // Created by: drose (20Feb02) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #ifndef ORDERED_VECTOR_H 00016 #define ORDERED_VECTOR_H 00017 #ifdef CPPPARSER // hack around this for interigate... 00018 //****** HACK allert *** 00019 // this code is intended to tell interigate to not expand this class definition past basic names 00020 // It drops the interigate memory foot pront and user time by a bunch 00021 // on pc cygwin from 3 minutes to 17 seconds ?? really need to explore interigate to figure out what is 00022 // going on .. 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 // There are some inheritance issues with template classes and typedef 00047 // names. Template classes that inherit typedef names from their base 00048 // class, which is also a template class, may confuse the typedef 00049 // names with globally scoped template names. In particular, the 00050 // local "iterator" type is easily confused with the std::iterator 00051 // template class. 00052 00053 // To work around this problem, as well as a problem in gcc 2.95.3 00054 // with value_type etc. not inheriting properly (even though we 00055 // explicitly typedef them in the derived class), we rename the 00056 // questionable typedefs here so that they no longer conflict with the 00057 // global template classes. 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 // Class : ordered_vector 00074 // Description : This template class presents an interface similar to 00075 // the STL set or multiset (and ov_set and ov_multiset 00076 // are implemented specifically, below), but it is 00077 // implemented using a vector that is kept always in 00078 // sorted order. 00079 // 00080 // In most cases, an ov_set or ov_multiset may be 00081 // dropped in transparently in place of a set or 00082 // multiset, but the implementation difference has a few 00083 // implications: 00084 // 00085 // (1) The ov_multiset will maintain stability of order 00086 // between elements that sort equally: they are stored 00087 // in the order in which they were added, from back to 00088 // front. 00089 // 00090 // (2) Insert and erase operations into the middle of 00091 // the set can be slow, just as inserting into the 00092 // middle of a vector can be slow. In fact, building up 00093 // an ov_set by inserting elements one at a time is an 00094 // n^2 operation. On the other hand, building up an 00095 // ov_set by adding elements to the end, one at time, is 00096 // somewhat faster than building up a traditional set; 00097 // and you can even add unsorted elements with 00098 // push_back() and then call sort() when you're done, 00099 // for a log(n) operation. 00100 // 00101 // (3) Iterators may not be valid for the life of the 00102 // ordered_vector. If the vector reallocates itself, 00103 // all iterators are invalidated. 00104 // 00105 // (4) Random access into the set is easy with the [] 00106 // operator. 00107 //////////////////////////////////////////////////////////////////// 00108 template<class Key, class Compare = less<Key> > 00109 class ordered_vector { 00110 private: 00111 typedef pvector<Key> Vector; 00112 00113 public: 00114 // Typedefs 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 // Be careful when using the non-const iterators that you do not 00123 // disturb the sorted order of the vector, or that if you do, you 00124 // call sort() when you are done. 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 // Since the #define symbols do not actually expand to the correct 00134 // names, we have to re-typedef them so callers can reference them 00135 // by their correct, lowercase names. 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 // Constructors. We don't implement the whole slew of STL 00151 // constructors here yet. 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 // Iterator access. 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 // Random access. 00171 INLINE reference operator [] (SIZE_TYPE n); 00172 INLINE const_reference operator [] (SIZE_TYPE n) const; 00173 00174 // Size information. 00175 INLINE SIZE_TYPE size() const; 00176 INLINE SIZE_TYPE max_size() const; 00177 INLINE bool empty() const; 00178 00179 // Equivalence and lexicographical comparisons. 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 // Insert operations. 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 // Erase operations. 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 // Find operations. 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 // Special operations. 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 // This function object is used in sort_unique(). It returns true 00249 // if two consecutive sorted elements are equivalent. 00250 class EquivalentTest { 00251 public: 00252 // For some reason, VC++ won't allow us to define these bodies 00253 // outside the class; they must be defined here. The error 00254 // message is C3206: "member functions of nested classes of a 00255 // template class cannot be defined outside the class". 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 // Class : ov_set 00272 // Description : A specialization of ordered_vector that emulates a 00273 // standard STL set: one copy of each element is 00274 // allowed. 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 // Class : ov_multiset 00297 // Description : A specialization of ordered_vector that emulates a 00298 // standard STL set: many copies of each element are 00299 // allowed. 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