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