tria.h

Go to the documentation of this file.

// -----------------------------------------------------------------------------
//
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception OR LGPL-2.1-or-later
// Copyright (C) 1998 - 2026 by the deal.II authors
//
// This file is part of the deal.II library.
//
// Detailed license information governing the source code and contributions
// can be found in LICENSE.md and CONTRIBUTING.md at the top level directory.
//
// -----------------------------------------------------------------------------
 
#ifndef dealii_tria_h
#define dealii_tria_h
 
 
#include <deal.II/base/config.h>
 
#include <deal.II/base/enable_observer_pointer.h>
#include <deal.II/base/geometry_info.h>
#include <deal.II/base/iterator_range.h>
#include <deal.II/base/observer_pointer.h>
#include <deal.II/base/partitioner.h>
#include <deal.II/base/point.h>
#include <deal.II/base/table.h>
 
#include <deal.II/grid/cell_id.h>
#include <deal.II/grid/cell_status.h>
#include <deal.II/grid/tria_accessor.h>
#include <deal.II/grid/tria_iterator_selector.h>
#include <deal.II/grid/tria_levels.h>
 
#include <boost/range/iterator_range_core.hpp>
#include <boost/serialization/map.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/serialization/unique_ptr.hpp>
#include <boost/serialization/vector.hpp>
#include <boost/signals2.hpp>
 
#include <bitset>
#include <functional>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <set>
#include <vector>
 
 
DEAL_II_NAMESPACE_OPEN
 
#ifdef signals
#  error \
    "The name 'signals' is already defined. You are most likely using the QT library \
and using the 'signals' keyword. You can either #include the Qt headers (or any conflicting headers) \
*after* the deal.II headers or you can define the 'QT_NO_KEYWORDS' macro and use the 'Q_SIGNALS' macro."
#endif
 
// Forward declarations
#ifndef DOXYGEN
// We need to forward-declare Manifold here since Manifold depends on
// Triangulation (e.g., it has functions which take face iterators as inputs).
template <int dim, int spacedim>
class Manifold;
 
template <int dim>
struct CellData;
 
struct SubCellData;
 
namespace TriangulationDescription
{
  template <int, int>
  struct Description;
}
 
namespace GridTools
{
  template <typename CellIterator>
  struct PeriodicFacePair;
}
 
template <int, int, int>
class TriaAccessor;
template <int spacedim>
class TriaAccessor<0, 1, spacedim>;
template <int, int, int>
class TriaAccessorBase;
 
namespace internal
{
  namespace TriangulationImplementation
  {
    template <int dim>
    class TriaFaces;
 
    class TriaObjects;
 
    template <int, int>
    class Policy;

    struct Implementation;
    struct ImplementationMixedMesh;
  } // namespace TriangulationImplementation
 
  namespace TriaAccessorImplementation
  {
    struct Implementation;
  }
} // namespace internal
#endif
 
 
/*------------------------------------------------------------------------*/
 
 
namespace internal
{
  namespace TriangulationImplementation
  {
    template <int dim>
    struct NumberCache
    {};

    template <>
    struct NumberCache<1>
    {
      unsigned int n_levels;

      unsigned int n_lines;

      std::vector<unsigned int> n_lines_level;

      unsigned int n_active_lines;

      std::vector<unsigned int> n_active_lines_level;

      std::shared_ptr<const Utilities::MPI::Partitioner>
        active_cell_index_partitioner;

      std::vector<std::shared_ptr<const Utilities::MPI::Partitioner>>
        level_cell_index_partitioners;

      NumberCache();

      std::size_t
      memory_consumption() const;

      template <class Archive>
      void
      serialize(Archive &ar, const unsigned int version);
    };
 

    template <>
    struct NumberCache<2> : public NumberCache<1>
    {
      unsigned int n_quads;

      std::vector<unsigned int> n_quads_level;

      unsigned int n_active_quads;

      std::vector<unsigned int> n_active_quads_level;

      NumberCache();

      std::size_t
      memory_consumption() const;

      template <class Archive>
      void
      serialize(Archive &ar, const unsigned int version);
    };
 

    template <>
    struct NumberCache<3> : public NumberCache<2>
    {
      unsigned int n_hexes;

      std::vector<unsigned int> n_hexes_level;

      unsigned int n_active_hexes;

      std::vector<unsigned int> n_active_hexes_level;

      NumberCache();

      std::size_t
      memory_consumption() const;

      template <class Archive>
      void
      serialize(Archive &ar, const unsigned int version);
    };

    template <int dim>
    struct Strides
    {
      Strides();

      Strides(const std::vector<ReferenceCell<dim>> &reference_cells);

