general.hpp File Reference

Plans for the module with tree datastructures. More...

Go to the source code of this file.


namespace  OKlib::Trees

Module for trees (algorithms and data structures; all kinds of trees)

namespace  OKlib

All components of the OKlibrary.

Detailed Description

Plans for the module with tree datastructures.

Update namespaces.
Concept design "Rooted trees with ordered children"
  • Compare with ComputerAlgebra/Trees/Lisp/Basics.mac.
  • Tree T:
    1. fully constructible, with equality
    2. vertex_type<Tree>::type; fully constructible with equality and with singular value
    3. root(T) of type vertex_type
    4. vertex_type v;
    5. Tree(T, v) copy constructor for the subtree of T at v
    6. children(T, v) yields a range, whose value-type is vertex_type
    7. parent(T, v) of type vertex_type (singular iff v == root(T))
    8. property_map(m, T, v)
    9. swap(T1, T2)
    10. swap(T, v, T2, v2) swaps the subtree of T at v with the subtree of T2 at v2 (swaps do not invalidate vertex descriptors nor iterators, but their meaning change).
  • in_order(T, v), pre_order(T, v), post_order(T, v) yield ranges to traverse the subtree of T at v.
  • Refinement "mutable":
    1. new_child(T, iterator) returns vertex_type with parent v, inserts at iterator (if iterator is begin, then this is front-insertion, if iterator is end, then this is back-insertion)
    2. remove_child(T, iterator) (again vertex descriptors and iterators are not invalidated (if possible), by both operations).
In a module GraphTrees rooted trees as Boost-graphs with one distinguished vertex establishing, while Parent-graph-trees additionally are equipped for every vertex with a property yielding the parent vertex (which in case of the root is the root itself).

Definition in file general.hpp.