Diagonal traversals and mappings from R2R^2 to R dimensional world

In this lesson, we will learn several new non-trivial mapping techniques.

Your implementation

Use the following playground for writing the code and testing it.

#include <iostream>
using namespace std;

#define MaxR 100
#define MaxC 100
#define Capacity 1000


void diagonalMapping1(int TDA[MaxR][MaxC], int rows, int cols, int projectionMap[Capacity], int &size)
{
    // Write your code here.
}


void diagonalMapping2(int TDA[MaxR][MaxC], int rows, int cols, int projectionMap[Capacity], int &size)
{
    // Write your code here.
}
void diagonalMapping3(int TDA[MaxR][MaxC], int rows, int cols, int projectionMap[Capacity], int &size)
{
    // Write your code here.
}

void print2DWorld(const char Msg[], int TDA[MaxR][MaxC], int rows, int cols)
{
    cout << Msg;
    for(int ri=0; ri<rows; ri++)
    {
        for(int ci=0; ci<cols; ci++)
        {
            cout << TDA[ri][ci]<<" ";
        }
        cout << endl;
    }
}
void print1DProjection(const char Msg[], int projectionMap[Capacity], int size)
{
    cout << Msg;
    for(int mi=0; mi<size; mi++)
    {
            cout << projectionMap[mi]<<" ";
    }
}
int main()
{
    int TDA[MaxR][MaxC] = {{1,2,3},{4,5,6},{7,8,9}}, rows=3, cols=3;
    int projectionMap[Capacity], size;
    print2DWorld("Two Dimensional World\n", TDA, rows, cols);

   diagonalMapping1(TDA, rows, cols, projectionMap, size);
   print1DProjection("\n\nProjected World\n", projectionMap, size);
    
   diagonalMapping2(TDA, rows, cols, projectionMap, size);
   print1DProjection("\n\nProjected World\n", projectionMap, size);
    
   diagonalMapping3(TDA, rows, cols, projectionMap, size);
   print1DProjection("\n\nProjected World\n", projectionMap, size);
   
   
    return 0;
}
Traversals and mappings from R2 to R dimensional world

Diagonal mapping I

Look at the mapping case below in which every diagonal traverses from left to right and bottom to top.

Look at the illustration and understand it before we move forward.

How to map

Look at the animation below carefully. The first upper half of the diagonals, including the middle diagonal (1st, 2nd, and the 3rd), start from the 0th column, and the starting row of each diagonal is one more than the previous diagonal, respectively. The lower half of the diagonals (4th, 5th, and 6th) always start from the last row, and the starting column of each lower diagonal is 1 more than the previous, respectively. Lastly, in each diagonal, the row decreases by 1, and the column increases by 1.

Implementation details

Here are the algorithmic details:

  • Initialized ai with 0, where ai is the mapping index of the one-dimensional array.
  • The first nested loop (for printing upper diagonals):
    • For each diagonal d from 0 to rows-1, because there are rows many upper diagonals:
      • For each pair r=d (the dth diagonal starts from dth row), c=0 (each diagonal starts from 0th column), row should be equal or greater than zero r>=0 and the row will decrement r-- and column will increment c++ in each step. Note: In all these upper diagonals, the row value, thus the boundary condition is that the row value must be greater than or equal to 0 (r>=0).
        • Update the 1-D array projectionMap[ai] with TDA[ri][ci] with an increment in ai.
  • The second nested loop (for printing lower diagonals).
    • For each diagonal d from 1 to cols-1, as there are total of cols-1 lower diagonals.
      • For each pair (r=rows-1, c=d):
        • Update the 1-D array projectionMap[ai] with TDA[ri][ci] with an increment in ai.
        • The row will decrement r-- and the column will increment c++, and the column index should be bounded by c<cols.

Instruction: Understand the code below, rewrite it in your playground, and test it.

Press + to interact
void diagonalMapping1(int TDA[maxR][maxC], int rows, int cols, int projectionMap[capacity], int &size)
{
    int ai=0;
    size = rows*cols;
    for(int d=0; d<rows; d++)
    {
        for(int r=d, c=0; r>=0; r--, c++)
        {
            projectionMap[ai] = TDA[r][c];ai++;
        }
    }
    for(int d=1; d<cols; d++)
    {
        for(int r=rows-1,c=d; c<cols; r--, c++)
        {
            projectionMap[ai] = TDA[r][c];ai++;
        }
    }
}

Exercise 1: Diagonal mapping II

Look at the mapping case below in which we traverse diagonally from left to right. Understand it before we move forward.

How to map

Look at the animation below carefully. The first upper half of the diagonals, including the middle diagonal (1st, 2nd, and 3rd), start from the 0th row, and the starting column of each diagonal is one more than the previous diagonal, respectively. The lower half of the diagonals (4th, 5th, and 6th) always start from the last column, and the starting row of each lower diagonal is 1 more than the previous, respectively. Lastly, in each diagonal, the row increases by 1, and the column decreases by 1.

Instruction: Write the code in your playground and test it. If you are stuck, look at the hint.

Exercise 2: Diagonal mapping III

Look at the case below where each even diagonal is traversing from left to right and in an upward direction and odd arrows right to left and in a downward direction.

How to map

The first thing we need to notice is that this mapping is a merge of the above two mappings such that the even diagonal (0th, 2nd, and so on) are moving from left to right and in upward directions, and in the odd case the diagonal is moving from right to left and downwards.

Alternative the even and the odd cases can be managed by maintaining one boolean variable. And toggling the state of this flag is just one line:

bool isEven = true/false;
.
.

isEven=!isEven; // toggling the state.

All we need to do is the following:

  • Again, we will print in two separate nested loops: one for the upper half and one for the lower half.
  • In both nested loops, in the case of the even diagonal mapping1() should get activated and mapping2() otherwise.

The complete code of the three diagonal mapping functions

Here is the complete implementation of the three diagonal mapping functions.

#include <iostream>
using namespace std;

#define MaxR 100
#define MaxC 100
#define Capacity 1000

void diagonalMapping1(int TDA[MaxR][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void diagonalMapping2(int TDA[MaxR][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void diagonalMapping3(int TDA[MaxR][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void print2DWorld(const char Msg[], int TDA[MaxR][MaxC], int rows, int cols);
void print1DProjection(const char Msg[], int projectionMap[Capacity], int size);

int main()
{
    int TDA[MaxR][MaxC] = {{1,2,3},{4,5,6},{7,8,9}}, rows=3, cols=3;
    int projectionMap[Capacity], size;
    print2DWorld("Two Dimensional World\n", TDA, rows, cols);

   diagonalMapping1(TDA, rows, cols, projectionMap, size);
   print1DProjection("\n\nProjected World\n", projectionMap, size);
    
   diagonalMapping2(TDA, rows, cols, projectionMap, size);
   print1DProjection("\n\nProjected World\n", projectionMap, size);
    
   diagonalMapping3(TDA, rows, cols, projectionMap, size);
   print1DProjection("\n\nProjected World\n", projectionMap, size);
   
   
    return 0;
}
Traversals and mappings from R2 to R dimensional world