      unsigned int max_children_per_cell;

      unsigned int max_faces_per_cell;

      unsigned int max_lines_per_cell;

      unsigned int max_vertices_per_cell;

      unsigned int max_children_per_face;

      unsigned int max_lines_per_face;
    };
  } // namespace TriangulationImplementation
 

  template <int dim, int spacedim = dim>
  DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
  struct CellAttachedData
  {
    using cell_iterator = TriaIterator<CellAccessor<dim, spacedim>>;

    unsigned int n_attached_data_sets;

    unsigned int n_attached_deserialize;
 
    using pack_callback_t =
      std::function<std::vector<char>(cell_iterator, CellStatus)>;

    std::vector<pack_callback_t> pack_callbacks_fixed;
    std::vector<pack_callback_t> pack_callbacks_variable;
  };

  template <int dim, int spacedim = dim>
  DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
  class CellAttachedDataSerializer
  {
  public:
    using cell_iterator = TriaIterator<CellAccessor<dim, spacedim>>;

    static inline constexpr unsigned int version_number = 5;

    using cell_relation_t = typename std::pair<cell_iterator, CellStatus>;
 
    CellAttachedDataSerializer();

    void
    pack_data(
      const std::vector<cell_relation_t> &cell_relations,
      const std::vector<
        typename internal::CellAttachedData<dim, spacedim>::pack_callback_t>
        &pack_callbacks_fixed,
      const std::vector<
        typename internal::CellAttachedData<dim, spacedim>::pack_callback_t>
                     &pack_callbacks_variable,
      const MPI_Comm &mpi_communicator);

    void
    unpack_cell_status(std::vector<cell_relation_t> &cell_relations) const;

    void
    unpack_data(
      const std::vector<cell_relation_t> &cell_relations,
      const unsigned int                  handle,
      const std::function<
        void(const cell_iterator &,
             const CellStatus &,
             const boost::iterator_range<std::vector<char>::const_iterator> &)>
        &unpack_callback) const;

    void
    save(const unsigned int global_first_cell,
         const unsigned int global_num_cells,
         const std::string &file_basename,
         const MPI_Comm    &mpi_communicator) const;

    void
    load(const unsigned int global_first_cell,
         const unsigned int global_num_cells,
         const unsigned int local_num_cells,
         const std::string &file_basename,
         const unsigned int n_attached_deserialize_fixed,
         const unsigned int n_attached_deserialize_variable,
         const MPI_Comm    &mpi_communicator);

    void
    clear();

    bool variable_size_data_stored;

    std::vector<unsigned int> sizes_fixed_cumulative;

    std::vector<char> src_data_fixed;
    std::vector<char> dest_data_fixed;

    std::vector<int>  src_sizes_variable;
    std::vector<int>  dest_sizes_variable;
    std::vector<char> src_data_variable;
    std::vector<char> dest_data_variable;
  };
} // namespace internal
 
 
/*------------------------------------------------------------------------*/
 

template <int dim, int spacedim = dim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
class Triangulation : public EnableObserverPointer
{
private:
  using IteratorSelector =
    ::internal::TriangulationImplementation::Iterators<dim, spacedim>;
 
public:
  enum MeshSmoothing
  {
    none = 0x0,
    limit_level_difference_at_vertices = 0x1,
    eliminate_unrefined_islands = 0x2,
    patch_level_1 = 0x4,
    coarsest_level_1 = 0x8,
    allow_anisotropic_smoothing = 0x10,
    eliminate_refined_inner_islands = 0x100,
    eliminate_refined_boundary_islands = 0x200,
    do_not_produce_unrefined_islands = 0x400,

    smoothing_on_refinement =
      (limit_level_difference_at_vertices | eliminate_unrefined_islands),
    smoothing_on_coarsening =
      (eliminate_refined_inner_islands | eliminate_refined_boundary_islands |
       do_not_produce_unrefined_islands),

    maximum_smoothing = 0xffff ^ allow_anisotropic_smoothing
  };

  using cell_iterator = TriaIterator<CellAccessor<dim, spacedim>>;

  using level_cell_iterator = cell_iterator;

  using active_cell_iterator = TriaActiveIterator<CellAccessor<dim, spacedim>>;

  using face_iterator = TriaIterator<TriaAccessor<dim - 1, dim, spacedim>>;

  using active_face_iterator =
    TriaActiveIterator<TriaAccessor<dim - 1, dim, spacedim>>;

  using vertex_iterator = TriaIterator<::TriaAccessor<0, dim, spacedim>>;

  using active_vertex_iterator =
    TriaActiveIterator<::TriaAccessor<0, dim, spacedim>>;

