Code

Inplace matrix transposition

November 3, 2010 Coded in C++

This C++ code intents to do inplace transposition for matrix.

It is more efficient for huge matrix, and quite generic as it uses classes and templates.

Feel free to use it and to modify it.

Allocation can be improved according to your system.

Compiles with g++

/* ------------------------------------------------------------------------- */
//
// This C++ code intents to do inplace transposition for matrix.
// It is more efficient for huge matrix, and quite generic as it uses classes 
// and templates.
//
// Feel free to use it and to modify it.
// Allocation can be improved according to your system.
// Compiles with g++
/* ------------------------------------------------------------------------- */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <alloca.h>
#include <iostream>

using std::swap;
using std::cout;

template <typename T>
class matrix_t
{
   public:
      unsigned int row;
      unsigned int col;
      T *addr;

      /* ------------------------------------------------------------------------- */
      // FUNCTION: matrix_t 
      /* ------------------------------------------------------------------------- */
      matrix_t()
      {
         row = 0;
         col = 0;
         addr = NULL;
      }

      /* ------------------------------------------------------------------------- */
      // FUNCTION: init 
      // 
      // PARAM: _row
      // PARAM: _col
      // 
      // Init with allocation
      //
      // RETURN:
      /* ------------------------------------------------------------------------- */
      int init(unsigned int _row, unsigned int _col)
      {
         row = _row;
         col = _col;
         addr = (T *) calloc(sizeof(T), row * col);
         if (addr == NULL)
         {
            return -1;
         }
         return 0;
      }

      /* ------------------------------------------------------------------------- */
      // FUNCTION: term 
      // 
      // Terminate
      //
      // RETURN:
      /* ------------------------------------------------------------------------- */
      int term()
      {
         if (addr)
         {
            free(addr);
         }
         addr = NULL;
         return 0;
      }

      /* ------------------------------------------------------------------------- */
      // FUNCTION: fill 
      //
      // Fill with values
      /* ------------------------------------------------------------------------- */
      void fill()
      {
         unsigned int x = 0;
         int c = 0;
         for (x = 0; x < row; x++)
         {
            unsigned int y = 0;
            for (y = 0; y < col; y++)
            {
               addr[x * col + y] = (T) c++;
            }
         }
      }

      /* ------------------------------------------------------------------------- */
      // FUNCTION: print 
      //
      // Print to standard output
      /* ------------------------------------------------------------------------- */
      void print()
      {
         unsigned int x = 0;
         cout << "row: " << row << "\n";
         cout << "col: " << col << "\n";
         for (x = 0; x < row; x++)
         {
            unsigned int y = 0;
            for (y = 0; y < col; y++)
            {
               cout.width(3);
               cout << addr[x * col + y] << " ";
            }
            cout << "\n";
         }
         cout << "\n";
         cout << "\n";
      }

      /* ------------------------------------------------------------------------- */
      // FUNCTION: operator== 
      // 
      // PARAM: mat2
      //
      // Comparaison of two matrices
      // 
      // RETURN: 1 if equals; 0 if differents
      /* ------------------------------------------------------------------------- */
      int operator==(matrix_t mat2)
      {
         unsigned int x = 0;

         if (row != mat2.row)
         {
            fprintf(stderr, "Error : different number of rows (%d != %d)\n", row, mat2.row);
            return 0;
         }

         if (col != mat2.col)
         {
            fprintf(stderr, "Error : different number of columns (%d != %d)\n", col, mat2.col);
            return 0;
         }
         
         for (x = 0; x < row; x++)
         {
            unsigned int y = 0;
            for (y = 0; y < col; y++)
            {
               unsigned int pos = x * col + y;
               if (addr[pos] != mat2.addr[pos])
               {
                  return 0;
               }
            }
         }
         return 1;
      }

      /* ------------------------------------------------------------------------- */
      // FUNCTION: transpose 
      // 
      // Transposition
      /* ------------------------------------------------------------------------- */
      int transpose()
      {
         unsigned int x = 0;
         T *addr2 = (T *) calloc(sizeof(T), row * col);
         
         if (addr2 == NULL)
         {
            return -1;
         }

         for (x = 0; x < row; x++)
         {
            unsigned int y = 0;
            for (y = 0; y < col; y++)
            {
               int s = x * col + y;
               int d = y * row + x;
               addr2[d] = addr[s];
            }
         }

         free(addr);
         addr = addr2;
         swap<unsigned int>(row, col);
         return 0;
      }

#define BITSET_POS(ptr,x)   ((int)(((unsigned char*)(ptr))[(x)/8]))
#define BITSET_IS(ptr,x)   ((int)(((unsigned char*)(ptr))[(x)/8]) & (int)(1<<((x)&7)))
#define BITSET_SET(ptr,x)   ((unsigned char*)(ptr))[(x)/8] |= (unsigned char)(1<<((x)&7))

      /* ------------------------------------------------------------------------- */
      // FUNCTION: transpose_inplace 
      //  
      // Inplace transposition
      /* ------------------------------------------------------------------------- */
      int transpose_inplace()
      {
         unsigned int len = row * col;
         unsigned int size = (len/8) + 1;
         unsigned int i = 0;
         unsigned char *data = (unsigned char*) calloc(1, size);
         if (addr == NULL)
         {
            return -1;
         }
         
         while (i < len)
         {
            if (BITSET_POS(data, i) == 0xff)
            {
               i += 8;
               continue;
            }

            if (BITSET_IS(data, i))
            {
               i++;
               continue;
            }

            unsigned int begin = i;
            BITSET_SET(data, i);
            T tmp = (T)0;
            do
            {
               swap<T>(addr[i], tmp);
               unsigned int _row = i / col;
               unsigned int _col = i % col;
               i = _col * row + _row;
               BITSET_SET(data, i);
            }
            while (i != begin);

            swap<T>(addr[i], tmp);
            i = begin + 1;
         }

         free(data);
         swap<unsigned int>(row, col);
         return 0;
      }
}; 

/* ------------------------------------------------------------------------- */
// FUNCTION: main 
// 
// Test case : 
//    transpose a 9x23 matrix
//    transpose inplace a 9x23 matrix
//    and compare
//
/* ------------------------------------------------------------------------- */
int main()
{
   matrix_t<double> m1, m1_ref;

   m1.init(9, 23);
   m1_ref.init(9, 23);

   m1.fill();
   m1_ref.fill();

   m1.print();

   m1.transpose_inplace();
   m1_ref.transpose();

   m1.print();

   if (m1 == m1_ref)
   {
      printf("==\n");
   }
   else
   {
      printf("!=\n");
   }
   
   m1.term();
   m1_ref.term();

   return 0;
}