Dividing an array into blocks

projectUser (31)
Given an array of size L1xL2 divide the array by blocks of 8x8. For example the size of the array is 16x16 so there will be four blocks of 8x8.

I can only get the first block of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
//matrix initialize to random numbers
int matrix[16][16];
int array[8][8];

for(r = 0; r < 8; r ++)
{
 for(c = 0; c < 8; c++)
 {
   array[r][c] = matrix[r][c];
   cout << array[r][c] << " "; 
 }
cout << "\n";
}


How can I access the rest of the elements and store them in an array? Is it possible to store the blocks in one array?
ToniAz (351)
1
2
3
4
5
6
7
8
9
10
11
12
13
 
//matrix initialize to random numbers
int matrix[16][16];
int array[8][8];

for(r = 8; r < 16; r ++)
{
 for(c = 0; c < 8; c++)
 {
   array[r-8][c] = matrix[r][c]; /* change array[r][c] to array[r-8][c], why? */
   cout << array[r][c] << " "; 
 }
cout << "\n";
}


Do you know which square of matrix corresponds to.
Last edited on
projectUser (31)
I tried doing this 

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
37
 
// Gets the first block
for(r = 0; r < 8; r++ )
{
   for(c = 0; c < 8; c++)
  {
     array[r][c] = matrix[r][c];
  }
}

// Gets the second block
for(r = 0; r < 8; r++ )
{
   for(c = 8; c < 16; c++)
  {
     array[r][c] = matrix[r][c];
  }
}

// Gets the third block
for(r = 8; r < 16; r++ )
{
   for(c = 0; c < 8; c++)
  {
     array[r][c] = matrix[r][c];
  }
}

// Gets the fourth block
for(r = 8; r < 16; r++ )
{
   for(c = 8; c < 16; c++)
  {
     array[r][c] = matrix[r][c];
  }
}


But I find the code very lengthy and it only works for 16x16 arrays. How can it be more dynamic to accommodate other array sizes?
JLBorges (13770)
> But I find the code very lengthy and it only works for 16x16 arrays.
> How can it be more dynamic to accommodate other array sizes

Factor the slicing logic into a function.

Something like:
1
2
3
4
5
6
7
8
9
10
 
// from an NxN matrix, retrieve an MxM slice starting at row i, col j
template< typename T, std::size_t N, std::size_t M >
void get_slice( const T (&matrix) [N][N], T (&slice)[M][M],
                 std::size_t i, std::size_t j )
{
    assert( N > std::min( i, j ) + M ) ;
    for( std::size_t k = 0 ; k < M ; ++k )
        for( std::size_t l = 0 ; l < M ; ++l )
            slice[k][l] = matrix[k+i][l+j] ;
}


And then:

1
2
3
4
5
6
7
8
9
10
11
 
enum { BLKSZ = 8, SIZE = 16, NBLOCKS = 4  } ;
int matrix[SIZE][SIZE] ;
int block[NBLOCKS][BLKSZ][BLKSZ];

get_slice( matrix, block[0], 0, 0 ) ; // gets the first block
get_slice( matrix, block[1], 0, BLKSZ ) ; // gets the second block
get_slice( matrix, block[2], BLKSZ, 0 ) ; // gets the third block
get_slice( matrix, block[3], BLKSZ, BLKSZ ) ; // gets the last block

for( int i = 0 ; i < NBLOCKS ; ++i ) // get all blocks (invariant: NBLOCKS == 4)
   get_slice( matrix, block[i], BLKSZ*i/2, BLKSZ*i%2 ) ;


Better still, use std::valarray<> instead of C array
http://en.cppreference.com/w/cpp/numeric/valarray
ToniAz (351)
@JLBorges

Didn't know size_t was in std... Do you recommend using vector class in stl or valarray? Is this one of those depends-on-your-applications situation?
JLBorges (13770)
When in doubt, use std::vector<>

