Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_34_1/boost/numeric/ublas/vector_sparse.hpp @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago
updated boost from 1_33_1 to 1_34_1
File size: 72.0 KB

Line
1	//
2	// Copyright (c) 2000-2002
3	// Joerg Walter, Mathias Koch
4	//
5	// Permission to use, copy, modify, distribute and sell this software
6	// and its documentation for any purpose is hereby granted without fee,
7	// provided that the above copyright notice appear in all copies and
8	// that both that copyright notice and this permission notice appear
9	// in supporting documentation. The authors make no representations
10	// about the suitability of this software for any purpose.
11	// It is provided "as is" without express or implied warranty.
12	//
13	// The authors gratefully acknowledge the support of
14	// GeNeSys mbH & Co. KG in producing this work.
15	//
16
17	#ifndef _BOOST_UBLAS_VECTOR_SPARSE_
18	#define _BOOST_UBLAS_VECTOR_SPARSE_
19
20	#include <boost/numeric/ublas/storage_sparse.hpp>
21	#include <boost/numeric/ublas/vector_expression.hpp>
22	#include <boost/numeric/ublas/detail/vector_assign.hpp>
23	#if BOOST_UBLAS_TYPE_CHECK
24	#include <boost/numeric/ublas/vector.hpp>
25	#endif
26
27	// Iterators based on ideas of Jeremy Siek
28
29	namespace boost { namespace numeric { namespace ublas {
30
31	#ifdef BOOST_UBLAS_STRICT_VECTOR_SPARSE
32
33	template<class V>
34	class sparse_vector_element:
35	public container_reference<V> {
36	public:
37	typedef V vector_type;
38	typedef typename V::size_type size_type;
39	typedef typename V::value_type value_type;
40	typedef const value_type &const_reference;
41	typedef value_type *pointer;
42
43	private:
44	// Proxied element operations
45	void get_d () const {
46	pointer p = (*this) ().find_element (i_);
47	if (p)
48	d_ = *p;
49	else
50	d_ = value_type/zero/();
51	}
52
53	void set (const value_type &s) const {
54	pointer p = (*this) ().find_element (i_);
55	if (!p)
56	(*this) ().insert_element (i_, s);
57	else
58	*p = s;
59	}
60
61	public:
62	// Construction and destruction
63	sparse_vector_element (vector_type &v, size_type i):
64	container_reference<vector_type> (v), i_ (i) {
65	}
66	BOOST_UBLAS_INLINE
67	sparse_vector_element (const sparse_vector_element &p):
68	container_reference<vector_type> (p), i_ (p.i_) {}
69	BOOST_UBLAS_INLINE
70	~sparse_vector_element () {
71	}
72
73	// Assignment
74	BOOST_UBLAS_INLINE
75	sparse_vector_element &operator = (const sparse_vector_element &p) {
76	// Overide the implict copy assignment
77	p.get_d ();
78	set (p.d_);
79	return *this;
80	}
81	template<class D>
82	BOOST_UBLAS_INLINE
83	sparse_vector_element &operator = (const D &d) {
84	set (d);
85	return *this;
86	}
87	template<class D>
88	BOOST_UBLAS_INLINE
89	sparse_vector_element &operator += (const D &d) {
90	get_d ();
91	d_ += d;
92	set (d_);
93	return *this;
94	}
95	template<class D>
96	BOOST_UBLAS_INLINE
97	sparse_vector_element &operator -= (const D &d) {
98	get_d ();
99	d_ -= d;
100	set (d_);
101	return *this;
102	}
103	template<class D>
104	BOOST_UBLAS_INLINE
105	sparse_vector_element &operator *= (const D &d) {
106	get_d ();
107	d_ *= d;
108	set (d_);
109	return *this;
110	}
111	template<class D>
112	BOOST_UBLAS_INLINE
113	sparse_vector_element &operator /= (const D &d) {
114	get_d ();
115	d_ /= d;
116	set (d_);
117	return *this;
118	}
119
120	// Comparison
121	template<class D>
122	BOOST_UBLAS_INLINE
123	bool operator == (const D &d) const {
124	get_d ();
125	return d_ == d;
126	}
127	template<class D>
128	BOOST_UBLAS_INLINE
129	bool operator != (const D &d) const {
130	get_d ();
131	return d_ != d;
132	}
133
134	// Conversion - weak link in proxy as d_ is not a perfect alias for the element
135	BOOST_UBLAS_INLINE
136	operator const_reference () const {
137	get_d ();
138	return d_;
139	}
140
141	// Conversion to reference - may be invalidated
142	BOOST_UBLAS_INLINE
143	value_type& ref () const {
144	const pointer p = (*this) ().find_element (i_);
145	if (!p)
146	return (this) ().insert_element (i_, value_type/zero*/());
147	else
148	return *p;
149	}
150
151	private:
152	size_type i_;
153	mutable value_type d_;
154	};
155
156	/*
157	* Generalise explicit reference access
158	*/
159	namespace detail {
160	template <class R>
161	struct element_reference {
162	typedef R& reference;
163	static reference get_reference (reference r)
164	{
165	return r;
166	}
167	};
168	template <class V>
169	struct element_reference<sparse_vector_element<V> > {
170	typedef typename V::value_type& reference;
171	static reference get_reference (const sparse_vector_element<V>& sve)
172	{
173	return sve.ref ();
174	}
175	};
176	}
177	template <class VER>
178	typename detail::element_reference<VER>::reference ref (VER& ver) {
179	return detail::element_reference<VER>::get_reference (ver);
180	}
181	template <class VER>
182	typename detail::element_reference<VER>::reference ref (const VER& ver) {
183	return detail::element_reference<VER>::get_reference (ver);
184	}
185
186
187	template<class V>
188	struct type_traits<sparse_vector_element<V> > {
189	typedef typename V::value_type element_type;
190	typedef type_traits<sparse_vector_element<V> > self_type;
191	typedef typename type_traits<element_type>::value_type value_type;
192	typedef typename type_traits<element_type>::const_reference const_reference;
193	typedef sparse_vector_element<V> reference;
194	typedef typename type_traits<element_type>::real_type real_type;
195	typedef typename type_traits<element_type>::precision_type precision_type;
196
197	static const unsigned plus_complexity = type_traits<element_type>::plus_complexity;
198	static const unsigned multiplies_complexity = type_traits<element_type>::multiplies_complexity;
199
200	static
201	BOOST_UBLAS_INLINE
202	real_type real (const_reference t) {
203	return type_traits<element_type>::real (t);
204	}
205	static
206	BOOST_UBLAS_INLINE
207	real_type imag (const_reference t) {
208	return type_traits<element_type>::imag (t);
209	}
210	static
211	BOOST_UBLAS_INLINE
212	value_type conj (const_reference t) {
213	return type_traits<element_type>::conj (t);
214	}
215
216	static
217	BOOST_UBLAS_INLINE
218	real_type type_abs (const_reference t) {
219	return type_traits<element_type>::type_abs (t);
220	}
221	static
222	BOOST_UBLAS_INLINE
223	value_type type_sqrt (const_reference t) {
224	return type_traits<element_type>::type_sqrt (t);
225	}
226
227	static
228	BOOST_UBLAS_INLINE
229	real_type norm_1 (const_reference t) {
230	return type_traits<element_type>::norm_1 (t);
231	}
232	static
233	BOOST_UBLAS_INLINE
234	real_type norm_2 (const_reference t) {
235	return type_traits<element_type>::norm_2 (t);
236	}
237	static
238	BOOST_UBLAS_INLINE
239	real_type norm_inf (const_reference t) {
240	return type_traits<element_type>::norm_inf (t);
241	}
242
243	static
244	BOOST_UBLAS_INLINE
245	bool equals (const_reference t1, const_reference t2) {
246	return type_traits<element_type>::equals (t1, t2);
247	}
248	};
249
250	template<class V1, class T2>
251	struct promote_traits<sparse_vector_element<V1>, T2> {
252	typedef typename promote_traits<typename sparse_vector_element<V1>::value_type, T2>::promote_type promote_type;
253	};
254	template<class T1, class V2>
255	struct promote_traits<T1, sparse_vector_element<V2> > {
256	typedef typename promote_traits<T1, typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
257	};
258	template<class V1, class V2>
259	struct promote_traits<sparse_vector_element<V1>, sparse_vector_element<V2> > {
260	typedef typename promote_traits<typename sparse_vector_element<V1>::value_type,
261	typename sparse_vector_element<V2>::value_type>::promote_type promote_type;
262	};
263
264	#endif
265
266
267	// Index map based sparse vector class
268	template<class T, class A>
269	class mapped_vector:
270	public vector_container<mapped_vector<T, A> > {
271
272	typedef T &true_reference;
273	typedef T *pointer;
274	typedef const T *const_pointer;
275	typedef mapped_vector<T, A> self_type;
276	public:
277	#ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
278	using vector_container<self_type>::operator ();
279	#endif
280	typedef typename A::size_type size_type;
281	typedef typename A::difference_type difference_type;
282	typedef T value_type;
283	typedef A array_type;
284	typedef const value_type &const_reference;
285	#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
286	typedef typename detail::map_traits<A,T>::reference reference;
287	#else
288	typedef sparse_vector_element<self_type> reference;
289	#endif
290	typedef const vector_reference<const self_type> const_closure_type;
291	typedef vector_reference<self_type> closure_type;
292	typedef self_type vector_temporary_type;
293	typedef sparse_tag storage_category;
294
295	// Construction and destruction
296	BOOST_UBLAS_INLINE
297	mapped_vector ():
298	vector_container<self_type> (),
299	size_ (0), data_ () {}
300	BOOST_UBLAS_INLINE
301	mapped_vector (size_type size, size_type non_zeros = 0):
302	vector_container<self_type> (),
303	size_ (size), data_ () {
304	detail::map_reserve (data(), restrict_capacity (non_zeros));
305	}
306	BOOST_UBLAS_INLINE
307	mapped_vector (const mapped_vector &v):
308	vector_container<self_type> (),
309	size_ (v.size_), data_ (v.data_) {}
310	template<class AE>
311	BOOST_UBLAS_INLINE
312	mapped_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
313	vector_container<self_type> (),
314	size_ (ae ().size ()), data_ () {
315	detail::map_reserve (data(), restrict_capacity (non_zeros));
316	vector_assign<scalar_assign> (*this, ae);
317	}
318
319	// Accessors
320	BOOST_UBLAS_INLINE
321	size_type size () const {
322	return size_;
323	}
324	BOOST_UBLAS_INLINE
325	size_type nnz_capacity () const {
326	return detail::map_capacity (data ());
327	}
328	BOOST_UBLAS_INLINE
329	size_type nnz () const {
330	return data (). size ();
331	}
332
333	// Storage accessors
334	BOOST_UBLAS_INLINE
335	const array_type &data () const {
336	return data_;
337	}
338	BOOST_UBLAS_INLINE
339	array_type &data () {
340	return data_;
341	}
342
343	// Resizing
344	private:
345	BOOST_UBLAS_INLINE
346	size_type restrict_capacity (size_type non_zeros) const {
347	non_zeros = (std::min) (non_zeros, size_);
348	return non_zeros;
349	}
350	public:
351	BOOST_UBLAS_INLINE
352	void resize (size_type size, bool preserve = true) {
353	size_ = size;
354	if (preserve) {
355	data ().erase (data ().lower_bound(size_), data ().end());
356	}
357	else {
358	data ().clear ();
359	}
360	}
361
362	// Reserving
363	BOOST_UBLAS_INLINE
364	void reserve (size_type non_zeros = 0, bool preserve = true) {
365	detail::map_reserve (data (), restrict_capacity (non_zeros));
366	}
367
368	// Element support
369	BOOST_UBLAS_INLINE
370	pointer find_element (size_type i) {
371	return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
372	}
373	BOOST_UBLAS_INLINE
374	const_pointer find_element (size_type i) const {
375	const_subiterator_type it (data ().find (i));
376	if (it == data ().end ())
377	return 0;
378	BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ()); // broken map
379	return &(*it).second;
380	}
381
382	// Element access
383	BOOST_UBLAS_INLINE
384	const_reference operator () (size_type i) const {
385	BOOST_UBLAS_CHECK (i < size_, bad_index ());
386	const_subiterator_type it (data ().find (i));
387	if (it == data ().end ())
388	return zero_;
389	BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ()); // broken map
390	return (*it).second;
391	}
392	BOOST_UBLAS_INLINE
393	true_reference ref (size_type i) {
394	BOOST_UBLAS_CHECK (i < size_, bad_index ());
395	std::pair<subiterator_type, bool> ii (data ().insert (typename array_type::value_type (i, value_type/zero/())));
396	BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ()); // broken map
397	return (ii.first)->second;
398	}
399	BOOST_UBLAS_INLINE
400	reference operator () (size_type i) {
401	#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
402	return ref (i);
403	#else
404	BOOST_UBLAS_CHECK (i < size_, bad_index ());
405	return reference (*this, i);
406	#endif
407	}
408
409	BOOST_UBLAS_INLINE
410	const_reference operator [] (size_type i) const {
411	return (*this) (i);
412	}
413	BOOST_UBLAS_INLINE
414	reference operator [] (size_type i) {
415	return (*this) (i);
416	}
417
418	// Element assignment
419	BOOST_UBLAS_INLINE
420	true_reference insert_element (size_type i, const_reference t) {
421	std::pair<subiterator_type, bool> ii = data ().insert (typename array_type::value_type (i, t));
422	BOOST_UBLAS_CHECK (ii.second, bad_index ()); // duplicate element
423	BOOST_UBLAS_CHECK ((ii.first)->first == i, internal_logic ()); // broken map
424	if (!ii.second) // existing element
425	(ii.first)->second = t;
426	return (ii.first)->second;
427	}
428	BOOST_UBLAS_INLINE
429	void erase_element (size_type i) {
430	subiterator_type it = data ().find (i);
431	if (it == data ().end ())
432	return;
433	data ().erase (it);
434	}
435
436	// Zeroing
437	BOOST_UBLAS_INLINE
438	void clear () {
439	data ().clear ();
440	}
441
442	// Assignment
443	BOOST_UBLAS_INLINE
444	mapped_vector &operator = (const mapped_vector &v) {
445	if (this != &v) {
446	size_ = v.size_;
447	data () = v.data ();
448	}
449	return *this;
450	}
451	template<class C> // Container assignment without temporary
452	BOOST_UBLAS_INLINE
453	mapped_vector &operator = (const vector_container<C> &v) {
454	resize (v ().size (), false);
455	assign (v);
456	return *this;
457	}
458	BOOST_UBLAS_INLINE
459	mapped_vector &assign_temporary (mapped_vector &v) {
460	swap (v);
461	return *this;
462	}
463	template<class AE>
464	BOOST_UBLAS_INLINE
465	mapped_vector &operator = (const vector_expression<AE> &ae) {
466	self_type temporary (ae, detail::map_capacity (data()));
467	return assign_temporary (temporary);
468	}
469	template<class AE>
470	BOOST_UBLAS_INLINE
471	mapped_vector &assign (const vector_expression<AE> &ae) {
472	vector_assign<scalar_assign> (*this, ae);
473	return *this;
474	}
475
476	// Computed assignment
477	template<class AE>
478	BOOST_UBLAS_INLINE
479	mapped_vector &operator += (const vector_expression<AE> &ae) {
480	self_type temporary (*this + ae, detail::map_capacity (data()));
481	return assign_temporary (temporary);
482	}
483	template<class C> // Container assignment without temporary
484	BOOST_UBLAS_INLINE
485	mapped_vector &operator += (const vector_container<C> &v) {
486	plus_assign (v);
487	return *this;
488	}
489	template<class AE>
490	BOOST_UBLAS_INLINE
491	mapped_vector &plus_assign (const vector_expression<AE> &ae) {
492	vector_assign<scalar_plus_assign> (*this, ae);
493	return *this;
494	}
495	template<class AE>
496	BOOST_UBLAS_INLINE
497	mapped_vector &operator -= (const vector_expression<AE> &ae) {
498	self_type temporary (*this - ae, detail::map_capacity (data()));
499	return assign_temporary (temporary);
500	}
501	template<class C> // Container assignment without temporary
502	BOOST_UBLAS_INLINE
503	mapped_vector &operator -= (const vector_container<C> &v) {
504	minus_assign (v);
505	return *this;
506	}
507	template<class AE>
508	BOOST_UBLAS_INLINE
509	mapped_vector &minus_assign (const vector_expression<AE> &ae) {
510	vector_assign<scalar_minus_assign> (*this, ae);
511	return *this;
512	}
513	template<class AT>
514	BOOST_UBLAS_INLINE
515	mapped_vector &operator *= (const AT &at) {
516	vector_assign_scalar<scalar_multiplies_assign> (*this, at);
517	return *this;
518	}
519	template<class AT>
520	BOOST_UBLAS_INLINE
521	mapped_vector &operator /= (const AT &at) {
522	vector_assign_scalar<scalar_divides_assign> (*this, at);
523	return *this;
524	}
525
526	// Swapping
527	BOOST_UBLAS_INLINE
528	void swap (mapped_vector &v) {
529	if (this != &v) {
530	std::swap (size_, v.size_);
531	data ().swap (v.data ());
532	}
533	}
534	BOOST_UBLAS_INLINE
535	friend void swap (mapped_vector &v1, mapped_vector &v2) {
536	v1.swap (v2);
537	}
538
539	// Iterator types
540	private:
541	// Use storage iterator
542	typedef typename A::const_iterator const_subiterator_type;
543	typedef typename A::iterator subiterator_type;
544
545	BOOST_UBLAS_INLINE
546	true_reference at_element (size_type i) {
547	BOOST_UBLAS_CHECK (i < size_, bad_index ());
548	subiterator_type it (data ().find (i));
549	BOOST_UBLAS_CHECK (it != data ().end(), bad_index ());
550	BOOST_UBLAS_CHECK ((*it).first == i, internal_logic ()); // broken map
551	return it->second;
552	}
553
554	public:
555	class const_iterator;
556	class iterator;
557
558	// Element lookup
559	// BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
560	const_iterator find (size_type i) const {
561	return const_iterator (*this, data ().lower_bound (i));
562	}
563	// BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
564	iterator find (size_type i) {
565	return iterator (*this, data ().lower_bound (i));
566	}
567
568
569	class const_iterator:
570	public container_const_reference<mapped_vector>,
571	public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
572	const_iterator, value_type> {
573	public:
574	typedef typename mapped_vector::value_type value_type;
575	typedef typename mapped_vector::difference_type difference_type;
576	typedef typename mapped_vector::const_reference reference;
577	typedef const typename mapped_vector::pointer pointer;
578
579	// Construction and destruction
580	BOOST_UBLAS_INLINE
581	const_iterator ():
582	container_const_reference<self_type> (), it_ () {}
583	BOOST_UBLAS_INLINE
584	const_iterator (const self_type &v, const const_subiterator_type &it):
585	container_const_reference<self_type> (v), it_ (it) {}
586	BOOST_UBLAS_INLINE
587	const_iterator (const typename self_type::iterator &it): // ISSUE self_type:: stops VC8 using std::iterator here
588	container_const_reference<self_type> (it ()), it_ (it.it_) {}
589
590	// Arithmetic
591	BOOST_UBLAS_INLINE
592	const_iterator &operator ++ () {
593	++ it_;
594	return *this;
595	}
596	BOOST_UBLAS_INLINE
597	const_iterator &operator -- () {
598	-- it_;
599	return *this;
600	}
601
602	// Dereference
603	BOOST_UBLAS_INLINE
604	const_reference operator * () const {
605	BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
606	return (*it_).second;
607	}
608
609	// Index
610	BOOST_UBLAS_INLINE
611	size_type index () const {
612	BOOST_UBLAS_CHECK (this != (this) ().end (), bad_index ());
613	BOOST_UBLAS_CHECK ((it_).first < (this) ().size (), bad_index ());
614	return (*it_).first;
615	}
616
617	// Assignment
618	BOOST_UBLAS_INLINE
619	const_iterator &operator = (const const_iterator &it) {
620	container_const_reference<self_type>::assign (&it ());
621	it_ = it.it_;
622	return *this;
623	}
624
625	// Comparison
626	BOOST_UBLAS_INLINE
627	bool operator == (const const_iterator &it) const {
628	BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
629	return it_ == it.it_;
630	}
631
632	private:
633	const_subiterator_type it_;
634	};
635
636	BOOST_UBLAS_INLINE
637	const_iterator begin () const {
638	return const_iterator (*this, data ().begin ());
639	}
640	BOOST_UBLAS_INLINE
641	const_iterator end () const {
642	return const_iterator (*this, data ().end ());
643	}
644
645	class iterator:
646	public container_reference<mapped_vector>,
647	public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
648	iterator, value_type> {
649	public:
650	typedef typename mapped_vector::value_type value_type;
651	typedef typename mapped_vector::difference_type difference_type;
652	typedef typename mapped_vector::true_reference reference;
653	typedef typename mapped_vector::pointer pointer;
654
655	// Construction and destruction
656	BOOST_UBLAS_INLINE
657	iterator ():
658	container_reference<self_type> (), it_ () {}
659	BOOST_UBLAS_INLINE
660	iterator (self_type &v, const subiterator_type &it):
661	container_reference<self_type> (v), it_ (it) {}
662
663	// Arithmetic
664	BOOST_UBLAS_INLINE
665	iterator &operator ++ () {
666	++ it_;
667	return *this;
668	}
669	BOOST_UBLAS_INLINE
670	iterator &operator -- () {
671	-- it_;
672	return *this;
673	}
674
675	// Dereference
676	BOOST_UBLAS_INLINE
677	reference operator * () const {
678	BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
679	return (*it_).second;
680	}
681
682	// Index
683	BOOST_UBLAS_INLINE
684	size_type index () const {
685	BOOST_UBLAS_CHECK (this != (this) ().end (), bad_index ());
686	BOOST_UBLAS_CHECK ((it_).first < (this) ().size (), bad_index ());
687	return (*it_).first;
688	}
689
690	// Assignment
691	BOOST_UBLAS_INLINE
692	iterator &operator = (const iterator &it) {
693	container_reference<self_type>::assign (&it ());
694	it_ = it.it_;
695	return *this;
696	}
697
698	// Comparison
699	BOOST_UBLAS_INLINE
700	bool operator == (const iterator &it) const {
701	BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
702	return it_ == it.it_;
703	}
704
705	private:
706	subiterator_type it_;
707
708	friend class const_iterator;
709	};
710
711	BOOST_UBLAS_INLINE
712	iterator begin () {
713	return iterator (*this, data ().begin ());
714	}
715	BOOST_UBLAS_INLINE
716	iterator end () {
717	return iterator (*this, data ().end ());
718	}
719
720	// Reverse iterator
721	typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
722	typedef reverse_iterator_base<iterator> reverse_iterator;
723
724	BOOST_UBLAS_INLINE
725	const_reverse_iterator rbegin () const {
726	return const_reverse_iterator (end ());
727	}
728	BOOST_UBLAS_INLINE
729	const_reverse_iterator rend () const {
730	return const_reverse_iterator (begin ());
731	}
732	BOOST_UBLAS_INLINE
733	reverse_iterator rbegin () {
734	return reverse_iterator (end ());
735	}
736	BOOST_UBLAS_INLINE
737	reverse_iterator rend () {
738	return reverse_iterator (begin ());
739	}
740
741	private:
742	size_type size_;
743	array_type data_;
744	static const value_type zero_;
745	};
746
747	template<class T, class A>
748	const typename mapped_vector<T, A>::value_type mapped_vector<T, A>::zero_ = value_type/zero/();
749
750
751	// Compressed array based sparse vector class
752	// Thanks to Kresimir Fresl for extending this to cover different index bases.
753	template<class T, std::size_t IB, class IA, class TA>
754	class compressed_vector:
755	public vector_container<compressed_vector<T, IB, IA, TA> > {
756
757	typedef T &true_reference;
758	typedef T *pointer;
759	typedef const T *const_pointer;
760	typedef compressed_vector<T, IB, IA, TA> self_type;
761	public:
762	#ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
763	using vector_container<self_type>::operator ();
764	#endif
765	// ISSUE require type consistency check
766	// is_convertable (IA::size_type, TA::size_type)
767	typedef typename IA::value_type size_type;
768	typedef typename IA::difference_type difference_type;
769	typedef T value_type;
770	typedef const T &const_reference;
771	#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
772	typedef T &reference;
773	#else
774	typedef sparse_vector_element<self_type> reference;
775	#endif
776	typedef IA index_array_type;
777	typedef TA value_array_type;
778	typedef const vector_reference<const self_type> const_closure_type;
779	typedef vector_reference<self_type> closure_type;
780	typedef self_type vector_temporary_type;
781	typedef sparse_tag storage_category;
782
783	// Construction and destruction
784	BOOST_UBLAS_INLINE
785	compressed_vector ():
786	vector_container<self_type> (),
787	size_ (0), capacity_ (restrict_capacity (0)), filled_ (0),
788	index_data_ (capacity_), value_data_ (capacity_) {
789	storage_invariants ();
790	}
791	explicit BOOST_UBLAS_INLINE
792	compressed_vector (size_type size, size_type non_zeros = 0):
793	vector_container<self_type> (),
794	size_ (size), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
795	index_data_ (capacity_), value_data_ (capacity_) {
796	storage_invariants ();
797	}
798	BOOST_UBLAS_INLINE
799	compressed_vector (const compressed_vector &v):
800	vector_container<self_type> (),
801	size_ (v.size_), capacity_ (v.capacity_), filled_ (v.filled_),
802	index_data_ (v.index_data_), value_data_ (v.value_data_) {
803	storage_invariants ();
804	}
805	template<class AE>
806	BOOST_UBLAS_INLINE
807	compressed_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
808	vector_container<self_type> (),
809	size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)), filled_ (0),
810	index_data_ (capacity_), value_data_ (capacity_) {
811	storage_invariants ();
812	vector_assign<scalar_assign> (*this, ae);
813	}
814
815	// Accessors
816	BOOST_UBLAS_INLINE
817	size_type size () const {
818	return size_;
819	}
820	BOOST_UBLAS_INLINE
821	size_type nnz_capacity () const {
822	return capacity_;
823	}
824	BOOST_UBLAS_INLINE
825	size_type nnz () const {
826	return filled_;
827	}
828
829	// Storage accessors
830	BOOST_UBLAS_INLINE
831	static size_type index_base () {
832	return IB;
833	}
834	BOOST_UBLAS_INLINE
835	typename index_array_type::size_type filled () const {
836	return filled_;
837	}
838	BOOST_UBLAS_INLINE
839	const index_array_type &index_data () const {
840	return index_data_;
841	}
842	BOOST_UBLAS_INLINE
843	const value_array_type &value_data () const {
844	return value_data_;
845	}
846	BOOST_UBLAS_INLINE
847	void set_filled (const typename index_array_type::size_type & filled) {
848	filled_ = filled;
849	storage_invariants ();
850	}
851	BOOST_UBLAS_INLINE
852	index_array_type &index_data () {
853	return index_data_;
854	}
855	BOOST_UBLAS_INLINE
856	value_array_type &value_data () {
857	return value_data_;
858	}
859
860	// Resizing
861	private:
862	BOOST_UBLAS_INLINE
863	size_type restrict_capacity (size_type non_zeros) const {
864	non_zeros = (std::max) (non_zeros, size_type (1));
865	non_zeros = (std::min) (non_zeros, size_);
866	return non_zeros;
867	}
868	public:
869	BOOST_UBLAS_INLINE
870	void resize (size_type size, bool preserve = true) {
871	// FIXME preserve unimplemented
872	BOOST_UBLAS_CHECK (!preserve, internal_logic ());
873	size_ = size;
874	capacity_ = restrict_capacity (capacity_);
875	index_data_. resize (capacity_);
876	value_data_. resize (capacity_);
877	filled_ = 0;
878	storage_invariants ();
879	}
880
881	// Reserving
882	BOOST_UBLAS_INLINE
883	void reserve (size_type non_zeros, bool preserve = true) {
884	capacity_ = restrict_capacity (non_zeros);
885	if (preserve) {
886	index_data_. resize (capacity_, size_type ());
887	value_data_. resize (capacity_, value_type ());
888	filled_ = (std::min) (capacity_, filled_);
889	}
890	else {
891	index_data_. resize (capacity_);
892	value_data_. resize (capacity_);
893	filled_ = 0;
894	}
895	storage_invariants ();
896	}
897
898	// Element support
899	BOOST_UBLAS_INLINE
900	pointer find_element (size_type i) {
901	return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
902	}
903	BOOST_UBLAS_INLINE
904	const_pointer find_element (size_type i) const {
905	const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
906	if (it == index_data_.begin () + filled_ \|\| *it != k_based (i))
907	return 0;
908	return &value_data_ [it - index_data_.begin ()];
909	}
910
911	// Element access
912	BOOST_UBLAS_INLINE
913	const_reference operator () (size_type i) const {
914	BOOST_UBLAS_CHECK (i < size_, bad_index ());
915	const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
916	if (it == index_data_.begin () + filled_ \|\| *it != k_based (i))
917	return zero_;
918	return value_data_ [it - index_data_.begin ()];
919	}
920	BOOST_UBLAS_INLINE
921	true_reference ref (size_type i) {
922	BOOST_UBLAS_CHECK (i < size_, bad_index ());
923	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
924	if (it == index_data_.begin () + filled_ \|\| *it != k_based (i))
925	return insert_element (i, value_type/zero/());
926	else
927	return value_data_ [it - index_data_.begin ()];
928	}
929	BOOST_UBLAS_INLINE
930	reference operator () (size_type i) {
931	#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
932	return ref (i) ;
933	#else
934	BOOST_UBLAS_CHECK (i < size_, bad_index ());
935	return reference (*this, i);
936	#endif
937	}
938
939	BOOST_UBLAS_INLINE
940	const_reference operator [] (size_type i) const {
941	return (*this) (i);
942	}
943	BOOST_UBLAS_INLINE
944	reference operator [] (size_type i) {
945	return (*this) (i);
946	}
947
948	// Element assignment
949	BOOST_UBLAS_INLINE
950	true_reference insert_element (size_type i, const_reference t) {
951	BOOST_UBLAS_CHECK (!find_element (i), bad_index ()); // duplicate element
952	if (filled_ >= capacity_)
953	reserve (2 * capacity_, true);
954	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
955	// ISSUE max_capacity limit due to difference_type
956	typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
957	BOOST_UBLAS_CHECK (filled_ == 0 \|\| filled_ == typename index_array_type::size_type (n) \|\| *it != k_based (i), internal_logic ()); // duplicate found by lower_bound
958	++ filled_;
959	it = index_data_.begin () + n;
960	std::copy_backward (it, index_data_.begin () + filled_ - 1, index_data_.begin () + filled_);
961	*it = k_based (i);
962	typename value_array_type::iterator itt (value_data_.begin () + n);
963	std::copy_backward (itt, value_data_.begin () + filled_ - 1, value_data_.begin () + filled_);
964	*itt = t;
965	storage_invariants ();
966	return *itt;
967	}
968	BOOST_UBLAS_INLINE
969	void erase_element (size_type i) {
970	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
971	typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
972	if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
973	std::copy (it + 1, index_data_.begin () + filled_, it);
974	typename value_array_type::iterator itt (value_data_.begin () + n);
975	std::copy (itt + 1, value_data_.begin () + filled_, itt);
976	-- filled_;
977	}
978	storage_invariants ();
979	}
980
981	// Zeroing
982	BOOST_UBLAS_INLINE
983	void clear () {
984	filled_ = 0;
985	storage_invariants ();
986	}
987
988	// Assignment
989	BOOST_UBLAS_INLINE
990	compressed_vector &operator = (const compressed_vector &v) {
991	if (this != &v) {
992	size_ = v.size_;
993	capacity_ = v.capacity_;
994	filled_ = v.filled_;
995	index_data_ = v.index_data_;
996	value_data_ = v.value_data_;
997	}
998	storage_invariants ();
999	return *this;
1000	}
1001	template<class C> // Container assignment without temporary
1002	BOOST_UBLAS_INLINE
1003	compressed_vector &operator = (const vector_container<C> &v) {
1004	resize (v ().size (), false);
1005	assign (v);
1006	return *this;
1007	}
1008	BOOST_UBLAS_INLINE
1009	compressed_vector &assign_temporary (compressed_vector &v) {
1010	swap (v);
1011	return *this;
1012	}
1013	template<class AE>
1014	BOOST_UBLAS_INLINE
1015	compressed_vector &operator = (const vector_expression<AE> &ae) {
1016	self_type temporary (ae, capacity_);
1017	return assign_temporary (temporary);
1018	}
1019	template<class AE>
1020	BOOST_UBLAS_INLINE
1021	compressed_vector &assign (const vector_expression<AE> &ae) {
1022	vector_assign<scalar_assign> (*this, ae);
1023	return *this;
1024	}
1025
1026	// Computed assignment
1027	template<class AE>
1028	BOOST_UBLAS_INLINE
1029	compressed_vector &operator += (const vector_expression<AE> &ae) {
1030	self_type temporary (*this + ae, capacity_);
1031	return assign_temporary (temporary);
1032	}
1033	template<class C> // Container assignment without temporary
1034	BOOST_UBLAS_INLINE
1035	compressed_vector &operator += (const vector_container<C> &v) {
1036	plus_assign (v);
1037	return *this;
1038	}
1039	template<class AE>
1040	BOOST_UBLAS_INLINE
1041	compressed_vector &plus_assign (const vector_expression<AE> &ae) {
1042	vector_assign<scalar_plus_assign> (*this, ae);
1043	return *this;
1044	}
1045	template<class AE>
1046	BOOST_UBLAS_INLINE
1047	compressed_vector &operator -= (const vector_expression<AE> &ae) {
1048	self_type temporary (*this - ae, capacity_);
1049	return assign_temporary (temporary);
1050	}
1051	template<class C> // Container assignment without temporary
1052	BOOST_UBLAS_INLINE
1053	compressed_vector &operator -= (const vector_container<C> &v) {
1054	minus_assign (v);
1055	return *this;
1056	}
1057	template<class AE>
1058	BOOST_UBLAS_INLINE
1059	compressed_vector &minus_assign (const vector_expression<AE> &ae) {
1060	vector_assign<scalar_minus_assign> (*this, ae);
1061	return *this;
1062	}
1063	template<class AT>
1064	BOOST_UBLAS_INLINE
1065	compressed_vector &operator *= (const AT &at) {
1066	vector_assign_scalar<scalar_multiplies_assign> (*this, at);
1067	return *this;
1068	}
1069	template<class AT>
1070	BOOST_UBLAS_INLINE
1071	compressed_vector &operator /= (const AT &at) {
1072	vector_assign_scalar<scalar_divides_assign> (*this, at);
1073	return *this;
1074	}
1075
1076	// Swapping
1077	BOOST_UBLAS_INLINE
1078	void swap (compressed_vector &v) {
1079	if (this != &v) {
1080	std::swap (size_, v.size_);
1081	std::swap (capacity_, v.capacity_);
1082	std::swap (filled_, v.filled_);
1083	index_data_.swap (v.index_data_);
1084	value_data_.swap (v.value_data_);
1085	}
1086	storage_invariants ();
1087	}
1088	BOOST_UBLAS_INLINE
1089	friend void swap (compressed_vector &v1, compressed_vector &v2) {
1090	v1.swap (v2);
1091	}
1092
1093	// Back element insertion and erasure
1094	BOOST_UBLAS_INLINE
1095	void push_back (size_type i, const_reference t) {
1096	BOOST_UBLAS_CHECK (filled_ == 0 \|\| index_data_ [filled_ - 1] < k_based (i), external_logic ());
1097	if (filled_ >= capacity_)
1098	reserve (2 * capacity_, true);
1099	BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
1100	index_data_ [filled_] = k_based (i);
1101	value_data_ [filled_] = t;
1102	++ filled_;
1103	storage_invariants ();
1104	}
1105	BOOST_UBLAS_INLINE
1106	void pop_back () {
1107	BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
1108	-- filled_;
1109	storage_invariants ();
1110	}
1111
1112	// Iterator types
1113	private:
1114	// Use index array iterator
1115	typedef typename IA::const_iterator const_subiterator_type;
1116	typedef typename IA::iterator subiterator_type;
1117
1118	BOOST_UBLAS_INLINE
1119	true_reference at_element (size_type i) {
1120	BOOST_UBLAS_CHECK (i < size_, bad_index ());
1121	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1122	BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
1123	return value_data_ [it - index_data_.begin ()];
1124	}
1125
1126	public:
1127	class const_iterator;
1128	class iterator;
1129
1130	// Element lookup
1131	// BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1132	const_iterator find (size_type i) const {
1133	return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1134	}
1135	// BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1136	iterator find (size_type i) {
1137	return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1138	}
1139
1140
1141	class const_iterator:
1142	public container_const_reference<compressed_vector>,
1143	public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1144	const_iterator, value_type> {
1145	public:
1146	typedef typename compressed_vector::value_type value_type;
1147	typedef typename compressed_vector::difference_type difference_type;
1148	typedef typename compressed_vector::const_reference reference;
1149	typedef const typename compressed_vector::pointer pointer;
1150
1151	// Construction and destruction
1152	BOOST_UBLAS_INLINE
1153	const_iterator ():
1154	container_const_reference<self_type> (), it_ () {}
1155	BOOST_UBLAS_INLINE
1156	const_iterator (const self_type &v, const const_subiterator_type &it):
1157	container_const_reference<self_type> (v), it_ (it) {}
1158	BOOST_UBLAS_INLINE
1159	const_iterator (const typename self_type::iterator &it): // ISSUE self_type:: stops VC8 using std::iterator here
1160	container_const_reference<self_type> (it ()), it_ (it.it_) {}
1161
1162	// Arithmetic
1163	BOOST_UBLAS_INLINE
1164	const_iterator &operator ++ () {
1165	++ it_;
1166	return *this;
1167	}
1168	BOOST_UBLAS_INLINE
1169	const_iterator &operator -- () {
1170	-- it_;
1171	return *this;
1172	}
1173
1174	// Dereference
1175	BOOST_UBLAS_INLINE
1176	const_reference operator * () const {
1177	BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
1178	return (this) ().value_data_ [it_ - (this) ().index_data_.begin ()];
1179	}
1180
1181	// Index
1182	BOOST_UBLAS_INLINE
1183	size_type index () const {
1184	BOOST_UBLAS_CHECK (this != (this) ().end (), bad_index ());
1185	BOOST_UBLAS_CHECK ((this) ().zero_based (it_) < (*this) ().size (), bad_index ());
1186	return (this) ().zero_based (it_);
1187	}
1188
1189	// Assignment
1190	BOOST_UBLAS_INLINE
1191	const_iterator &operator = (const const_iterator &it) {
1192	container_const_reference<self_type>::assign (&it ());
1193	it_ = it.it_;
1194	return *this;
1195	}
1196
1197	// Comparison
1198	BOOST_UBLAS_INLINE
1199	bool operator == (const const_iterator &it) const {
1200	BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
1201	return it_ == it.it_;
1202	}
1203
1204	private:
1205	const_subiterator_type it_;
1206	};
1207
1208	BOOST_UBLAS_INLINE
1209	const_iterator begin () const {
1210	return find (0);
1211	}
1212	BOOST_UBLAS_INLINE
1213	const_iterator end () const {
1214	return find (size_);
1215	}
1216
1217	class iterator:
1218	public container_reference<compressed_vector>,
1219	public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1220	iterator, value_type> {
1221	public:
1222	typedef typename compressed_vector::value_type value_type;
1223	typedef typename compressed_vector::difference_type difference_type;
1224	typedef typename compressed_vector::true_reference reference;
1225	typedef typename compressed_vector::pointer pointer;
1226
1227	// Construction and destruction
1228	BOOST_UBLAS_INLINE
1229	iterator ():
1230	container_reference<self_type> (), it_ () {}
1231	BOOST_UBLAS_INLINE
1232	iterator (self_type &v, const subiterator_type &it):
1233	container_reference<self_type> (v), it_ (it) {}
1234
1235	// Arithmetic
1236	BOOST_UBLAS_INLINE
1237	iterator &operator ++ () {
1238	++ it_;
1239	return *this;
1240	}
1241	BOOST_UBLAS_INLINE
1242	iterator &operator -- () {
1243	-- it_;
1244	return *this;
1245	}
1246
1247	// Dereference
1248	BOOST_UBLAS_INLINE
1249	reference operator * () const {
1250	BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
1251	return (this) ().value_data_ [it_ - (this) ().index_data_.begin ()];
1252	}
1253
1254	// Index
1255	BOOST_UBLAS_INLINE
1256	size_type index () const {
1257	BOOST_UBLAS_CHECK (this != (this) ().end (), bad_index ());
1258	BOOST_UBLAS_CHECK ((this) ().zero_based (it_) < (*this) ().size (), bad_index ());
1259	return (this) ().zero_based (it_);
1260	}
1261
1262	// Assignment
1263	BOOST_UBLAS_INLINE
1264	iterator &operator = (const iterator &it) {
1265	container_reference<self_type>::assign (&it ());
1266	it_ = it.it_;
1267	return *this;
1268	}
1269
1270	// Comparison
1271	BOOST_UBLAS_INLINE
1272	bool operator == (const iterator &it) const {
1273	BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
1274	return it_ == it.it_;
1275	}
1276
1277	private:
1278	subiterator_type it_;
1279
1280	friend class const_iterator;
1281	};
1282
1283	BOOST_UBLAS_INLINE
1284	iterator begin () {
1285	return find (0);
1286	}
1287	BOOST_UBLAS_INLINE
1288	iterator end () {
1289	return find (size_);
1290	}
1291
1292	// Reverse iterator
1293	typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
1294	typedef reverse_iterator_base<iterator> reverse_iterator;
1295
1296	BOOST_UBLAS_INLINE
1297	const_reverse_iterator rbegin () const {
1298	return const_reverse_iterator (end ());
1299	}
1300	BOOST_UBLAS_INLINE
1301	const_reverse_iterator rend () const {
1302	return const_reverse_iterator (begin ());
1303	}
1304	BOOST_UBLAS_INLINE
1305	reverse_iterator rbegin () {
1306	return reverse_iterator (end ());
1307	}
1308	BOOST_UBLAS_INLINE
1309	reverse_iterator rend () {
1310	return reverse_iterator (begin ());
1311	}
1312
1313	private:
1314	void storage_invariants () const
1315	{
1316	BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
1317	BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
1318	BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
1319	}
1320
1321	size_type size_;
1322	typename index_array_type::size_type capacity_;
1323	typename index_array_type::size_type filled_;
1324	index_array_type index_data_;
1325	value_array_type value_data_;
1326	static const value_type zero_;
1327
1328	BOOST_UBLAS_INLINE
1329	static size_type zero_based (size_type k_based_index) {
1330	return k_based_index - IB;
1331	}
1332	BOOST_UBLAS_INLINE
1333	static size_type k_based (size_type zero_based_index) {
1334	return zero_based_index + IB;
1335	}
1336
1337	friend class iterator;
1338	friend class const_iterator;
1339	};
1340
1341	template<class T, std::size_t IB, class IA, class TA>
1342	const typename compressed_vector<T, IB, IA, TA>::value_type compressed_vector<T, IB, IA, TA>::zero_ = value_type/zero/();
1343
1344
1345	// Coordimate array based sparse vector class
1346	// Thanks to Kresimir Fresl for extending this to cover different index bases.
1347	template<class T, std::size_t IB, class IA, class TA>
1348	class coordinate_vector:
1349	public vector_container<coordinate_vector<T, IB, IA, TA> > {
1350
1351	typedef T &true_reference;
1352	typedef T *pointer;
1353	typedef const T *const_pointer;
1354	typedef coordinate_vector<T, IB, IA, TA> self_type;
1355	public:
1356	#ifdef BOOST_UBLAS_ENABLE_PROXY_SHORTCUTS
1357	using vector_container<self_type>::operator ();
1358	#endif
1359	// ISSUE require type consistency check
1360	// is_convertable (IA::size_type, TA::size_type)
1361	typedef typename IA::value_type size_type;
1362	typedef typename IA::difference_type difference_type;
1363	typedef T value_type;
1364	typedef const T &const_reference;
1365	#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
1366	typedef T &reference;
1367	#else
1368	typedef sparse_vector_element<self_type> reference;
1369	#endif
1370	typedef IA index_array_type;
1371	typedef TA value_array_type;
1372	typedef const vector_reference<const self_type> const_closure_type;
1373	typedef vector_reference<self_type> closure_type;
1374	typedef self_type vector_temporary_type;
1375	typedef sparse_tag storage_category;
1376
1377	// Construction and destruction
1378	BOOST_UBLAS_INLINE
1379	coordinate_vector ():
1380	vector_container<self_type> (),
1381	size_ (0), capacity_ (restrict_capacity (0)),
1382	filled_ (0), sorted_filled_ (filled_), sorted_ (true),
1383	index_data_ (capacity_), value_data_ (capacity_) {
1384	storage_invariants ();
1385	}
1386	explicit BOOST_UBLAS_INLINE
1387	coordinate_vector (size_type size, size_type non_zeros = 0):
1388	vector_container<self_type> (),
1389	size_ (size), capacity_ (restrict_capacity (non_zeros)),
1390	filled_ (0), sorted_filled_ (filled_), sorted_ (true),
1391	index_data_ (capacity_), value_data_ (capacity_) {
1392	storage_invariants ();
1393	}
1394	BOOST_UBLAS_INLINE
1395	coordinate_vector (const coordinate_vector &v):
1396	vector_container<self_type> (),
1397	size_ (v.size_), capacity_ (v.capacity_),
1398	filled_ (v.filled_), sorted_filled_ (v.sorted_filled_), sorted_ (v.sorted_),
1399	index_data_ (v.index_data_), value_data_ (v.value_data_) {
1400	storage_invariants ();
1401	}
1402	template<class AE>
1403	BOOST_UBLAS_INLINE
1404	coordinate_vector (const vector_expression<AE> &ae, size_type non_zeros = 0):
1405	vector_container<self_type> (),
1406	size_ (ae ().size ()), capacity_ (restrict_capacity (non_zeros)),
1407	filled_ (0), sorted_filled_ (filled_), sorted_ (true),
1408	index_data_ (capacity_), value_data_ (capacity_) {
1409	storage_invariants ();
1410	vector_assign<scalar_assign> (*this, ae);
1411	}
1412
1413	// Accessors
1414	BOOST_UBLAS_INLINE
1415	size_type size () const {
1416	return size_;
1417	}
1418	BOOST_UBLAS_INLINE
1419	size_type nnz_capacity () const {
1420	return capacity_;
1421	}
1422	BOOST_UBLAS_INLINE
1423	size_type nnz () const {
1424	return filled_;
1425	}
1426
1427	// Storage accessors
1428	BOOST_UBLAS_INLINE
1429	static size_type index_base () {
1430	return IB;
1431	}
1432	BOOST_UBLAS_INLINE
1433	typename index_array_type::size_type filled () const {
1434	return filled_;
1435	}
1436	BOOST_UBLAS_INLINE
1437	const index_array_type &index_data () const {
1438	return index_data_;
1439	}
1440	BOOST_UBLAS_INLINE
1441	const value_array_type &value_data () const {
1442	return value_data_;
1443	}
1444	BOOST_UBLAS_INLINE
1445	void set_filled (const typename index_array_type::size_type &sorted, const typename index_array_type::size_type &filled) {
1446	sorted_filled_ = sorted;
1447	filled_ = filled;
1448	storage_invariants ();
1449	return filled_;
1450	}
1451	BOOST_UBLAS_INLINE
1452	index_array_type &index_data () {
1453	return index_data_;
1454	}
1455	BOOST_UBLAS_INLINE
1456	value_array_type &value_data () {
1457	return value_data_;
1458	}
1459
1460	// Resizing
1461	private:
1462	BOOST_UBLAS_INLINE
1463	size_type restrict_capacity (size_type non_zeros) const {
1464	// minimum non_zeros
1465	non_zeros = (std::max) (non_zeros, size_type (1));
1466	// ISSUE no maximum as coordinate may contain inserted duplicates
1467	return non_zeros;
1468	}
1469	public:
1470	BOOST_UBLAS_INLINE
1471	void resize (size_type size, bool preserve = true) {
1472	if (preserve)
1473	sort (); // remove duplicate elements.
1474	capacity_ = restrict_capacity (capacity_);
1475	if (preserve) {
1476	index_data_. resize (capacity_, size_type ());
1477	value_data_. resize (capacity_, value_type ());
1478	filled_ = (std::min) (capacity_, filled_);
1479	}
1480	else {
1481	index_data_. resize (capacity_);
1482	value_data_. resize (capacity_);
1483	filled_ = 0;
1484	}
1485	sorted_filled_ = filled_;
1486	size_ = size;
1487	storage_invariants ();
1488	}
1489	// Reserving
1490	BOOST_UBLAS_INLINE
1491	void reserve (size_type non_zeros, bool preserve = true) {
1492	if (preserve)
1493	sort (); // remove duplicate elements.
1494	capacity_ = restrict_capacity (non_zeros);
1495	if (preserve) {
1496	index_data_. resize (capacity_, size_type ());
1497	value_data_. resize (capacity_, value_type ());
1498	filled_ = (std::min) (capacity_, filled_);
1499	}
1500	else {
1501	index_data_. resize (capacity_);
1502	value_data_. resize (capacity_);
1503	filled_ = 0;
1504	}
1505	sorted_filled_ = filled_;
1506	storage_invariants ();
1507	}
1508
1509	// Element support
1510	BOOST_UBLAS_INLINE
1511	pointer find_element (size_type i) {
1512	return const_cast<pointer> (const_cast<const self_type&>(*this).find_element (i));
1513	}
1514	BOOST_UBLAS_INLINE
1515	const_pointer find_element (size_type i) const {
1516	sort ();
1517	const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1518	if (it == index_data_.begin () + filled_ \|\| *it != k_based (i))
1519	return 0;
1520	return &value_data_ [it - index_data_.begin ()];
1521	}
1522
1523	// Element access
1524	BOOST_UBLAS_INLINE
1525	const_reference operator () (size_type i) const {
1526	BOOST_UBLAS_CHECK (i < size_, bad_index ());
1527	sort ();
1528	const_subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1529	if (it == index_data_.begin () + filled_ \|\| *it != k_based (i))
1530	return zero_;
1531	return value_data_ [it - index_data_.begin ()];
1532	}
1533	BOOST_UBLAS_INLINE
1534	true_reference ref (size_type i) {
1535	BOOST_UBLAS_CHECK (i < size_, bad_index ());
1536	sort ();
1537	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1538	if (it == index_data_.begin () + filled_ \|\| *it != k_based (i))
1539	return insert_element (i, value_type/zero/());
1540	else
1541	return value_data_ [it - index_data_.begin ()];
1542	}
1543	BOOST_UBLAS_INLINE
1544	reference operator () (size_type i) {
1545	#ifndef BOOST_UBLAS_STRICT_VECTOR_SPARSE
1546	return ref (i);
1547	#else
1548	BOOST_UBLAS_CHECK (i < size_, bad_index ());
1549	return reference (*this, i);
1550	#endif
1551	}
1552
1553	BOOST_UBLAS_INLINE
1554	const_reference operator [] (size_type i) const {
1555	return (*this) (i);
1556	}
1557	BOOST_UBLAS_INLINE
1558	reference operator [] (size_type i) {
1559	return (*this) (i);
1560	}
1561
1562	// Element assignment
1563	BOOST_UBLAS_INLINE
1564	void append_element (size_type i, const_reference t) {
1565	if (filled_ >= capacity_)
1566	reserve (2 * filled_, true);
1567	BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
1568	index_data_ [filled_] = k_based (i);
1569	value_data_ [filled_] = t;
1570	++ filled_;
1571	sorted_ = false;
1572	storage_invariants ();
1573	}
1574	BOOST_UBLAS_INLINE
1575	true_reference insert_element (size_type i, const_reference t) {
1576	BOOST_UBLAS_CHECK (!find_element (i), bad_index ()); // duplicate element
1577	append_element (i, t);
1578	return value_data_ [filled_ - 1];
1579	}
1580	BOOST_UBLAS_INLINE
1581	void erase_element (size_type i) {
1582	sort ();
1583	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1584	typename std::iterator_traits<subiterator_type>::difference_type n = it - index_data_.begin ();
1585	if (filled_ > typename index_array_type::size_type (n) && *it == k_based (i)) {
1586	std::copy (it + 1, index_data_.begin () + filled_, it);
1587	typename value_array_type::iterator itt (value_data_.begin () + n);
1588	std::copy (itt + 1, value_data_.begin () + filled_, itt);
1589	-- filled_;
1590	sorted_filled_ = filled_;
1591	}
1592	storage_invariants ();
1593	}
1594
1595	// Zeroing
1596	BOOST_UBLAS_INLINE
1597	void clear () {
1598	filled_ = 0;
1599	sorted_filled_ = filled_;
1600	sorted_ = true;
1601	storage_invariants ();
1602	}
1603
1604	// Assignment
1605	BOOST_UBLAS_INLINE
1606	coordinate_vector &operator = (const coordinate_vector &v) {
1607	if (this != &v) {
1608	size_ = v.size_;
1609	capacity_ = v.capacity_;
1610	filled_ = v.filled_;
1611	sorted_filled_ = v.sorted_filled_;
1612	sorted_ = v.sorted_;
1613	index_data_ = v.index_data_;
1614	value_data_ = v.value_data_;
1615	}
1616	storage_invariants ();
1617	return *this;
1618	}
1619	template<class C> // Container assignment without temporary
1620	BOOST_UBLAS_INLINE
1621	coordinate_vector &operator = (const vector_container<C> &v) {
1622	resize (v ().size (), false);
1623	assign (v);
1624	return *this;
1625	}
1626	BOOST_UBLAS_INLINE
1627	coordinate_vector &assign_temporary (coordinate_vector &v) {
1628	swap (v);
1629	return *this;
1630	}
1631	template<class AE>
1632	BOOST_UBLAS_INLINE
1633	coordinate_vector &operator = (const vector_expression<AE> &ae) {
1634	self_type temporary (ae, capacity_);
1635	return assign_temporary (temporary);
1636	}
1637	template<class AE>
1638	BOOST_UBLAS_INLINE
1639	coordinate_vector &assign (const vector_expression<AE> &ae) {
1640	vector_assign<scalar_assign> (*this, ae);
1641	return *this;
1642	}
1643
1644	// Computed assignment
1645	template<class AE>
1646	BOOST_UBLAS_INLINE
1647	coordinate_vector &operator += (const vector_expression<AE> &ae) {
1648	self_type temporary (*this + ae, capacity_);
1649	return assign_temporary (temporary);
1650	}
1651	template<class C> // Container assignment without temporary
1652	BOOST_UBLAS_INLINE
1653	coordinate_vector &operator += (const vector_container<C> &v) {
1654	plus_assign (v);
1655	return *this;
1656	}
1657	template<class AE>
1658	BOOST_UBLAS_INLINE
1659	coordinate_vector &plus_assign (const vector_expression<AE> &ae) {
1660	vector_assign<scalar_plus_assign> (*this, ae);
1661	return *this;
1662	}
1663	template<class AE>
1664	BOOST_UBLAS_INLINE
1665	coordinate_vector &operator -= (const vector_expression<AE> &ae) {
1666	self_type temporary (*this - ae, capacity_);
1667	return assign_temporary (temporary);
1668	}
1669	template<class C> // Container assignment without temporary
1670	BOOST_UBLAS_INLINE
1671	coordinate_vector &operator -= (const vector_container<C> &v) {
1672	minus_assign (v);
1673	return *this;
1674	}
1675	template<class AE>
1676	BOOST_UBLAS_INLINE
1677	coordinate_vector &minus_assign (const vector_expression<AE> &ae) {
1678	vector_assign<scalar_minus_assign> (*this, ae);
1679	return *this;
1680	}
1681	template<class AT>
1682	BOOST_UBLAS_INLINE
1683	coordinate_vector &operator *= (const AT &at) {
1684	vector_assign_scalar<scalar_multiplies_assign> (*this, at);
1685	return *this;
1686	}
1687	template<class AT>
1688	BOOST_UBLAS_INLINE
1689	coordinate_vector &operator /= (const AT &at) {
1690	vector_assign_scalar<scalar_divides_assign> (*this, at);
1691	return *this;
1692	}
1693
1694	// Swapping
1695	BOOST_UBLAS_INLINE
1696	void swap (coordinate_vector &v) {
1697	if (this != &v) {
1698	std::swap (size_, v.size_);
1699	std::swap (capacity_, v.capacity_);
1700	std::swap (filled_, v.filled_);
1701	std::swap (sorted_filled_, v.sorted_filled_);
1702	std::swap (sorted_, v.sorted_);
1703	index_data_.swap (v.index_data_);
1704	value_data_.swap (v.value_data_);
1705	}
1706	storage_invariants ();
1707	}
1708	BOOST_UBLAS_INLINE
1709	friend void swap (coordinate_vector &v1, coordinate_vector &v2) {
1710	v1.swap (v2);
1711	}
1712
1713	// Sorting and summation of duplicates
1714	BOOST_UBLAS_INLINE
1715	void sort () const {
1716	if (! sorted_ && filled_ > 0) {
1717	typedef index_pair_array<index_array_type, value_array_type> array_pair;
1718	array_pair ipa (filled_, index_data_, value_data_);
1719	const typename array_pair::iterator iunsorted = ipa.begin () + sorted_filled_;
1720	// sort new elements and merge
1721	std::sort (iunsorted, ipa.end ());
1722	std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
1723
1724	// sum duplicates with += and remove
1725	size_type filled = 0;
1726	for (size_type i = 1; i < filled_; ++ i) {
1727	if (index_data_ [filled] != index_data_ [i]) {
1728	++ filled;
1729	if (filled != i) {
1730	index_data_ [filled] = index_data_ [i];
1731	value_data_ [filled] = value_data_ [i];
1732	}
1733	} else {
1734	value_data_ [filled] += value_data_ [i];
1735	}
1736	}
1737	filled_ = filled + 1;
1738	sorted_filled_ = filled_;
1739	sorted_ = true;
1740	storage_invariants ();
1741	}
1742	}
1743
1744	// Back element insertion and erasure
1745	BOOST_UBLAS_INLINE
1746	void push_back (size_type i, const_reference t) {
1747	// must maintain sort order
1748	BOOST_UBLAS_CHECK (sorted_ && (filled_ == 0 \|\| index_data_ [filled_ - 1] < k_based (i)), external_logic ());
1749	if (filled_ >= capacity_)
1750	reserve (2 * filled_, true);
1751	BOOST_UBLAS_CHECK (filled_ < capacity_, internal_logic ());
1752	index_data_ [filled_] = k_based (i);
1753	value_data_ [filled_] = t;
1754	++ filled_;
1755	sorted_filled_ = filled_;
1756	storage_invariants ();
1757	}
1758	BOOST_UBLAS_INLINE
1759	void pop_back () {
1760	// ISSUE invariants could be simpilfied if sorted required as precondition
1761	BOOST_UBLAS_CHECK (filled_ > 0, external_logic ());
1762	-- filled_;
1763	sorted_filled_ = (std::min) (sorted_filled_, filled_);
1764	sorted_ = sorted_filled_ = filled_;
1765	storage_invariants ();
1766	}
1767
1768	// Iterator types
1769	private:
1770	// Use index array iterator
1771	typedef typename IA::const_iterator const_subiterator_type;
1772	typedef typename IA::iterator subiterator_type;
1773
1774	BOOST_UBLAS_INLINE
1775	true_reference at_element (size_type i) {
1776	BOOST_UBLAS_CHECK (i < size_, bad_index ());
1777	sort ();
1778	subiterator_type it (detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1779	BOOST_UBLAS_CHECK (it != index_data_.begin () + filled_ && *it == k_based (i), bad_index ());
1780	return value_data_ [it - index_data_.begin ()];
1781	}
1782
1783	public:
1784	class const_iterator;
1785	class iterator;
1786
1787	// Element lookup
1788	// BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1789	const_iterator find (size_type i) const {
1790	sort ();
1791	return const_iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1792	}
1793	// BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
1794	iterator find (size_type i) {
1795	sort ();
1796	return iterator (*this, detail::lower_bound (index_data_.begin (), index_data_.begin () + filled_, k_based (i), std::less<size_type> ()));
1797	}
1798
1799
1800	class const_iterator:
1801	public container_const_reference<coordinate_vector>,
1802	public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1803	const_iterator, value_type> {
1804	public:
1805	typedef typename coordinate_vector::value_type value_type;
1806	typedef typename coordinate_vector::difference_type difference_type;
1807	typedef typename coordinate_vector::const_reference reference;
1808	typedef const typename coordinate_vector::pointer pointer;
1809
1810	// Construction and destruction
1811	BOOST_UBLAS_INLINE
1812	const_iterator ():
1813	container_const_reference<self_type> (), it_ () {}
1814	BOOST_UBLAS_INLINE
1815	const_iterator (const self_type &v, const const_subiterator_type &it):
1816	container_const_reference<self_type> (v), it_ (it) {}
1817	BOOST_UBLAS_INLINE
1818	const_iterator (const typename self_type::iterator &it): // ISSUE self_type:: stops VC8 using std::iterator here
1819	container_const_reference<self_type> (it ()), it_ (it.it_) {}
1820
1821	// Arithmetic
1822	BOOST_UBLAS_INLINE
1823	const_iterator &operator ++ () {
1824	++ it_;
1825	return *this;
1826	}
1827	BOOST_UBLAS_INLINE
1828	const_iterator &operator -- () {
1829	-- it_;
1830	return *this;
1831	}
1832
1833	// Dereference
1834	BOOST_UBLAS_INLINE
1835	const_reference operator * () const {
1836	BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
1837	return (this) ().value_data_ [it_ - (this) ().index_data_.begin ()];
1838	}
1839
1840	// Index
1841	BOOST_UBLAS_INLINE
1842	size_type index () const {
1843	BOOST_UBLAS_CHECK (this != (this) ().end (), bad_index ());
1844	BOOST_UBLAS_CHECK ((this) ().zero_based (it_) < (*this) ().size (), bad_index ());
1845	return (this) ().zero_based (it_);
1846	}
1847
1848	// Assignment
1849	BOOST_UBLAS_INLINE
1850	const_iterator &operator = (const const_iterator &it) {
1851	container_const_reference<self_type>::assign (&it ());
1852	it_ = it.it_;
1853	return *this;
1854	}
1855
1856	// Comparison
1857	BOOST_UBLAS_INLINE
1858	bool operator == (const const_iterator &it) const {
1859	BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
1860	return it_ == it.it_;
1861	}
1862
1863	private:
1864	const_subiterator_type it_;
1865	};
1866
1867	BOOST_UBLAS_INLINE
1868	const_iterator begin () const {
1869	return find (0);
1870	}
1871	BOOST_UBLAS_INLINE
1872	const_iterator end () const {
1873	return find (size_);
1874	}
1875
1876	class iterator:
1877	public container_reference<coordinate_vector>,
1878	public bidirectional_iterator_base<sparse_bidirectional_iterator_tag,
1879	iterator, value_type> {
1880	public:
1881	typedef typename coordinate_vector::value_type value_type;
1882	typedef typename coordinate_vector::difference_type difference_type;
1883	typedef typename coordinate_vector::true_reference reference;
1884	typedef typename coordinate_vector::pointer pointer;
1885
1886	// Construction and destruction
1887	BOOST_UBLAS_INLINE
1888	iterator ():
1889	container_reference<self_type> (), it_ () {}
1890	BOOST_UBLAS_INLINE
1891	iterator (self_type &v, const subiterator_type &it):
1892	container_reference<self_type> (v), it_ (it) {}
1893
1894	// Arithmetic
1895	BOOST_UBLAS_INLINE
1896	iterator &operator ++ () {
1897	++ it_;
1898	return *this;
1899	}
1900	BOOST_UBLAS_INLINE
1901	iterator &operator -- () {
1902	-- it_;
1903	return *this;
1904	}
1905
1906	// Dereference
1907	BOOST_UBLAS_INLINE
1908	reference operator * () const {
1909	BOOST_UBLAS_CHECK (index () < (*this) ().size (), bad_index ());
1910	return (this) ().value_data_ [it_ - (this) ().index_data_.begin ()];
1911	}
1912
1913	// Index
1914	BOOST_UBLAS_INLINE
1915	size_type index () const {
1916	BOOST_UBLAS_CHECK (this != (this) ().end (), bad_index ());
1917	BOOST_UBLAS_CHECK ((this) ().zero_based (it_) < (*this) ().size (), bad_index ());
1918	return (this) ().zero_based (it_);
1919	}
1920
1921	// Assignment
1922	BOOST_UBLAS_INLINE
1923	iterator &operator = (const iterator &it) {
1924	container_reference<self_type>::assign (&it ());
1925	it_ = it.it_;
1926	return *this;
1927	}
1928
1929	// Comparison
1930	BOOST_UBLAS_INLINE
1931	bool operator == (const iterator &it) const {
1932	BOOST_UBLAS_CHECK (&(*this) () == &it (), external_logic ());
1933	return it_ == it.it_;
1934	}
1935
1936	private:
1937	subiterator_type it_;
1938
1939	friend class const_iterator;
1940	};
1941
1942	BOOST_UBLAS_INLINE
1943	iterator begin () {
1944	return find (0);
1945	}
1946	BOOST_UBLAS_INLINE
1947	iterator end () {
1948	return find (size_);
1949	}
1950
1951	// Reverse iterator
1952	typedef reverse_iterator_base<const_iterator> const_reverse_iterator;
1953	typedef reverse_iterator_base<iterator> reverse_iterator;
1954
1955	BOOST_UBLAS_INLINE
1956	const_reverse_iterator rbegin () const {
1957	return const_reverse_iterator (end ());
1958	}
1959	BOOST_UBLAS_INLINE
1960	const_reverse_iterator rend () const {
1961	return const_reverse_iterator (begin ());
1962	}
1963	BOOST_UBLAS_INLINE
1964	reverse_iterator rbegin () {
1965	return reverse_iterator (end ());
1966	}
1967	BOOST_UBLAS_INLINE
1968	reverse_iterator rend () {
1969	return reverse_iterator (begin ());
1970	}
1971
1972	private:
1973	void storage_invariants () const
1974	{
1975	BOOST_UBLAS_CHECK (capacity_ == index_data_.size (), internal_logic ());
1976	BOOST_UBLAS_CHECK (capacity_ == value_data_.size (), internal_logic ());
1977	BOOST_UBLAS_CHECK (filled_ <= capacity_, internal_logic ());
1978	BOOST_UBLAS_CHECK (sorted_filled_ <= filled_, internal_logic ());
1979	BOOST_UBLAS_CHECK (sorted_ == (sorted_filled_ == filled_), internal_logic ());
1980	}
1981
1982	size_type size_;
1983	size_type capacity_;
1984	mutable typename index_array_type::size_type filled_;
1985	mutable typename index_array_type::size_type sorted_filled_;
1986	mutable bool sorted_;
1987	mutable index_array_type index_data_;
1988	mutable value_array_type value_data_;
1989	static const value_type zero_;
1990
1991	BOOST_UBLAS_INLINE
1992	static size_type zero_based (size_type k_based_index) {
1993	return k_based_index - IB;
1994	}
1995	BOOST_UBLAS_INLINE
1996	static size_type k_based (size_type zero_based_index) {
1997	return zero_based_index + IB;
1998	}
1999
2000	friend class iterator;
2001	friend class const_iterator;
2002	};
2003
2004	template<class T, std::size_t IB, class IA, class TA>
2005	const typename coordinate_vector<T, IB, IA, TA>::value_type coordinate_vector<T, IB, IA, TA>::zero_ = value_type/zero/();
2006
2007	}}}
2008
2009	#endif

Note: See TracBrowser for help on using the repository browser.

Download in other formats: