ArrayBuffer.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h> // IWYU pragma: keep
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/memory.h>
 
#include <algorithm>
#include <cstring>
#include <limits>
#include <ostream>
#include <random>
#include <type_traits>
 
namespace ogdf {
 
 
template<class E, class INDEX = int>
class ArrayBuffer : private Array<E, INDEX> {
    INDEX num; 
    bool growable;
 
public:
    using key_type = INDEX;
    using value_type = E;
    using const_iterator = typename Array<E, INDEX>::const_iterator;
    using iterator = typename Array<E, INDEX>::iterator;
    using const_reverse_iterator = typename Array<E, INDEX>::const_reverse_iterator;
    using reverse_iterator = typename Array<E, INDEX>::reverse_iterator;
 
    ArrayBuffer() : Array<E, INDEX>(), num(0), growable(true) { }
 
    explicit ArrayBuffer(INDEX size, bool autogrow = true)
        : Array<E, INDEX>(size), num(0), growable(autogrow) { }
 
    explicit ArrayBuffer(const Array<E, INDEX>& source, bool autogrow = true)
        : Array<E, INDEX>(source), num(0), growable(autogrow) { }
 
    ArrayBuffer(const ArrayBuffer<E, INDEX>& buffer)
        : Array<E, INDEX>(buffer), num(buffer.num), growable(buffer.growable) { }
 
 
    ArrayBuffer(ArrayBuffer<E, INDEX>&& buffer)
        : Array<E, INDEX>(std::move(buffer)), num(buffer.num), growable(buffer.growable) {
        buffer.num = 0;
        buffer.growable = true;
    }
 
    void clear() { num = 0; }
 
 
    void leftShift(ArrayBuffer<INDEX, INDEX>& ind) {
        const INDEX nInd = ind.size();
        if (nInd == 0) {
            return;
        }
 
        OGDF_ASSERT(ind[0] >= 0);
        OGDF_ASSERT(ind[0] < num);
 
        INDEX j, current = ind[0];
        for (INDEX i = 0; i < nInd - 1; i++) {
            OGDF_ASSERT(ind[i + 1] >= 0);
            OGDF_ASSERT(ind[i + 1] < num);
 
            const INDEX last = ind[i + 1];
            for (j = ind[i] + 1; j < last; j++) {
                operator[](current++) = operator[](j);
            }
        }
 
        for (j = ind[nInd - 1] + 1; j < size(); j++) {
            operator[](current++) = operator[](j);
        }
 
        num -= nInd;
    }
 
    bool isGrowable() const { return growable; }
 
    void setGrowable(bool _growable) { growable = _growable; }
 
 
    iterator begin() { return Array<E, INDEX>::begin(); }
 
    const_iterator begin() const { return Array<E, INDEX>::begin(); }
 
    iterator end() { return Array<E, INDEX>::begin() + num; }
 
    const_iterator end() const { return Array<E, INDEX>::begin() + num; }
 
    reverse_iterator rbegin() { return Array<E, INDEX>::begin() + (num - 1); }
 
    const_reverse_iterator rbegin() const { return Array<E, INDEX>::begin() + (num - 1); }
 
    reverse_iterator rend() { return Array<E, INDEX>::rend(); }
 
    const_reverse_iterator rend() const { return Array<E, INDEX>::rend(); }
 
 
 
    const E& operator[](INDEX i) const {
        OGDF_ASSERT(0 <= i);
        OGDF_ASSERT(i < num);
        return Array<E, INDEX>::operator[](i);
    }
 
    E& operator[](INDEX i) {
        OGDF_ASSERT(0 <= i);
        OGDF_ASSERT(i < num);
        return Array<E, INDEX>::operator[](i);
    }
 
    const E& top() const {
        OGDF_ASSERT(num > 0);
        return Array<E, INDEX>::operator[](num - 1);
    }
 
    E& top() {
        OGDF_ASSERT(num > 0);
        return Array<E, INDEX>::operator[](num - 1);
    }
 
    void push(E e) {
        if (num == Array<E, INDEX>::size()) {
            OGDF_ASSERT(growable);
            Array<E, INDEX>::grow(max(num, static_cast<INDEX>(1))); // double the size
        }
        Array<E, INDEX>::operator[](num++) = e;
    }
 
    void pop() {
        OGDF_ASSERT(num > 0);
        --num;
    }
 
    E popRet() {
        OGDF_ASSERT(num > 0);
        return Array<E, INDEX>::operator[](--num);
    }
 
    bool empty() const { return !num; }
 
    bool full() const { return !growable && num == Array<E, INDEX>::size(); }
 
    INDEX size() const { return num; }
 
    INDEX capacity() const { return Array<E, INDEX>::size(); }
 
 
 
    void init() { Array<E, INDEX>::init(); }
 
