vtkKeys.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
 
#ifndef vtkKeys_h
#define vtkKeys_h
 
#include "vtkABINamespace.h"
#include "vtkKeysTraits.h" // For the checks of the concepts
#include "vtkType.h"       // For vtkIdType
 
#include <cstdint>
#include <memory>
#include <type_traits>
 
//------------------------------------------------------------------------------
// Concepts, checked at compile time, see vtkKeysTraits.h.
//
// Input: records that are the elements (1-1).
//   RecordIdType GetNumberOfRecords() const;
//   KeyType GetKey(RecordIdType record) const; // called concurrently
//   // Optional, otherwise the type of GetKey() and RecordIdType.
//   using KeyType = ...;
//   using ElementIdType = ...;
//
// InputMapper: records mapped to several elements (1-M), e.g., cells to their faces.
//   using KeyType = ...;
//   using ElementIdType = ...; // must hold the number of elements
//   RecordIdType GetNumberOfRecords() const;
//   // The number of elements of record beginRecord + i, to counts[i].
//   void CountElements(RecordIdType beginRecord, RecordIdType endRecord,
//     ElementIdType* counts) const;
//   // The keys of the elements of every record, to keys[offsets[record]], ..., in order.
//   void WriteKeys(RecordIdType beginRecord, RecordIdType endRecord,
//     const ElementIdType* offsets, KeyType* keys) const;
//   The methods are called concurrently on disjoint ranges of records, so that they can set up
//   their scratch data once per range.
//
// Output: the scattered elements, in one array or in several (a structure of arrays).
//   void SetNumberOfElements(ElementIdType numberOfElements); // 0 first, to release
//   // Called concurrently, at distinct positions, with the record of an Input, or the record
//   // and the index of the element in its record of an InputMapper, from which the Output reads
//   // what it needs, as Viskores's ExternalFaces worklet does.
//   void SetElement(ElementIdType position, RecordIdType record);
//   void SetElement(ElementIdType position, RecordIdType record, ElementIdType index);
//   // For Compact() only, as vtkDataSetAttributes::CopyData().
//   void CopyData(const Output& source, ElementIdType destinationStart, ElementIdType count,
//     ElementIdType sourceStart);
//
// KeyType: an integer type for ScatterDense(); for ScatterSparse(), any type that is default
//   constructible, copy assignable and ordered by operator<, e.g., std::pair<vtkIdType, vtkIdType>.
//
// Element: an element of an array, copy assignable, with
//   KeyType GetKey() const; // equal elements have the same key
//   and, for SortUnique and SortGroup, operator<, operator== and operator!=. The ElementIdType of
//   an array is the type of its number of elements.
//
// Keys: the result of ScatterDense() or ScatterSparse(), a DenseKeys or a SparseKeys, or their
//   reductions, which derive from KeysBase, all that the operations use.
//
// Functors of ForEachKeyRange(), Reduce() and Group(): callables on a range of key ids of the
// Output, called concurrently on disjoint ranges, see ForEachKeyRange():
//   // Reduce functor: keep the survivors of key id k at its front, their number to counts[k].
//   void operator()(Output& output, KeyIdType beginKeyId, KeyIdType endKeyId,
//     const ElementIdType* offsets, ElementIdType* counts);
//   // Group functor: make the equal elements of every key contiguous, and set groupStarts[i] to 1
//   // for every element i that differs from the previous one.
//   void operator()(Output& output, KeyIdType beginKeyId, KeyIdType endKeyId,
//     const ElementIdType* offsets, uint8_t* groupStarts);
//   As vtkSMPTools functors, they can have an Initialize() and a Reduce(), to keep their scratch
//   data or their results per thread.
namespace vtk
{
namespace keys
{
namespace detail
{
VTK_ABI_NAMESPACE_BEGIN
 
// The writers of the results, defined in vtkKeys.txx.
struct DenseScatterer;
struct SparseScatterer;
struct Reducer;
struct Grouper;
 
VTK_ABI_NAMESPACE_END
} // namespace detail
 
VTK_ABI_NAMESPACE_BEGIN

template <typename TKey, typename TElementId, typename TKeyId>
class KeysBase
{
public:
  using KeyType = TKey;
  using ElementIdType = TElementId;
  using KeyIdType = TKeyId;
 
  static_assert(std::is_integral_v<ElementIdType>, "ElementIdType must be an integer type");
 
  vtkIdType GetNumberOfRecords() const { return this->NumberOfRecords; }
  vtkIdType GetNumberOfElements() const { return this->NumberOfElements; }
  KeyIdType GetNumberOfKeys() const { return this->NumberOfKeys; }