  using line_iterator = typename IteratorSelector::line_iterator;

  using active_line_iterator = typename IteratorSelector::active_line_iterator;

  using quad_iterator = typename IteratorSelector::quad_iterator;

  using active_quad_iterator = typename IteratorSelector::active_quad_iterator;

  using hex_iterator = typename IteratorSelector::hex_iterator;

  using active_hex_iterator = typename IteratorSelector::active_hex_iterator;

  struct DistortedCellList : public ::ExceptionBase
  {
    virtual ~DistortedCellList() noexcept override;

    std::list<typename Triangulation<dim, spacedim>::cell_iterator>
      distorted_cells;
  };

  static constexpr unsigned int dimension = dim;

  static constexpr unsigned int space_dimension = spacedim;

  Triangulation(const MeshSmoothing smooth_grid               = none,
                const bool          check_for_distorted_cells = false);

  Triangulation(const Triangulation<dim, spacedim> &) = delete;

  Triangulation(Triangulation<dim, spacedim> &&tria) noexcept;

  Triangulation &
  operator=(Triangulation<dim, spacedim> &&tria) noexcept;

  virtual ~Triangulation() override;

  virtual void
  clear();

  virtual MPI_Comm
  get_mpi_communicator() const;

  DEAL_II_DEPRECATED_WITH_COMMENT(
    "Access the MPI communicator with get_mpi_communicator() instead.")
  MPI_Comm
  get_communicator() const;

  virtual std::weak_ptr<const Utilities::MPI::Partitioner>
  global_active_cell_index_partitioner() const;

  virtual std::weak_ptr<const Utilities::MPI::Partitioner>
  global_level_cell_index_partitioner(const unsigned int level) const;

  virtual void
  set_mesh_smoothing(const MeshSmoothing mesh_smoothing);

  virtual const MeshSmoothing &
  get_mesh_smoothing() const;

  void
  set_manifold(const types::manifold_id       number,
               const Manifold<dim, spacedim> &manifold_object);

  void
  reset_manifold(const types::manifold_id manifold_number);

  void
  reset_all_manifolds();

  void
  set_all_manifold_ids(const types::manifold_id number);

  void
  set_all_manifold_ids_on_boundary(const types::manifold_id number);

  void
  set_all_manifold_ids_on_boundary(const types::boundary_id b_id,
                                   const types::manifold_id number);

  const Manifold<dim, spacedim> &
  get_manifold(const types::manifold_id number) const;

  virtual std::vector<types::boundary_id>
  get_boundary_ids() const;

  virtual std::vector<types::manifold_id>
  get_manifold_ids() const;

  virtual void
  copy_triangulation(const Triangulation<dim, spacedim> &other_tria);

  virtual void
  create_triangulation(const std::vector<Point<spacedim>> &vertices,
                       const std::vector<CellData<dim>>   &cells,
                       const SubCellData                  &subcelldata);

  virtual void
  create_triangulation(
    const TriangulationDescription::Description<dim, spacedim>
      &construction_data);

  void
  flip_all_direction_flags();

  void
  compute_line_to_adjacent_cells_map();


  void
  set_all_refine_flags();

  void
  refine_global(const unsigned int times = 1);

  void
  coarsen_global(const unsigned int times = 1);

  virtual void
  execute_coarsening_and_refinement();

  virtual bool
  prepare_coarsening_and_refinement();


  using CellStatus DEAL_II_DEPRECATED = ::CellStatus;

  static constexpr auto CELL_PERSIST DEAL_II_DEPRECATED =
    ::CellStatus::cell_will_persist;

  static constexpr auto CELL_REFINE DEAL_II_DEPRECATED =
    ::CellStatus::cell_will_be_refined;

  static constexpr auto CELL_COARSEN DEAL_II_DEPRECATED =
    ::CellStatus::children_will_be_coarsened;

  static constexpr auto CELL_INVALID DEAL_II_DEPRECATED =
    ::CellStatus::cell_invalid;
 

  template <typename T>
  struct CellWeightSum
  {
    using result_type = T;
 
    template <typename InputIterator>
    T
    operator()(InputIterator first, InputIterator last) const
    {
      return std::accumulate(first, last, T());
    }
  };

  struct Signals
  {
    boost::signals2::signal<void()> create;

    boost::signals2::signal<void()> pre_refinement;

    boost::signals2::signal<void()> post_refinement;

    boost::signals2::signal<void()> pre_partition;

    boost::signals2::signal<void()> mesh_movement;

    boost::signals2::signal<void(
      const typename Triangulation<dim, spacedim>::cell_iterator &cell)>
      pre_coarsening_on_cell;

