Panda3D

ordered_vector.h

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> &copy);
00156   INLINE ordered_vector<Key, Compare> &operator = (const ordered_vector<Key, Compare> &copy);
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> &copy);
00286   INLINE ov_set<Key, Compare> &operator = (const ov_set<Key, Compare> &copy);
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> &copy);
00311   INLINE ov_multiset<Key, Compare> &operator = (const ov_multiset<Key, Compare> &copy);
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
 All Classes Functions Variables Enumerations