  ElementIdType GetOffset(KeyIdType keyId) const { return this->Offsets[keyId]; }

  const ElementIdType* GetOffsets() const { return this->Offsets.get(); }
 
  ElementIdType GetNumberOfElementsOfKey(KeyIdType keyId) const
  {
    return this->Offsets[keyId + 1] - this->Offsets[keyId];
  }
 
protected:
  void ResetBase()
  {
    this->NumberOfRecords = this->NumberOfElements = 0;
    this->NumberOfKeys = 0;
    this->Offsets.reset();
  }
 
  // The records and the keys of other keys, e.g., of a reduction, without their offsets.
  void CopyBaseFrom(const KeysBase& other)
  {
    this->NumberOfRecords = other.NumberOfRecords;
    this->NumberOfKeys = other.NumberOfKeys;
  }
 
  vtkIdType NumberOfRecords = 0;
  vtkIdType NumberOfElements = 0;
  KeyIdType NumberOfKeys = 0;
  std::unique_ptr<ElementIdType[]> Offsets; // NumberOfKeys + 1
};

template <typename TKey = vtkIdType, typename TElementId = vtkIdType>
class DenseKeys : public KeysBase<TKey, TElementId, TKey>
{
public:
  using KeyType = TKey;
  using KeyIdType = TKey;
 
  static_assert(std::is_integral_v<KeyType> && !std::is_same_v<KeyType, bool>,
    "The KeyType of DenseKeys must be an integer type: a key id is its difference with the "
    "minimum key");
 
  KeyType GetMinKey() const { return this->MinKey; }
  KeyType GetMaxKey() const { return this->MaxKey; }

  KeyType GetKey(KeyIdType keyId) const { return this->MinKey + keyId; }
  KeyIdType GetKeyId(KeyType key) const { return DenseKeys::GetKeyId(key, this->MinKey); }

  void Reset()
  {
    this->ResetBase();
    this->MinKey = this->MaxKey = 0;
  }
 
private:
  friend struct detail::DenseScatterer;
  friend struct detail::Reducer;
  friend struct detail::Grouper;
 
  // The key id of a key given the minimum key, kept in a register by the loops of ScatterDense().
  static KeyIdType GetKeyId(KeyType key, KeyType minKey) { return key - minKey; }
 
  // The keys of other keys of this type, e.g., of a reduction.
  void CopyKeysFrom(const DenseKeys& other)
  {
    this->CopyBaseFrom(other);
    this->MinKey = other.MinKey;
    this->MaxKey = other.MaxKey;
  }
 
  KeyType MinKey = 0;
  KeyType MaxKey = 0;
};

template <typename TKey = vtkIdType, typename TElementId = vtkIdType>
class SparseKeys : public KeysBase<TKey, TElementId, TElementId>
{
public:
  using KeyType = TKey;
  using KeyIdType = TElementId;
 
  static_assert(std::is_signed_v<TElementId>, "ElementIdType must be signed, see FindKeyId()");

  KeyType GetKey(KeyIdType keyId) const { return this->Keys[keyId]; }
  KeyIdType FindKeyId(KeyType key) const;

  void Reset()
  {
    this->ResetBase();
    this->Keys.reset();
  }
 
private:
  friend struct detail::SparseScatterer;
  friend struct detail::Reducer;
  friend struct detail::Grouper;
 
  // The keys of other keys of this type, e.g., of a reduction, which share the distinct keys.
  void CopyKeysFrom(const SparseKeys& other)
  {
    this->CopyBaseFrom(other);
    this->Keys = other.Keys;
  }
 
