Array.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/exceptions.h>
#include <ogdf/basic/memory.h>
 
#include <algorithm>
#include <cstdlib>
#include <initializer_list>
#include <new>
#include <ostream>
#include <random>
#include <type_traits>
 
namespace ogdf {
 
template<class E, bool isConst>
class ArrayReverseIteratorBase;
template<class E, class INDEX>
class ArrayBuffer;
 
template<class E>
using ArrayConstIterator = const E*;
template<class E>
using ArrayIterator = E*;
template<class E>
using ArrayConstReverseIterator = ArrayReverseIteratorBase<E, true>;
template<class E>
using ArrayReverseIterator = ArrayReverseIteratorBase<E, false>;
 
 
template<class E, bool isConst>
class ArrayReverseIteratorBase {
    friend class ArrayReverseIteratorBase<E, !isConst>;
 
    using Elem = typename std::conditional<isConst, const E, E>::type;
 
    Elem* m_pX;
 
public:
    ArrayReverseIteratorBase(E* pX) : m_pX(pX) { }
 
    template<bool isConstSFINAE = isConst, typename std::enable_if<isConstSFINAE, int>::type = 0>
    ArrayReverseIteratorBase(const E* pX) : m_pX(pX) { }
 
    ArrayReverseIteratorBase() : ArrayReverseIteratorBase(nullptr) { }
 
    template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0>
    ArrayReverseIteratorBase(const ArrayReverseIteratorBase<E, isArgConst>& it)
        : ArrayReverseIteratorBase(it.m_pX) { }
 
    ArrayReverseIteratorBase(const ArrayReverseIteratorBase<E, isConst>& it)
        : ArrayReverseIteratorBase(it.m_pX) { }
 
    operator std::conditional<isConst, const E, E>*() const { return m_pX; }
 
    bool operator==(const ArrayReverseIteratorBase<E, isConst>& it) const {
        return m_pX == it.m_pX;
    }
 
    bool operator!=(const ArrayReverseIteratorBase<E, isConst>& it) const {
        return m_pX != it.m_pX;
    }
 
    Elem& operator*() const { return *m_pX; }
 
    ArrayReverseIteratorBase<E, isConst>& operator=(const ArrayReverseIteratorBase<E, isConst>& it) {
        m_pX = it.m_pX;
        return *this;
    }
 
    ArrayReverseIteratorBase<E, isConst>& operator++() {
        m_pX--;
        return *this;
    }
 
    ArrayReverseIteratorBase<E, isConst> operator++(int) {
        ArrayReverseIteratorBase<E, isConst> it = *this;
        m_pX--;
        return it;
    }
 
    ArrayReverseIteratorBase<E, isConst>& operator--() {
        m_pX++;
        return *this;
    }
 
    ArrayReverseIteratorBase<E, isConst> operator--(int) {
        ArrayReverseIteratorBase<E, isConst> it = *this;
        m_pX++;
        return it;
    }
 
    ArrayReverseIteratorBase<E, isConst>& operator+=(const int& rhs) {
        m_pX -= rhs;
        return *this;
    }
 
    ArrayReverseIteratorBase<E, isConst>& operator-=(const int& rhs) {
        m_pX += rhs;
        return *this;
    }
 
    ArrayReverseIteratorBase<E, isConst> operator+(const int& rhs) {
        return ArrayReverseIteratorBase<E, isConst>(m_pX - rhs);
    }
 
    friend ArrayReverseIteratorBase<E, isConst> operator+(const int& lhs,
            ArrayReverseIteratorBase<E, isConst> rhs) {
        return ArrayReverseIteratorBase<E, isConst>(rhs.m_pX - lhs);
    }
 
    ArrayReverseIteratorBase<E, isConst> operator-(const int& rhs) {
        return ArrayReverseIteratorBase<E, isConst>(m_pX + rhs);
    }
 
    template<bool isArgConst>
    int operator-(ArrayReverseIteratorBase<E, isArgConst>& rhs) {
        return rhs.m_pX - m_pX;
    }
 
    bool operator<(ArrayReverseIteratorBase<E, isConst>& it) const { return m_pX > it.m_pX; }
 
    bool operator>(ArrayReverseIteratorBase<E, isConst>& it) const { return m_pX < it.m_pX; }
 
