Array2D.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/exceptions.h>
 
#include <cmath>
#include <cstdlib>
#include <new>
#include <type_traits>
 
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>& A) { copy(A); }
 
 
    Array2D(Array2D<E>&& A)
        : m_vpStart(A.m_vpStart)
        , m_lenDim2(A.m_lenDim2)
        , m_pStart(A.m_pStart)
        , m_pStop(A.m_pStop)
        , m_a(A.m_a)
        , m_b(A.m_b)
        , m_c(A.m_c)
        , m_d(A.m_d) {
        A.construct(0, -1, 0, -1);
    }
 
    ~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);
        OGDF_ASSERT(i <= m_b);
        OGDF_ASSERT(m_c <= j);
        OGDF_ASSERT(j <= m_d);
        return m_vpStart[size_t(i - m_a) * m_lenDim2 + j];
    }
 
    E& operator()(int i, int j) {
        OGDF_ASSERT(m_a <= i);
        OGDF_ASSERT(i <= m_b);
        OGDF_ASSERT(m_c <= j);
        OGDF_ASSERT(j <= m_d);
        return m_vpStart[size_t(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;
    }
 
 
    Array2D<E>& operator=(Array2D<E>&& A) {
        deconstruct();
 
        m_vpStart = A.m_vpStart;
        m_pStart = A.m_pStart;
        m_pStop = A.m_pStop;
        m_lenDim2 = A.m_lenDim2;
        m_a = A.m_a;
        m_b = A.m_b;
        m_c = A.m_c;
        m_d = A.m_d;
 
        A.construct(0, -1, 0, -1);
        return *this;
    }
 
    void fill(const E& x) {
        E* pDest = m_pStop;
        while (pDest > m_pStart) {
            *--pDest = x;
        }
    }
 
private:
    E* m_vpStart; 
    int m_lenDim2; 
    E* m_pStart; 
    E* m_pStop; 
 
    int m_a; 
    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;
 
    size_t lenDim1 = b - a + 1;
    m_lenDim2 = d - c + 1;
 
    if (lenDim1 < 1 || m_lenDim2 < 1) {
        m_pStart = m_vpStart = m_pStop = nullptr;
 
    } else {
        size_t len = lenDim1 * m_lenDim2;
        m_pStart = static_cast<E*>(malloc(len * sizeof(E)));
        if (m_pStart == nullptr) {
            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 (!std::is_trivially_destructible<E>::value) {
        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 {
    // matrix must be quadratic
    OGDF_ASSERT(size1() == size2());
 
    int a = m_a;
    int b = m_b;
    int c = m_c;
    int d = m_d;
    int n = m_lenDim2;
 
    int i, j;
    int column;
 
    float determinant = 0.0;
 
    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++) {
            int rem_i = 0;
            int 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;
}
 
}