    boost::signals2::signal<void(
      const typename Triangulation<dim, spacedim>::cell_iterator &cell)>
      post_refinement_on_cell;

    boost::signals2::signal<void(
      const Triangulation<dim, spacedim> &destination_tria)>
      copy;

    boost::signals2::signal<void()> clear;

    boost::signals2::signal<void()> any_change;

    boost::signals2::signal<unsigned int(const cell_iterator &,
                                         const ::CellStatus),
                            CellWeightSum<unsigned int>>
      weight;

    boost::signals2::signal<void()> pre_distributed_refinement;

    boost::signals2::signal<void()> post_p4est_refinement;

    boost::signals2::signal<void()> post_distributed_refinement;

    boost::signals2::signal<void()> pre_distributed_repartition;

    boost::signals2::signal<void()> post_distributed_repartition;

    boost::signals2::signal<void()> pre_distributed_save;

    boost::signals2::signal<void()> post_distributed_save;

    boost::signals2::signal<void()> pre_distributed_load;

    boost::signals2::signal<void()> post_distributed_load;
  };


  mutable Signals signals;



  void
  save_refine_flags(std::ostream &out) const;

  void
  save_refine_flags(std::vector<bool> &v) const;

  void
  load_refine_flags(std::istream &in);

  void
  load_refine_flags(const std::vector<bool> &v);

  void
  save_coarsen_flags(std::ostream &out) const;

  void
  save_coarsen_flags(std::vector<bool> &v) const;

  void
  load_coarsen_flags(std::istream &out);

  void
  load_coarsen_flags(const std::vector<bool> &v);

  bool
  get_anisotropic_refinement_flag() const;



  void
  clear_user_flags();

  void
  save_user_flags(std::ostream &out) const;

  void
  save_user_flags(std::vector<bool> &v) const;

  void
  load_user_flags(std::istream &in);

  void
  load_user_flags(const std::vector<bool> &v);

  void
  clear_user_flags_line();

  void
  save_user_flags_line(std::ostream &out) const;

  void
  save_user_flags_line(std::vector<bool> &v) const;

  void
  load_user_flags_line(std::istream &in);

  void
  load_user_flags_line(const std::vector<bool> &v);

  void
  clear_user_flags_quad();

  void
  save_user_flags_quad(std::ostream &out) const;

  void
  save_user_flags_quad(std::vector<bool> &v) const;

  void
  load_user_flags_quad(std::istream &in);

  void
  load_user_flags_quad(const std::vector<bool> &v);
 

  void
  clear_user_flags_hex();

  void
  save_user_flags_hex(std::ostream &out) const;

  void
  save_user_flags_hex(std::vector<bool> &v) const;

  void
  load_user_flags_hex(std::istream &in);

  void
  load_user_flags_hex(const std::vector<bool> &v);

  void
  clear_user_data();

  void
  save_user_indices(std::vector<unsigned int> &v) const;

  void
  load_user_indices(const std::vector<unsigned int> &v);

  void
  save_user_pointers(std::vector<void *> &v) const;

  void
  load_user_pointers(const std::vector<void *> &v);

  void
  save_user_indices_line(std::vector<unsigned int> &v) const;

  void
  load_user_indices_line(const std::vector<unsigned int> &v);

  void
  save_user_indices_quad(std::vector<unsigned int> &v) const;

  void
  load_user_indices_quad(const std::vector<unsigned int> &v);

  void
  save_user_indices_hex(std::vector<unsigned int> &v) const;

  void
  load_user_indices_hex(const std::vector<unsigned int> &v);
  void
  save_user_pointers_line(std::vector<void *> &v) const;

  void
  load_user_pointers_line(const std::vector<void *> &v);

  void
  save_user_pointers_quad(std::vector<void *> &v) const;

  void
  load_user_pointers_quad(const std::vector<void *> &v);

  void
  save_user_pointers_hex(std::vector<void *> &v) const;

  void
  load_user_pointers_hex(const std::vector<void *> &v);



  cell_iterator
  begin(const unsigned int level = 0) const;

  active_cell_iterator
  begin_active(const unsigned int level = 0) const;

  cell_iterator
  end() const;

  cell_iterator
  end(const unsigned int level) const;

  active_cell_iterator
  end_active(const unsigned int level) const;
 

  cell_iterator
  last() const;

  active_cell_iterator
  last_active() const;

  cell_iterator
  create_cell_iterator(const CellId &cell_id) const;

  bool
  contains_cell(const CellId &cell_id) const;


  IteratorRange<cell_iterator>
  cell_iterators() const;

  IteratorRange<active_cell_iterator>
  active_cell_iterators() const;

  IteratorRange<cell_iterator>
  cell_iterators_on_level(const unsigned int level) const;

