c++ - Given a 2D array, convert to Z-Order -

having trouble wrapping head around conversion. want recursively convert 2d nxn matrix z-order version.

for example given array:

[ 1  2 ] [ 3  4 ] 

the z-order

[ 1 2 3 4]  

what steps recursively z-order conversion?

the recursive way simple:

• visit top-left
• visit top-right
• visit bottom-left
• visit bottom-right

in code

#include <iostream>  template<typename m, typename cback> void zorder(const m& m, int y0, int x0, int size,             cback cback) {     if (size == 1) {         // base case, 1 cell         cback(m[y0][x0]);     } else {         // recurse in z-order         int h = size/2;         zorder(m, y0,   x0,   h, cback); // top-left         zorder(m, y0,   x0+h, h, cback); // top-right         zorder(m, y0+h, x0,   h, cback); // bottom-left         zorder(m, y0+h, x0+h, h, cback); // bottom-right     } }  void print(int x) {     std::cout << x << " "; }  int main(int argc, const char *argv[]) {     int x[][4] = {{ 1,  2,  3,  4},                   { 5,  6,  7,  8},                   { 9, 10, 11, 12},                   {13, 14, 15, 16}};     zorder(x, 0, 0, 4, print);     std::cout << std::endl;     return 0; } 

output of program is

1 2 5 6 3 4 7 8 9 10 13 14 11 12 15 16 

note there non-recursive approach: visit elements in z-order can iterate on counter , take odd-bits y , even-bits x (counting bits 0):

int zorder_x_of(int index) {     int x = 0;     (int b=0,k=0; (1<<b) <= index; b+=2,k++) {         x += ((index & (1<<b)) != 0) << k;     }     return x; }  int zorder_y_of(int index) {     return zorder_x_of(index>>1); }  template<typename m, typename cback> void zorder2(const m& m, int size, cback cback) {     (int i=0; i<size*size; i++) {         cback(m[zorder_y_of(i)][zorder_x_of(i)]);     } } 

note:

in above code samples created function accepts "callback" (named cback) called elements of matrix, 1 @ time, in z-order.

to allow using both matrix , callback supports double [] indexing , can called used c++ template.

in main program matrix i've used bi-dimensional array of integers , function, code have compiled example std::vector< std::vector< double > > matrix , object instance of class providing operator()(double) callback.