"Fossies" - the Fresh Open Source Software Archive

Member "dune-typetree-2.8.0/dune/typetree/treepath.hh" (31 Aug 2021, 14303 Bytes) of package /linux/misc/dune/dune-typetree-2.8.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "treepath.hh" see the Fossies "Dox" file reference documentation.

    1 // -*- tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
    2 // vi: set et ts=8 sw=2 sts=2:
    3 
    4 #ifndef DUNE_TYPETREE_TREEPATH_HH
    5 #define DUNE_TYPETREE_TREEPATH_HH
    6 
    7 #include <cstddef>
    8 #include <iostream>
    9 
   10 #include <dune/common/documentation.hh>
   11 #include <dune/common/typetraits.hh>
   12 #include <dune/common/indices.hh>
   13 #include <dune/common/hybridutilities.hh>
   14 
   15 #include <dune/typetree/fixedcapacitystack.hh>
   16 #include <dune/typetree/utility.hh>
   17 
   18 
   19 namespace Dune {
   20   namespace TypeTree {
   21 
   22     template<typename... T>
   23     class HybridTreePath;
   24 
   25     //! \addtogroup TreePath
   26     //! \ingroup TypeTree
   27     //! \{
   28 
   29     namespace TreePathType {
   30       enum Type { fullyStatic, dynamic };
   31     }
   32 
   33     template<typename>
   34     struct TreePathSize;
   35 
   36     template<typename,std::size_t>
   37     struct TreePathPushBack;
   38 
   39     template<typename,std::size_t>
   40     struct TreePathPushFront;
   41 
   42     template<typename>
   43     struct TreePathBack;
   44 
   45     template<typename>
   46     struct TreePathFront;
   47 
   48     template<typename, std::size_t...>
   49     struct TreePathPopBack;
   50 
   51     template<typename>
   52     struct TreePathPopFront;
   53 
   54     template<typename, typename>
   55     struct TreePathConcat;
   56 
   57     template<std::size_t... i>
   58     void print_tree_path(std::ostream& os)
   59     {}
   60 
   61     template<std::size_t k, std::size_t... i>
   62     void print_tree_path(std::ostream& os)
   63     {
   64       os << k << " ";
   65       print_tree_path<i...>(os);
   66     }
   67 
   68     //! A hybrid version of TreePath that supports both compile time and run time indices.
   69     /**
   70      * A `HybridTreePath` supports storing a combination of run time and compile time indices.
   71      * This makes it possible to store the tree path to a tree node inside the tree node itself,
   72      * even if the path contains one or more `PowerNode`s, where each child must have exactly the
   73      * same type. At the same time, as much information as possible is kept accessible at compile
   74      * time, allowing for more efficient algorithms.
   75      *
   76      */
   77     template<typename... T>
   78     class HybridTreePath
   79     {
   80 
   81     public:
   82 
   83       //! An `index_sequence` for the entries in this `HybridTreePath`.
   84       using index_sequence = std::index_sequence_for<T...>;
   85 
   86       //! Default constructor
   87       constexpr HybridTreePath()
   88       {}
   89 
   90       constexpr HybridTreePath(const HybridTreePath& tp) = default;
   91       constexpr HybridTreePath(HybridTreePath&& tp) = default;
   92 
   93       //! Constructor from a `std::tuple`
   94       explicit constexpr HybridTreePath(std::tuple<T...> t)
   95         : _data(t)
   96       {}
   97 
   98       //! Constructor from arguments
   99       template<typename... U, typename std::enable_if<(sizeof...(T) > 0 && sizeof...(U) == sizeof...(T)),bool>::type = true>
  100       explicit constexpr HybridTreePath(U... t)
  101         : _data(t...)
  102       {}
  103 
  104       //! Returns an index_sequence for enumerating the components of this HybridTreePath.
  105       constexpr static index_sequence enumerate()
  106       {
  107         return {};
  108       }
  109 
  110       //! Get the size (length) of this path.
  111       constexpr static std::size_t size()
  112       {
  113         return sizeof...(T);
  114       }
  115 
  116       //! Get the index value at position pos.
  117       template<std::size_t i>
  118       constexpr auto operator[](Dune::index_constant<i> pos) const
  119       {
  120         return std::get<i>(_data);
  121       }
  122 
  123       //! Get the index value at position pos.
  124       constexpr std::size_t operator[](std::size_t pos) const
  125       {
  126         std::size_t entry = 0;
  127         Dune::Hybrid::forEach(enumerate(), [&] (auto i) {
  128             if (i==pos)
  129               entry = this->element(i);
  130         });
  131         return entry;
  132       }
  133 
  134       //! Get the last index value.
  135       template<std::size_t i>
  136       constexpr auto element(Dune::index_constant<i> pos = {}) const
  137       {
  138         return std::get<i>(_data);
  139       }
  140 
  141       //! Get the index value at position pos.
  142       constexpr std::size_t element(std::size_t pos) const
  143       {
  144         std::size_t entry = 0;
  145         Dune::Hybrid::forEach(enumerate(), [&] (auto i) {
  146             if (i==pos)
  147               entry = this->element(i);
  148         });
  149         return entry;
  150       }
  151 
  152       //! Get the last index value.
  153       auto back() const
  154       {
  155         return std::get<sizeof...(T)-1>(_data);
  156       }
  157 
  158 #ifndef DOXYGEN
  159 
  160       // I can't be bothered to make all the external accessors friends of HybridTreePath,
  161       // so we'll only hide the data tuple from the user in Doxygen.
  162 
  163       using Data = std::tuple<T...>;
  164       Data _data;
  165 
  166 #endif // DOXYGEN
  167 
  168     };
  169 
  170 
  171     //! Constructs a new `HybridTreePath` from the given indices.
  172     /**
  173      * This function returns a new `HybridTreePath` with the given index values. It exists
  174      * mainly to avoid having to manually specify the exact type of the new object.
  175      */
  176     template<typename... T>
  177     constexpr HybridTreePath<T...> hybridTreePath(const T&... t)
  178     {
  179       return HybridTreePath<T...>(t...);
  180     }
  181 
  182     //! Constructs a new `HybridTreePath` from the given indices.
  183     /**
  184      * This function returns a new `HybridTreePath` with the given index values. It exists
  185      * mainly to avoid having to manually specify the exact type of the new object.
  186      */
  187     template<typename... T>
  188     constexpr HybridTreePath<T...> treePath(const T&... t)
  189     {
  190       return HybridTreePath<T...>(t...);
  191     }
  192 
  193 
  194     //! Returns the size (number of components) of the given `HybridTreePath`.
  195     template<typename... T>
  196     constexpr std::size_t treePathSize(const HybridTreePath<T...>&)
  197     {
  198       return sizeof...(T);
  199     }
  200 
  201     //! Returns a copy of the i-th element of the `HybridTreePath`.
  202     /**
  203      * As `HybridTreePath` instances should not be mutated after their creation, this function
  204      * returns a copy of the value. As values are either `std::integral_constant` or `std::size_t`, that's
  205      * just as cheap as returning a reference.
  206      *
  207      * The index for the entry can be passed either as a template parameter or as an `index_constant`:
  208      *
  209      * \code{.cc}
  210      * auto tp = hybridTreePath(1,2,3,4);
  211      * using namespace Dune::TypeTree::Indices;
  212      * // the following two lines are equivalent
  213      * std::cout << treePathEntry<2>(tp) << std::endl;
  214      * std::cout << treePathEntry(tp,_2) << std::endl;
  215      * \endcode
  216      *
  217      */
  218     template<std::size_t i, typename... T>
  219     constexpr auto treePathEntry(const HybridTreePath<T...>& tp, index_constant<i> = {})
  220       -> typename std::decay<decltype(std::get<i>(tp._data))>::type
  221     {
  222       return std::get<i>(tp._data);
  223     }
  224 
  225     //! Returns the index value of the i-th element of the `HybridTreePath`.
  226     /**
  227      * This function always returns the actual index value, irrespective of whether the
  228      * entry is a compile time index or a run time index.
  229      *
  230      * The index for the entry can be passed either as a template parameter or as an `index_constant`:
  231      *
  232      * \code{.cc}
  233      * auto tp = hybridTreePath(1,2,3,4);
  234      * using namespace Dune::TypeTree::Indices;
  235      * // the following two lines are equivalent
  236      * std::cout << treePathIndex<2>(tp) << std::endl;
  237      * std::cout << treePathIndex(tp,_2) << std::endl;
  238      * \endcode
  239      *
  240      */
  241     template<std::size_t i,typename... T>
  242     constexpr std::size_t treePathIndex(const HybridTreePath<T...>& tp, index_constant<i> = {})
  243     {
  244       return std::get<i>(tp._data);
  245     }
  246 
  247     //! Returns a copy of the last element of the `HybridTreePath`.
  248     /**
  249      * As `HybridTreePath` instances should not be mutated after their creation, this function
  250      * returns a copy of the value. As values are either `std::integral_constant` or `std::size_t`, that's
  251      * just as cheap as returning a reference.
  252      */
  253     template<typename... T, typename std::enable_if<(sizeof...(T) > 0),bool>::type = true>
  254     constexpr auto back(const HybridTreePath<T...>& tp)
  255       -> decltype(treePathEntry<sizeof...(T)-1>(tp))
  256     {
  257       return treePathEntry<sizeof...(T)-1>(tp);
  258     }
  259 
  260     //! Returns a copy of the first element of the `HybridTreePath`.
  261     /**
  262      * As `HybridTreePath` instances should not be mutated after their creation, this function
  263      * returns a copy of the value. As values are either `std::integral_constant` or `std::size_t`, that's
  264      * just as cheap as returning a reference.
  265      */
  266     template<typename... T>
  267     constexpr auto front(const HybridTreePath<T...>& tp)
  268       -> decltype(treePathEntry<0>(tp))
  269     {
  270       return treePathEntry<0>(tp);
  271     }
  272 
  273     //! Appends a run time index to a `HybridTreePath`.
  274     /**
  275      * This function returns a new `HybridTreePath` with the run time index `i` appended.
  276      */
  277     template<typename... T>
  278     constexpr HybridTreePath<T...,std::size_t> push_back(const HybridTreePath<T...>& tp, std::size_t i)
  279     {
  280       return HybridTreePath<T...,std::size_t>(std::tuple_cat(tp._data,std::make_tuple(i)));
  281     }
  282 
  283     //! Appends a compile time index to a `HybridTreePath`.
  284     /**
  285      * This function returns a new `HybridTreePath` with the compile time index `i` appended.
  286      *
  287      * The value for the new entry can be passed either as a template parameter or as an `index_constant`:
  288      *
  289      * \code{.cc}
  290      * auto tp = hybridTreePath(1,2,3,4);
  291      * using namespace Dune::TypeTree::Indices;
  292      * // the following two lines are equivalent
  293      * auto tp_a = push_back<1>(tp);
  294      * auto tp_b = push_back(tp,_1);
  295      * \endcode
  296      *
  297      */
  298     template<std::size_t i, typename... T>
  299     constexpr HybridTreePath<T...,index_constant<i>> push_back(const HybridTreePath<T...>& tp, index_constant<i> i_ = {})
  300     {
  301       return HybridTreePath<T...,index_constant<i> >(std::tuple_cat(tp._data,std::make_tuple(i_)));
  302     }
  303 
  304     //! Prepends a run time index to a `HybridTreePath`.
  305     /**
  306      * This function returns a new `HybridTreePath` with the run time index `i` prepended.
  307      */
  308     template<typename... T>
  309     constexpr HybridTreePath<std::size_t,T...> push_front(const HybridTreePath<T...>& tp, std::size_t element)
  310     {
  311       return HybridTreePath<std::size_t,T...>(std::tuple_cat(std::make_tuple(element),tp._data));
  312     }
  313 
  314     //! Prepends a compile time index to a `HybridTreePath`.
  315     /**
  316      * This function returns a new `HybridTreePath` with the compile time index `i` prepended.
  317      *
  318      * The value for the new entry can be passed either as a template parameter or as an `index_constant`:
  319      *
  320      * \code{.cc}
  321      * auto tp = hybridTreePath(1,2,3,4);
  322      * using namespace Dune::TypeTree::Indices;
  323      * // the following two lines are equivalent
  324      * auto tp_a = push_front<1>(tp);
  325      * auto tp_b = push_front(tp,_1);
  326      * \endcode
  327      *
  328      */
  329     template<std::size_t i, typename... T>
  330     constexpr HybridTreePath<index_constant<i>,T...> push_front(const HybridTreePath<T...>& tp, index_constant<i> _i = {})
  331     {
  332       return HybridTreePath<index_constant<i>,T...>(std::tuple_cat(std::make_tuple(_i),tp._data));
  333     }
  334 
  335 
  336     template<std::size_t... i>
  337     struct TreePathSize<HybridTreePath<index_constant<i>...> >
  338       : public index_constant<sizeof...(i)>
  339     {};
  340 
  341 
  342     template<std::size_t k, std::size_t... i>
  343     struct TreePathPushBack<HybridTreePath<index_constant<i>...>,k>
  344     {
  345       typedef HybridTreePath<index_constant<i>...,index_constant<k>> type;
  346     };
  347 
  348     template<std::size_t k, std::size_t... i>
  349     struct TreePathPushFront<HybridTreePath<index_constant<i>...>,k>
  350     {
  351       typedef HybridTreePath<index_constant<k>,index_constant<i>...> type;
  352     };
  353 
  354     template<std::size_t k>
  355     struct TreePathBack<HybridTreePath<index_constant<k>>>
  356       : public index_constant<k>
  357     {};
  358 
  359     template<std::size_t j, std::size_t k, std::size_t... l>
  360     struct TreePathBack<HybridTreePath<index_constant<j>,index_constant<k>,index_constant<l>...>>
  361       : public TreePathBack<HybridTreePath<index_constant<k>,index_constant<l>...>>
  362     {};
  363 
  364     template<std::size_t k, std::size_t... i>
  365     struct TreePathFront<HybridTreePath<index_constant<k>,index_constant<i>...>>
  366       : public index_constant<k>
  367     {};
  368 
  369     template<std::size_t k, std::size_t... i>
  370     struct TreePathPopBack<HybridTreePath<index_constant<k>>,i...>
  371     {
  372       typedef HybridTreePath<index_constant<i>...> type;
  373     };
  374 
  375     template<std::size_t j,
  376              std::size_t k,
  377              std::size_t... l,
  378              std::size_t... i>
  379     struct TreePathPopBack<HybridTreePath<index_constant<j>,index_constant<k>,index_constant<l>...>,i...>
  380       : public TreePathPopBack<HybridTreePath<index_constant<k>,index_constant<l>...>,i...,j>
  381     {};
  382 
  383     template<std::size_t k, std::size_t... i>
  384     struct TreePathPopFront<HybridTreePath<index_constant<k>,index_constant<i>...> >
  385     {
  386       typedef HybridTreePath<index_constant<i>...> type;
  387     };
  388 
  389     template<std::size_t... i, std::size_t... k>
  390     struct TreePathConcat<HybridTreePath<index_constant<i>...>,HybridTreePath<index_constant<k>...> >
  391     {
  392       typedef HybridTreePath<index_constant<i>...,index_constant<k>...> type;
  393     };
  394 
  395 #ifndef DOXYGEN
  396 
  397     namespace impl {
  398 
  399       // end of recursion
  400       template<std::size_t i, typename... T>
  401       typename std::enable_if<
  402         (i == sizeof...(T))
  403         >::type
  404       print_hybrid_tree_path(std::ostream& os, const HybridTreePath<T...>& tp, index_constant<i> _i)
  405       {}
  406 
  407       // print current entry and recurse
  408       template<std::size_t i, typename... T>
  409       typename std::enable_if<
  410         (i < sizeof...(T))
  411         >::type
  412       print_hybrid_tree_path(std::ostream& os, const HybridTreePath<T...>& tp, index_constant<i> _i)
  413       {
  414         os << treePathIndex(tp,_i) << " ";
  415         print_hybrid_tree_path(os,tp,index_constant<i+1>{});
  416       }
  417 
  418     } // namespace impl
  419 
  420 #endif // DOXYGEN
  421 
  422     //! Dumps a `HybridTreePath` to a stream.
  423     template<typename... T>
  424     std::ostream& operator<<(std::ostream& os, const HybridTreePath<T...>& tp)
  425     {
  426       os << "HybridTreePath< ";
  427       impl::print_hybrid_tree_path(os, tp, index_constant<0>{});
  428       os << ">";
  429       return os;
  430     }
  431 
  432     template<std::size_t... i>
  433     using TreePath [[deprecated("use StaticTreePath, this type will be removed after DUNE 2.7")]] = HybridTreePath<Dune::index_constant<i>...>;
  434 
  435     template<std::size_t... i>
  436     using StaticTreePath = HybridTreePath<Dune::index_constant<i>...>;
  437 
  438     //! \} group TypeTree
  439 
  440   } // namespace TypeTree
  441 } //namespace Dune
  442 
  443 #endif // DUNE_TYPETREE_TREEPATH_HH