    bool operator<=(ArrayReverseIteratorBase<E, isConst>& it) const { return m_pX >= it.m_pX; }
 
    bool operator>=(ArrayReverseIteratorBase<E, isConst>& it) const { return m_pX <= it.m_pX; }
 
    Elem& operator[](std::size_t idx) { return m_pX[-idx]; }
 
    const Elem& operator[](std::size_t idx) const { return m_pX[-idx]; }
 
    OGDF_NEW_DELETE
};
 
 
template<class E, class INDEX = int>
class Array {
public:
    static const int maxSizeInsertionSort = 40;
 
    using value_type = E;
    using reference = E&;
    using const_reference = const E&;
    using const_iterator = ArrayConstIterator<E>;
    using iterator = ArrayIterator<E>;
    using const_reverse_iterator = ArrayConstReverseIterator<E>;
    using reverse_iterator = ArrayReverseIterator<E>;
 
    Array() { construct(0, -1); }
 
    explicit Array(INDEX s) : Array(0, s - 1) { }
 
    Array(INDEX a, INDEX b) {
        construct(a, b);
        initialize();
    }
 
    Array(INDEX a, INDEX b, const E& x) {
        construct(a, b);
        initialize(x);
    }
 
 
    Array(std::initializer_list<E> initList) {
        construct(0, ((INDEX)initList.size()) - 1);
        initialize(initList);
    }
 
    Array(const Array<E, INDEX>& A) { copy(A); }
 
 
    Array(Array<E, INDEX>&& A) noexcept
        : m_vpStart(A.m_vpStart)
        , m_pStart(A.m_pStart)
        , m_pStop(A.m_pStop)
        , m_low(A.m_low)
        , m_high(A.m_high) {
        A.construct(0, -1);
    }
 
    Array(const ArrayBuffer<E, INDEX>& A);
 
    ~Array() { deconstruct(); }
 
 
    INDEX low() const { return m_low; }
 
    INDEX high() const { return m_high; }
 
    INDEX size() const { return m_high - m_low + 1; }
 
    bool empty() const { return size() == 0; }
 
    const_reference operator[](INDEX i) const {
        OGDF_ASSERT(m_low <= i);
        OGDF_ASSERT(i <= m_high);
        return m_vpStart[i];
    }
 
    reference operator[](INDEX i) {
        OGDF_ASSERT(m_low <= i);
        OGDF_ASSERT(i <= m_high);
        return m_vpStart[i];
    }
 
 
 
    iterator begin() { return m_pStart; }
 
    const_iterator begin() const { return m_pStart; }
 
    const_iterator cbegin() const { return m_pStart; }
 
    iterator end() { return m_pStop; }
 
    const_iterator end() const { return m_pStop; }
 
    const_iterator cend() const { return m_pStop; }
 
    reverse_iterator rbegin() { return m_pStop - 1; }
 
    const_reverse_iterator rbegin() const { return m_pStop - 1; }
 
    const_reverse_iterator crbegin() const { return m_pStop - 1; }
 
    reverse_iterator rend() { return m_pStart - 1; }
 
    const_reverse_iterator rend() const { return m_pStart - 1; }
 
    const_reverse_iterator crend() const { return m_pStart - 1; }
 
 
 
    void init() {
        deconstruct();
        construct(0, -1);
    }
 
 
    void init(INDEX s) { init(0, s - 1); }
 
 
    void init(INDEX a, INDEX b) {
        deconstruct();
        construct(a, b);
        initialize();
    }
 
    void init(INDEX a, INDEX b, const E& x) {
        deconstruct();
        construct(a, b);
        initialize(x);
    }
 
    void fill(const E& x) {
        E* pDest = m_pStop;
        while (pDest > m_pStart) {
            *--pDest = x;
        }
    }
 
    void fill(INDEX i, INDEX j, const E& x) {
        OGDF_ASSERT(m_low <= i);
        OGDF_ASSERT(i <= m_high);
        OGDF_ASSERT(m_low <= j);
        OGDF_ASSERT(j <= m_high);
 
        E *pI = m_vpStart + i, *pJ = m_vpStart + j + 1;
        while (pJ > pI) {
            *--pJ = x;
        }
    }
 
 
    void grow(INDEX add, const E& x);
 
 
    void grow(INDEX add);
 
 
    void resize(INDEX newSize, const E& x) { grow(newSize - size(), x); }
 
 
    void resize(INDEX newSize) { grow(newSize - size()); }
 
