cell_id.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) 2013 - 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_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>
 
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<std::uint64_t, 3>;
 
  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;
 
  std::uint8_t n_child_indices;
 
  std::array<std::uint8_t, numbers::max_n_levels - 1> child_indices;
 
  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 << '_' << int(cid.n_child_indices) << ':';
  for (std::uint8_t 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)
{
  types::coarse_cell_id cellid = numbers::invalid_coarse_cell_id;
  is >> cellid;
  if (is.eof())
    return is;
 
  cid.coarse_cell_id = cellid;
  char dummy;
  is >> dummy;
  Assert(dummy == '_', ExcMessage("invalid CellId"));
  unsigned int n_child_indices;
  is >> n_child_indices;
  Assert(n_child_indices < cid.child_indices.size(),
         ExcMessage("invalid CellId"));
  cid.n_child_indices = static_cast<std::uint8_t>(n_child_indices);
  is >> dummy;
  Assert(dummy == ':', ExcMessage("invalid CellId"));
 
  unsigned char value;
  for (std::uint8_t 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 (std::uint8_t 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;
 
  std::uint8_t 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 (std::uint8_t 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(), std::size_t(n_child_indices)};
}
 
 
DEAL_II_NAMESPACE_CLOSE
 
#endif