  IteratorRange<active_cell_iterator>
  active_cell_iterators_on_level(const unsigned int level) const;

 
  /*-------------------------------------------------------------------------*/


  face_iterator
  begin_face() const;

  active_face_iterator
  begin_active_face() const;

  face_iterator
  end_face() const;

  IteratorRange<active_face_iterator>
  active_face_iterators() const;

 
  /*-------------------------------------------------------------------------*/


  vertex_iterator
  begin_vertex() const;

  active_vertex_iterator
  begin_active_vertex() const;

  vertex_iterator
  end_vertex() const;




  unsigned int
  n_lines() const;

  unsigned int
  n_lines(const unsigned int level) const;

  unsigned int
  n_active_lines() const;

  unsigned int
  n_active_lines(const unsigned int level) const;

  unsigned int
  n_quads() const;

  unsigned int
  n_quads(const unsigned int level) const;

  unsigned int
  n_active_quads() const;

  unsigned int
  n_active_quads(const unsigned int level) const;

  unsigned int
  n_hexs() const;

  unsigned int
  n_hexs(const unsigned int level) const;

  unsigned int
  n_active_hexs() const;

  unsigned int
  n_active_hexs(const unsigned int level) const;

  unsigned int
  n_cells() const;

  unsigned int
  n_cells(const unsigned int level) const;

  unsigned int
  n_active_cells() const;

  virtual types::global_cell_index
  n_global_active_cells() const;
 

  unsigned int
  n_active_cells(const unsigned int level) const;

  virtual types::coarse_cell_id
  n_global_coarse_cells() const;

  unsigned int
  n_faces() const;

  unsigned int
  n_active_faces() const;

  unsigned int
  n_levels() const;

  virtual unsigned int
  n_global_levels() const;

  virtual bool
  has_hanging_nodes() const;

  unsigned int
  n_vertices() const;

  const std::vector<Point<spacedim>> &
  get_vertices() const;

  unsigned int
  n_used_vertices() const;

  bool
  vertex_used(const unsigned int index) const;

  const std::vector<bool> &
  get_used_vertices() const;

  unsigned int
  max_adjacent_cells() const;

  virtual types::subdomain_id
  locally_owned_subdomain() const;

  Triangulation<dim, spacedim> &
  get_triangulation();

  const Triangulation<dim, spacedim> &
  get_triangulation() const;
 



  unsigned int
  n_raw_lines() const;

  unsigned int
  n_raw_lines(const unsigned int level) const;

  unsigned int
  n_raw_quads() const;

  unsigned int
  n_raw_quads(const unsigned int level) const;

  unsigned int
  n_raw_hexs(const unsigned int level) const;

  unsigned int
  n_raw_cells(const unsigned int level) const;

  unsigned int
  n_raw_faces() const;


  virtual std::size_t
  memory_consumption() const;

  template <class Archive>
  void
  save(Archive &ar, const unsigned int version) const;

  template <class Archive>
  void
  load(Archive &ar, const unsigned int version);
 

  virtual void
  save(const std::string &file_basename) const;

  virtual void
  load(const std::string &file_basename);
 

  virtual void
  add_periodicity(
    const std::vector<GridTools::PeriodicFacePair<cell_iterator>> &);

  const std::map<std::pair<cell_iterator, unsigned int>,
                 std::pair<std::pair<cell_iterator, unsigned int>,
                           types::geometric_orientation>> &
  get_periodic_face_map() const;

  const std::vector<ReferenceCell<dim>> &
  get_reference_cells() const;

  bool
  all_reference_cells_are_hyper_cube() const;

  bool
  all_reference_cells_are_simplex() const;

  bool
  is_mixed_mesh() const;
 
#ifdef DOXYGEN
  template <class Archive>
  void
  serialize(Archive &archive, const unsigned int version);
#else
  // This macro defines the serialize() method that is compatible with
  // the templated save() and load() method that have been implemented.
  BOOST_SERIALIZATION_SPLIT_MEMBER()
#endif

public:
  unsigned int
  register_data_attach(
    const std::function<std::vector<char>(const cell_iterator &,
                                          const ::CellStatus)>
              &pack_callback,
    const bool returns_variable_size_data);

  void
  notify_ready_to_unpack(
    const unsigned int handle,
    const std::function<
      void(const cell_iterator &,
           const ::CellStatus,
           const boost::iterator_range<std::vector<char>::const_iterator> &)>
      &unpack_callback);
 
  internal::CellAttachedData<dim, spacedim> cell_attached_data;
 
protected:
  void
  save_attached_data(const unsigned int global_first_cell,
                     const unsigned int global_num_cells,
                     const std::string &file_basename) const;