    Array<E, INDEX>& operator=(const Array<E, INDEX>& A) {
        deconstruct();
        copy(A);
        return *this;
    }
 
 
    Array<E, INDEX>& operator=(Array<E, INDEX>&& A) {
        deconstruct();
 
        m_vpStart = A.m_vpStart;
        m_pStart = A.m_pStart;
        m_pStop = A.m_pStop;
        m_low = A.m_low;
        m_high = A.m_high;
 
        A.construct(0, -1);
        return *this;
    }
 
 
    bool operator==(const Array<E, INDEX>& L) const {
        if (size() != L.size()) {
            return false;
        }
 
        auto thisIterator = begin();
        auto thatIterator = L.begin();
 
        while (thisIterator != end() && thatIterator != L.end()) {
            if (*thisIterator != *thatIterator) {
                return false;
            }
            ++thisIterator;
            ++thatIterator;
        }
 
        OGDF_ASSERT(thisIterator == end() && thatIterator == L.end());
        return true;
    }
 
    bool operator!=(const Array<E, INDEX>& L) const { return !operator==(L); }
 
 
 
    void swap(INDEX i, INDEX j) {
        OGDF_ASSERT(m_low <= i);
        OGDF_ASSERT(i <= m_high);
        OGDF_ASSERT(m_low <= j);
        OGDF_ASSERT(j <= m_high);
 
        std::swap(m_vpStart[i], m_vpStart[j]);
    }
 
    void permute(INDEX l, INDEX r) {
        std::minstd_rand rng(randomSeed());
        permute(l, r, rng);
    }
 
    void permute() { permute(low(), high()); }
 
    template<class RNG>
    void permute(INDEX l, INDEX r, RNG& rng);
 
