« back to all changes in this revision
Viewing changes to include/mdds/quad_type_matrix.hpp
- browse files at revision 5
- compare with another revision
- download diff
- download tarball
- view history from revision 5
- Committer: Bazaar Package Importer
- Author(s): Rene Engelhard
- Date: 2010-12-21 03:00:49 UTC
- mfrom: (1.1.2 upstream)
- Revision ID: james.westby@ubuntu.com-20101221030049-15awcps1vyzo90s0
Tags: 0.4.0-1
New upstream release
- files added:
- .pc/debian-changes-0.4.0-1
- .pc/debian-changes-0.4.0-1/bin
- .pc/debian-changes-0.4.0-1/example
- .pc/debian-changes-0.4.0-1/misc
- bin
- misc
- files removed:
- include/mdds/quad_type_matrix.hpp
- files modified:
- .pc/DESTDIR.diff/Makefile.in
added
removed
include/mdds/quad_type_matrix.hpp
1
/*************************************************************************
2
*
3
* Copyright (c) 2010 Kohei Yoshida
4
*
5
* Permission is hereby granted, free of charge, to any person
6
* obtaining a copy of this software and associated documentation
7
* files (the "Software"), to deal in the Software without
8
* restriction, including without limitation the rights to use,
9
* copy, modify, merge, publish, distribute, sublicense, and/or sell
10
* copies of the Software, and to permit persons to whom the
11
* Software is furnished to do so, subject to the following
12
* conditions:
13
*
14
* The above copyright notice and this permission notice shall be
15
* included in all copies or substantial portions of the Software.
16
*
17
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24
* OTHER DEALINGS IN THE SOFTWARE.
25
*
26
************************************************************************/
27
28
#ifndef __MDDS_QUAD_TYPE_MATRIX_HPP__
29
#define __MDDS_QUAD_TYPE_MATRIX_HPP__
30
31
#include "mdds/global.hpp"
32
#include "mdds/hash_container/map.hpp"
33
34
#include <iostream>
35
#include <cstdlib>
36
#include <boost/ptr_container/ptr_vector.hpp>
37
#include <boost/ptr_container/ptr_map.hpp>
38
39
namespace mdds {
40
41
enum matrix_density_t
42
{
43
matrix_density_filled_zero,
44
matrix_density_filled_empty,
45
matrix_density_sparse_zero,
46
matrix_density_sparse_empty
47
};
48
49
enum matrix_element_t
50
{
51
element_empty = 0,
52
element_numeric = 1,
53
element_boolean = 2,
54
element_string = 3
55
};
56
57
enum matrix_init_element_t
58
{
59
matrix_init_element_zero,
60
matrix_init_element_empty
61
};
62
63
class matrix_error : public ::mdds::general_error
64
{
65
public:
66
matrix_error(const ::std::string& msg) : general_error(msg) {}
67
};
68
69
matrix_init_element_t get_init_element_type(matrix_density_t density)
70
{
71
switch (density)
72
{
73
case matrix_density_filled_empty:
74
case matrix_density_sparse_empty:
75
return matrix_init_element_empty;
76
case matrix_density_filled_zero:
77
case matrix_density_sparse_zero:
78
return matrix_init_element_zero;
79
default:
80
throw matrix_error("unknown matrix density type.");
81
}
82
}
83
84
/**
85
* This data structure represents a matrix where each individual element may
86
* be of one of four types: value, boolean, string, or empty.
87
*/
88
template<typename _String, typename _Flag>
89
class quad_type_matrix
90
{
91
public:
92
typedef _String string_type;
93
typedef _Flag flag_type;
94
typedef size_t size_type;
95
typedef ::std::pair<size_type, size_type> size_pair_type;
96
97
/**
98
* Default constructor.
99
*/
100
quad_type_matrix();
101
102
/**
103
* Construct an empty matrix with specified density type.
104
*/
105
quad_type_matrix(matrix_density_t density);
106
107
/**
108
* Construct a matrix of specified size with specified density type.
109
*/
110
quad_type_matrix(size_t rows, size_t cols, matrix_density_t density);
111
112
quad_type_matrix(const quad_type_matrix& r);
113
~quad_type_matrix();
114
115
quad_type_matrix& operator= (const quad_type_matrix& r);
116
117
/**
118
* Get the type of element specified by its position. The type can be one
119
* of empty, string, numeric, or boolean.
120
*
121
* @return element type.
122
*/
123
matrix_element_t get_type(size_t row, size_t col) const;
124
125
double get_numeric(size_t row, size_t col) const;
126
bool get_boolean(size_t row, size_t col) const;
127
const string_type* get_string(size_t row, size_t col) const;
128
129
void set_numeric(size_t row, size_t col, double val);
130
void set_boolean(size_t row, size_t col, bool val);
131
void set_string(size_t row, size_t col, string_type* str);
132
void set_empty(size_t row, size_t col);
133
134
void set(size_t row, size_t col, double val);
135
void set(size_t row, size_t col, bool val);
136
void set(size_t row, size_t col, string_type* str);
137
138
/**
139
* Set flag value at specified position.
140
*
141
* @param row row position
142
* @param col column position
143
* @param flag_type flag value
144
*/
145
void set_flag(size_t row, size_t col, flag_type flag);
146
147
/**
148
* Get flag value at specified position.
149
*
150
* @param row row position
151
* @param col column position
152
*
153
* @return flag value stored at specified position
154
*/
155
flag_type get_flag(size_t row, size_t col) const;
156
157
void clear_flag(size_t row, size_t cols);
158
159
/**
160
* Return the size of matrix as a pair. The first value is the row size,
161
* while the second value is the column size.
162
*
163
* @return matrix size as a value pair.
164
*/
165
size_pair_type size() const;
166
167
/**
168
* Transpose the stored matrix data.
169
*
170
* @return reference to this matrix instance.
171
*/
172
quad_type_matrix& transpose();
173
174
/**
175
* Assign values from the passed matrix instance. If the size of the
176
* passed matrix is smaller, then the element values are assigned by their
177
* positions, while the rest of the elements that fall outside the size of
178
* the passed matrix instance will remain unmodified. If the size of the
179
* pass matrix instance is larger, then only the elements within the size
180
* of this matrix instance will get assigned.
181
*
182
* @param r passed matrix object to assign element values from.
183
*/
184
void assign(const quad_type_matrix& r);
185
186
/**
187
* Resize the matrix to specified size. This method supports resizing to
188
* zero-sized matrix; however, either specifying the row or column size to
189
* zero will resize the matrix to 0 x 0.
190
*
191
* @param row new row size
192
* @param col new column size
193
*/
194
void resize(size_t row, size_t col);
195
196
/**
197
* Empty the matrix.
198
*/
199
void clear();
200
201
/**
202
* Check whether or not this matrix is numeric. A numeric matrix contains
203
* only numeric or boolean elements.
204
*
205
* @return true if the matrix contains only numeric or boolean elements,
206
* or false otherwise.
207
*/
208
bool numeric() const;
209
210
/**
211
* Check whether or not this matrix is empty.
212
*
213
* @return true if this matrix is empty, or false otherwise.
214
*/
215
bool empty() const;
216
217
/**
218
* Swap the content of the matrix with another instance.
219
*/
220
void swap(quad_type_matrix& r);
221
222
#ifdef UNIT_TEST
223
void dump() const;
224
void dump_flags() const;
225
#endif
226
227
private:
228
struct size_pair_type_hash
229
{
230
size_t operator() (const size_pair_type& val) const
231
{
232
size_t n = val.first + (val.second << 8);
233
return n;
234
}
235
};
236
typedef _mdds_unordered_map_type<size_pair_type, flag_type, size_pair_type_hash> flag_store_type;
237
238
class flag_storage
239
{
240
public:
241
flag_storage() {}
242
flag_storage(const flag_storage& r) : m_flags(r.m_flags) {}
243
244
void set_flag(size_t row, size_t col, flag_type flag)
245
{
246
size_pair_type pos = size_pair_type(row, col);
247
typename flag_store_type::iterator itr = m_flags.find(pos);
248
if (itr == m_flags.end())
249
{
250
// flag not stored for this position.
251
::std::pair<typename flag_store_type::iterator, bool> r =
252
m_flags.insert(typename flag_store_type::value_type(pos, flag));
253
return;
254
}
255
itr->second = flag;
256
}
257
258
flag_type get_flag(size_t row, size_t col)
259
{
260
size_pair_type pos = size_pair_type(row, col);
261
typename flag_store_type::iterator itr = m_flags.find(pos);
262
return itr == m_flags.end() ? static_cast<flag_type>(0) : itr->second;
263
}
264
265
void clear_flag(size_t row, size_t col)
266
{
267
size_pair_type pos = size_pair_type(row, col);
268
typename flag_store_type::iterator itr = m_flags.find(pos);
269
if (itr != m_flags.end())
270
// Flag is stored at this position. Remove it.
271
m_flags.erase(itr);
272
}
273
#if UNIT_TEST
274
void dump() const
275
{
276
using namespace std;
277
if (m_flags.empty())
278
{
279
cout << "no flags stored" << endl;
280
return;
281
}
282
283
cout << "flags stored:" << endl;
284
typename flag_store_type::const_iterator itr = m_flags.begin(), itr_end = m_flags.end();
285
for (; itr != itr_end; ++itr)
286
{
287
const size_pair_type& pos = itr->first;
288
flag_type val = itr->second;
289
cout << "(row=" << pos.first << ",col=" << pos.second << ") = 0x" << hex << static_cast<size_t>(val) << endl;
290
}
291
}
292
#endif
293
private:
294
flag_store_type m_flags;
295
};
296
297
struct element
298
{
299
matrix_element_t m_type:2;
300
301
union
302
{
303
double m_numeric;
304
bool m_boolean;
305
string_type* mp_string;
306
};
307
308
element() : m_type(element_empty) {}
309
element(const element& r) : m_type(r.m_type)
310
{
311
switch (m_type)
312
{
313
case element_boolean:
314
m_boolean = r.m_boolean;
315
break;
316
case element_numeric:
317
m_numeric = r.m_numeric;
318
break;
319
case element_string:
320
mp_string = new string_type(*r.mp_string);
321
break;
322
case element_empty:
323
default:
324
;
325
}
326
}
327
328
explicit element(double v) : m_type(element_numeric), m_numeric(v) {}
329
explicit element(bool v) : m_type(element_boolean), m_boolean(v) {}
330
explicit element(string_type* p) : m_type(element_string), mp_string(p) {}
331
332
bool operator== (const element& r) const
333
{
334
if (m_type != r.m_type)
335
return false;
336
337
switch (m_type)
338
{
339
case element_boolean:
340
return m_boolean == r.m_boolean;
341
case element_numeric:
342
return m_numeric == r.m_numeric;
343
case element_string:
344
return *mp_string == *r.mp_string;
345
case element_empty:
346
default:
347
;
348
}
349
350
return true;
351
}
352
353
element& operator= (const element& r)
354
{
355
if (m_type == element_string)
356
delete mp_string;
357
358
m_type = r.m_type;
359
360
switch (m_type)
361
{
362
case element_boolean:
363
m_boolean = r.m_boolean;
364
break;
365
case element_numeric:
366
m_numeric = r.m_numeric;
367
break;
368
case element_string:
369
mp_string = new string_type(*r.mp_string);
370
break;
371
case element_empty:
372
default:
373
;
374
}
375
return *this;
376
}
377
378
~element()
379
{
380
if (m_type == element_string)
381
delete mp_string;
382
}
383
384
void set_empty()
385
{
386
if (m_type == element_string)
387
delete mp_string;
388
m_type = element_empty;
389
}
390
391
void set_numeric(double val)
392
{
393
if (m_type == element_string)
394
delete mp_string;
395
m_type = element_numeric;
396
m_numeric = val;
397
}
398
399
void set_boolean(bool val)
400
{
401
if (m_type == element_string)
402
delete mp_string;
403
m_type = element_boolean;
404
m_boolean = val;
405
}
406
407
void set_string(string_type* str)
408
{
409
if (m_type == element_string)
410
delete mp_string;
411
m_type = element_string;
412
mp_string = str;
413
}
414
};
415
416
class storage_base
417
{
418
public:
419
storage_base(matrix_init_element_t init) : m_init_type(init) {}
420
storage_base(const storage_base& r) : m_init_type(r.m_init_type), m_flags(r.m_flags) {}
421
422
virtual ~storage_base() {}
423
424
virtual element& get_element(size_t row, size_t col) = 0;
425
426
virtual matrix_element_t get_type(size_t row, size_t col) const = 0;
427
428
virtual double get_numeric(size_t row, size_t col) const = 0;
429
virtual const string_type* get_string(size_t row, size_t col) const = 0;
430
virtual bool get_boolean(size_t row, size_t col) const = 0;
431
432
virtual size_t rows() const = 0;
433
virtual size_t cols() const = 0;
434
435
virtual void transpose() = 0;
436
virtual void resize(size_t row, size_t col) = 0;
437
virtual void clear() = 0;
438
virtual bool numeric() = 0;
439
virtual bool empty() const = 0;
440
441
virtual storage_base* clone() const = 0;
442
443
flag_storage& get_flag_storage() { return m_flags; }
444
445
protected:
446
matrix_init_element_t get_init_type() const { return m_init_type; }
447
448
private:
449
matrix_init_element_t m_init_type;
450
flag_storage m_flags;
451
};
452
453
/**
454
* This storage creates instance for every single element, even for the
455
* empty elements.
456
*/
457
class storage_filled : public storage_base
458
{
459
typedef ::boost::ptr_vector<element> row_type;
460
typedef ::boost::ptr_vector<row_type> rows_type;
461
462
public:
463
storage_filled(size_t _rows, size_t _cols, matrix_init_element_t init_type) :
464
storage_base(init_type),
465
m_numeric(false),
466
m_valid(false)
467
{
468
m_rows.reserve(_rows);
469
for (size_t i = 0; i < _rows; ++i)
470
{
471
m_rows.push_back(new row_type);
472
init_row(m_rows.back(), _cols);
473
}
474
}
475
476
storage_filled(const storage_filled& r) :
477
storage_base(r),
478
m_rows(r.m_rows),
479
m_numeric(r.m_numeric),
480
m_valid(r.m_valid) {}
481
482
virtual ~storage_filled() {}
483
484
virtual element& get_element(size_t row, size_t col)
485
{
486
m_valid = false;
487
return m_rows.at(row).at(col);
488
}
489
490
virtual matrix_element_t get_type(size_t row, size_t col) const
491
{
492
return m_rows.at(row).at(col).m_type;
493
}
494
495
virtual double get_numeric(size_t row, size_t col) const
496
{
497
const element& elem = m_rows.at(row).at(col);
498
if (elem.m_type != element_numeric && elem.m_type != element_boolean)
499
throw matrix_error("element type is not numeric.");
500
501
if (elem.m_type == element_boolean)
502
return static_cast<double>(elem.m_boolean);
503
504
return elem.m_numeric;
505
}
506
507
virtual const string_type* get_string(size_t row, size_t col) const
508
{
509
const element& elem = m_rows.at(row).at(col);
510
if (elem.m_type != element_string)
511
throw matrix_error("element type is not string.");
512
513
return elem.mp_string;
514
}
515
516
virtual bool get_boolean(size_t row, size_t col) const
517
{
518
const element& elem = m_rows.at(row).at(col);
519
if (elem.m_type != element_boolean)
520
throw matrix_error("element type is not boolean.");
521
522
return elem.m_boolean;
523
}
524
525
virtual size_t rows() const
526
{
527
return m_rows.size();
528
}
529
530
virtual size_t cols() const
531
{
532
return m_rows.empty() ? 0 : m_rows[0].size();
533
}
534
535
virtual void transpose()
536
{
537
rows_type trans_mx;
538
size_t row_size = rows(), col_size = cols();
539
trans_mx.reserve(col_size);
540
for (size_t col = 0; col < col_size; ++col)
541
{
542
trans_mx.push_back(new row_type);
543
row_type& trans_row = trans_mx.back();
544
trans_row.reserve(row_size);
545
for (size_t row = 0; row < row_size; ++row)
546
trans_row.push_back(new element(m_rows[row][col]));
547
}
548
m_rows.swap(trans_mx);
549
}
550
551
virtual void resize(size_t row, size_t col)
552
{
553
m_valid = false;
554
if (!row || !col)
555
{
556
// Empty the matrix.
557
clear();
558
return;
559
}
560
561
size_t cur_rows = rows(), cur_cols = cols();
562
563
if (row > cur_rows)
564
{
565
// Insert extra rows...
566
size_t new_row_count = row - cur_rows;
567
m_rows.reserve(row);
568
for (size_t i = 0; i < new_row_count; ++i)
569
{
570
m_rows.push_back(new row_type);
571
init_row(m_rows.back(), col);
572
}
573
574
resize_rows(cur_rows-1, cur_cols, col);
575
}
576
else if (cur_rows > row)
577
{
578
// Remove rows to new size.
579
m_rows.resize(row);
580
resize_rows(row-1, cur_cols, col);
581
}
582
else
583
{
584
assert(cur_rows == row);
585
resize_rows(cur_rows-1, cur_cols, col);
586
}
587
}
588
589
virtual void clear()
590
{
591
m_rows.clear();
592
m_valid = true;
593
m_numeric = false;
594
}
595
596
virtual bool numeric()
597
{
598
if (m_valid)
599
return m_numeric;
600
601
typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end();
602
for (; itr_row != itr_row_end; ++itr_row)
603
{
604
typename row_type::const_iterator itr_col = itr_row->begin(), itr_col_end = itr_row->end();
605
for (; itr_col != itr_col_end; ++itr_col)
606
{
607
matrix_element_t elem_type = itr_col->m_type;
608
if (elem_type != element_numeric && elem_type != element_boolean)
609
{
610
m_numeric = false;
611
m_valid = true;
612
return m_numeric;
613
}
614
}
615
}
616
617
m_numeric = true;
618
m_valid = true;
619
return m_numeric;
620
}
621
622
virtual bool empty() const
623
{
624
return m_rows.empty();
625
}
626
627
virtual storage_base* clone() const
628
{
629
return new storage_filled(*this);
630
}
631
632
private:
633
634
/**
635
* Resize rows to a new column size, from row 0 up to specified upper
636
* row.
637
*/
638
void resize_rows(size_t upper_row, size_t cur_cols, size_t new_cols)
639
{
640
for (size_t i = 0; i <= upper_row; ++i)
641
{
642
// Resize pre-existing rows to new column size.
643
if (new_cols > cur_cols)
644
{
645
size_t new_col_count = new_cols - cur_cols;
646
for (size_t j = 0; j < new_col_count; ++j)
647
insert_new_elem(m_rows[i]);
648
}
649
else if (new_cols < cur_cols)
650
m_rows[i].resize(new_cols);
651
}
652
}
653
654
void init_row(row_type& row, size_t col_size)
655
{
656
row.reserve(col_size);
657
for (size_t j = 0; j < col_size; ++j)
658
insert_new_elem(row);
659
}
660
661
void insert_new_elem(row_type& row)
662
{
663
matrix_init_element_t init_type = storage_base::get_init_type();
664
switch (init_type)
665
{
666
case matrix_init_element_zero:
667
row.push_back(new element(static_cast<double>(0.0)));
668
break;
669
case matrix_init_element_empty:
670
row.push_back(new element);
671
break;
672
default:
673
throw matrix_error("unknown init type.");
674
}
675
}
676
677
private:
678
rows_type m_rows;
679
bool m_numeric:1;
680
bool m_valid:1;
681
};
682
683
/**
684
* This storage stores only non-empty elements.
685
*/
686
class storage_sparse : public storage_base
687
{
688
typedef ::boost::ptr_map<size_t, element> row_type;
689
typedef ::boost::ptr_map<size_t, row_type> rows_type;
690
691
public:
692
storage_sparse(size_t _rows, size_t _cols, matrix_init_element_t init_type) :
693
storage_base(init_type),
694
m_row_size(_rows), m_col_size(_cols),
695
m_numeric(_rows && _cols), m_valid(true)
696
{
697
switch (storage_base::get_init_type())
698
{
699
case matrix_init_element_zero:
700
m_empty_elem.m_type = element_numeric;
701
m_empty_elem.m_numeric = 0.0;
702
break;
703
default:
704
m_empty_elem.m_type = element_empty;
705
m_numeric = false;
706
}
707
}
708
709
storage_sparse(const storage_sparse& r) :
710
storage_base(r),
711
m_rows(r.m_rows),
712
m_empty_elem(r.m_empty_elem),
713
m_row_size(r.m_row_size),
714
m_col_size(r.m_col_size) {}
715
716
virtual ~storage_sparse() {}
717
718
virtual element & get_element(size_t row, size_t col)
719
{
720
if (row >= m_row_size || col >= m_col_size)
721
throw matrix_error("specified element is out-of-bound.");
722
723
m_valid = false;
724
725
typename rows_type::iterator itr = m_rows.find(row);
726
if (itr == m_rows.end())
727
{
728
// Insert a brand-new row.
729
::std::pair<typename rows_type::iterator, bool> r = m_rows.insert(row, new row_type);
730
if (!r.second)
731
throw matrix_error("failed to insert a new row instance into storage_sparse.");
732
itr = r.first;
733
}
734
735
row_type& row_store = *itr->second;
736
typename row_type::iterator itr_elem = row_store.find(col);
737
if (itr_elem == row_store.end())
738
{
739
// Insert a new element at this column position.
740
::std::pair<typename row_type::iterator, bool> r = row_store.insert(col, new element);
741
if (!r.second)
742
throw matrix_error("failed to insert a new element instance.");
743
itr_elem = r.first;
744
}
745
return *itr_elem->second;
746
}
747
748
virtual matrix_element_t get_type(size_t row, size_t col) const
749
{
750
typename rows_type::const_iterator itr = m_rows.find(row);
751
if (itr == m_rows.end())
752
return m_empty_elem.m_type;
753
754
const row_type& row_store = *itr->second;
755
typename row_type::const_iterator itr_elem = row_store.find(col);
756
if (itr_elem == row_store.end())
757
return m_empty_elem.m_type;
758
759
return itr_elem->second->m_type;
760
}
761
762
virtual double get_numeric(size_t row, size_t col) const
763
{
764
matrix_element_t elem_type = get_type(row, col);
765
if (elem_type != element_numeric && elem_type != element_boolean)
766
throw matrix_error("element type is not numeric.");
767
768
const element& elem = get_non_empty_element(row, col);
769
770
if (elem.m_type == element_boolean)
771
return static_cast<double>(elem.m_boolean);
772
773
return elem.m_numeric;
774
}
775
776
virtual const string_type* get_string(size_t row, size_t col) const
777
{
778
matrix_element_t elem_type = get_type(row, col);
779
if (elem_type != element_string)
780
throw matrix_error("element type is not string.");
781
782
return get_non_empty_element(row, col).mp_string;
783
}
784
785
virtual bool get_boolean(size_t row, size_t col) const
786
{
787
matrix_element_t elem_type = get_type(row, col);
788
if (elem_type != element_boolean)
789
throw matrix_error("element type is not string.");
790
791
return get_non_empty_element(row, col).m_boolean;
792
}
793
794
virtual size_t rows() const
795
{
796
return m_row_size;
797
}
798
799
virtual size_t cols() const
800
{
801
return m_col_size;
802
}
803
804
typedef ::std::pair<size_t, size_t> elem_pos_type;
805
806
struct elem_pos_sorter : ::std::binary_function<elem_pos_type, elem_pos_type, bool>
807
{
808
bool operator() (const elem_pos_type& left, const elem_pos_type& right) const
809
{
810
if (left.first != right.first)
811
return left.first < right.first;
812
return left.second < right.second;
813
}
814
};
815
816
virtual void transpose()
817
{
818
using namespace std;
819
820
rows_type trans;
821
822
// First, pick up the positions of all non-empty elements.
823
vector<elem_pos_type> filled_elems;
824
{
825
typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end();
826
for (; itr_row != itr_row_end; ++itr_row)
827
{
828
size_t row_idx = itr_row->first;
829
const row_type& row = *itr_row->second;
830
typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end();
831
for (; itr_col != itr_col_end; ++itr_col)
832
{
833
// Be sure to swap the row and column indices.
834
filled_elems.push_back(elem_pos_type(itr_col->first, row_idx));
835
}
836
}
837
}
838
// Sort by row index first, then by column index.
839
sort(filled_elems.begin(), filled_elems.end(), elem_pos_sorter());
840
841
// Iterate through the non-empty element positions and perform
842
// transposition.
843
typename vector<elem_pos_type>::const_iterator
844
itr_pos = filled_elems.begin(), itr_pos_end = filled_elems.end();
845
while (itr_pos != itr_pos_end)
846
{
847
// First item of the new row.
848
size_t row_idx = itr_pos->first;
849
size_t col_idx = itr_pos->second;
850
pair<typename rows_type::iterator, bool> r = trans.insert(row_idx, new row_type);
851
if (!r.second)
852
throw matrix_error("failed to insert a new row instance during transposition.");
853
854
typename rows_type::iterator itr_row = r.first;
855
row_type& row = *itr_row->second;
856
pair<typename row_type::iterator, bool> r2 =
857
row.insert(col_idx, new element(m_rows[col_idx][row_idx]));
858
if (!r2.second)
859
throw matrix_error("afiled to insert a new element instance during transposition.");
860
861
// Keep iterating until we get a different row index.
862
for (++itr_pos; itr_pos != itr_pos_end && itr_pos->first == row_idx; ++itr_pos)
863
{
864
col_idx = itr_pos->second;
865
r2 = row.insert(col_idx, new element(m_rows[col_idx][row_idx]));
866
if (!r2.second)
867
throw matrix_error("afiled to insert a new element instance during transposition.");
868
}
869
}
870
871
m_rows.swap(trans);
872
::std::swap(m_row_size, m_col_size);
873
}
874
875
virtual void resize(size_t row, size_t col)
876
{
877
m_valid = false;
878
879
if (!row || !col)
880
{
881
clear();
882
return;
883
}
884
885
// Resizing a sparse matrix need to modify the data only when
886
// shrinking.
887
888
if (m_row_size > row)
889
{
890
// Remove all rows where the row index is greater than or
891
// equal to 'row'.
892
typename rows_type::iterator itr = m_rows.lower_bound(row);
893
m_rows.erase(itr, m_rows.end());
894
}
895
896
if (m_col_size > col)
897
{
898
typename rows_type::iterator itr = m_rows.begin(), itr_end = m_rows.end();
899
for (; itr != itr_end; ++itr)
900
{
901
// Now, remove all columns where the column index is
902
// greater than or equal to 'col'.
903
row_type& row_container = *itr->second;
904
typename row_type::iterator itr_elem = row_container.lower_bound(col);
905
row_container.erase(itr_elem, row_container.end());
906
}
907
}
908
909
m_row_size = row;
910
m_col_size = col;
911
}
912
913
virtual void clear()
914
{
915
m_rows.clear();
916
m_row_size = 0;
917
m_col_size = 0;
918
m_valid = true;
919
m_numeric = false;
920
}
921
922
virtual bool numeric()
923
{
924
using namespace std;
925
926
if (m_valid)
927
return m_numeric;
928
929
size_t non_empty_count = 0;
930
typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end();
931
for (; itr_row != itr_row_end; ++itr_row)
932
{
933
const row_type& row = *itr_row->second;
934
non_empty_count += row.size();
935
assert(row.size() <= m_col_size);
936
typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end();
937
for (; itr_col != itr_col_end; ++itr_col)
938
{
939
const element& elem = *itr_col->second;
940
if (elem.m_type != element_numeric && elem.m_type != element_boolean)
941
{
942
m_valid = true;
943
m_numeric = false;
944
return m_numeric;
945
}
946
}
947
}
948
949
// All non-empty elements are numeric.
950
951
matrix_init_element_t init_type = storage_base::get_init_type();
952
if (init_type == matrix_init_element_zero)
953
m_numeric = true;
954
else
955
{
956
size_t total_elem_count = m_row_size * m_col_size;
957
assert(non_empty_count <= total_elem_count);
958
m_numeric = total_elem_count == non_empty_count;
959
}
960
961
m_valid = true;
962
return m_numeric;
963
}
964
965
virtual bool empty() const
966
{
967
// If one of row and column sizes are zero, the other size must be
968
// zero, and vise versa.
969
assert((!m_row_size && !m_col_size) || (m_row_size && m_col_size));
970
971
return m_row_size == 0 || m_col_size == 0;
972
}
973
974
virtual storage_base* clone() const
975
{
976
return new storage_sparse(*this);
977
}
978
979
private:
980
const element& get_non_empty_element(size_t row, size_t col) const
981
{
982
typename rows_type::const_iterator itr = m_rows.find(row);
983
if (itr == m_rows.end())
984
return m_empty_elem;
985
986
const row_type& row_store = *itr->second;
987
typename row_type::const_iterator itr_elem = row_store.find(col);
988
if (itr_elem == row_store.end())
989
return m_empty_elem;
990
return *itr_elem->second;
991
}
992
993
private:
994
rows_type m_rows;
995
element m_empty_elem;
996
size_t m_row_size;
997
size_t m_col_size;
998
bool m_numeric:1;
999
bool m_valid:1;
1000
};
1001
1002
private:
1003
static storage_base* create_storage(size_t rows, size_t cols, matrix_density_t density);
1004
1005
private:
1006
storage_base* mp_storage;
1007
};
1008
1009
template<typename _String, typename _Flag>
1010
typename quad_type_matrix<_String,_Flag>::storage_base*
1011
quad_type_matrix<_String,_Flag>::create_storage(size_t rows, size_t cols, matrix_density_t density)
1012
{
1013
switch (density)
1014
{
1015
case matrix_density_filled_zero:
1016
return new storage_filled(rows, cols, matrix_init_element_zero);
1017
case matrix_density_filled_empty:
1018
return new storage_filled(rows, cols, matrix_init_element_empty);
1019
case matrix_density_sparse_zero:
1020
return new storage_sparse(rows, cols, matrix_init_element_zero);
1021
case matrix_density_sparse_empty:
1022
return new storage_sparse(rows, cols, matrix_init_element_empty);
1023
default:
1024
throw matrix_error("unknown density type");
1025
}
1026
return NULL;
1027
}
1028
1029
template<typename _String, typename _Flag>
1030
quad_type_matrix<_String,_Flag>::quad_type_matrix() :
1031
mp_storage(NULL)
1032
{
1033
mp_storage = create_storage(0, 0, matrix_density_filled_zero);
1034
}
1035
1036
template<typename _String, typename _Flag>
1037
quad_type_matrix<_String,_Flag>::quad_type_matrix(matrix_density_t density) :
1038
mp_storage(NULL)
1039
{
1040
mp_storage = create_storage(0, 0, density);
1041
}
1042
1043
template<typename _String, typename _Flag>
1044
quad_type_matrix<_String,_Flag>::quad_type_matrix(size_t rows, size_t cols, matrix_density_t density) :
1045
mp_storage(NULL)
1046
{
1047
mp_storage = create_storage(rows, cols, density);
1048
}
1049
1050
template<typename _String, typename _Flag>
1051
quad_type_matrix<_String,_Flag>::quad_type_matrix(const quad_type_matrix& r) :
1052
mp_storage(r.mp_storage->clone())
1053
{
1054
}
1055
1056
template<typename _String, typename _Flag>
1057
quad_type_matrix<_String,_Flag>::~quad_type_matrix()
1058
{
1059
delete mp_storage;
1060
}
1061
1062
template<typename _String, typename _Flag>
1063
quad_type_matrix<_String,_Flag>&
1064
quad_type_matrix<_String,_Flag>::operator= (const quad_type_matrix& r)
1065
{
1066
if (this == &r)
1067
// self assignment.
1068
return *this;
1069
1070
delete mp_storage;
1071
mp_storage = r.mp_storage->clone();
1072
return *this;
1073
}
1074
1075
template<typename _String, typename _Flag>
1076
matrix_element_t quad_type_matrix<_String,_Flag>::get_type(size_t row, size_t col) const
1077
{
1078
return mp_storage->get_type(row, col);
1079
}
1080
1081
template<typename _String, typename _Flag>
1082
double quad_type_matrix<_String,_Flag>::get_numeric(size_t row, size_t col) const
1083
{
1084
return mp_storage->get_numeric(row, col);
1085
}
1086
1087
template<typename _String, typename _Flag>
1088
bool quad_type_matrix<_String,_Flag>::get_boolean(size_t row, size_t col) const
1089
{
1090
return mp_storage->get_boolean(row, col);
1091
}
1092
1093
template<typename _String, typename _Flag>
1094
const typename quad_type_matrix<_String,_Flag>::string_type*
1095
quad_type_matrix<_String,_Flag>::get_string(size_t row, size_t col) const
1096
{
1097
return mp_storage->get_string(row, col);
1098
}
1099
1100
template<typename _String, typename _Flag>
1101
void quad_type_matrix<_String,_Flag>::set_numeric(size_t row, size_t col, double val)
1102
{
1103
mp_storage->get_element(row, col).set_numeric(val);
1104
}
1105
1106
template<typename _String, typename _Flag>
1107
void quad_type_matrix<_String,_Flag>::set_boolean(size_t row, size_t col, bool val)
1108
{
1109
mp_storage->get_element(row, col).set_boolean(val);
1110
}
1111
1112
template<typename _String, typename _Flag>
1113
void quad_type_matrix<_String,_Flag>::set_string(size_t row, size_t col, string_type* str)
1114
{
1115
mp_storage->get_element(row, col).set_string(str);
1116
}
1117
1118
template<typename _String, typename _Flag>
1119
void quad_type_matrix<_String,_Flag>::set_flag(size_t row, size_t col, flag_type flag)
1120
{
1121
mp_storage->get_flag_storage().set_flag(row, col, flag);
1122
}
1123
1124
template<typename _String, typename _Flag>
1125
typename quad_type_matrix<_String,_Flag>::flag_type
1126
quad_type_matrix<_String,_Flag>::get_flag(size_t row, size_t col) const
1127
{
1128
return mp_storage->get_flag_storage().get_flag(row, col);
1129
}
1130
1131
template<typename _String, typename _Flag>
1132
void quad_type_matrix<_String,_Flag>::clear_flag(size_t row, size_t col)
1133
{
1134
return mp_storage->get_flag_storage().clear_flag(row, col);
1135
}
1136
1137
template<typename _String, typename _Flag>
1138
void quad_type_matrix<_String,_Flag>::set_empty(size_t row, size_t col)
1139
{
1140
mp_storage->get_element(row, col).set_empty();
1141
}
1142
1143
template<typename _String, typename _Flag>
1144
void quad_type_matrix<_String,_Flag>::set(size_t row, size_t col, double val)
1145
{
1146
set_numeric(row, col, val);
1147
}
1148
1149
template<typename _String, typename _Flag>
1150
void quad_type_matrix<_String,_Flag>::set(size_t row, size_t col, bool val)
1151
{
1152
set_boolean(row, col, val);
1153
}
1154
1155
template<typename _String, typename _Flag>
1156
void quad_type_matrix<_String,_Flag>::set(size_t row, size_t col, string_type* str)
1157
{
1158
set_string(row, col, str);
1159
}
1160
1161
template<typename _String, typename _Flag>
1162
typename quad_type_matrix<_String,_Flag>::size_pair_type
1163
quad_type_matrix<_String,_Flag>::size() const
1164
{
1165
size_pair_type size_pair(mp_storage->rows(), mp_storage->cols());
1166
return size_pair;
1167
}
1168
1169
template<typename _String, typename _Flag>
1170
quad_type_matrix<_String,_Flag>&
1171
quad_type_matrix<_String,_Flag>::transpose()
1172
{
1173
mp_storage->transpose();
1174
return *this;
1175
}
1176
1177
template<typename _String, typename _Flag>
1178
void quad_type_matrix<_String,_Flag>::assign(const quad_type_matrix& r)
1179
{
1180
if (this == &r)
1181
// assignment to self.
1182
return;
1183
1184
size_t row_count = ::std::min(mp_storage->rows(), r.mp_storage->rows());
1185
size_t col_count = ::std::min(mp_storage->cols(), r.mp_storage->cols());
1186
for (size_t i = 0; i < row_count; ++i)
1187
for (size_t j = 0; j < col_count; ++j)
1188
mp_storage->get_element(i, j) = r.mp_storage->get_element(i, j);
1189
}
1190
1191
template<typename _String, typename _Flag>
1192
void quad_type_matrix<_String,_Flag>::resize(size_t row, size_t col)
1193
{
1194
mp_storage->resize(row, col);
1195
}
1196
1197
template<typename _String, typename _Flag>
1198
void quad_type_matrix<_String,_Flag>::clear()
1199
{
1200
mp_storage->clear();
1201
}
1202
1203
template<typename _String, typename _Flag>
1204
bool quad_type_matrix<_String,_Flag>::numeric() const
1205
{
1206
return mp_storage->numeric();
1207
}
1208
1209
template<typename _String, typename _Flag>
1210
bool quad_type_matrix<_String,_Flag>::empty() const
1211
{
1212
return mp_storage->empty();
1213
}
1214
1215
template<typename _String, typename _Flag>
1216
void quad_type_matrix<_String,_Flag>::swap(quad_type_matrix& r)
1217
{
1218
::std::swap(mp_storage, r.mp_storage);
1219
}
1220
1221
#ifdef UNIT_TEST
1222
template<typename _String, typename _Flag>
1223
void quad_type_matrix<_String,_Flag>::dump() const
1224
{
1225
using namespace std;
1226
size_t rows = mp_storage->rows(), cols = mp_storage->cols();
1227
cout << "rows: " << mp_storage->rows() << " cols: " << mp_storage->cols() << endl;
1228
for (size_t i = 0; i < rows; ++i)
1229
{
1230
cout << "row " << i << ": ";
1231
for (size_t j = 0; j < cols; ++j)
1232
{
1233
matrix_element_t etype = mp_storage->get_type(i, j);
1234
if (j > 0)
1235
cout << ", ";
1236
cout << "(col " << j << ": ";
1237
switch (etype)
1238
{
1239
case element_boolean:
1240
cout << boolalpha << mp_storage->get_boolean(i, j) << noboolalpha;
1241
break;
1242
case element_empty:
1243
cout << "-";
1244
break;
1245
case element_numeric:
1246
cout << mp_storage->get_numeric(i, j);
1247
break;
1248
case element_string:
1249
cout << "'" << mp_storage->get_string(i, j) << "'";
1250
break;
1251
default:
1252
;
1253
}
1254
cout << ")";
1255
}
1256
cout << endl;
1257
}
1258
}
1259
1260
template<typename _String, typename _Flag>
1261
void quad_type_matrix<_String,_Flag>::dump_flags() const
1262
{
1263
mp_storage->get_flag_storage().dump();
1264
}
1265
#endif
1266
1267
}
1268
1269
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1