# Iterating through separate matrices as if they're one

This topic is 3999 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Here's the variables in question: One matrix holds a bunch of variables, we'll call them T A second matrix holds a grid for the layout of the former matrix There is also a class of variables. A top coordinate called 1, a left coordinate called 2, a bottom coordinate called 3, and a right coordinate called 4. Here is how all the information is layed out:
 [T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]
[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]
[T] [T] [T] [1] [T]|[T] [T] [1] [T] [T]|[T] [1] [T] [T] [T]
[T] [T] [2] [T] [4]|[2] [T] [T] [T] [4]|[2] [T] [4] [T] [T]
[T] [T] [T] [3] [T]|[T] [T] [3] [T] [T]|[T] [3] [T] [T] [T]
-------------------+-------------------+-------------------
[T] [T] [T] [1] [T]|[T] [T] [1] [T] [T]|[T] [1] [T] [T] [T]
[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]
[T] [T] [T] [2] [4]|[2] [T] [T] [T] [4]|[2] [T] [4] [T] [T]
[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]
[T] [T] [T] [3] [T]|[T] [T] [3] [T] [T]|[T] [3] [T] [T] [T]
-------------------+-------------------+-------------------
[T] [T] [T] [1] [T]|[T] [T] [1] [T] [T]|[T] [1] [T] [T] [T]
[T] [T] [2] [T] [4]|[2] [T] [T] [T] [4]|[2] [T] [4] [T] [T]
[T] [T] [T] [3] [T]|[T] [T] [3] [T] [T]|[T] [3] [T] [T] [T]
[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]
[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]|[T] [T] [T] [T] [T]

Each [] represents a position in the first matrix. The -, |, and + are positions in the second matrix. The letter or number within each [] is the variables as described above. How this needs to be iterated through is the top line is read in order from left to right, then go to the next line and begin anew, all the way to the bottom right. The order in which this is read is of utmost importance, so you can't read one of the first matrices all at once before moving to the next one. Instead it needs to, for example, start in the matrix in the top left, read to the right until it reaches the border of the middle matrix, read the line through that etc to the right. Then start a new line and start over at the first matrix over to the third. Continue down until the bottom of the matrices are reached and transfer to the second row of matrices. The most obvious solution, make a mega-matrix and draw them all into the correct positions in the big one, then read through that, isn't an acceptable solution. The reading from top left to bottom right needs to be O(n). Additional storage in certain parts may be needed, but hopefully a sophisticated iterative approach is usable.

use an array...

##### Share on other sites
... sorry, *what*???

Could you try showing the declarations of the original matrices, and a list of the elements you want to iterate over, in order?

##### Share on other sites
Quote:
 Original post by Zahlman... sorry, *what*???Could you try showing the declarations of the original matrices, and a list of the elements you want to iterate over, in order?

Here's a smaller example that's easier to read:
I have 4 small matrices, 3x3 in size, each cell of which represented by []
So here is what one of the matrices will look like:

[ ] [ ] [ ][ ] [ ] [ ][ ] [ ] [ ]

I have 1 large matrix that stores the read order of the 4 smaller matrices. It looks like this:

    |  1 | 2----+----  3 | 4    |

Here's the whole thing together:

[ 1] [ 2] [ 3] | [ 4] [ 5] [ 6][ 7] [ 8] [ 9] | [10] [11] [12][13] [14] [15] | [16] [17] [18]---------------+---------------[19] [20] [21] | [22] [23] [24][25] [26] [27] | [28] [29] [30][31] [32] [33] | [34] [35] [36]

The numbers in the above example represent the order in which the cells should be read. That's the first challenge.

Got that? Now let's expand it a step further.

I have a set of variables that store positions in the 4 small matrices. There are two positions per matrix, a top left square and a bottom right square. Essentially, I'm drawing a smaller matrix within it. It may look something like this:

[  ] [  ] [  ] | [  ] [  ] [  ][  ] [TL] [  ] | [TL] [  ] [  ][  ] [  ]  | [  ]  [  ]---------------+---------------[  ] [TL] [  ] | [TL] [  ] [  ][  ] [  ]  | [  ]  [  ][  ] [  ] [  ] | [  ] [  ] [  ]

TL = Top Left
BR = Bottom Right

The function needs to iterate through the matrices in the top left to bottom right manner I explained first, but ONLY the squares within the top left and bottom right. Thus, putting everything together, here's the final iteration order:

