]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
26 | namespace 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 | |
7c673cae | 198 | template<class I, class T, class ALLOC> |
92f5a8d4 | 199 | class map_std : public std::map<I, T, std::less<I>, ALLOC> { |
7c673cae FG |
200 | public: |
201 | // Serialization | |
202 | template<class Archive> | |
203 | void serialize(Archive & ar, const unsigned int /* file_version */){ | |
92f5a8d4 | 204 | ar & serialization::make_nvp("base", boost::serialization::base_object< std::map<I, T, std::less<I>, ALLOC> >(*this)); |
7c673cae FG |
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 (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 () + 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 () + 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. | |
92f5a8d4 | 400 | iterator insert (iterator /*hint*/, const value_type &p) { |
7c673cae FG |
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 () - 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 () - (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 (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("size",s); | |
511 | if (Archive::is_loading::value) { | |
512 | resize(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 |