?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
remove \r
[extl.git] / extl / container / sparse_matrix_base.h
blob8ee2a84ac5a8a99e22ea89a3d9923eaf6a6331dc
1 /* ///////////////////////////////////////////////////////////////////////
2 * File: sparse_matrix_base.h
3 *
4 * Created: 08.12.07
5 * Updated: 08.12.08
6 *
7 * Brief: sparse_matrix_base class - fixed-size
8 *
9 * [<Home>]
10 * Copyright (c) 2008-2020, Waruqi All rights reserved.
11 * //////////////////////////////////////////////////////////////////// */
12
13 #ifndef EXTL_CONTAINER_SPARSE_MATRIX_BASE_H
14 #define EXTL_CONTAINER_SPARSE_MATRIX_BASE_H
15
16 /*!\file sparse_matrix_base.h
17 * \brief sparse_matrix_base class
18 */
19
20 /* ///////////////////////////////////////////////////////////////////////
21 * Includes
22 */
23 #include "prefix.h"
24 #include "../memory/buffer.h"
25 #include "../algorithm/algorithm.h"
26 #include "list.h"
27 #include "detail/sparse_matrix_rowe_iterator.h"
28 #include "detail/sparse_matrix_cole_iterator.h"
29 /* ///////////////////////////////////////////////////////////////////////
30 * ::extl namespace
31 */
32 EXTL_BEGIN_NAMESPACE
33
34 /*!brief sparse_matrix_base
35 *
36 * <pre>
37 * (empty node: point to self)
38 * --- --- --- --- -- --
39 * (dim1) | | | | | | | | | | | |
40 * cheads: [0] | [1] | [2] | [3] | |->[4]<-|
41 * rheads | | | | | | | | | | | |
42 * (dim0) | | | | | | | | '--' '--'
43 * [0] --------------------|->(val)--|- | | | |
44 * | `--------------------|--'| | | | | | | |
45 * '----------------------|---|-|---|-' | | | |
46 * | | | | | | | |
47 * | | | | | | | |
48 * [1] | | | | | | | |
49 * | | | | | | | |
50 * | | | | | | | |
51 * | | | | | | | |
52 * | | | | | | | |
53 * [2] --------------------|->(val)--|-------------|->(val)--|-
54 * | `--------------------|--'| |`--|-------------|--'| | | |
55 * | '---' '---' '---' '---' |
56 * '----------------------------------------------------------'
57 *
58 * </pre>
59 *
60 * \param Dev The derived type
61 * \param Val The value type
62 *
63 * \ingroup extl_group_container
64 */
65 template< typename_param_k Dev
66 , typename_param_k Val
67 >
68 class sparse_matrix_base
69 {
70 /// \name Types
71 /// @{
72 public:
73 typedef sparse_matrix_base class_type;
74 typedef Dev derived_type;
75 typedef Val value_type;
76 typedef Val* pointer;
77 typedef Val const* const_pointer;
78 typedef Val& reference;
79 typedef Val const& const_reference;
80 typedef e_size_t size_type;
81 typedef e_bool_t bool_type;
82 typedef e_ptrdiff_t difference_type;
83 typedef e_int_t int_type;
84 typedef size_type index_type;
85 typedef typename_type_k list_selector<value_type>::list_type list_type;
86 typedef typename_type_k list_type::allocator_type allocator_type;
87 typedef typename_type_k list_type::iterator iterator;
88 typedef typename_type_k list_type::const_iterator const_iterator;
89 typedef typename_type_k list_type::reverse_iterator reverse_iterator;
90 typedef typename_type_k list_type::const_reverse_iterator const_reverse_iterator;
91 class const_reduced_dimension_type
92 {
93 private:
94 derived_type const* m_this;
95 index_type m_i;
96 size_type m_dim;
97
98 public:
99 const_reduced_dimension_type(derived_type const* p, index_type i)
100 : m_this(p)
101 , m_i(i)
102 {}
103 public:
104 const_reference operator[](index_type j) const
105 {
106 return at_unchecked(j);
107 }
108 #if EXTL_WORKAROUND_DMC(<, 0x0850)
109 const_reference at(index_type j) const
110 {
111 return static_cast<class_type const*>(m_this)->at(m_i, j);
112 }
113 const_reference at_unchecked(index_type j) const
114 {
115 return static_cast<class_type const*>(m_this)->at_unchecked(m_i, j);
116 }
117 #else
118 const_reference at(index_type j) const
119 {
120 return m_this->at(m_i, j);
121 }
122 const_reference at_unchecked(index_type j) const
123 {
124 return m_this->at_unchecked(m_i, j);
125 }
126 #endif
127 };
128 class reduced_dimension_type
129 {
130 private:
131 derived_type const* m_this;
132 index_type m_i;
133 size_type m_dim;
134
135 public:
136 reduced_dimension_type(derived_type const* p, index_type i)
137 : m_this(p)
138 , m_i(i)
139 {}
140 public:
141 reference operator[](index_type j)
142 {
143 return at_unchecked(j);
144 }
145 #if EXTL_WORKAROUND_DMC(<, 0x0850)
146 reference at(index_type j)
147 {
148 return const_cast<reference>(static_cast<class_type const*>(m_this)->at(m_i, j));
149 }
150 reference at_unchecked(index_type j)
151 {
152 return const_cast<reference>(static_cast<class_type const*>(m_this)->at_unchecked(m_i, j));
153 }
154 #else
155 reference at(index_type j)
156 {
157 return const_cast<reference>(m_this->at(m_i, j));
158 }
159 reference at_unchecked(index_type j)
160 {
161 return const_cast<reference>(m_this->at_unchecked(m_i, j));
162 }
163 #endif
164 };
165 /// @}
166
167 /// \name Protected Types
168 /// @{
169 protected:
170 /// node_type
171 struct node_type
172 {
173 /// \name Members
174 /// @{
175 private:
176 index_type m_i0; //!< row
177 index_type m_i1; //!< col
178
179 node_type const* m_top;
180 node_type const* m_bottom;
181 node_type const* m_left;
182 node_type const* m_right;
183
184 const_iterator m_pos;
185 /// @}
186
187 /// \name Attributes
188 /// @{
189 public:
190 index_type row() const { return m_i0; }
191 void row(index_type i0) { m_i0 = i0; }
192
193 index_type col() const { return m_i1; }
194 void col(index_type i1) { m_i1 = i1; }
195
196 iterator pos() { return iterator(m_pos); }
197 const_iterator pos() const { return m_pos; }
198 void pos(const_iterator p) { m_pos = p; }
199
200 const_reference value() const { return *(pos()); }
201 reference value() { return *(pos()); }
202 void value(const_reference v) { *(pos()) = v; }
203
204 node_type const* top() const { return m_top; }
205 node_type* top() { return const_cast<node_type*>(m_top); }
206 void top(node_type const* node) { m_top = node; }
207
208 node_type const* bottom() const { return m_bottom; }
209 node_type* bottom() { return const_cast<node_type*>(m_bottom); }
210 void bottom(node_type const* node) { m_bottom = node; }
211
212 node_type const* left() const { return m_left; }
213 node_type* left() { return const_cast<node_type*>(m_left); }
214 void left(node_type const* node) { m_left = node; }
215
216 node_type const* right() const { return m_right; }
217 node_type* right() { return const_cast<node_type*>(m_right); }
218 void right(node_type const* node) { m_right = node; }
219
220 bool_type is_empty() const { return (top() == this) && (bottom() == this) && (left() == this) && (right() == this); }
221 /// @}
222
223 /// \name Mutators
224 /// @{
225 public:
226 void init() { clear(); }
227 void clear()
228 {
229 m_i0 = 0;
230 m_i1 = 0;
231
232 /*!point to self:
233 * <pre>
234 * self-reference:
235 * --------
236 * | |
237 * ----------- -
238 * | top |
239 * ----------------------------
240 * --| left value right |---
241 * | ---------------------------- |
242 * | | | bottom | | |
243 * ---- -- ---------- ----
244 * | |
245 * -------
246 *
247 * </pre>
248 */
249 m_top = this;
250 m_bottom = this;
251 m_left = this;
252 m_right = this;
253
254 m_pos = const_iterator();
255 }
256 /// @}
257
258 };
259 typedef node_type* node_pointer;
260 typedef node_type const* const_node_pointer;
261 typedef node_type& node_reference;
262 typedef node_type const& const_node_reference;
263 typedef typename_type_k buffer_selector<node_type>::buffer_type buffer_type;
264 typedef typename_type_k buffer_type::allocator_type node_allocator_type;
265 typedef buffer_type rheads_type;
266 typedef buffer_type cheads_type;
267 /// @}
268
269 /// \name Iterator Types
270 /// \note cannot insert and erase nodes in the iteration
271 /// @{
272 public:
273 // row element iterator
274 typedef EXTL_NS_DETAIL(sparse_matrix_rowe_iterator)<value_type, node_type> rowe_iterator;
275 typedef EXTL_NS_DETAIL(const_sparse_matrix_rowe_iterator)<value_type, node_type> const_rowe_iterator;
276 typedef reverse_bidirectional_iterator_base<const_rowe_iterator> rowe_reverse_iterator;
277 typedef const_reverse_bidirectional_iterator_base<const_rowe_iterator> const_rowe_reverse_iterator;
278
279 // column element iterator
280 typedef EXTL_NS_DETAIL(sparse_matrix_cole_iterator)<value_type, node_type> cole_iterator;
281 typedef EXTL_NS_DETAIL(const_sparse_matrix_cole_iterator)<value_type, node_type> const_cole_iterator;
282 typedef reverse_bidirectional_iterator_base<const_cole_iterator> cole_reverse_iterator;
283 typedef const_reverse_bidirectional_iterator_base<const_cole_iterator> const_cole_reverse_iterator;
284 /// @}
285
286 public:
287 /// The dimension of the matrix
288 EXTL_STATIC_MEMBER_CONST(size_type, dimension = 2);
289
290 /// \name Members
291 /// @{
292 private:
293 list_type m_nodes; //!< nodes list
294 rheads_type m_rheads; //!< row heads
295 cheads_type m_cheads; //!< col heads
296 /// @}
297
298 private:
299 /*!\brief Prohibit the following case:
300 *
301 * \code
302 Dev da, db;
303 B &ba = da, &bb = db;
304 ba = bb;
305 B b(ba);
306 * \endcode
307 */
308 sparse_matrix_base(class_type const&);
309 class_type& operator=(class_type const&);
310
311 /// \name Constructors
312 /// @{
313 public:
314 sparse_matrix_base()
315 : m_nodes()
316 , m_rheads()
317 , m_cheads()
318 {
319 derive().init();
320 EXTL_ASSERT(derive().is_valid());
321 }
322 explicit_k sparse_matrix_base(derived_type const& rhs)
323 : m_nodes()
324 , m_rheads()
325 , m_cheads()
326 {
327 EXTL_ASSERT(rhs.is_valid());
328 derive().assign(rhs);
329 EXTL_ASSERT(derive().is_valid());
330 }
331 // d0 * d1
332 sparse_matrix_base(index_type d0, index_type d1)
333 : m_nodes()
334 , m_rheads(d0)
335 , m_cheads(d1)
336 {
337 derive().init();
338 EXTL_ASSERT(derive().is_valid());
339 }
340 ~sparse_matrix_base()
341 {
342 destroy();
343 }
344 /// @}
345
346
347 /// \name Attributes
348 /// @{
349 public:
350 allocator_type allocator() const { return nodes().allocator(); }
351 size_type dim0() const { return cheads().size(); }
352 size_type dim1() const { return rheads().size(); }
353 size_type row() const { return derive().dim0(); }
354 size_type col() const { return derive().dim1(); }
355 size_type size() const { return dim0() * dim1(); }
356 size_type nodes_size() const { return nodes().size(); }
357 bool_type is_empty() const { return nodes().is_empty(); }
358 bool_type empty() const { return nodes().is_empty(); }
359 size_type max_size() { return dim0() * dim1(); }
360 bool_type exists(index_type i0, index_type i1) const;
361 bool_type is_valid() const;
362 /// @}
363
364 /// \name Mutators
365 /// @{
366 public:
367 /// swap *this & rhs
368 void swap(derived_type& rhs);
369 /// clear *this
370 void clear();
371
372 /// insert an element
373 const_reference insert(index_type i0, index_type i1, const_reference value, bool_type* has_existed = NULL);
374 /// erase an element
375 void erase(index_type i0, index_type i1, bool_type* has_existed = NULL);
376
377 /// erase the whole row
378 /// \note non-exception-safe, please use it carefully
379 size_type erase_row(index_type i0);
380 /// erase the whole column
381 /// \note non-exception-safe, please use it carefully
382 size_type erase_col(index_type i1);
383
384 /// assigment
385 /// \note non-exception-safe, please use it carefully
386 derived_type& assign(derived_type const& rhs);
387 /// assigment
388 derived_type& operator =(derived_type const& rhs);
389 /// assigment
390 derived_type& operator =(const_reference value);
391 /// @}
392
393 /// \name Accessors
394 /// @{
395 public:
396 // note: insert an empty node if not exists
397 reference at(index_type i0, index_type i1);
398 const_reference at(index_type i0, index_type i1) const;
399
400 reference at_unchecked(index_type i0, index_type i1);
401 const_reference at_unchecked(index_type i0, index_type i1) const;
402
403 reduced_dimension_type at(index_type i0);
404 const_reduced_dimension_type at(index_type i0) const;
405
406 reduced_dimension_type at_unchecked(index_type i0);
407 const_reduced_dimension_type at_unchecked(index_type i0) const;
408
409 reduced_dimension_type operator[](index_type i0) { return at_unchecked(i0); }
410 const_reduced_dimension_type operator[](index_type i0) const { return at_unchecked(i0); }
411
412 bool_type get_if_exists(index_type i0, index_type i1, reference ret) const;
413 bool_type set_if_exists(index_type i0, index_type i1, const_reference val);
414 /// @}
415
416 /// \name Iterators
417 /// @{
418 public:
419 const_iterator begin() const { return nodes().begin(); }
420 iterator begin() { return nodes().begin(); }
421
422 const_iterator end() const { return nodes().end(); }
423 iterator end() { return nodes().end(); }
424
425 const_reverse_iterator rbegin() const { return nodes().rbegin(); }
426 reverse_iterator rbegin() { return nodes().rbegin(); }
427
428 const_reverse_iterator rend() const { return nodes().rend(); }
429 reverse_iterator rend() { return nodes().rend(); }
430 /// @}
431
432 /// \name Row Element Iterators
433 /// \note cannot insert and erase nodes in the iteration
434 /// @{
435 public:
436 const_rowe_iterator rowe_begin(index_type i0) const { return const_rowe_iterator(rheads()[i0].right()); }
437 rowe_iterator rowe_begin(index_type i0) { return rowe_iterator(rheads()[i0].right()); }
438
439 const_rowe_iterator rowe_end(index_type i0) const { return const_rowe_iterator(&(rheads()[i0])); }
440 rowe_iterator rowe_end(index_type i0) { return rowe_iterator(&(rheads()[i0])); }
441
442 const_rowe_reverse_iterator rowe_rbegin(index_type i0) const { return const_rowe_reverse_iterator(rowe_end(i0)); }
443 rowe_reverse_iterator rowe_rbegin(index_type i0) { return rowe_reverse_iterator(rowe_end(i0)); }
444
445 const_rowe_reverse_iterator rowe_rend(index_type i0) const { return const_rowe_reverse_iterator(rowe_begin(i0)); }
446 rowe_reverse_iterator rowe_rend(index_type i0) { return rowe_reverse_iterator(rowe_begin(i0)); }
447 /// @}
448
449 /// \name Column Element Iterators
450 /// \note cannot insert and erase nodes in the iteration
451 /// @{
452 public:
453 const_cole_iterator cole_begin(index_type i1) const { return const_cole_iterator(cheads()[i1].bottom()); }
454 cole_iterator cole_begin(index_type i1) { return cole_iterator(cheads()[i1].bottom()); }
455
456 const_cole_iterator cole_end(index_type i1) const { return const_cole_iterator(&(cheads()[i1])); }
457 cole_iterator cole_end(index_type i1) { return cole_iterator(&(cheads()[i1])); }
458
459 const_cole_reverse_iterator cole_rbegin(index_type i1) const { return const_cole_reverse_iterator(cole_end(i1)); }
460 cole_reverse_iterator cole_rbegin(index_type i1) { return cole_reverse_iterator(cole_end(i1)); }
461
462 const_cole_reverse_iterator cole_rend(index_type i1) const { return const_cole_reverse_iterator(cole_begin(i1)); }
463 cole_reverse_iterator cole_rend(index_type i1) { return cole_reverse_iterator(cole_begin(i1)); }
464 /// @}
465
466 /// \name Others
467 /// @{
468 protected:
469 derived_type& derive() { return static_cast<derived_type&>(*this); }
470 derived_type const& derive() const { return static_cast<derived_type const&>(*this); }
471
472 buffer_type& rheads() { return m_rheads; }
473 buffer_type const& rheads() const { return m_rheads; }
474
475 buffer_type& cheads() { return m_cheads; }
476 buffer_type const& cheads() const { return m_cheads; }
477
478 list_type& nodes() { return m_nodes; }
479 list_type const& nodes() const { return m_nodes; }
480
481 node_allocator_type node_allocator() const { return node_allocator_type(); }
482 /// @}
483
484 /// \name Helpers
485 /// @{
486 protected:
487 void init();
488 void destroy();
489
490 node_pointer create_node(index_type i0, index_type i1, const_reference value = value_type());
491 void destroy_node(node_pointer node);
492 void destroy_nodes();
493
494 node_pointer erase_from_row(index_type i0, index_type i1, bool_type* has_existed);
495 node_pointer erase_from_col(index_type i0, index_type i1, bool_type* has_existed);
496
497 void insert_into_row(node_pointer node, bool_type* has_existed);
498 void insert_into_col(node_pointer node, bool_type* has_existed);
499 /// @}
500 };
501 /* Template declaration */
502 #ifdef EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
503 # undef EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
504 #endif
505
506 #define EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL \
507 template< typename_param_k Dev \
508 , typename_param_k Val \
509 >
510
511 /* Class qualification */
512 #ifdef EXTL_SPARSE_MATRIX_BASE_QUAL
513 # undef EXTL_SPARSE_MATRIX_BASE_QUAL
514 #endif
515
516 #define EXTL_SPARSE_MATRIX_BASE_QUAL sparse_matrix_base<Dev, Val>
517
518 /* Class qualification */
519 #ifdef EXTL_SPARSE_MATRIX_BASE_RET_QUAL
520 # undef EXTL_SPARSE_MATRIX_BASE_RET_QUAL
521 #endif
522
523 #define EXTL_SPARSE_MATRIX_BASE_RET_QUAL(ret_type) \
524 typename_type_ret_k EXTL_SPARSE_MATRIX_BASE_QUAL::ret_type \
525 EXTL_SPARSE_MATRIX_BASE_QUAL
526 /* /////////////////////////////////////////////////////////////////////////
527 * Implemention
528 */
529 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
530 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(node_pointer)::create_node(index_type i0, index_type i1, const_reference value)
531 {
532 /// allocate a new node
533 node_pointer node = node_allocator().allocate(1);
534 EXTL_ASSERT(node != NULL);
535 if (NULL == node) return NULL;
536
537 const_iterator pos;
538 EXTL_TRY
539 node->init();
540 node->row(i0);
541 node->col(i1);
542 pos = nodes().insert(nodes().end(), value);
543 node->pos(pos);
544 EXTL_CATCH_ALL
545 nodes().erase(pos);
546 node_allocator().deallocate(node);
547 // reraise
548 EXTL_THROW;
549 EXTL_CATCH_END
550
551 return node;
552
553 }
554 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
555 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::destroy_node(node_pointer node)
556 {
557 EXTL_ASSERT(node != NULL);
558 if (NULL == node) return ;
559 nodes().erase(node->pos());
560 node->clear();
561 node_allocator().deallocate(node);
562 }
563
564 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
565 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::insert_into_row(node_pointer node, bool_type* has_existed)
566 {
567 EXTL_ASSERT(NULL != node);
568 index_type row = node->row();
569 index_type col = node->col();
570
571 // insert node after rheads()[row]
572 if (rheads()[row].is_empty())
573 {
574 rheads()[row].right(node);
575 node->right(&(rheads()[row]));
576 rheads()[row].left(node);
577 node->left(&(rheads()[row]));
578
579 if (NULL != has_existed) *has_existed = e_false_v;
580 return ;
581 }
582
583 // find insertion point
584 node_pointer rp = rheads()[row].right();
585 EXTL_ASSERT(NULL != rp);
586 for (; &(rheads()[row]) != rp && rp->col() < col; rp = rp->right());
587
588 if (rp != &(rheads()[row]))
589 {
590 if (rp->col() != col) // insert node if node not exists
591 {
592 EXTL_ASSERT(rp->col() > col);
593 rp->left()->right(node);
594 node->left(rp->left());
595 rp->left(node);
596 node->right(rp);
597
598 if (NULL != has_existed) *has_existed = e_false_v;
599 }
600 else // update node if node already exists
601 {
602 rp->value(node->value());
603 if (NULL != has_existed) *has_existed = e_true_v;
604 }
605 }
606 else // insert node before rheads()[row], that is at last position
607 {
608 rp->left()->right(node);
609 node->left(rp->left());
610 rp->left(node);
611 node->right(rp);
612
613 if (NULL != has_existed) *has_existed = e_false_v;
614 }
615 }
616 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
617 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(node_pointer)::erase_from_row(index_type i0, index_type i1, bool_type* has_existed)
618 {
619 index_type row = i0;
620 index_type col = i1;
621
622 if (rheads()[row].is_empty())
623 {
624 if (NULL != has_existed) *has_existed = e_false_v;
625 return NULL;
626 }
627
628 // find position
629 node_pointer rp = rheads()[row].right();
630 EXTL_ASSERT(NULL != rp);
631 for (; &(rheads()[row]) != rp && rp->col() < col; rp = rp->right());
632
633 // node not exists
634 if (rp == &(rheads()[row]) || rp->col() != col)
635 {
636 if (NULL != has_existed) *has_existed = e_false_v;
637 return NULL;
638 }
639
640 // erase node
641 rp->left()->right(rp->right());
642 rp->right()->left(rp->left());
643
644 if (NULL != has_existed) *has_existed = e_true_v;
645 return rp;
646 }
647 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
648 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::insert_into_col(node_pointer node, bool_type* has_existed)
649 {
650 EXTL_ASSERT(NULL != node);
651 index_type row = node->row();
652 index_type col = node->col();
653
654 // insert node after cheads()[col]
655 if (cheads()[col].is_empty())
656 {
657 cheads()[col].bottom(node);
658 node->bottom(&(cheads()[col]));
659 cheads()[col].top(node);
660 node->top(&(cheads()[col]));
661 if (NULL != has_existed) *has_existed = e_false_v;
662 return ;
663 }
664
665 // find insertion point
666 node_pointer cp = cheads()[col].bottom();
667 EXTL_ASSERT(NULL != cp);
668 for (; &(cheads()[col]) != cp && cp->row() < row; cp = cp->bottom());
669
670 if (cp != &(cheads()[col]))
671 {
672 if (cp->row() != row) // insert node if node not exists
673 {
674 EXTL_ASSERT(cp->row() > row);
675 cp->top()->bottom(node);
676 node->top(cp->top());
677 cp->top(node);
678 node->bottom(cp);
679 if (NULL != has_existed) *has_existed = e_false_v;
680 }
681 else // update node if node already exists
682 {
683 cp->value(node->value());
684 if (NULL != has_existed) *has_existed = e_true_v;
685 }
686 }
687 else // insert node before cheads()[col], that is at last position
688 {
689 cp->top()->bottom(node);
690 node->top(cp->top());
691 cp->top(node);
692 node->bottom(cp);
693 if (NULL != has_existed) *has_existed = e_false_v;
694 }
695 }
696 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
697 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(node_pointer)::erase_from_col(index_type i0, index_type i1, bool_type* has_existed)
698 {
699 index_type row = i0;
700 index_type col = i1;
701
702 if (cheads()[col].is_empty())
703 {
704 if (NULL != has_existed) *has_existed = e_false_v;
705 return NULL;
706 }
707
708 // find position
709 node_pointer cp = cheads()[col].bottom();
710 EXTL_ASSERT(NULL != cp);
711 for (; &(cheads()[col]) != cp && cp->row() < row; cp = cp->bottom());
712
713 // node not exists
714 if (cp == &(cheads()[col]) || cp->row() != row)
715 {
716 if (NULL != has_existed) *has_existed = e_false_v;
717 return NULL;
718 }
719
720 // erase node
721 cp->top()->bottom(cp->bottom());
722 cp->bottom()->top(cp->top());
723
724 if (NULL != has_existed) *has_existed = e_true_v;
725
726 return cp;
727 }
728 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
729 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(const_reference)::insert(index_type i0, index_type i1, const_reference value, bool_type* has_existed)
730 {
731 EXTL_MESSAGE_ASSERT(i0 < dim0() && i1 < dim1(), "out of range");
732 EXTL_ASSERT(derive().is_valid());
733
734 // create node
735 node_pointer node = create_node(i0, i1, value);
736 EXTL_ASSERT(NULL != node);
737
738 size_type step = 0;
739 EXTL_TRY
740 derive().insert_into_row(node, has_existed);
741 step = 1;
742 derive().insert_into_col(node, has_existed);
743 EXTL_CATCH_ALL
744 switch (step)
745 {
746 case 1:
747 derive().erase_from_row(i0, i1, has_existed);
748 case 0:
749 destroy_node(node);
750 }
751 // reraise
752 EXTL_THROW;
753 EXTL_CATCH_END
754
755 EXTL_ASSERT(derive().is_valid());
756
757 return *(node->pos());
758 }
759 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
760 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::erase(index_type i0, index_type i1, bool_type* has_existed)
761 {
762 EXTL_MESSAGE_ASSERT(i0 < dim0() && i1 < dim1(), "out of range");
763 EXTL_ASSERT(derive().is_valid());
764
765 if (!(i0 < dim0())) return ;
766 if (!(i1 < dim1())) return ;
767
768 node_pointer node = NULL;
769 size_type step = 0;
770 EXTL_TRY
771 node = derive().erase_from_row(i0, i1, has_existed);
772 step = 1;
773 node = derive().erase_from_col(i0, i1, has_existed);
774 step = 2;
775 if (NULL != node) destroy_node(node);
776 EXTL_CATCH_ALL
777 switch (step)
778 {
779 case 2:
780 {
781 EXTL_ASSERT(NULL != node);
782 if (NULL != node)
783 derive().insert_into_col(node, has_existed);
784 }
785 case 1:
786 {
787 EXTL_ASSERT(NULL != node);
788 if (NULL != node)
789 derive().insert_into_row(node, has_existed);
790 }
791 }
792 // reraise
793 EXTL_THROW;
794 EXTL_CATCH_END
795
796 EXTL_ASSERT(derive().is_valid());
797 }
798
799 // note: non-exception-safe
800 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
801 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(size_type)::erase_row(index_type i0)
802 {
803 if (rheads()[i0].is_empty()) return 0;
804
805 size_type n = 0;
806 node_pointer rp = rheads()[i0].right();
807 EXTL_ASSERT(NULL != rp);
808 for (; &(rheads()[i0]) != rp; ++n)
809 {
810 node_pointer old = rp;
811
812 // erase node
813 rp->top()->bottom(rp->bottom());
814 rp->bottom()->top(rp->top());
815
816 // destroy node
817 rp = rp->right();
818 if (NULL != old) destroy_node(old);
819 }
820 rheads()[i0].clear();
821
822 return n;
823 }
824 // note: non-exception-safe
825 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
826 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(size_type)::erase_col(index_type i1)
827 {
828 if (cheads()[i1].is_empty()) return 0;
829
830 size_type n = 0;
831 node_pointer cp = cheads()[i1].bottom();
832 EXTL_ASSERT(NULL != cp);
833 for (; &(cheads()[i1]) != cp; ++n)
834 {
835 node_pointer old = cp;
836
837 // erase node
838 cp->left()->right(cp->right());
839 cp->right()->left(cp->left());
840
841 // destroy node
842 cp = cp->bottom();
843 if (NULL != old) destroy_node(old);
844 }
845 cheads()[i1].clear();
846
847 return n;
848 }
849
850 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
851 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::init()
852 {
853 // clear nodes
854 nodes().clear();
855
856 // clear rheads
857 size_type rn = rheads().size();
858 EXTL_ASSERT(rn == dim0());
859 for (index_type i = 0; i < rn; ++i)
860 rheads()[i].clear();
861
862 // clear cheads
863 size_type cn = cheads().size();
864 EXTL_ASSERT(cn == dim1());
865 for (index_type j = 0; j < cn; ++j)
866 cheads()[j].clear();
867
868 EXTL_ASSERT(derive().is_valid());
869 }
870
871 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
872 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::destroy()
873 {
874 derive().clear();
875 }
876
877 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
878 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::destroy_nodes()
879 {
880 // destroy nodes
881 size_type rn = rheads().size();
882 EXTL_ASSERT(rn == dim0());
883 for (index_type i = 0; i < rn; ++i)
884 {
885 for (node_pointer rp = rheads()[i].right(); &(rheads()[i]) != rp; )
886 {
887 if (NULL != rp)
888 {
889 node_pointer node = rp;
890 rp = rp->right();
891 destroy_node(node);
892 }
893 }
894 }
895
896 EXTL_ASSERT(nodes().size() == 0);
897 }
898
899 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
900 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::clear()
901 {
902 EXTL_ASSERT(derive().is_valid());
903
904 // destroy nodes
905 destroy_nodes();
906
907 // clear nodes
908 nodes().clear();
909
910 // clear rheads
911 size_type rn = rheads().size();
912 EXTL_ASSERT(rn == dim0());
913 for (index_type i = 0; i < rn; ++i)
914 rheads()[i].clear();
915
916 // clear cheads
917 size_type cn = cheads().size();
918 EXTL_ASSERT(cn == dim1());
919 for (index_type j = 0; j < cn; ++j)
920 cheads()[j].clear();
921
922 EXTL_ASSERT(derive().is_valid());
923 }
924 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
925 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(bool_type)::exists(index_type i0, index_type i1) const
926 {
927 if (!(i0 < dim0())) return e_false_v;
928 if (!(i1 < dim1())) return e_false_v;
929
930 if (rheads()[i0].is_empty()) return e_false_v;
931 if (cheads()[i1].is_empty()) return e_false_v;
932
933 // find i1(col) from i0(row)
934 const_node_pointer rp = rheads()[i0].right();
935 EXTL_ASSERT(NULL != rp);
936 for (; &(rheads()[i0]) != rp && rp->col() < i1; rp = rp->right());
937 if (rp == &(rheads()[i0]) || rp->col() != i1) return e_false_v;
938
939 // find i0(row) from i1(col)
940 /*const_node_pointer cp = cheads()[i1].bottom();
941 EXTL_ASSERT(NULL != cp);
942 for (; &(cheads()[i1]) != cp && cp->row() < i0; cp = cp->bottom());
943 if (cp == &(cheads()[i1]) || cp->row() != i0) return e_false_v;*/
944
945 return e_true_v;
946 }
947
948 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
949 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(bool_type)::is_valid() const
950 {
951 size_type rn = rheads().size();
952 if (rn != dim0()) return e_false_v;
953
954 size_type cn = cheads().size();
955 if (cn != dim1()) return e_false_v;
956
957 // check invariance from rheads
958 for (index_type i = 0; i < rn; ++i)
959 {
960 const_node_pointer rp = rheads()[i].right();
961 if (NULL == rp->right()) return e_false_v;
962 for (; &(rheads()[i]) != rp; rp = rp->right())
963 {
964 if (NULL == rp->right()) return e_false_v;
965 if (NULL == rp->left()) return e_false_v;
966 if (NULL == rp->top()) return e_false_v;
967 if (NULL == rp->bottom()) return e_false_v;
968
969 if (!(rp->row() == i)) return e_false_v;
970 if (&(cheads()[rp->col()]) != rp->top() && !(rp->top()->row() < i)) return e_false_v;
971 if (&(cheads()[rp->col()]) != rp->bottom() && !(rp->bottom()->row() > i)) return e_false_v;
972 if (&(rheads()[i]) != rp->left() && !(rp->left()->col() < rp->col())) return e_false_v;
973 }
974 }
975
976 // check invariance from cheads
977 for (index_type j = 0; j < cn; ++j)
978 {
979 const_node_pointer cp = cheads()[j].bottom();
980 if (NULL == cp->bottom()) return e_false_v;
981 for (; &(cheads()[j]) != cp; cp = cp->bottom())
982 {
983 if (NULL == cp->right()) return e_false_v;
984 if (NULL == cp->left()) return e_false_v;
985 if (NULL == cp->top()) return e_false_v;
986 if (NULL == cp->bottom()) return e_false_v;
987
988 if (!(cp->col() == j)) return e_false_v;
989 if (&(rheads()[cp->row()]) != cp->left() && !(cp->left()->col() < j)) return e_false_v;
990 if (&(rheads()[cp->row()]) != cp->right() && !(cp->right()->col() > j)) return e_false_v;
991 if (&(cheads()[j]) != cp->top() && !(cp->top()->row() < cp->row())) return e_false_v;
992 }
993 }
994
995 return e_true_v;
996 }
997 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
998 inline void EXTL_SPARSE_MATRIX_BASE_QUAL::swap(derived_type& rhs)
999 {
1000 derived_type tmp(derive());
1001 derive().assign(rhs);
1002 rhs.assign(tmp);
1003 }
1004 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1005 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(derived_type&)::operator =(derived_type const& rhs)
1006 {
1007 derive().assign(rhs);
1008 return derive();
1009 }
1010 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1011 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(derived_type&)::assign(derived_type const& rhs)
1012 {
1013 EXTL_ASSERT(rhs.is_valid());
1014 if (&derive() == &rhs) return derive();
1015
1016 derive().clear();
1017 rheads().resize(rhs.dim0());
1018 cheads().resize(rhs.dim1());
1019 derive().init();
1020
1021 size_type rn = rheads().size();
1022 EXTL_ASSERT(rn == derive().dim0());
1023
1024 class_type const* prhs = static_cast<class_type const*>(&rhs);
1025 EXTL_ASSERT(NULL != prhs);
1026
1027 // insert nodes
1028 for (index_type i = 0; i < rn; ++i)
1029 {
1030 if (prhs->rheads()[i].is_empty())
1031 continue;
1032
1033 const_node_pointer rp = prhs->rheads()[i].right();
1034 EXTL_ASSERT(NULL != rp->right());
1035 for (; &(prhs->rheads()[i]) != rp; rp = rp->right())
1036 {
1037 EXTL_ASSERT(NULL != rp);
1038
1039 #ifdef EXTL_COMPILER_IS_DMC
1040 const_reference val = derive().insert(i, rp->col(), rp->value());
1041 EXTL_SUPPRESS_UNUSED(val);
1042 #else
1043 derive().insert(i, rp->col(), rp->value());
1044 #endif
1045 }
1046 }
1047 return derive();
1048 }
1049 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1050 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(reference)::at(index_type i0, index_type i1)
1051 {
1052 return const_cast<reference>(static_cast<derived_type const&>(*this).at(i0, i1));
1053 }
1054 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1055 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(const_reference)::at(index_type i0, index_type i1) const
1056 {
1057 EXTL_MESSAGE_ASSERT(i0 < dim0() && i1 < dim1(), "out of range");
1058 EXTL_ASSERT_THROW(i0 < dim0() && i1 < dim1(), index_type("out of range"));
1059 return at_unchecked(i0, i1);
1060 }
1061 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1062 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(reference)::at_unchecked(index_type i0, index_type i1)
1063 {
1064 return const_cast<reference>(static_cast<derived_type const&>(*this).at_unchecked(i0, i1));
1065 }
1066 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1067 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(const_reference)::at_unchecked(index_type i0, index_type i1) const
1068 {
1069 EXTL_MESSAGE_ASSERT(i0 < dim0() && i1 < dim1(), "out of range");
1070
1071 index_type row = i0;
1072 index_type col = i1;
1073
1074 // find insertion point
1075 const_node_pointer rp = rheads()[row].right();
1076 EXTL_ASSERT(NULL != rp);
1077 for (; &(rheads()[row]) != rp && rp->col() < col; rp = rp->right());
1078
1079 if (rp != &rheads()[row] && rp->col() == col)
1080 return rp->value();
1081
1082 /*const_node_pointer cp = cheads()[col].bottom();
1083 EXTL_ASSERT(NULL != cp);
1084 for (; &(cheads()[col]) != cp && cp->row() < row; cp = cp->bottom());
1085
1086 if (cp != &cheads()[col] && cp->row() == row)
1087 return cp->value();*/
1088
1089 // insert node if not exists
1090 return const_cast<derived_type&>(derive()).insert(i0, i1, value_type());
1091 }
1092
1093 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1094 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(reduced_dimension_type)::at(index_type i0)
1095 {
1096 EXTL_MESSAGE_ASSERT(i0 < dim0(), "out of range");
1097 EXTL_ASSERT_THROW(i0 < dim0(), index_type("out of range"));
1098 return reduced_dimension_type(&derive(), i0);
1099 }
1100 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1101 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(const_reduced_dimension_type)::at(index_type i0) const
1102 {
1103 EXTL_MESSAGE_ASSERT(i0 < dim0(), "out of range");
1104 EXTL_ASSERT_THROW(i0 < dim0(), index_type("out of range"));
1105 return const_reduced_dimension_type(&derive(), i0);
1106 }
1107
1108 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1109 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(reduced_dimension_type)::at_unchecked(index_type i0)
1110 {
1111 return reduced_dimension_type(&derive(), i0);
1112 }
1113 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1114 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(const_reduced_dimension_type)::at_unchecked(index_type i0) const
1115 {
1116 return const_reduced_dimension_type(&derive(), i0);
1117 }
1118 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1119 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(bool_type)::get_if_exists(index_type i0, index_type i1, reference ret) const
1120 {
1121 EXTL_MESSAGE_ASSERT(i0 < dim0() && i1 < dim1(), "out of range");
1122
1123 index_type row = i0;
1124 index_type col = i1;
1125
1126 // find insertion point
1127 const_node_pointer rp = rheads()[row].right();
1128 EXTL_ASSERT(NULL != rp);
1129 for (; &(rheads()[row]) != rp && rp->col() < col; rp = rp->right());
1130
1131 // if exists
1132 if (rp != &rheads()[row] && rp->col() == col)
1133 {
1134 ret = rp->value();
1135 return e_true_v;
1136 }
1137
1138 return e_false_v;
1139 }
1140 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1141 inline EXTL_SPARSE_MATRIX_BASE_RET_QUAL(bool_type)::set_if_exists(index_type i0, index_type i1, const_reference val)
1142 {
1143 EXTL_MESSAGE_ASSERT(i0 < dim0() && i1 < dim1(), "out of range");
1144
1145 index_type row = i0;
1146 index_type col = i1;
1147
1148 // find insertion point
1149 node_pointer rp = rheads()[row].right();
1150 EXTL_ASSERT(NULL != rp);
1151 for (; &(rheads()[row]) != rp && rp->col() < col; rp = rp->right());
1152
1153 // if exists
1154 if (rp != &rheads()[row] && rp->col() == col)
1155 {
1156 rp->value(val);
1157 return e_true_v;
1158 }
1159
1160 return e_false_v;
1161 }
1162 /* /////////////////////////////////////////////////////////////////////////
1163 * swapping
1164 */
1165 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1166 EXTL_INLINE void swap(EXTL_SPARSE_MATRIX_BASE_QUAL& lhs, EXTL_SPARSE_MATRIX_BASE_QUAL& rhs)
1167 {
1168 static_cast<Dev&>(lhs).swap(static_cast<Dev&>(rhs));
1169 }
1170
1171 EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1172 EXTL_INLINE typename_type_ret_k EXTL_SPARSE_MATRIX_BASE_QUAL::
1173 size_type get_size(EXTL_SPARSE_MATRIX_BASE_QUAL const& mx)
1174 {
1175 return static_cast<Dev const&>(mx).size();
1176 }
1177
1178 /* //////////////////////////////////////////////////////////////////// */
1179 #undef EXTL_SPARSE_MATRIX_BASE_TEMPLATE_DECL
1180 #undef EXTL_SPARSE_MATRIX_BASE_QUAL
1181 #undef EXTL_SPARSE_MATRIX_BASE_RET_QUAL
1182 /* ///////////////////////////////////////////////////////////////////////
1183 * ::extl namespace
1184 */
1185 EXTL_END_NAMESPACE
1186
1187 /* ///////////////////////////////////////////////////////////////////////
1188 * std::swap
1189 */
1190 #if !defined(EXTL_NO_STL) && \
1191 !defined(EXTL_NO_NAMESPACE)
1192 /* ::std namespace */
1193 EXTL_STD_BEGIN_NAMESPACE
1194
1195 template< typename_param_k Dev
1196 , typename_param_k Val
1197 >
1198 EXTL_INLINE void swap(EXTL_NS(sparse_matrix_base)<Dev, Val>& lhs,
1199 EXTL_NS(sparse_matrix_base)<Dev, Val>& rhs)
1200 {
1201 static_cast<Dev&>(lhs).swap(static_cast<Dev&>(rhs));
1202 }
1203 /* ::std namespace */
1204 EXTL_STD_END_NAMESPACE
1205 #endif
1206
1207 /* //////////////////////////////////////////////////////////////////// */
1208 #endif /* EXTL_CONTAINER_SPARSE_MATRIX_BASE_H */
1209 /* //////////////////////////////////////////////////////////////////// */
a c++ generic library