    void init(INDEX size) { Array<E, INDEX>::init(size); }
 
    ArrayBuffer<E, INDEX>& operator=(const ArrayBuffer<E, INDEX>& buffer) {
        Array<E, INDEX>::operator=(buffer);
        num = buffer.num;
        growable = buffer.growable;
        return *this;
    }
 
 
    ArrayBuffer<E, INDEX>& operator=(ArrayBuffer<E, INDEX>&& buffer) {
        Array<E, INDEX>::operator=(std::move(buffer));
        num = buffer.num;
        growable = buffer.growable;
        buffer.num = 0;
        buffer.growable = true;
        return *this;
    }
 
 
    void compactCpycon(Array<E, INDEX>& A2) const {
        OGDF_ASSERT(this != &A2);
        if (num) {
            INDEX tmp = Array<E, INDEX>::m_high; // thank god i'm a friend of Array
            Array<E, INDEX>::m_high = num - 1; // fake smaller size
            A2.copy(*this); // copy
            Array<E, INDEX>::m_high = tmp;
        } else {
            A2.init(0);
        }
    }
 
 
    template<typename EE = E, typename std::enable_if<!OGDF_TRIVIALLY_COPYABLE<EE>::value, int>::type = 0>
    void compactCopy(Array<E, INDEX>& A2) const {
        OGDF_ASSERT(this != &A2);
        if (num) {
            A2.init(num);
            for (INDEX i = num; i-- > 0;) {
                A2[i] = (*this)[i];
            }
        } else {
            A2.init(0);
        }
    }
 
 
    template<typename EE = E, typename std::enable_if<OGDF_TRIVIALLY_COPYABLE<EE>::value, int>::type = 0>
    void compactCopy(Array<E, INDEX>& A2) const {
        OGDF_ASSERT(this != &A2);
        if (num) {
            A2.init(num);
            OGDF_ASSERT(sizeof(E) <= size_t(std::numeric_limits<INDEX>::max() / num));
 
            memcpy(A2.m_pStart, this->m_pStart,
                    sizeof(E) <= size_t(std::numeric_limits<INDEX>::max() / num)
                            ? sizeof(E) * num
                            : size_t(std::numeric_limits<INDEX>::max()));
        } else {
            A2.init(0);
        }
    }
 
 
    bool operator==(const ArrayBuffer<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 ArrayBuffer<E, INDEX>& L) const { return !operator==(L); }
 
 
 
 
    INDEX linearSearch(const E& x) const {
        INDEX i;
        for (i = num; i-- > 0;) {
            if (x == Array<E, INDEX>::m_vpStart[i]) {
                break;
            }
        }
        return i;
    }
 
 
    template<class COMPARER>
    INDEX linearSearch(const E& x, const COMPARER& comp) const {
        INDEX i;
        for (i = num; i-- > 0;) {
            if (comp.equal(x, Array<E, INDEX>::m_vpStart[i])) {
                break;
            }
        }
        return i;
    }
 
    inline void quicksort() {
        if (num == 0) {
            return;
        }
        Array<E, INDEX>::quicksort(0, num - 1, StdComparer<E>());
    }
 
 
    template<class COMPARER>
    inline void quicksort(const COMPARER& comp) {
        if (num == 0) {
            return;
        }
        Array<E, INDEX>::quicksort(0, num - 1, comp);
    }
 
 
    inline INDEX binarySearch(const E& e) const {
        return Array<E, INDEX>::binarySearch(0, num - 1, e, StdComparer<E>());
    }
 
 
    template<class COMPARER>
    inline INDEX binarySearch(const E& e, const COMPARER& comp) const {
        return Array<E, INDEX>::binarySearch(0, num - 1, e, comp);
    }
 
 
 
    using Array<E, INDEX>::swap;
 
    template<class RNG>
    void permute(INDEX l, INDEX r, RNG& rng) {
        Array<E, INDEX>::permute(l, r, rng);
    }
 
    template<class RNG>
    void permute(RNG& rng) {
        permute(0, num - 1, rng);
    }
 
    void permute(INDEX l, INDEX r) {
        std::minstd_rand rng(randomSeed());
        permute(l, r, rng);
    }
 
    void permute() { permute(0, num - 1); }
 
 
 
    void setCapacity(INDEX newCapacity) { Array<E, INDEX>::resize(newCapacity); }
 
    OGDF_NEW_DELETE
};
 
template<class E, class INDEX>
void print(std::ostream& os, const ArrayBuffer<E, INDEX>& a, char delim = ' ') {
    for (int i = 0; i < a.size(); i++) {
        if (i > 0) {
            os << delim;
        }
        os << a[i];
    }
}
 
template<class E, class INDEX>
std::ostream& operator<<(std::ostream& os, const ogdf::ArrayBuffer<E, INDEX>& a) {
    print(os, a);
    return os;
}
 
}