Use std::valarray<> if and only if there is a specific reason to justify its use - in this particular case, support for slicing and indirect access.
Last edited on
projectUser (31)
@JLBorges is the code sample in C? and can you please explain the code below. How come it became 3D?

int block[NBLOCKS][BLKSZ][BLKSZ];

BTW I tried running the code but it forces the cmd to close

[code]
Assertion failed: N > min( i, j ) + M, file try.cpp, line 16

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.
[code]
Last edited on
JLBorges (13770)
> @JLBorges is the code sample in C?

No. Template, reference, namespace - must be C++


> can you please explain the code below. How come it became 3D?
> int block[NBLOCKS][BLKSZ][BLKSZ];

We need to make four BLKSZ x BLKSZ (8 x 8) slices from a 16 x 16 matrix.
The 3D array contains four 2D blocks - block[0] is the first block, block[1] is the second block and so on.


> BTW I tried running the code but it forces the cmd to close
Assertion failed: N > min( i, j ) + M, file try.cpp, line 16

Mea culpa.

1
2
 
    // assert( N > std::min( i, j ) + M ) ;
    assert( N >= std::max( i, j ) + M ) ;

And
1
2
3
 
    for( int i = 0 ; i < NBLOCKS ; ++i ) // get all blocks (invariant: NBLOCKS == 4)
       // get_slice( matrix, block[i], BLKSZ*i/2, BLKSZ*i%2 ) ;
       get_slice( matrix, block[i], BLKSZ * ( i/2 != 0 ), BLKSZ * (i%2) ) ;

projectUser (31)
ok thanks I will try it
projectUser (31)
@JLBorges

So instead of doing this
 
 
enum { BLKSZ = 8, SIZE = 16, NBLOCKS = 4  } ;


I just declared it one by one
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
// width and height of array
int w = width;
int h = height;

int block = 8;
int noBlocks = w / 8; // number of blocks

int block[noBlocks][blockSize][blockSize];
int matrix[w][h];

for(int i = 0; i < w; ++i)
{
  for(int j = 0; j < h; ++j)
  {
     matrix[i][j] = array[i][j];
  }
}

//get the first block
get_slice(matrix, block[0], 0, 0);

but i get this error
no matching function for call to ‘get_slice ...

Shouldn't the code above just be the same as the enum declaration? The only difference is I declared it instead of enumerating them.

I also tried doing this but no luck
enum { BLKSZ = 8, SIZE = w, NBLOCKS = numBlocks } ;
Last edited on
JLBorges (13770)
> Shouldn't the code above just be the same as the enum declaration?
> The only difference is I declared it instead of enumerating them.

In C++, the size of an array must be a positive, integral constexpr (a value that can be evaluated at compile-time).

If the number of elements in the sequence is not known at compile-time, prefer using a std::vector<>
http://www.mochima.com/tutorials/vectors.html

The earlier example re-written for the size of the matrix being known only at run-time:
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
37
38
39
40
41
42
43
44
45
46
 
#include <vector>

// template typedef: not C++98
template< typename T > using matrix_t = std::vector< std::vector<T> > ;

// from a matrix, retrieve an nxn slice starting at row i, col j
// throws std::out_of_range on error
template< typename T >
matrix_t<T> get_slice( const matrix_t<T>& matrix, std::size_t n,
                       std::size_t i, std::size_t j )
{
    const std::size_t N = matrix.size() ;
    matrix_t<T> slice(n) ;

    for( std::size_t k = 0 ; k < n ; ++k )
        for( std::size_t l = 0 ; l < n ; ++l )
            slice[k].emplace_back( matrix.at(k+i).at(l+j) ) ; // C++98: push_back()

    return slice ;
}

// **** trivial test driver ******

#include <iostream>

template< typename T > void print( const matrix_t<T>& matrix )
{
    for( const auto& row : matrix ) // range-based for: not C++98
    {
        for( int value : row ) std::cout << value << ' ' ;
        std::cout << '\n' ;
    }
    std::cout << "--------------------\n" ;
}

