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