AdjEntryArray.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
 
namespace ogdf {
 
 
 
class AdjEntryArrayBase {
    ListIterator<AdjEntryArrayBase*> m_it;
 
public:
    const Graph* m_pGraph; 
 
    AdjEntryArrayBase() : m_pGraph(nullptr) { }
 
    explicit AdjEntryArrayBase(const Graph* pG) : m_pGraph(pG) {
        if (pG) {
            m_it = pG->registerArray(this);
        }
    }
 
    AdjEntryArrayBase(AdjEntryArrayBase& base) : m_it(base.m_it), m_pGraph(base.m_pGraph) {
        if (m_pGraph) {
            m_pGraph->moveRegisterArray(m_it, this);
        }
        base.m_pGraph = nullptr;
        base.m_it = ListIterator<AdjEntryArrayBase*>();
    }
 
    virtual ~AdjEntryArrayBase() {
        if (m_pGraph) {
            m_pGraph->unregisterArray(m_it);
        }
    }
 
    // event interface used by Graph
    virtual void enlargeTable(int newTableSize) = 0;
    virtual void reinit(int initTableSize) = 0;
    virtual void disconnect() = 0;
    virtual void resetIndex(int newIndex, int oldIndex) = 0;
 
    void reregister(const Graph* pG) {
        if (m_pGraph) {
            m_pGraph->unregisterArray(m_it);
        }
        if ((m_pGraph = pG) != nullptr) {
            m_it = pG->registerArray(this);
        }
    }
 
    void moveRegister(AdjEntryArrayBase& base) {
        if (m_pGraph) {
            m_pGraph->unregisterArray(m_it);
        }
        m_pGraph = base.m_pGraph;
        m_it = base.m_it;
        base.m_pGraph = nullptr;
        base.m_it = ListIterator<AdjEntryArrayBase*>();
        if (m_pGraph != nullptr) {
            m_pGraph->moveRegisterArray(m_it, this);
        }
    }
};
 
 
template<class T>
class AdjEntryArray : private Array<T>, protected AdjEntryArrayBase {
    T m_x; 
 
public:
    using key_type = adjEntry;
    using value_type = T;
 
    using iterator = internal::GraphArrayIterator<AdjEntryArray<T>>;
    using const_iterator = internal::GraphArrayConstIterator<AdjEntryArray<T>>;
 
    AdjEntryArray() : Array<T>(), AdjEntryArrayBase() { }
 
    explicit AdjEntryArray(const Graph& G)
        : Array<T>(G.adjEntryArrayTableSize()), AdjEntryArrayBase(&G) { }
 
 
    AdjEntryArray(const Graph& G, const T& x)
        : Array<T>(0, G.adjEntryArrayTableSize() - 1, x), AdjEntryArrayBase(&G), m_x(x) { }
 
 
    AdjEntryArray(const AdjEntryArray<T>& A)
        : Array<T>(A), AdjEntryArrayBase(A.m_pGraph), m_x(A.m_x) { }
 
 
    AdjEntryArray(AdjEntryArray<T>&& A)
        : Array<T>(std::move(A)), AdjEntryArrayBase(A), m_x(A.m_x) { }
 
 
    bool valid() const { return Array<T>::low() <= Array<T>::high(); }
 
    const Graph* graphOf() const { return m_pGraph; }
 
    const T& operator[](adjEntry adj) const {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(adj->graphOf() == m_pGraph);
        return Array<T>::operator[](adj->index());
    }
 
    T& operator[](adjEntry adj) {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(adj->graphOf() == m_pGraph);
        return Array<T>::operator[](adj->index());
    }
 
    const T& operator()(adjEntry adj) const {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(adj->graphOf() == m_pGraph);
        return Array<T>::operator[](adj->index());
    }
 
    T& operator()(adjEntry adj) {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(adj->graphOf() == m_pGraph);
        return Array<T>::operator[](adj->index());
    }
 
 
 
 
    iterator begin() { return iterator(findFirstKey(), this); }
 
 
    const_iterator begin() const { return const_iterator(findFirstKey(), this); }
 
 
    const_iterator cbegin() const { return const_iterator(findFirstKey(), this); }
 
 
    iterator end() { return iterator(nullptr, this); }
 
 
    const_iterator end() const { return const_iterator(nullptr, this); }
 
 
    const_iterator cend() const { return const_iterator(nullptr, this); }
 
 
 
    void init() {
        Array<T>::init();
        reregister(nullptr);
    }
 
    void init(const Graph& G) {
        Array<T>::init(G.adjEntryArrayTableSize());
        reregister(&G);
    }
 
 
    void init(const Graph& G, const T& x) {
        Array<T>::init(0, G.adjEntryArrayTableSize() - 1, m_x = x);
        reregister(&G);
    }
 
    void fill(const T& x) {
        int high = m_pGraph->maxAdjEntryIndex();
        if (high >= 0) {
            Array<T>::fill(0, high, x);
        }
    }
 
    AdjEntryArray<T>& operator=(const AdjEntryArray<T>& A) {
        Array<T>::operator=(A);
        m_x = A.m_x;
        reregister(A.m_pGraph);
        return *this;
    }
 
 
    AdjEntryArray<T>& operator=(AdjEntryArray<T>&& a) {
        Array<T>::operator=(std::move(a));
        m_x = a.m_x;
        moveRegister(a);
        return *this;
    }
 
 
 
    static adjEntry findSuccKey(adjEntry adj) {
        if (adj->succ() != nullptr) {
            return adj->succ();
        }
        node v = adj->theNode();
        for (v = v->succ(); v != nullptr && v->firstAdj() == nullptr; v = v->succ()) {
            ;
        }
        return (v != nullptr) ? v->firstAdj() : nullptr;
    }
 
    static adjEntry findPredKey(adjEntry adj) {
        if (adj->pred() != nullptr) {
            return adj->pred();
        }
        node v = adj->theNode();
        for (v = v->pred(); v != nullptr && v->lastAdj() == nullptr; v = v->pred()) {
            ;
        }
        return (v != nullptr) ? v->lastAdj() : nullptr;
    }
 
 
private:
    adjEntry findFirstKey() const {
        node v = m_pGraph->firstNode();
        while (v != nullptr && v->firstAdj() == nullptr) {
            v = v->succ();
        }
        adjEntry key = (v != nullptr) ? v->firstAdj() : nullptr;
        return key;
    }
 
    adjEntry findLastKey() const {
        node v = m_pGraph->lastNode();
        while (v != nullptr && v->lastAdj() == nullptr) {
            v = v->pred();
        }
        adjEntry key = (v != nullptr) ? v->lastAdj() : nullptr;
        return key;
    }
 
    virtual void enlargeTable(int newTableSize) {
        Array<T>::grow(newTableSize - Array<T>::size(), m_x);
    }
 
    virtual void reinit(int initTableSize) { Array<T>::init(0, initTableSize - 1, m_x); }
 
    virtual void resetIndex(int newIndex, int oldIndex) {
        Array<T>::operator[](newIndex) = Array<T>::operator[](oldIndex);
    }
 
    virtual void disconnect() {
        Array<T>::init();
        m_pGraph = nullptr;
    }
 
    OGDF_NEW_DELETE
};
 
}