tria.h

Go to the documentation of this file.

// ------------------------------------------------------------------------
//
// SPDX-License-Identifier: LGPL-2.1-or-later
// Copyright (C) 1998 - 2024 by the deal.II authors
//
// This file is part of the deal.II library.
//
// Part of the source code is dual licensed under Apache-2.0 WITH
// LLVM-exception OR LGPL-2.1-or-later. Detailed license information
// governing the source code and code contributions can be found in
// LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II.
//
// ------------------------------------------------------------------------
 
#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/grid/cell_id.h>
#include <deal.II/grid/cell_status.h>
#include <deal.II/grid/tria_description.h>
#include <deal.II/grid/tria_iterator_selector.h>
#include <deal.II/grid/tria_levels.h>
 
#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 <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
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
  {
    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);
    };
  } // 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_EARLY_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
  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>, unsigned char>> &
  get_periodic_face_map() const;
 
  const std::vector<ReferenceCell> &
  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:
  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!");
 
  DeclExceptionMsg(
    ExcInconsistentCoarseningFlags,
    "A cell is flagged for coarsening, but either not all of its siblings "
    "are active or flagged for coarsening as well. Please clean up all "
    "coarsen flags on your triangulation via "
    "Triangulation::prepare_coarsening_and_refinement() beforehand!");
 
protected:
  MeshSmoothing smooth_grid;
 
  std::vector<ReferenceCell> reference_cells;
 
  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();
 
  virtual void
  update_reference_cells();
 
 
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>, unsigned char>>
    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>>
    levels;
 
  std::unique_ptr<::internal::TriangulationImplementation::TriaFaces>
    faces;
 
 
  std::vector<Point<spacedim>> vertices;
 
  std::vector<bool> vertices_used;
 
  std::map<types::manifold_id, std::unique_ptr<const Manifold<dim, spacedim>>>
    manifolds;
 
  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;
 
  unsigned int n_levels = levels.size();
  ar          &n_levels;
  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;
 
  unsigned int size;
  ar          &size;
  levels.resize(size);
  for (auto &level_ : levels)
    {
      std::unique_ptr<internal::TriangulationImplementation::TriaLevel> 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 because
  // they are easy enough to rebuild upon re-loading data. do
  // this here. don't forget to first resize the fields appropriately
  {
    for (const auto &level : levels)
      {
        level->active_cell_indices.resize(level->refine_flags.size());
        level->global_active_cell_indices.resize(level->refine_flags.size());
        level->global_level_cell_indices.resize(level->refine_flags.size());
      }
    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>::n_quads() const;
template <>
unsigned int
Triangulation<1, 1>::n_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 1>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<2, 2>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<3, 3>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<3, 3>::n_raw_quads() const;
template <>
unsigned int
Triangulation<1, 1>::n_active_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 1>::n_active_quads() const;
template <>
unsigned int
Triangulation<1, 1>::n_raw_hexs(const unsigned int level) const;
template <>
unsigned int
Triangulation<3, 3>::n_raw_hexs(const unsigned int level) const;
template <>
unsigned int
Triangulation<3, 3>::n_hexs() const;
template <>
unsigned int
Triangulation<3, 3>::n_active_hexs() const;
template <>
unsigned int
Triangulation<3, 3>::n_active_hexs(const unsigned int) const;
template <>
unsigned int
Triangulation<3, 3>::n_hexs(const unsigned int level) const;
 
template <>
unsigned int
Triangulation<1, 1>::max_adjacent_cells() const;
 
 
// -------------------------------------------------------------------
// -- Explicit specializations for codimension one grids
 
 
template <>
unsigned int
Triangulation<1, 2>::n_quads() const;
template <>
unsigned int
Triangulation<1, 2>::n_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 2>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<2, 3>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 2>::n_raw_hexs(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 2>::n_active_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 2>::n_active_quads() const;
template <>
unsigned int
Triangulation<1, 2>::max_adjacent_cells() const;
 
// -------------------------------------------------------------------
// -- Explicit specializations for codimension two grids
 
template <>
unsigned int
Triangulation<1, 3>::n_quads() const;
template <>
unsigned int
Triangulation<1, 3>::n_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 3>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<2, 3>::n_raw_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 3>::n_raw_hexs(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 3>::n_active_quads(const unsigned int level) const;
template <>
unsigned int
Triangulation<1, 3>::n_active_quads() 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();
 
 
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 // DOXYGEN
 
DEAL_II_NAMESPACE_CLOSE
 
// Include tria_accessor.h here, so that it is possible for an end
// user to use the iterators of Triangulation<dim> directly without
// the need to include tria_accessor.h separately. (Otherwise the
// iterators are an 'opaque' or 'incomplete' type.)
#include <deal.II/grid/tria_accessor.h>
 
#endif