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, bool isConst>
class GraphIteratorBase;
template<class GraphObjectPtr>
using GraphIterator = GraphIteratorBase<GraphObjectPtr, false, false>;
template<class GraphObjectPtr>
using GraphReverseIterator = GraphIteratorBase<GraphObjectPtr, true, false>;
 
template<class GraphObjectPtr, bool isReverse, bool isConst>
class GraphIteratorBase {
    friend class GraphIteratorBase<GraphObjectPtr, !isReverse, isConst>;
    using T = GraphIteratorBase<GraphObjectPtr, isReverse, isConst>;
 
    GraphObjectPtr m_ptr;
 
public:
    using difference_type = std::ptrdiff_t;
    using value_type = typename std::conditional<isConst, const GraphObjectPtr, GraphObjectPtr>::type;
    using iterator_category = std::bidirectional_iterator_tag;
    using pointer = value_type*;
    using reference = value_type&;
 
    GraphIteratorBase() : m_ptr(nullptr) { }
 
    GraphIteratorBase(GraphObjectPtr ptr) : m_ptr(ptr) { }
 
    template<bool isArgReverse>
    GraphIteratorBase(GraphIteratorBase<GraphObjectPtr, isArgReverse, isConst>& it)
        : m_ptr(it.m_ptr) { }
 
    bool operator==(const T& other) const { return m_ptr == other.m_ptr; }
 
    bool operator!=(const T& other) const { return m_ptr != other.m_ptr; }
 
    const GraphObjectPtr& operator*() const { return m_ptr; }
 
    T& operator++() {
        OGDF_ASSERT(m_ptr != nullptr);
        m_ptr = isReverse ? m_ptr->pred() : m_ptr->succ();
        return *this;
    }
 
    T operator++(int) {
        OGDF_ASSERT(m_ptr != nullptr);
        GraphObjectPtr ptr = m_ptr;
        m_ptr = isReverse ? m_ptr->pred() : m_ptr->succ();
        return ptr;
    }
 
    T& operator--() {
        OGDF_ASSERT(m_ptr != nullptr);
        m_ptr = isReverse ? m_ptr->succ() : m_ptr->pred();
        return *this;
    }
 
    T 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; 
};
 
template<typename It>
class SimpleRange {
    It m_begin;
    It m_end;
 
public:
    SimpleRange(It&& begin, It&& end) : m_begin(std::move(begin)), m_end(std::move(end)) { }
 
    SimpleRange(const It& begin, const It& end) : m_begin(begin), m_end(end) { }
 
    SimpleRange() = default;
 
    const It& begin() const { return m_begin; }
 
    const It& end() const { return m_end; }
 
    It& begin() { return m_begin; }
 
    It& end() { return m_end; }
};
 
}
}