GraphList.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/internal/config_autogen.h>
#include <ogdf/basic/internal/graph_iterators.h>
#include <ogdf/basic/memory.h>
 
#include <iterator>
#include <random>
#include <utility>
 
namespace ogdf {
 
class ClusterGraph;
class CombinatorialEmbedding;
class ConstCombinatorialEmbedding;
class Graph;
 
namespace internal {
 
 
 
class OGDF_EXPORT GraphElement {
    friend class ogdf::Graph;
    friend class GraphListBase;
 
protected:
    GraphElement* m_next = nullptr; 
    GraphElement* m_prev = nullptr; 
 
    OGDF_NEW_DELETE
};
 
class OGDF_EXPORT GraphListBase {
protected:
    int m_size; 
    GraphElement* m_head; 
    GraphElement* m_tail; 
 
public:
    GraphListBase() {
        m_head = m_tail = nullptr;
        m_size = 0;
    }
 
    ~GraphListBase() { }
 
    int size() const { return m_size; }
 
    bool empty() const { return m_size == 0; }
 
    void pushBack(GraphElement* pX) {
        pX->m_next = nullptr;
        pX->m_prev = m_tail;
        if (m_head) {
            m_tail = m_tail->m_next = pX;
        } else {
            m_tail = m_head = pX;
        }
        ++m_size;
    }
 
    void insertAfter(GraphElement* pX, GraphElement* pY) {
        pX->m_prev = pY;
        GraphElement* pYnext = pX->m_next = pY->m_next;
        pY->m_next = pX;
        if (pYnext) {
            pYnext->m_prev = pX;
        } else {
            m_tail = pX;
        }
        ++m_size;
    }
 
    void insertBefore(GraphElement* pX, GraphElement* pY) {
        pX->m_next = pY;
        GraphElement* pYprev = pX->m_prev = pY->m_prev;
        pY->m_prev = pX;
        if (pYprev) {
            pYprev->m_next = pX;
        } else {
            m_head = pX;
        }
        ++m_size;
    }
 
    void del(GraphElement* pX) {
        GraphElement *pxPrev = pX->m_prev, *pxNext = pX->m_next;
 
        if (pxPrev) {
            pxPrev->m_next = pxNext;
        } else {
            m_head = pxNext;
        }
        if (pxNext) {
            pxNext->m_prev = pxPrev;
        } else {
            m_tail = pxPrev;
        }
        m_size--;
    }
 
    template<class LIST>
    void sort(const LIST& newOrder) {
        using std::begin;
        using std::end;
        sort(begin(newOrder), end(newOrder));
    }
 
    template<class IT>
    void sort(IT begin, IT end) {
        if (begin == end) {
            return;
        }
        m_head = *begin;
        GraphElement* pPred = nullptr;
        for (auto it = begin; it != end; ++it) {
            GraphElement* p = *it;
            if ((p->m_prev = pPred) != nullptr) {
                pPred->m_next = p;
            }
            pPred = p;
        }
        (m_tail = pPred)->m_next = nullptr;
    }
 
    void reverse() {
        GraphElement* pX = m_head;
        m_head = m_tail;
        m_tail = pX;
        while (pX) {
            GraphElement* pY = pX->m_next;
            pX->m_next = pX->m_prev;
            pX = pX->m_prev = pY;
        }
    }
 
    void swap(GraphElement* pX, GraphElement* pY) {
        if (pX->m_next == pY) {
            pX->m_next = pY->m_next;
            pY->m_prev = pX->m_prev;
            pY->m_next = pX;
            pX->m_prev = pY;
 
        } else if (pY->m_next == pX) {
            pY->m_next = pX->m_next;
            pX->m_prev = pY->m_prev;
            pX->m_next = pY;
            pY->m_prev = pX;
 
        } else {
            std::swap(pX->m_next, pY->m_next);
            std::swap(pX->m_prev, pY->m_prev);
        }
 
        if (pX->m_prev) {
            pX->m_prev->m_next = pX;
        } else {
            m_head = pX;
        }
        if (pX->m_next) {
            pX->m_next->m_prev = pX;
        } else {
            m_tail = pX;
        }
 
        if (pY->m_prev) {
            pY->m_prev->m_next = pY;
        } else {
            m_head = pY;
        }
        if (pY->m_next) {
            pY->m_next->m_prev = pY;
        } else {
            m_tail = pY;
        }
 
#ifdef OGDF_DEBUG
        consistencyCheck();
#endif
    }
 
