Array2D.h

Go to the documentation of this file.

/*
 * $Revision: 2030 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-03 10:29:11 +0200 (Fri, 03 Sep 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_ARRAY2D_H
#define OGDF_ARRAY2D_H


#include <ogdf/basic/basic.h>
#include <math.h>


namespace ogdf {


template<class E> class Array2D
{
public:
    // constructors

    Array2D() { construct(0,-1,0,-1); }

    Array2D(int a, int b, int c, int d) {
        construct(a,b,c,d); initialize();
    }

    Array2D(int a, int b, int c, int d, const E &x) {
        construct(a,b,c,d); initialize(x);
    }

    Array2D(const Array2D<E> &array2) {
        copy(array2);
    }

    // destructor
     ~Array2D() {
         deconstruct();
    }

    int low1() const { return m_a; }

    int high1() const { return m_b; }

    int low2() const { return m_c; }

    int high2() const { return m_d; }

    int size() const { return size1() * size2(); }

    int size1() const { return m_b - m_a + 1; }

    int size2() const { return m_lenDim2; }


    float det();

    const E &operator()(int i, int j) const {
        OGDF_ASSERT(m_a <= i && i <= m_b && m_c <= j && j <= m_d);
        return m_vpStart[(i-m_a)*m_lenDim2+j];
    }

    E &operator()(int i, int j) {
        OGDF_ASSERT(m_a <= i && i <= m_b && m_c <= j && j <= m_d);
        return m_vpStart[(i-m_a)*m_lenDim2+j];
    }

    void init() { init(0,-1,0,-1); }

    void init(int a, int b, int c, int d) {
        deconstruct();
        construct(a,b,c,d);
        initialize();
    }

    void init(int a, int b, int c, int d, const E &x) {
        deconstruct();
        construct(a,b,c,d);
        initialize(x);
    }

    Array2D<E> &operator=(const Array2D<E> &array2) {
        deconstruct();
        copy(array2);
        return *this;
    }

    void fill(const E &x) {
        E *pDest = m_pStop;
        while(pDest > m_pStart)
            *--pDest = x;
    }

private:
    E   *m_vpStart; 
    int  m_a; 
    int  m_lenDim2; 
    E   *m_pStart; 
    E   *m_pStop; 
    int  m_b; 
    int  m_c; 
    int  m_d; 

    void construct(int a, int b, int c, int d);

    void initialize();
    void initialize(const E &x);

    void deconstruct();

    void copy(const Array2D<E> &array2);

};



template<class E>
void Array2D<E>::construct(int a, int b, int c, int d)
{
    m_a = a;
    m_b = b;
    m_c = c;
    m_d = d;

    int lenDim1 = b-a+1;
    m_lenDim2   = d-c+1;
    
    if (lenDim1 < 1 || m_lenDim2 < 1) {
        m_pStart = m_vpStart = m_pStop = 0;

    } else {
        int len = lenDim1*m_lenDim2;
        m_pStart = (E *)malloc(len*sizeof(E));
        if (m_pStart == 0)
            OGDF_THROW(InsufficientMemoryException);

        m_vpStart = m_pStart - c;
        m_pStop   = m_pStart + len;
    }
}


template<class E>
void Array2D<E>::initialize()
{
    E *pDest = m_pStart;
    try {
        for (; pDest < m_pStop; pDest++)
            new(pDest) E;
    } catch (...) {
        while(--pDest >= m_pStart)
            pDest->~E();
        free(m_pStart);
        throw;
    }
}


template<class E>
void Array2D<E>::initialize(const E &x)
{
    E *pDest = m_pStart;
    try {
        for (; pDest < m_pStop; pDest++)
            new(pDest) E(x);
    } catch (...) {
        while(--pDest >= m_pStart)
            pDest->~E();
        free(m_pStart);
        throw;
    }
}


template<class E>
void Array2D<E>::deconstruct()
{
    if (doDestruction((E*)0)) {
        for (E *pDest = m_pStart; pDest < m_pStop; pDest++)
            pDest->~E();
    }
    free(m_pStart);
}


template<class E>
void Array2D<E>::copy(const Array2D<E> &array2)
{
    construct(array2.m_a, array2.m_b, array2.m_c, array2.m_d);

    if (m_pStart != 0) {
        E *pSrc  = array2.m_pStop;
        E *pDest = m_pStop;
        while(pDest > m_pStart)
            new (--pDest) E(*--pSrc);
    }
}



template<class E>
float Array2D<E>::det()
{
  int a = m_a;
  int b = m_b;
  int c = m_c;
  int d = m_d;
  int m = m_b - m_a + 1;
  int n = m_lenDim2;

  int i, j;
  int rem_i, rem_j, column;

  float determinant = 0.0;

  OGDF_ASSERT(m == n);

  switch(n) {
  case 0:
    break;
  case 1:
    determinant = (float)((*this)(a, c));
    break;
  case 2:
    determinant = (float)((*this)(a, c) * (*this)(b, d) - (*this)(a, d) * (*this)(b, c));
    break;

  // Expanding along the first row (Laplace's Formula)
  default:
    Array2D<E> remMatrix(0, n-2, 0, n-2);             // the remaining matrix
    for(column = c; column <= d; column++) {
      rem_i = 0;
      rem_j = 0;
      for(i = a; i <= b; i++) {
    for(j = c; j <= d; j++) {
      if(i != a && j != column) {
        remMatrix(rem_i, rem_j) = (*this)(i, j);
        if(rem_j < n-2) {
          rem_j++;
        }
        else {
          rem_i++;
          rem_j = 0;
        }
      }
    }
      }
      determinant += pow(-1,(a+column)) * (*this)(a,column) * remMatrix.det();
    }
  }  
  return determinant;
}



} // end namespace ogdf


#endif