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