  std::shared_ptr<KeyType[]> Keys; // NumberOfKeys
};

template <typename Input>
using DenseKeysOf = DenseKeys<detail::KeyTypeOfT<Input>, detail::ElementIdTypeOfT<Input>>;
template <typename Input>
using SparseKeysOf = SparseKeys<detail::KeyTypeOfT<Input>, detail::ElementIdTypeOfT<Input>>;
template <typename Element, typename ElementIdType>
using DenseArrayKeys = DenseKeys<detail::ElementKeyOf<Element>, ElementIdType>;
template <typename Element, typename ElementIdType>
using SparseArrayKeys = SparseKeys<detail::ElementKeyOf<Element>, ElementIdType>;
 
//------------------------------------------------------------------------------
// ScatterDense() and ScatterSparse(): the elements are moved to the Output in key order.

template <typename InputMapper>
vtkIdType CountElements(const InputMapper& mapper);

template <typename Input, typename Output>
DenseKeysOf<Input> ScatterDense(const Input& input, Output& output);
template <typename Input, typename Output>
DenseKeysOf<Input> ScatterDense(const Input& input, detail::KeyTypeOfT<Input> minKey,
  detail::KeyTypeOfT<Input> maxKey, Output& output);

template <typename Element, typename ElementIdType>
DenseArrayKeys<Element, ElementIdType> ScatterDense(
  const Element* elements, ElementIdType numberOfElements, Element* scattered);
template <typename Element, typename ElementIdType>
DenseArrayKeys<Element, ElementIdType> ScatterDense(const Element* elements,
  ElementIdType numberOfElements, detail::ElementKeyOf<Element> minKey,
  detail::ElementKeyOf<Element> maxKey, Element* scattered);

template <typename Input, typename Output>
SparseKeysOf<Input> ScatterSparse(const Input& input, Output& output);
template <typename Element, typename ElementIdType>
SparseArrayKeys<Element, ElementIdType> ScatterSparse(
  const Element* elements, ElementIdType numberOfElements, Element* scattered);
 
//------------------------------------------------------------------------------
// ForEachKeyRange(), Reduce() and Group(): the elements of every key are processed.

template <typename TKeys, typename Output, typename Functor, typename... Args>
void ForEachKeyRange(const TKeys& keys, Output&& output, Functor& functor, Args... args);
 
//------------------------------------------------------------------------------
// Reduce(): the surviving elements of every key, e.g., the faces used once.

template <typename TKeys>
class ReducedKeys : public TKeys
{
};

template <typename TKeys, typename Output, typename Functor>
ReducedKeys<TKeys> Reduce(const TKeys& keys, Output&& output, Functor&& functor);

template <typename TKeys, typename Output, typename = std::enable_if_t<!std::is_pointer_v<Output>>>
typename TKeys::ElementIdType Compact(
  const TKeys& keys, const ReducedKeys<TKeys>& reduced, const Output& input, Output& output);
template <typename TKeys, typename Element>
typename TKeys::ElementIdType Compact(
  const TKeys& keys, const ReducedKeys<TKeys>& reduced, const Element* input, Element* output);

struct SortUnique
{
  template <typename Element, typename KeyIdType, typename ElementIdType>
  void operator()(Element* elements, KeyIdType beginKeyId, KeyIdType endKeyId,
    const ElementIdType* offsets, ElementIdType* counts) const;
};
 
//------------------------------------------------------------------------------
// Group(): the groups of equal elements of every key, e.g., the faces shared by cells.

template <typename TKeys>
class GroupedElements
{
public:
  using ElementIdType = typename TKeys::ElementIdType;
 
  ElementIdType GetNumberOfGroups() const { return this->NumberOfGroups; }

  ElementIdType GetGroupOffset(ElementIdType group) const { return this->GroupOffsets[group]; }

  const ElementIdType* GetGroupOffsets() const { return this->GroupOffsets.get(); }
 
  ElementIdType GetGroupSize(ElementIdType group) const
  {
    return this->GroupOffsets[group + 1] - this->GroupOffsets[group];
  }

  void Reset()
  {
    this->NumberOfGroups = 0;
    this->GroupOffsets.reset();
  }
 
private:
  friend struct detail::Grouper;
 
  ElementIdType NumberOfGroups = 0;
  std::unique_ptr<ElementIdType[]> GroupOffsets; // NumberOfGroups + 1
};

template <typename TKeys>
struct Grouping
{
  GroupedElements<TKeys> Groups;
  ReducedKeys<TKeys> Keys;
};

template <typename TKeys, typename Output, typename Functor>
Grouping<TKeys> Group(const TKeys& keys, Output&& output, Functor&& functor);

template <typename TKeys, typename Output, typename = std::enable_if_t<!std::is_pointer_v<Output>>>
typename TKeys::ElementIdType Compact(
  const GroupedElements<TKeys>& groups, const Output& input, Output& output);
template <typename TKeys, typename Element>
typename TKeys::ElementIdType Compact(
  const GroupedElements<TKeys>& groups, const Element* input, Element* output);

struct SortGroup
{
  template <typename Element, typename KeyIdType, typename ElementIdType>
  void operator()(Element* elements, KeyIdType beginKeyId, KeyIdType endKeyId,
    const ElementIdType* offsets, uint8_t* groupStarts) const;
};
 
VTK_ABI_NAMESPACE_END
} // namespace keys
} // namespace vtk
 
#include "vtkKeys.txx"
 
#endif
// VTK-HeaderTest-Exclude: vtkKeys.h