  void
  load_attached_data(const unsigned int global_first_cell,
                     const unsigned int global_num_cells,
                     const unsigned int local_num_cells,
                     const std::string &file_basename,
                     const unsigned int n_attached_deserialize_fixed,
                     const unsigned int n_attached_deserialize_variable);

  void
  update_cell_relations();

  void
  pack_data_serial();
 

  void
  unpack_data_serial();

  std::vector<typename internal::CellAttachedDataSerializer<dim, spacedim>::
                cell_relation_t>
    local_cell_relations;
 
  internal::CellAttachedDataSerializer<dim, spacedim> data_serializer;
 
public:

  DeclExceptionMsg(ExcTooManyLevels,
                   "The provided refinement pattern requires creating a level "
                   "in the Triangulation. However, the maximum number of "
                   "levels has already been reached, so that is not allowed.");
 
  DeclException2(ExcInvalidLevel,
                 int,
                 int,
                 << "You are requesting information from refinement level "
                 << arg1
                 << " of a triangulation, but this triangulation only has "
                 << arg2 << " refinement levels. The given level " << arg1
                 << " must be *less* than " << arg2 << '.');
  DeclException2(
    ExcTriangulationNotEmpty,
    int,
    int,
    << "You are trying to perform an operation on a triangulation "
    << "that is only allowed if the triangulation is currently empty. "
    << "However, it currently stores " << arg1 << " vertices and has "
    << "cells on " << arg2 << " levels.");
  DeclException0(ExcGridReadError);
  DeclException0(ExcFacesHaveNoLevel);
  DeclException1(ExcEmptyLevel,
                 int,
                 << "You tried to do something on level " << arg1
                 << ", but this level is empty.");

  DeclException1(ExcBoundaryIdNotFound,
                 types::boundary_id,
                 << "The given boundary_id " << arg1
                 << " is not defined in this Triangulation!");
 
protected:
  MeshSmoothing smooth_grid;

  std::vector<ReferenceCell<dim>> reference_cells;

  internal::TriangulationImplementation::Strides<dim> strides;

  std::optional<Table<2, std::set<active_cell_iterator>>>
    line_to_adjacent_cells_map;

  static void
  write_bool_vector(const unsigned int       magic_number1,
                    const std::vector<bool> &v,
                    const unsigned int       magic_number2,
                    std::ostream            &out);

  static void
  read_bool_vector(const unsigned int magic_number1,
                   std::vector<bool> &v,
                   const unsigned int magic_number2,
                   std::istream      &in);

  void
  update_periodic_face_map();
 
 
private:
  std::unique_ptr<
    ::internal::TriangulationImplementation::Policy<dim, spacedim>>
    policy;

  std::vector<GridTools::PeriodicFacePair<cell_iterator>>
    periodic_face_pairs_level_0;

  std::map<std::pair<cell_iterator, unsigned int>,
           std::pair<std::pair<cell_iterator, unsigned int>,
                     types::geometric_orientation>>
    periodic_face_map;

  using raw_cell_iterator = TriaRawIterator<CellAccessor<dim, spacedim>>;
  using raw_face_iterator =
    TriaRawIterator<TriaAccessor<dim - 1, dim, spacedim>>;
  using raw_vertex_iterator =
    TriaRawIterator<::TriaAccessor<0, dim, spacedim>>;
  using raw_line_iterator = typename IteratorSelector::raw_line_iterator;
  using raw_quad_iterator = typename IteratorSelector::raw_quad_iterator;
  using raw_hex_iterator  = typename IteratorSelector::raw_hex_iterator;


  raw_cell_iterator
  begin_raw(const unsigned int level = 0) const;

  raw_cell_iterator
  end_raw(const unsigned int level) const;



  raw_line_iterator
  begin_raw_line(const unsigned int level = 0) const;

  line_iterator
  begin_line(const unsigned int level = 0) const;

  active_line_iterator
  begin_active_line(const unsigned int level = 0) const;

  line_iterator
  end_line() const;



  raw_quad_iterator
  begin_raw_quad(const unsigned int level = 0) const;

  quad_iterator
  begin_quad(const unsigned int level = 0) const;

  active_quad_iterator
  begin_active_quad(const unsigned int level = 0) const;

  quad_iterator
  end_quad() const;



  raw_hex_iterator
  begin_raw_hex(const unsigned int level = 0) const;

  hex_iterator
  begin_hex(const unsigned int level = 0) const;

  active_hex_iterator
  begin_active_hex(const unsigned int level = 0) const;

  hex_iterator
  end_hex() const;

 

  void
  clear_despite_subscriptions();

  void
  reset_policy();