[  ] [  ] [  ] | [  ] [  ] [  ][  ] [ 1] [ 2] | [ 3] [ 4] [  ][  ] [ 5] [ 6] | [ 7] [ 8] [  ]---------------+---------------[  ] [ 9] [10] | [11] [12] [  ][  ] [13] [14] | [15] [16] [  ][  ] [  ] [  ] | [  ] [  ] [  ]

##### Share on other sites
The simplest way is to group the four matrices into a single large matrix, then to clip that matrix to the specified "top left, bottom right" rectangle, and to iterate within the clipped matrix.

In order to keep performance, do the regrouping and clipping operations lazily (that is, you only do them when the user accesses an element). This should be fairly easy to do by writing two adapter classes.

##### Share on other sites
I just knocked this together quickly. It's not particularly refined, but it does what you want, as far as I can tell.

#include <algorithm>#include <cstddef>#include <cassert>#include <iostream>template<bool> struct ct_assert;template<> struct ct_assert<true> { };template<typename T, typename U> struct same_type { static const bool value = false; };template<typename T> struct same_type<T, T> { static const bool value = true; };template<typename T, std::size_t H, std::size_t W>struct matrix_defs{    typedef T element_type;    static const std::size_t height = H;    static const std::size_t width = W;};template<typename T, std::size_t H, std::size_t W>class matrix : public matrix_defs<T, H, W>{    private:        typedef matrix_defs<T, H, W> base;        public:        typedef typename base::element_type element_type;            matrix() { std::fill(a_, a_ + sizeof(a_) / sizeof(*a_), T(0)); }                // ...                const element_type &operator() (std::size_t i, std::size_t j) const        {            assert(i < base::height);            assert(j < base::width);            return a_[i * base::width + j];        }                element_type &operator() (std::size_t i, std::size_t j)        {            assert(i < base::height);            assert(j < base::width);            return a_[i * base::width + j];        }            private:        T a_[H * W];};template<typename MatrixType1, typename MatrixType2>class matrix_hjoin_ref :     public matrix_defs    <        typename MatrixType1::element_type,         MatrixType1::height,         MatrixType1::width + MatrixType2::width    >{    private:        typedef matrix_defs        <            typename MatrixType1::element_type,             MatrixType1::height,             MatrixType1::width + MatrixType2::width        >        base;    public:        typedef typename base::element_type element_type;            matrix_hjoin_ref(MatrixType1 &left, MatrixType2 &right) :            left_(&left),            right_(&right)        {            ct_assert<MatrixType1::height == MatrixType2::height>();            ct_assert<same_type<typename MatrixType1::element_type, typename MatrixType2::element_type>::value>();        }                const element_type &operator() (std::size_t i, std::size_t j) const        {            assert(i < base::height);            assert(j < base::width);            return  (j < MatrixType1::width) ?                    (*left_)(i, j) :                    (*right_)(i, j - MatrixType1::width);        }                element_type &operator() (std::size_t i, std::size_t j)        {            assert(i < base::height);            assert(j < base::width);            return  (j < MatrixType1::width) ?                    (*left_)(i, j) :                    (*right_)(i, j - MatrixType1::width);        }            private:        MatrixType1 *left_;        MatrixType2 *right_;};template<typename MatrixType1, typename MatrixType2>class matrix_vjoin_ref :     public matrix_defs    <        typename MatrixType1::element_type,         MatrixType1::height + MatrixType2::height,         MatrixType1::width    >{    private:        typedef matrix_defs        <            typename MatrixType1::element_type,             MatrixType1::height + MatrixType2::height,             MatrixType1::width        >        base;            public:        typedef typename base::element_type element_type;            matrix_vjoin_ref(MatrixType1 &top, MatrixType2 &bottom) :            top_(&top),            bottom_(&bottom)        {            ct_assert<MatrixType1::height == MatrixType2::height>();            ct_assert<same_type<typename MatrixType1::element_type, typename MatrixType2::element_type>::value>();        }                const element_type &operator() (std::size_t i, std::size_t j) const        {            assert(i < base::height);            assert(j < base::width);            return  (i < MatrixType1::height) ?                    (*top_)(i, j) :                    (*bottom_)(i - MatrixType1::height, j);        }                element_type &operator() (std::size_t i, std::size_t j)        {            assert(i < base::height);            assert(j < base::width);            return  (i < MatrixType1::height) ?                    (*top_)(i, j) :                    (*bottom_)(i - MatrixType1::height, j);        }            private:        MatrixType1 *top_;        MatrixType2 *bottom_;};template<typename MatrixType, std::size_t H, std::size_t W>class matrix_window_ref : public matrix_defs<typename MatrixType::element_type, H, W>{    private:        typedef matrix_defs<typename MatrixType::element_type, H, W> base;            public:        typedef typename MatrixType::element_type element_type;            matrix_window_ref(MatrixType &matrix, std::size_t i_offset, std::size_t j_offset) :            matrix_(&matrix),            i_offset_(i_offset),            j_offset_(j_offset)        {        }                const element_type &operator() (std::size_t i, std::size_t j) const        {            assert(i < base::height);            assert(j < base::width);            return (*matrix_)(i + i_offset_, j + j_offset_);        }                element_type &operator() (std::size_t i, std::size_t j)        {            assert(i < base::height);            assert(j < base::width);            return (*matrix_)(i + i_offset_, j + j_offset_);        }            private:        MatrixType *matrix_;        std::size_t i_offset_;        std::size_t j_offset_;};template<typename T, std::size_t H, std::size_t W>std::ostream &operator<< (std::ostream &out, const matrix<T, H, W> &m){    for (std::size_t i = 0; i != H; ++i)        for (std::size_t j = 0; j != W; ++j)            out << m(i, j) << (j == W - 1 ? '\n' : '\t');                return out;}int main(){    typedef matrix<double, 4, 4> mat4x4;    typedef matrix_hjoin_ref<mat4x4, mat4x4> row_type;    typedef matrix_vjoin_ref<row_type, row_type> row_stack;    typedef matrix_window_ref<row_stack, 6, 6> window6x6;        mat4x4 tl, tr, bl, br;        row_type top_row(tl, tr); // join tl and tr to make a 4x8    row_type bottom_row(bl, br);  // join bl and br to make a 4x8    row_stack both_rows(top_row, bottom_row); // an 8x8    window6x6 middle6x6(both_rows, 1, 1); // central 6x6 sub-matrix        double count = 0;        for (std::size_t i = 0; i != window6x6::height; ++i)        for (std::size_t j = 0; j != window6x6::width; ++j)            middle6x6(i, j) = count++;                std::cout << tl << '\n';    std::cout << tr << '\n';    std::cout << bl << '\n';    std::cout << br << '\n';        return 0;}

