ceph/src/boost/boost/numeric/ublas/storage.hpp

   1 //
   2 //  Copyright (c) 2000-2002
   3 //  Joerg Walter, Mathias Koch
   4 //
   5 //  Distributed under the Boost Software License, Version 1.0. (See
   6 //  accompanying file LICENSE_1_0.txt or copy at
   7 //  http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 //  The authors gratefully acknowledge the support of
  10 //  GeNeSys mbH & Co. KG in producing this work.
  11 //
  12
  13 #ifndef BOOST_UBLAS_STORAGE_H
  14 #define BOOST_UBLAS_STORAGE_H
  15
  16 #include <algorithm>
  17 #ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
  18 #include <boost/shared_array.hpp>
  19 #endif
  20
  21 #include <boost/serialization/array.hpp>
  22 #include <boost/serialization/collection_size_type.hpp>
  23 #include <boost/serialization/nvp.hpp>
  24
  25 #include <boost/numeric/ublas/exception.hpp>
  26 #include <boost/numeric/ublas/traits.hpp>
  27 #include <boost/numeric/ublas/detail/iterator.hpp>
  28
  29
  30 namespace boost { namespace numeric { namespace ublas {
  31
  32
  33     // Base class for Storage Arrays - see the Barton Nackman trick
  34     template<class E>
  35     class storage_array:
  36         private nonassignable {
  37     };
  38
  39
  40     // Unbounded array - with allocator
  41     template<class T, class ALLOC>
  42     class unbounded_array:
  43         public storage_array<unbounded_array<T, ALLOC> > {
  44
  45         typedef unbounded_array<T, ALLOC> self_type;
  46     public:
  47         typedef ALLOC allocator_type;
  48         typedef typename ALLOC::size_type size_type;
  49         typedef typename ALLOC::difference_type difference_type;
  50         typedef T value_type;
  51         typedef const T &const_reference;
  52         typedef T &reference;
  53         typedef const T *const_pointer;
  54         typedef T *pointer;
  55         typedef const_pointer const_iterator;
  56         typedef pointer iterator;
  57
  58         // Construction and destruction
  59         explicit BOOST_UBLAS_INLINE
  60         unbounded_array (const ALLOC &a = ALLOC()):
  61             alloc_ (a), size_ (0) {
  62             data_ = 0;
  63         }
  64         explicit BOOST_UBLAS_INLINE
  65         unbounded_array (size_type size, const ALLOC &a = ALLOC()):
  66             alloc_(a), size_ (size) {
  67           if (size_) {
  68               data_ = alloc_.allocate (size_);
  69 //Disabled warning C4127 because the conditional expression is constant
  70 #ifdef _MSC_VER
  71 #pragma warning(push)
  72 #pragma warning(disable: 4127)
  73 #endif
  74               if (! detail::has_trivial_constructor<T>::value) {
  75 #ifdef _MSC_VER
  76 #pragma warning(pop)
  77 #endif
  78                   for (pointer d = data_; d != data_ + size_; ++d)
  79                       alloc_.construct(d, value_type());
  80               }
  81           }
  82           else
  83               data_ = 0;
  84         }
  85         // No value initialised, but still be default constructed
  86         BOOST_UBLAS_INLINE
  87         unbounded_array (size_type size, const value_type &init, const ALLOC &a = ALLOC()):
  88             alloc_ (a), size_ (size) {
  89             if (size_) {
  90                 data_ = alloc_.allocate (size_);
  91                 std::uninitialized_fill (begin(), end(), init);
  92             }
  93             else
  94                 data_ = 0;
  95         }
  96         BOOST_UBLAS_INLINE
  97         unbounded_array (const unbounded_array &c):
  98             storage_array<unbounded_array<T, ALLOC> >(),
  99             alloc_ (c.alloc_), size_ (c.size_) {
 100             if (size_) {
 101                 data_ = alloc_.allocate (size_);
 102                 std::uninitialized_copy (c.begin(), c.end(), begin());
 103             }
 104             else
 105                 data_ = 0;
 106         }
 107 #ifdef BOOST_UBLAS_CPP_GE_2011
 108                 BOOST_UBLAS_INLINE
 109                 unbounded_array (unbounded_array &&c) :
 110                         storage_array<unbounded_array<T, ALLOC> >(),
 111                         alloc_ (std::move(c.alloc_)), size_ (c.size_), data_(c.data_)
 112                 {
 113                         c.size_ = 0;
 114                         c.data_ = nullptr;
 115                 }
 116 #endif
 117         BOOST_UBLAS_INLINE
 118         ~unbounded_array () {
 119             if (size_) {
 120 //Disabled warning C4127 because the conditional expression is constant
 121 #ifdef _MSC_VER
 122 #pragma warning(push)
 123 #pragma warning(disable: 4127)
 124 #endif
 125                 if (! detail::has_trivial_destructor<T>::value) {
 126 #ifdef _MSC_VER
 127 #pragma warning(pop)
 128 #endif
 129                     // std::_Destroy (begin(), end(), alloc_);
 130                     const iterator i_end = end();
 131                     for (iterator i = begin (); i != i_end; ++i) {
 132                         iterator_destroy (i);
 133                     }
 134                 }
 135                 alloc_.deallocate (data_, size_);
 136             }
 137         }
 138
 139         // Resizing
 140     private:
 141         BOOST_UBLAS_INLINE
 142         void resize_internal (const size_type size, const value_type init, const bool preserve) {
 143             if (size != size_) {
 144                 pointer p_data = data_;
 145                 if (size) {
 146                     data_ = alloc_.allocate (size);
 147                     if (preserve) {
 148                         pointer si = p_data;
 149                         pointer di = data_;
 150                         if (size < size_) {
 151                             for (; di != data_ + size; ++di) {
 152                                 alloc_.construct (di, *si);
 153                                 ++si;
 154                             }
 155                         }
 156                         else {
 157                             for (; si != p_data + size_; ++si) {
 158                                 alloc_.construct (di, *si);
 159                                 ++di;
 160                             }
 161                             for (; di != data_ + size; ++di) {
 162                                 alloc_.construct (di, init);
 163                             }
 164                         }
 165                     }
 166                     else {
 167 //Disabled warning C4127 because the conditional expression is constant
 168 #ifdef _MSC_VER
 169 #pragma warning(push)
 170 #pragma warning(disable: 4127)
 171 #endif
 172                         if (! detail::has_trivial_constructor<T>::value) {
 173 #ifdef _MSC_VER
 174 #pragma warning(pop)
 175 #endif
 176                             for (pointer di = data_; di != data_ + size; ++di)
 177                                 alloc_.construct (di, value_type());
 178                         }
 179                     }
 180                 }
 181
 182                 if (size_) {
 183 //Disabled warning C4127 because the conditional expression is constant
 184 #ifdef _MSC_VER
 185 #pragma warning(push)
 186 #pragma warning(disable: 4127)
 187 #endif
 188                     if (! detail::has_trivial_destructor<T>::value) {
 189 #ifdef _MSC_VER
 190 #pragma warning(pop)
 191 #endif
 192                         for (pointer si = p_data; si != p_data + size_; ++si)
 193                             alloc_.destroy (si);
 194                     }
 195                     alloc_.deallocate (p_data, size_);
 196                 }
 197
 198                 if (!size)
 199                     data_ = 0;
 200                 size_ = size;
 201             }
 202         }
 203     public:
 204         BOOST_UBLAS_INLINE
 205         void resize (size_type size) {
 206             resize_internal (size, value_type (), false);
 207         }
 208         BOOST_UBLAS_INLINE
 209         void resize (size_type size, value_type init) {
 210             resize_internal (size, init, true);
 211         }
 212
 213         // Random Access Container
 214         BOOST_UBLAS_INLINE
 215         size_type max_size () const {
 216             return ALLOC ().max_size();
 217         }
 218
 219         BOOST_UBLAS_INLINE
 220         bool empty () const {
 221             return size_ == 0;
 222         }
 223
 224         BOOST_UBLAS_INLINE
 225         size_type size () const {
 226             return size_;
 227         }
 228
 229         // Element access
 230         BOOST_UBLAS_INLINE
 231         const_reference operator [] (size_type i) const {
 232             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 233             return data_ [i];
 234         }
 235         BOOST_UBLAS_INLINE
 236         reference operator [] (size_type i) {
 237             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 238             return data_ [i];
 239         }
 240
 241         // Assignment
 242         BOOST_UBLAS_INLINE
 243         unbounded_array &operator = (const unbounded_array &a) {
 244             if (this != &a) {
 245                 resize (a.size_);
 246                 std::copy (a.data_, a.data_ + a.size_, data_);
 247             }
 248             return *this;
 249         }
 250         BOOST_UBLAS_INLINE
 251         unbounded_array &assign_temporary (unbounded_array &a) {
 252             swap (a);
 253             return *this;
 254         }
 255
 256         // Swapping
 257         BOOST_UBLAS_INLINE
 258         void swap (unbounded_array &a) {
 259             if (this != &a) {
 260                 std::swap (size_, a.size_);
 261                 std::swap (data_, a.data_);
 262             }
 263         }
 264         BOOST_UBLAS_INLINE
 265         friend void swap (unbounded_array &a1, unbounded_array &a2) {
 266             a1.swap (a2);
 267         }
 268
 269         BOOST_UBLAS_INLINE
 270         const_iterator begin () const {
 271             return data_;
 272         }
 273         BOOST_UBLAS_INLINE
 274         const_iterator cbegin () const {
 275             return begin ();
 276         }
 277         BOOST_UBLAS_INLINE
 278         const_iterator end () const {
 279             return data_ + size_;
 280         }
 281         BOOST_UBLAS_INLINE
 282         const_iterator cend () const {
 283             return end ();
 284         }
 285
 286         BOOST_UBLAS_INLINE
 287         iterator begin () {
 288             return data_;
 289         }
 290         BOOST_UBLAS_INLINE
 291         iterator end () {
 292             return data_ + size_;
 293         }
 294
 295         // Reverse iterators
 296         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 297         typedef std::reverse_iterator<iterator> reverse_iterator;
 298
 299         BOOST_UBLAS_INLINE
 300         const_reverse_iterator rbegin () const {
 301             return const_reverse_iterator (end ());
 302         }
 303         BOOST_UBLAS_INLINE
 304         const_reverse_iterator crbegin () const {
 305             return rbegin ();
 306         }
 307         BOOST_UBLAS_INLINE
 308         const_reverse_iterator rend () const {
 309             return const_reverse_iterator (begin ());
 310         }
 311         BOOST_UBLAS_INLINE
 312         const_reverse_iterator crend () const {
 313             return rend ();
 314         }
 315         BOOST_UBLAS_INLINE
 316         reverse_iterator rbegin () {
 317             return reverse_iterator (end ());
 318         }
 319         BOOST_UBLAS_INLINE
 320         reverse_iterator rend () {
 321             return reverse_iterator (begin ());
 322         }
 323
 324         // Allocator
 325         allocator_type get_allocator () {
 326             return alloc_;
 327         }
 328
 329     private:
 330         friend class boost::serialization::access;
 331
 332         // Serialization
 333         template<class Archive>
 334         void serialize(Archive & ar, const unsigned int /*version*/)
 335         {
 336             serialization::collection_size_type s(size_);
 337             ar & serialization::make_nvp("size",s);
 338             if ( Archive::is_loading::value ) {
 339                 resize(s);
 340             }
 341             ar & serialization::make_array(data_, s);
 342         }
 343
 344     private:
 345         // Handle explict destroy on a (possibly indexed) iterator
 346         BOOST_UBLAS_INLINE
 347         static void iterator_destroy (iterator &i) {
 348             (void)(i);
 349             (&(*i)) -> ~value_type ();
 350         }
 351         ALLOC alloc_;
 352         size_type size_;
 353         pointer data_;
 354     };
 355
 356     // Bounded array - with allocator for size_type and difference_type
 357     template<class T, std::size_t N, class ALLOC>
 358     class bounded_array:
 359         public storage_array<bounded_array<T, N, ALLOC> > {
 360
 361         typedef bounded_array<T, N, ALLOC> self_type;
 362     public:
 363         // No allocator_type as ALLOC is not used for allocation
 364         typedef typename ALLOC::size_type size_type;
 365         typedef typename ALLOC::difference_type difference_type;
 366         typedef T value_type;
 367         typedef const T &const_reference;
 368         typedef T &reference;
 369         typedef const T *const_pointer;
 370         typedef T *pointer;
 371         typedef const_pointer const_iterator;
 372         typedef pointer iterator;
 373
 374         // Construction and destruction
 375         BOOST_UBLAS_INLINE
 376         bounded_array ():
 377             size_ (0) /*, data_ ()*/ {   // size 0 - use bounded_vector to default construct with size N
 378         }
 379         explicit BOOST_UBLAS_INLINE
 380         bounded_array (size_type size):
 381             size_ (size) /*, data_ ()*/ {
 382             BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
 383             // data_ (an array) elements are already default constructed
 384         }
 385         BOOST_UBLAS_INLINE
 386         bounded_array (size_type size, const value_type &init):
 387             size_ (size) /*, data_ ()*/ {
 388             BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
 389             // ISSUE elements should be value constructed here, but we must fill instead as already default constructed
 390             std::fill (begin(), end(), init) ;
 391         }
 392         BOOST_UBLAS_INLINE
 393         bounded_array (const bounded_array &c):
 394             size_ (c.size_)  {
 395             // ISSUE elements should be copy constructed here, but we must copy instead as already default constructed
 396             std::copy (c.begin(), c.end(), begin());
 397         }
 398
 399         // Resizing
 400         BOOST_UBLAS_INLINE
 401         void resize (size_type size) {
 402             BOOST_UBLAS_CHECK (size <= N, bad_size ());
 403             size_ = size;
 404         }
 405         BOOST_UBLAS_INLINE
 406         void resize (size_type size, value_type init) {
 407             BOOST_UBLAS_CHECK (size <= N, bad_size ());
 408             if (size > size_)
 409                 std::fill (data_ + size_, data_ + size, init);
 410             size_ = size;
 411         }
 412
 413         // Random Access Container
 414         BOOST_UBLAS_INLINE
 415         size_type max_size () const {
 416             return N;
 417         }
 418
 419         BOOST_UBLAS_INLINE
 420         bool empty () const {
 421             return size_ == 0;
 422         }
 423
 424         BOOST_UBLAS_INLINE
 425         size_type size () const {
 426             return size_;
 427         }
 428
 429         // Element access
 430         BOOST_UBLAS_INLINE
 431         const_reference operator [] (size_type i) const {
 432             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 433             return data_ [i];
 434         }
 435         BOOST_UBLAS_INLINE
 436         reference operator [] (size_type i) {
 437             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 438             return data_ [i];
 439         }
 440
 441         // Assignment
 442         BOOST_UBLAS_INLINE
 443         bounded_array &operator = (const bounded_array &a) {
 444             if (this != &a) {
 445                 resize (a.size_);
 446                 std::copy (a.data_, a.data_ + a.size_, data_);
 447             }
 448             return *this;
 449         }
 450         BOOST_UBLAS_INLINE
 451         bounded_array &assign_temporary (bounded_array &a) {
 452             *this = a;
 453             return *this;
 454         }
 455
 456         // Swapping
 457         BOOST_UBLAS_INLINE
 458         void swap (bounded_array &a) {
 459             if (this != &a) {
 460                 std::swap (size_, a.size_);
 461                 std::swap_ranges (data_, data_ + (std::max) (size_, a.size_), a.data_);
 462             }
 463         }
 464         BOOST_UBLAS_INLINE
 465         friend void swap (bounded_array &a1, bounded_array &a2) {
 466             a1.swap (a2);
 467         }
 468
 469         BOOST_UBLAS_INLINE
 470         const_iterator begin () const {
 471             return data_;
 472         }
 473         BOOST_UBLAS_INLINE
 474         const_iterator cbegin () const {
 475             return begin ();
 476         }
 477         BOOST_UBLAS_INLINE
 478         const_iterator end () const {
 479             return data_ + size_;
 480         }
 481         BOOST_UBLAS_INLINE
 482         const_iterator cend () const {
 483             return end ();
 484         }
 485
 486         BOOST_UBLAS_INLINE
 487         iterator begin () {
 488             return data_;
 489         }
 490         BOOST_UBLAS_INLINE
 491         iterator end () {
 492             return data_ + size_;
 493         }
 494
 495         // Reverse iterators
 496         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 497         typedef std::reverse_iterator<iterator> reverse_iterator;
 498
 499         BOOST_UBLAS_INLINE
 500         const_reverse_iterator rbegin () const {
 501             return const_reverse_iterator (end ());
 502         }
 503         BOOST_UBLAS_INLINE
 504         const_reverse_iterator crbegin () const {
 505             return rbegin ();
 506         }
 507         BOOST_UBLAS_INLINE
 508         const_reverse_iterator rend () const {
 509             return const_reverse_iterator (begin ());
 510         }
 511         BOOST_UBLAS_INLINE
 512         const_reverse_iterator crend () const {
 513             return rend ();
 514         }
 515         BOOST_UBLAS_INLINE
 516         reverse_iterator rbegin () {
 517             return reverse_iterator (end ());
 518         }
 519         BOOST_UBLAS_INLINE
 520         reverse_iterator rend () {
 521             return reverse_iterator (begin ());
 522         }
 523
 524     private:
 525         // Serialization
 526         friend class boost::serialization::access;
 527
 528         template<class Archive>
 529         void serialize(Archive & ar, const unsigned int /*version*/)
 530         {
 531             serialization::collection_size_type s(size_);
 532             ar & serialization::make_nvp("size", s);
 533             if ( Archive::is_loading::value ) {
 534                 if (s > N) bad_size("too large size in bounded_array::load()\n").raise();
 535                 resize(s);
 536             }
 537             ar & serialization::make_array(data_, s);
 538         }
 539
 540     private:
 541         size_type size_;
 542 // MSVC does not like arrays of size 0 in base classes.  Hence, this conditionally changes the size to 1
 543 #ifdef _MSC_VER
 544         BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [(N>0)?N:1];
 545 #else
 546         BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [N];
 547 #endif
 548     };
 549
 550
 551     // Array adaptor with normal deep copy semantics of elements
 552     template<class T>
 553     class array_adaptor:
 554         public storage_array<array_adaptor<T> > {
 555
 556         typedef array_adaptor<T> self_type;
 557     public:
 558         typedef std::size_t size_type;
 559         typedef std::ptrdiff_t difference_type;
 560         typedef T value_type;
 561         typedef const T &const_reference;
 562         typedef T &reference;
 563         typedef const T *const_pointer;
 564         typedef T *pointer;
 565
 566         // Construction and destruction
 567         BOOST_UBLAS_INLINE
 568         array_adaptor ():
 569             size_ (0), own_ (true), data_ (new value_type [0]) {
 570         }
 571         explicit BOOST_UBLAS_INLINE
 572         array_adaptor (size_type size):
 573             size_ (size), own_ (true), data_ (new value_type [size]) {
 574         }
 575         BOOST_UBLAS_INLINE
 576         array_adaptor (size_type size, const value_type &init):
 577             size_ (size), own_ (true), data_ (new value_type [size]) {
 578             std::fill (data_, data_ + size_, init);
 579         }
 580         BOOST_UBLAS_INLINE
 581         array_adaptor (size_type size, pointer data):
 582             size_ (size), own_ (false), data_ (data) {}
 583
 584         template <size_t N>
 585         BOOST_UBLAS_INLINE array_adaptor (T (&data)[N]):
 586             size_ (N), own_ (false), data_ (data) {}
 587         BOOST_UBLAS_INLINE
 588         array_adaptor (const array_adaptor &a):
 589             storage_array<self_type> (),
 590             size_ (a.size_), own_ (true), data_ (new value_type [a.size_]) {
 591             *this = a;
 592         }
 593         BOOST_UBLAS_INLINE
 594         ~array_adaptor () {
 595             if (own_) {
 596                 delete [] data_;
 597             }
 598         }
 599
 600         // Resizing
 601     private:
 602         BOOST_UBLAS_INLINE
 603         void resize_internal (size_type size, value_type init, bool preserve = true) {
 604            if (size != size_) {
 605                 pointer data = new value_type [size];
 606                 if (preserve) {
 607                     std::copy (data_, data_ + (std::min) (size, size_), data);
 608                     std::fill (data + (std::min) (size, size_), data + size, init);
 609                 }
 610                 if (own_)
 611                     delete [] data_;
 612                 size_ = size;
 613                 own_ = true;
 614                 data_ = data;
 615             }
 616         }
 617         BOOST_UBLAS_INLINE
 618         void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
 619             if (data != data_) {
 620                 if (preserve) {
 621                     std::copy (data_, data_ + (std::min) (size, size_), data);
 622                     std::fill (data + (std::min) (size, size_), data + size, init);
 623                 }
 624                 if (own_)
 625                     delete [] data_;
 626                 own_ = false;
 627                 data_ = data;
 628             }
 629             else {
 630                 std::fill (data + (std::min) (size, size_), data + size, init);
 631             }
 632             size_ = size;
 633         }
 634     public:
 635         BOOST_UBLAS_INLINE
 636         void resize (size_type size) {
 637             resize_internal (size, value_type (), false);
 638         }
 639         BOOST_UBLAS_INLINE
 640         void resize (size_type size, value_type init) {
 641             resize_internal (size, init, true);
 642         }
 643         BOOST_UBLAS_INLINE
 644         void resize (size_type size, pointer data) {
 645             resize_internal (size, data, value_type (), false);
 646         }
 647         BOOST_UBLAS_INLINE
 648         void resize (size_type size, pointer data, value_type init) {
 649             resize_internal (size, data, init, true);
 650         }
 651
 652         template <size_t N>
 653         BOOST_UBLAS_INLINE void resize (T (&data)[N]) {
 654             resize_internal (N, data, value_type (), false);
 655         }
 656
 657         template <size_t N>
 658         BOOST_UBLAS_INLINE void resize (T (&data)[N], value_type init) {
 659             resize_internal (N, data, init, true);
 660         }
 661
 662         BOOST_UBLAS_INLINE
 663         size_type size () const {
 664             return size_;
 665         }
 666
 667         // Element access
 668         BOOST_UBLAS_INLINE
 669         const_reference operator [] (size_type i) const {
 670             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 671             return data_ [i];
 672         }
 673         BOOST_UBLAS_INLINE
 674         reference operator [] (size_type i) {
 675             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 676             return data_ [i];
 677         }
 678
 679         // Assignment
 680         BOOST_UBLAS_INLINE
 681         array_adaptor &operator = (const array_adaptor &a) {
 682             if (this != &a) {
 683                 resize (a.size_);
 684                 std::copy (a.data_, a.data_ + a.size_, data_);
 685             }
 686             return *this;
 687         }
 688         BOOST_UBLAS_INLINE
 689         array_adaptor &assign_temporary (array_adaptor &a) {
 690             if (own_ && a.own_)
 691                 swap (a);
 692             else
 693                 *this = a;
 694             return *this;
 695         }
 696
 697         // Swapping
 698         BOOST_UBLAS_INLINE
 699         void swap (array_adaptor &a) {
 700             if (this != &a) {
 701                 std::swap (size_, a.size_);
 702                 std::swap (own_, a.own_);
 703                 std::swap (data_, a.data_);
 704             }
 705         }
 706         BOOST_UBLAS_INLINE
 707         friend void swap (array_adaptor &a1, array_adaptor &a2) {
 708             a1.swap (a2);
 709         }
 710
 711         // Iterators simply are pointers.
 712
 713         typedef const_pointer const_iterator;
 714
 715         BOOST_UBLAS_INLINE
 716         const_iterator begin () const {
 717             return data_;
 718         }
 719         BOOST_UBLAS_INLINE
 720         const_iterator cbegin () const {
 721             return begin ();
 722         }
 723         BOOST_UBLAS_INLINE
 724         const_iterator end () const {
 725             return data_ + size_;
 726         }
 727         BOOST_UBLAS_INLINE
 728         const_iterator cend () const {
 729             return end ();
 730         }
 731
 732         typedef pointer iterator;
 733
 734         BOOST_UBLAS_INLINE
 735         iterator begin () {
 736             return data_;
 737         }
 738         BOOST_UBLAS_INLINE
 739         iterator end () {
 740             return data_ + size_;
 741         }
 742
 743         // Reverse iterators
 744         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 745         typedef std::reverse_iterator<iterator> reverse_iterator;
 746
 747         BOOST_UBLAS_INLINE
 748         const_reverse_iterator rbegin () const {
 749             return const_reverse_iterator (end ());
 750         }
 751         BOOST_UBLAS_INLINE
 752         const_reverse_iterator crbegin () const {
 753             return rbegin ();
 754         }
 755         BOOST_UBLAS_INLINE
 756         const_reverse_iterator rend () const {
 757             return const_reverse_iterator (begin ());
 758         }
 759         BOOST_UBLAS_INLINE
 760         const_reverse_iterator crend () const {
 761             return rend ();
 762         }
 763         BOOST_UBLAS_INLINE
 764         reverse_iterator rbegin () {
 765             return reverse_iterator (end ());
 766         }
 767         BOOST_UBLAS_INLINE
 768         reverse_iterator rend () {
 769             return reverse_iterator (begin ());
 770         }
 771
 772     private:
 773         size_type size_;
 774         bool own_;
 775         pointer data_;
 776     };
 777
 778 #ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
 779     // Array adaptor with shallow (reference) copy semantics of elements.
 780     // shared_array is used to maintain reference counts.
 781     // This class breaks the normal copy semantics for a storage container and is very dangerous!
 782     template<class T>
 783     class shallow_array_adaptor:
 784         public storage_array<shallow_array_adaptor<T> > {
 785
 786         typedef shallow_array_adaptor<T> self_type;
 787
 788         template<class TT>
 789         struct leaker {
 790             typedef void result_type;
 791             typedef TT *argument_type;
 792
 793             BOOST_UBLAS_INLINE
 794             result_type operator () (argument_type /* x */) {}
 795         };
 796
 797     public:
 798         typedef std::size_t size_type;
 799         typedef std::ptrdiff_t difference_type;
 800         typedef T value_type;
 801         typedef const T &const_reference;
 802         typedef T &reference;
 803         typedef const T *const_pointer;
 804         typedef T *pointer;
 805
 806         // Construction and destruction
 807         BOOST_UBLAS_INLINE
 808         shallow_array_adaptor ():
 809             size_ (0), own_ (true), data_ (new value_type [0]) {
 810         }
 811         explicit BOOST_UBLAS_INLINE
 812         shallow_array_adaptor (size_type size):
 813             size_ (size), own_ (true), data_ (new value_type [size]) {
 814         }
 815         BOOST_UBLAS_INLINE
 816         shallow_array_adaptor (size_type size, const value_type &init):
 817             size_ (size), own_ (true), data_ (new value_type [size]) {
 818             std::fill (data_.get (), data_.get () + size_, init);
 819         }
 820         BOOST_UBLAS_INLINE
 821         shallow_array_adaptor (size_type size, pointer data):
 822             size_ (size), own_ (false), data_ (data, leaker<value_type> ()) {}
 823         template <size_t N>
 824         BOOST_UBLAS_INLINE
 825         shallow_array_adaptor (T (&data)[N]):
 826             size_ (N), own_ (false), data_ (data, leaker<value_type> ()) {}
 827
 828         BOOST_UBLAS_INLINE
 829         shallow_array_adaptor (const shallow_array_adaptor &a):
 830             storage_array<self_type> (),
 831             size_ (a.size_), own_ (a.own_), data_ (a.data_) {}
 832
 833         BOOST_UBLAS_INLINE
 834         ~shallow_array_adaptor () {
 835         }
 836
 837         // Resizing
 838     private:
 839         BOOST_UBLAS_INLINE
 840         void resize_internal (size_type size, value_type init, bool preserve = true) {
 841             if (size != size_) {
 842                 shared_array<value_type> data (new value_type [size]);
 843                 if (preserve) {
 844                     std::copy (data_.get (), data_.get () + (std::min) (size, size_), data.get ());
 845                     std::fill (data.get () + (std::min) (size, size_), data.get () + size, init);
 846                 }
 847                 size_ = size;
 848                 own_ = true;
 849                 data_ = data;
 850             }
 851         }
 852         BOOST_UBLAS_INLINE
 853         void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
 854             if (preserve) {
 855                 std::copy (data_.get (), data_.get () + (std::min) (size, size_), data);
 856                 std::fill (data + (std::min) (size, size_), data + size, init);
 857             }
 858             size_ = size;
 859             own_ = false;
 860             data_.reset(data, leaker<value_type> ());
 861         }
 862     public:
 863         BOOST_UBLAS_INLINE
 864         void resize (size_type size) {
 865             resize_internal (size, value_type (), false);
 866         }
 867         BOOST_UBLAS_INLINE
 868         void resize (size_type size, value_type init) {
 869             resize_internal (size, init, true);
 870         }
 871         BOOST_UBLAS_INLINE
 872         void resize (size_type size, pointer data) {
 873             resize_internal (size, data, value_type (), false);
 874         }
 875         BOOST_UBLAS_INLINE
 876         void resize (size_type size, pointer data, value_type init) {
 877             resize_internal (size, data, init, true);
 878         }
 879         template <size_t N>
 880         BOOST_UBLAS_INLINE
 881         void resize (T (&data)[N]) {
 882             resize_internal (N, data, value_type (), false);
 883         }
 884         template <size_t N>
 885         BOOST_UBLAS_INLINE
 886         void resize (T (&data)[N], value_type init) {
 887             resize_internal (N, data, init, true);
 888         }
 889
 890         BOOST_UBLAS_INLINE
 891         size_type size () const {
 892             return size_;
 893         }
 894
 895         // Element access
 896         BOOST_UBLAS_INLINE
 897         const_reference operator [] (size_type i) const {
 898             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 899             return data_ [i];
 900         }
 901         BOOST_UBLAS_INLINE
 902         reference operator [] (size_type i) {
 903             BOOST_UBLAS_CHECK (i < size_, bad_index ());
 904             return data_ [i];
 905         }
 906
 907         // Assignment
 908         BOOST_UBLAS_INLINE
 909         shallow_array_adaptor &operator = (const shallow_array_adaptor &a) {
 910             if (this != &a) {
 911                 resize (a.size_);
 912                 std::copy (a.data_.get (), a.data_.get () + a.size_, data_.get ());
 913             }
 914             return *this;
 915         }
 916         BOOST_UBLAS_INLINE
 917         shallow_array_adaptor &assign_temporary (shallow_array_adaptor &a) {
 918             if (own_ && a.own_)
 919                 swap (a);
 920             else
 921                 *this = a;
 922             return *this;
 923         }
 924
 925         // Swapping
 926         BOOST_UBLAS_INLINE
 927         void swap (shallow_array_adaptor &a) {
 928             if (this != &a) {
 929                 std::swap (size_, a.size_);
 930                 std::swap (own_, a.own_);
 931                 std::swap (data_, a.data_);
 932             }
 933         }
 934         BOOST_UBLAS_INLINE
 935         friend void swap (shallow_array_adaptor &a1, shallow_array_adaptor &a2) {
 936             a1.swap (a2);
 937         }
 938
 939         // Iterators simply are pointers.
 940
 941         typedef const_pointer const_iterator;
 942
 943         BOOST_UBLAS_INLINE
 944         const_iterator begin () const {
 945             return data_.get ();
 946         }
 947         BOOST_UBLAS_INLINE
 948         const_iterator cbegin () const {
 949             return begin ();
 950         }
 951         BOOST_UBLAS_INLINE
 952         const_iterator end () const {
 953             return data_.get () + size_;
 954         }
 955         BOOST_UBLAS_INLINE
 956         const_iterator cend () const {
 957             return end ();
 958         }
 959
 960         typedef pointer iterator;
 961
 962         BOOST_UBLAS_INLINE
 963         iterator begin () {
 964             return data_.get ();
 965         }
 966         BOOST_UBLAS_INLINE
 967         iterator end () {
 968             return data_.get () + size_;
 969         }
 970
 971         // Reverse iterators
 972         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 973         typedef std::reverse_iterator<iterator> reverse_iterator;
 974
 975         BOOST_UBLAS_INLINE
 976         const_reverse_iterator rbegin () const {
 977             return const_reverse_iterator (end ());
 978         }
 979         BOOST_UBLAS_INLINE
 980         const_reverse_iterator crbegin () const {
 981             return rbegin ();
 982         }
 983         BOOST_UBLAS_INLINE
 984         const_reverse_iterator rend () const {
 985             return const_reverse_iterator (begin ());
 986         }
 987         BOOST_UBLAS_INLINE
 988         const_reverse_iterator crend () const {
 989             return rend ();
 990         }
 991         BOOST_UBLAS_INLINE
 992         reverse_iterator rbegin () {
 993             return reverse_iterator (end ());
 994         }
 995         BOOST_UBLAS_INLINE
 996         reverse_iterator rend () {
 997             return reverse_iterator (begin ());
 998         }
 999
1000     private:
1001         size_type size_;
1002         bool own_;
1003         shared_array<value_type> data_;
1004     };
1005
1006 #endif
1007
1008
1009     // Range class
1010     template <class Z, class D>
1011     class basic_range {
1012         typedef basic_range<Z, D> self_type;
1013     public:
1014         typedef Z size_type;
1015         typedef D difference_type;
1016         typedef size_type value_type;
1017         typedef value_type const_reference;
1018         typedef const_reference reference;
1019         typedef const value_type *const_pointer;
1020         typedef value_type *pointer;
1021
1022         // Construction and destruction
1023         BOOST_UBLAS_INLINE
1024         basic_range ():
1025             start_ (0), size_ (0) {}
1026         BOOST_UBLAS_INLINE
1027         basic_range (size_type start, size_type stop):
1028             start_ (start), size_ (stop - start) {
1029             BOOST_UBLAS_CHECK (start_ <= stop, bad_index ());
1030         }
1031
1032         BOOST_UBLAS_INLINE
1033         size_type start () const {
1034             return start_;
1035         }
1036         BOOST_UBLAS_INLINE
1037         size_type size () const {
1038             return size_;
1039         }
1040
1041         // Random Access Container
1042         BOOST_UBLAS_INLINE
1043         size_type max_size () const {
1044             return size_;
1045         }
1046
1047         BOOST_UBLAS_INLINE
1048         bool empty () const {
1049             return size_ == 0;
1050         }
1051
1052         // Element access
1053         BOOST_UBLAS_INLINE
1054         const_reference operator () (size_type i) const {
1055             BOOST_UBLAS_CHECK (i < size_, bad_index ());
1056             return start_ + i;
1057         }
1058
1059         // Composition
1060         BOOST_UBLAS_INLINE
1061         basic_range compose (const basic_range &r) const {
1062             return basic_range (start_ + r.start_, start_ + r.start_ + r.size_);
1063         }
1064
1065         // Comparison
1066         BOOST_UBLAS_INLINE
1067         bool operator == (const basic_range &r) const {
1068             return start_ == r.start_ && size_ == r.size_;
1069         }
1070         BOOST_UBLAS_INLINE
1071         bool operator != (const basic_range &r) const {
1072             return ! (*this == r);
1073         }
1074
1075         // Iterator types
1076     private:
1077         // Use and index
1078         typedef size_type const_subiterator_type;
1079
1080     public:
1081 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1082         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1083 #else
1084         class const_iterator:
1085             public container_const_reference<basic_range>,
1086             public random_access_iterator_base<std::random_access_iterator_tag,
1087                                                const_iterator, value_type> {
1088         public:
1089             typedef typename basic_range::value_type value_type;
1090             typedef typename basic_range::difference_type difference_type;
1091             typedef typename basic_range::const_reference reference;
1092             typedef typename basic_range::const_pointer pointer;
1093
1094             // Construction and destruction
1095             BOOST_UBLAS_INLINE
1096             const_iterator ():
1097                 container_const_reference<basic_range> (), it_ () {}
1098             BOOST_UBLAS_INLINE
1099             const_iterator (const basic_range &r, const const_subiterator_type &it):
1100                 container_const_reference<basic_range> (r), it_ (it) {}
1101
1102             // Arithmetic
1103             BOOST_UBLAS_INLINE
1104             const_iterator &operator ++ () {
1105                 ++ it_;
1106                 return *this;
1107             }
1108             BOOST_UBLAS_INLINE
1109             const_iterator &operator -- () {
1110                 BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
1111                 -- it_;
1112                 return *this;
1113             }
1114             BOOST_UBLAS_INLINE
1115             const_iterator &operator += (difference_type n) {
1116                 BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
1117                 it_ += n;
1118                 return *this;
1119             }
1120             BOOST_UBLAS_INLINE
1121             const_iterator &operator -= (difference_type n) {
1122                 BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
1123                 it_ -= n;
1124                 return *this;
1125             }
1126             BOOST_UBLAS_INLINE
1127             difference_type operator - (const const_iterator &it) const {
1128                 return it_ - it.it_;
1129             }
1130
1131             // Dereference
1132             BOOST_UBLAS_INLINE
1133             const_reference operator * () const {
1134                 BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
1135                 BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
1136                 return it_;
1137             }
1138
1139             BOOST_UBLAS_INLINE
1140             const_reference operator [] (difference_type n) const {
1141                 return *(*this + n);
1142             }
1143
1144             // Index
1145             BOOST_UBLAS_INLINE
1146             size_type index () const {
1147                 BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
1148                 BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
1149                 return it_ - (*this) ().start ();
1150             }
1151
1152             // Assignment
1153             BOOST_UBLAS_INLINE
1154             const_iterator &operator = (const const_iterator &it) {
1155                 // Comeau recommends...
1156                 this->assign (&it ());
1157                 it_ = it.it_;
1158                 return *this;
1159             }
1160
1161             // Comparison
1162             BOOST_UBLAS_INLINE
1163             bool operator == (const const_iterator &it) const {
1164                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1165                 return it_ == it.it_;
1166             }
1167             BOOST_UBLAS_INLINE
1168             bool operator < (const const_iterator &it) const {
1169                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1170                 return it_ < it.it_;
1171             }
1172
1173         private:
1174             const_subiterator_type it_;
1175         };
1176 #endif
1177
1178         BOOST_UBLAS_INLINE
1179         const_iterator begin () const {
1180             return const_iterator (*this, start_);
1181         }
1182         BOOST_UBLAS_INLINE
1183         const_iterator cbegin () const {
1184             return begin ();
1185         }
1186         BOOST_UBLAS_INLINE
1187         const_iterator end () const {
1188             return const_iterator (*this, start_ + size_);
1189         }
1190         BOOST_UBLAS_INLINE
1191         const_iterator cend () const {
1192             return end ();
1193         }
1194
1195         // Reverse iterator
1196         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1197
1198         BOOST_UBLAS_INLINE
1199         const_reverse_iterator rbegin () const {
1200             return const_reverse_iterator (end ());
1201         }
1202         BOOST_UBLAS_INLINE
1203         const_reverse_iterator crbegin () const {
1204             return rbegin ();
1205         }
1206         BOOST_UBLAS_INLINE
1207         const_reverse_iterator rend () const {
1208             return const_reverse_iterator (begin ());
1209         }
1210         BOOST_UBLAS_INLINE
1211         const_reverse_iterator crend () const {
1212             return rend ();
1213         }
1214
1215         BOOST_UBLAS_INLINE
1216         basic_range preprocess (size_type size) const {
1217             if (this != &all_)
1218                 return *this;
1219             return basic_range (0, size);
1220         }
1221         static
1222         BOOST_UBLAS_INLINE
1223         const basic_range &all () {
1224             return all_;
1225         }
1226
1227     private:
1228         size_type start_;
1229         size_type size_;
1230         static const basic_range all_;
1231     };
1232
1233     template <class Z, class D>
1234     const basic_range<Z,D> basic_range<Z,D>::all_  (0, size_type (-1));
1235
1236
1237     // Slice class
1238     template <class Z, class D>
1239     class basic_slice {
1240         typedef basic_slice<Z, D> self_type;
1241     public:
1242         typedef Z size_type;
1243         typedef D difference_type;
1244         typedef size_type value_type;
1245         typedef value_type const_reference;
1246         typedef const_reference reference;
1247         typedef const value_type *const_pointer;
1248         typedef value_type *pointer;
1249
1250         // Construction and destruction
1251         BOOST_UBLAS_INLINE
1252         basic_slice ():
1253             start_ (0), stride_ (0), size_ (0) {}
1254         BOOST_UBLAS_INLINE
1255         basic_slice (size_type start, difference_type stride, size_type size):
1256             start_ (start), stride_ (stride), size_ (size) {}
1257
1258         BOOST_UBLAS_INLINE
1259         size_type start () const {
1260             return start_;
1261         }
1262         BOOST_UBLAS_INLINE
1263         difference_type stride () const {
1264             return stride_;
1265         }
1266         BOOST_UBLAS_INLINE
1267         size_type size () const {
1268             return size_;
1269         }
1270
1271         // Random Access Container
1272         BOOST_UBLAS_INLINE
1273         size_type max_size () const {
1274             return size_;
1275         }
1276
1277         BOOST_UBLAS_INLINE
1278         bool empty () const {
1279             return size_ == 0;
1280         }
1281
1282         // Element access
1283         BOOST_UBLAS_INLINE
1284         const_reference operator () (size_type i) const {
1285             BOOST_UBLAS_CHECK (i < size_, bad_index ());
1286             BOOST_UBLAS_CHECK (stride_ >= 0 || start_ >= i * -stride_, bad_index ());
1287             return start_ + i * stride_;
1288         }
1289
1290         // Composition
1291         BOOST_UBLAS_INLINE
1292         basic_slice compose (const basic_range<size_type, difference_type> &r) const {
1293             BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * r.start(), bad_index ());
1294             return basic_slice (start_ + stride_ * r.start (), stride_, r.size ());
1295         }
1296         BOOST_UBLAS_INLINE
1297         basic_slice compose (const basic_slice &s) const {
1298             BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * s.start_, bad_index ());
1299             return basic_slice (start_ + stride_ * s.start_, stride_ * s.stride_, s.size_);
1300         }
1301
1302         // Comparison
1303         BOOST_UBLAS_INLINE
1304         bool operator == (const basic_slice &s) const {
1305             return start_ == s.start_ && stride_ == s.stride_ && size_ == s.size_;
1306         }
1307         BOOST_UBLAS_INLINE
1308         bool operator != (const basic_slice &s) const {
1309             return ! (*this == s);
1310         }
1311
1312         // Iterator types
1313     private:
1314         // Use and index
1315         typedef size_type const_subiterator_type;
1316
1317     public:
1318 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1319         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1320 #else
1321         class const_iterator:
1322             public container_const_reference<basic_slice>,
1323             public random_access_iterator_base<std::random_access_iterator_tag,
1324                                                const_iterator, value_type> {
1325         public:
1326             typedef typename basic_slice::value_type value_type;
1327             typedef typename basic_slice::difference_type difference_type;
1328             typedef typename basic_slice::const_reference reference;
1329             typedef typename basic_slice::const_pointer pointer;
1330
1331             // Construction and destruction
1332             BOOST_UBLAS_INLINE
1333             const_iterator ():
1334                 container_const_reference<basic_slice> (), it_ () {}
1335             BOOST_UBLAS_INLINE
1336             const_iterator (const basic_slice &s, const const_subiterator_type &it):
1337                 container_const_reference<basic_slice> (s), it_ (it) {}
1338
1339             // Arithmetic
1340             BOOST_UBLAS_INLINE
1341             const_iterator &operator ++ () {
1342                 ++it_;
1343                 return *this;
1344             }
1345             BOOST_UBLAS_INLINE
1346             const_iterator &operator -- () {
1347                 BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
1348                 --it_;
1349                 return *this;
1350             }
1351             BOOST_UBLAS_INLINE
1352             const_iterator &operator += (difference_type n) {
1353                 BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
1354                 it_ += n;
1355                 return *this;
1356             }
1357             BOOST_UBLAS_INLINE
1358             const_iterator &operator -= (difference_type n) {
1359                 BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
1360                 it_ -= n;
1361                 return *this;
1362             }
1363             BOOST_UBLAS_INLINE
1364             difference_type operator - (const const_iterator &it) const {
1365                 return it_ - it.it_;
1366             }
1367
1368             // Dereference
1369             BOOST_UBLAS_INLINE
1370             const_reference operator * () const {
1371                 BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
1372                 return (*this) ().start () + it_* (*this) ().stride ();
1373             }
1374
1375             BOOST_UBLAS_INLINE
1376             const_reference operator [] (difference_type n) const {
1377                 return *(*this + n);
1378             }
1379
1380             // Index
1381             BOOST_UBLAS_INLINE
1382             size_type index () const {
1383                 BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
1384                 return it_;
1385             }
1386
1387             // Assignment
1388             BOOST_UBLAS_INLINE
1389             const_iterator &operator = (const const_iterator &it) {
1390                 // Comeau recommends...
1391                 this->assign (&it ());
1392                 it_ = it.it_;
1393                 return *this;
1394             }
1395
1396             // Comparison
1397             BOOST_UBLAS_INLINE
1398             bool operator == (const const_iterator &it) const {
1399                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1400                 return it_ == it.it_;
1401             }
1402             BOOST_UBLAS_INLINE
1403             bool operator < (const const_iterator &it) const {
1404                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1405                 return it_ < it.it_;
1406             }
1407
1408         private:
1409             const_subiterator_type it_;
1410         };
1411 #endif
1412
1413         BOOST_UBLAS_INLINE
1414         const_iterator begin () const {
1415             return const_iterator (*this, 0);
1416         }
1417         BOOST_UBLAS_INLINE
1418         const_iterator cbegin () const {
1419             return begin ();
1420         }
1421         BOOST_UBLAS_INLINE
1422         const_iterator end () const {
1423             return const_iterator (*this, size_);
1424         }
1425         BOOST_UBLAS_INLINE
1426         const_iterator cend () const {
1427             return end ();
1428         }
1429
1430         // Reverse iterator
1431         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1432
1433         BOOST_UBLAS_INLINE
1434         const_reverse_iterator rbegin () const {
1435             return const_reverse_iterator (end ());
1436         }
1437         BOOST_UBLAS_INLINE
1438         const_reverse_iterator crbegin () const {
1439             return rbegin ();
1440         }
1441         BOOST_UBLAS_INLINE
1442         const_reverse_iterator rend () const {
1443             return const_reverse_iterator (begin ());
1444         }
1445         BOOST_UBLAS_INLINE
1446         const_reverse_iterator crend () const {
1447             return rend ();
1448         }
1449
1450         BOOST_UBLAS_INLINE
1451         basic_slice preprocess (size_type size) const {
1452             if (this != &all_)
1453                 return *this;
1454             return basic_slice (0, 1, size);
1455         }
1456         static
1457         BOOST_UBLAS_INLINE
1458         const basic_slice &all () {
1459             return all_;
1460         }
1461
1462     private:
1463         size_type start_;
1464         difference_type stride_;
1465         size_type size_;
1466         static const basic_slice all_;
1467     };
1468
1469     template <class Z, class D>
1470     const basic_slice<Z,D> basic_slice<Z,D>::all_  (0, 1, size_type (-1));
1471
1472
1473     // Indirect array class
1474     template<class A>
1475     class indirect_array {
1476         typedef indirect_array<A> self_type;
1477     public:
1478         typedef A array_type;
1479         typedef const A const_array_type;
1480         typedef typename A::size_type size_type;
1481         typedef typename A::difference_type difference_type;
1482         typedef typename A::value_type value_type;
1483         typedef typename A::const_reference const_reference;
1484         typedef typename A::reference reference;
1485         typedef typename A::const_pointer const_pointer;
1486         typedef typename A::pointer pointer;
1487
1488         // Construction and destruction
1489         BOOST_UBLAS_INLINE
1490         indirect_array ():
1491             size_ (), data_ () {}
1492         explicit BOOST_UBLAS_INLINE
1493         indirect_array (size_type size):
1494             size_ (size), data_ (size) {}
1495         BOOST_UBLAS_INLINE
1496         indirect_array (size_type size, const array_type &data):
1497             size_ (size), data_ (data) {}
1498         BOOST_UBLAS_INLINE
1499         indirect_array (pointer start, pointer stop):
1500             size_ (stop - start), data_ (stop - start) {
1501             std::copy (start, stop, data_.begin ());
1502         }
1503
1504         BOOST_UBLAS_INLINE
1505         size_type size () const {
1506             return size_;
1507         }
1508         BOOST_UBLAS_INLINE
1509         const_array_type data () const {
1510             return data_;
1511         }
1512         BOOST_UBLAS_INLINE
1513         array_type data () {
1514             return data_;
1515         }
1516
1517         // Random Access Container
1518         BOOST_UBLAS_INLINE
1519         size_type max_size () const {
1520             return size_;
1521         }
1522
1523         BOOST_UBLAS_INLINE
1524         bool empty () const {
1525             return data_.size () == 0;
1526         }
1527
1528         // Element access
1529         BOOST_UBLAS_INLINE
1530         const_reference operator () (size_type i) const {
1531             BOOST_UBLAS_CHECK (i < size_, bad_index ());
1532             return data_ [i];
1533         }
1534         BOOST_UBLAS_INLINE
1535         reference operator () (size_type i) {
1536             BOOST_UBLAS_CHECK (i < size_, bad_index ());
1537             return data_ [i];
1538         }
1539
1540         BOOST_UBLAS_INLINE
1541         const_reference operator [] (size_type i) const {
1542             return (*this) (i);
1543         }
1544         BOOST_UBLAS_INLINE
1545         reference operator [] (size_type i) {
1546             return (*this) (i);
1547         }
1548
1549         // Composition
1550         BOOST_UBLAS_INLINE
1551         indirect_array compose (const basic_range<size_type, difference_type> &r) const {
1552             BOOST_UBLAS_CHECK (r.start () + r.size () <= size_, bad_size ());
1553             array_type data (r.size ());
1554             for (size_type i = 0; i < r.size (); ++ i)
1555                 data [i] = data_ [r.start () + i];
1556             return indirect_array (r.size (), data);
1557         }
1558         BOOST_UBLAS_INLINE
1559         indirect_array compose (const basic_slice<size_type, difference_type> &s) const {
1560             BOOST_UBLAS_CHECK (s.start () + s.stride () * (s.size () - (s.size () > 0)) <= size (), bad_size ());
1561             array_type data (s.size ());
1562             for (size_type i = 0; i < s.size (); ++ i)
1563                 data [i] = data_ [s.start () + s.stride () * i];
1564             return indirect_array (s.size (), data);
1565         }
1566         BOOST_UBLAS_INLINE
1567         indirect_array compose (const indirect_array &ia) const {
1568             array_type data (ia.size_);
1569             for (size_type i = 0; i < ia.size_; ++ i) {
1570                 BOOST_UBLAS_CHECK (ia.data_ [i] <= size_, bad_size ());
1571                 data [i] = data_ [ia.data_ [i]];
1572             }
1573             return indirect_array (ia.size_, data);
1574         }
1575
1576         // Comparison
1577         template<class OA>
1578         BOOST_UBLAS_INLINE
1579         bool operator == (const indirect_array<OA> &ia) const {
1580             if (size_ != ia.size_)
1581                 return false;
1582             for (size_type i = 0; i < BOOST_UBLAS_SAME (size_, ia.size_); ++ i)
1583                 if (data_ [i] != ia.data_ [i])
1584                     return false;
1585             return true;
1586         }
1587         template<class OA>
1588         BOOST_UBLAS_INLINE
1589         bool operator != (const indirect_array<OA> &ia) const {
1590             return ! (*this == ia);
1591         }
1592
1593         // Iterator types
1594     private:
1595         // Use a index difference
1596         typedef difference_type const_subiterator_type;
1597
1598     public:
1599 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1600         typedef indexed_const_iterator<indirect_array, std::random_access_iterator_tag> const_iterator;
1601 #else
1602         class const_iterator:
1603             public container_const_reference<indirect_array>,
1604             public random_access_iterator_base<std::random_access_iterator_tag,
1605                                                const_iterator, value_type> {
1606         public:
1607             typedef typename indirect_array::value_type value_type;
1608             typedef typename indirect_array::difference_type difference_type;
1609             typedef typename indirect_array::const_reference reference;
1610             typedef typename indirect_array::const_pointer pointer;
1611
1612             // Construction and destruction
1613             BOOST_UBLAS_INLINE
1614             const_iterator ():
1615                 container_const_reference<indirect_array> (), it_ () {}
1616             BOOST_UBLAS_INLINE
1617             const_iterator (const indirect_array &ia, const const_subiterator_type &it):
1618                 container_const_reference<indirect_array> (ia), it_ (it) {}
1619
1620             // Arithmetic
1621             BOOST_UBLAS_INLINE
1622             const_iterator &operator ++ () {
1623                 ++ it_;
1624                 return *this;
1625             }
1626             BOOST_UBLAS_INLINE
1627             const_iterator &operator -- () {
1628                 -- it_;
1629                 return *this;
1630             }
1631             BOOST_UBLAS_INLINE
1632             const_iterator &operator += (difference_type n) {
1633                 it_ += n;
1634                 return *this;
1635             }
1636             BOOST_UBLAS_INLINE
1637             const_iterator &operator -= (difference_type n) {
1638                 it_ -= n;
1639                 return *this;
1640             }
1641             BOOST_UBLAS_INLINE
1642             difference_type operator - (const const_iterator &it) const {
1643                 return it_ - it.it_;
1644             }
1645
1646             // Dereference
1647             BOOST_UBLAS_INLINE
1648             const_reference operator * () const {
1649                 return (*this) () (it_);
1650             }
1651
1652             BOOST_UBLAS_INLINE
1653             const_reference operator [] (difference_type n) const {
1654                 return *(*this + n);
1655             }
1656
1657             // Index
1658             BOOST_UBLAS_INLINE
1659             size_type index () const {
1660                 return it_;
1661             }
1662
1663             // Assignment
1664             BOOST_UBLAS_INLINE
1665             const_iterator &operator = (const const_iterator &it) {
1666                 // Comeau recommends...
1667                 this->assign (&it ());
1668                 it_ = it.it_;
1669                 return *this;
1670             }
1671
1672             // Comparison
1673             BOOST_UBLAS_INLINE
1674             bool operator == (const const_iterator &it) const {
1675                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1676                 return it_ == it.it_;
1677             }
1678             BOOST_UBLAS_INLINE
1679             bool operator < (const const_iterator &it) const {
1680                 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1681                 return it_ < it.it_;
1682             }
1683
1684         private:
1685             const_subiterator_type it_;
1686         };
1687 #endif
1688
1689         BOOST_UBLAS_INLINE
1690         const_iterator begin () const {
1691             return const_iterator (*this, 0);
1692         }
1693         BOOST_UBLAS_INLINE
1694         const_iterator cbegin () const {
1695             return begin ();
1696         }
1697         BOOST_UBLAS_INLINE
1698         const_iterator end () const {
1699             return const_iterator (*this, size_);
1700         }
1701         BOOST_UBLAS_INLINE
1702         const_iterator cend () const {
1703             return end ();
1704         }
1705
1706         // Reverse iterator
1707         typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1708
1709         BOOST_UBLAS_INLINE
1710         const_reverse_iterator rbegin () const {
1711             return const_reverse_iterator (end ());
1712         }
1713         BOOST_UBLAS_INLINE
1714         const_reverse_iterator crbegin () const {
1715             return rbegin ();
1716         }
1717         BOOST_UBLAS_INLINE
1718         const_reverse_iterator rend () const {
1719             return const_reverse_iterator (begin ());
1720         }
1721         BOOST_UBLAS_INLINE
1722         const_reverse_iterator crend () const {
1723             return rend ();
1724         }
1725
1726         BOOST_UBLAS_INLINE
1727         indirect_array preprocess (size_type size) const {
1728             if (this != &all_)
1729                 return *this;
1730             indirect_array ia (size);
1731             for (size_type i = 0; i < size; ++ i)
1732                ia (i) = i;
1733             return ia;
1734         }
1735         static
1736         BOOST_UBLAS_INLINE
1737         const indirect_array &all () {
1738             return all_;
1739         }
1740
1741     private:
1742         size_type size_;
1743         array_type data_;
1744         static const indirect_array all_;
1745     };
1746
1747     template<class A>
1748     const indirect_array<A> indirect_array<A>::all_;
1749
1750
1751
1752     // Gunter Winkler contributed the classes index_pair, index_pair_array,
1753     // index_triple and index_triple_array to enable inplace sort of parallel arrays.
1754
1755     template <class V>
1756     class index_pair :
1757         public container_reference<V> {
1758
1759         typedef index_pair<V> self_type;
1760     public:
1761         typedef typename V::size_type size_type;
1762
1763         BOOST_UBLAS_INLINE
1764         index_pair(V& v, size_type i) :
1765             container_reference<V>(v), i_(i),
1766             v1_(v.data1_[i]), v2_(v.data2_[i]),
1767             dirty_(false), is_copy_(false) {}
1768          BOOST_UBLAS_INLINE
1769         index_pair(const self_type& rhs) :
1770             container_reference<V>(rhs()), i_(0),
1771             v1_(rhs.v1_), v2_(rhs.v2_),
1772             dirty_(false), is_copy_(true) {}
1773          BOOST_UBLAS_INLINE
1774         ~index_pair() {
1775             if (dirty_ && (!is_copy_) ) {
1776                 (*this)().data1_[i_] = v1_;
1777                 (*this)().data2_[i_] = v2_;
1778             }
1779         }
1780
1781         BOOST_UBLAS_INLINE
1782         self_type& operator=(const self_type& rhs) {
1783             v1_ = rhs.v1_;
1784             v2_ = rhs.v2_;
1785             dirty_ = true;
1786             return *this;
1787         }
1788
1789         BOOST_UBLAS_INLINE
1790         void swap(self_type& rhs) {
1791             self_type tmp(rhs);
1792             rhs = *this;
1793             *this = tmp;
1794         }
1795
1796         BOOST_UBLAS_INLINE
1797         friend void swap(self_type& lhs, self_type& rhs) {
1798             lhs.swap(rhs);
1799         }
1800
1801         friend void swap(self_type lhs, self_type rhs) { // For gcc 4.8 and c++11
1802             lhs.swap(rhs);
1803         }
1804
1805
1806         BOOST_UBLAS_INLINE
1807         bool equal(const self_type& rhs) const {
1808             return (v1_ == rhs.v1_);
1809         }
1810         BOOST_UBLAS_INLINE
1811         bool less(const self_type& rhs) const {
1812             return (v1_ < rhs.v1_);
1813         }
1814         BOOST_UBLAS_INLINE
1815         friend bool operator == (const self_type& lhs, const self_type& rhs) {
1816             return lhs.equal(rhs);
1817         }
1818         BOOST_UBLAS_INLINE
1819         friend bool operator != (const self_type& lhs, const self_type& rhs) {
1820             return !lhs.equal(rhs);
1821         }
1822         BOOST_UBLAS_INLINE
1823         friend bool operator < (const self_type& lhs, const self_type& rhs) {
1824             return lhs.less(rhs);
1825         }
1826         BOOST_UBLAS_INLINE
1827         friend bool operator >= (const self_type& lhs, const self_type& rhs) {
1828             return !lhs.less(rhs);
1829         }
1830         BOOST_UBLAS_INLINE
1831         friend bool operator > (const self_type& lhs, const self_type& rhs) {
1832             return rhs.less(lhs);
1833         }
1834         BOOST_UBLAS_INLINE
1835         friend bool operator <= (const self_type& lhs, const self_type& rhs) {
1836             return !rhs.less(lhs);
1837         }
1838
1839     private:
1840         size_type i_;
1841         typename V::value1_type v1_;
1842         typename V::value2_type v2_;
1843         bool dirty_;
1844         bool is_copy_;
1845      };
1846
1847     template <class V1, class V2>
1848     class index_pair_array:
1849         private boost::noncopyable {
1850
1851         typedef index_pair_array<V1, V2> self_type;
1852     public:
1853         typedef typename V1::value_type value1_type;
1854         typedef typename V2::value_type value2_type;
1855
1856         typedef typename V1::size_type size_type;
1857         typedef typename V1::difference_type difference_type;
1858         typedef index_pair<self_type> value_type;
1859         // There is nothing that can be referenced directly. Always return a copy of the index_pair
1860         typedef value_type reference;
1861         typedef const value_type const_reference;
1862
1863         BOOST_UBLAS_INLINE
1864         index_pair_array(size_type size, V1& data1, V2& data2) :
1865               size_(size),data1_(data1),data2_(data2) {}
1866
1867         BOOST_UBLAS_INLINE
1868         size_type size() const {
1869             return size_;
1870         }
1871
1872         BOOST_UBLAS_INLINE
1873         const_reference operator () (size_type i) const {
1874             return value_type((*this), i);
1875         }
1876         BOOST_UBLAS_INLINE
1877         reference operator () (size_type i) {
1878             return value_type((*this), i);
1879         }
1880
1881         typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
1882         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1883
1884         BOOST_UBLAS_INLINE
1885         iterator begin() {
1886             return iterator( (*this), 0);
1887         }
1888         BOOST_UBLAS_INLINE
1889         iterator end() {
1890             return iterator( (*this), size());
1891         }
1892
1893         BOOST_UBLAS_INLINE
1894         const_iterator begin() const {
1895             return const_iterator( (*this), 0);
1896         }
1897         BOOST_UBLAS_INLINE
1898         const_iterator cbegin () const {
1899             return begin ();
1900         }
1901         BOOST_UBLAS_INLINE
1902         const_iterator end() const {
1903             return const_iterator( (*this), size());
1904         }
1905         BOOST_UBLAS_INLINE
1906         const_iterator cend () const {
1907             return end ();
1908         }
1909
1910         // unnecessary function:
1911         BOOST_UBLAS_INLINE
1912         bool equal(size_type i1, size_type i2) const {
1913             return data1_[i1] == data1_[i2];
1914         }
1915         BOOST_UBLAS_INLINE
1916         bool less(size_type i1, size_type i2) const {
1917             return data1_[i1] < data1_[i2];
1918         }
1919
1920         // gives a large speedup
1921         BOOST_UBLAS_INLINE
1922         friend void iter_swap(const iterator& lhs, const iterator& rhs) {
1923             const size_type i1 = lhs.index();
1924             const size_type i2 = rhs.index();
1925             std::swap(lhs().data1_[i1], rhs().data1_[i2]);
1926             std::swap(lhs().data2_[i1], rhs().data2_[i2]);
1927         }
1928
1929     private:
1930         size_type size_;
1931         V1& data1_;
1932         V2& data2_;
1933
1934         // friend class value_type;
1935         friend class index_pair<self_type>;
1936     };
1937
1938     template <class M>
1939     class index_triple :
1940         public container_reference<M> {
1941
1942         typedef index_triple<M> self_type;
1943     public:
1944         typedef typename M::size_type size_type;
1945
1946         BOOST_UBLAS_INLINE
1947         index_triple(M& m, size_type i) :
1948             container_reference<M>(m), i_(i),
1949             v1_(m.data1_[i]), v2_(m.data2_[i]), v3_(m.data3_[i]),
1950             dirty_(false), is_copy_(false) {}
1951         BOOST_UBLAS_INLINE
1952         index_triple(const self_type& rhs) :
1953             container_reference<M>(rhs()), i_(0),
1954             v1_(rhs.v1_), v2_(rhs.v2_), v3_(rhs.v3_),
1955             dirty_(false), is_copy_(true) {}
1956         BOOST_UBLAS_INLINE
1957         ~index_triple() {
1958             if (dirty_ && (!is_copy_) ) {
1959                 (*this)().data1_[i_] = v1_;
1960                 (*this)().data2_[i_] = v2_;
1961                 (*this)().data3_[i_] = v3_;
1962             }
1963         }
1964
1965         BOOST_UBLAS_INLINE
1966         self_type& operator=(const self_type& rhs) {
1967             v1_ = rhs.v1_;
1968             v2_ = rhs.v2_;
1969             v3_ = rhs.v3_;
1970             dirty_ = true;
1971             return *this;
1972         }
1973
1974         BOOST_UBLAS_INLINE
1975         void swap(self_type& rhs) {
1976             self_type tmp(rhs);
1977             rhs = *this;
1978             *this = tmp;
1979         }
1980
1981         BOOST_UBLAS_INLINE
1982         friend void swap(self_type& lhs, self_type& rhs) {
1983             lhs.swap(rhs);
1984         }
1985
1986         friend void swap(self_type lhs, self_type rhs) { // For gcc 4.8 and c++11
1987             lhs.swap(rhs);
1988         }
1989
1990         BOOST_UBLAS_INLINE
1991         bool equal(const self_type& rhs) const {
1992             return ((v1_ == rhs.v1_) && (v2_ == rhs.v2_));
1993         }
1994         BOOST_UBLAS_INLINE
1995         bool less(const self_type& rhs) const {
1996             return ((v1_ < rhs.v1_) ||
1997                     (v1_ == rhs.v1_ && v2_ < rhs.v2_));
1998         }
1999         BOOST_UBLAS_INLINE
2000         friend bool operator == (const self_type& lhs, const self_type& rhs) {
2001             return lhs.equal(rhs);
2002         }
2003         BOOST_UBLAS_INLINE
2004         friend bool operator != (const self_type& lhs, const self_type& rhs) {
2005             return !lhs.equal(rhs);
2006         }
2007         BOOST_UBLAS_INLINE
2008         friend bool operator < (const self_type& lhs, const self_type& rhs) {
2009             return lhs.less(rhs);
2010         }
2011         BOOST_UBLAS_INLINE
2012         friend bool operator >= (const self_type& lhs, const self_type& rhs) {
2013             return !lhs.less(rhs);
2014         }
2015         BOOST_UBLAS_INLINE
2016         friend bool operator > (const self_type& lhs, const self_type& rhs) {
2017             return rhs.less(lhs);
2018         }
2019         BOOST_UBLAS_INLINE
2020         friend bool operator <= (const self_type& lhs, const self_type& rhs) {
2021             return !rhs.less(lhs);
2022         }
2023
2024     private:
2025         size_type i_;
2026         typename M::value1_type v1_;
2027         typename M::value2_type v2_;
2028         typename M::value3_type v3_;
2029         bool dirty_;
2030         bool is_copy_;
2031     };
2032
2033     template <class V1, class V2, class V3>
2034     class index_triple_array:
2035         private boost::noncopyable {
2036
2037         typedef index_triple_array<V1, V2, V3> self_type;
2038     public:
2039         typedef typename V1::value_type value1_type;
2040         typedef typename V2::value_type value2_type;
2041         typedef typename V3::value_type value3_type;
2042
2043         typedef typename V1::size_type size_type;
2044         typedef typename V1::difference_type difference_type;
2045         typedef index_triple<self_type> value_type;
2046         // There is nothing that can be referenced directly. Always return a copy of the index_triple
2047         typedef value_type reference;
2048         typedef const value_type const_reference;
2049
2050         BOOST_UBLAS_INLINE
2051         index_triple_array(size_type size, V1& data1, V2& data2, V3& data3) :
2052               size_(size),data1_(data1),data2_(data2),data3_(data3) {}
2053
2054         BOOST_UBLAS_INLINE
2055         size_type size() const {
2056             return size_;
2057         }
2058
2059         BOOST_UBLAS_INLINE
2060         const_reference operator () (size_type i) const {
2061             return value_type((*this), i);
2062         }
2063         BOOST_UBLAS_INLINE
2064         reference operator () (size_type i) {
2065             return value_type((*this), i);
2066         }
2067
2068         typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
2069         typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
2070
2071         BOOST_UBLAS_INLINE
2072         iterator begin() {
2073             return iterator( (*this), 0);
2074         }
2075         BOOST_UBLAS_INLINE
2076         iterator end() {
2077             return iterator( (*this), size());
2078         }
2079
2080         BOOST_UBLAS_INLINE
2081         const_iterator begin() const {
2082             return const_iterator( (*this), 0);
2083         }
2084         BOOST_UBLAS_INLINE
2085         const_iterator cbegin () const {
2086             return begin ();
2087         }
2088         BOOST_UBLAS_INLINE
2089         const_iterator end() const {
2090             return const_iterator( (*this), size());
2091         }
2092         BOOST_UBLAS_INLINE
2093         const_iterator cend () const {
2094             return end ();
2095         }
2096
2097         // unnecessary function:
2098         BOOST_UBLAS_INLINE
2099         bool equal(size_type i1, size_type i2) const {
2100             return ((data1_[i1] == data1_[i2]) && (data2_[i1] == data2_[i2]));
2101         }
2102         BOOST_UBLAS_INLINE
2103         bool less(size_type i1, size_type i2) const {
2104             return ((data1_[i1] < data1_[i2]) ||
2105                     (data1_[i1] == data1_[i2] && data2_[i1] < data2_[i2]));
2106         }
2107
2108         // gives a large speedup
2109         BOOST_UBLAS_INLINE
2110         friend void iter_swap(const iterator& lhs, const iterator& rhs) {
2111             const size_type i1 = lhs.index();
2112             const size_type i2 = rhs.index();
2113             std::swap(lhs().data1_[i1], rhs().data1_[i2]);
2114             std::swap(lhs().data2_[i1], rhs().data2_[i2]);
2115             std::swap(lhs().data3_[i1], rhs().data3_[i2]);
2116         }
2117
2118     private:
2119         size_type size_;
2120         V1& data1_;
2121         V2& data2_;
2122         V3& data3_;
2123
2124         // friend class value_type;
2125         friend class index_triple<self_type>;
2126     };
2127
2128 }}}
2129
2130 #endif