Collection.hpp

Go to the documentation of this file.
00001 #ifndef COLLECTION_HPP__
00002 #define COLLECTION_HPP__
00003 
00004 #include "TObjArray.h"
00005 #include <iterator>
00006 #include <cassert>
00007 
00008 namespace cafe {
00009 
00024     template<class T>
00025     class Collection {
00026     public:
00027         typedef T      value_type;
00028         typedef size_t size_type;
00029         typedef T*     pointer_type;
00030         typedef T&     reference_type;
00031         typedef const T* const_pointer_type;
00032         typedef const T& const_reference_type;
00033     public:
00036         Collection(TObjArray *data)
00037             : _data(0)
00038         {
00039             if (data)
00040                 _data = (new array_holder(data, false));
00041             else
00042                 _data = (new array_holder(new TObjArray(), true));
00043         }
00044 
00047         Collection(const Collection<T>& other)
00048             : _data(other._data)
00049         {
00050             _data->inc();
00051         }
00054         Collection(void)
00055             : _data (new array_holder(new TObjArray(), true))
00056         {}
00057 
00059         virtual ~Collection() {
00060             _data->decAndDeleteIf();
00061         }
00062 
00064         Collection<T>& operator=(const Collection<T>& other) 
00065         {
00066             if(&other != this) {
00067                 _data->decAndDeleteIf();
00068                 _data = other._data;
00069                 _data->inc();
00070             }
00071             return *this;
00072         }
00073 
00077         void push_back (const T& item)
00078         {
00079             assert(item.IsOnHeap());
00080             make_us_owner_of_data();
00081             (*_data)->Add(const_cast<T*>(&item));
00082         }
00083 
00086         void push_back(T *item)
00087         {
00088             make_us_owner_of_data();
00089             (*_data)->Add(item);
00090         }
00091 
00093         const T& operator[](size_t index) const { return *static_cast<T*>((*_data)->At(index)); }
00094 
00096 
00097         class iterator;
00098         class const_iterator;
00099 
00101         iterator begin() { return iterator(*_data, 0); }
00102         const_iterator begin() const { return const_iterator(*_data, 0); }
00103 
00105         iterator end()   { return iterator(*_data, *_data ? (*_data)->GetLast() + 1 : 0); }
00106         const_iterator end()   const { return const_iterator(*_data, (*_data) ? (*_data)->GetLast() + 1 : 0); }
00107 
00109         iterator erase(iterator it) 
00110         { 
00111             int i = it._index;
00112             make_us_owner_of_data();
00113             (*_data)->RemoveAt(i);
00114             (*_data)->Compress();
00115             return iterator((*_data), i);
00116         }
00117 
00119         iterator erase(iterator first, iterator last)
00120         {
00121             int i = first._index;
00122             make_us_owner_of_data();
00123             while(i != last._index) {
00124                 (*_data)->RemoveAt(i);
00125                 ++i;
00126             }
00127             (*_data)->Compress();
00128             return iterator((*_data),first._index);
00129         }
00130 
00132         
00134         size_t size() const { return _data ? (*_data)->GetLast() + 1 : 0; }
00135 
00146         template <typename compare>
00147         void sort(iterator from, iterator to, compare CompFun)
00148         {
00149             make_us_owner_of_data();
00150             full_sort(*(*_data),from._index,to._index,CompFun);
00151             return;
00152         } 
00153 
00155         class iterator : public std::iterator<std::random_access_iterator_tag, T> {
00156         public:
00157             iterator() : _data(0), _index(0) {}
00158             iterator(const iterator& other) : _data(other._data), _index(other._index) {}
00159             iterator& operator=(const iterator& other)
00160             {
00161                 if(this != &other) {
00162                     _data  = other._data;
00163                     _index = other._index;
00164                 }
00165                 return *this;
00166             }
00167 
00168             reference_type operator*() const { return *static_cast<T*>(_data->At(_index)); }
00169             pointer_type operator->() const { return static_cast<T*>(_data->At(_index)); }
00170 
00171             iterator& operator++()    { _index++; return *this; }
00172             iterator  operator++(int) { iterator  result(*this); _index++; return result; }
00173 
00174             iterator& operator--()    { _index--; return *this; }
00175             iterator  operator--(int) { iterator  result(*this); _index--; return result; }
00176 
00177             iterator operator+(size_t offset) const { return iterator(_data, _index + offset); }
00178             iterator operator-(size_t offset) const { return iterator(_data, _index - offset); }
00179 
00180             // template horror ahead
00181             typename std::iterator<std::random_access_iterator_tag, T>::difference_type 
00182             operator-(const iterator& other) const { return _index - other._index; }
00183 
00184             typename std::iterator<std::random_access_iterator_tag, T>::difference_type 
00185             operator+(const iterator& other) const { return _index + other._index; }
00186 
00187             iterator& operator+=(size_t offset) { _index += offset; return *this; }
00188             iterator& operator-=(size_t offset) { _index -= offset; return *this; }
00189 
00190             bool operator<(const iterator& other)  const{ return _index < other._index; }
00191             bool operator!=(const iterator& other) const { return _index != other._index; }
00192 
00193         private:
00194             friend class Collection;
00195             friend class const_iterator;
00196             iterator(TObjArray* data, int index = 0) : _data(data), _index(index) {}
00197         
00198             const TObjArray *_data;
00199             int             _index;
00200         };
00201 
00205         typedef iterator cafe_collection_iterator;
00206 
00208         class const_iterator : public std::iterator<std::random_access_iterator_tag, T> {
00209         public:
00210             const_iterator() : _data(0), _index(0) {}
00211             const_iterator(const const_iterator& other) : _data(other._data), _index(other._index) {}
00212             const_iterator(const cafe_collection_iterator& other) : _data(other._data), _index(other._index) {}
00213             const_iterator& operator=(const const_iterator& other)
00214             {
00215                 if(this != &other) {
00216                     _data  = other._data;
00217                     _index = other._index;
00218                 }
00219                 return *this;
00220             }
00221 
00222             const_reference_type operator*() const { return *static_cast<const T*>(_data->At(_index)); }
00223             const_pointer_type operator->() const { return static_cast<const T*>(_data->At(_index)); }
00224 
00225             const_iterator& operator++()    { _index++; return *this; }
00226             const_iterator  operator++(int) { const_iterator  result(*this); _index++; return result; }
00227 
00228             const_iterator& operator--()    { _index--; return *this; }
00229             const_iterator  operator--(int) { const_iterator  result(*this); _index--; return result; }
00230 
00231             const_iterator operator+(size_t offset) const { return const_iterator(_data, _index + offset); }
00232             const_iterator operator-(size_t offset) const { return const_iterator(_data, _index - offset); }
00233 
00234             // template horror ahead
00235             typename std::iterator<std::random_access_iterator_tag, T>::difference_type 
00236             operator-(const const_iterator& other) const { return _index - other._index; }
00237 
00238             typename std::iterator<std::random_access_iterator_tag, T>::difference_type 
00239             operator+(const const_iterator& other) const { return _index + other._index; }
00240 
00241             const_iterator& operator+=(size_t offset) { _index += offset; return *this; }
00242             const_iterator& operator-=(size_t offset) { _index -= offset; return *this; }
00243 
00244             bool operator<(const const_iterator& other)  const{ return _index < other._index; }
00245             bool operator!=(const const_iterator& other) const { return _index != other._index; }
00246 
00247         private:
00248             friend class Collection;
00249             const_iterator(const TObjArray* data, int index = 0) : _data(data), _index(index) {}
00250         
00251             const TObjArray *_data;
00252             int             _index;
00253         };
00254 
00257         class array_holder {
00258         public:
00259             inline array_holder (TObjArray *obj, bool owned)
00260                 : _array (obj), _count(1), _owned(owned)
00261             {}
00262             inline ~array_holder (void) {
00263                 if (_owned) {
00264                     delete _array;
00265                 }
00266             }
00267 
00268             TObjArray * operator->() {return _array;}
00269             operator TObjArray*() {return _array;}
00270             operator bool () {return _array != 0;}
00271 
00272             inline void inc (void) {
00273                 _count++;
00274             }
00275             inline void dec (void) {
00276                 _count--;
00277             }
00278             inline void decAndDeleteIf (void) {
00279                 dec();
00280                 if (!ownersLeft()) {
00281                     delete this;
00282                 }
00283             }
00284             inline bool ownersLeft (void) {
00285                 return _count != 0;
00286             }
00287             inline bool isOwned (void) {
00288                 return _owned;
00289             }
00290         private:
00291             TObjArray *_array;
00292             int        _count;
00293             bool       _owned;
00294         };
00295     private:
00298         array_holder *_data; 
00299 
00302         void make_us_owner_of_data (void)
00303         {
00304             if (_data->isOwned()) {
00305                 return;
00306             }
00307             TObjArray *t = new TObjArray (*(*_data));
00308             _data->decAndDeleteIf();
00309             _data = new array_holder (t, true);
00310         }
00311 
00312         // Sorting routines.
00313         // The insert_sort routine does a simple insertion sort. This is used by the
00314         // full_sort method for small Collections.
00315         template <typename compare>
00316         void insert_sort(TObjArray& array, int const from, int const to, compare CompFun)
00317         {
00318             int j = 0;
00319             TObject* tmp;
00320 
00321             for (int i = from; i != to; ++i) {
00322                 j   = i;
00323                 tmp = array.At(j);
00324                 while ((j>from) &&
00325                        !CompFun(*static_cast<T const*>(array.At(j-1)),*static_cast<T const*>(tmp))) {
00326                     array[j] = array.At(j-1);
00327                     --j;
00328                 } // while
00329                 array[j] = tmp;
00330             } // for
00331             return;
00332         } // insert_sort
00333 
00334         // The partial_quicksort does quicksort for Collections larger than insertSortMax entries.
00335         // It is called by full_sort.
00336         template <typename compare>
00337         void partial_quicksort(TObjArray& array, int indLow, int indHigh, compare CompFun)
00338         {
00339 
00340             const int insertSortMax = 8;
00341             int i = 0;
00342             int j = 0;
00343             int indTurn = 0;
00344             TObject const* turn = NULL;
00345 
00346             if ((indHigh - indLow) > insertSortMax) {
00347                 indTurn = (indLow+indHigh)/2;
00348                 turn = array.At(indTurn);
00349                 i = indLow;
00350                 j = indHigh-1;
00351 
00352                 swap(array,indTurn,indHigh);
00353 
00354                 // This may not be very nice but we'll use an infinite loop
00355                 // which we will exit via breaks.
00356                 while (true) {
00357                     while (!CompFun(*static_cast<T const*>(array.At(i)),*static_cast<T const*>(turn)) &&
00358                            (i<=j)) {
00359                         ++i;
00360                     }
00361                     while (CompFun(*static_cast<T const*>(array.At(j)),*static_cast<T const*>(turn)) &&
00362                            (i<j)) {
00363                         --j;
00364                     }
00365                     if (j<=i) {
00366                         break;
00367                     }
00368                     swap(array,i,j);
00369 
00370                 } // while (infinite loop)
00371                 swap(array,indHigh,j);
00372 
00373                 partial_quicksort(array,indLow,j-1,CompFun);
00374                 partial_quicksort(array,j+1,indHigh,CompFun);
00375             } // if (insert_sort or quicksort)
00376 
00377             return;
00378         } 
00379 
00380         // This is the sorting routine for Collections. It does insertion sort for
00381         // small Collections and quicksort for larger ones.
00382         template <typename compare>
00383         void full_sort(TObjArray& array, int const from, int const to, compare CompFun)
00384         {
00385             // First do a rough sort using partial_quicksort,
00386             // then finish things by sorting the remaining bits
00387             // using insert_sort.
00388             partial_quicksort(array,from,to-1,CompFun);
00389             insert_sort(array,from,to,CompFun);
00390             return;
00391         } 
00392 
00393         // The swap routine is a helper for the sorting methods.
00394         void swap(TObjArray& array, int i, int j)
00395         {
00396             TObject* tmp = array.At(i);
00397             array[i] = array.At(j);
00398             array[j] = tmp;
00399             return;
00400         }
00401 
00402     public:
00403         ClassDef(Collection, 0);
00404     };
00405 
00406 }
00407 
00408 #endif // COLLECTION_HPP__

Generated on Thu Apr 3 04:14:22 2008 for CAF by doxygen 1.3.4