2 // Copyright (c) 2000-2002
3 // Joerg Walter, Mathias Koch
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)
9 // The authors gratefully acknowledge the support of
10 // GeNeSys mbH & Co. KG in producing this work.
13 #ifndef BOOST_UBLAS_STORAGE_H
14 #define BOOST_UBLAS_STORAGE_H
17 #ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
18 #include <boost/shared_array.hpp>
21 #include <boost/core/allocator_access.hpp>
22 #include <boost/serialization/array.hpp>
23 #include <boost/serialization/collection_size_type.hpp>
24 #include <boost/serialization/nvp.hpp>
26 #include <boost/numeric/ublas/exception.hpp>
27 #include <boost/numeric/ublas/traits.hpp>
28 #include <boost/numeric/ublas/detail/iterator.hpp>
31 namespace boost { namespace numeric { namespace ublas {
34 // Base class for Storage Arrays - see the Barton Nackman trick
37 private nonassignable {
41 // Unbounded array - with allocator
42 template<class T, class ALLOC>
43 class unbounded_array:
44 public storage_array<unbounded_array<T, ALLOC> > {
46 typedef unbounded_array<T, ALLOC> self_type;
48 typedef ALLOC allocator_type;
49 typedef typename boost::allocator_size_type<ALLOC>::type size_type;
50 typedef typename boost::allocator_difference_type<ALLOC>::type difference_type;
52 typedef const T &const_reference;
54 typedef const T *const_pointer;
56 typedef const_pointer const_iterator;
57 typedef pointer iterator;
59 // Construction and destruction
60 explicit BOOST_UBLAS_INLINE
61 unbounded_array (const ALLOC &a = ALLOC()):
62 alloc_ (a), size_ (0) {
65 explicit BOOST_UBLAS_INLINE
66 unbounded_array (size_type size, const ALLOC &a = ALLOC()):
67 alloc_(a), size_ (size) {
69 data_ = alloc_.allocate (size_);
70 //Disabled warning C4127 because the conditional expression is constant
73 #pragma warning(disable: 4127)
75 if (! detail::has_trivial_constructor<T>::value) {
79 for (pointer d = data_; d != data_ + size_; ++d)
80 boost::allocator_construct(alloc_, d);
86 // No value initialised, but still be default constructed
88 unbounded_array (size_type size, const value_type &init, const ALLOC &a = ALLOC()):
89 alloc_ (a), size_ (size) {
91 data_ = alloc_.allocate (size_);
92 std::uninitialized_fill (begin(), end(), init);
98 unbounded_array (const unbounded_array &c):
99 storage_array<unbounded_array<T, ALLOC> >(),
100 alloc_ (c.alloc_), size_ (c.size_) {
102 data_ = alloc_.allocate (size_);
103 std::uninitialized_copy (c.begin(), c.end(), begin());
108 #ifdef BOOST_UBLAS_CPP_GE_2011
110 unbounded_array (unbounded_array &&c) :
111 storage_array<unbounded_array<T, ALLOC> >(),
112 alloc_ (std::move(c.alloc_)), size_ (c.size_), data_(c.data_)
119 ~unbounded_array () {
121 //Disabled warning C4127 because the conditional expression is constant
123 #pragma warning(push)
124 #pragma warning(disable: 4127)
126 if (! detail::has_trivial_destructor<T>::value) {
130 // std::_Destroy (begin(), end(), alloc_);
131 const iterator i_end = end();
132 for (iterator i = begin (); i != i_end; ++i) {
133 iterator_destroy (i);
136 alloc_.deallocate (data_, size_);
143 void resize_internal (const size_type size, const value_type init, const bool preserve) {
145 pointer p_data = data_;
147 data_ = alloc_.allocate (size);
152 for (; di != data_ + size; ++di) {
153 boost::allocator_construct(alloc_, di, *si);
158 for (; si != p_data + size_; ++si) {
159 boost::allocator_construct(alloc_, di, *si);
162 for (; di != data_ + size; ++di) {
163 boost::allocator_construct(alloc_, di, init);
168 //Disabled warning C4127 because the conditional expression is constant
170 #pragma warning(push)
171 #pragma warning(disable: 4127)
173 if (! detail::has_trivial_constructor<T>::value) {
177 for (pointer di = data_; di != data_ + size; ++di)
178 boost::allocator_construct(alloc_, di);
184 //Disabled warning C4127 because the conditional expression is constant
186 #pragma warning(push)
187 #pragma warning(disable: 4127)
189 if (! detail::has_trivial_destructor<T>::value) {
193 for (pointer si = p_data; si != p_data + size_; ++si)
194 boost::allocator_destroy(alloc_, si);
196 alloc_.deallocate (p_data, size_);
206 void resize (size_type size) {
207 resize_internal (size, value_type (), false);
210 void resize (size_type size, value_type init) {
211 resize_internal (size, init, true);
214 // Random Access Container
216 size_type max_size () const {
217 return boost::allocator_max_size(alloc_);
221 bool empty () const {
226 size_type size () const {
232 const_reference operator [] (size_type i) const {
233 BOOST_UBLAS_CHECK (i < size_, bad_index ());
237 reference operator [] (size_type i) {
238 BOOST_UBLAS_CHECK (i < size_, bad_index ());
244 unbounded_array &operator = (const unbounded_array &a) {
247 std::copy (a.data_, a.data_ + a.size_, data_);
252 unbounded_array &assign_temporary (unbounded_array &a) {
259 void swap (unbounded_array &a) {
261 std::swap (size_, a.size_);
262 std::swap (data_, a.data_);
266 friend void swap (unbounded_array &a1, unbounded_array &a2) {
271 const_iterator begin () const {
275 const_iterator cbegin () const {
279 const_iterator end () const {
280 return data_ + size_;
283 const_iterator cend () const {
293 return data_ + size_;
297 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
298 typedef std::reverse_iterator<iterator> reverse_iterator;
301 const_reverse_iterator rbegin () const {
302 return const_reverse_iterator (end ());
305 const_reverse_iterator crbegin () const {
309 const_reverse_iterator rend () const {
310 return const_reverse_iterator (begin ());
313 const_reverse_iterator crend () const {
317 reverse_iterator rbegin () {
318 return reverse_iterator (end ());
321 reverse_iterator rend () {
322 return reverse_iterator (begin ());
326 allocator_type get_allocator () {
331 friend class boost::serialization::access;
334 template<class Archive>
335 void serialize(Archive & ar, const unsigned int /*version*/)
337 serialization::collection_size_type s(size_);
338 ar & serialization::make_nvp("size",s);
339 if ( Archive::is_loading::value ) {
342 ar & serialization::make_array(data_, s);
346 // Handle explict destroy on a (possibly indexed) iterator
348 static void iterator_destroy (iterator &i) {
350 (&(*i)) -> ~value_type ();
357 // Bounded array - with allocator for size_type and difference_type
358 template<class T, std::size_t N, class ALLOC>
360 public storage_array<bounded_array<T, N, ALLOC> > {
362 typedef bounded_array<T, N, ALLOC> self_type;
364 // No allocator_type as ALLOC is not used for allocation
365 typedef typename boost::allocator_size_type<ALLOC>::type size_type;
366 typedef typename boost::allocator_difference_type<ALLOC>::type difference_type;
367 typedef T value_type;
368 typedef const T &const_reference;
369 typedef T &reference;
370 typedef const T *const_pointer;
372 typedef const_pointer const_iterator;
373 typedef pointer iterator;
375 // Construction and destruction
378 size_ (0) /*, data_ ()*/ { // size 0 - use bounded_vector to default construct with size N
380 explicit BOOST_UBLAS_INLINE
381 bounded_array (size_type size):
382 size_ (size) /*, data_ ()*/ {
383 BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
384 // data_ (an array) elements are already default constructed
387 bounded_array (size_type size, const value_type &init):
388 size_ (size) /*, data_ ()*/ {
389 BOOST_UBLAS_CHECK (size_ <= N, bad_size ());
390 // ISSUE elements should be value constructed here, but we must fill instead as already default constructed
391 std::fill (begin(), end(), init) ;
394 bounded_array (const bounded_array &c):
396 // ISSUE elements should be copy constructed here, but we must copy instead as already default constructed
397 std::copy (c.begin(), c.end(), begin());
402 void resize (size_type size) {
403 BOOST_UBLAS_CHECK (size <= N, bad_size ());
407 void resize (size_type size, value_type init) {
408 BOOST_UBLAS_CHECK (size <= N, bad_size ());
410 std::fill (data_ + size_, data_ + size, init);
414 // Random Access Container
416 size_type max_size () const {
421 bool empty () const {
426 size_type size () const {
432 const_reference operator [] (size_type i) const {
433 BOOST_UBLAS_CHECK (i < size_, bad_index ());
437 reference operator [] (size_type i) {
438 BOOST_UBLAS_CHECK (i < size_, bad_index ());
444 bounded_array &operator = (const bounded_array &a) {
447 std::copy (a.data_, a.data_ + a.size_, data_);
452 bounded_array &assign_temporary (bounded_array &a) {
459 void swap (bounded_array &a) {
461 std::swap (size_, a.size_);
462 std::swap_ranges (data_, data_ + (std::max) (size_, a.size_), a.data_);
466 friend void swap (bounded_array &a1, bounded_array &a2) {
471 const_iterator begin () const {
475 const_iterator cbegin () const {
479 const_iterator end () const {
480 return data_ + size_;
483 const_iterator cend () const {
493 return data_ + size_;
497 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
498 typedef std::reverse_iterator<iterator> reverse_iterator;
501 const_reverse_iterator rbegin () const {
502 return const_reverse_iterator (end ());
505 const_reverse_iterator crbegin () const {
509 const_reverse_iterator rend () const {
510 return const_reverse_iterator (begin ());
513 const_reverse_iterator crend () const {
517 reverse_iterator rbegin () {
518 return reverse_iterator (end ());
521 reverse_iterator rend () {
522 return reverse_iterator (begin ());
527 friend class boost::serialization::access;
529 template<class Archive>
530 void serialize(Archive & ar, const unsigned int /*version*/)
532 serialization::collection_size_type s(size_);
533 ar & serialization::make_nvp("size", s);
534 if ( Archive::is_loading::value ) {
535 if (s > N) bad_size("too large size in bounded_array::load()\n").raise();
538 ar & serialization::make_array(data_, s);
543 // MSVC does not like arrays of size 0 in base classes. Hence, this conditionally changes the size to 1
545 BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [(N>0)?N:1];
547 BOOST_UBLAS_BOUNDED_ARRAY_ALIGN value_type data_ [N];
552 // Array adaptor with normal deep copy semantics of elements
555 public storage_array<array_adaptor<T> > {
557 typedef array_adaptor<T> self_type;
559 typedef std::size_t size_type;
560 typedef std::ptrdiff_t difference_type;
561 typedef T value_type;
562 typedef const T &const_reference;
563 typedef T &reference;
564 typedef const T *const_pointer;
567 // Construction and destruction
570 size_ (0), own_ (true), data_ (new value_type [0]) {
572 explicit BOOST_UBLAS_INLINE
573 array_adaptor (size_type size):
574 size_ (size), own_ (true), data_ (new value_type [size]) {
577 array_adaptor (size_type size, const value_type &init):
578 size_ (size), own_ (true), data_ (new value_type [size]) {
579 std::fill (data_, data_ + size_, init);
582 array_adaptor (size_type size, pointer data):
583 size_ (size), own_ (false), data_ (data) {}
586 BOOST_UBLAS_INLINE array_adaptor (T (&data)[N]):
587 size_ (N), own_ (false), data_ (data) {}
589 array_adaptor (const array_adaptor &a):
590 storage_array<self_type> (),
591 size_ (a.size_), own_ (true), data_ (new value_type [a.size_]) {
604 void resize_internal (size_type size, value_type init, bool preserve = true) {
606 pointer data = new value_type [size];
608 std::copy (data_, data_ + (std::min) (size, size_), data);
609 std::fill (data + (std::min) (size, size_), data + size, init);
619 void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
622 std::copy (data_, data_ + (std::min) (size, size_), data);
623 std::fill (data + (std::min) (size, size_), data + size, init);
631 std::fill (data + (std::min) (size, size_), data + size, init);
637 void resize (size_type size) {
638 resize_internal (size, value_type (), false);
641 void resize (size_type size, value_type init) {
642 resize_internal (size, init, true);
645 void resize (size_type size, pointer data) {
646 resize_internal (size, data, value_type (), false);
649 void resize (size_type size, pointer data, value_type init) {
650 resize_internal (size, data, init, true);
654 BOOST_UBLAS_INLINE void resize (T (&data)[N]) {
655 resize_internal (N, data, value_type (), false);
659 BOOST_UBLAS_INLINE void resize (T (&data)[N], value_type init) {
660 resize_internal (N, data, init, true);
664 size_type size () const {
670 const_reference operator [] (size_type i) const {
671 BOOST_UBLAS_CHECK (i < size_, bad_index ());
675 reference operator [] (size_type i) {
676 BOOST_UBLAS_CHECK (i < size_, bad_index ());
682 array_adaptor &operator = (const array_adaptor &a) {
685 std::copy (a.data_, a.data_ + a.size_, data_);
690 array_adaptor &assign_temporary (array_adaptor &a) {
700 void swap (array_adaptor &a) {
702 std::swap (size_, a.size_);
703 std::swap (own_, a.own_);
704 std::swap (data_, a.data_);
708 friend void swap (array_adaptor &a1, array_adaptor &a2) {
712 // Iterators simply are pointers.
714 typedef const_pointer const_iterator;
717 const_iterator begin () const {
721 const_iterator cbegin () const {
725 const_iterator end () const {
726 return data_ + size_;
729 const_iterator cend () const {
733 typedef pointer iterator;
741 return data_ + size_;
745 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
746 typedef std::reverse_iterator<iterator> reverse_iterator;
749 const_reverse_iterator rbegin () const {
750 return const_reverse_iterator (end ());
753 const_reverse_iterator crbegin () const {
757 const_reverse_iterator rend () const {
758 return const_reverse_iterator (begin ());
761 const_reverse_iterator crend () const {
765 reverse_iterator rbegin () {
766 return reverse_iterator (end ());
769 reverse_iterator rend () {
770 return reverse_iterator (begin ());
779 #ifdef BOOST_UBLAS_SHALLOW_ARRAY_ADAPTOR
780 // Array adaptor with shallow (reference) copy semantics of elements.
781 // shared_array is used to maintain reference counts.
782 // This class breaks the normal copy semantics for a storage container and is very dangerous!
784 class shallow_array_adaptor:
785 public storage_array<shallow_array_adaptor<T> > {
787 typedef shallow_array_adaptor<T> self_type;
791 typedef void result_type;
792 typedef TT *argument_type;
795 result_type operator () (argument_type /* x */) {}
799 typedef std::size_t size_type;
800 typedef std::ptrdiff_t difference_type;
801 typedef T value_type;
802 typedef const T &const_reference;
803 typedef T &reference;
804 typedef const T *const_pointer;
807 // Construction and destruction
809 shallow_array_adaptor ():
810 size_ (0), own_ (true), data_ (new value_type [0]) {
812 explicit BOOST_UBLAS_INLINE
813 shallow_array_adaptor (size_type size):
814 size_ (size), own_ (true), data_ (new value_type [size]) {
817 shallow_array_adaptor (size_type size, const value_type &init):
818 size_ (size), own_ (true), data_ (new value_type [size]) {
819 std::fill (data_.get (), data_.get () + size_, init);
822 shallow_array_adaptor (size_type size, pointer data):
823 size_ (size), own_ (false), data_ (data, leaker<value_type> ()) {}
826 shallow_array_adaptor (T (&data)[N]):
827 size_ (N), own_ (false), data_ (data, leaker<value_type> ()) {}
830 shallow_array_adaptor (const shallow_array_adaptor &a):
831 storage_array<self_type> (),
832 size_ (a.size_), own_ (a.own_), data_ (a.data_) {}
835 ~shallow_array_adaptor () {
841 void resize_internal (size_type size, value_type init, bool preserve = true) {
843 shared_array<value_type> data (new value_type [size]);
845 std::copy (data_.get (), data_.get () + (std::min) (size, size_), data.get ());
846 std::fill (data.get () + (std::min) (size, size_), data.get () + size, init);
854 void resize_internal (size_type size, pointer data, value_type init, bool preserve = true) {
856 std::copy (data_.get (), data_.get () + (std::min) (size, size_), data);
857 std::fill (data + (std::min) (size, size_), data + size, init);
861 data_.reset(data, leaker<value_type> ());
865 void resize (size_type size) {
866 resize_internal (size, value_type (), false);
869 void resize (size_type size, value_type init) {
870 resize_internal (size, init, true);
873 void resize (size_type size, pointer data) {
874 resize_internal (size, data, value_type (), false);
877 void resize (size_type size, pointer data, value_type init) {
878 resize_internal (size, data, init, true);
882 void resize (T (&data)[N]) {
883 resize_internal (N, data, value_type (), false);
887 void resize (T (&data)[N], value_type init) {
888 resize_internal (N, data, init, true);
892 size_type size () const {
898 const_reference operator [] (size_type i) const {
899 BOOST_UBLAS_CHECK (i < size_, bad_index ());
903 reference operator [] (size_type i) {
904 BOOST_UBLAS_CHECK (i < size_, bad_index ());
910 shallow_array_adaptor &operator = (const shallow_array_adaptor &a) {
913 std::copy (a.data_.get (), a.data_.get () + a.size_, data_.get ());
918 shallow_array_adaptor &assign_temporary (shallow_array_adaptor &a) {
928 void swap (shallow_array_adaptor &a) {
930 std::swap (size_, a.size_);
931 std::swap (own_, a.own_);
932 std::swap (data_, a.data_);
936 friend void swap (shallow_array_adaptor &a1, shallow_array_adaptor &a2) {
940 // Iterators simply are pointers.
942 typedef const_pointer const_iterator;
945 const_iterator begin () const {
949 const_iterator cbegin () const {
953 const_iterator end () const {
954 return data_.get () + size_;
957 const_iterator cend () const {
961 typedef pointer iterator;
969 return data_.get () + size_;
973 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
974 typedef std::reverse_iterator<iterator> reverse_iterator;
977 const_reverse_iterator rbegin () const {
978 return const_reverse_iterator (end ());
981 const_reverse_iterator crbegin () const {
985 const_reverse_iterator rend () const {
986 return const_reverse_iterator (begin ());
989 const_reverse_iterator crend () const {
993 reverse_iterator rbegin () {
994 return reverse_iterator (end ());
997 reverse_iterator rend () {
998 return reverse_iterator (begin ());
1004 shared_array<value_type> data_;
1011 template <class Z, class D>
1013 typedef basic_range<Z, D> self_type;
1015 typedef Z size_type;
1016 typedef D difference_type;
1017 typedef size_type value_type;
1018 typedef value_type const_reference;
1019 typedef const_reference reference;
1020 typedef const value_type *const_pointer;
1021 typedef value_type *pointer;
1023 // Construction and destruction
1026 start_ (0), size_ (0) {}
1028 basic_range (size_type start, size_type stop):
1029 start_ (start), size_ (stop - start) {
1030 BOOST_UBLAS_CHECK (start_ <= stop, bad_index ());
1034 size_type start () const {
1038 size_type size () const {
1042 // Random Access Container
1044 size_type max_size () const {
1049 bool empty () const {
1055 const_reference operator () (size_type i) const {
1056 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1062 basic_range compose (const basic_range &r) const {
1063 return basic_range (start_ + r.start_, start_ + r.start_ + r.size_);
1068 bool operator == (const basic_range &r) const {
1069 return start_ == r.start_ && size_ == r.size_;
1072 bool operator != (const basic_range &r) const {
1073 return ! (*this == r);
1079 typedef size_type const_subiterator_type;
1082 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1083 typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1085 class const_iterator:
1086 public container_const_reference<basic_range>,
1087 public random_access_iterator_base<std::random_access_iterator_tag,
1088 const_iterator, value_type> {
1090 typedef typename basic_range::value_type value_type;
1091 typedef typename basic_range::difference_type difference_type;
1092 typedef typename basic_range::const_reference reference;
1093 typedef typename basic_range::const_pointer pointer;
1095 // Construction and destruction
1098 container_const_reference<basic_range> (), it_ () {}
1100 const_iterator (const basic_range &r, const const_subiterator_type &it):
1101 container_const_reference<basic_range> (r), it_ (it) {}
1105 const_iterator &operator ++ () {
1110 const_iterator &operator -- () {
1111 BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
1116 const_iterator &operator += (difference_type n) {
1117 BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
1122 const_iterator &operator -= (difference_type n) {
1123 BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
1128 difference_type operator - (const const_iterator &it) const {
1129 return it_ - it.it_;
1134 const_reference operator * () const {
1135 BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
1136 BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
1141 const_reference operator [] (difference_type n) const {
1142 return *(*this + n);
1147 size_type index () const {
1148 BOOST_UBLAS_CHECK ((*this) ().start () <= it_, bad_index ());
1149 BOOST_UBLAS_CHECK (it_ < (*this) ().start () + (*this) ().size (), bad_index ());
1150 return it_ - (*this) ().start ();
1155 const_iterator &operator = (const const_iterator &it) {
1156 // Comeau recommends...
1157 this->assign (&it ());
1164 bool operator == (const const_iterator &it) const {
1165 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1166 return it_ == it.it_;
1169 bool operator < (const const_iterator &it) const {
1170 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1171 return it_ < it.it_;
1175 const_subiterator_type it_;
1180 const_iterator begin () const {
1181 return const_iterator (*this, start_);
1184 const_iterator cbegin () const {
1188 const_iterator end () const {
1189 return const_iterator (*this, start_ + size_);
1192 const_iterator cend () const {
1197 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1200 const_reverse_iterator rbegin () const {
1201 return const_reverse_iterator (end ());
1204 const_reverse_iterator crbegin () const {
1208 const_reverse_iterator rend () const {
1209 return const_reverse_iterator (begin ());
1212 const_reverse_iterator crend () const {
1217 basic_range preprocess (size_type size) const {
1220 return basic_range (0, size);
1224 const basic_range &all () {
1231 static const basic_range all_;
1234 template <class Z, class D>
1235 const basic_range<Z,D> basic_range<Z,D>::all_ (0, size_type (-1));
1239 template <class Z, class D>
1241 typedef basic_slice<Z, D> self_type;
1243 typedef Z size_type;
1244 typedef D difference_type;
1245 typedef size_type value_type;
1246 typedef value_type const_reference;
1247 typedef const_reference reference;
1248 typedef const value_type *const_pointer;
1249 typedef value_type *pointer;
1251 // Construction and destruction
1254 start_ (0), stride_ (0), size_ (0) {}
1256 basic_slice (size_type start, difference_type stride, size_type size):
1257 start_ (start), stride_ (stride), size_ (size) {}
1260 size_type start () const {
1264 difference_type stride () const {
1268 size_type size () const {
1272 // Random Access Container
1274 size_type max_size () const {
1279 bool empty () const {
1285 const_reference operator () (size_type i) const {
1286 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1287 BOOST_UBLAS_CHECK (stride_ >= 0 || start_ >= i * -stride_, bad_index ());
1288 return start_ + i * stride_;
1293 basic_slice compose (const basic_range<size_type, difference_type> &r) const {
1294 BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * r.start(), bad_index ());
1295 return basic_slice (start_ + stride_ * r.start (), stride_, r.size ());
1298 basic_slice compose (const basic_slice &s) const {
1299 BOOST_UBLAS_CHECK (stride_ >=0 || start_ >= -stride_ * s.start_, bad_index ());
1300 return basic_slice (start_ + stride_ * s.start_, stride_ * s.stride_, s.size_);
1305 bool operator == (const basic_slice &s) const {
1306 return start_ == s.start_ && stride_ == s.stride_ && size_ == s.size_;
1309 bool operator != (const basic_slice &s) const {
1310 return ! (*this == s);
1316 typedef size_type const_subiterator_type;
1319 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1320 typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1322 class const_iterator:
1323 public container_const_reference<basic_slice>,
1324 public random_access_iterator_base<std::random_access_iterator_tag,
1325 const_iterator, value_type> {
1327 typedef typename basic_slice::value_type value_type;
1328 typedef typename basic_slice::difference_type difference_type;
1329 typedef typename basic_slice::const_reference reference;
1330 typedef typename basic_slice::const_pointer pointer;
1332 // Construction and destruction
1335 container_const_reference<basic_slice> (), it_ () {}
1337 const_iterator (const basic_slice &s, const const_subiterator_type &it):
1338 container_const_reference<basic_slice> (s), it_ (it) {}
1342 const_iterator &operator ++ () {
1347 const_iterator &operator -- () {
1348 BOOST_UBLAS_CHECK (it_ > 0, bad_index ());
1353 const_iterator &operator += (difference_type n) {
1354 BOOST_UBLAS_CHECK (n >= 0 || it_ >= size_type(-n), bad_index ());
1359 const_iterator &operator -= (difference_type n) {
1360 BOOST_UBLAS_CHECK (n <= 0 || it_ >= size_type(n), bad_index ());
1365 difference_type operator - (const const_iterator &it) const {
1366 return it_ - it.it_;
1371 const_reference operator * () const {
1372 BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
1373 return (*this) ().start () + it_* (*this) ().stride ();
1377 const_reference operator [] (difference_type n) const {
1378 return *(*this + n);
1383 size_type index () const {
1384 BOOST_UBLAS_CHECK (it_ < (*this) ().size (), bad_index ());
1390 const_iterator &operator = (const const_iterator &it) {
1391 // Comeau recommends...
1392 this->assign (&it ());
1399 bool operator == (const const_iterator &it) const {
1400 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1401 return it_ == it.it_;
1404 bool operator < (const const_iterator &it) const {
1405 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1406 return it_ < it.it_;
1410 const_subiterator_type it_;
1415 const_iterator begin () const {
1416 return const_iterator (*this, 0);
1419 const_iterator cbegin () const {
1423 const_iterator end () const {
1424 return const_iterator (*this, size_);
1427 const_iterator cend () const {
1432 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1435 const_reverse_iterator rbegin () const {
1436 return const_reverse_iterator (end ());
1439 const_reverse_iterator crbegin () const {
1443 const_reverse_iterator rend () const {
1444 return const_reverse_iterator (begin ());
1447 const_reverse_iterator crend () const {
1452 basic_slice preprocess (size_type size) const {
1455 return basic_slice (0, 1, size);
1459 const basic_slice &all () {
1465 difference_type stride_;
1467 static const basic_slice all_;
1470 template <class Z, class D>
1471 const basic_slice<Z,D> basic_slice<Z,D>::all_ (0, 1, size_type (-1));
1474 // Indirect array class
1476 class indirect_array {
1477 typedef indirect_array<A> self_type;
1479 typedef A array_type;
1480 typedef const A const_array_type;
1481 typedef typename A::size_type size_type;
1482 typedef typename A::difference_type difference_type;
1483 typedef typename A::value_type value_type;
1484 typedef typename A::const_reference const_reference;
1485 typedef typename A::reference reference;
1486 typedef typename A::const_pointer const_pointer;
1487 typedef typename A::pointer pointer;
1489 // Construction and destruction
1492 size_ (), data_ () {}
1493 explicit BOOST_UBLAS_INLINE
1494 indirect_array (size_type size):
1495 size_ (size), data_ (size) {}
1497 indirect_array (size_type size, const array_type &data):
1498 size_ (size), data_ (data) {}
1500 indirect_array (pointer start, pointer stop):
1501 size_ (stop - start), data_ (stop - start) {
1502 std::copy (start, stop, data_.begin ());
1506 size_type size () const {
1510 const_array_type data () const {
1514 array_type data () {
1518 // Random Access Container
1520 size_type max_size () const {
1525 bool empty () const {
1526 return data_.size () == 0;
1531 const_reference operator () (size_type i) const {
1532 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1536 reference operator () (size_type i) {
1537 BOOST_UBLAS_CHECK (i < size_, bad_index ());
1542 const_reference operator [] (size_type i) const {
1546 reference operator [] (size_type i) {
1552 indirect_array compose (const basic_range<size_type, difference_type> &r) const {
1553 BOOST_UBLAS_CHECK (r.start () + r.size () <= size_, bad_size ());
1554 array_type data (r.size ());
1555 for (size_type i = 0; i < r.size (); ++ i)
1556 data [i] = data_ [r.start () + i];
1557 return indirect_array (r.size (), data);
1560 indirect_array compose (const basic_slice<size_type, difference_type> &s) const {
1561 BOOST_UBLAS_CHECK (s.start () + s.stride () * (s.size () - (s.size () > 0)) <= size (), bad_size ());
1562 array_type data (s.size ());
1563 for (size_type i = 0; i < s.size (); ++ i)
1564 data [i] = data_ [s.start () + s.stride () * i];
1565 return indirect_array (s.size (), data);
1568 indirect_array compose (const indirect_array &ia) const {
1569 array_type data (ia.size_);
1570 for (size_type i = 0; i < ia.size_; ++ i) {
1571 BOOST_UBLAS_CHECK (ia.data_ [i] <= size_, bad_size ());
1572 data [i] = data_ [ia.data_ [i]];
1574 return indirect_array (ia.size_, data);
1580 bool operator == (const indirect_array<OA> &ia) const {
1581 if (size_ != ia.size_)
1583 for (size_type i = 0; i < BOOST_UBLAS_SAME (size_, ia.size_); ++ i)
1584 if (data_ [i] != ia.data_ [i])
1590 bool operator != (const indirect_array<OA> &ia) const {
1591 return ! (*this == ia);
1596 // Use a index difference
1597 typedef difference_type const_subiterator_type;
1600 #ifdef BOOST_UBLAS_USE_INDEXED_ITERATOR
1601 typedef indexed_const_iterator<indirect_array, std::random_access_iterator_tag> const_iterator;
1603 class const_iterator:
1604 public container_const_reference<indirect_array>,
1605 public random_access_iterator_base<std::random_access_iterator_tag,
1606 const_iterator, value_type> {
1608 typedef typename indirect_array::value_type value_type;
1609 typedef typename indirect_array::difference_type difference_type;
1610 typedef typename indirect_array::const_reference reference;
1611 typedef typename indirect_array::const_pointer pointer;
1613 // Construction and destruction
1616 container_const_reference<indirect_array> (), it_ () {}
1618 const_iterator (const indirect_array &ia, const const_subiterator_type &it):
1619 container_const_reference<indirect_array> (ia), it_ (it) {}
1623 const_iterator &operator ++ () {
1628 const_iterator &operator -- () {
1633 const_iterator &operator += (difference_type n) {
1638 const_iterator &operator -= (difference_type n) {
1643 difference_type operator - (const const_iterator &it) const {
1644 return it_ - it.it_;
1649 const_reference operator * () const {
1650 return (*this) () (it_);
1654 const_reference operator [] (difference_type n) const {
1655 return *(*this + n);
1660 size_type index () const {
1666 const_iterator &operator = (const const_iterator &it) {
1667 // Comeau recommends...
1668 this->assign (&it ());
1675 bool operator == (const const_iterator &it) const {
1676 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1677 return it_ == it.it_;
1680 bool operator < (const const_iterator &it) const {
1681 BOOST_UBLAS_CHECK ((*this) () == it (), external_logic ());
1682 return it_ < it.it_;
1686 const_subiterator_type it_;
1691 const_iterator begin () const {
1692 return const_iterator (*this, 0);
1695 const_iterator cbegin () const {
1699 const_iterator end () const {
1700 return const_iterator (*this, size_);
1703 const_iterator cend () const {
1708 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1711 const_reverse_iterator rbegin () const {
1712 return const_reverse_iterator (end ());
1715 const_reverse_iterator crbegin () const {
1719 const_reverse_iterator rend () const {
1720 return const_reverse_iterator (begin ());
1723 const_reverse_iterator crend () const {
1728 indirect_array preprocess (size_type size) const {
1731 indirect_array ia (size);
1732 for (size_type i = 0; i < size; ++ i)
1738 const indirect_array &all () {
1745 static const indirect_array all_;
1749 const indirect_array<A> indirect_array<A>::all_;
1753 // Gunter Winkler contributed the classes index_pair, index_pair_array,
1754 // index_triple and index_triple_array to enable inplace sort of parallel arrays.
1758 public container_reference<V> {
1760 typedef index_pair<V> self_type;
1762 typedef typename V::size_type size_type;
1765 index_pair(V& v, size_type i) :
1766 container_reference<V>(v), i_(i),
1767 v1_(v.data1_[i]), v2_(v.data2_[i]),
1768 dirty_(false), is_copy_(false) {}
1770 index_pair(const self_type& rhs) :
1771 container_reference<V>(rhs()), i_(0),
1772 v1_(rhs.v1_), v2_(rhs.v2_),
1773 dirty_(false), is_copy_(true) {}
1776 if (dirty_ && (!is_copy_) ) {
1777 (*this)().data1_[i_] = v1_;
1778 (*this)().data2_[i_] = v2_;
1783 self_type& operator=(const self_type& rhs) {
1791 void swap(self_type& rhs) {
1798 friend void swap(self_type& lhs, self_type& rhs) {
1802 friend void swap(self_type lhs, self_type rhs) { // For gcc 4.8 and c++11
1808 bool equal(const self_type& rhs) const {
1809 return (v1_ == rhs.v1_);
1812 bool less(const self_type& rhs) const {
1813 return (v1_ < rhs.v1_);
1816 friend bool operator == (const self_type& lhs, const self_type& rhs) {
1817 return lhs.equal(rhs);
1820 friend bool operator != (const self_type& lhs, const self_type& rhs) {
1821 return !lhs.equal(rhs);
1824 friend bool operator < (const self_type& lhs, const self_type& rhs) {
1825 return lhs.less(rhs);
1828 friend bool operator >= (const self_type& lhs, const self_type& rhs) {
1829 return !lhs.less(rhs);
1832 friend bool operator > (const self_type& lhs, const self_type& rhs) {
1833 return rhs.less(lhs);
1836 friend bool operator <= (const self_type& lhs, const self_type& rhs) {
1837 return !rhs.less(lhs);
1842 typename V::value1_type v1_;
1843 typename V::value2_type v2_;
1848 template <class V1, class V2>
1849 class index_pair_array:
1850 private boost::noncopyable {
1852 typedef index_pair_array<V1, V2> self_type;
1854 typedef typename V1::value_type value1_type;
1855 typedef typename V2::value_type value2_type;
1857 typedef typename V1::size_type size_type;
1858 typedef typename V1::difference_type difference_type;
1859 typedef index_pair<self_type> value_type;
1860 // There is nothing that can be referenced directly. Always return a copy of the index_pair
1861 typedef value_type reference;
1862 typedef const value_type const_reference;
1865 index_pair_array(size_type size, V1& data1, V2& data2) :
1866 size_(size),data1_(data1),data2_(data2) {}
1869 size_type size() const {
1874 const_reference operator () (size_type i) const {
1875 return value_type((*this), i);
1878 reference operator () (size_type i) {
1879 return value_type((*this), i);
1882 typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
1883 typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
1887 return iterator( (*this), 0);
1891 return iterator( (*this), size());
1895 const_iterator begin() const {
1896 return const_iterator( (*this), 0);
1899 const_iterator cbegin () const {
1903 const_iterator end() const {
1904 return const_iterator( (*this), size());
1907 const_iterator cend () const {
1911 // unnecessary function:
1913 bool equal(size_type i1, size_type i2) const {
1914 return data1_[i1] == data1_[i2];
1917 bool less(size_type i1, size_type i2) const {
1918 return data1_[i1] < data1_[i2];
1921 // gives a large speedup
1923 friend void iter_swap(const iterator& lhs, const iterator& rhs) {
1924 const size_type i1 = lhs.index();
1925 const size_type i2 = rhs.index();
1926 std::swap(lhs().data1_[i1], rhs().data1_[i2]);
1927 std::swap(lhs().data2_[i1], rhs().data2_[i2]);
1935 // friend class value_type;
1936 friend class index_pair<self_type>;
1940 class index_triple :
1941 public container_reference<M> {
1943 typedef index_triple<M> self_type;
1945 typedef typename M::size_type size_type;
1948 index_triple(M& m, size_type i) :
1949 container_reference<M>(m), i_(i),
1950 v1_(m.data1_[i]), v2_(m.data2_[i]), v3_(m.data3_[i]),
1951 dirty_(false), is_copy_(false) {}
1953 index_triple(const self_type& rhs) :
1954 container_reference<M>(rhs()), i_(0),
1955 v1_(rhs.v1_), v2_(rhs.v2_), v3_(rhs.v3_),
1956 dirty_(false), is_copy_(true) {}
1959 if (dirty_ && (!is_copy_) ) {
1960 (*this)().data1_[i_] = v1_;
1961 (*this)().data2_[i_] = v2_;
1962 (*this)().data3_[i_] = v3_;
1967 self_type& operator=(const self_type& rhs) {
1976 void swap(self_type& rhs) {
1983 friend void swap(self_type& lhs, self_type& rhs) {
1987 friend void swap(self_type lhs, self_type rhs) { // For gcc 4.8 and c++11
1992 bool equal(const self_type& rhs) const {
1993 return ((v1_ == rhs.v1_) && (v2_ == rhs.v2_));
1996 bool less(const self_type& rhs) const {
1997 return ((v1_ < rhs.v1_) ||
1998 (v1_ == rhs.v1_ && v2_ < rhs.v2_));
2001 friend bool operator == (const self_type& lhs, const self_type& rhs) {
2002 return lhs.equal(rhs);
2005 friend bool operator != (const self_type& lhs, const self_type& rhs) {
2006 return !lhs.equal(rhs);
2009 friend bool operator < (const self_type& lhs, const self_type& rhs) {
2010 return lhs.less(rhs);
2013 friend bool operator >= (const self_type& lhs, const self_type& rhs) {
2014 return !lhs.less(rhs);
2017 friend bool operator > (const self_type& lhs, const self_type& rhs) {
2018 return rhs.less(lhs);
2021 friend bool operator <= (const self_type& lhs, const self_type& rhs) {
2022 return !rhs.less(lhs);
2027 typename M::value1_type v1_;
2028 typename M::value2_type v2_;
2029 typename M::value3_type v3_;
2034 template <class V1, class V2, class V3>
2035 class index_triple_array:
2036 private boost::noncopyable {
2038 typedef index_triple_array<V1, V2, V3> self_type;
2040 typedef typename V1::value_type value1_type;
2041 typedef typename V2::value_type value2_type;
2042 typedef typename V3::value_type value3_type;
2044 typedef typename V1::size_type size_type;
2045 typedef typename V1::difference_type difference_type;
2046 typedef index_triple<self_type> value_type;
2047 // There is nothing that can be referenced directly. Always return a copy of the index_triple
2048 typedef value_type reference;
2049 typedef const value_type const_reference;
2052 index_triple_array(size_type size, V1& data1, V2& data2, V3& data3) :
2053 size_(size),data1_(data1),data2_(data2),data3_(data3) {}
2056 size_type size() const {
2061 const_reference operator () (size_type i) const {
2062 return value_type((*this), i);
2065 reference operator () (size_type i) {
2066 return value_type((*this), i);
2069 typedef indexed_iterator<self_type, std::random_access_iterator_tag> iterator;
2070 typedef indexed_const_iterator<self_type, std::random_access_iterator_tag> const_iterator;
2074 return iterator( (*this), 0);
2078 return iterator( (*this), size());
2082 const_iterator begin() const {
2083 return const_iterator( (*this), 0);
2086 const_iterator cbegin () const {
2090 const_iterator end() const {
2091 return const_iterator( (*this), size());
2094 const_iterator cend () const {
2098 // unnecessary function:
2100 bool equal(size_type i1, size_type i2) const {
2101 return ((data1_[i1] == data1_[i2]) && (data2_[i1] == data2_[i2]));
2104 bool less(size_type i1, size_type i2) const {
2105 return ((data1_[i1] < data1_[i2]) ||
2106 (data1_[i1] == data1_[i2] && data2_[i1] < data2_[i2]));
2109 // gives a large speedup
2111 friend void iter_swap(const iterator& lhs, const iterator& rhs) {
2112 const size_type i1 = lhs.index();
2113 const size_type i2 = rhs.index();
2114 std::swap(lhs().data1_[i1], rhs().data1_[i2]);
2115 std::swap(lhs().data2_[i1], rhs().data2_[i2]);
2116 std::swap(lhs().data3_[i1], rhs().data3_[i2]);
2125 // friend class value_type;
2126 friend class index_triple<self_type>;