parallel scatter of elements by key, and operations on the elements of every key More...

#include "vtkABINamespace.h"
#include "vtkKeysTraits.h"
#include "vtkType.h"
#include <cstdint>
#include <memory>
#include <type_traits>
#include "vtkKeys.txx"

Include dependency graph for vtkKeys.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	vtk::keys::KeysBase< TKey, TElementId, TKeyId >
	What DenseKeys and SparseKeys share, and all that Reduce(), Group(), Compact() and ForEachKeyRange() use: the first element of every key id, the elements of key id k being at [GetOffset(k), GetOffset(k + 1)) of the Output. More...
class	vtk::keys::DenseKeys< TKey, TElementId >
	The dense keys of the elements, returned by ScatterDense(): every key of the key range [GetMinKey(), GetMaxKey()], present or not, whose key id is its position in the range. More...
class	vtk::keys::SparseKeys< TKey, TElementId >
	The sparse keys of the elements, returned by ScatterSparse(): the distinct keys, in increasing order of their operator<, whose key id is their position. More...
class	vtk::keys::ReducedKeys< TKeys >
	The keys of the surviving elements of Reduce(), or of the groups of Group(): the keys of the scattered keys, with the scanned survivors of every key id as offsets, i.e., the keys of the Output once compacted. More...
struct	vtk::keys::SortUnique
	The reduce functor of an array of elements that keeps one element of every set of equal ones, with operator< and operator==: it sorts the elements of every key, then applies std::unique(). More...
class	vtk::keys::GroupedElements< TKeys >
	The groups of equal elements of Group(), ordered by key: the elements of group g are at [GetGroupOffset(g), GetGroupOffset(g + 1)) of the grouped Output. More...
struct	vtk::keys::Grouping< TKeys >
	The result of Group(): the groups, and the keys of the groups, i.e., the groups of key id k are [Keys.GetOffset(k), Keys.GetOffset(k + 1)), which are also the keys of the first elements of the groups once compacted. More...
struct	vtk::keys::SortGroup
	The group functor of an array of elements, with operator< and operator!=: it sorts the elements of every key, then flags the elements that differ from the previous one. More...

Namespaces
namespace	vtk
	Specialization of tuple ranges and iterators for vtkAOSDataArrayTemplate.
namespace	vtk::keys
namespace	vtk::keys::detail

Typedefs
template<typename Input>
using	vtk::keys::DenseKeysOf = DenseKeys<detail::KeyTypeOfT<Input>, detail::ElementIdTypeOfT<Input>>
	The keys of the scatters of an input, with its KeyType and ElementIdType, and of an array.
template<typename Input>
using	vtk::keys::SparseKeysOf = SparseKeys<detail::KeyTypeOfT<Input>, detail::ElementIdTypeOfT<Input>>
template<typename Element, typename ElementIdType>
using	vtk::keys::DenseArrayKeys = DenseKeys<detail::ElementKeyOf<Element>, ElementIdType>
template<typename Element, typename ElementIdType>
using	vtk::keys::SparseArrayKeys = SparseKeys<detail::ElementKeyOf<Element>, ElementIdType>

Functions
template<typename InputMapper>
vtkIdType	vtk::keys::CountElements (const InputMapper &mapper)
	The number of elements of an InputMapper, without storing them, e.g., to choose its ElementIdType.
template<typename Input, typename Output>
DenseKeysOf< Input >	vtk::keys::ScatterDense (const Input &input, Output &output)
	Scatter the elements of an Input or an InputMapper to an Output by a counting sort over the key range, with the KeyType and ElementIdType of the input.
template<typename Input, typename Output>
DenseKeysOf< Input >	vtk::keys::ScatterDense (const Input &input, detail::KeyTypeOfT< Input > minKey, detail::KeyTypeOfT< Input > maxKey, Output &output)
template<typename Element, typename ElementIdType>
DenseArrayKeys< Element, ElementIdType >	vtk::keys::ScatterDense (const Element elements, ElementIdType numberOfElements, Element scattered)
	Scatter an array of elements, keyed by their GetKey() (Element concept), to scattered, which holds as many elements and does not overlap elements.
template<typename Element, typename ElementIdType>
DenseArrayKeys< Element, ElementIdType >	vtk::keys::ScatterDense (const Element elements, ElementIdType numberOfElements, detail::ElementKeyOf< Element > minKey, detail::ElementKeyOf< Element > maxKey, Element scattered)
template<typename Input, typename Output>
SparseKeysOf< Input >	vtk::keys::ScatterSparse (const Input &input, Output &output)
	Scatter the elements of an Input or an InputMapper, or an array of elements, to an Output by a parallel sort of their keys, for keys too sparse for ScatterDense().
template<typename Element, typename ElementIdType>
SparseArrayKeys< Element, ElementIdType >	vtk::keys::ScatterSparse (const Element elements, ElementIdType numberOfElements, Element scattered)
template<typename TKeys, typename Output, typename Functor, typename... Args>
void	vtk::keys::ForEachKeyRange (const TKeys &keys, Output &&output, Functor &functor, Args... args)
	Call functor(output, beginKeyId, endKeyId, offsets, args...) on disjoint ranges of key ids, concurrently, on the same functor, where the elements of key id k are [offsets[k], offsets[k + 1]) of the Output, for DenseKeys or SparseKeys.
