In this lesson, we’ll traverse 2-D arrays differently and map them to a 1-D array. Mapping here refers to the process of taking elements from a two-dimensional matrix and rearranging them in a specific order to form a one-dimensional array. The specific order will be determined by the direction specified by an arrow in the question. This direction can be row-wise, column-wise, diagonally, or any other specific direction.

For example, a row-wise mapping function would take the elements of the 2-D matrix and arrange them in the order in which they appear in each row. A column-wise mapping function, on the other hand, would arrange the elements in the order in which they appear in each column.

Traversals and mappings from R2R^2 to RR world

Mapping is a way to transform complex data structures into simpler data structures. In this case it transforms a 2-D matrix into a 1-D array, making it easier to process or manipulate.

Given a rows x cols two-dimensional matrix TDA, write the mapping functions from R2R^2 (two dimensions) to RR (one dimension) for each different problem.

Implement the mapping function for each different mapping case below to convert a two-dimensional matrix TDA with dimensions of rows x cols to a one-dimensional array projectionMap. The functions should take the elements of the 2-D array and arrange them in a specific order as indicated by the direction specified by an arrow.

Playground for your implementation

Write your implementation of the mapping function here.

#include <iostream>
using namespace std;

#define MaxR 100
#define MaxC 100
#define Capacity 10000

void MappingCase1(int TDA[MaxR][MaxC], int rows, int cols, 
                      int projectionMap[Capacity], int &size)
{
    // Code here

}
void MappingCase2(int TDA[MaxR][MaxC], int rows, int cols, 
                      int projectionMap[Capacity], int &size)
{
    // Code here

}

// Exercise
void MappingCase3(int TDA[MaxR][MaxC], int rows, int cols, 
                      int projectionMap[Capacity], int &size)
{
    // Code here

}

void MappingCase4(int TDA[MaxR][MaxC], int rows, int cols, 
                      int projectionMap[Capacity], int &size)
{
    // Code here

}

