← Back to branch summary

~ubuntu-branches/ubuntu/raring/mdds/raring

« back to all changes in this revision

Viewing changes to include/mdds/mixed_type_matrix_storage.hpp

  • 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

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/mdds/mixed_type_matrix_storage.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_MIXED_TYPE_MATRIX_STORAGE_HPP__
 
29
#define __MDDS_MIXED_TYPE_MATRIX_STORAGE_HPP__
 
30
 
 
31
#include <cassert>
 
32
 
 
33
#include <boost/ptr_container/ptr_vector.hpp>
 
34
#include <boost/ptr_container/ptr_map.hpp>
 
35
 
 
36
namespace mdds {
 
37
 
 
38
enum matrix_storage_t
 
39
{
 
40
    matrix_storage_filled,
 
41
    matrix_storage_sparse
 
42
};
 
43
 
 
44
enum matrix_init_element_t
 
45
{
 
46
    matrix_init_element_zero,
 
47
    matrix_init_element_empty
 
48
};
 
49
 
 
50
class matrix_storage_error : public ::mdds::general_error
 
51
{
 
52
public:
 
53
    matrix_storage_error(const ::std::string& msg) : general_error(msg) {}
 
54
};
 
55
 
 
56
/**
 
57
 * Wrapper class that provides access to the storage internals.  This is 
 
58
 * used by storage_base::const_iterator to traverse data in different 
 
59
 * storage backends. 
 
60
 */
 
61
template<typename _StoreType, typename _ElemWrap, typename _RowsWrap>
 
62
class const_itr_access
 
63
{
 
64
    typedef _StoreType  store_type;
 
65
    typedef _ElemWrap   element_wrap_type;
 
66
    typedef _RowsWrap   rows_wrap_type;
 
67
public:
 
68
    typedef typename _StoreType::element element;
 
69
 
 
70
    const_itr_access(const store_type& db) : 
 
71
        m_db(db), 
 
72
        m_rows_itr(db.get_rows().begin()),
 
73
        m_rows_itr_end(db.get_rows().end())
 
74
    {
 
75
        // create iterators for the first row.
 
76
        if (!empty())
 
77
            update_row_itr();
 
78
    }
 
79
 
 
80
    const_itr_access(const const_itr_access& r) :
 
81
        m_db(r.m_db),
 
82
        m_rows_itr(r.m_rows_itr),
 
83
        m_rows_itr_end(r.m_rows_itr_end),
 
84
        m_row_itr(r.m_row_itr),
 
85
        m_row_itr_end(r.m_row_itr_end) {}
 
86
 
 
87
    /**
 
88
     * Set the current iterator position to the end position.
 
89
     */
 
90
    void set_to_end()
 
91
    {
 
92
        if (empty())
 
93
            return;
 
94
 
 
95
        m_rows_itr = m_rows_itr_end;
 
96
        typename store_type::rows_type::const_iterator itr = m_rows_itr_end;
 
97
        --itr; // Move to the last row.
 
98
 
 
99
        // They both need to be at the end position of the last row.
 
100
        m_row_itr = m_row_itr_end = m_rows_wrap(itr).end();
 
101
    }
 
102
 
 
103
    bool operator== (const const_itr_access& r) const
 
104
    {
 
105
        if (&m_db != &r.m_db)
 
106
            // different storage instances.
 
107
            return false;
 
108
 
 
109
        if (empty())
 
110
            return r.empty();
 
111
 
 
112
        if (m_rows_itr != r.m_rows_itr)
 
113
            return false;
 
114
 
 
115
        // If the rows iterators are equal, the end positions should be equal
 
116
        // too.  No need to check it.
 
117
        assert(m_rows_itr_end == r.m_rows_itr_end);
 
118
 
 
119
        if (m_row_itr != r.m_row_itr)
 
120
            return false;
 
121
 
 
122
        // Same assumption holds here too. See above.
 
123
        assert(m_row_itr_end == r.m_row_itr_end);
 
124
        return true;
 
125
    }
 
126
 
 
127
    bool empty() const { return m_db.get_rows().begin() == m_rows_itr_end; }
 
128
 
 
129
    void update_row_itr()
 
130
    {
 
131
        m_row_itr = m_rows_wrap(m_rows_itr).begin();
 
132
        m_row_itr_end = m_rows_wrap(m_rows_itr).end();
 
133
    }
 
134
 
 
135
    const element& get() const { return m_wrap(m_row_itr); }
 
136
 
 
137
    bool inc()
 
138
    {
 
139
        if (m_row_itr == m_row_itr_end)
 
140
            return false;
 
141
 
 
142
        ++m_row_itr;
 
143
        if (m_row_itr == m_row_itr_end)
 
144
        {    
 
145
            // Move to the next row.
 
146
            if (m_rows_itr != m_rows_itr_end)
 
147
            {
 
148
                ++m_rows_itr;
 
149
                if (m_rows_itr == m_rows_itr_end)
 
150
                    // no more rows.
 
151
                    return false;
 
152
                update_row_itr();
 
153
            }
 
154
        }
 
155
        return true;
 
156
    }
 
157
 
 
158
    bool dec()
 
159
    {
 
160
        if (m_rows_itr == m_rows_itr_end)
 
161
        {
 
162
            --m_rows_itr;
 
163
            assert(m_row_itr == m_row_itr_end);
 
164
            --m_row_itr;
 
165
            return true;
 
166
        }
 
167
 
 
168
        if (m_row_itr == m_rows_wrap(m_rows_itr).begin())
 
169
        {
 
170
            // On the first element of a row.
 
171
            if (m_rows_itr == m_db.get_rows().begin())
 
172
                // already on the first row. 
 
173
                return false;
 
174
 
 
175
            // Move up to the previous row, and select its last element.
 
176
            --m_rows_itr;
 
177
            assert(!m_rows_wrap(m_rows_itr).empty());
 
178
            m_row_itr_end = m_rows_wrap(m_rows_itr).end();
 
179
            m_row_itr = m_row_itr_end;
 
180
            --m_row_itr;
 
181
            return true;
 
182
        }
 
183
 
 
184
        // Not on the first element of a row.
 
185
        --m_row_itr;
 
186
        return true;
 
187
    }
 
188
 
 
189
private:
 
190
    const store_type& m_db;
 
191
    typename store_type::rows_type::const_iterator m_rows_itr;
 
192
    typename store_type::rows_type::const_iterator m_rows_itr_end;
 
193
    typename store_type::row_type::const_iterator m_row_itr;
 
194
    typename store_type::row_type::const_iterator m_row_itr_end;
 
195
    element_wrap_type m_wrap;
 
196
    rows_wrap_type m_rows_wrap;
 
197
};
 
198
 
 
199
template<typename _MatrixType>
 
200
class storage_base
 
201
{
 
202
public:
 
203
    typedef _MatrixType matrix_type;
 
204
 
 
205
    typedef typename _MatrixType::element               element;
 
206
    typedef typename _MatrixType::flag_storage          flag_storage;
 
207
    typedef typename _MatrixType::string_type           string_type;
 
208
    typedef typename _MatrixType::filled_storage_type   filled_storage_type;
 
209
    typedef typename _MatrixType::sparse_storage_type   sparse_storage_type;
 
210
 
 
211
    class const_iterator
 
212
    {
 
213
        typedef typename filled_storage_type::const_itr_access filled_access_type;
 
214
        typedef typename sparse_storage_type::const_itr_access sparse_access_type;
 
215
    public:
 
216
        // iterator traits
 
217
        typedef element     value_type;
 
218
        typedef element*    pointer;
 
219
        typedef element&    reference;
 
220
        typedef ptrdiff_t   difference_type;
 
221
        typedef ::std::bidirectional_iterator_tag   iterator_category;
 
222
 
 
223
        const_iterator() : 
 
224
            m_const_itr_access(NULL), m_type(matrix_storage_filled)
 
225
        {}
 
226
 
 
227
        const_iterator(void* p, matrix_storage_t type, bool _end = false) : 
 
228
            m_const_itr_access(p), m_type(type)
 
229
        {
 
230
            assert(p != NULL);
 
231
            if (_end)
 
232
            {
 
233
                switch (m_type)
 
234
                {
 
235
                    case matrix_storage_filled:
 
236
                        get_filled_itr()->set_to_end();
 
237
                    break;
 
238
                    case matrix_storage_sparse:
 
239
                        get_sparse_itr()->set_to_end();
 
240
                    break;
 
241
                    default:
 
242
                        assert(!"unknown storage type");
 
243
                }
 
244
            }
 
245
        }
 
246
 
 
247
        const_iterator(const const_iterator& r) :
 
248
            m_const_itr_access(NULL),
 
249
            m_type(r.m_type)
 
250
        {
 
251
            if (!r.m_const_itr_access)
 
252
                return;
 
253
 
 
254
            switch (r.m_type)
 
255
            {
 
256
                case matrix_storage_filled:
 
257
                    m_const_itr_access = new filled_access_type(*r.get_filled_itr());
 
258
                break;
 
259
                case matrix_storage_sparse:
 
260
                    m_const_itr_access = new sparse_access_type(*r.get_sparse_itr());
 
261
                break;
 
262
                default:
 
263
                    assert(!"unknown storage type");
 
264
            }
 
265
        }
 
266
 
 
267
        ~const_iterator()
 
268
        {
 
269
            switch (m_type)
 
270
            {
 
271
                case matrix_storage_filled:
 
272
                    delete get_filled_itr();
 
273
                break;
 
274
                case matrix_storage_sparse:
 
275
                    delete get_sparse_itr();
 
276
                break;
 
277
                default:
 
278
                    assert(!"unknown storage type");
 
279
            }
 
280
        }
 
281
 
 
282
        void swap(const_iterator& r)
 
283
        {
 
284
            ::std::swap(m_type, r.m_type);
 
285
            ::std::swap(m_const_itr_access, r.m_const_itr_access);
 
286
        }
 
287
 
 
288
        const_iterator& operator=(const const_iterator& r)
 
289
        {
 
290
            if (this == &r)
 
291
                // self assignment.
 
292
                return *this;
 
293
 
 
294
            const_iterator new_itr(r);
 
295
            swap(new_itr);
 
296
            return *this;
 
297
        }
 
298
 
 
299
        const element& operator*() const
 
300
        {
 
301
            switch (m_type)
 
302
            {
 
303
                case matrix_storage_filled:
 
304
                    return get_filled_itr()->get();
 
305
                case matrix_storage_sparse:
 
306
                    return get_sparse_itr()->get();
 
307
                default:
 
308
                    assert(!"unknown storage type");
 
309
            }
 
310
            throw matrix_storage_error("unknown storage type");
 
311
        }
 
312
 
 
313
        const element* operator->() const
 
314
        {
 
315
            switch (m_type)
 
316
            {
 
317
                case matrix_storage_filled:
 
318
                    return &get_filled_itr()->get();
 
319
                case matrix_storage_sparse:
 
320
                    return &get_sparse_itr()->get();
 
321
                default:
 
322
                    assert(!"unknown storage type");
 
323
            }
 
324
            return NULL;
 
325
        }
 
326
 
 
327
        const element* operator++()
 
328
        {
 
329
            bool has_next = false;
 
330
            switch (m_type)
 
331
            {
 
332
                case matrix_storage_filled:
 
333
                    has_next = get_filled_itr()->inc();
 
334
                break;
 
335
                case matrix_storage_sparse:
 
336
                    has_next = get_sparse_itr()->inc();
 
337
                break;
 
338
                default:
 
339
                    assert(!"unknown storage type");
 
340
            }
 
341
            return has_next ? operator->() : NULL;
 
342
        }
 
343
 
 
344
        const element* operator--()
 
345
        {
 
346
            bool has_next = false;
 
347
            switch (m_type)
 
348
            {
 
349
                case matrix_storage_filled:
 
350
                    has_next = get_filled_itr()->dec();
 
351
                break;
 
352
                case matrix_storage_sparse:
 
353
                    has_next = get_sparse_itr()->dec();
 
354
                break;
 
355
                default:
 
356
                    assert(!"unknown storage type");
 
357
            }
 
358
            return has_next ? operator->() : NULL;
 
359
        }
 
360
 
 
361
        bool operator== (const const_iterator& r) const
 
362
        {
 
363
            if (m_type != r.m_type)
 
364
                // Types differ.
 
365
                return false;
 
366
 
 
367
            if (!m_const_itr_access)
 
368
                // This instance has empty access.  The other one must be empty too.
 
369
                return r.m_const_itr_access == NULL;
 
370
 
 
371
            assert(m_const_itr_access != NULL);
 
372
            assert(r.m_const_itr_access != NULL);
 
373
 
 
374
            switch (m_type)
 
375
            {
 
376
                case matrix_storage_filled:
 
377
                    return *get_filled_itr() == *r.get_filled_itr();
 
378
                case matrix_storage_sparse:
 
379
                    return *get_sparse_itr() == *r.get_sparse_itr();
 
380
                default:
 
381
                    assert(!"unknown storage type");
 
382
            }
 
383
            return false;
 
384
        }
 
385
 
 
386
        bool operator!= (const const_iterator& r) const
 
387
        {
 
388
            return !operator==(r);
 
389
        }
 
390
 
 
391
    private:
 
392
        filled_access_type* get_filled_itr()
 
393
        {
 
394
            return static_cast<filled_access_type*>(m_const_itr_access);
 
395
        }
 
396
 
 
397
        const filled_access_type* get_filled_itr() const
 
398
        {
 
399
            return static_cast<const filled_access_type*>(m_const_itr_access);
 
400
        }
 
401
 
 
402
        sparse_access_type* get_sparse_itr()
 
403
        {
 
404
            return static_cast<sparse_access_type*>(m_const_itr_access);
 
405
        }
 
406
 
 
407
        const sparse_access_type* get_sparse_itr() const
 
408
        {
 
409
            return static_cast<const sparse_access_type*>(m_const_itr_access);
 
410
        }
 
411
 
 
412
        /**
 
413
         * Stores new'ed instance of const_itr_access of the respective
 
414
         * storage type. TODO: Find out if there is a way to store the
 
415
         * const_itr_access instance in a type-safe way.
 
416
         */
 
417
        void* m_const_itr_access;
 
418
 
 
419
        /**
 
420
         * Matrix storage type which is either filled or sparse.
 
421
         */
 
422
        matrix_storage_t m_type;
 
423
    };
 
424
 
 
425
    storage_base(matrix_storage_t store_type, matrix_init_element_t init) : 
 
426
        m_store_type(store_type), m_init_type(init) {}
 
427
 
 
428
    storage_base(const storage_base& r) : 
 
429
        m_store_type(r.m_store_type), m_init_type(r.m_init_type), m_flags(r.m_flags) {}
 
430
 
 
431
    matrix_storage_t get_storage_type() const { return m_store_type; }
 
432
 
 
433
    /** 
 
434
     * the destructor must remain virtual because the derived classes have 
 
435
     * different sizes.  TODO: Figure out a way to remove the virtual-ness 
 
436
     * without leaking memory. 
 
437
     */ 
 
438
    virtual ~storage_base() {}
 
439
 
 
440
    const_iterator begin() const
 
441
    {
 
442
        switch (m_store_type)
 
443
        {
 
444
            case matrix_storage_filled:
 
445
            {
 
446
                void* p = static_cast<const filled_storage_type*>(this)->get_const_itr_access();
 
447
                return const_iterator(p, m_store_type);
 
448
            }
 
449
            break;
 
450
            case matrix_storage_sparse:
 
451
            {
 
452
                void* p = static_cast<const sparse_storage_type*>(this)->get_const_itr_access();
 
453
                return const_iterator(p, m_store_type);
 
454
            }
 
455
            break;
 
456
            default:
 
457
                assert(!"unknown storage type");
 
458
        }
 
459
        throw matrix_storage_error("unknown storage type");
 
460
    }
 
461
 
 
462
    const_iterator end() const
 
463
    {
 
464
        switch (m_store_type)
 
465
        {
 
466
            case matrix_storage_filled:
 
467
            {
 
468
                void* p = static_cast<const filled_storage_type*>(this)->get_const_itr_access();
 
469
                return const_iterator(p, m_store_type, true);
 
470
            }
 
471
            break;
 
472
            case matrix_storage_sparse:
 
473
            {
 
474
                void* p = static_cast<const sparse_storage_type*>(this)->get_const_itr_access();
 
475
                return const_iterator(p, m_store_type, true);
 
476
            }
 
477
            break;
 
478
            default:
 
479
                assert(!"unknown storage type");
 
480
        }
 
481
        throw matrix_storage_error("unknown storage type");
 
482
    }
 
483
 
 
484
    element& get_element(size_t row, size_t col)
 
485
    {
 
486
        switch (m_store_type)
 
487
        {
 
488
            case matrix_storage_filled:
 
489
                return static_cast<filled_storage_type*>(this)->get_element(row, col);
 
490
            case matrix_storage_sparse:
 
491
                return static_cast<sparse_storage_type*>(this)->get_element(row, col);
 
492
            default:
 
493
                assert(!"unknown storage type");
 
494
        }
 
495
        throw matrix_storage_error("unknown storage type");
 
496
    }
 
497
 
 
498
    matrix_element_t get_type(size_t row, size_t col) const
 
499
    {
 
500
        switch (m_store_type)
 
501
        {
 
502
            case matrix_storage_filled:
 
503
                return static_cast<const filled_storage_type*>(this)->get_type(row, col);
 
504
            case matrix_storage_sparse:
 
505
                return static_cast<const sparse_storage_type*>(this)->get_type(row, col);
 
506
            default:
 
507
                assert(!"unknown storage type");
 
508
        }
 
509
        throw matrix_storage_error("unknown storage type");
 
510
    }
 
511
 
 
512
    double get_numeric(size_t row, size_t col) const
 
513
    {
 
514
        switch (m_store_type)
 
515
        {
 
516
            case matrix_storage_filled:
 
517
                return static_cast<const filled_storage_type*>(this)->get_numeric(row, col);
 
518
            case matrix_storage_sparse:
 
519
                return static_cast<const sparse_storage_type*>(this)->get_numeric(row, col);
 
520
            default:
 
521
                assert(!"unknown storage type");
 
522
        }
 
523
        throw matrix_storage_error("unknown storage type");
 
524
    }
 
525
 
 
526
    const string_type* get_string(size_t row, size_t col) const
 
527
    {
 
528
        switch (m_store_type)
 
529
        {
 
530
            case matrix_storage_filled:
 
531
                return static_cast<const filled_storage_type*>(this)->get_string(row, col);
 
532
            case matrix_storage_sparse:
 
533
                return static_cast<const sparse_storage_type*>(this)->get_string(row, col);
 
534
            default:
 
535
                assert(!"unknown storage type");
 
536
        }
 
537
        throw matrix_storage_error("unknown storage type");
 
538
    }
 
539
 
 
540
    bool get_boolean(size_t row, size_t col) const
 
541
    {
 
542
        switch (m_store_type)
 
543
        {
 
544
            case matrix_storage_filled:
 
545
                return static_cast<const filled_storage_type*>(this)->get_boolean(row, col);
 
546
            case matrix_storage_sparse:
 
547
                return static_cast<const sparse_storage_type*>(this)->get_boolean(row, col);
 
548
            default:
 
549
                assert(!"unknown storage type");
 
550
        }
 
551
        throw matrix_storage_error("unknown storage type");
 
552
    }
 
553
 
 
554
    size_t rows() const
 
555
    {
 
556
        switch (m_store_type)
 
557
        {
 
558
            case matrix_storage_filled:
 
559
                return static_cast<const filled_storage_type*>(this)->rows();
 
560
            case matrix_storage_sparse:
 
561
                return static_cast<const sparse_storage_type*>(this)->rows();
 
562
            default:
 
563
                assert(!"unknown storage type");
 
564
        }
 
565
        throw matrix_storage_error("unknown storage type");
 
566
    }
 
567
 
 
568
    size_t cols() const
 
569
    {
 
570
        switch (m_store_type)
 
571
        {
 
572
            case matrix_storage_filled:
 
573
                return static_cast<const filled_storage_type*>(this)->cols();
 
574
            case matrix_storage_sparse:
 
575
                return static_cast<const sparse_storage_type*>(this)->cols();
 
576
            default:
 
577
                assert(!"unknown storage type");
 
578
        }
 
579
        throw matrix_storage_error("unknown storage type");
 
580
    }
 
581
 
 
582
    void transpose()
 
583
    {
 
584
        switch (m_store_type)
 
585
        {
 
586
            case matrix_storage_filled:
 
587
                static_cast<filled_storage_type*>(this)->transpose();
 
588
            break;
 
589
            case matrix_storage_sparse:
 
590
                static_cast<sparse_storage_type*>(this)->transpose();
 
591
            break;
 
592
            default:
 
593
                assert(!"unknown storage type");
 
594
        }
 
595
    }
 
596
 
 
597
    void resize(size_t row, size_t col)
 
598
    {
 
599
        switch (m_store_type)
 
600
        {
 
601
            case matrix_storage_filled:
 
602
                static_cast<filled_storage_type*>(this)->resize(row, col);
 
603
            break;
 
604
            case matrix_storage_sparse:
 
605
                static_cast<sparse_storage_type*>(this)->resize(row, col);
 
606
            break;
 
607
            default:
 
608
                assert(!"unknown storage type");
 
609
        }
 
610
    }
 
611
 
 
612
    void clear()
 
613
    {
 
614
        switch (m_store_type)
 
615
        {
 
616
            case matrix_storage_filled:
 
617
                static_cast<filled_storage_type*>(this)->clear();
 
618
            break;
 
619
            case matrix_storage_sparse:
 
620
                static_cast<sparse_storage_type*>(this)->clear();
 
621
            break;
 
622
            default:
 
623
                assert(!"unknown storage type");
 
624
        }
 
625
    }
 
626
 
 
627
    bool numeric()
 
628
    {
 
629
        switch (m_store_type)
 
630
        {
 
631
            case matrix_storage_filled:
 
632
                return static_cast<filled_storage_type*>(this)->numeric();
 
633
            case matrix_storage_sparse:
 
634
                return static_cast<sparse_storage_type*>(this)->numeric();
 
635
            default:
 
636
                assert(!"unknown storage type");
 
637
        }
 
638
        throw matrix_storage_error("unknown storage type");
 
639
    }
 
640
 
 
641
    bool empty() const
 
642
    {
 
643
        switch (m_store_type)
 
644
        {
 
645
            case matrix_storage_filled:
 
646
                return static_cast<const filled_storage_type*>(this)->empty();
 
647
            case matrix_storage_sparse:
 
648
                return static_cast<const sparse_storage_type*>(this)->empty();
 
649
            default:
 
650
                assert(!"unknown storage type");
 
651
        }
 
652
        throw matrix_storage_error("unknown storage type");
 
653
    }
 
654
 
 
655
    storage_base* clone() const
 
656
    {
 
657
        switch (m_store_type)
 
658
        {
 
659
            case matrix_storage_filled:
 
660
                return static_cast<const filled_storage_type*>(this)->clone();
 
661
            case matrix_storage_sparse:
 
662
                return static_cast<const sparse_storage_type*>(this)->clone();
 
663
            default:
 
664
                assert(!"unknown storage type");
 
665
        }
 
666
        throw matrix_storage_error("unknown storage type");
 
667
    }
 
668
 
 
669
    flag_storage& get_flag_storage() { return m_flags; }
 
670
 
 
671
protected:
 
672
    matrix_init_element_t get_init_type() const { return m_init_type; }
 
673
 
 
674
private:
 
675
    matrix_storage_t        m_store_type;
 
676
    matrix_init_element_t   m_init_type;
 
677
    flag_storage            m_flags;
 
678
};
 
679
 
 
680
/**
 
681
 * This storage creates instance for every single element, even for the
 
682
 * empty elements. 
 
683
 */
 
684
template<typename _MatrixType>
 
685
class storage_filled : public ::mdds::storage_base<_MatrixType>
 
686
{
 
687
    typedef _MatrixType matrix_type;
 
688
    typedef typename matrix_type::string_type   string_type;
 
689
 
 
690
public:
 
691
    typedef typename matrix_type::element element;
 
692
    typedef ::boost::ptr_vector<element>  row_type;
 
693
    typedef ::boost::ptr_vector<row_type> rows_type;
 
694
 
 
695
    struct elem_wrap
 
696
    {
 
697
        const element& operator() (const typename row_type::const_iterator& itr) const 
 
698
        { 
 
699
            return *itr; 
 
700
        }
 
701
    };
 
702
    struct rows_wrap
 
703
    {
 
704
        const row_type& operator() (const typename rows_type::const_iterator& itr) const
 
705
        { 
 
706
            return *itr;
 
707
        }
 
708
    };
 
709
    typedef ::mdds::const_itr_access<storage_filled, elem_wrap, rows_wrap> const_itr_access;
 
710
 
 
711
    storage_filled(size_t _rows, size_t _cols, matrix_init_element_t init_type) :
 
712
        storage_base<matrix_type>(matrix_storage_filled, init_type),
 
713
        m_numeric(false),
 
714
        m_valid(false)
 
715
    {
 
716
        m_rows.reserve(_rows);
 
717
        for (size_t i = 0; i < _rows; ++i)
 
718
        {
 
719
            m_rows.push_back(new row_type);
 
720
            init_row(m_rows.back(), _cols);
 
721
        }
 
722
    }
 
723
 
 
724
    storage_filled(const storage_filled& r) :
 
725
        storage_base<matrix_type>(r),
 
726
        m_rows(r.m_rows),
 
727
        m_numeric(r.m_numeric),
 
728
        m_valid(r.m_valid) {}
 
729
 
 
730
    virtual ~storage_filled() {}
 
731
 
 
732
    const_itr_access* get_const_itr_access() const
 
733
    {
 
734
        return new const_itr_access(*this);
 
735
    }
 
736
 
 
737
    element& get_element(size_t row, size_t col)
 
738
    {
 
739
        m_valid = false;
 
740
        return m_rows.at(row).at(col);
 
741
    }
 
742
 
 
743
    matrix_element_t get_type(size_t row, size_t col) const
 
744
    {
 
745
        return m_rows.at(row).at(col).m_type;
 
746
    }
 
747
 
 
748
    double get_numeric(size_t row, size_t col) const
 
749
    {
 
750
        const element& elem = m_rows.at(row).at(col);
 
751
        switch (elem.m_type)
 
752
        {
 
753
            case element_numeric:
 
754
                return elem.m_numeric;
 
755
            case element_boolean:
 
756
                return static_cast<double>(elem.m_boolean);
 
757
            case element_empty:
 
758
            default:
 
759
                ;
 
760
        }
 
761
        return 0.0;
 
762
    }
 
763
 
 
764
    const string_type* get_string(size_t row, size_t col) const
 
765
    {
 
766
        const element& elem = m_rows.at(row).at(col);
 
767
        if (elem.m_type != element_string)
 
768
            throw matrix_storage_error("element type is not string.");
 
769
 
 
770
        return elem.mp_string;
 
771
    }
 
772
 
 
773
    bool get_boolean(size_t row, size_t col) const
 
774
    {
 
775
        const element& elem = m_rows.at(row).at(col);
 
776
        if (elem.m_type != element_boolean)
 
777
            throw matrix_storage_error("element type is not boolean.");
 
778
 
 
779
        return elem.m_boolean;
 
780
    }
 
781
 
 
782
    size_t rows() const
 
783
    {
 
784
        return m_rows.size();
 
785
    }
 
786
 
 
787
    size_t cols() const
 
788
    {
 
789
        return m_rows.empty() ? 0 : m_rows[0].size();
 
790
    }
 
791
 
 
792
    void transpose()
 
793
    {
 
794
        rows_type trans_mx;
 
795
        size_t row_size = rows(), col_size = cols();
 
796
        trans_mx.reserve(col_size);
 
797
        for (size_t col = 0; col < col_size; ++col)
 
798
        {
 
799
            trans_mx.push_back(new row_type);
 
800
            row_type& trans_row = trans_mx.back();
 
801
            trans_row.reserve(row_size);
 
802
            for (size_t row = 0; row < row_size; ++row)
 
803
                trans_row.push_back(new element(m_rows[row][col]));
 
804
        }
 
805
        m_rows.swap(trans_mx);
 
806
    }
 
807
 
 
808
    void resize(size_t row, size_t col)
 
809
    {
 
810
        m_valid = false;
 
811
        if (!row || !col)
 
812
        {
 
813
            // Empty the matrix.
 
814
            clear();
 
815
            return;
 
816
        }
 
817
 
 
818
        size_t cur_rows = rows(), cur_cols = cols();
 
819
 
 
820
        if (!cur_rows || !cur_cols)
 
821
        {
 
822
            // current matrix is empty.
 
823
            rows_type new_rows;
 
824
            new_rows.reserve(row);
 
825
            for (size_t i = 0; i < row; ++i)
 
826
            {
 
827
                new_rows.push_back(new row_type);
 
828
                init_row(new_rows.back(), col);
 
829
            }
 
830
            m_rows.swap(new_rows);
 
831
            return;
 
832
        }
 
833
 
 
834
        if (row > cur_rows)
 
835
        {
 
836
            // Insert extra rows...
 
837
            size_t new_row_count = row - cur_rows;
 
838
            m_rows.reserve(row);
 
839
            for (size_t i = 0; i < new_row_count; ++i)
 
840
            {
 
841
                m_rows.push_back(new row_type);
 
842
                init_row(m_rows.back(), col);
 
843
            }
 
844
 
 
845
            resize_rows(cur_rows-1, cur_cols, col);
 
846
        }
 
847
        else if (cur_rows > row)
 
848
        {
 
849
            // Remove rows to new size.
 
850
            m_rows.resize(row);
 
851
            resize_rows(row-1, cur_cols, col);
 
852
        }
 
853
        else
 
854
        {
 
855
            assert(cur_rows == row);
 
856
            resize_rows(cur_rows-1, cur_cols, col);
 
857
        }
 
858
    }
 
859
 
 
860
    void clear()
 
861
    {
 
862
        m_rows.clear();
 
863
        m_valid = true;
 
864
        m_numeric = false;
 
865
    }
 
866
 
 
867
    bool numeric()
 
868
    {
 
869
        if (m_valid)
 
870
            return m_numeric;
 
871
 
 
872
        typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end();
 
873
        for (; itr_row != itr_row_end; ++itr_row)
 
874
        {
 
875
            typename row_type::const_iterator itr_col = itr_row->begin(), itr_col_end = itr_row->end();
 
876
            for (; itr_col != itr_col_end; ++itr_col)
 
877
            {
 
878
                matrix_element_t elem_type = itr_col->m_type;
 
879
                if (elem_type != element_numeric && elem_type != element_boolean)
 
880
                {
 
881
                    m_numeric = false;
 
882
                    m_valid = true;
 
883
                    return m_numeric;
 
884
                }
 
885
            }
 
886
        }
 
887
 
 
888
        m_numeric = true;
 
889
        m_valid = true;
 
890
        return m_numeric;
 
891
    }
 
892
 
 
893
    bool empty() const
 
894
    {
 
895
        return m_rows.empty();
 
896
    }
 
897
 
 
898
    ::mdds::storage_base<matrix_type>* clone() const
 
899
    {
 
900
        return new storage_filled(*this);
 
901
    }
 
902
 
 
903
    const rows_type& get_rows() const { return m_rows; }
 
904
 
 
905
private:
 
906
 
 
907
    /**
 
908
     * Resize rows to a new column size, from row 0 up to specified upper 
 
909
     * row. 
 
910
     */
 
911
    void resize_rows(size_t upper_row, size_t cur_cols, size_t new_cols)
 
912
    {
 
913
        for (size_t i = 0; i <= upper_row; ++i)
 
914
        {
 
915
            // Resize pre-existing rows to new column size.
 
916
            if (new_cols > cur_cols)
 
917
            {
 
918
                size_t new_col_count = new_cols - cur_cols;
 
919
                for (size_t j = 0; j < new_col_count; ++j)
 
920
                    insert_new_elem(m_rows[i]);
 
921
            }
 
922
            else if (new_cols < cur_cols)
 
923
                m_rows[i].resize(new_cols);
 
924
        }
 
925
    }
 
926
 
 
927
    void init_row(row_type& row, size_t col_size)
 
928
    {
 
929
        row.reserve(col_size);
 
930
        for (size_t j = 0; j < col_size; ++j)
 
931
            insert_new_elem(row);
 
932
    }
 
933
 
 
934
    void insert_new_elem(row_type& row)
 
935
    {
 
936
        matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type();
 
937
        switch (init_type)
 
938
        {
 
939
            case matrix_init_element_zero:
 
940
                row.push_back(new element(static_cast<double>(0.0)));
 
941
            break;
 
942
            case matrix_init_element_empty:
 
943
                row.push_back(new element);
 
944
            break;
 
945
            default:
 
946
                throw matrix_storage_error("unknown init type.");
 
947
        }
 
948
    }
 
949
 
 
950
private:
 
951
    rows_type m_rows;
 
952
    bool m_numeric:1;
 
953
    bool m_valid:1;
 
954
};
 
955
 
 
956
/**
 
957
 * This storage stores only non-empty elements. 
 
958
 */
 
959
template<typename _MatrixType>
 
960
class storage_sparse : public storage_base<_MatrixType>
 
961
{
 
962
    typedef _MatrixType matrix_type;
 
963
 
 
964
    typedef typename matrix_type::string_type  string_type;
 
965
 
 
966
public:
 
967
    typedef typename matrix_type::element      element;
 
968
    typedef ::boost::ptr_map<size_t, element>  row_type;
 
969
    typedef ::boost::ptr_map<size_t, row_type> rows_type;
 
970
    struct elem_wrap
 
971
    {
 
972
        const element& operator() (const typename row_type::const_iterator& itr) const
 
973
        {
 
974
            return *itr->second;
 
975
        }
 
976
    };
 
977
    struct rows_wrap
 
978
    {
 
979
        const row_type& operator() (const typename rows_type::const_iterator& itr) const
 
980
        {
 
981
            return *itr->second;
 
982
        }
 
983
    };
 
984
    typedef ::mdds::const_itr_access<storage_sparse, elem_wrap, rows_wrap> const_itr_access;
 
985
 
 
986
    storage_sparse(size_t _rows, size_t _cols, matrix_init_element_t init_type) : 
 
987
        storage_base<matrix_type>(matrix_storage_sparse, init_type),
 
988
        m_row_size(_rows), m_col_size(_cols),
 
989
        m_numeric(_rows && _cols), m_valid(true)
 
990
    {
 
991
        switch (storage_base<matrix_type>::get_init_type())
 
992
        {
 
993
            case matrix_init_element_zero:
 
994
                m_empty_elem.m_type = element_numeric;
 
995
                m_empty_elem.m_numeric = 0.0;
 
996
            break;
 
997
            default:
 
998
                m_empty_elem.m_type = element_empty;
 
999
                m_numeric = false;
 
1000
        }
 
1001
    }
 
1002
 
 
1003
    storage_sparse(const storage_sparse& r) :
 
1004
        storage_base<matrix_type>(r),
 
1005
        m_rows(r.m_rows), 
 
1006
        m_empty_elem(r.m_empty_elem), 
 
1007
        m_row_size(r.m_row_size), 
 
1008
        m_col_size(r.m_col_size) {}
 
1009
 
 
1010
    virtual ~storage_sparse() {}
 
1011
 
 
1012
    const_itr_access* get_const_itr_access() const { return new const_itr_access(*this); }
 
1013
 
 
1014
    element & get_element(size_t row, size_t col)
 
1015
    {
 
1016
        if (row >= m_row_size || col >= m_col_size)
 
1017
            throw matrix_storage_error("specified element is out-of-bound.");
 
1018
 
 
1019
        m_valid = false;
 
1020
 
 
1021
        typename rows_type::iterator itr = m_rows.find(row);
 
1022
        if (itr == m_rows.end())
 
1023
        {
 
1024
            // Insert a brand-new row.
 
1025
            ::std::pair<typename rows_type::iterator, bool> r = m_rows.insert(row, new row_type);
 
1026
            if (!r.second)
 
1027
                throw matrix_storage_error("failed to insert a new row instance into storage_sparse.");
 
1028
            itr = r.first;
 
1029
        }
 
1030
 
 
1031
        row_type& row_store = *itr->second;
 
1032
        typename row_type::iterator itr_elem = row_store.find(col);
 
1033
        if (itr_elem == row_store.end())
 
1034
        {
 
1035
            // Insert a new element at this column position.
 
1036
            ::std::pair<typename row_type::iterator, bool> r = row_store.insert(col, new element);
 
1037
            if (!r.second)
 
1038
                throw matrix_storage_error("failed to insert a new element instance.");
 
1039
            itr_elem = r.first;
 
1040
        }
 
1041
        return *itr_elem->second;
 
1042
    }
 
1043
 
 
1044
    matrix_element_t get_type(size_t row, size_t col) const
 
1045
    {
 
1046
        typename rows_type::const_iterator itr = m_rows.find(row);
 
1047
        if (itr == m_rows.end())
 
1048
            return m_empty_elem.m_type;
 
1049
 
 
1050
        const row_type& row_store = *itr->second;
 
1051
        typename row_type::const_iterator itr_elem = row_store.find(col);
 
1052
        if (itr_elem == row_store.end())
 
1053
            return m_empty_elem.m_type;
 
1054
 
 
1055
        return itr_elem->second->m_type;
 
1056
    }
 
1057
 
 
1058
    double get_numeric(size_t row, size_t col) const
 
1059
    {
 
1060
        const element& elem = get_non_empty_element(row, col);
 
1061
        switch (elem.m_type)
 
1062
        {
 
1063
            case element_numeric:
 
1064
                return elem.m_numeric;
 
1065
            case element_boolean:
 
1066
                return static_cast<double>(elem.m_boolean);
 
1067
            case element_empty:
 
1068
            default:
 
1069
                ;
 
1070
        }
 
1071
        return 0.0;
 
1072
    }
 
1073
 
 
1074
    const string_type* get_string(size_t row, size_t col) const
 
1075
    {
 
1076
        matrix_element_t elem_type = get_type(row, col);
 
1077
        if (elem_type != element_string)
 
1078
            throw matrix_storage_error("element type is not string.");
 
1079
 
 
1080
        return get_non_empty_element(row, col).mp_string;
 
1081
    }
 
1082
 
 
1083
    bool get_boolean(size_t row, size_t col) const
 
1084
    {
 
1085
        matrix_element_t elem_type = get_type(row, col);
 
1086
        if (elem_type != element_boolean)
 
1087
            throw matrix_storage_error("element type is not string.");
 
1088
 
 
1089
        return get_non_empty_element(row, col).m_boolean;
 
1090
    }
 
1091
 
 
1092
    size_t rows() const
 
1093
    {
 
1094
        return m_row_size;
 
1095
    }
 
1096
 
 
1097
    size_t cols() const
 
1098
    {
 
1099
        return m_col_size;
 
1100
    }
 
1101
 
 
1102
    typedef ::std::pair<size_t, size_t> elem_pos_type;
 
1103
 
 
1104
    struct elem_pos_sorter : public ::std::binary_function<elem_pos_type, elem_pos_type, bool>
 
1105
    {
 
1106
        bool operator() (const elem_pos_type& left, const elem_pos_type& right) const
 
1107
        {
 
1108
            if (left.first != right.first)
 
1109
                return left.first < right.first;
 
1110
            return left.second < right.second;
 
1111
        }
 
1112
    };
 
1113
 
 
1114
    void transpose()
 
1115
    {
 
1116
        using namespace std;
 
1117
 
 
1118
        rows_type trans;
 
1119
 
 
1120
        // First, pick up the positions of all non-empty elements.
 
1121
        vector<elem_pos_type> filled_elems;
 
1122
        {
 
1123
            typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end();
 
1124
            for (; itr_row != itr_row_end; ++itr_row)
 
1125
            {
 
1126
                size_t row_idx = itr_row->first;
 
1127
                const row_type& row = *itr_row->second;
 
1128
                typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end();
 
1129
                for (; itr_col != itr_col_end; ++itr_col)
 
1130
                {
 
1131
                    // Be sure to swap the row and column indices.
 
1132
                    filled_elems.push_back(elem_pos_type(itr_col->first, row_idx));
 
1133
                }
 
1134
            }
 
1135
        }
 
1136
        // Sort by row index first, then by column index.
 
1137
        sort(filled_elems.begin(), filled_elems.end(), elem_pos_sorter());
 
1138
 
 
1139
        // Iterate through the non-empty element positions and perform 
 
1140
        // transposition.
 
1141
        typename vector<elem_pos_type>::const_iterator 
 
1142
            itr_pos = filled_elems.begin(), itr_pos_end = filled_elems.end();
 
1143
        while (itr_pos != itr_pos_end)
 
1144
        {
 
1145
            // First item of the new row.
 
1146
            size_t row_idx = itr_pos->first;
 
1147
            size_t col_idx = itr_pos->second;
 
1148
            pair<typename rows_type::iterator, bool> r = trans.insert(row_idx, new row_type);
 
1149
            if (!r.second)
 
1150
                throw matrix_storage_error("failed to insert a new row instance during transposition.");
 
1151
 
 
1152
            typename rows_type::iterator itr_row = r.first;
 
1153
            row_type& row = *itr_row->second;
 
1154
            pair<typename row_type::iterator, bool> r2 = 
 
1155
                row.insert(col_idx, new element(m_rows[col_idx][row_idx]));
 
1156
            if (!r2.second)
 
1157
                throw matrix_storage_error("afiled to insert a new element instance during transposition.");
 
1158
 
 
1159
            // Keep iterating until we get a different row index.
 
1160
            for (++itr_pos; itr_pos != itr_pos_end && itr_pos->first == row_idx; ++itr_pos)
 
1161
            {
 
1162
                col_idx = itr_pos->second;
 
1163
                r2 = row.insert(col_idx, new element(m_rows[col_idx][row_idx]));
 
1164
                if (!r2.second)
 
1165
                    throw matrix_storage_error("afiled to insert a new element instance during transposition.");
 
1166
            }
 
1167
        }
 
1168
 
 
1169
        m_rows.swap(trans);
 
1170
        ::std::swap(m_row_size, m_col_size);
 
1171
    }
 
1172
 
 
1173
    void resize(size_t row, size_t col)
 
1174
    {
 
1175
        m_valid = false;
 
1176
 
 
1177
        if (!row || !col)
 
1178
        {
 
1179
            clear();
 
1180
            return;
 
1181
        }
 
1182
 
 
1183
        // Resizing a sparse matrix need to modify the data only when 
 
1184
        // shrinking.
 
1185
 
 
1186
        if (m_row_size > row)
 
1187
        {
 
1188
            // Remove all rows where the row index is greater than or 
 
1189
            // equal to 'row'.
 
1190
            typename rows_type::iterator itr = m_rows.lower_bound(row);
 
1191
            m_rows.erase(itr, m_rows.end());
 
1192
        }
 
1193
 
 
1194
        if (m_col_size > col)
 
1195
        {
 
1196
            typename rows_type::iterator itr = m_rows.begin(), itr_end = m_rows.end();
 
1197
            for (; itr != itr_end; ++itr)
 
1198
            {
 
1199
                // Now, remove all columns where the column index is 
 
1200
                // greater than or equal to 'col'.
 
1201
                row_type& row_container = *itr->second;
 
1202
                typename row_type::iterator itr_elem = row_container.lower_bound(col);
 
1203
                row_container.erase(itr_elem, row_container.end());
 
1204
            }
 
1205
        }
 
1206
 
 
1207
        m_row_size = row;
 
1208
        m_col_size = col;
 
1209
    }
 
1210
 
 
1211
    void clear()
 
1212
    {
 
1213
        m_rows.clear();
 
1214
        m_row_size = 0;
 
1215
        m_col_size = 0;
 
1216
        m_valid = true;
 
1217
        m_numeric = false;
 
1218
    }
 
1219
 
 
1220
    bool numeric()
 
1221
    {
 
1222
        using namespace std;
 
1223
 
 
1224
        if (m_valid)
 
1225
            return m_numeric;
 
1226
 
 
1227
        size_t non_empty_count = 0;
 
1228
        typename rows_type::const_iterator itr_row = m_rows.begin(), itr_row_end = m_rows.end();
 
1229
        for (; itr_row != itr_row_end; ++itr_row)
 
1230
        {
 
1231
            const row_type& row = *itr_row->second;
 
1232
            non_empty_count += row.size();
 
1233
            assert(row.size() <= m_col_size);
 
1234
            typename row_type::const_iterator itr_col = row.begin(), itr_col_end = row.end();
 
1235
            for (; itr_col != itr_col_end; ++itr_col)
 
1236
            {
 
1237
                const element& elem = *itr_col->second;
 
1238
                if (elem.m_type != element_numeric && elem.m_type != element_boolean)
 
1239
                {
 
1240
                    m_valid = true;
 
1241
                    m_numeric = false;
 
1242
                    return m_numeric;
 
1243
                }
 
1244
            }
 
1245
        }
 
1246
 
 
1247
        // All non-empty elements are numeric.
 
1248
 
 
1249
        matrix_init_element_t init_type = storage_base<matrix_type>::get_init_type();
 
1250
        if (init_type == matrix_init_element_zero)
 
1251
            m_numeric = true;
 
1252
        else
 
1253
        {    
 
1254
            size_t total_elem_count = m_row_size * m_col_size;
 
1255
            assert(non_empty_count <= total_elem_count);
 
1256
            m_numeric = total_elem_count == non_empty_count;
 
1257
        }
 
1258
 
 
1259
        m_valid = true;
 
1260
        return m_numeric;
 
1261
    }
 
1262
 
 
1263
    bool empty() const
 
1264
    {
 
1265
        // If one of row and column sizes are zero, the other size must be
 
1266
        // zero, and vise versa.
 
1267
        assert((!m_row_size && !m_col_size) || (m_row_size && m_col_size));
 
1268
 
 
1269
        return m_row_size == 0 || m_col_size == 0;
 
1270
    }
 
1271
 
 
1272
    storage_base<matrix_type>* clone() const
 
1273
    {
 
1274
        return new storage_sparse(*this);
 
1275
    }
 
1276
 
 
1277
    const rows_type& get_rows() const { return m_rows; }
 
1278
 
 
1279
private:
 
1280
    const element& get_non_empty_element(size_t row, size_t col) const
 
1281
    {
 
1282
        typename rows_type::const_iterator itr = m_rows.find(row);
 
1283
        if (itr == m_rows.end())
 
1284
            return m_empty_elem;
 
1285
 
 
1286
        const row_type& row_store = *itr->second;
 
1287
        typename row_type::const_iterator itr_elem = row_store.find(col);
 
1288
        if (itr_elem == row_store.end())
 
1289
            return m_empty_elem;
 
1290
        return *itr_elem->second;
 
1291
    }
 
1292
 
 
1293
private:
 
1294
    rows_type   m_rows;
 
1295
    element     m_empty_elem;
 
1296
    size_t      m_row_size;
 
1297
    size_t      m_col_size;
 
1298
    bool        m_numeric:1;
 
1299
    bool        m_valid:1;
 
1300
};
 
1301
 
 
1302
}
 
1303
 
 
1304
#endif