Add IndexTree datastructures to represent hierarchic structure of the basis

Open Simon Praetorius requested to merge feature/blocking2 into master


This MR implements an idea discussed in a dune-functions developer meeting: Represent the hierarchic structure accessible by multi-indices in an IndexTree. This tree contains information about uniform and non-uniform sub-structures and about the sizes of this structure. It is implemented for PowerPreBasis and CompositePreBasis and all leaf prebases with a dimension get a default flat IndexTree.


There are various tree nodes implemented representing all situations I could think of:

  • leaf nodes (representing flat containers), with static and dynamic size (StaticFlatIndexTree, DynamicFlatIndexTree)
  • uniform trees with all sub-trees of the same type and shape, with static and dynamic degree ([Static]UniformIndexTree)
  • non-uniform tree with all sub-trees of either different types or the same types with different shape again with static and dynamic size (TypeUniformIndexTree, StaticTypeUniformIndexTree, NonUniformIndexTree (not implemented), StaticNonUniformIndexTree)

Inner index-tree nodes follow the interface

struct IndexTree
  static constexpr bool isUniform = [true|false];     // Whether all children are identical
  static constexpr bool isTypeUniform = [true|false]; // Whether all children have the same type

  template<class Index>
  SubTree operator[](Index i) const;  // return the i-th sub-tree

  [static constexpr] std::size_t size() [const];  // return the number of sub-nodes


  • Decide whether to name the structure SizeTree or IndexTree
  • Add changelog entry
  • Squash commits
  • requires !389 (merged) to be merged and then a rebase to include these commits.
  • Update concepts definition
Edited by Simon Praetorius

Merge request reports