template class detangled::accessor

Overview

accessors are used for creating pointers to nodes in a raw_tree. More…

#include <accessor.h>

template <class Container>
class accessor {
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;

    // fields

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

    // construction

    accessor(node_type& node);
    accessor();
    accessor(accessor&&);
    accessor(const accessor<container_type>& pos);
    accessor(const accessor<const container_type>& post);

    // 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;
};

Detailed Documentation

accessors are used for creating pointers to nodes in a raw_tree.

Overview:

Accessor objects are used for referencing a node in a tree and for navigating through the various nodes in the tree. It is a single object that can be used to visit all the nodes in the tree.

Clients should see these classes as more fundamental than detangled::iterator s are because objects of these classes don’t know next and can navigate freely through the container. Freely doesn’t imply cheaply; complexity costs are indicated on the various methods.

End accessor:

Other than nodes in a tree, accessor objects may be put in a state we call end (because typically this state is useful when done as an iterator). In this state the accessor refers to an invalid object. This accessor may be seen like a virtual node which is the parent of the root node of this tree with the difference that it is impossible to navigate down after reaching there.

Properties:

Validity in the face of Mutating methods:

Accessor objects are generally stable. They remain valid if the tree that the node they point to is modified in any way including detaching enveloping subtrees. So long as the node pointed to is not deleted (detach with dropped reference or replace) any accessors pointing to it are valid.

Their behaviour may be seen analogous to that of std::list::iterator s which remain valid across inward and outward splice operations done on the lists.

Operations on end accessors:

Once in end state doing any operations on the accessor or dereferenced tree nodes is undefined unless specified otherwise as being end_safe.

Swap operations:

Accessors would lose some semantic relevance across swap operations. In swaps, the memory allocation of two nodes remains the same and the contents are switched. This would cause the first memory location to become the tree rooted at the second location. Accessors are tied to memory locations and hence will not port across swaps.

Parameters:

Container

is the tree container type that this accessor works over. Methods like parent(), child<side::left>() etc. are expected to be defined over this type.

Methods

bool
operator==(const accessor& other) const

Equality and position queries. These are end_safe operations.

uint32_t
depth() const

Complexity: O(lg(n))

Returns:

the ‘depth’ of the node. Invalid result is returned when we are at end.