WIP: A new implementation of type-tree
Summary
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
.
Proposal
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 (closed) 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.
Details
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:
- type uniformity (
isTypeUniform
) - value uniformity, i.e. whether all childs are identical (
isUniform
) - 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
andDune::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.