[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]
Iterating through separate matrices as if they're one
Author
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:
... 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?
Could you try showing the declarations of the original matrices, and a list of the elements you want to iterate over, in order?
Author
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] [ ][ ] [ ] [ ] | [ ] [ ] [ ]
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.
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.
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_;<br> }<br> <br> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j)<br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> a_;<br> }<br> <br> <span class="cpp-keyword">private</span>:<br> T a_[H * W];<br>};<br><br><span class="cpp-keyword">template</span><typename MatrixType1, typename MatrixType2><br><span class="cpp-keyword">class</span> matrix_hjoin_ref : <br> <span class="cpp-keyword">public</span> matrix_defs<br> <<br> typename MatrixType1::element_type, <br> MatrixType1::height, <br> MatrixType1::width + MatrixType2::width<br> ><br>{<br> <span class="cpp-keyword">private</span>:<br> <span class="cpp-keyword">typedef</span> matrix_defs<br> <<br> typename MatrixType1::element_type, <br> MatrixType1::height, <br> MatrixType1::width + MatrixType2::width<br> ><br> base;<br><br> <span class="cpp-keyword">public</span>:<br> <span class="cpp-keyword">typedef</span> typename base::element_type element_type;<br> <br> matrix_hjoin_ref(MatrixType1 &left, MatrixType2 &right) :<br> left_(&left),<br> right_(&right)<br> {<br> ct_assert<MatrixType1::height == MatrixType2::height>();<br> ct_assert<same_type<typename MatrixType1::element_type, typename MatrixType2::element_type>::value>();<br> }<br> <br> <span class="cpp-keyword">const</span> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j) <span class="cpp-keyword">const</span><br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> (j < MatrixType1::width) ?<br> (*left_)(i, j) :<br> (*right_)(i, j - MatrixType1::width);<br> }<br> <br> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j)<br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> (j < MatrixType1::width) ?<br> (*left_)(i, j) :<br> (*right_)(i, j - MatrixType1::width);<br> }<br> <br> <span class="cpp-keyword">private</span>:<br> MatrixType1 *left_;<br> MatrixType2 *right_;<br>};<br><br><span class="cpp-keyword">template</span><typename MatrixType1, typename MatrixType2><br><span class="cpp-keyword">class</span> matrix_vjoin_ref : <br> <span class="cpp-keyword">public</span> matrix_defs<br> <<br> typename MatrixType1::element_type, <br> MatrixType1::height + MatrixType2::height, <br> MatrixType1::width<br> ><br>{<br> <span class="cpp-keyword">private</span>:<br> <span class="cpp-keyword">typedef</span> matrix_defs<br> <<br> typename MatrixType1::element_type, <br> MatrixType1::height + MatrixType2::height, <br> MatrixType1::width<br> ><br> base;<br> <br> <span class="cpp-keyword">public</span>:<br> <span class="cpp-keyword">typedef</span> typename base::element_type element_type;<br> <br> matrix_vjoin_ref(MatrixType1 &top, MatrixType2 &bottom) :<br> top_(&top),<br> bottom_(&bottom)<br> {<br> ct_assert<MatrixType1::height == MatrixType2::height>();<br> ct_assert<same_type<typename MatrixType1::element_type, typename MatrixType2::element_type>::value>();<br> }<br> <br> <span class="cpp-keyword">const</span> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j) <span class="cpp-keyword">const</span><br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> (i < MatrixType1::height) ?<br> (*top_)(i, j) :<br> (*bottom_)(i - MatrixType1::height, j);<br> }<br> <br> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j)<br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> (i < MatrixType1::height) ?<br> (*top_)(i, j) :<br> (*bottom_)(i - MatrixType1::height, j);<br> }<br> <br> <span class="cpp-keyword">private</span>:<br> MatrixType1 *top_;<br> MatrixType2 *bottom_;<br>};<br><br><span class="cpp-keyword">template</span><typename MatrixType, std::size_t H, std::size_t W><br><span class="cpp-keyword">class</span> matrix_window_ref : <span class="cpp-keyword">public</span> matrix_defs<typename MatrixType::element_type, H, W><br>{<br> <span class="cpp-keyword">private</span>:<br> <span class="cpp-keyword">typedef</span> matrix_defs<typename MatrixType::element_type, H, W> base;<br> <br> <span class="cpp-keyword">public</span>:<br> <span class="cpp-keyword">typedef</span> typename MatrixType::element_type element_type;<br> <br> matrix_window_ref(MatrixType &matrix, std::size_t i_offset, std::size_t j_offset) :<br> matrix_(&matrix),<br> i_offset_(i_offset),<br> j_offset_(j_offset)<br> {<br> }<br> <br> <span class="cpp-keyword">const</span> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j) <span class="cpp-keyword">const</span><br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> (*matrix_)(i + i_offset_, j + j_offset_);<br> }<br> <br> element_type &<span class="cpp-keyword">operator</span>() (std::size_t i, std::size_t j)<br> {<br> assert(i < base::height);<br> assert(j < base::width);<br> <span class="cpp-keyword">return</span> (*matrix_)(i + i_offset_, j + j_offset_);<br> }<br> <br> <span class="cpp-keyword">private</span>:<br> MatrixType *matrix_;<br> std::size_t i_offset_;<br> std::size_t j_offset_;<br>};<br><br><span class="cpp-keyword">template</span><typename T, std::size_t H, std::size_t W><br>std::ostream &<span class="cpp-keyword">operator</span><< (std::ostream &out, <span class="cpp-keyword">const</span> matrix<T, H, W> &m)<br>{<br> <span class="cpp-keyword">for</span> (std::size_t i = <span class="cpp-number">0</span>; i != H; ++i)<br> <span class="cpp-keyword">for</span> (std::size_t j = <span class="cpp-number">0</span>; j != W; ++j)<br> out << m(i, j) << (j == W - <span class="cpp-number">1</span> ? '\n' : '\t');<br> <br> <span class="cpp-keyword">return</span> out;<br>}<br><br><span class="cpp-keyword">int</span> main()<br>{<br> <span class="cpp-keyword">typedef</span> matrix<<span class="cpp-keyword">double</span>, <span class="cpp-number">4</span>, <span class="cpp-number">4</span>> mat4x4;<br> <span class="cpp-keyword">typedef</span> matrix_hjoin_ref<mat4x4, mat4x4> row_type;<br> <span class="cpp-keyword">typedef</span> matrix_vjoin_ref<row_type, row_type> row_stack;<br> <span class="cpp-keyword">typedef</span> matrix_window_ref<row_stack, <span class="cpp-number">6</span>, <span class="cpp-number">6</span>> window6x6;<br> <br> mat4x4 tl, tr, bl, br;<br> <br> row_type top_row(tl, tr); <span class="cpp-comment">// join tl and tr to make a 4x8</span><br> row_type bottom_row(bl, br); <span class="cpp-comment">// join bl and br to make a 4x8</span><br> row_stack both_rows(top_row, bottom_row); <span class="cpp-comment">// an 8x8</span><br> window6x6 middle6x6(both_rows, <span class="cpp-number">1</span>, <span class="cpp-number">1</span>); <span class="cpp-comment">// central 6x6 sub-matrix</span><br> <br> <span class="cpp-keyword">double</span> count = <span class="cpp-number">0</span>;<br> <br> <span class="cpp-keyword">for</span> (std::size_t i = <span class="cpp-number">0</span>; i != window6x6::height; ++i)<br> <span class="cpp-keyword">for</span> (std::size_t j = <span class="cpp-number">0</span>; j != window6x6::width; ++j)<br> middle6x6(i, j) = count++;<br> <br> std::cout << tl << '\n';<br> std::cout << tr << '\n';<br> std::cout << bl << '\n';<br> std::cout << br << '\n';<br> <br> <span class="cpp-keyword">return</span> <span class="cpp-number">0</span>;<br>}<br><br><br></pre></div><!–ENDSCRIPT–><br><br>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.
Author
Quote:Original post by ToohrVyk
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.
Quote:Original post by Montblanty
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).
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
Quote:Original post by MontblantyQuote:Original post by ToohrVyk
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.Quote:Original post by Montblanty
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).
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
