Line data    Source code

       1            0 : // Distributed under the MIT License.
       2              : // See LICENSE.txt for details.
       3              : 
       4              : #pragma once
       5              : 
       6              : #include <array>
       7              : #include <cstddef>
       8              : #include <iterator>
       9              : #include <map>
      10              : #include <memory>
      11              : #include <vector>
      12              : 
      13              : #include "DataStructures/Tensor/TypeAliases.hpp"
      14              : 
      15              : /// \cond
      16              : template <size_t VolumeDim>
      17              : class ElementId;
      18              : /// \endcond
      19              : 
      20              : namespace domain {
      21              : /// \cond
      22              : template <size_t Dim>
      23              : class ElementSearchTree;
      24              : /// \endcond
      25              : 
      26              : template <size_t Dim>
      27            0 : class ElementSearchTreeIterator {
      28              :  public:
      29            0 :   using iterator_category = std::forward_iterator_tag;
      30            0 :   using value_type = ElementId<Dim>;
      31            0 :   using difference_type = std::ptrdiff_t;
      32            0 :   using pointer = const ElementId<Dim>*;
      33            0 :   using reference = const ElementId<Dim>&;
      34              : 
      35            0 :   ElementSearchTreeIterator();
      36            0 :   ElementSearchTreeIterator(ElementSearchTreeIterator&&);
      37            0 :   ElementSearchTreeIterator(const ElementSearchTreeIterator&);
      38            0 :   ElementSearchTreeIterator& operator=(ElementSearchTreeIterator&&);
      39            0 :   ElementSearchTreeIterator& operator=(const ElementSearchTreeIterator&);
      40            0 :   ~ElementSearchTreeIterator();
      41              : 
      42            0 :   reference operator*() const;
      43            0 :   pointer operator->() const;
      44              : 
      45            0 :   ElementSearchTreeIterator& operator++();
      46            0 :   ElementSearchTreeIterator operator++(int);
      47              : 
      48              :  private:
      49              :   friend class ElementSearchTree<Dim>;
      50              : 
      51              :   template <typename T>
      52            0 :   static ElementSearchTreeIterator from_impl(T impl);
      53              : 
      54              :   template <size_t Dim2>
      55            0 :   friend bool operator==(const ElementSearchTreeIterator<Dim2>& a,
      56              :                          const ElementSearchTreeIterator<Dim2>& b);
      57              : 
      58              :   // Use an array and manual construction rather than a simpler pimpl
      59              :   // since iterators are constructed a lot.
      60            0 :   std::array<char, 8> data_;
      61              : };
      62              : 
      63              : /*!
      64              :  * \brief Search tree for efficiently looking up elements by their bounding
      65              :  * boxes in block-logical coordinates.
      66              :  *
      67              :  * The search tree is constructed from a list of `ElementId`s, which define
      68              :  * bounding boxes in block-logical coordinates. All `ElementId`s must be in the
      69              :  * same block. Then, the search tree can be used to efficiently search for the
      70              :  * element that contains a given block-logical coordinate (see e.g.
      71              :  * `element_logical_coordinates`).
      72              :  *
      73              :  * Example usage:
      74              :  * \snippet Test_ElementSearchTree.cpp element_search_tree_example
      75              :  *
      76              :  * Use `domain::index_element_ids()` to create one search tree for each block in
      77              :  * the domain given the full list of `ElementId`s.
      78              :  *
      79              :  * \details The search tree is a `boost::geometry::rtree` with a choice of
      80              :  * quadratic splitting algorithm and a maximum of 16 elements per node. These
      81              :  * choices work well, but haven't been extensively tuned.
      82              :  */
      83              : template <size_t Dim>
      84            1 : class ElementSearchTree {
      85              :  public:
      86            0 :   ElementSearchTree();
      87            0 :   ElementSearchTree(ElementSearchTree&&);
      88            0 :   ElementSearchTree& operator=(ElementSearchTree&&);
      89            0 :   ElementSearchTree(const ElementSearchTree&) = delete;
      90            0 :   ElementSearchTree& operator=(const ElementSearchTree&) = delete;
      91            0 :   ~ElementSearchTree();
      92              : 
      93              :   /// Construct a search tree containing the ids in `[begin, end)`.
      94              :   template <typename Iter>
      95            1 :   ElementSearchTree(Iter begin, const Iter end) : ElementSearchTree() {
      96              :     insert(begin, end);
      97              :   }
      98              : 
      99            0 :   size_t size() const;
     100            0 :   bool empty() const;
     101            0 :   void clear();
     102              : 
     103            0 :   void insert(const ElementId<Dim>& id);
     104              : 
     105              :   /// Insert the ids in `[begin, end)`.
     106              :   template <typename Iter>
     107            1 :   void insert(Iter begin, const Iter end) {
     108              :     while (begin != end) {
     109              :       insert(*begin);
     110              :       ++begin;
     111              :     }
     112              :   }
     113              : 
     114            0 :   ElementSearchTreeIterator<Dim> begin_covers(
     115              :       const tnsr::I<double, Dim, Frame::BlockLogical>& coords) const;
     116              : 
     117            0 :   ElementSearchTreeIterator<Dim> end_covers() const;
     118              : 
     119              :  private:
     120              :   // Use a pimpl to keep all the boost::geometry stuff in a cpp file,
     121              :   // because the boost headers are quite expensive to include.
     122              :   struct Impl;
     123            0 :   std::unique_ptr<Impl> impl_;
     124              : };
     125              : 
     126              : /*!
     127              :  * \brief Sorts element IDs into one `ElementSearchTree` per block for efficient
     128              :  * searching.
     129              :  *
     130              :  * Returns a map of search trees indexed by block ID. Each search tree contains
     131              :  * all the `ElementId`s for that block.
     132              :  *
     133              :  * \see ElementSearchTree
     134              :  */
     135              : template <size_t Dim>
     136            1 : std::map<size_t, ElementSearchTree<Dim>> index_element_ids(
     137              :     const std::vector<ElementId<Dim>>& element_ids);
     138              : }  // namespace domain