Boost.uBlas 1.49
Linear Algebra in C++: matrices, vectors and numeric algorithms

storage.hpp

Go to the documentation of this file.
00001 //
00002 //  Copyright (c) 2000-2002
00003 //  Joerg Walter, Mathias Koch
00004 //
00005 //  Distributed under the Boost Software License, Version 1.0. (See
00006 //  accompanying file LICENSE_1_0.txt or copy at
00007 //  http://www.boost.org/LICENSE_1_0.txt)
00008 //
00009 //  The authors gratefully acknowledge the support of
00010 //  GeNeSys mbH & Co. KG in producing this work.
00011 //
00012 
00013 #ifndef BOOST_UBLAS_STORAGE_H
00014 #define BOOST_UBLAS_STORAGE_H
00015 
00016 #include <algorithm>
00017 #ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
00018 #include <boost/shared_array.hpp>
00019 #endif
00020 
00021 #include <boost/serialization/array.hpp>
00022 #include <boost/serialization/collection_size_type.hpp>
00023 #include <boost/serialization/nvp.hpp>
00024 
00025 #include <boost/numeric/ublas/exception.hpp>
00026 #include <boost/numeric/ublas/traits.hpp>
00027 #include <boost/numeric/ublas/detail/iterator.hpp>
00028 
00029 
00030 namespace boost { namespace numeric { namespace ublas {
00031 
00032 
00033     // Base class for Storage Arrays - see the Barton Nackman trick
00034     template<class E>
00035     class storage_array:
00036         private nonassignable {
00037     };
00038 
00039 
00040     // Unbounded array - with allocator
00041     template<class T, class ALLOC>
00042     class unbounded_array:
00043         public storage_array<unbounded_array<T, ALLOC> > {
00044 
00045         typedef unbounded_array<T, ALLOC> self_type;
00046     public:
00047         typedef ALLOC allocator_type;
00048         typedef typename ALLOC::size_type size_type;
00049         typedef typename ALLOC::difference_type difference_type;
00050         typedef T value_type;
00051         typedef const T &const_reference;
00052         typedef T &reference;
00053         typedef const T *const_pointer;
00054         typedef T *pointer;
00055         typedef const_pointer const_iterator;
00056         typedef pointer iterator;
00057 
00058         // Construction and destruction
00059         explicit BOOST_UBLAS_INLINE
00060         unbounded_array (const ALLOC &a = ALLOC()):
00061             alloc_ (a), size_ (0) {
00062             data_ = 0;
00063         }
00064         explicit BOOST_UBLAS_INLINE
00065         unbounded_array (size_type size, const ALLOC &a = ALLOC()):
00066             alloc_(a), size_ (size) {
00067           if (size_) {
00068               data_ = alloc_.allocate (size_);
00069               if (! detail::has_trivial_constructor<T>::value) {
00070                   for (pointer d = data_; d != data_ + size_; ++d)
00071                       alloc_.construct(d, value_type());
00072               }
00073           }
00074           else
00075               data_ = 0;
00076         }
00077         // No value initialised, but still be default constructed
00078         BOOST_UBLAS_INLINE
00079         unbounded_array (size_type size, const value_type &init, const ALLOC &a = ALLOC()):
00080             alloc_ (a), size_ (size) {
00081             if (size_) {
00082                 data_ = alloc_.allocate (size_);
00083                 std::uninitialized_fill (begin(), end(), init);
00084             }
00085             else
00086                 data_ = 0;
00087         }
00088         BOOST_UBLAS_INLINE
00089         unbounded_array (const unbounded_array &c):
00090             storage_array<unbounded_array<T, ALLOC> >(),
00091             alloc_ (c.alloc_), size_ (c.size_) {
00092             if (size_) {
00093                 data_ = alloc_.allocate (size_);
00094                 std::uninitialized_copy (c.begin(), c.end(), begin());
00095             }
00096             else
00097                 data_ = 0;
00098         }
00099         BOOST_UBLAS_INLINE
00100         ~unbounded_array () {
00101             if (size_) {
00102                 if (! detail::has_trivial_destructor<T>::value) {
00103                     // std::_Destroy (begin(), end(), alloc_);
00104                     const iterator i_end = end();
00105                     for (iterator i = begin (); i != i_end; ++i) {
00106                         iterator_destroy (i); 
00107                     }
00108                 }
00109                 alloc_.deallocate (data_, size_);
00110             }
00111         }
00112 
00113         // Resizing
00114     private:
00115         BOOST_UBLAS_INLINE
00116         void resize_internal (const size_type size, const value_type init, const bool preserve) {
00117             if (size != size_) {
00118                 pointer p_data = data_;
00119                 if (size) {
00120                     data_ = alloc_.allocate (size);
00121                     if (preserve) {
00122                         pointer si = p_data;
00123                         pointer di = data_;
00124                         if (size < size_) {
00125                             for (; di != data_ + size; ++di) {
00126                                 alloc_.construct (di, *si);
00127                                 ++si;
00128                             }
00129                         }
00130                         else {
00131                             for (pointer si = p_data; si != p_data + size_; ++si) {
00132                                 alloc_.construct (di, *si);
00133                                 ++di;
00134                             }
00135                             for (; di != data_ + size; ++di) {
00136                                 alloc_.construct (di, init);
00137                             }
00138                         }
00139                     }
00140                     else {
00141                         if (! detail::has_trivial_constructor<T>::value) {
00142                             for (pointer di = data_; di != data_ + size; ++di)
00143                                 alloc_.construct (di, value_type());
00144                         }
00145                     }
00146                 }
00147 
00148                 if (size_) {
00149                     if (! detail::has_trivial_destructor<T>::value) {
00150                         for (pointer si = p_data; si != p_data + size_; ++si)
00151                             alloc_.destroy (si);
00152                     }
00153                     alloc_.deallocate (p_data, size_);
00154                 }
00155 
00156                 if (!size)
00157                     data_ = 0;
00158                 size_ = size;
00159             }
00160         }
00161     public:
00162         BOOST_UBLAS_INLINE
00163         void resize (size_type size) {
00164             resize_internal (size, value_type (), false);
00165         }
00166         BOOST_UBLAS_INLINE
00167         void resize (size_type size, value_type init) {
00168             resize_internal (size, init, true);
00169         }
00170                     
00171         // Random Access Container
00172         BOOST_UBLAS_INLINE
00173         size_type max_size () const {
00174             return ALLOC ().max_size();
00175         }
00176         
00177         BOOST_UBLAS_INLINE
00178         bool empty () const {
00179             return size_ == 0;
00180         }
00181             
00182         BOOST_UBLAS_INLINE
00183         size_type size () const {
00184             return size_;
00185         }
00186 
00187         // Element access
00188         BOOST_UBLAS_INLINE
00189         const_reference operator [] (size_type i) const {
00190             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00191             return data_ [i];
00192         }
00193         BOOST_UBLAS_INLINE
00194         reference operator [] (size_type i) {
00195             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00196             return data_ [i];
00197         }
00198 
00199         // Assignment
00200         BOOST_UBLAS_INLINE
00201         unbounded_array &operator = (const unbounded_array &a) {
00202             if (this != &a) {
00203                 resize (a.size_);
00204                 std::copy (a.data_, a.data_ + a.size_, data_);
00205             }
00206             return *this;
00207         }
00208         BOOST_UBLAS_INLINE
00209         unbounded_array &assign_temporary (unbounded_array &a) {
00210             swap (a);
00211             return *this;
00212         }
00213 
00214         // Swapping
00215         BOOST_UBLAS_INLINE
00216         void swap (unbounded_array &a) {
00217             if (this != &a) {
00218                 std::swap (size_, a.size_);
00219                 std::swap (data_, a.data_);
00220             }
00221         }
00222         BOOST_UBLAS_INLINE
00223         friend void swap (unbounded_array &a1, unbounded_array &a2) {
00224             a1.swap (a2);
00225         }
00226 
00227         BOOST_UBLAS_INLINE
00228         const_iterator begin () const {
00229             return data_;
00230         }
00231         BOOST_UBLAS_INLINE
00232         const_iterator end () const {
00233             return data_ + size_;
00234         }
00235 
00236         BOOST_UBLAS_INLINE
00237         iterator begin () {
00238             return data_;
00239         }
00240         BOOST_UBLAS_INLINE
00241         iterator end () {
00242             return data_ + size_;
00243         }
00244 
00245         // Reverse iterators
00246         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00247         typedef std::reverse_iterator<iterator> reverse_iterator;
00248 
00249         BOOST_UBLAS_INLINE
00250         const_reverse_iterator rbegin () const {
00251             return const_reverse_iterator (end ());
00252         }
00253         BOOST_UBLAS_INLINE
00254         const_reverse_iterator rend () const {
00255             return const_reverse_iterator (begin ());
00256         }
00257         BOOST_UBLAS_INLINE
00258         reverse_iterator rbegin () {
00259             return reverse_iterator (end ());
00260         }
00261         BOOST_UBLAS_INLINE
00262         reverse_iterator rend () {
00263             return reverse_iterator (begin ());
00264         }
00265 
00266         // Allocator
00267         allocator_type get_allocator () {
00268             return alloc_;
00269         }
00270 
00271     private:
00272         friend class boost::serialization::access;
00273 
00274         // Serialization
00275         template<class Archive>
00276         void serialize(Archive & ar, const unsigned int version)
00277         { 
00278             serialization::collection_size_type s(size_);
00279             ar & serialization::make_nvp("size",s);
00280             if ( Archive::is_loading::value ) {
00281                 resize(s);
00282             }
00283             ar & serialization::make_array(data_, s);
00284         }
00285 
00286     private:
00287         // Handle explict destroy on a (possibly indexed) iterator
00288         BOOST_UBLAS_INLINE
00289         static void iterator_destroy (iterator &i) {
00290             (&(*i)) -> ~value_type ();
00291         }
00292         ALLOC alloc_;
00293         size_type size_;
00294         pointer data_;
00295     };
00296 
00297     // Bounded array - with allocator for size_type and difference_type
00298     template<class T, std::size_t N, class ALLOC>
00299     class bounded_array:
00300         public storage_array<bounded_array<T, N, ALLOC> > {
00301 
00302         typedef bounded_array<T, N, ALLOC> self_type;
00303     public:
00304         // No allocator_type as ALLOC is not used for allocation
00305         typedef typename ALLOC::size_type size_type;
00306         typedef typename ALLOC::difference_type difference_type;
00307         typedef T value_type;
00308         typedef const T &const_reference;
00309         typedef T &reference;
00310         typedef const T *const_pointer;
00311         typedef T *pointer;
00312         typedef const_pointer const_iterator;
00313         typedef pointer iterator;
00314 
00315         // Construction and destruction
00316         BOOST_UBLAS_INLINE
00317         bounded_array ():
00318             size_ (0) /*, data_ ()*/ {   // size 0 - use bounded_vector to default construct with size N
00319         }
00320         explicit BOOST_UBLAS_INLINE
00321         bounded_array (size_type size):
00322             size_ (size) /*, data_ ()*/ {
00323             BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
00324             // data_ (an array) elements are already default constructed
00325         }
00326         BOOST_UBLAS_INLINE
00327         bounded_array (size_type size, const value_type &init):
00328             size_ (size) /*, data_ ()*/ {
00329             BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
00330             // ISSUE elements should be value constructed here, but we must fill instead as already default constructed
00331             std::fill (begin(), end(), init) ;
00332         }
00333         BOOST_UBLAS_INLINE
00334         bounded_array (const bounded_array &c):
00335             size_ (c.size_)  {
00336             // ISSUE elements should be copy constructed here, but we must copy instead as already default constructed
00337             std::copy (c.begin(), c.end(), begin());
00338         }
00339         
00340         // Resizing
00341         BOOST_UBLAS_INLINE
00342         void resize (size_type size) {
00343             BOOST_UBLAS_CHECK (size <= N, bad_size ());
00344             size_ = size;
00345         }
00346         BOOST_UBLAS_INLINE
00347         void resize (size_type size, value_type init) {
00348             BOOST_UBLAS_CHECK (size <= N, bad_size ());
00349             if (size > size_)
00350                 std::fill (data_ + size_, data_ + size, init);
00351             size_ = size;
00352         }
00353 
00354         // Random Access Container
00355         BOOST_UBLAS_INLINE
00356         size_type max_size () const {
00357             return ALLOC ().max_size();
00358         }
00359         
00360         BOOST_UBLAS_INLINE
00361         bool empty () const {
00362             return size_ == 0;
00363         }
00364             
00365         BOOST_UBLAS_INLINE
00366         size_type size () const {
00367             return size_;
00368         }
00369 
00370         // Element access
00371         BOOST_UBLAS_INLINE
00372         const_reference operator [] (size_type i) const {
00373             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00374             return data_ [i];
00375         }
00376         BOOST_UBLAS_INLINE
00377         reference operator [] (size_type i) {
00378             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00379             return data_ [i];
00380         }
00381 
00382         // Assignment
00383         BOOST_UBLAS_INLINE
00384         bounded_array &operator = (const bounded_array &a) {
00385             if (this != &a) {
00386                 resize (a.size_);
00387                 std::copy (a.data_, a.data_ + a.size_, data_);
00388             }
00389             return *this;
00390         }
00391         BOOST_UBLAS_INLINE
00392         bounded_array &assign_temporary (bounded_array &a) { 
00393             *this = a;
00394             return *this;
00395         }
00396 
00397         // Swapping
00398         BOOST_UBLAS_INLINE
00399         void swap (bounded_array &a) {
00400             if (this != &a) {
00401                 std::swap (size_, a.size_);
00402                 std::swap_ranges (data_, data_ + (std::max) (size_, a.size_), a.data_);
00403             }
00404         }
00405         BOOST_UBLAS_INLINE
00406         friend void swap (bounded_array &a1, bounded_array &a2) {
00407             a1.swap (a2);
00408         }
00409 
00410         BOOST_UBLAS_INLINE
00411         const_iterator begin () const {
00412             return data_;
00413         }
00414         BOOST_UBLAS_INLINE
00415         const_iterator end () const {
00416             return data_ + size_;
00417         }
00418 
00419         BOOST_UBLAS_INLINE
00420         iterator begin () {
00421             return data_;
00422         }
00423         BOOST_UBLAS_INLINE
00424         iterator end () {
00425             return data_ + size_;
00426         }
00427 
00428         // Reverse iterators
00429         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00430         typedef std::reverse_iterator<iterator> reverse_iterator;
00431 
00432         BOOST_UBLAS_INLINE
00433         const_reverse_iterator rbegin () const {
00434             return const_reverse_iterator (end ());
00435         }
00436         BOOST_UBLAS_INLINE
00437         const_reverse_iterator rend () const {
00438             return const_reverse_iterator (begin ());
00439         }
00440         BOOST_UBLAS_INLINE
00441         reverse_iterator rbegin () {
00442             return reverse_iterator (end ());
00443         }
00444         BOOST_UBLAS_INLINE
00445         reverse_iterator rend () {
00446             return reverse_iterator (begin ());
00447         }
00448 
00449     private:
00450         // Serialization
00451         friend class boost::serialization::access;
00452 
00453         template<class Archive>
00454         void serialize(Archive & ar, const unsigned int version)
00455         {
00456             serialization::collection_size_type s(size_);
00457             ar & serialization::make_nvp("size", s);
00458             if ( Archive::is_loading::value ) {
00459                 if (s > N) bad_size("too large size in bounded_array::load()\n").raise();
00460                 resize(s);
00461             }
00462             ar & serialization::make_array(data_, s);
00463         }
00464 
00465     private:
00466         size_type size_;
00467 // MSVC does not like arrays of size 0 in base classes.  Hence, this conditionally changes the size to 1
00468 #ifdef _MSC_VER
00469         BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [(N>0)?N:1];
00470 #else
00471         BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [N];
00472 #endif
00473     };
00474 
00475 
00476     // Array adaptor with normal deep copy semantics of elements
00477     template<class T>
00478     class array_adaptor:
00479         public storage_array<array_adaptor<T> > {
00480 
00481         typedef array_adaptor<T> self_type;
00482     public:
00483         typedef std::size_t size_type;
00484         typedef std::ptrdiff_t difference_type;
00485         typedef T value_type;
00486         typedef const T &const_reference;
00487         typedef T &reference;
00488         typedef const T *const_pointer;
00489         typedef T *pointer;
00490 
00491         // Construction and destruction
00492         BOOST_UBLAS_INLINE
00493         array_adaptor ():
00494             size_ (0), own_ (true), data_ (new value_type [0]) {
00495         }
00496         explicit BOOST_UBLAS_INLINE
00497         array_adaptor (size_type size):
00498             size_ (size), own_ (true), data_ (new value_type [size]) {
00499         }
00500         BOOST_UBLAS_INLINE
00501         array_adaptor (size_type size, const value_type &init):
00502             size_ (size), own_ (true), data_ (new value_type [size]) {
00503             std::fill (data_, data_ + size_, init);
00504         }
00505         BOOST_UBLAS_INLINE
00506         array_adaptor (size_type size, pointer data):
00507             size_ (size), own_ (false), data_ (data) {}
00508         BOOST_UBLAS_INLINE
00509         array_adaptor (const array_adaptor &a):
00510             storage_array<self_type> (),
00511             size_ (a.size_), own_ (true), data_ (new value_type [a.size_]) {
00512             *this = a;
00513         }
00514         BOOST_UBLAS_INLINE
00515         ~array_adaptor () {
00516             if (own_) {
00517                 delete [] data_;
00518             }
00519         }
00520 
00521         // Resizing
00522     private:
00523         BOOST_UBLAS_INLINE
00524         void resize_internal (size_type size, value_type init, bool preserve = true) {
00525            if (size != size_) {
00526                 pointer data = new value_type [size];
00527                 if (preserve) {
00528                     std::copy (data_, data_ + (std::min) (size, size_), data);
00529                     std::fill (data + (std::min) (size, size_), data + size, init);
00530                 }
00531                 if (own_)
00532                     delete [] data_;
00533                 size_ = size;
00534                 own_ = true;
00535                 data_ = data;
00536             }
00537         }
00538         BOOST_UBLAS_INLINE
00539         void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
00540             if (data != data_) {
00541                 if (preserve) {
00542                     std::copy (data_, data_ + (std::min) (size, size_), data);
00543                     std::fill (data + (std::min) (size, size_), data + size, init);
00544                 }
00545                 if (own_)
00546                     delete [] data_;
00547                 own_ = false;
00548                 data_ = data;
00549             }
00550             else {
00551                 std::fill (data + (std::min) (size, size_), data + size, init);
00552             }
00553             size_ = size;
00554         }
00555     public:
00556         BOOST_UBLAS_INLINE
00557         void resize (size_type size) {
00558             resize_internal (size, value_type (), false);
00559         }
00560         BOOST_UBLAS_INLINE
00561         void resize (size_type size, value_type init) {
00562             resize_internal (size, init, true);
00563         }
00564         BOOST_UBLAS_INLINE
00565         void resize (size_type size, pointer data) {
00566             resize_internal (size, data, value_type (), false);
00567         }
00568         BOOST_UBLAS_INLINE
00569         void resize (size_type size, pointer data, value_type init) {
00570             resize_internal (size, data, init, true);
00571         }
00572 
00573         BOOST_UBLAS_INLINE
00574         size_type size () const {
00575             return size_;
00576         }
00577 
00578         // Element access
00579         BOOST_UBLAS_INLINE
00580         const_reference operator [] (size_type i) const {
00581             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00582             return data_ [i];
00583         }
00584         BOOST_UBLAS_INLINE
00585         reference operator [] (size_type i) {
00586             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00587             return data_ [i];
00588         }
00589 
00590         // Assignment
00591         BOOST_UBLAS_INLINE
00592         array_adaptor &operator = (const array_adaptor &a) {
00593             if (this != &a) {
00594                 resize (a.size_);
00595                 std::copy (a.data_, a.data_ + a.size_, data_);
00596             }
00597             return *this;
00598         }
00599         BOOST_UBLAS_INLINE
00600         array_adaptor &assign_temporary (array_adaptor &a) {
00601             if (own_ && a.own_)
00602                 swap (a);
00603             else
00604                 *this = a;
00605             return *this;
00606         }
00607 
00608         // Swapping
00609         BOOST_UBLAS_INLINE
00610         void swap (array_adaptor &a) {
00611             if (this != &a) {
00612                 std::swap (size_, a.size_);
00613                 std::swap (own_, a.own_);
00614                 std::swap (data_, a.data_);
00615             }
00616         }
00617         BOOST_UBLAS_INLINE
00618         friend void swap (array_adaptor &a1, array_adaptor &a2) {
00619             a1.swap (a2);
00620         }
00621 
00622         // Iterators simply are pointers.
00623 
00624         typedef const_pointer const_iterator;
00625 
00626         BOOST_UBLAS_INLINE
00627         const_iterator begin () const {
00628             return data_;
00629         }
00630         BOOST_UBLAS_INLINE
00631         const_iterator end () const {
00632             return data_ + size_;
00633         }
00634 
00635         typedef pointer iterator;
00636 
00637         BOOST_UBLAS_INLINE
00638         iterator begin () {
00639             return data_;
00640         }
00641         BOOST_UBLAS_INLINE
00642         iterator end () {
00643             return data_ + size_;
00644         }
00645 
00646         // Reverse iterators
00647         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00648         typedef std::reverse_iterator<iterator> reverse_iterator;
00649 
00650         BOOST_UBLAS_INLINE
00651         const_reverse_iterator rbegin () const {
00652             return const_reverse_iterator (end ());
00653         }
00654         BOOST_UBLAS_INLINE
00655         const_reverse_iterator rend () const {
00656             return const_reverse_iterator (begin ());
00657         }
00658         BOOST_UBLAS_INLINE
00659         reverse_iterator rbegin () {
00660             return reverse_iterator (end ());
00661         }
00662         BOOST_UBLAS_INLINE
00663         reverse_iterator rend () {
00664             return reverse_iterator (begin ());
00665         }
00666 
00667     private:
00668         size_type size_;
00669         bool own_;
00670         pointer data_;
00671     };
00672 
00673 #ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
00674     // Array adaptor with shallow (reference) copy semantics of elements.
00675     // shared_array is used to maintain reference counts.
00676     // This class breaks the normal copy semantics for a storage container and is very dangerous!
00677     template<class T>
00678     class shallow_array_adaptor:
00679         public storage_array<shallow_array_adaptor<T> > {
00680 
00681         typedef shallow_array_adaptor<T> self_type;
00682 
00683         template<class TT>
00684         struct leaker {
00685             typedef void result_type;
00686             typedef TT *argument_type;
00687 
00688             BOOST_UBLAS_INLINE
00689             result_type operator () (argument_type x) {}
00690         };
00691 
00692     public:
00693         typedef std::size_t size_type;
00694         typedef std::ptrdiff_t difference_type;
00695         typedef T value_type;
00696         typedef const T &const_reference;
00697         typedef T &reference;
00698         typedef const T *const_pointer;
00699         typedef T *pointer;
00700 
00701         // Construction and destruction
00702         BOOST_UBLAS_INLINE
00703         shallow_array_adaptor ():
00704             size_ (0), own_ (true), data_ (new value_type [0]) {
00705         }
00706         explicit BOOST_UBLAS_INLINE
00707         shallow_array_adaptor (size_type size):
00708             size_ (size), own_ (true), data_ (new value_type [size]) {
00709         }
00710         BOOST_UBLAS_INLINE
00711         shallow_array_adaptor (size_type size, const value_type &init):
00712             size_ (size), own_ (true), data_ (new value_type [size]) {
00713             std::fill (data_.get (), data_.get () + size_, init);
00714         }
00715         BOOST_UBLAS_INLINE
00716         shallow_array_adaptor (size_type size, pointer data):
00717             size_ (size), own_ (false), data_ (data, leaker<value_type> ()) {}
00718 
00719         BOOST_UBLAS_INLINE
00720         shallow_array_adaptor (const shallow_array_adaptor &a):
00721             storage_array<self_type> (),
00722             size_ (a.size_), own_ (a.own_), data_ (a.data_) {}
00723 
00724         BOOST_UBLAS_INLINE
00725         ~shallow_array_adaptor () {
00726         }
00727 
00728         // Resizing
00729     private:
00730         BOOST_UBLAS_INLINE
00731         void resize_internal (size_type size, value_type init, bool preserve = true) {
00732             if (size != size_) {
00733                 shared_array<value_type> data (new value_type [size]);
00734                 if (preserve) {
00735                     std::copy (data_.get (), data_.get () + (std::min) (size, size_), data.get ());
00736                     std::fill (data.get () + (std::min) (size, size_), data.get () + size, init);
00737                 }
00738                 size_ = size;
00739                 data_ = data;
00740             }
00741         }
00742         BOOST_UBLAS_INLINE
00743         void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
00744             if (preserve) {
00745                 std::copy (data_.get (), data_.get () + (std::min) (size, size_), data);
00746                 std::fill (data + (std::min) (size, size_), data + size, init);
00747             }
00748             size_ = size;
00749             data_ = data;
00750         }
00751     public:
00752         BOOST_UBLAS_INLINE
00753         void resize (size_type size) {
00754             resize_internal (size, value_type (), false);
00755         }
00756         BOOST_UBLAS_INLINE
00757         void resize (size_type size, value_type init) {
00758             resize_internal (size, init, true);
00759         }
00760         BOOST_UBLAS_INLINE
00761         void resize (size_type size, pointer data) {
00762             resize_internal (size, data, value_type (), false);
00763         }
00764         BOOST_UBLAS_INLINE
00765         void resize (size_type size, pointer data, value_type init) {
00766             resize_internal (size, data, init, true);
00767         }
00768 
00769         BOOST_UBLAS_INLINE
00770         size_type size () const {
00771             return size_;
00772         }
00773 
00774         // Element access
00775         BOOST_UBLAS_INLINE
00776         const_reference operator [] (size_type i) const {
00777             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00778             return data_ [i];
00779         }
00780         BOOST_UBLAS_INLINE
00781         reference operator [] (size_type i) {
00782             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00783             return data_ [i];
00784         }
00785 
00786         // Assignment
00787         BOOST_UBLAS_INLINE
00788         shallow_array_adaptor &operator = (const shallow_array_adaptor &a) {
00789             if (this != &a) {
00790                 resize (a.size_);
00791                 std::copy (a.data_.get (), a.data_.get () + a.size_, data_.get ());
00792             }
00793             return *this;
00794         }
00795         BOOST_UBLAS_INLINE
00796         shallow_array_adaptor &assign_temporary (shallow_array_adaptor &a) {
00797             if (own_ && a.own_)
00798                 swap (a);
00799             else
00800                 *this = a;
00801             return *this;
00802         }
00803 
00804         // Swapping
00805         BOOST_UBLAS_INLINE
00806         void swap (shallow_array_adaptor &a) {
00807             if (this != &a) {
00808                 std::swap (size_, a.size_);
00809                 std::swap (own_, a.own_);
00810                 std::swap (data_, a.data_);
00811             }
00812         }
00813         BOOST_UBLAS_INLINE
00814         friend void swap (shallow_array_adaptor &a1, shallow_array_adaptor &a2) {
00815             a1.swap (a2);
00816         }
00817 
00818         // Iterators simply are pointers.
00819 
00820         typedef const_pointer const_iterator;
00821 
00822         BOOST_UBLAS_INLINE
00823         const_iterator begin () const {
00824             return data_.get ();
00825         }
00826         BOOST_UBLAS_INLINE
00827         const_iterator end () const {
00828             return data_.get () + size_;
00829         }
00830 
00831         typedef pointer iterator;
00832 
00833         BOOST_UBLAS_INLINE
00834         iterator begin () {
00835             return data_.get ();
00836         }
00837         BOOST_UBLAS_INLINE
00838         iterator end () {
00839             return data_.get () + size_;
00840         }
00841 
00842         // Reverse iterators
00843         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00844         typedef std::reverse_iterator<iterator> reverse_iterator;
00845 
00846         BOOST_UBLAS_INLINE
00847         const_reverse_iterator rbegin () const {
00848             return const_reverse_iterator (end ());
00849         }
00850         BOOST_UBLAS_INLINE
00851         const_reverse_iterator rend () const {
00852             return const_reverse_iterator (begin ());
00853         }
00854         BOOST_UBLAS_INLINE
00855         reverse_iterator rbegin () {
00856             return reverse_iterator (end ());
00857         }
00858         BOOST_UBLAS_INLINE
00859         reverse_iterator rend () {
00860             return reverse_iterator (begin ());
00861         }
00862 
00863     private:
00864         size_type size_;
00865         bool own_;
00866         shared_array<value_type> data_;
00867     };
00868 
00869 #endif
00870 
00871 
00872     // Range class
00873     template <class Z, class D>
00874     class basic_range {
00875         typedef basic_range<Z, D> self_type;
00876     public:
00877         typedef Z size_type;
00878         typedef D difference_type;
00879         typedef size_type value_type;
00880         typedef value_type const_reference;
00881         typedef const_reference reference;
00882         typedef const value_type *const_pointer;
00883         typedef value_type *pointer;
00884 
00885         // Construction and destruction
00886         BOOST_UBLAS_INLINE
00887         basic_range ():
00888             start_ (0), size_ (0) {}
00889         BOOST_UBLAS_INLINE
00890         basic_range (size_type start, size_type stop):
00891             start_ (start), size_ (stop - start) {
00892             BOOST_UBLAS_CHECK (start_ <= stop, bad_index ());
00893         }
00894 
00895         BOOST_UBLAS_INLINE
00896         size_type start () const {
00897             return start_;
00898         }
00899         BOOST_UBLAS_INLINE
00900         size_type size () const {
00901             return size_;
00902         }
00903 
00904         // Random Access Container
00905         BOOST_UBLAS_INLINE
00906         size_type max_size () const {
00907             return size_;
00908         }
00909         
00910         BOOST_UBLAS_INLINE
00911         bool empty () const {
00912             return size_ == 0;
00913         }
00914             
00915         // Element access
00916         BOOST_UBLAS_INLINE
00917         const_reference operator () (size_type i) const {
00918             BOOST_UBLAS_CHECK (i < size_, bad_index ());
00919             return start_ + i;
00920         }
00921 
00922         // Composition
00923         BOOST_UBLAS_INLINE
00924         basic_range compose (const basic_range &r) const {
00925             return basic_range (start_ + r.start_, start_ + r.start_ + r.size_);
00926         }
00927 
00928         // Comparison
00929         BOOST_UBLAS_INLINE
00930         bool operator == (const basic_range &r) const {
00931             return start_ == r.start_ && size_ == r.size_;
00932         }
00933         BOOST_UBLAS_INLINE
00934         bool operator != (const basic_range &r) const {
00935             return ! (*this == r);
00936         }
00937 
00938         // Iterator types
00939     private:
00940         // Use and index
00941         typedef size_type const_subiterator_type;
00942 
00943     public:
00944 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
00945         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
00946 #else
00947         class const_iterator:
00948             public container_const_reference<basic_range>,
00949             public random_access_iterator_base<std::random_access_iterator_tag,
00950                                                const_iterator, value_type> {
00951         public:
00952             typedef typename basic_range::value_type value_type;
00953             typedef typename basic_range::difference_type difference_type;
00954             typedef typename basic_range::const_reference reference;
00955             typedef typename basic_range::const_pointer pointer;
00956 
00957             // Construction and destruction
00958             BOOST_UBLAS_INLINE
00959             const_iterator ():
00960                 container_const_reference<basic_range> (), it_ () {}
00961             BOOST_UBLAS_INLINE
00962             const_iterator (const basic_range &r, const const_subiterator_type &it):
00963                 container_const_reference<basic_range> (r), it_ (it) {}
00964 
00965             // Arithmetic
00966             BOOST_UBLAS_INLINE
00967             const_iterator &operator ++ () {
00968                 ++ it_;
00969                 return *this;
00970             }
00971             BOOST_UBLAS_INLINE
00972             const_iterator &operator -- () {
00973                 BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
00974                 -- it_;
00975                 return *this;
00976             }
00977             BOOST_UBLAS_INLINE
00978             const_iterator &operator += (difference_type n) {
00979                 BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
00980                 it_ += n;
00981                 return *this;
00982             }
00983             BOOST_UBLAS_INLINE
00984             const_iterator &operator -= (difference_type n) {
00985                 BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
00986                 it_ -= n;
00987                 return *this;
00988             }
00989             BOOST_UBLAS_INLINE
00990             difference_type operator - (const const_iterator &it) const {
00991                 return it_ - it.it_;
00992             }
00993 
00994             // Dereference
00995             BOOST_UBLAS_INLINE
00996             const_reference operator * () const {
00997                 BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
00998                 BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
00999                 return it_;
01000             }
01001 
01002             BOOST_UBLAS_INLINE
01003             const_reference operator [] (difference_type n) const {
01004                 return *(*this + n);
01005             }
01006 
01007             // Index
01008             BOOST_UBLAS_INLINE
01009             size_type index () const {
01010                 BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
01011                 BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
01012                 return it_ - (*this) ().start ();
01013             }
01014 
01015             // Assignment
01016             BOOST_UBLAS_INLINE
01017             const_iterator &operator = (const const_iterator &it) {
01018                 // Comeau recommends...
01019                 this->assign (&it ());
01020                 it_ = it.it_;
01021                 return *this;
01022             }
01023 
01024             // Comparison
01025             BOOST_UBLAS_INLINE
01026             bool operator == (const const_iterator &it) const {
01027                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
01028                 return it_ == it.it_;
01029             }
01030             BOOST_UBLAS_INLINE
01031             bool operator < (const const_iterator &it) const {
01032                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
01033                 return it_ < it.it_;
01034             }
01035 
01036         private:
01037             const_subiterator_type it_;
01038         };
01039 #endif
01040 
01041         BOOST_UBLAS_INLINE
01042         const_iterator begin () const {
01043             return const_iterator (*this, start_);
01044         }
01045         BOOST_UBLAS_INLINE
01046         const_iterator end () const {
01047             return const_iterator (*this, start_ + size_);
01048         }
01049 
01050         // Reverse iterator
01051         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01052 
01053         BOOST_UBLAS_INLINE
01054         const_reverse_iterator rbegin () const {
01055             return const_reverse_iterator (end ());
01056         }
01057         BOOST_UBLAS_INLINE
01058         const_reverse_iterator rend () const {
01059             return const_reverse_iterator (begin ());
01060         }
01061 
01062         BOOST_UBLAS_INLINE
01063         basic_range preprocess (size_type size) const {
01064             if (this != &all_)
01065                 return *this;
01066             return basic_range (0, size);
01067         }
01068         static
01069         BOOST_UBLAS_INLINE
01070         const basic_range &all () {
01071             return all_;
01072         }
01073 
01074     private:
01075         size_type start_;
01076         size_type size_;
01077         static const basic_range all_;
01078     };
01079 
01080     template <class Z, class D>
01081     const basic_range<Z,D> basic_range<Z,D>::all_  (0, size_type (-1));
01082 
01083 
01084     // Slice class
01085     template <class Z, class D>
01086     class basic_slice {
01087         typedef basic_slice<Z, D> self_type;
01088     public:
01089         typedef Z size_type;
01090         typedef D difference_type;
01091         typedef size_type value_type;
01092         typedef value_type const_reference;
01093         typedef const_reference reference;
01094         typedef const value_type *const_pointer;
01095         typedef value_type *pointer;
01096 
01097         // Construction and destruction
01098         BOOST_UBLAS_INLINE
01099         basic_slice ():
01100             start_ (0), stride_ (0), size_ (0) {}
01101         BOOST_UBLAS_INLINE
01102         basic_slice (size_type start, difference_type stride, size_type size):
01103             start_ (start), stride_ (stride), size_ (size) {}
01104 
01105         BOOST_UBLAS_INLINE
01106         size_type start () const {
01107             return start_;
01108         }
01109         BOOST_UBLAS_INLINE
01110         difference_type stride () const {
01111             return stride_;
01112         }
01113         BOOST_UBLAS_INLINE
01114         size_type size () const {
01115             return size_;
01116         }
01117 
01118         // Random Access Container
01119         BOOST_UBLAS_INLINE
01120         size_type max_size () const {
01121             return size_;
01122         }
01123         
01124         BOOST_UBLAS_INLINE
01125         bool empty () const {
01126             return size_ == 0;
01127         }
01128             
01129         // Element access
01130         BOOST_UBLAS_INLINE
01131         const_reference operator () (size_type i) const {
01132             BOOST_UBLAS_CHECK (i < size_, bad_index ());
01133             BOOST_UBLAS_CHECK (stride_ >= 0 || start_ >= i * -stride_, bad_index ());
01134             return start_ + i * stride_;
01135         }
01136 
01137         // Composition
01138         BOOST_UBLAS_INLINE
01139         basic_slice compose (const basic_range<size_type, difference_type> &r) const {
01140             BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * r.start(), bad_index ());
01141             return basic_slice (start_ + stride_ * r.start (), stride_, r.size ());
01142         }
01143         BOOST_UBLAS_INLINE
01144         basic_slice compose (const basic_slice &s) const {
01145             BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * s.start_, bad_index ());
01146             return basic_slice (start_ + stride_ * s.start_, stride_ * s.stride_, s.size_);
01147         }
01148 
01149         // Comparison
01150         BOOST_UBLAS_INLINE
01151         bool operator == (const basic_slice &s) const {
01152             return start_ == s.start_ && stride_ == s.stride_ && size_ == s.size_; 
01153         }
01154         BOOST_UBLAS_INLINE
01155         bool operator != (const basic_slice &s) const {
01156             return ! (*this == s);
01157         }
01158 
01159         // Iterator types
01160     private:
01161         // Use and index
01162         typedef size_type const_subiterator_type;
01163 
01164     public:
01165 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
01166         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
01167 #else
01168         class const_iterator:
01169             public container_const_reference<basic_slice>,
01170             public random_access_iterator_base<std::random_access_iterator_tag,
01171                                                const_iterator, value_type> {
01172         public:
01173             typedef typename basic_slice::value_type value_type;
01174             typedef typename basic_slice::difference_type difference_type;
01175             typedef typename basic_slice::const_reference reference;
01176             typedef typename basic_slice::const_pointer pointer;
01177 
01178             // Construction and destruction
01179             BOOST_UBLAS_INLINE
01180             const_iterator ():
01181                 container_const_reference<basic_slice> (), it_ () {}
01182             BOOST_UBLAS_INLINE
01183             const_iterator (const basic_slice &s, const const_subiterator_type &it):
01184                 container_const_reference<basic_slice> (s), it_ (it) {}
01185 
01186             // Arithmetic
01187             BOOST_UBLAS_INLINE
01188             const_iterator &operator ++ () {
01189                 ++it_;
01190                 return *this;
01191             }
01192             BOOST_UBLAS_INLINE
01193             const_iterator &operator -- () {
01194                 BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
01195                 --it_;
01196                 return *this;
01197             }
01198             BOOST_UBLAS_INLINE
01199             const_iterator &operator += (difference_type n) {
01200                 BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
01201                 it_ += n;
01202                 return *this;
01203             }
01204             BOOST_UBLAS_INLINE
01205             const_iterator &operator -= (difference_type n) {
01206                 BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
01207                 it_ -= n;
01208                 return *this;
01209             }
01210             BOOST_UBLAS_INLINE
01211             difference_type operator - (const const_iterator &it) const {
01212                 return it_ - it.it_;
01213             }
01214 
01215             // Dereference
01216             BOOST_UBLAS_INLINE
01217             const_reference operator * () const {
01218                 BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
01219                 return (*this) ().start () + it_* (*this) ().stride ();
01220             }
01221 
01222             BOOST_UBLAS_INLINE
01223             const_reference operator [] (difference_type n) const {
01224                 return *(*this + n);
01225             }
01226 
01227             // Index
01228             BOOST_UBLAS_INLINE
01229             size_type index () const {
01230                 BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
01231                 return it_;
01232             }
01233 
01234             // Assignment
01235             BOOST_UBLAS_INLINE
01236             const_iterator &operator = (const const_iterator &it) {
01237                 // Comeau recommends...
01238                 this->assign (&it ());
01239                 it_ = it.it_;
01240                 return *this;
01241             }
01242 
01243             // Comparison
01244             BOOST_UBLAS_INLINE
01245             bool operator == (const const_iterator &it) const {
01246                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
01247                 return it_ == it.it_;
01248             }
01249             BOOST_UBLAS_INLINE
01250             bool operator < (const const_iterator &it) const {
01251                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
01252                 return it_ < it.it_;
01253             }
01254 
01255         private:
01256             const_subiterator_type it_;
01257         };
01258 #endif
01259 
01260         BOOST_UBLAS_INLINE
01261         const_iterator begin () const {
01262             return const_iterator (*this, 0);
01263         }
01264         BOOST_UBLAS_INLINE
01265         const_iterator end () const {
01266             return const_iterator (*this, size_);
01267         }
01268 
01269         // Reverse iterator
01270         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01271 
01272         BOOST_UBLAS_INLINE
01273         const_reverse_iterator rbegin () const {
01274             return const_reverse_iterator (end ());
01275         }
01276         BOOST_UBLAS_INLINE
01277         const_reverse_iterator rend () const {
01278             return const_reverse_iterator (begin ());
01279         }
01280 
01281         BOOST_UBLAS_INLINE
01282         basic_slice preprocess (size_type size) const {
01283             if (this != &all_)
01284                 return *this;
01285             return basic_slice (0, 1, size);
01286         }
01287         static
01288         BOOST_UBLAS_INLINE
01289         const basic_slice &all () {
01290             return all_;
01291         }
01292 
01293     private:
01294         size_type start_;
01295         difference_type stride_;
01296         size_type size_;
01297         static const basic_slice all_;
01298     };
01299 
01300     template <class Z, class D>
01301     const basic_slice<Z,D> basic_slice<Z,D>::all_  (0, 1, size_type (-1));
01302 
01303 
01304     // Indirect array class
01305     template<class A>
01306     class indirect_array {
01307         typedef indirect_array<A> self_type;
01308     public:
01309         typedef A array_type;
01310         typedef const A const_array_type;
01311         typedef typename A::size_type size_type;
01312         typedef typename A::difference_type difference_type;
01313         typedef typename A::value_type value_type;
01314         typedef typename A::const_reference const_reference;
01315         typedef typename A::reference reference;
01316         typedef typename A::const_pointer const_pointer;
01317         typedef typename A::pointer pointer;
01318 
01319         // Construction and destruction
01320         BOOST_UBLAS_INLINE
01321         indirect_array ():
01322             size_ (), data_ () {}
01323         explicit BOOST_UBLAS_INLINE
01324         indirect_array (size_type size):
01325             size_ (size), data_ (size) {}
01326         BOOST_UBLAS_INLINE
01327         indirect_array (size_type size, const array_type &data):
01328             size_ (size), data_ (data) {}
01329         BOOST_UBLAS_INLINE
01330         indirect_array (pointer start, pointer stop):
01331             size_ (stop - start), data_ (stop - start) {
01332             std::copy (start, stop, data_.begin ());
01333         }
01334 
01335         BOOST_UBLAS_INLINE
01336         size_type size () const {
01337             return size_;
01338         }
01339         BOOST_UBLAS_INLINE
01340         const_array_type data () const {
01341             return data_;
01342         }
01343         BOOST_UBLAS_INLINE
01344         array_type data () {
01345             return data_;
01346         }
01347 
01348         // Random Access Container
01349         BOOST_UBLAS_INLINE
01350         size_type max_size () const {
01351             return size_;
01352         }
01353         
01354         BOOST_UBLAS_INLINE
01355         bool empty () const {
01356             return data_.size () == 0;
01357         }
01358             
01359         // Element access
01360         BOOST_UBLAS_INLINE
01361         const_reference operator () (size_type i) const {
01362             BOOST_UBLAS_CHECK (i < size_, bad_index ());
01363             return data_ [i];
01364         }
01365         BOOST_UBLAS_INLINE
01366         reference operator () (size_type i) {
01367             BOOST_UBLAS_CHECK (i < size_, bad_index ());
01368             return data_ [i];
01369         }
01370 
01371         BOOST_UBLAS_INLINE
01372         const_reference operator [] (size_type i) const {
01373             return (*this) (i);
01374         }
01375         BOOST_UBLAS_INLINE
01376         reference operator [] (size_type i) {
01377             return (*this) (i);
01378         }
01379 
01380         // Composition
01381         BOOST_UBLAS_INLINE
01382         indirect_array compose (const basic_range<size_type, difference_type> &r) const {
01383             BOOST_UBLAS_CHECK (r.start () + r.size () <= size_, bad_size ());
01384             array_type data (r.size ());
01385             for (size_type i = 0; i < r.size (); ++ i)
01386                 data [i] = data_ [r.start () + i];
01387             return indirect_array (r.size (), data);
01388         }
01389         BOOST_UBLAS_INLINE
01390         indirect_array compose (const basic_slice<size_type, difference_type> &s) const {
01391             BOOST_UBLAS_CHECK (s.start () + s.stride () * (s.size () - (s.size () > 0)) <= size (), bad_size ());
01392             array_type data (s.size ());
01393             for (size_type i = 0; i < s.size (); ++ i)
01394                 data [i] = data_ [s.start () + s.stride () * i];
01395             return indirect_array (s.size (), data);
01396         }
01397         BOOST_UBLAS_INLINE
01398         indirect_array compose (const indirect_array &ia) const {
01399             array_type data (ia.size_);
01400             for (size_type i = 0; i < ia.size_; ++ i) {
01401                 BOOST_UBLAS_CHECK (ia.data_ [i] <= size_, bad_size ());
01402                 data [i] = data_ [ia.data_ [i]];
01403             }
01404             return indirect_array (ia.size_, data);
01405         }
01406 
01407         // Comparison
01408         template<class OA>
01409         BOOST_UBLAS_INLINE
01410         bool operator == (const indirect_array<OA> &ia) const {
01411             if (size_ != ia.size_)
01412                 return false;
01413             for (size_type i = 0; i < BOOST_UBLAS_SAME (size_, ia.size_); ++ i)
01414                 if (data_ [i] != ia.data_ [i])
01415                     return false;
01416             return true;
01417         }
01418         template<class OA>
01419         BOOST_UBLAS_INLINE
01420         bool operator != (const indirect_array<OA> &ia) const {
01421             return ! (*this == ia);
01422         }
01423 
01424         // Iterator types
01425     private:
01426         // Use a index difference
01427         typedef difference_type const_subiterator_type;
01428 
01429     public:
01430 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
01431         typedef indexed_const_iterator<indirect_array, std::random_access_iterator_tag> const_iterator;
01432 #else
01433         class const_iterator:
01434             public container_const_reference<indirect_array>,
01435             public random_access_iterator_base<std::random_access_iterator_tag,
01436                                                const_iterator, value_type> {
01437         public:
01438             typedef typename indirect_array::value_type value_type;
01439             typedef typename indirect_array::difference_type difference_type;
01440             typedef typename indirect_array::const_reference reference;
01441             typedef typename indirect_array::const_pointer pointer;
01442 
01443             // Construction and destruction
01444             BOOST_UBLAS_INLINE
01445             const_iterator ():
01446                 container_const_reference<indirect_array> (), it_ () {}
01447             BOOST_UBLAS_INLINE
01448             const_iterator (const indirect_array &ia, const const_subiterator_type &it):
01449                 container_const_reference<indirect_array> (ia), it_ (it) {}
01450 
01451             // Arithmetic
01452             BOOST_UBLAS_INLINE
01453             const_iterator &operator ++ () {
01454                 ++ it_;
01455                 return *this;
01456             }
01457             BOOST_UBLAS_INLINE
01458             const_iterator &operator -- () {
01459                 -- it_;
01460                 return *this;
01461             }
01462             BOOST_UBLAS_INLINE
01463             const_iterator &operator += (difference_type n) {
01464                 it_ += n;
01465                 return *this;
01466             }
01467             BOOST_UBLAS_INLINE
01468             const_iterator &operator -= (difference_type n) {
01469                 it_ -= n;
01470                 return *this;
01471             }
01472             BOOST_UBLAS_INLINE
01473             difference_type operator - (const const_iterator &it) const {
01474                 return it_ - it.it_;
01475             }
01476 
01477             // Dereference
01478             BOOST_UBLAS_INLINE
01479             const_reference operator * () const {
01480                 return (*this) () (it_);
01481             }
01482 
01483             BOOST_UBLAS_INLINE
01484             const_reference operator [] (difference_type n) const {
01485                 return *(*this + n);
01486             }
01487 
01488             // Index
01489             BOOST_UBLAS_INLINE
01490             size_type index () const {
01491                 return it_;
01492             }
01493 
01494             // Assignment
01495             BOOST_UBLAS_INLINE
01496             const_iterator &operator = (const const_iterator &it) {
01497                 // Comeau recommends...
01498                 this->assign (&it ());
01499                 it_ = it.it_;
01500                 return *this;
01501             }
01502 
01503             // Comparison
01504             BOOST_UBLAS_INLINE
01505             bool operator == (const const_iterator &it) const {
01506                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
01507                 return it_ == it.it_;
01508             }
01509             BOOST_UBLAS_INLINE
01510             bool operator < (const const_iterator &it) const {
01511                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
01512                 return it_ < it.it_;
01513             }
01514 
01515         private:
01516             const_subiterator_type it_;
01517         };
01518 #endif
01519 
01520         BOOST_UBLAS_INLINE
01521         const_iterator begin () const {
01522             return const_iterator (*this, 0);
01523         }
01524         BOOST_UBLAS_INLINE
01525         const_iterator end () const {
01526             return const_iterator (*this, size_);
01527         }
01528 
01529         // Reverse iterator
01530         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
01531 
01532         BOOST_UBLAS_INLINE
01533         const_reverse_iterator rbegin () const {
01534             return const_reverse_iterator (end ());
01535         }
01536         BOOST_UBLAS_INLINE
01537         const_reverse_iterator rend () const {
01538             return const_reverse_iterator (begin ());
01539         }
01540 
01541         BOOST_UBLAS_INLINE
01542         indirect_array preprocess (size_type size) const {
01543             if (this != &all_)
01544                 return *this;
01545             indirect_array ia (size);
01546             for (size_type i = 0; i < size; ++ i)
01547                ia (i) = i;
01548             return ia;
01549         }
01550         static
01551         BOOST_UBLAS_INLINE
01552         const indirect_array &all () {
01553             return all_;
01554         }
01555 
01556     private:
01557         size_type size_;
01558         array_type data_;
01559         static const indirect_array all_;
01560     };
01561 
01562     template<class A>
01563     const indirect_array<A> indirect_array<A>::all_;
01564 
01565 
01566 
01567     // Gunter Winkler contributed the classes index_pair, index_pair_array,
01568     // index_triple and index_triple_array to enable inplace sort of parallel arrays.
01569 
01570     template <class V>
01571     class index_pair :
01572         private boost::noncopyable,
01573         public container_reference<V> {
01574 
01575         typedef index_pair<V> self_type;
01576     public:
01577         typedef typename V::size_type size_type;
01578 
01579         BOOST_UBLAS_INLINE
01580         index_pair(V& v, size_type i) :
01581             container_reference<V>(v), i_(i),
01582             v1_(v.data1_[i]), v2_(v.data2_[i]),
01583             dirty_(false), is_copy_(false) {}
01584          BOOST_UBLAS_INLINE
01585         index_pair(const self_type& rhs) :
01586             container_reference<V>(rhs()), i_(0),
01587             v1_(rhs.v1_), v2_(rhs.v2_),
01588             dirty_(false), is_copy_(true) {}
01589          BOOST_UBLAS_INLINE
01590         ~index_pair() {
01591             if (dirty_ && (!is_copy_) ) {
01592                 (*this)().data1_[i_] = v1_;
01593                 (*this)().data2_[i_] = v2_;
01594             }
01595         }
01596 
01597         BOOST_UBLAS_INLINE
01598         self_type& operator=(const self_type& rhs) {
01599             v1_ = rhs.v1_;
01600             v2_ = rhs.v2_;
01601             dirty_ = true;
01602             return *this;
01603         }
01604 
01605         BOOST_UBLAS_INLINE
01606         void swap(self_type& rhs) {
01607             self_type tmp(rhs);
01608             rhs = *this;
01609             *this = tmp;
01610         }
01611         BOOST_UBLAS_INLINE
01612         friend void swap(self_type& lhs, self_type& rhs) {
01613             lhs.swap(rhs);
01614         }
01615 
01616         BOOST_UBLAS_INLINE
01617         bool equal(const self_type& rhs) const {
01618             return (v1_ == rhs.v1_);
01619         }
01620         BOOST_UBLAS_INLINE
01621         bool less(const self_type& rhs) const {
01622             return (v1_ < rhs.v1_);
01623         }
01624         BOOST_UBLAS_INLINE
01625         friend bool operator == (const self_type& lhs, const self_type& rhs) {
01626             return lhs.equal(rhs);
01627         }
01628         BOOST_UBLAS_INLINE
01629         friend bool operator != (const self_type& lhs, const self_type& rhs) {
01630             return !lhs.equal(rhs);
01631         }
01632         BOOST_UBLAS_INLINE
01633         friend bool operator < (const self_type& lhs, const self_type& rhs) {
01634             return lhs.less(rhs);
01635         }
01636         BOOST_UBLAS_INLINE
01637         friend bool operator >= (const self_type& lhs, const self_type& rhs) {
01638             return !lhs.less(rhs);
01639         }
01640         BOOST_UBLAS_INLINE
01641         friend bool operator > (const self_type& lhs, const self_type& rhs) {
01642             return rhs.less(lhs);
01643         }
01644         BOOST_UBLAS_INLINE
01645         friend bool operator <= (const self_type& lhs, const self_type& rhs) {
01646             return !rhs.less(lhs);
01647         }
01648 
01649     private:
01650         size_type i_;
01651         typename V::value1_type v1_;
01652         typename V::value2_type v2_;
01653         bool dirty_;
01654         bool is_copy_;
01655      };
01656 
01657     template <class V1, class V2>
01658     class index_pair_array:
01659         private boost::noncopyable {
01660 
01661         typedef index_pair_array<V1, V2> self_type;
01662     public:
01663         typedef typename V1::value_type value1_type;
01664         typedef typename V2::value_type value2_type;
01665 
01666         typedef typename V1::size_type size_type;
01667         typedef typename V1::difference_type difference_type;
01668         typedef index_pair<self_type> value_type;
01669         // There is nothing that can be referenced directly. Always return a copy of the index_pair
01670         typedef value_type reference;
01671         typedef const value_type const_reference;
01672 
01673         BOOST_UBLAS_INLINE
01674         index_pair_array(size_type size, V1& data1, V2& data2) :
01675               size_(size),data1_(data1),data2_(data2) {}
01676 
01677         BOOST_UBLAS_INLINE
01678         size_type size() const {
01679             return size_;
01680         }
01681 
01682         BOOST_UBLAS_INLINE
01683         const_reference operator () (size_type i) const {
01684             return value_type((*this), i);
01685         }
01686         BOOST_UBLAS_INLINE
01687         reference operator () (size_type i) {
01688             return value_type((*this), i);
01689         }
01690 
01691         typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
01692         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
01693 
01694         BOOST_UBLAS_INLINE
01695         iterator begin() {
01696             return iterator( (*this), 0);
01697         }
01698         BOOST_UBLAS_INLINE
01699         iterator end() {
01700             return iterator( (*this), size());
01701         }
01702 
01703         BOOST_UBLAS_INLINE
01704         const_iterator begin() const {
01705             return const_iterator( (*this), 0);
01706         }
01707         BOOST_UBLAS_INLINE
01708         const_iterator end() const {
01709             return const_iterator( (*this), size());
01710         }
01711 
01712         // unnecessary function:
01713         BOOST_UBLAS_INLINE
01714         bool equal(size_type i1, size_type i2) const {
01715             return data1_[i1] == data1_[i2];
01716         }
01717         BOOST_UBLAS_INLINE
01718         bool less(size_type i1, size_type i2) const {
01719             return data1_[i1] < data1_[i2];
01720         }
01721 
01722         // gives a large speedup
01723         BOOST_UBLAS_INLINE
01724         friend void iter_swap(const iterator& lhs, const iterator& rhs) {
01725             const size_type i1 = lhs.index();
01726             const size_type i2 = rhs.index();
01727             std::swap(lhs().data1_[i1], rhs().data1_[i2]);
01728             std::swap(lhs().data2_[i1], rhs().data2_[i2]);
01729         }
01730 
01731     private:
01732         size_type size_;
01733         V1& data1_;
01734         V2& data2_;
01735 
01736         // friend class value_type;
01737         friend class index_pair<self_type>;
01738     };
01739 
01740     template <class M>
01741     class index_triple :
01742         private boost::noncopyable,
01743         public container_reference<M> {
01744 
01745         typedef index_triple<M> self_type;
01746     public:
01747         typedef typename M::size_type size_type;
01748 
01749         BOOST_UBLAS_INLINE
01750         index_triple(M& m, size_type i) :
01751             container_reference<M>(m), i_(i),
01752             v1_(m.data1_[i]), v2_(m.data2_[i]), v3_(m.data3_[i]),
01753             dirty_(false), is_copy_(false) {}
01754         BOOST_UBLAS_INLINE
01755         index_triple(const self_type& rhs) :
01756             container_reference<M>(rhs()), i_(0),
01757             v1_(rhs.v1_), v2_(rhs.v2_), v3_(rhs.v3_),
01758             dirty_(false), is_copy_(true) {}
01759         BOOST_UBLAS_INLINE
01760         ~index_triple() {
01761             if (dirty_ && (!is_copy_) ) {
01762                 (*this)().data1_[i_] = v1_;
01763                 (*this)().data2_[i_] = v2_;
01764                 (*this)().data3_[i_] = v3_;
01765             }
01766         }
01767 
01768         BOOST_UBLAS_INLINE
01769         self_type& operator=(const self_type& rhs) {
01770             v1_ = rhs.v1_;
01771             v2_ = rhs.v2_;
01772             v3_ = rhs.v3_;
01773             dirty_ = true;
01774             return *this;
01775         }
01776 
01777         BOOST_UBLAS_INLINE
01778         void swap(self_type& rhs) {
01779             self_type tmp(rhs);
01780             rhs = *this;
01781             *this = tmp;
01782         }
01783         BOOST_UBLAS_INLINE
01784         friend void swap(self_type& lhs, self_type& rhs) {
01785             lhs.swap(rhs);
01786         }
01787 
01788         BOOST_UBLAS_INLINE
01789         bool equal(const self_type& rhs) const {
01790             return ((v1_ == rhs.v1_) && (v2_ == rhs.v2_));
01791         }
01792         BOOST_UBLAS_INLINE
01793         bool less(const self_type& rhs) const {
01794             return ((v1_ < rhs.v1_) ||
01795                     (v1_ == rhs.v1_ && v2_ < rhs.v2_));
01796         }
01797         BOOST_UBLAS_INLINE
01798         friend bool operator == (const self_type& lhs, const self_type& rhs) {
01799             return lhs.equal(rhs);
01800         }
01801         BOOST_UBLAS_INLINE
01802         friend bool operator != (const self_type& lhs, const self_type& rhs) {
01803             return !lhs.equal(rhs);
01804         }
01805         BOOST_UBLAS_INLINE
01806         friend bool operator < (const self_type& lhs, const self_type& rhs) {
01807             return lhs.less(rhs);
01808         }
01809         BOOST_UBLAS_INLINE
01810         friend bool operator >= (const self_type& lhs, const self_type& rhs) {
01811             return !lhs.less(rhs);
01812         }
01813         BOOST_UBLAS_INLINE
01814         friend bool operator > (const self_type& lhs, const self_type& rhs) {
01815             return rhs.less(lhs);
01816         }
01817         BOOST_UBLAS_INLINE
01818         friend bool operator <= (const self_type& lhs, const self_type& rhs) {
01819             return !rhs.less(lhs);
01820         }
01821 
01822     private:
01823         size_type i_;
01824         typename M::value1_type v1_;
01825         typename M::value2_type v2_;
01826         typename M::value3_type v3_;
01827         bool dirty_;
01828         bool is_copy_;
01829     };
01830 
01831     template <class V1, class V2, class V3>
01832     class index_triple_array:
01833         private boost::noncopyable {
01834 
01835         typedef index_triple_array<V1, V2, V3> self_type;
01836     public:
01837         typedef typename V1::value_type value1_type;
01838         typedef typename V2::value_type value2_type;
01839         typedef typename V3::value_type value3_type;
01840 
01841         typedef typename V1::size_type size_type;
01842         typedef typename V1::difference_type difference_type;
01843         typedef index_triple<self_type> value_type;
01844         // There is nothing that can be referenced directly. Always return a copy of the index_triple
01845         typedef value_type reference;
01846         typedef const value_type const_reference;
01847 
01848         BOOST_UBLAS_INLINE
01849         index_triple_array(size_type size, V1& data1, V2& data2, V3& data3) :
01850               size_(size),data1_(data1),data2_(data2),data3_(data3) {}
01851 
01852         BOOST_UBLAS_INLINE
01853         size_type size() const {
01854             return size_;
01855         }
01856 
01857         BOOST_UBLAS_INLINE
01858         const_reference operator () (size_type i) const {
01859             return value_type((*this), i);
01860         }
01861         BOOST_UBLAS_INLINE
01862         reference operator () (size_type i) {
01863             return value_type((*this), i);
01864         }
01865 
01866         typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
01867         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
01868 
01869         BOOST_UBLAS_INLINE
01870         iterator begin() {
01871             return iterator( (*this), 0);
01872         }
01873         BOOST_UBLAS_INLINE
01874         iterator end() {
01875             return iterator( (*this), size());
01876         }
01877 
01878         BOOST_UBLAS_INLINE
01879         const_iterator begin() const {
01880             return const_iterator( (*this), 0);
01881         }
01882         BOOST_UBLAS_INLINE
01883         const_iterator end() const {
01884             return const_iterator( (*this), size());
01885         }
01886 
01887         // unnecessary function:
01888         BOOST_UBLAS_INLINE
01889         bool equal(size_type i1, size_type i2) const {
01890             return ((data1_[i1] == data1_[i2]) && (data2_[i1] == data2_[i2]));
01891         }
01892         BOOST_UBLAS_INLINE
01893         bool less(size_type i1, size_type i2) const {
01894             return ((data1_[i1] < data1_[i2]) ||
01895                     (data1_[i1] == data1_[i2] && data2_[i1] < data2_[i2]));
01896         }
01897 
01898         // gives a large speedup
01899         BOOST_UBLAS_INLINE
01900         friend void iter_swap(const iterator& lhs, const iterator& rhs) {
01901             const size_type i1 = lhs.index();
01902             const size_type i2 = rhs.index();
01903             std::swap(lhs().data1_[i1], rhs().data1_[i2]);
01904             std::swap(lhs().data2_[i1], rhs().data2_[i2]);
01905             std::swap(lhs().data3_[i1], rhs().data3_[i2]);
01906         }
01907 
01908     private:
01909         size_type size_;
01910         V1& data1_;
01911         V2& data2_;
01912         V3& data3_;
01913 
01914         // friend class value_type;
01915         friend class index_triple<self_type>;
01916     };
01917 
01918 }}}
01919 
01920 #endif