Array2D.h

Go to the documentation of this file.

/*
 * $Revision: 2615 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
 ***************************************************************/

#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;

    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() const
{
    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.0,(a+column)) * (*this)(a,column) * remMatrix.det();
        }
    }

    return determinant;
}



} // end namespace ogdf


#endif