template class detangled::iterator

Overview

Objects of this class allow sequentially accessing raw_tree elements. More…

#include <iterator.h>

template <class C, traversal_order order, side wing>
class iterator:
    public detangled::virtual_accessor,
    public std::iterator< std::bidirectional_iterator_tag, C::value_type > {
public:
    // typedefs

    typedef virtual_accessor<C> base_type;
    typedef typename base_type::container_type container_type;
    typedef typename base_type::node_type node_type;
    typedef typename base_type::value_type_t value_type_t;

    // construction

    iterator(node_type& node);

    // methods

    iterator&
    operator++();

    iterator
    operator++(int);

    iterator&
    operator--();

    iterator
    operator--(int);
};

Inherited Members

public:
    // typedefs

    typedef typename ::std::remove_cv<Container>::type container_type;
    typedef typename std::conditional<is_const, const container_type, container_type>::type node_type;
    typedef typename std::conditional<is_const, const typename container_type::value_type, typename container_type::value_type>::type value_type_t;
    typedef accessor<ContainerType> base_type;
    typedef typename base_type::container_type container_type;
    typedef typename base_type::node_type node_type;
    typedef typename base_type::value_type_t value_type_t;

    // fields

    static constexpr bool is_const = ::std::is_const<Container>::value;

    // methods

    accessor&
    operator=(const accessor&);

    accessor&
    operator=(accessor&&);

    value_type_t&
    operator*() const;

    node_type&
    node() const;

    node_type*
    operator->() const;

    operator bool() const;

    bool
    operator==(const accessor& other) const;

    bool
    operator!=(const accessor& other) const;

    bool
    is_root() const;

    uint32_t
    depth() const;

    void
    up();

    void
    root();

    template <side wing>
    bool
    down();

    bool
    down(side wing);

    template <side wing>
    bool
    ancestor();

    bool
    ancestor(side wing);

    accessor
    common_ancestor(const accessor& other) const;

    accessor<container_type>
    non_const() const;

    virtual_accessor&
    operator=(const virtual_accessor&);

    virtual_accessor&
    operator=(virtual_accessor&&);

    operator bool() const;

    bool
    operator==(const virtual_accessor& other) const;

    bool
    operator!=(const virtual_accessor& other) const;

    bool
    is_root() const;

    uint32_t
    depth() const;

    void
    up();

    void
    root();

    template <side wing>
    bool
    down();

    bool
    down(side wing);

Detailed Documentation

Objects of this class allow sequentially accessing raw_tree elements.

The constructed iterators are *BidirectionalIterator*s and can be decremented from end state as well.

Typical usage:

raw_tree<uint32_t> tree_elements(...);
...
for (auto it = tree_elements.begin<traversal_order::pre, side::left>();
     it != tree_elements.prelend(); ++it) {
    ...
}

The above allows accessing elements of the tree in pre-order (left first). Note that prelend is a mnemonic which constructs raw_tree::end<traversal_order::pre, side::left>(). See RAW_TREE_MAKE_ALIAS for details.

Sequence definition:

Unlike standard containers like std::vector the elements in a tree can be accessed in a number of sequences. The traditionally defined ways are traversal_order::pre, traversal_order::in and traversal_order::post. This iterator template class allows instantiating the correct object factory representing one of these.

This is a slight generalization over the iterator / reverse_iterator type pair in standard containers. The generalization would fit better if we called the standard iterators, detangled::iterator<side::left> and detangled::iterator<side::right> instead.

Parameters:

C	is the tree container type that we are trying to make the iterator for. We specify this to DRY the code that we would have to write for const-iterator,
order	is the traversal_order that we wish to follow.
wing	is the side of child / subtree nodes that we prefer during traversal.