template<typename TKeys, typename Output, typename Functor>
ReducedKeys< TKeys >	vtk::keys::Reduce (const TKeys &keys, Output &&output, Functor &&functor)
	Keep the surviving elements of every key of the Output at its front with a reduce functor called as functor(output, beginKeyId, endKeyId, offsets, counts), which writes the survivors of key id k to counts[k], see ForEachKeyRange().
template<typename TKeys, typename Output, typename = std::enable_if_t<!std::is_pointer_v<Output>>>
TKeys::ElementIdType	vtk::keys::Compact (const TKeys &keys, const ReducedKeys< TKeys > &reduced, const Output &input, Output &output)
	Copy the survivors of the reduced Output input contiguously into output, another Output that implements CopyData(), or arrays of elements.
template<typename TKeys, typename Element>
TKeys::ElementIdType	vtk::keys::Compact (const TKeys &keys, const ReducedKeys< TKeys > &reduced, const Element input, Element output)
template<typename TKeys, typename Output, typename Functor>
Grouping< TKeys >	vtk::keys::Group (const TKeys &keys, Output &&output, Functor &&functor)
	Group the equal elements of every key of the Output with a group functor called as functor(output, beginKeyId, endKeyId, offsets, groupStarts), which makes them contiguous and sets groupStarts[i] to 1 for every element i that differs from the previous one, see ForEachKeyRange().
template<typename TKeys, typename Output, typename = std::enable_if_t<!std::is_pointer_v<Output>>>
TKeys::ElementIdType	vtk::keys::Compact (const GroupedElements< TKeys > &groups, const Output &input, Output &output)
	Copy the first element of every group of the grouped Output input to output, another Output that implements CopyData(), or arrays of elements, so that group g is element g of output.
template<typename TKeys, typename Element>
TKeys::ElementIdType	vtk::keys::Compact (const GroupedElements< TKeys > &groups, const Element input, Element output)

Detailed Description

parallel scatter of elements by key, and operations on the elements of every key

vtk::keys moves elements, e.g., the faces of the cells of a mesh, into the order of their keys, e.g., their smallest point id, in parallel, so that the elements of a key are contiguous and processed together. As in Viskores, the data is separate from the operations:

ScatterDense() moves the elements to an Output in key order with a counting sort over the key range, for dense keys, e.g., point ids, and returns their DenseKeys: every key of the range, with the first element of every key;
ScatterSparse() does it with a sort, for sparse keys, e.g., hashes or pairs of point ids, and returns their SparseKeys: the distinct keys, with the first element of every key;
Reduce() keeps the surviving elements of every key at its front, e.g., the faces used once (a segmented compaction), and returns their ReducedKeys;
Group() makes the equal elements of every key contiguous, e.g., the faces shared by cells (a segmented run-length encoding), and returns their GroupedElements and the ReducedKeys of the groups;
Compact() copies the surviving elements, or the first element of every group, contiguously. Reduce() and Group() work on both kinds of keys, and only reorder the elements of every key, with a reduce or group functor called on ranges of key ids, see ForEachKeyRange(). A key id is the position of a key: in the key range for DenseKeys, among the distinct keys for SparseKeys. Every result holds its own arrays, and can be released alone.

A record is what the input is iterated over, e.g., a cell, and an element what is scattered: the record (1-1), or one of its elements (1-M), e.g., a face of a cell. The operations take objects of the concepts below, or arrays of elements that provide their key (Element concept).

// The unique edges, by their smallest point id.
std::vector<Edge> scattered(edges.size());
auto keys = vtk::keys::ScatterDense(
  edges.data(), numberOfEdges, 0, numberOfPoints - 1, scattered.data());
auto unique = vtk::keys::Reduce(keys, scattered.data(), vtk::keys::SortUnique{});
std::vector<Edge> uniqueEdges(unique.GetNumberOfElements());
vtk::keys::Compact(keys, unique, scattered.data(), uniqueEdges.data());
// The unique edges of key id k are at [unique.GetOffset(k), unique.GetOffset(k + 1)).

The dense scatter is the atomic histogram, prefix scan and atomic scatter of DP-Hash-Count, as Kokkos::BinSort, and the sparse one is the sort by key of Viskores's Keys. The operations process every key as a segment, as reduce_by_key in Thrust or WorkletReduceByKey in Viskores.

Warning: DenseKeys hold (maxKey - minKey) + 1 keys: use them for dense keys only. ScatterSparse() keeps the elements of every key in the order of their records. ScatterDense() fills every key from its front, as vtkStaticCellLinksTemplate: in the order of their records with the sequential backend, but in an order that depends on thread scheduling with the others, so that equal elements that carry different data can be ordered differently from one run to the next, unless the elements of every key are sorted, as vtkStaticCellLinksTemplate does.

See also: vtkStaticElementLocator vtkUnstructuredGridSides

Definition in file vtkKeys.h.

Classes

Namespaces

Typedefs

Functions

Detailed Description