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