graph_iterators.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Reverse.h>
#include <ogdf/basic/basic.h>
 
#include <functional>
 
namespace ogdf {
 
namespace internal {
 
template<class GraphObjectPtr, bool isReverse>
class GraphIteratorBase;
template<class GraphObjectPtr>
using GraphIterator = GraphIteratorBase<GraphObjectPtr, false>;
template<class GraphObjectPtr>
using GraphReverseIterator = GraphIteratorBase<GraphObjectPtr, true>;
 
template<class GraphObjectPtr, bool isReverse>
class GraphIteratorBase {
    friend class GraphIteratorBase<GraphObjectPtr, !isReverse>;
 
    GraphObjectPtr m_ptr;
 
public:
    GraphIteratorBase() : m_ptr(nullptr) { }
 
    GraphIteratorBase(GraphObjectPtr ptr) : m_ptr(ptr) { }
 
    template<bool isArgReverse>
    GraphIteratorBase(GraphIteratorBase<GraphObjectPtr, isArgReverse>& it) : m_ptr(it.m_ptr) { }
 
    bool operator==(const GraphIteratorBase<GraphObjectPtr, isReverse>& other) const {
        return m_ptr == other.m_ptr;
    }
 
    bool operator!=(const GraphIteratorBase<GraphObjectPtr, isReverse>& other) const {
        return m_ptr != other.m_ptr;
    }
 
    GraphObjectPtr& operator*() { return m_ptr; }
 
    GraphIteratorBase<GraphObjectPtr, isReverse>& operator++() {
        OGDF_ASSERT(m_ptr != nullptr);
        m_ptr = isReverse ? m_ptr->pred() : m_ptr->succ();
        return *this;
    }
 
    GraphIteratorBase<GraphObjectPtr, isReverse> operator++(int) {
        OGDF_ASSERT(m_ptr != nullptr);
        GraphObjectPtr ptr = m_ptr;
        m_ptr = isReverse ? m_ptr->pred() : m_ptr->succ();
        return ptr;
    }
 
    GraphIteratorBase<GraphObjectPtr, isReverse>& operator--() {
        OGDF_ASSERT(m_ptr != nullptr);
        m_ptr = isReverse ? m_ptr->succ() : m_ptr->pred();
        return *this;
    }
 
    GraphIteratorBase<GraphObjectPtr, isReverse> operator--(int) {
        OGDF_ASSERT(m_ptr != nullptr);
        GraphObjectPtr ptr = m_ptr;
        m_ptr = isReverse ? m_ptr->succ() : m_ptr->pred();
        return ptr;
    }
};
 
template<class ArrayType, bool isConst>
class GraphArrayIteratorBase;
template<class ArrayType>
using GraphArrayIterator = GraphArrayIteratorBase<ArrayType, false>;
template<class ArrayType>
using GraphArrayConstIterator = GraphArrayIteratorBase<ArrayType, true>;
 
template<class ArrayType, bool isConst>
class GraphArrayIteratorBase {
    friend class GraphArrayIteratorBase<ArrayType, true>;
 
public:
    using key_type = typename ArrayType::key_type;
    using value_type = typename std::conditional<isConst, const typename ArrayType::value_type,
            typename ArrayType::value_type>::type;
    using array_pointer_type = typename std::conditional<isConst, const ArrayType*, ArrayType*>::type;
 
    GraphArrayIteratorBase() : m_key(nullptr), m_array(nullptr) { }
 
    GraphArrayIteratorBase(key_type key, array_pointer_type a) : m_key(key), m_array(a) { }
 
    template<bool isArgConst, typename std::enable_if<isConst || !isArgConst, int>::type = 0>
    GraphArrayIteratorBase(const GraphArrayIteratorBase<ArrayType, isArgConst>& iter)
        : GraphArrayIteratorBase(iter.m_key, iter.m_array) { }
 
    // gcc9 complains since it cannot match the templated constructor above (-Werror=deprecated-copy).
    GraphArrayIteratorBase(const GraphArrayIteratorBase<ArrayType, isConst>& iter)
        : GraphArrayIteratorBase(iter.m_key, iter.m_array) { }
 
    GraphArrayIteratorBase<ArrayType, isConst>& operator=(
            const GraphArrayIteratorBase<ArrayType, isConst>& iter) {
        m_key = iter.m_key;
        m_array = iter.m_array;
        return *this;
    }
 
    key_type key() const { return m_key; }
 
    value_type& value() const { return (*m_array)[m_key]; }
 
    value_type& operator*() const { return (*m_array)[m_key]; }
 
    bool operator==(const GraphArrayIteratorBase<ArrayType, isConst>& iter) const {
        return m_key == iter.m_key && m_array == iter.m_array;
    }
 
    bool operator!=(const GraphArrayIteratorBase<ArrayType, isConst>& iter) const {
        return !operator==(iter);
    }
 
    GraphArrayIteratorBase<ArrayType, isConst>& operator++() {
        OGDF_ASSERT(m_key != nullptr);
        m_key = ArrayType::findSuccKey(m_key);
        return *this;
    }
 
    GraphArrayIteratorBase<ArrayType, isConst> operator++(int) {
        GraphArrayIteratorBase<ArrayType, isConst> iter = *this;
        m_key = ArrayType::findSuccKey(m_key);
        return iter;
    }
 
    GraphArrayIteratorBase<ArrayType, isConst>& operator--() {
        OGDF_ASSERT(m_key != nullptr);
        m_key = ArrayType::findPredKey(m_key);
        return *this;
    }
 
    GraphArrayIteratorBase<ArrayType, isConst> operator--(int) {
        GraphArrayIteratorBase<ArrayType, isConst> iter = *this;
        m_key = ArrayType::findPredKey(m_key);
        return iter;
    }
 
private:
    key_type m_key; 
    array_pointer_type m_array; 
};
 
}
}