    template<class RNG>
    void permute(RNG& rng) {
        if (!empty()) {
            permute(low(), high(), rng);
        }
    }
 
 
 
 
    inline int binarySearch(const E& e) const {
        return binarySearch(low(), high(), e, StdComparer<E>());
    }
 
 
    inline int binarySearch(INDEX l, INDEX r, const E& e) const {
        return binarySearch(l, r, e, StdComparer<E>());
    }
 
 
    template<class COMPARER>
    inline int binarySearch(const E& e, const COMPARER& comp) const {
        return binarySearch(low(), high(), e, comp);
    }
 
 
    template<class COMPARER>
    INDEX binarySearch(INDEX l, INDEX r, const E& e, const COMPARER& comp) const {
        if (r < l) {
            return low() - 1;
        }
        while (r > l) {
            INDEX m = (r + l) / 2;
            if (comp.greater(e, m_vpStart[m])) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return comp.equal(e, m_vpStart[l]) ? l : low() - 1;
    }
 
 
    inline INDEX linearSearch(const E& e) const {
        int i;
        for (i = size(); i-- > 0;) {
            if (e == m_pStart[i]) {
                break;
            }
        }
        return i + low();
    }
 
 
    template<class COMPARER>
    INDEX linearSearch(const E& e, const COMPARER& comp) const {
        int i;
        for (i = size(); i-- > 0;) {
            if (comp.equal(e, m_pStart[i])) {
                break;
            }
        }
        return i + low();
    }
 
    inline void quicksort() { quicksort(StdComparer<E>()); }
 
    inline void quicksort(INDEX l, INDEX r) { quicksort(l, r, StdComparer<E>()); }
 
 
    template<class COMPARER>
    inline void quicksort(const COMPARER& comp) {
        if (low() < high()) {
            quicksortInt(m_pStart, m_pStop - 1, comp);
        }
    }
 
 
    template<class COMPARER>
    void quicksort(INDEX l, INDEX r, const COMPARER& comp) {
        OGDF_ASSERT(low() <= l);
        OGDF_ASSERT(l <= high());
        OGDF_ASSERT(low() <= r);
        OGDF_ASSERT(r <= high());
        if (l < r) {
            quicksortInt(m_vpStart + l, m_vpStart + r, comp);
        }
    }
 
 
    void leftShift(ArrayBuffer<INDEX, INDEX>& ind);
 
 
    void leftShift(ArrayBuffer<INDEX, INDEX>& ind, const E& val) {
        leftShift(ind);
        fill(high() - ind.size(), high(), val);
    }
 
 
    template<class F, class I>
    friend class ArrayBuffer; // for efficient ArrayBuffer::compact-method
 
private:
    E* m_vpStart; 
    E* m_pStart; 
    E* m_pStop; 
    INDEX m_low; 
    INDEX m_high; 
 
    void construct(INDEX a, INDEX b);
 
    void initialize();
 
    void initialize(const E& x);
 
    void initialize(std::initializer_list<E> initList);
 
    void deconstruct();
 
    void copy(const Array<E, INDEX>& A);
 
    void expandArray(INDEX add);
 
    template<typename EE = E, typename std::enable_if<OGDF_TRIVIALLY_COPYABLE<EE>::value, int>::type = 0>
    void expandArrayHelper(INDEX sOld, INDEX sNew) {
        // If the element type is trivially copiable, just use realloc.
        E* p = static_cast<E*>(realloc(m_pStart, sNew * sizeof(E)));
        if (p == nullptr) {
            OGDF_THROW(InsufficientMemoryException);
        }
        m_pStart = p;
    }
 
    template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE<EE>::value, int>::type = 0>
    void expandArrayHelper(INDEX sOld, INDEX sNew) {
        // If the element type is not trivially copiable,
        // allocate a new block, move the elements, and free the old block.
        E* p = static_cast<E*>(malloc(sNew * sizeof(E)));
        if (p == nullptr) {
            OGDF_THROW(InsufficientMemoryException);
        }
 
        for (int i = 0; i < min(sOld, sNew); ++i) {
            new (&p[i]) E(std::move(m_pStart[i]));
        }
 
        deconstruct();
        m_pStart = p;
    }
 
    template<class COMPARER>
    static void quicksortInt(E* pL, E* pR, const COMPARER& comp) {
        size_t s = pR - pL;
 
        // use insertion sort for small instances
        if (s < maxSizeInsertionSort) {
            for (E* pI = pL + 1; pI <= pR; pI++) {
                E v = *pI;
                E* pJ = pI;
                while (--pJ >= pL && comp.less(v, *pJ)) {
                    *(pJ + 1) = *pJ;
                }
                *(pJ + 1) = v;
            }
            return;
        }
 
        E *pI = pL, *pJ = pR;
        E x = *(pL + (s >> 1));
 
        do {
            while (comp.less(*pI, x)) {
                pI++;
            }
            while (comp.less(x, *pJ)) {
                pJ--;
            }
            if (pI <= pJ) {
                std::swap(*pI++, *pJ--);
            }
        } while (pI <= pJ);
 
        if (pL < pJ) {
            quicksortInt(pL, pJ, comp);
        }
        if (pI < pR) {
            quicksortInt(pI, pR, comp);
        }
    }
 
    OGDF_NEW_DELETE
};
 
// enlarges storage for array and moves old entries
template<class E, class INDEX>
void Array<E, INDEX>::expandArray(INDEX add) {
    INDEX sOld = size(), sNew = sOld + add;
 
    // expand allocated memory block
    if (m_pStart != nullptr) {
        expandArrayHelper(sOld, sNew);
    } else {
        m_pStart = static_cast<E*>(malloc(sNew * sizeof(E)));
        if (m_pStart == nullptr) {
            OGDF_THROW(InsufficientMemoryException);
        }
    }
 
    m_vpStart = m_pStart - m_low;
    m_pStop = m_pStart + sNew;
    m_high += add;
}
 
// enlarges array by add elements and sets new elements to x
template<class E, class INDEX>
void Array<E, INDEX>::grow(INDEX add, const E& x) {
    if (add == 0) {
        return;
    }
 
    INDEX sOld = size();
    expandArray(add);
 
    // initialize new array entries
    for (E* pDest = m_pStart + sOld; pDest < m_pStop; pDest++) {
        new (pDest) E(x);
    }
}
 
// enlarges array by add elements (initialized with default constructor)
template<class E, class INDEX>
void Array<E, INDEX>::grow(INDEX add) {
    if (add == 0) {
        return;
    }
 
    INDEX sOld = size();
    expandArray(add);
 
    // initialize new array entries
    for (E* pDest = m_pStart + sOld; pDest < m_pStop; pDest++) {
        new (pDest) E();
    }
}
 
template<class E, class INDEX>
void Array<E, INDEX>::construct(INDEX a, INDEX b) {
    m_low = a;
    m_high = b;
    INDEX s = b - a + 1;
 
    if (s < 1) {
        m_pStart = m_vpStart = m_pStop = nullptr;
 
    } else {
        m_pStart = static_cast<E*>(malloc(s * sizeof(E)));
        if (m_pStart == nullptr) {
            OGDF_THROW(InsufficientMemoryException);
        }
 
        m_vpStart = m_pStart - a;
        m_pStop = m_pStart + s;
    }
}
 
template<class E, class INDEX>
void Array<E, INDEX>::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, class INDEX>
void Array<E, INDEX>::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, class INDEX>
void Array<E, INDEX>::initialize(std::initializer_list<E> initList) {
    E* pDest = m_pStart;
    try {
        for (const E& x : initList) {
            new (pDest++) E(x);
        }
    } catch (...) {
        while (--pDest >= m_pStart) {
            pDest->~E();
        }
        free(m_pStart);
        throw;
    }
}
 
template<class E, class INDEX>
void Array<E, INDEX>::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, class INDEX>
void Array<E, INDEX>::copy(const Array<E, INDEX>& array2) {
    construct(array2.m_low, array2.m_high);
 
    if (m_pStart != nullptr) {
        E* pSrc = array2.m_pStop;
        E* pDest = m_pStop;
        while (pDest > m_pStart)
#if 0
            *--pDest = *--pSrc;
#endif
            new (--pDest) E(*--pSrc);
    }
}
 
// permutes array a from a[l] to a[r] randomly
template<class E, class INDEX>
template<class RNG>
void Array<E, INDEX>::permute(INDEX l, INDEX r, RNG& rng) {
    OGDF_ASSERT(low() <= l);
    OGDF_ASSERT(l <= high());
    OGDF_ASSERT(low() <= r);
    OGDF_ASSERT(r <= high());
 
    std::uniform_int_distribution<int> dist(0, r - l);
 
    E *pI = m_vpStart + l, *pStart = m_vpStart + l, *pStop = m_vpStart + r;
    while (pI <= pStop) {
        std::swap(*pI++, *(pStart + dist(rng)));
    }
}
 
template<class E, class INDEX>
void print(std::ostream& os, const Array<E, INDEX>& a, char delim = ' ') {
    for (int i = a.low(); i <= a.high(); i++) {
        if (i > a.low()) {
            os << delim;
        }
        os << a[i];
    }
}
 
template<class E, class INDEX>
std::ostream& operator<<(std::ostream& os, const ogdf::Array<E, INDEX>& a) {
    print(os, a);
    return os;
}
 
}
 
namespace ogdf {
 
template<class E, class INDEX>
void Array<E, INDEX>::leftShift(ArrayBuffer<INDEX, INDEX>& ind) {
    const INDEX nInd = ind.size();
    if (nInd == 0) {
        return;
    }
 
    OGDF_ASSERT(ind[0] >= low());
    OGDF_ASSERT(ind[0] <= high());
 
    INDEX j, current = ind[0];
    for (INDEX i = 0; i < nInd - 1; i++) {
        OGDF_ASSERT(ind[i + 1] >= low());
        OGDF_ASSERT(ind[i + 1] <= high());
 
        const INDEX last = ind[i + 1];
        for (j = ind[i] + 1; j < last; j++) {
            m_vpStart[current++] = m_vpStart[j];
        }
    }
 
    for (j = ind[nInd - 1] + 1; j < size(); j++) {
        m_vpStart[current++] = m_vpStart[j];
    }
}
 
template<class E, class INDEX>
Array<E, INDEX>::Array(const ArrayBuffer<E, INDEX>& A) {
    construct(0, -1);
    A.compactCopy(*this);
}
 
}