Planet

navi

home

PPS

about

screenshots

download

development

forum

Context Navigation

source: downloads/boost_1_33_1/boost/numeric/ublas/vector_sparse.hpp @ 20

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

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

Download in other formats: