cell_id.h

// ---------------------------------------------------------------------
//
// Copyright (C) 1998 - 2018 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_cell_id_h
#define dealii_cell_id_h

#include <deal.II/base/config.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

template <int, int>
class Triangulation;

class CellId
{
public:
  using binary_type = std::array<unsigned int, 4>;

  CellId(const unsigned int               coarse_cell_id,
         const std::vector<std::uint8_t> &child_indices);

  CellId(const unsigned int  coarse_cell_id,
         const unsigned int  n_child_indices,
         const std::uint8_t *child_indices);

  CellId(const binary_type &binary_representation);

  CellId();

  std::string
  to_string() const;

  template <int dim>
  binary_type
  to_binary() const;

  template <int dim, int spacedim>
  typename Triangulation<dim, spacedim>::cell_iterator
  to_cell(const Triangulation<dim, spacedim> &tria) const;

  bool
  operator==(const CellId &other) const;

  bool
  operator!=(const CellId &other) const;

  bool
  operator<(const CellId &other) const;

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

private:
  unsigned int 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
}

DEAL_II_NAMESPACE_CLOSE

#endif