arrays.h

Go to the documentation of this file.
00001 /** @file rutz/arrays.h STL-style array classes similar to std::vector
00002     but much more lightweight */
00003 
00004 ///////////////////////////////////////////////////////////////////////
00005 //
00006 // Copyright (c) 2000-2004 California Institute of Technology
00007 // Copyright (c) 2004-2007 University of Southern California
00008 // Rob Peters <rjpeters at usc dot edu>
00009 //
00010 // created: Mon Mar  6 15:56:36 2000
00011 // commit: $Id: arrays.h 8249 2007-04-12 06:03:40Z rjpeters $
00012 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/rutz/arrays.h $
00013 //
00014 // --------------------------------------------------------------------
00015 //
00016 // This file is part of GroovX.
00017 //   [http://ilab.usc.edu/rjpeters/groovx/]
00018 //
00019 // GroovX is free software; you can redistribute it and/or modify it
00020 // under the terms of the GNU General Public License as published by
00021 // the Free Software Foundation; either version 2 of the License, or
00022 // (at your option) any later version.
00023 //
00024 // GroovX is distributed in the hope that it will be useful, but
00025 // WITHOUT ANY WARRANTY; without even the implied warranty of
00026 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00027 // General Public License for more details.
00028 //
00029 // You should have received a copy of the GNU General Public License
00030 // along with GroovX; if not, write to the Free Software Foundation,
00031 // Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
00032 //
00033 ///////////////////////////////////////////////////////////////////////
00034 
00035 #ifndef GROOVX_RUTZ_ARRAYS_H_UTC20050626084020_DEFINED
00036 #define GROOVX_RUTZ_ARRAYS_H_UTC20050626084020_DEFINED
00037 
00038 #include "rutz/algo.h"
00039 #include "rutz/atomic.h"
00040 
00041 #include <cstddef>
00042 
00043 namespace rutz
00044 {
00045   /// Exception class for range errors.
00046   /** Used in static_block, fixed_block, dynamic_block. */
00047   class out_of_range {};
00048 
00049   /// Get a pointer to the beginning of a C-style array.
00050   template<class T, std::size_t N>
00051   T* array_begin(T (&array)[N])
00052   {
00053     return &array[0];
00054   }
00055 
00056   /// Get a pointer to the one-past-the-end of a C-style array.
00057   template<class T, std::size_t N>
00058   T* array_end(T (&array)[N])
00059   {
00060     return &array[0]+N;
00061   }
00062 
00063   /// Get a pointer to the beginning of a C-style const array.
00064   template<class T, std::size_t N>
00065   const T* array_begin(T const (&array)[N])
00066   {
00067     return &array[0];
00068   }
00069 
00070   /// Get a pointer to the one-past-the-end of a C-style const array.
00071   template<class T, std::size_t N>
00072   const T* array_end(T const (&array)[N])
00073   {
00074     return &array[0]+N;
00075   }
00076 
00077 
00078   //  #######################################################
00079   //  =======================================================
00080 
00081   /// A simple wrapper around a C-style array.
00082   /** \c static_block provides an STL-style container interface,
00083       including both checked and unchecked access, as well as access
00084       to the container's size with the \c size() member function. */
00085 
00086   template <class T, size_t N>
00087   struct static_block
00088   {
00089     typedef T value_type;                     ///< STL value type.
00090 
00091     typedef T* pointer;                       ///< STL pointer type.
00092     typedef const T* const_pointer;           ///< STL const pointer type.
00093     typedef T& reference ;                    ///< STL reference type.
00094     typedef const T& const_reference;         ///< STL const reference type.
00095 
00096     typedef pointer iterator;                 ///< STL iterator type.
00097     typedef const_pointer const_iterator;     ///< STL const iterator type.
00098 
00099     typedef size_t size_type;                 ///< STL size type.
00100     typedef ptrdiff_t difference_type;        ///< STL iterator difference type.
00101 
00102     iterator begin() { return data; }         ///< Iterator to array start.
00103     iterator end() { return data+N; }         ///< Iterator to array one-past-the-end.
00104 
00105     const_iterator begin() const { return data; } ///< Const iterator to array start.
00106     const_iterator end() const { return data+N; } ///< Const iterator to array one-past-the-end.
00107 
00108     /// Unchecked non-const array index.
00109     reference operator[](size_type n) { return data[n]; }
00110 
00111     /// Unchecked const array index.
00112     const_reference operator[](size_type n) const { return data[n]; }
00113 
00114     /// Checked non-const array index (rutz::out_of_range on bounds error).
00115     reference at(size_type n)
00116     {
00117       if ( n >= N )
00118         throw rutz::out_of_range();
00119       return data[n];
00120     }
00121 
00122     /// Checked const array index (rutz::out_of_range on bounds error).
00123     const_reference at(size_type n) const
00124     {
00125       if ( n >= N )
00126         throw rutz::out_of_range();
00127       return data[n];
00128     }
00129 
00130     /// Size of array.
00131     size_type size() const { return N; }
00132 
00133     /// Maximum size of array type.
00134     size_type max_size() const { return size_type(-1) / sizeof(T); }
00135 
00136     /// Query whether size is zero.
00137     bool is_empty() const { return (N == 0); }
00138 
00139     /// Swap data with another array.
00140     /** This requires an element-by-element swap. */
00141     void swap(static_block& other)
00142     {
00143       rutz::swap2(*this, other);
00144     }
00145 
00146     T data[N];
00147   };
00148 
00149 
00150   //  #######################################################
00151   //  =======================================================
00152 
00153   /// A dynamically-allocated array whose size is fixed at construction.
00154   /** Copying and assignment are not  allowed. */
00155 
00156   template <class T>
00157   class fixed_block
00158   {
00159   private:
00160     fixed_block(const fixed_block<T>& other);
00161 
00162     fixed_block<T>& operator=(const fixed_block<T>& other);
00163 
00164     template <class Itr>
00165     void assign(Itr thatitr, Itr thatend)
00166     {
00167       iterator thisitr = begin(), thisend = end();
00168 
00169       while (thatitr != thatend && thisitr != thisend)
00170         {
00171           *thisitr = *thatitr;
00172           ++thisitr;
00173           ++thatitr;
00174         }
00175     }
00176 
00177   public:
00178     typedef T value_type;                     ///< STL value type.
00179 
00180     typedef T* pointer;                       ///< STL pointer type.
00181     typedef const T* const_pointer;           ///< STL const pointer type.
00182     typedef T& reference ;                    ///< STL reference type.
00183     typedef const T& const_reference;         ///< STL const reference type.
00184 
00185     typedef pointer iterator;                 ///< STL iterator type.
00186     typedef const_pointer const_iterator;     ///< STL const iterator type.
00187 
00188     typedef size_t size_type;                 ///< STL size type.
00189     typedef ptrdiff_t difference_type;        ///< STL iterator difference type.
00190 
00191     /// Construct with a given size.
00192     fixed_block(size_type n) : N(n), data(new T[N]) {}
00193 
00194     /// Destructor.
00195     ~fixed_block() { delete [] data; }
00196 
00197     /// Construct by copying from a given iterator range.
00198     template <class Itr>
00199     fixed_block(Itr itr, Itr end) : N(end-itr), data(new T[N])
00200     {
00201       assign(itr, end);
00202     }
00203 
00204     iterator begin() { return data; }         ///< Iterator to array start.
00205     iterator end() { return data+N; }         ///< Iterator to array one-past-the-end.
00206 
00207     const_iterator begin() const { return data; } ///< Const iterator to array start.
00208     const_iterator end() const { return data+N; } ///< Const iterator to array one-past-the-end.
00209 
00210     /// Unchecked non-const array index.
00211     reference operator[](size_type n) { return data[n]; }
00212 
00213     /// Unchecked const array index.
00214     const_reference operator[](size_type n) const { return data[n]; }
00215 
00216     /// Checked non-const array index (rutz::out_of_range thrown on bounds error).
00217     reference at(size_type n)
00218     {
00219       if ( n >= N )
00220         throw rutz::out_of_range();
00221       return data[n];
00222     }
00223 
00224     /// Checked const array index (rutz::out_of_range thrown on bounds error).
00225     const_reference at(size_type n) const
00226     {
00227       if ( n >= N )
00228         throw rutz::out_of_range();
00229       return data[n];
00230     }
00231 
00232     /// Size of array.
00233     size_type size() const { return N; }
00234 
00235     /// Maximum size of array type.
00236     size_type max_size() const { return size_type(-1) / sizeof(T); }
00237 
00238     /// Query whether size is zero.
00239     bool is_empty() const { return (N == 0); }
00240 
00241     /// Swap with another fixed_block.
00242     /** This is fast since it only requires swapping the interal
00243         pointers to the dynamically-allocated arrays; no element-wise
00244         swap is needed. */
00245     void swap(fixed_block& other)
00246     {
00247       rutz::swap2(N,    other.N);
00248       rutz::swap2(data, other.data);
00249     }
00250 
00251   private:
00252     size_type N;
00253     T* data;
00254   };
00255 
00256 
00257   //  #######################################################
00258   //  =======================================================
00259 
00260   /// A reference-counted smart pointer for arrays.
00261 
00262   /** The array pointed to is deleted when the last shared_array
00263       pointing to it is destroyed or reset. */
00264 
00265   template<typename T>
00266   class shared_array
00267   {
00268   public:
00269     /// The pointed-to type.
00270     typedef T element_type;
00271 
00272     /// Construct with the given array pointer.
00273     /** Ownership is now unconditionally transferred to the
00274         shared_array. If the shared_array constructor causes an
00275         exception, the pointed-to array will be destroyed. */
00276     explicit shared_array(T* p =0) : px(p)
00277     {
00278       try { pn = new rutz::atomic_int_t; pn->atomic_set(1); }
00279       catch (...) { delete [] p; throw; }  // don't leak p if new throws
00280     }
00281 
00282     /// Copy constructor.
00283     shared_array(const shared_array& r) throw() : px(r.px), pn(r.pn)
00284     { pn->atomic_incr(); }
00285 
00286     /// Destructor.
00287     ~shared_array()
00288     {
00289       if (pn->atomic_decr_test_zero())
00290         {
00291           delete [] px; px = 0;
00292           delete pn;    pn = 0;
00293         }
00294     }
00295 
00296     /// Assignment oeprator.
00297     shared_array& operator=(const shared_array& r)
00298     {
00299       if (pn != r.pn) // Q: why not px != r.px? A: fails when both px == 0
00300         shared_array(r).swap(*this);
00301       return *this;
00302     }
00303 
00304     /// Reset to point to a new array.
00305     void reset(T* p=0)
00306     {
00307       if (px != p) // self-assignment safe
00308         shared_array(p).swap(*this);
00309     }
00310 
00311     /// Get a pointer to the pointed-to array.
00312     T* get() const                     throw() { return px; }
00313 
00314     /// Index into the pointed-to array.
00315     T& operator[](std::size_t i) const throw() { return px[i]; }
00316 
00317     /// Get the reference count of the shared array.
00318     long use_count() const             throw() { return pn->atomic_get(); }
00319 
00320     /// Query whether the shared array is uniquely owned (i.e. refcount == 1).
00321     bool unique() const                throw() { return use_count() == 1; }
00322 
00323     /// Swap pointees with another shared_array.
00324     void swap(shared_array<T>& other) throw()
00325     { rutz::swap2(px,other.px); rutz::swap2(pn,other.pn); }
00326 
00327   private:
00328     T*                   px;     // contained pointer
00329     rutz::atomic_int_t*  pn;     // ptr to reference counter
00330   };  // shared_array
00331 
00332   /// Equality for shared_array; returns true if both have the same pointee.
00333   template<typename T>
00334   inline bool operator==(const shared_array<T>& a, const shared_array<T>& b)
00335   { return a.get() == b.get(); }
00336 
00337   /// Inequality for shared_array; returns true if each has different pointees.
00338   template<typename T>
00339   inline bool operator!=(const shared_array<T>& a, const shared_array<T>& b)
00340   { return a.get() != b.get(); }
00341 
00342 
00343 
00344   //  #######################################################
00345   //  =======================================================
00346 
00347   /// A dynamically-allocated array whose size may be changed at runtime.
00348 
00349   template <class T>
00350   class dynamic_block
00351   {
00352   public:
00353     typedef T value_type;                     ///< STL value type.
00354 
00355     typedef T* pointer;                       ///< STL pointer type.
00356     typedef const T* const_pointer;           ///< STL const pointer type.
00357     typedef T& reference ;                    ///< STL reference type.
00358     typedef const T& const_reference;         ///< STL const reference type.
00359 
00360     typedef pointer iterator;                 ///< STL iterator type.
00361     typedef const_pointer const_iterator;     ///< STL const iterator type.
00362 
00363     typedef size_t size_type;                 ///< STL size type.
00364     typedef ptrdiff_t difference_type;        ///< STL iterator difference type.
00365 
00366     /// Construct with a given size.
00367     dynamic_block(size_type n = 0) : N(n), data(new T[N]) {}
00368 
00369     /// Copy construct.
00370     dynamic_block(const dynamic_block<T>& other) :
00371       N(other.N), data(new T[N])
00372     {
00373       assign_varsize(other, *this);
00374     }
00375 
00376     /// Assignment operator.
00377     dynamic_block<T>& operator=(const dynamic_block<T>& other)
00378     {
00379       dynamic_block temp(other);
00380       this->swap(temp);
00381       return *this;
00382     }
00383 
00384     /// Destructor.
00385     ~dynamic_block() { delete [] data; }
00386 
00387     iterator begin() { return data; }         ///< Iterator to array start.
00388     iterator end() { return data+N; }         ///< Iterator to array one-past-the-end.
00389 
00390     const_iterator begin() const { return data; } ///< Const iterator to array start.
00391     const_iterator end() const { return data+N; } ///< Const iterator to array one-past-the-end.
00392 
00393     /// Unchecked non-const array index.
00394     reference operator[](size_type n) { return data[n]; }
00395 
00396     /// Unchecked const array index.
00397     const_reference operator[](size_type n) const { return data[n]; }
00398 
00399     /// Checked non-const array index (rutz::out_of_range on bounds error).
00400     reference at(size_type n)
00401     {
00402       if ( n >= N )
00403         throw rutz::out_of_range();
00404       return data[n];
00405     }
00406 
00407     /// Checked const array index (rutz::out_of_range on bounds error).
00408     const_reference at(size_type n) const
00409     {
00410       if ( n >= N )
00411         throw rutz::out_of_range();
00412       return data[n];
00413     }
00414 
00415     /// Size of array.
00416     size_type size() const { return N; }
00417 
00418     /// Maximum size of array type.
00419     size_type max_size() const { return size_type(-1) / sizeof(T); }
00420 
00421     /// Query whether size is zero.
00422     bool is_empty() const { return (N == 0); }
00423 
00424     /// Swap with another dynamic_block.
00425     /** This is fast since it only requires swapping the interal
00426         pointers to the dynamically-allocated arrays; no element-wise
00427         swap is needed. */
00428     void swap(dynamic_block& other)
00429     {
00430       rutz::swap2(N,    other.N);
00431       rutz::swap2(data, other.data);
00432     }
00433 
00434     /// Resize to a new size.
00435     void resize(size_type new_size)
00436     {
00437       dynamic_block temp(new_size);
00438       assign_varsize(*this, temp);
00439       this->swap(temp);
00440     }
00441 
00442     /// Assign from a given iterator range.
00443     template <class RandomAccessIterator>
00444     void assign(RandomAccessIterator start, RandomAccessIterator finish)
00445     {
00446       int num = finish-start;
00447       if (num < 0)
00448         {
00449           resize(0);
00450           return;
00451         }
00452       resize(num);
00453       iterator ii = begin();
00454       while (start != finish)
00455         {
00456           *ii = *start;
00457           ++ii;
00458           ++start;
00459         }
00460     }
00461 
00462   private:
00463     /// Assign one dynamic_block to another whose sizes may differ.
00464     static void assign_varsize(const dynamic_block& b_from,
00465                                dynamic_block& b_to)
00466     {
00467       const_iterator from = b_from.begin();
00468       iterator to = b_to.begin();
00469 
00470       while(from != b_from.end() && to != b_to.end())
00471         {
00472           *to++ = *from++;
00473         }
00474     }
00475 
00476     size_type N;
00477     T* data;
00478   };
00479 }
00480 
00481 static const char __attribute__((used)) vcid_groovx_rutz_arrays_h_utc20050626084020[] = "$Id: arrays.h 8249 2007-04-12 06:03:40Z rjpeters $ $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/rutz/arrays.h $";
00482 #endif // !GROOVX_RUTZ_ARRAYS_H_UTC20050626084020_DEFINED
Generated on Sun May 8 08:42:08 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3