Skip to content

WIP: A new implementation of type-tree

Simon Praetorius requested to merge feature/new-typetree into master


This is an experiment to replace the old structures of a typetree with a new implementation more similar to the TreeContainer in dune-functions, i.e., a direct composition of std::array, std::tuple and std::vector.


This MR proposes to unify the multiple type-tree implementations we are currently using or that are proposed. In dune-functions we currently have at least 2 type-trees: The basis-tree and the tree-container. Both with different purpose and both with different interface. Both need hierarchic traversal/access and size/resize utilities. In dune-functions!350 a third tree is proposed, again with the same requirements, but encoding something different. Actually, there are more trees hidden: The basis tree is basically a combination of two trees, a localbasis tree and an index tree.

The proposed TypeTree a data-structures are flexible enough to represent all these trees, with a simple and efficient storage, access, traversal and transformation. It is possible to transform a basis-tree into a tree-container, or a basis-tree into a size-tree... with a not too complicated utility. A generic tree-transform function is provided and the corresponding test from dune-typetree are passing.


The type-tree is based on a composition of std::array for static-size uniform-type nodes, std::tuple for non-uniform-type nodes, std::vector for dynamic-size uniform-type nodes, and two special nodes in case all the children are exactly identical.

The tree nodes encode the three properties:

  1. type uniformity (isTypeUniform)
  2. value uniformity, i.e. whether all childs are identical (isUniform)
  3. whether this size is statically known (hasStaticSize)

The names of the nodes try to encode these properties, but are up to discussion, see below.

The tree nodes are derived from the corresponding std containers, thus provide typically an operator[](index) access and a size() method. This is not the public interface, but the corresponding methods child(index) and degree(). But, the base-class methods are not hidden, meaning they can be used e.g. in a tree-container interface.

Differences to old implementation

  • TypeTree is a direct composition of std::array, std::vector and Dune::TupleVector + some lightweight nodes for uniform childs
  • Nodes are stored by value and not as shared_ptr. (this might be a discussion point)
  • A TreeContainer is just a Tree with its LeafNode replaced by a corresponding value type.
  • Traversal and child access as before with no change
  • Tree container vector-backend can use standard tree traversal and access. Resize method can be simplified a lot.
Edited by Simon Praetorius

Merge request reports