cell_id.h

Go to the documentation of this file.

// ------------------------------------------------------------------------
//
// SPDX-License-Identifier: LGPL-2.1-or-later
// Copyright (C) 2013 - 2023 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_cell_id_h
#define dealii_cell_id_h
 
#include <deal.II/base/config.h>
 
#include <deal.II/base/array_view.h>
#include <deal.II/base/exceptions.h>
 
#include <array>
#include <cstdint>
#include <iostream>
#include <vector>
 
#ifdef DEAL_II_WITH_P4EST
#  include <deal.II/distributed/p4est_wrappers.h>
#endif
 
DEAL_II_NAMESPACE_OPEN
 
// Forward declarations
#ifndef DOXYGEN
template <int dim, int spacedim>
DEAL_II_CXX20_REQUIRES((concepts::is_valid_dim_spacedim<dim, spacedim>))
class Triangulation;
#endif
 
class CellId
{
public:
  using binary_type = std::array<unsigned int, 4>;
 
  CellId(const types::coarse_cell_id      coarse_cell_id,
         const std::vector<std::uint8_t> &child_indices);
 
  CellId(const types::coarse_cell_id coarse_cell_id,
         const unsigned int          n_child_indices,
         const std::uint8_t         *child_indices);
 
  CellId(const binary_type &binary_representation);
 
  explicit CellId(const std::string &string_representation);
 
  CellId();
 
  std::string
  to_string() const;
 
  template <int dim>
  binary_type
  to_binary() const;
 
  bool
  operator==(const CellId &other) const;
 
  bool
  operator!=(const CellId &other) const;
 
  bool
  operator<(const CellId &other) const;
 
  bool
  is_parent_of(const CellId &other) const;
 
  bool
  is_ancestor_of(const CellId &other) const;
 
  template <class Archive>
  void
  serialize(Archive &ar, const unsigned int version);
 
  types::coarse_cell_id
  get_coarse_cell_id() const;
 
  ArrayView<const std::uint8_t>
  get_child_indices() const;
 
private:
  types::coarse_cell_id coarse_cell_id;
 
  unsigned int n_child_indices;
 
#ifdef DEAL_II_WITH_P4EST
  std::array<std::uint8_t, internal::p4est::functions<2>::max_level>
    child_indices;
#else
  std::array<std::uint8_t, 30> child_indices;
#endif
 
  friend std::istream &
  operator>>(std::istream &is, CellId &cid);
  friend std::ostream &
  operator<<(std::ostream &os, const CellId &cid);
};
 
 
 
inline std::ostream &
operator<<(std::ostream &os, const CellId &cid)
{
  os << cid.coarse_cell_id << '_' << cid.n_child_indices << ':';
  for (unsigned int i = 0; i < cid.n_child_indices; ++i)
    // write the child indices. because they are between 0 and 2^dim-1, they all
    // just have one digit, so we could write them as one character
    // objects. it's probably clearer to write them as one-digit characters
    // starting at '0'
    os << static_cast<unsigned char>('0' + cid.child_indices[i]);
  return os;
}
 
 
 
template <class Archive>
void
CellId::serialize(Archive &ar, const unsigned int /*version*/)
{
  ar &coarse_cell_id;
  ar &n_child_indices;
  ar &child_indices;
}
 
inline std::istream &
operator>>(std::istream &is, CellId &cid)
{
  unsigned int cellid;
  is >> cellid;
  if (is.eof())
    return is;
 
  cid.coarse_cell_id = cellid;
  char dummy;
  is >> dummy;
  Assert(dummy == '_', ExcMessage("invalid CellId"));
  is >> cid.n_child_indices;
  is >> dummy;
  Assert(dummy == ':', ExcMessage("invalid CellId"));
 
  unsigned char value;
  for (unsigned int i = 0; i < cid.n_child_indices; ++i)
    {
      // read the one-digit child index (as an integer number) and
      // convert it back into unsigned integer type
      is >> value;
      cid.child_indices[i] = value - '0';
    }
  return is;
}
 
 
 
inline bool
CellId::operator==(const CellId &other) const
{
  if (this->coarse_cell_id != other.coarse_cell_id)
    return false;
  if (n_child_indices != other.n_child_indices)
    return false;
 
  for (unsigned int i = 0; i < n_child_indices; ++i)
    if (child_indices[i] != other.child_indices[i])
      return false;
 
  return true;
}
 
 
 
inline bool
CellId::operator!=(const CellId &other) const
{
  return !(*this == other);
}
 
 
 
inline bool
CellId::operator<(const CellId &other) const
{
  if (this->coarse_cell_id != other.coarse_cell_id)
    return this->coarse_cell_id < other.coarse_cell_id;
 
  unsigned int idx = 0;
  while (idx < n_child_indices)
    {
      if (idx >= other.n_child_indices)
        return false;
 
      if (child_indices[idx] != other.child_indices[idx])
        return child_indices[idx] < other.child_indices[idx];
 
      ++idx;
    }
 
  if (n_child_indices == other.n_child_indices)
    return false;
  return true; // other.id is longer
}
 
 
 
inline bool
CellId::is_parent_of(const CellId &other) const
{
  if (this->coarse_cell_id != other.coarse_cell_id)
    return false;
 
  if (n_child_indices + 1 != other.n_child_indices)
    return false;
 
  for (unsigned int idx = 0; idx < n_child_indices; ++idx)
    if (child_indices[idx] != other.child_indices[idx])
      return false;
 
  return true; // other.id is longer
}
 
 
 
inline bool
CellId::is_ancestor_of(const CellId &other) const
{
  if (this->coarse_cell_id != other.coarse_cell_id)
    return false;
 
  if (n_child_indices >= other.n_child_indices)
    return false;
 
  for (unsigned int idx = 0; idx < n_child_indices; ++idx)
    if (child_indices[idx] != other.child_indices[idx])
      return false;
 
  return true; // other.id is longer
}
 
 
 
inline types::coarse_cell_id
CellId::get_coarse_cell_id() const
{
  return coarse_cell_id;
}
 
 
 
inline ArrayView<const std::uint8_t>
CellId::get_child_indices() const
{
  return {child_indices.data(), n_child_indices};
}
 
 
DEAL_II_NAMESPACE_CLOSE
 
#endif