  void
  reset_active_cell_indices();

  void
  reset_global_cell_indices();

  void
  reset_cell_vertex_indices_cache();

  DistortedCellList
  execute_refinement();

  void
  execute_coarsening();

  void
  fix_coarsen_flags();

  virtual unsigned int
  coarse_cell_id_to_coarse_cell_index(
    const types::coarse_cell_id coarse_cell_id) const;
 

  virtual types::coarse_cell_id
  coarse_cell_index_to_coarse_cell_id(
    const unsigned int coarse_cell_index) const;

  std::vector<std::unique_ptr<
    ::internal::TriangulationImplementation::TriaLevel<dim, spacedim>>>
    levels;

  std::unique_ptr<::internal::TriangulationImplementation::TriaFaces<dim>>
    faces;
 

  std::vector<Point<spacedim>> vertices;

  std::vector<bool> vertices_used;

  std::map<types::manifold_id, std::unique_ptr<const Manifold<dim, spacedim>>>
    manifolds;

  const std::unique_ptr<const Manifold<dim, spacedim>> default_flat_manifold;

  bool anisotropic_refinement;
 

  const bool check_for_distorted_cells;

  ::internal::TriangulationImplementation::NumberCache<dim> number_cache;

  std::unique_ptr<std::map<unsigned int, types::boundary_id>>
    vertex_to_boundary_id_map_1d;
 

  std::unique_ptr<std::map<unsigned int, types::manifold_id>>
    vertex_to_manifold_id_map_1d;
 
  // make a couple of classes friends
  template <int, int, int>
  friend class TriaAccessorBase;
  template <int, int, int>
  friend class TriaAccessor;
  friend class TriaAccessor<0, 1, spacedim>;
 
  friend class CellAccessor<dim, spacedim>;
 
  friend struct ::internal::TriaAccessorImplementation::Implementation;
 
  friend struct ::internal::TriangulationImplementation::Implementation;
  friend struct ::internal::TriangulationImplementation::
    ImplementationMixedMesh;
 
  friend class ::internal::TriangulationImplementation::TriaObjects;
 
  // explicitly check for sensible template arguments, but not on windows
  // because MSVC creates bogus warnings during normal compilation
#ifndef DEAL_II_MSVC
  static_assert(dim <= spacedim,
                "The dimension <dim> of a Triangulation must be less than or "
                "equal to the space dimension <spacedim> in which it lives.");
#endif
};
 
 
#ifndef DOXYGEN
 
 
 
