tria.h

Go to the documentation of this file.

// ---------------------------------------------------------------------
//
// Copyright (C) 1998 - 2022 by the deal.II authors
//
// This file is part of the deal.II library.
//
// The deal.II library is free software; you can use it, redistribute
// it, and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// The full text of the license can be found in the file LICENSE.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/geometry_info.h>
#include <deal.II/base/iterator_range.h>
#include <deal.II/base/point.h>
#include <deal.II/base/smartpointer.h>
#include <deal.II/base/subscriptor.h>
 
#include <deal.II/grid/cell_id.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;
 
      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
} // namespace internal
 
 
/*------------------------------------------------------------------------*/
 
 
template <int dim, int spacedim = dim>
class Triangulation : public Subscriptor
{
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_communicator() 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);
 
  DEAL_II_DEPRECATED
  virtual void
  create_triangulation_compatibility(
    const std::vector<Point<spacedim>> &vertices,
    const std::vector<CellData<dim>> &  cells,
    const SubCellData &                 subcelldata);
 
  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();
 
  /*
   * @}
   */
 
  enum CellStatus
  {
    CELL_PERSIST,
    CELL_REFINE,
    CELL_COARSEN,
    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;
 
    Signals()
      : cell_weight(weight)
    {}
 
    class LegacySignal
    {
    public:
      using signature_type = unsigned int(const cell_iterator &,
                                          const CellStatus);
      using combiner_type  = CellWeightSum<unsigned int>;
 
      using slot_function_type = boost::function<signature_type>;
      using slot_type =
        boost::signals2::slot<signature_type, slot_function_type>;
 
      LegacySignal(
        boost::signals2::signal<signature_type, combiner_type> &new_signal)
        : new_signal(new_signal)
      {}
 
      ~LegacySignal()
      {
        base_weight.disconnect();
      }
 
      DEAL_II_DEPRECATED_EARLY
      boost::signals2::connection
      connect(
        const slot_type &                 slot,
        boost::signals2::connect_position position = boost::signals2::at_back)
      {
        if (base_weight.connected() == false)
          {
            base_weight = new_signal.connect(
              [](const cell_iterator &, const CellStatus) -> unsigned int {
                return 1000;
              });
            Assert(base_weight.connected() && new_signal.num_slots() == 1,
                   ExcInternalError());
          }
 
        return new_signal.connect(slot, position);
      }
 
      DEAL_II_DEPRECATED_EARLY
      std::size_t
      num_slots() const
      {
        return new_signal.num_slots() -
               static_cast<std::size_t>(base_weight.connected());
      }
 
      DEAL_II_DEPRECATED_EARLY
      bool
      empty() const
      {
        if (num_slots() == 0)
          {
            Assert(new_signal.num_slots() == 0, ExcInternalError());
            return true;
          }
        return false;
      }
 
      template <typename S>
      DEAL_II_DEPRECATED_EARLY void
      disconnect(const S &connection)
      {
        new_signal.disconnect(connection);
 
        if (num_slots() == 0)
          {
            Assert(base_weight.connected() && new_signal.num_slots() == 1,
                   ExcInternalError());
            new_signal.disconnect(base_weight);
          }
      }
 
      DEAL_II_DEPRECATED_EARLY
      unsigned int
      operator()(const cell_iterator &iterator, const CellStatus status)
      {
        return new_signal(iterator, status);
      }
 
    private:
      boost::signals2::connection base_weight;
 
      boost::signals2::signal<signature_type, combiner_type> &new_signal;
    };
 
    LegacySignal cell_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;
 
  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
  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>, std::bitset<3>>> &
  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
 
  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.");
  DeclException0(ExcNonOrientableTriangulation);
 
  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>, std::bitset<3>>>
    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>
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>
inline unsigned int
Triangulation<dim, spacedim>::n_levels() const
{
  return number_cache.n_levels;
}
 
template <int dim, int spacedim>
inline unsigned int
Triangulation<dim, spacedim>::n_global_levels() const
{
  return number_cache.n_levels;
}
 
 
template <int dim, int spacedim>
inline unsigned int
Triangulation<dim, spacedim>::n_vertices() const
{
  return vertices.size();
}
 
 
 
template <int dim, int spacedim>
inline const std::vector<Point<spacedim>> &
Triangulation<dim, spacedim>::get_vertices() const
{
  return vertices;
}
 
 
template <int dim, int 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>
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 (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>
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>
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