1//
2// Copyright (c) 2000-2002
3// Joerg Walter, Mathias Koch
4//
5// Distributed under the Boost Software License, Version 1.0. (See
6// accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9// The authors gratefully acknowledge the support of
10// GeNeSys mbH & Co. KG in producing this work.
11//
12
13#ifndef _BOOST_UBLAS_STORAGE_SPARSE_
14#define _BOOST_UBLAS_STORAGE_SPARSE_
15
16#include <map>
17#include <boost/serialization/collection_size_type.hpp>
18#include <boost/serialization/nvp.hpp>
19#include <boost/serialization/array.hpp>
20#include <boost/serialization/map.hpp>
21#include <boost/serialization/base_object.hpp>
22
23#include <boost/numeric/ublas/storage.hpp>
24
25
26namespace boost { namespace numeric { namespace ublas {
27
28 namespace detail {
29
30 template<class I, class T, class C>
31 BOOST_UBLAS_INLINE
32 I lower_bound (const I &begin, const I &end, const T &t, C compare) {
33 // t <= *begin <=> ! (*begin < t)
34 if (begin == end || ! compare (*begin, t))
35 return begin;
36 if (compare (*(end - 1), t))
37 return end;
38 return std::lower_bound (begin, end, t, compare);
39 }
40 template<class I, class T, class C>
41 BOOST_UBLAS_INLINE
42 I upper_bound (const I &begin, const I &end, const T &t, C compare) {
43 if (begin == end || compare (t, *begin))
44 return begin;
45 // (*end - 1) <= t <=> ! (t < *end)
46 if (! compare (t, *(end - 1)))
47 return end;
48 return std::upper_bound (begin, end, t, compare);
49 }
50
51 template<class P>
52 struct less_pair {
53 BOOST_UBLAS_INLINE
54 bool operator () (const P &p1, const P &p2) {
55 return p1.first < p2.first;
56 }
57 };
58 template<class T>
59 struct less_triple {
60 BOOST_UBLAS_INLINE
61 bool operator () (const T &t1, const T &t2) {
62 return t1.first.first < t2.first.first ||
63 (t1.first.first == t2.first.first && t1.first.second < t2.first.second);
64 }
65 };
66
67 }
68
69#ifdef BOOST_UBLAS_STRICT_MAP_ARRAY
70 template<class A>
71 class sparse_storage_element:
72 public container_reference<A> {
73 public:
74 typedef A array_type;
75 typedef typename A::key_type index_type;
76 typedef typename A::mapped_type data_value_type;
77 // typedef const data_value_type &data_const_reference;
78 typedef typename type_traits<data_value_type>::const_reference data_const_reference;
79 typedef data_value_type &data_reference;
80 typedef typename A::value_type value_type;
81 typedef value_type *pointer;
82
83 // Construction and destruction
84 BOOST_UBLAS_INLINE
85 sparse_storage_element (array_type &a, pointer it):
86 container_reference<array_type> (a), it_ (it), i_ (it->first), d_ (it->second), dirty_ (false) {}
87 BOOST_UBLAS_INLINE
88 sparse_storage_element (array_type &a, index_type i):
89 container_reference<array_type> (a), it_ (), i_ (i), d_ (), dirty_ (false) {
90 pointer it = (*this) ().find (i_);
91 if (it == (*this) ().end ())
92 it = (*this) ().insert ((*this) ().end (), value_type (i_, d_));
93 d_ = it->second;
94 }
95 BOOST_UBLAS_INLINE
96 ~sparse_storage_element () {
97 if (dirty_) {
98 if (! it_)
99 it_ = (*this) ().find (i_);
100 BOOST_UBLAS_CHECK (it_ != (*this) ().end (), internal_logic ());
101 it_->second = d_;
102 }
103 }
104
105 // Element access - only if data_const_reference is defined
106 BOOST_UBLAS_INLINE
107 typename data_value_type::data_const_reference
108 operator [] (index_type i) const {
109 return d_ [i];
110 }
111
112 // Assignment
113 BOOST_UBLAS_INLINE
114 sparse_storage_element &operator = (const sparse_storage_element &p) {
115 // Overide the implict copy assignment
116 d_ = p.d_;
117 dirty_ = true;
118 return *this;
119 }
120 template<class D>
121 BOOST_UBLAS_INLINE
122 sparse_storage_element &operator = (const D &d) {
123 d_ = d;
124 dirty_ = true;
125 return *this;
126 }
127 template<class D>
128 BOOST_UBLAS_INLINE
129 sparse_storage_element &operator += (const D &d) {
130 d_ += d;
131 dirty_ = true;
132 return *this;
133 }
134 template<class D>
135 BOOST_UBLAS_INLINE
136 sparse_storage_element &operator -= (const D &d) {
137 d_ -= d;
138 dirty_ = true;
139 return *this;
140 }
141 template<class D>
142 BOOST_UBLAS_INLINE
143 sparse_storage_element &operator *= (const D &d) {
144 d_ *= d;
145 dirty_ = true;
146 return *this;
147 }
148 template<class D>
149 BOOST_UBLAS_INLINE
150 sparse_storage_element &operator /= (const D &d) {
151 d_ /= d;
152 dirty_ = true;
153 return *this;
154 }
155
156 // Comparison
157 template<class D>
158 BOOST_UBLAS_INLINE
159 bool operator == (const D &d) const {
160 return d_ == d;
161 }
162 template<class D>
163 BOOST_UBLAS_INLINE
164 bool operator != (const D &d) const {
165 return d_ != d;
166 }
167
168 // Conversion
169 BOOST_UBLAS_INLINE
170 operator data_const_reference () const {
171 return d_;
172 }
173
174 // Swapping
175 BOOST_UBLAS_INLINE
176 void swap (sparse_storage_element p) {
177 if (this != &p) {
178 dirty_ = true;
179 p.dirty_ = true;
180 std::swap (d_, p.d_);
181 }
182 }
183 BOOST_UBLAS_INLINE
184 friend void swap (sparse_storage_element p1, sparse_storage_element p2) {
185 p1.swap (p2);
186 }
187
188 private:
189 pointer it_;
190 index_type i_;
191 data_value_type d_;
192 bool dirty_;
193 };
194#endif
195
196
197 // Default map type is simply forwarded to std::map
198 template<class I, class T, class ALLOC>
199 class map_std : public std::map<I, T, std::less<I>, ALLOC> {
200 public:
201 // Serialization
202 template<class Archive>
203 void serialize(Archive & ar, const unsigned int /* file_version */){
204 ar & serialization::make_nvp("base", boost::serialization::base_object< std::map<I, T, std::less<I>, ALLOC> >(*this));
205 }
206 };
207
208
209
210
211 // Map array
212 // Implementation requires pair<I, T> allocator definition (without const)
213 template<class I, class T, class ALLOC>
214 class map_array {
215 public:
216 typedef ALLOC allocator_type;
217 typedef typename ALLOC::size_type size_type;
218 typedef typename ALLOC::difference_type difference_type;
219 typedef std::pair<I,T> value_type;
220 typedef I key_type;
221 typedef T mapped_type;
222 typedef const value_type &const_reference;
223 typedef value_type &reference;
224 typedef const value_type *const_pointer;
225 typedef value_type *pointer;
226 // Iterators simply are pointers.
227 typedef const_pointer const_iterator;
228 typedef pointer iterator;
229
230 typedef const T &data_const_reference;
231#ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
232 typedef T &data_reference;
233#else
234 typedef sparse_storage_element<map_array> data_reference;
235#endif
236
237 // Construction and destruction
238 BOOST_UBLAS_INLINE
239 map_array (const ALLOC &a = ALLOC()):
240 alloc_(a), capacity_ (0), size_ (0) {
241 data_ = 0;
242 }
243 BOOST_UBLAS_INLINE
244 map_array (const map_array &c):
245 alloc_ (c.alloc_), capacity_ (c.size_), size_ (c.size_) {
246 if (capacity_) {
247 data_ = alloc_.allocate (capacity_);
248 std::uninitialized_copy (data_, data_ + capacity_, c.data_);
249 // capacity != size_ requires uninitialized_fill (size_ to capacity_)
250 }
251 else
252 data_ = 0;
253 }
254 BOOST_UBLAS_INLINE
255 ~map_array () {
256 if (capacity_) {
257 std::for_each (data_, data_ + capacity_, static_destroy);
258 alloc_.deallocate (data_, capacity_);
259 }
260 }
261
262 private:
263 // Resizing - implicitly exposses uninitialized (but default constructed) mapped_type
264 BOOST_UBLAS_INLINE
265 void resize (size_type size) {
266 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
267 if (size > capacity_) {
268 const size_type capacity = size << 1;
269 BOOST_UBLAS_CHECK (capacity, internal_logic ());
270 pointer data = alloc_.allocate (capacity);
271 std::uninitialized_copy (data_, data_ + (std::min) (size, size_), data);
272 std::uninitialized_fill (data + (std::min) (size, size_), data + capacity, value_type ());
273
274 if (capacity_) {
275 std::for_each (data_, data_ + capacity_, static_destroy);
276 alloc_.deallocate (data_, capacity_);
277 }
278 capacity_ = capacity;
279 data_ = data;
280 }
281 size_ = size;
282 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
283 }
284 public:
285
286 // Reserving
287 BOOST_UBLAS_INLINE
288 void reserve (size_type capacity) {
289 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
290 // Reduce capacity_ if size_ allows
291 BOOST_UBLAS_CHECK (capacity >= size_, bad_size ());
292 pointer data;
293 if (capacity) {
294 data = alloc_.allocate (capacity);
295 std::uninitialized_copy (data_, data_ + size_, data);
296 std::uninitialized_fill (data + size_, data + capacity, value_type ());
297 }
298 else
299 data = 0;
300
301 if (capacity_) {
302 std::for_each (data_, data_ + capacity_, static_destroy);
303 alloc_.deallocate (data_, capacity_);
304 }
305 capacity_ = capacity;
306 data_ = data;
307 BOOST_UBLAS_CHECK (size_ <= capacity_, internal_logic ());
308 }
309
310 // Random Access Container
311 BOOST_UBLAS_INLINE
312 size_type size () const {
313 return size_;
314 }
315 BOOST_UBLAS_INLINE
316 size_type capacity () const {
317 return capacity_;
318 }
319 BOOST_UBLAS_INLINE
320 size_type max_size () const {
321 return 0; //TODO
322 }
323
324 BOOST_UBLAS_INLINE
325 bool empty () const {
326 return size_ == 0;
327 }
328
329 // Element access
330 BOOST_UBLAS_INLINE
331 data_reference operator [] (key_type i) {
332#ifndef BOOST_UBLAS_STRICT_MAP_ARRAY
333 pointer it = find (i);
334 if (it == end ())
335 it = insert (end (), value_type (i, mapped_type (0)));
336 BOOST_UBLAS_CHECK (it != end (), internal_logic ());
337 return it->second;
338#else
339 return data_reference (*this, i);
340#endif
341 }
342
343 // Assignment
344 BOOST_UBLAS_INLINE
345 map_array &operator = (const map_array &a) {
346 if (this != &a) {
347 resize (size: a.size_);
348 std::copy (a.data_, a.data_ + a.size_, data_);
349 }
350 return *this;
351 }
352 BOOST_UBLAS_INLINE
353 map_array &assign_temporary (map_array &a) {
354 swap (a);
355 return *this;
356 }
357
358 // Swapping
359 BOOST_UBLAS_INLINE
360 void swap (map_array &a) {
361 if (this != &a) {
362 std::swap (capacity_, a.capacity_);
363 std::swap (data_, a.data_);
364 std::swap (size_, a.size_);
365 }
366 }
367 BOOST_UBLAS_INLINE
368 friend void swap (map_array &a1, map_array &a2) {
369 a1.swap (a2);
370 }
371
372 // Element insertion and deletion
373
374 // From Back Insertion Sequence concept
375 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
376 iterator push_back (iterator it, const value_type &p) {
377 if (size () == 0 || (it = end () - 1)->first < p.first) {
378 resize (size: size () + 1);
379 *(it = end () - 1) = p;
380 return it;
381 }
382 external_logic ().raise ();
383 return it;
384 }
385 // Form Unique Associative Container concept
386 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
387 std::pair<iterator,bool> insert (const value_type &p) {
388 iterator it = detail::lower_bound (begin (), end (), p, detail::less_pair<value_type> ());
389 if (it != end () && it->first == p.first)
390 return std::make_pair (it, false);
391 difference_type n = it - begin ();
392 resize (size: size () + 1);
393 it = begin () + n; // allow for invalidation
394 std::copy_backward (it, end () - 1, end ());
395 *it = p;
396 return std::make_pair (it, true);
397 }
398 // Form Sorted Associative Container concept
399 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
400 iterator insert (iterator /*hint*/, const value_type &p) {
401 return insert (p).first;
402 }
403 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
404 void erase (iterator it) {
405 BOOST_UBLAS_CHECK (begin () <= it && it < end (), bad_index ());
406 std::copy (it + 1, end (), it);
407 resize (size: size () - 1);
408 }
409 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
410 void erase (iterator it1, iterator it2) {
411 if (it1 == it2) return /* nothing to erase */;
412 BOOST_UBLAS_CHECK (begin () <= it1 && it1 < it2 && it2 <= end (), bad_index ());
413 std::copy (it2, end (), it1);
414 resize (size: size () - (it2 - it1));
415 }
416 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
417 void clear () {
418 resize (size: 0);
419 }
420
421 // Element lookup
422 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
423 const_iterator find (key_type i) const {
424 const_iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
425 if (it == end () || it->first != i)
426 it = end ();
427 return it;
428 }
429 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
430 iterator find (key_type i) {
431 iterator it (detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ()));
432 if (it == end () || it->first != i)
433 it = end ();
434 return it;
435 }
436 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
437 const_iterator lower_bound (key_type i) const {
438 return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
439 }
440 // BOOST_UBLAS_INLINE This function seems to be big. So we do not let the compiler inline it.
441 iterator lower_bound (key_type i) {
442 return detail::lower_bound (begin (), end (), value_type (i, mapped_type (0)), detail::less_pair<value_type> ());
443 }
444
445 BOOST_UBLAS_INLINE
446 const_iterator begin () const {
447 return data_;
448 }
449 BOOST_UBLAS_INLINE
450 const_iterator cbegin () const {
451 return begin ();
452 }
453 BOOST_UBLAS_INLINE
454 const_iterator end () const {
455 return data_ + size_;
456 }
457 BOOST_UBLAS_INLINE
458 const_iterator cend () const {
459 return end ();
460 }
461
462 BOOST_UBLAS_INLINE
463 iterator begin () {
464 return data_;
465 }
466 BOOST_UBLAS_INLINE
467 iterator end () {
468 return data_ + size_;
469 }
470
471 // Reverse iterators
472 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
473 typedef std::reverse_iterator<iterator> reverse_iterator;
474
475 BOOST_UBLAS_INLINE
476 const_reverse_iterator rbegin () const {
477 return const_reverse_iterator (end ());
478 }
479 BOOST_UBLAS_INLINE
480 const_reverse_iterator crbegin () const {
481 return rbegin ();
482 }
483 BOOST_UBLAS_INLINE
484 const_reverse_iterator rend () const {
485 return const_reverse_iterator (begin ());
486 }
487 BOOST_UBLAS_INLINE
488 const_reverse_iterator crend () const {
489 return rend ();
490 }
491
492 BOOST_UBLAS_INLINE
493 reverse_iterator rbegin () {
494 return reverse_iterator (end ());
495 }
496 BOOST_UBLAS_INLINE
497 reverse_iterator rend () {
498 return reverse_iterator (begin ());
499 }
500
501 // Allocator
502 allocator_type get_allocator () {
503 return alloc_;
504 }
505
506 // Serialization
507 template<class Archive>
508 void serialize(Archive & ar, const unsigned int /* file_version */){
509 serialization::collection_size_type s (size_);
510 ar & serialization::make_nvp(n: "size",v&: s);
511 if (Archive::is_loading::value) {
512 resize(size: s);
513 }
514 ar & serialization::make_array(data_, s);
515 }
516
517 private:
518 // Provide destroy as a non member function
519 BOOST_UBLAS_INLINE
520 static void static_destroy (reference p) {
521 (&p) -> ~value_type ();
522 }
523 ALLOC alloc_;
524 size_type capacity_;
525 pointer data_;
526 size_type size_;
527 };
528
529
530 namespace detail {
531 template<class A, class T>
532 struct map_traits {
533 typedef typename A::mapped_type &reference;
534 };
535 template<class I, class T, class ALLOC>
536 struct map_traits<map_array<I, T, ALLOC>, T > {
537 typedef typename map_array<I, T, ALLOC>::data_reference reference;
538 };
539
540 // reserve helpers for map_array and generic maps
541 // ISSUE should be in map_traits but want to use on all compilers
542
543 template<class M>
544 BOOST_UBLAS_INLINE
545 void map_reserve (M &/* m */, typename M::size_type /* capacity */) {
546 }
547 template<class I, class T, class ALLOC>
548 BOOST_UBLAS_INLINE
549 void map_reserve (map_array<I, T, ALLOC> &m, typename map_array<I, T, ALLOC>::size_type capacity) {
550 m.reserve (capacity);
551 }
552
553 template<class M>
554 struct map_capacity_traits {
555 typedef typename M::size_type type ;
556 type operator() ( M const& m ) const {
557 return m.size ();
558 }
559 } ;
560
561 template<class I, class T, class ALLOC>
562 struct map_capacity_traits< map_array<I, T, ALLOC> > {
563 typedef typename map_array<I, T, ALLOC>::size_type type ;
564 type operator() ( map_array<I, T, ALLOC> const& m ) const {
565 return m.capacity ();
566 }
567 } ;
568
569 template<class M>
570 BOOST_UBLAS_INLINE
571 typename map_capacity_traits<M>::type map_capacity (M const& m) {
572 return map_capacity_traits<M>() ( m );
573 }
574 }
575
576}}}
577
578#endif
579

source code of include/boost/numeric/ublas/storage_sparse.hpp