namespace internal
{
  namespace TriangulationImplementation
  {
    template <class Archive>
    void
    NumberCache<1>::serialize(Archive &ar, const unsigned int)
    {
      ar                 &n_levels;
      ar &n_lines        &n_lines_level;
      ar &n_active_lines &n_active_lines_level;
    }
 
 
    template <class Archive>
    void
    NumberCache<2>::serialize(Archive &ar, const unsigned int version)
    {
      this->NumberCache<1>::serialize(ar, version);
 
      ar &n_quads        &n_quads_level;
      ar &n_active_quads &n_active_quads_level;
    }
 
 
    template <class Archive>
    void
    NumberCache<3>::serialize(Archive &ar, const unsigned int version)
    {
      this->NumberCache<2>::serialize(ar, version);
 
      ar &n_hexes        &n_hexes_level;
      ar &n_active_hexes &n_active_hexes_level;
    }
  } // namespace TriangulationImplementation
} // namespace internal
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline bool Triangulation<dim, spacedim>::vertex_used(
  const unsigned int index) const
{
  AssertIndexRange(index, vertices_used.size());
  return vertices_used[index];
}
 
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline unsigned int Triangulation<dim, spacedim>::n_levels() const
{
  return number_cache.n_levels;
}
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline unsigned int Triangulation<dim, spacedim>::n_global_levels() const
{
  return number_cache.n_levels;
}
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline unsigned int Triangulation<dim, spacedim>::n_vertices() const
{
  return vertices.size();
}
 
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline const std::vector<Point<spacedim>>
  &Triangulation<dim, spacedim>::get_vertices() const
{
  return vertices;
}
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
template <class Archive>
void Triangulation<dim, spacedim>::save(Archive &ar, const unsigned int) const
{
  // as discussed in the documentation, do not store the signals as
  // well as boundary and manifold description but everything else
  ar &smooth_grid;
 
  ar &reference_cells;
 
  unsigned int n_levels = levels.size();
  ar          &n_levels;
  Assert(n_levels <= numbers::max_n_levels, ExcInternalError());
  for (const auto &level : levels)
    ar &level;
 
  // boost dereferences a nullptr when serializing a nullptr
  // at least up to 1.65.1. This causes problems with clang-5.
  // Therefore, work around it.
  bool faces_is_nullptr = (faces.get() == nullptr);
  ar  &faces_is_nullptr;
  if (!faces_is_nullptr)
    ar &faces;
 
  ar &vertices;
  ar &vertices_used;
 
  ar &anisotropic_refinement;
  ar &number_cache;
 
  ar &check_for_distorted_cells;
 
  if (dim == 1)
    {
      ar &vertex_to_boundary_id_map_1d;
      ar &vertex_to_manifold_id_map_1d;
    }
}
 
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
template <class Archive>
void Triangulation<dim, spacedim>::load(Archive &ar, const unsigned int)
{
  // clear previous content. this also calls the respective signal
  clear();
 
  // as discussed in the documentation, do not store the signals as
  // well as boundary and manifold description but everything else
  ar &smooth_grid;
 
  ar &reference_cells;
  strides =
    internal::TriangulationImplementation::Strides<dim>(reference_cells);
 
  unsigned int n_levels;
  ar          &n_levels;
  Assert(n_levels <= numbers::max_n_levels, ExcInternalError());
  levels.resize(n_levels);
  for (auto &level_ : levels)
    {
      std::unique_ptr<
        internal::TriangulationImplementation::TriaLevel<dim, spacedim>>
          level;
      ar &level;
      level_ = std::move(level);
    }
 
  // Workaround for nullptr, see in save().
  bool faces_is_nullptr = true;
  ar  &faces_is_nullptr;
  if (!faces_is_nullptr)
    ar &faces;
 
  ar &vertices;
  ar &vertices_used;
 
  ar &anisotropic_refinement;
  ar &number_cache;
 
  // the levels do not serialize the active_cell_indices or cached cell vertices
  // because they are easy enough to rebuild upon re-loading data. do this here.
  reset_cell_vertex_indices_cache();
  reset_active_cell_indices();
  reset_global_cell_indices();
 
  reset_policy();
 
  bool my_check_for_distorted_cells;
  ar  &my_check_for_distorted_cells;
 
  Assert(my_check_for_distorted_cells == check_for_distorted_cells,
         ExcMessage("The triangulation loaded into here must have the "
                    "same setting with regard to reporting distorted "
                    "cell as the one previously stored."));
 
  if (dim == 1)
    {
      ar &vertex_to_boundary_id_map_1d;
      ar &vertex_to_manifold_id_map_1d;
    }
 
  // trigger the create signal to indicate
  // that new content has been imported into
  // the triangulation
  signals.create();
}
 
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline unsigned int Triangulation<dim, spacedim>::
  coarse_cell_id_to_coarse_cell_index(
    const types::coarse_cell_id coarse_cell_id) const
{
  return coarse_cell_id;
}
 
 
 
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
inline types::coarse_cell_id
  Triangulation<dim, spacedim>::coarse_cell_index_to_coarse_cell_id(
    const unsigned int coarse_cell_index) const
{
  return coarse_cell_index;
}
 
 
 
/* -------------- declaration of explicit specializations ------------- */
 
template <>
unsigned int
Triangulation<1, 1>::max_adjacent_cells() const;
template <>
unsigned int
Triangulation<1, 2>::max_adjacent_cells() const;
template <>
unsigned int
Triangulation<1, 3>::max_adjacent_cells() const;
 
template <>
bool
Triangulation<1, 1>::prepare_coarsening_and_refinement();
template <>
bool
Triangulation<1, 2>::prepare_coarsening_and_refinement();
template <>
bool
Triangulation<1, 3>::prepare_coarsening_and_refinement();
 
 
// Declare the existence of explicit instantiations of the class
// above. This is not strictly necessary, but tells the compiler to
// avoid instantiating templates that we know are instantiated in
// .cc files and so can be referenced without implicit
// instantiations.
//
// Unfortunately, this does not seem to work when building modules
// with clang++ versions before 22 because they then just don't
// instantiate these classes at all, even though their members are
// defined and explicitly instantiated in a .cc file.
//
// See https://github.com/llvm/llvm-project/issues/153225 for the
// corresponding bug report.
#  if !(defined(DEAL_II_BUILDING_CXX20_MODULE) && defined(__clang__) && \
        (__clang_major__ < 22))
extern template class Triangulation<1, 1>;
extern template class Triangulation<1, 2>;
extern template class Triangulation<1, 3>;
extern template class Triangulation<2, 2>;
extern template class Triangulation<2, 3>;
extern template class Triangulation<3, 3>;
#  endif
 
#endif // DOXYGEN
 
DEAL_II_NAMESPACE_CLOSE
 
#endif