    template<class RNG>
    void permute(RNG& rng) {
        Array<GraphElement*> A(m_size + 2);
        A[0] = A[m_size + 1] = nullptr;
 
        int i = 1;
        GraphElement* pX;
        for (pX = m_head; pX; pX = pX->m_next) {
            A[i++] = pX;
        }
 
        A.permute(1, m_size, rng);
 
        for (i = 1; i <= m_size; i++) {
            pX = A[i];
            pX->m_next = A[i + 1];
            pX->m_prev = A[i - 1];
        }
 
        m_head = A[1];
        m_tail = A[m_size];
 
#ifdef OGDF_DEBUG
        consistencyCheck();
#endif
    }
 
    void permute() {
        std::minstd_rand rng(randomSeed());
        permute(rng);
    }
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const {
        OGDF_ASSERT((m_head == nullptr) == (m_tail == nullptr));
 
        if (m_head != nullptr) {
            OGDF_ASSERT(m_head->m_prev == nullptr);
            OGDF_ASSERT(m_tail->m_next == nullptr);
 
            for (GraphElement* pX = m_head; pX; pX = pX->m_next) {
                if (pX->m_prev) {
                    OGDF_ASSERT(pX->m_prev->m_next == pX);
                } else {
                    OGDF_ASSERT(pX == m_head);
                }
 
                if (pX->m_next) {
                    OGDF_ASSERT(pX->m_next->m_prev == pX);
                } else {
                    OGDF_ASSERT(pX == m_tail);
                }
            }
        }
    }
#endif
 
    OGDF_NEW_DELETE
};
 
 
template<class T>
class GraphList : protected GraphListBase {
public:
    using value_type = T*;
    using iterator = GraphIterator<T*>;
    using reverse_iterator = GraphReverseIterator<T*>;
 
    GraphList() { }
 
    ~GraphList() {
        if (m_head) {
            OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head, m_tail);
        }
    }
 
    using GraphListBase::empty;
    using GraphListBase::size;
 
    T* head() const { return static_cast<T*>(m_head); }
 
    T* tail() const { return static_cast<T*>(m_tail); }
 
    void pushBack(T* pX) { GraphListBase::pushBack(pX); }
 
    void insertAfter(T* pX, T* pY) { GraphListBase::insertAfter(pX, pY); }
 
    void insertBefore(T* pX, T* pY) { GraphListBase::insertBefore(pX, pY); }
 
    void move(T* pX, GraphList<T>& L, T* pY, Direction dir) {
        GraphListBase::del(pX);
        if (dir == Direction::after) {
            L.insertAfter(pX, pY);
        } else {
            L.insertBefore(pX, pY);
        }
    }
 
    void move(T* pX, GraphList<T>& L) {
        GraphListBase::del(pX);
        L.pushBack(pX);
    }
 
    void moveAfter(T* pX, T* pY) {
        GraphListBase::del(pX);
        insertAfter(pX, pY);
    }
 
    void moveBefore(T* pX, T* pY) {
        GraphListBase::del(pX);
        insertBefore(pX, pY);
    }
 
    void del(T* pX) {
        GraphListBase::del(pX);
        delete pX;
    }
 
    void delPure(T* pX) { GraphListBase::del(pX); }
 
    void clear() {
        if (m_head) {
            OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head, m_tail);
            m_head = m_tail = nullptr;
            m_size = 0;
        }
    }
 
    iterator begin() const { return GraphList<T>::head(); }
 
    iterator end() const { return iterator(); }
 
    reverse_iterator rbegin() const { return reverse_iterator(GraphList<T>::tail()); }
 
    reverse_iterator rend() const { return reverse_iterator(); }
 
    using GraphListBase::permute;
    using GraphListBase::reverse;
    using GraphListBase::sort;
 
    void swap(T* pX, T* pY) { GraphListBase::swap(pX, pY); }
 
#ifdef OGDF_DEBUG
    using GraphListBase::consistencyCheck;
#endif
};
 
template<class GraphObject>
class GraphObjectContainer : private GraphList<GraphObject> {
    friend class ogdf::Graph;
    friend class ogdf::ClusterGraph;
    friend class ogdf::ConstCombinatorialEmbedding;
    friend class ogdf::CombinatorialEmbedding;
 
public:
    using typename GraphList<GraphObject>::value_type;
    using typename GraphList<GraphObject>::iterator;
    using typename GraphList<GraphObject>::reverse_iterator;
 
    using GraphList<GraphObject>::begin;
    using GraphList<GraphObject>::rbegin;
    using GraphList<GraphObject>::end;
    using GraphList<GraphObject>::rend;
 
    using GraphList<GraphObject>::size;
    using GraphList<GraphObject>::empty;
    using GraphList<GraphObject>::head;
    using GraphList<GraphObject>::tail;
};
 
}
}