// Exercise
void MappingCase5(int TDA[MaxR][MaxC], int rows, int cols, 
                      int projectionMap[Capacity], int &size)
{
    // 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[][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);
    MappingCase1(TDA, rows, cols, projectionMap, size);
    print1DProjection("Projected World 1:\n", projectionMap, size);
    
    MappingCase2(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 2:\n", projectionMap, size);
    
    MappingCase3(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 3:\n", projectionMap, size);
    
    MappingCase4(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 4:\n", projectionMap, size);
    
    MappingCase5(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 5:\n", projectionMap, size);
    
   
    return 0;
}
Traversals and mappings from R2 to R dimensional world

Let’s create a function mappingCase_() so that for each case, we will pass a two-dimensional array TDA[][maxC] with dimensions rows and cols and a one-dimensional array projectionMap with its size as parameters. We want to traverse each row from left to right in TDA and map each value in projectionMap. This convention will be used for every mapping.

Mapping case 1: Horizontal traversal I

Look at the following mapping illustration.

Mapping the horizontal traversal I

Here are the algorithmic details:

  • Initialized ai with 0.
  • We have a nested loop that traverses each row and column:
    • For each row ri from 0 to rows-1:
      • For each column ci from 0 to cols-1:
        • In each inner iteration (which moves column index ci from 0 to cols-1), the row will be fixed, and the column will be changed. We will update the 1-D array projectionMap[ai] with TDA[ri][ci] and also increment in ai by 1 .

Instruction: Understand the code below and add the code to your playground.

Look at the animation below:

Press + to interact
void mappingCase1(int TDA[][maxC], int rows, int cols, 
                      int projectionMap[capacity], int &size)
{
    int ai=0;
    size = rows*cols;  // assigning the size of the projection map
    
    for(int ri=0; ri<rows; ri++)
    {
        for(int ci=0; ci<cols; ci++)
        {
            projectionMap[ai] = TDA[ri][ci];ai++;
        }
    }
}

Mapping case 2: Horizontal traversal II

(even row   ⟹  \implies ascending and odd row   ⟹  \implies descending order)

Now, look at the case below carefully.

We would like to traverse the first and last row from left to right and the second row from right to left and map each value onto the one-dimensional array.

Mapping the horizontal traversal II

Here is the idea:

  • Initialized ai with 0.
  • We will have a similar nested loop that traverses each row and each column of each row but in a different order:
    • For each row ri from 0 to rows-1:
      • If the row is even (for ri ∈{0,2,4...}\in \{0, 2, 4 ...\}):
        • For each column ci from 0 to cols-1 (traversing in the forward direction):
          • Update the 1-D array projectionMap[ai] with TDA[ri][ci] and increment ai by 1.
      • If the row is odd (for ri ∈{1,3,5...}\in \{1, 3, 5 ...\}):
        • For each column ci from cols-1 to 0 (traversing in the backward direction):
          • Update the 1-D array projectionMap[ai] with TDA[ri][ci] and increment ai by 1.

Instruction: Understand the code below and add the code to your playground.

Look at the animation below:

Press + to interact
void mappingCase2(int TDA[][maxC], int rows, int cols, 
                      int projectionMap[capacity], int &size)
{
    int ai=0;
    size = rows*cols;
    for(int ri=0; ri<rows; ri++)
    {
        if(ri%2==0)
        {    
            for(int ci=0; ci<cols; ci++)
            {
                projectionMap[ai] = TDA[ri][ci];ai++;
            }
        }
        else
        {
            for(int ci=cols-1; ci>=0; ci--)
            {
                projectionMap[ai] = TDA[ri][ci];ai++;
            }
        }
    }
}

Exercise: Mapping case 3—Vertical traversal I

Look at the case below in which we traversed each column from top to bottom and mapped each value in the 1-D array.

Your code should print the following:

1 4 7 2 5 8 3 6 9

Best of luck!

Press + to interact
void mappingCase3(int TDA[][MaxC],int rows,int cols,
                      int projectionMap[Capacity],int & size)
{
    // Write your code here
}

Exercise: Mapping case 4—Vertical traversal II

Look at the case below in which we traversed the zero and 2nd column (even) from top to bottom, and the first column () from bottom to top and mapped each value in the 1-D array.

Your code should map onto a one-dimensional array in this order:

1 4 7 8 5 2 3 6 9

Best of luck!

Press + to interact
void mappingCase4(int TDA[MaxR][MaxC],int rows,int cols,
                      int projectionMap[Capacity],int & size)
{
    // Write your code here: 
}

Exercise: Mapping case 5—Horizontal traversal III

Look at the case below in which we traversed each row from left to right and mapped each value in the 1-D array. The point to be noted here, we have started traversing from the last row to the first row.

Your code should print the following:

7 8 9 4 5 6 1 2 3

Best of luck!

Press + to interact
void mappingCase5(int TDA[MaxR][MaxC],int rows,int cols,
                      int projectionMap[Capacity],int & size)
{
    // Write your code here: 
}

The complete code of 5 mapping functions

Here is the complete implementation of the five functions.

#include <iostream>
using namespace std;

#define MaxR 100
#define MaxC 100
#define Capacity 10000

void MappingCase1(int TDA[][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void MappingCase2(int TDA[][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void MappingCase3(int TDA[][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void MappingCase4(int TDA[][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void MappingCase5(int TDA[][MaxC], int rows, int cols, int projectionMap[Capacity], int &size);
void print2DWorld(const char Msg[], int TDA[][MaxC], int rows, int cols);
void print1DProjection(const char Msg[], int projectionMap[Capacity], int size);

int main()
{
    int TDA[][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);
    MappingCase1(TDA, rows, cols, projectionMap, size);
    print1DProjection("Projected World 1:\n", projectionMap, size);
    
    MappingCase2(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 2:\n", projectionMap, size);
    
    MappingCase3(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 3:\n", projectionMap, size);
    
    MappingCase4(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 4:\n", projectionMap, size);
    
    MappingCase5(TDA, rows, cols, projectionMap, size);
    print1DProjection("\n\nProjected World 5:\n", projectionMap, size);
    
   
    return 0;
}
Traversals and mappings from R2 to R dimensional world