int main()
{
    matrix_t<int> matrix = { {1,2,3,4}, {5,6,7,8}, {9,0,1,2}, {3,4,5,6}, {7,8,9,0} } ;
    print(matrix) ;

    auto block = get_slice( matrix, 2, 2, 1 ) ; // type inference: not C++98
    print(block) ;

    block = get_slice( matrix, 3, 1, 1 ) ;
    print(block) ;
}


Note: Standard C++ code. If you are using an old compiler, the code would require a few modifications.
Last edited on
projectUser (31)
I can't get the code to work. I remove the std since I use "using namespace std" and I put the "iostream" above and instead of print I used cout.

I get this error code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
6:24: error: expected unqualified-id before ‘using’
11:1: error: ‘matrix_t’ does not name a type
28:42: error: ‘matrix_t’ does not name a type
 error: ISO C++ forbids declaration of ‘parameter’ with no type [-fpermissive]
:28:50: error: expected ‘,’ or ‘...’ before ‘<’ token
 In function ‘void print(int)’:
 error: ISO C++ forbids declaration of ‘row’ with no type [-fpermissive]
:30:28: error: range-based-for loops are not allowed in C++98 mode
30:28: error: ‘matrix’ was not declared in this scope
:32:26: error: range-based-for loops are not allowed in C++98 mode
: In function ‘int main()’:
40:5: error: ‘matrix_t’ was not declared in this scope
40:14: error: expected primary-expression before ‘int’
40:14: error: expected ‘;’ before ‘int’
51:1: error: expected ‘}’ at end of input


Also i notice the word "using". What is it for?
template< typename T > using matrix_t = std::vector< std::vector<T> > ;
Last edited on
JLBorges (13770)
> I can't get the code to work. I remove the std since I use "using namespace std" ...

This should work with an old (less than fifteen years or so) C++ compiler: 
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
37
38
39
40
41
42
43
44
45
46
47
 
#include <vector>
#include <iostream>
using namespace std ;

// from a matrix, retrieve an nxn slice starting at row i, col j
// throws std::out_of_range on error
template< typename T >
vector< vector<T> > get_slice( const vector< vector<T> >& matrix, std::size_t n,
                               std::size_t i, std::size_t j )
{
    const std::size_t N = matrix.size() ;
    vector< vector<T> > slice(n) ;

    for( std::size_t k = 0 ; k < n ; ++k )
        for( std::size_t l = 0 ; l < n ; ++l )
            slice[k].push_back( matrix.at(k+i).at(l+j) ) ;

    return slice ;
}

// **** trivial test driver ******

template< typename T > void print( const vector< vector<T> >& matrix )
{
    for( std::size_t i = 0 ; i < matrix.size() ; ++i )
    {
        for( std::size_t j = 0 ; j < matrix[i].size() ; ++j )
                   std::cout << matrix[i][j] << ' ' ;
        std::cout << '\n' ;
    }
    std::cout << "--------------------\n" ;
}

int main()
{
    enum { N = 5, M = 4 } ;
    const int test_data[N][M] = { {1,2,3,4}, {5,6,7,8}, {9,0,1,2}, {3,4,5,6}, {7,8,9,0} } ;
    vector< vector<int> > matrix(N) ;
    for( int i = 0 ; i < N ; ++i ) matrix[i].assign( test_data[i], test_data[i] + M ) ;
    print(matrix) ;

    vector< vector<int> > block = get_slice( matrix, 2, 2, 1 ) ;
    print(block) ;

    block = get_slice( matrix, 3, 1, 1 ) ;
    print(block) ;
}



> Also i notice the word "using". What is it for?

See: http://www2.research.att.com/~bs/C++0xFAQ.html#template-alias
projectUser (31)
Ok thanks I will try again
Topic archived. No new replies allowed.