It doesn't implement ToohrVyk's laziness idea, but if you're only iterating over the elements once, it may not be worth it, anyway.

##### Share on other sites
Quote:
 Original post by ToohrVykThe simplest way is to group the four matrices into a single large matrix, then to clip that matrix to the specified "top left, bottom right" rectangle, and to iterate within the clipped matrix.In order to keep performance, do the regrouping and clipping operations lazily (that is, you only do them when the user accesses an element). This should be fairly easy to do by writing two adapter classes.

Quote:
 Original post by MontblantyThe most obvious solution, make a mega-matrix and draw them all into the correct positions in the big one, then read through that, isn't an acceptable solution. The reading from top left to bottom right needs to be O(n).

The matrices will be accessed several times a second so I can't do the easy inefficient memory-wastey solution.

The way I see this working is a custom set of iterative variables that ignore the actual array positions, then write some functionality to compensate for that

##### Share on other sites
Quote:
Original post by Montblanty
Quote:
 Original post by ToohrVykThe simplest way is to group the four matrices into a single large matrix, then to clip that matrix to the specified "top left, bottom right" rectangle, and to iterate within the clipped matrix.In order to keep performance, do the regrouping and clipping operations lazily (that is, you only do them when the user accesses an element). This should be fairly easy to do by writing two adapter classes.

Quote:
 Original post by MontblantyThe most obvious solution, make a mega-matrix and draw them all into the correct positions in the big one, then read through that, isn't an acceptable solution. The reading from top left to bottom right needs to be O(n).

The matrices will be accessed several times a second so I can't do the easy inefficient memory-wastey solution.

Um, doing it by "wasting" memory is exactly the approach you should be taking if speed is a concern. "Creating a custom set of iterative variables" (I assume you mean, a custom iterator class) would be what you do if you *don't* have lots of memory, and speed is not a concern.

Keep in mind that once you've built the larger array, you could *keep* it somewhere.

##### Share on other sites
Ended up coming up with the solution on my own, thanks anyway

1. 1
2. 2
Rutin
19
3. 3
JoeJ
16
4. 4
5. 5

• 29
• 21
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631700
• Total Posts
3001797
×