% -*- latex -*-

\chapter{Worklet Type Reference}
\label{chap:WorkletTypeReference}

\index{worklet|(}
\index{worklet!creating|(}

\index{worklet types|(}

Chapter \ref{chap:SimpleWorklets} introduces worklets and provides a simple example of creating a worklet to run an algorithm on a many core device.
Different operations in visualization can have different data access patterns, perform different execution flow, and require different provisions.
\VTKm manages these different accesses, execution, and provisions by grouping visualization algorithms into common classes of operation and supporting each class with its own worklet type.

Each worklet type has a generic superclass that worklets of that particular type must inherit.
This makes the type of the worklet easy to identify.
The following list describes each worklet type provided by \VTKm and the superclass that supports it.

\begin{description}
\item[Field Map]
  \index{worklet types!field map} \index{field map worklet}
  A worklet deriving \vtkmworklet{WorkletMapField} performs a basic mapping operation that applies a function (the operator in the worklet) on all the field values at a single point or cell and creates a new field value at that same location.
  Although the intention is to operate on some variable over a mesh, a \textidentifier{WorkletMapField} may actually be applied to any array.
  Thus, a field map can be used as a basic \index{map}map operation.

\item[Topology Map]
  \index{worklet types!topology map} \index{topology map worklet}
  A worklet deriving \vtkmworklet{WorkletMapTopology} or one of its child classes performs a mapping operation that applies a function (the operator in the worklet) on all elements of a particular type (such as points or cells) and creates a new field for those elements.
  The basic operation is similar to a field map except that in addition to access fields being mapped on, the worklet operation also has access to incident fields.

  There are multiple convenience classes available for the most common types of topology mapping.
  \index{worklet types!visit cells} \index{visit cells worklet} \vtkmworklet{WorkletVisitCellsWithPoints} calls the worklet operation for each cell and makes every incident point available.
  This type of map also has access to cell structures and can interpolate point fields.
  \index{worklet types!visit points} \index{visit points worklet} Likewise, \vtkmworklet{WorkletVisitPointsWithCells} calls the worklet operation for each point and makes every incident cell available.

\item[Point Neighborhood]
  \index{worklet types!point neighborhood} \index{point neighborhood worklet}
  A worklet deriving from \vtkmworklet{WorkletPointNeighborhood} performs a mapping operation that applies a function (the operator in the worklet) on all points of a structured mesh.
  The basic operation is similar to a field map except that in addition to having access to the point being operated on, you can get the field values of nearby points within a neighborhood of a given size.
  Point neighborhood worklets can only applied to structured cell sets.

\item[Reduce by Key]
  \index{worklet types!reduce by key} \index{reduce by key worklet}
  A worklet deriving \vtkmworklet{WorkletReduceByKey} operates on an array of keys and one or more associated arrays of values.
  When a reduce by key worklet is invoked, all identical keys are collected and the worklet is called once for each unique key.
  Each worklet invocation is given a \Veclike containing all values associated with the unique key.
  Reduce by key worklets are very useful for combining like items such as shared topology elements or coincident points.
\end{description}

The remainder of this chapter provides details on how to create worklets of each type.
It is also possible to create new worklet types in \VTKm.
This is an advanced topic covered in Chapter~\ref{chap:NewWorkletTypes}.


\newcommand{\commoncontrolsignaturetags}{
\item[\sigtag{WholeArrayIn}]
  This tag represents an array where all entries can be read by every worklet invocation.
  A \sigtag{WholeArrayIn} argument expects an \textidentifier{ArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  An array portal capable of reading from any place in the array is given to the worklet.
  Whole arrays are discussed in detail in Section~\ref{sec:WholeArrays} starting on page~\pageref{sec:WholeArrays}.

\item[\sigtag{WholeArrayOut}]
  This tag represents an array where any entry can be written by any worklet invocation.
  A \sigtag{WholeArrayOut} argument expects an \textidentifier{ArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  An array portal capable of writing to any place in the array is given to the worklet.
  Developers should take care when using writable whole arrays as introducing race conditions is possible.
  Whole arrays are discussed in detail in Section~\ref{sec:WholeArrays} starting on page~\pageref{sec:WholeArrays}.

\item[\sigtag{WholeArrayInOut}]
  This tag represents an array where any entry can be read or written by any worklet invocation.
  A \sigtag{WholeArrayInOut} argument expects an \textidentifier{ArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  An array portal capable of reading from or writing to any place in the array is given to the worklet.
  Developers should take care when using writable whole arrays as introducing race conditions is possible.
  Whole arrays are discussed in detail in Section~\ref{sec:WholeArrays} starting on page~\pageref{sec:WholeArrays}.

\item[\sigtag{AtomicArrayInOut}]
  This tag represents an array where any entry can be read or written by any worklet invocation.
  A \sigtag{AtomicArrayInOut} argument expects an \textidentifier{ArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  A \vtkmexec{AtomicArray} object capable of performing atomic operations to the entries in the array is given to the worklet.
  Atomic arrays can help avoid race conditions but can slow down the running of a parallel algorithm.
  Atomic arrays are discussed in detail in Section~\ref{sec:AtomicArrays} starting on page~\pageref{sec:AtomicArrays}.

\item[\sigtag{WholeCellSetIn}]
  This tag represents the connectivity of a cell set.
  A \sigtag{WholeCellSetIn} argument expects a \vtkmcont{CellSet} in the associated parameter of the \textidentifier{Invoker}.
  A connectivity object capable of finding elements of one type that are incident on elements of a different type.
  Accessing whole cell set connectivity is discussed in detail in Section~\ref{sec:WholeCellSets}.

\item[\sigtag{ExecObject}]
  This tag represents an execution object that is passed directly from the control environment to the worklet.
  A \sigtag{ExecObject} argument expects a subclass of \vtkmexec{ExecutionObjectBase}.
  Subclasses of \textidentifier{ExecutionObjectBase} behave like a factory for objects that work on particular devices.
  They do this by implementing a \classmember*{ExecutionObjectBase}{PrepareForExecution} method that takes a device adapter tag and returns an object that works on that device.
  That device-specific object is passed directly to the worklet.
  Execution objects are discussed in detail in Section~\ref{chap:ExecutionObjects} starting on page~\pageref{chap:ExecutionObjects}.}

\newcommand{\numericexecutionsignaturetags}{
\item[\sigtagnum{1}, \sigtagnum{2},$\ldots$]
  These reference the corresponding parameter in the \controlsignature.
}

\newcommand{\commonexecutionsignaturetags}{
\item[\sigtag{WorkIndex}]
  This tag produces a \vtkm{Id} that uniquely identifies the invocation of the worklet.
\item[\sigtag{VisitIndex}]
  This tag produces a \vtkm{IdComponent} that uniquely identifies when multiple worklet invocations operate on the same input item, which can happen when defining a worklet with scatter (as described in Section~\ref{sec:WorkletScatter}).
\item[\sigtag{InputIndex}]
  This tag produces a \vtkm{Id} that identifies the index of the input element, which can differ from the \sigtag{WorkIndex} in a worklet with a scatter (as described in Section~\ref{sec:WorkletScatter}).
\item[\sigtag{OutputIndex}]
  This tag produces a \vtkm{Id} that identifies the index of the output element. (This is generally the same as \sigtag{WorkIndex}.)
\item[\sigtag{ThreadIndices}]
  This tag produces an internal object that manages indices and other metadata of the current thread. Thread indices objects are described in Section~\ref{sec:ThreadIndices}, but most users can get the information they need through other signature tags.
}

\section{Field Map}

\index{worklet types!field map|(}
\index{field map worklet|(}
\index{map field|(}

A worklet deriving \vtkmworklet{WorkletMapField} performs a basic mapping operation that applies a function (the operator in the worklet) on all the field values at a single point or cell and creates a new field value at that same location.
Although the intention is to operate on some variable over the mesh, a \textidentifier{WorkletMapField} can actually be applied to any array.

A field map worklet supports the following tags in the parameters of its
\controlsignature.

\begin{description}
\item[\sigtag{FieldIn}]
  This tag represents an input field.
  A \sigtag{FieldIn} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a single value out of this array.

  The worklet's \inputdomain can be set to a \sigtag{FieldIn} argument. In
  this case, the input domain will be the size of the array.

\item[\sigtag{FieldOut}]
  This tag represents an output field.
  A \sigtag{FieldOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

\item[\sigtag{FieldInOut}]
  This tag represents field that is both an input and an output.
  A \sigtag{FieldInOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a single value out of this array, which is replaced by the resulting value after the worklet completes.

  The worklet's \inputdomain can be set to a \sigtag{FieldInOut} argument. In
  this case, the input domain will be the size of the array.

  \commoncontrolsignaturetags
\end{description}

A field map worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

  \commonexecutionsignaturetags
\end{description}

Field maps most commonly perform basic calculator arithmetic, as demonstrated in the following example.

\vtkmlisting[ex:UseWorkletMapField]{Implementation and use of a field map worklet.}{UseWorkletMapField.cxx}

Although simple, the \textidentifier{WorkletMapField} worklet type can be used (and abused) as a general parallel-for/scheduling mechanism.
In particular, the \sigtag{WorkIndex} execution signature tag can be used to get a unique index, the \textsignature{WholeArray}* tags can be used to get random access to arrays, and the \sigtag{ExecObject} control signature tag can be used to pass execution objects directly to the worklet.
Whole arrays and execution objects are talked about in more detail in Chapters \ref{chap:Globals} and \ref{chap:ExecutionObjects}, respectively, in more detail, but here is a simple example that uses the random access of \sigtag{WholeArrayOut} to make a worklet that copies an array in reverse order.

\vtkmlisting[ex:WholeArray]{Leveraging field maps and field maps for general processing.}{RandomArrayAccess.cxx}

\index{map field|)}
\index{field map worklet|)}
\index{worklet types!field map|)}

\section{Topology Map}
\label{sec:TopologyMaps}

A topology map performs a mapping that it applies a function (the operator in the worklet) on all the elements of a \textidentifier{DataSet} of a particular type (i.e. point, edge, face, or cell).
While operating on the element, the worklet has access to data from all incident elements of another type.

There are several versions of topology maps that differ in what type of element being mapped from and what type of element being mapped to.
The subsequent sections describe these different variations of the topology maps.

\subsection{Visit Cells with Points}
\label{sec:WorkletVistCellsWithPoint}

\index{worklet types!visit cells|(}
\index{visit cells worklet|(}

A worklet deriving \vtkmworklet{WorkletVisitCellsWithPoints} performs a mapping operation that applies a function (the operator in the worklet) on all the cells of a \textidentifier{DataSet}.
While operating on the cell, the worklet has access to fields associated both with the cell and with all incident points.
Additionally, the worklet can get information about the structure of the cell and can perform operations like interpolation on it.

A visit cells with points worklet supports the following tags in the parameters of its \controlsignature.

\begin{description}
\item[\sigtag{CellSetIn}]
  This tag represents the cell set that defines the collection of cells the map will operate on.
  A \sigtag{CellSetIn} argument expects a \textidentifier{CellSet} subclass or an \textidentifier{UnknownCellSet} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a cell shape tag.
  (Cell shapes and the operations you can do with cells are discussed in Chapter \ref{chap:WorkingWithCells}.)

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's \inputdomain must be set to this argument.

\item[\sigtag{FieldInPoint}]
  This tag represents an input field that is associated with the points.
  A \sigtag{FieldInPoint} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of points.

  Each invocation of the worklet gets a \Veclike object containing the field values for all the points incident with the cell being visited.
  The order of the entries is consistent with the defined order of the vertices for the visited cell's shape.
  If the field is a vector field, then the provided object is a Vec of Vecs.

\item[\sigtag{FieldInCell}]
  This tag represents an input field that is associated with the cells.
  A \sigtag{FieldInCell} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of cells.
  Each invocation of the worklet gets a single value out of this array.

\item[\sigtag{FieldOutCell}]
  This tag represents an output field, which is necessarily associated with cells.
  A \sigtag{FieldOutCell} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

  \sigtag{FieldOut} is an alias for \sigtag{FieldOutCell} (since output arrays can only be defined on cells).

\item[\sigtag{FieldInOutCell}]
  This tag represents field that is both an input and an output, which is necessarily associated with cells.
  A \sigtag{FieldInOutCell} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a single value out of this array, which is replaced by the resulting value after the worklet completes.

  \sigtag{FieldInOut} is an alias for \sigtag{FieldInOutCell} (since output arrays can only be defined on cells).

  \commoncontrolsignaturetags
\end{description}

A visit cells with points worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{CellShape}]
  This tag produces a shape tag corresponding to the shape of the visited cell.
  (Cell shapes and the operations you can do with cells are discussed in Chapter \ref{chap:WorkingWithCells}.)
  This is the same value that gets provided if you reference the \textsignature{CellSetIn} parameter.

\item[\sigtag{PointCount}]
  This tag produces a \vtkm{IdComponent} equal to the number of points incident on the cell being visited.
  The Vecs provided from a \textsignature{FieldInPoint} parameter will be the same size as \sigtag{PointCount}.

\item[\sigtag{PointIndices}]
  This tag produces a \Veclike object of \vtkm{Id}s giving the indices for all incident points.
  Like values from a \textsignature{FieldInPoint} parameter, the order of the entries is consistent with the defined order of the vertices for the visited cell's shape.

  \commonexecutionsignaturetags
\end{description}

Point to cell field maps are a powerful construct that allow you to interpolate point fields throughout the space of the data set.
See Chapter \ref{chap:WorkingWithCells} for a description on how to work with the cell information provided to the worklet.
The following example provides a simple demonstration that finds the geometric center of each cell by interpolating the point coordinates to the cell centers.

\vtkmlisting[ex:UseWorkletVisitCellsWithPoints]{Implementation and use of a visit cells with points worklet.}{UseWorkletVisitCellsWithPoints.cxx}

\index{visit cells worklet|)}
\index{worklet types!visit cells|)}

\subsection{Visit Points with Cells}
\label{sec:WorkletVisitPointsWithCells}

\index{worklet types!visit points|(}
\index{visit points worklet|(}

A worklet deriving \vtkmworklet{WorkletVisitPointsWithCells} performs a mapping operation that applies a function (the operator in the worklet) on all the points of a \textidentifier{DataSet}.
While operating on the point, the worklet has access to fields associated both with the point and with all incident cells.

A visit points with cells worklet supports the following tags in the parameters of its \controlsignature.

\begin{description}
\item[\sigtag{CellSetIn}]
  This tag represents the cell set that defines the collection of points the map will operate on.
  A \sigtag{CellSetIn} argument expects a \textidentifier{CellSet} subclass or an \textidentifier{UnknownCellSet} in the associated parameter of the \textidentifier{Invoker}.

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's \inputdomain must be set to this argument.

\item[\sigtag{FieldInCell}]
  This tag represents an input field that is associated with the cells.
  A \sigtag{FieldInCell} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of cells.

  Each invocation of the worklet gets a \Veclike object containing the field values for all the cells incident with the point being visited.
  The order of the entries is arbitrary but will be consistent with the values of all other \sigtag{FieldInCell} arguments for the same worklet invocation.
  If the field is a vector field, then the provided object is a Vec of Vecs.

\item[\sigtag{FieldInPoint}]
  This tag represents an input field that is associated with the points.
  A \sigtag{FieldInPoint} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of points.
  Each invocation of the worklet gets a single value out of this array.

\item[\sigtag{FieldOutPoint}]
  This tag represents an output field, which is necessarily associated with points.
  A \sigtag{FieldOutPoint} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

  \sigtag{FieldOut} is an alias for \sigtag{FieldOutPoint} (since output arrays can only be defined on points).

\item[\sigtag{FieldInOutPoint}]
  This tag represents field that is both an input and an output, which is necessarily associated with points.
  A \sigtag{FieldInOutPoint} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a single value out of this array, which is replaced by the resulting value after the worklet completes.

  \sigtag{FieldInOut} is an alias for \sigtag{FieldInOutPoint} (since output arrays can only be defined on points).

  \commoncontrolsignaturetags
\end{description}

A visit points with cells worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{CellCount}]
  This tag produces a \vtkm{IdComponent} equal to the number of cells incident on the point being visited.
  The Vecs provided from a \textsignature{FieldInCell} parameter will be the same size as \sigtag{CellCount}.

\item[\sigtag{CellIndices}]
  This tag produces a \Veclike object of \vtkm{Id}s giving the indices for all incident cells.
  The order of the entries is arbitrary but will be consistent with the values of all other \textsignature{FieldInCell} arguments for the same worklet invocation.

  \commonexecutionsignaturetags
\end{description}

Cell to point field maps are typically used for converting fields associated with cells to points so that they can be interpolated.
The following example does a simple averaging, but you can also implement other strategies such as a volume weighted average.

\vtkmlisting{Implementation and use of a visit points with cells worklet.}{UseWorkletVisitPointsWithCells.cxx}

\index{visit points worklet|)}
\index{worklet types!visit points|)}

\subsection{General Topology Maps}
\label{sec:WorkletMapTopology}

\index{worklet types!topology map|(}
\index{topology map worklet|(}
\index{map topology|(}

A worklet deriving \vtkmworklet{WorkletMapTopology} performs a mapping operation that applies a function (the operator in the worklet) on all the elements of a specified type from a \textidentifier{DataSet}.
While operating on each element, the worklet has access to fields associated both with that element and with all incident elements of a different specified type.

The \textidentifier{WorkletMapTopology} class is a template with two template parameters.
The first template parameter specifies the ``visit'' topology element, and the second parameter specifies the ``incident'' topology element.
The worklet is scheduled such that each instance is associated with a particular ``visit'' topology element and has access to ``incident'' topology elements.

\index{topology element tag|(}
\index{tag!topology element|(}

These visit and incident topology elements are specified with topology element tags, which are defined in the \vtkmheader{vtkm}{TopologyElementTag.h} header file.
The available topology element tags are \vtkm{TopologyElementTagCell}, \vtkm{TopologyElementTagPoint}, \vtkm{TopologyElementTagEdge}, and \vtkm{TopologyElementTagFace}, which represent the cell, point, edge, and face elements, respectively.

\index{topology element tag|)}
\index{tag!topology element|)}

\textidentifier{WorkletMapTopology} is a generic form of a topology map, and it can perform identically to the aforementioned forms of topology map with the correct template parameters.
For example,
\begin{quote}
  \vtkmworklet{WorkletMapTopology}\tparams{%
  \vtkm{TopologyElementTagCell}, %
  \vtkm{TopologyElementTagPoint}}
\end{quote}
is equivalent to the \vtkmworklet{WorkletVisitCellsWithPoints} class except the signature tags have different names.
The names used in the specific topology map superclasses (such as \textidentifier{WorkletVisitCellsWithPoints}) tend to be easier to read and are thus preferable.
However, the generic \textidentifier{WorkletMapTopology} is available for topology combinations without a specific superclass or to support more general mappings in a worklet.

The general topology map worklet supports the following tags in the parameters of its \controlsignature, which are equivalent to tags in the other topology maps but with different (more general) names.

\begin{description}
\item[\sigtag{CellSetIn}]
  This tag represents the cell set that defines the collection of elements the map will operate on.
  A \sigtag{CellSetIn} argument expects a \textidentifier{CellSet} subclass or an \textidentifier{UnknownCellSet} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a cell shape tag.
  (Cell shapes and the operations you can do with cells are discussed in Chapter \ref{chap:WorkingWithCells}.)

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's \inputdomain must be set to this argument.

\item[\sigtag{FieldInVisit}]
  This tag represents an input field that is associated with the ``visit'' element.
  A \sigtag{FieldInVisit} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of cells.
  Each invocation of the worklet gets a single value out of this array.

\item[\sigtag{FieldInIncident}]
  This tag represents an input field that is associated with the ``incident'' elements.
  A \sigtag{FieldInIncident} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of ``incident'' elements.

  Each invocation of the worklet gets a \Veclike object containing the field values for all the ``incident'' elements incident with the ``visit'' element being visited.
  If the field is a vector field, then the provided object is a \textidentifier{Vec} of \textidentifier{Vec}s.

\item[\sigtag{FieldOut}]
  This tag represents an output field, which is necessarily associated with ``visit'' elements.
  A \sigtag{FieldOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

\item[\sigtag{FieldInOut}]
  This tag represents field that is both an input and an output, which is necessarily associated with ``visit'' elements.
  A \sigtag{FieldInOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a single value out of this array, which is replaced by the resulting value after the worklet completes.

  \commoncontrolsignaturetags
\end{description}

A general topology map worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{CellShape}]
  This tag produces a shape tag corresponding to the shape of the visited element.
  (Cell shapes and the operations you can do with cells are discussed in Chapter \ref{chap:WorkingWithCells}.)
  This is the same value that gets provided if you reference the \textsignature{CellSetIn} parameter.

  If the ``visit'' element is cells, the \sigtag{CellShape} clearly will match the shape of each cell.
  Other elements will have shapes to match their structures.
  Points have vertex shapes, edges have line shapes, and faces have some type of polygonal shape.

\item[\sigtag{IncidentElementCount}]
  This tag produces a \vtkm{IdComponent} equal to the number of elements incident on the element being visited.
  The Vecs provided from a \textsignature{FieldInIncident} parameter will be the same size as \sigtag{IncidentElementCount}.

\item[\sigtag{IncidentElementIndices}]
  This tag produces a \Veclike object of \vtkm{Id}s giving the indices for all incident elements.
  The order of the entries is consistent with the values of all other \textsignature{FieldInIncident} arguments for the same worklet invocation.

  \commonexecutionsignaturetags
\end{description}

\index{map topology|)}
\index{topology map worklet|)}
\index{worklet types!topology map|)}

\section{Point Neighborhood}
\label{sec:WorkletPointNeighborhood}

\index{worklet types!point neighborhood|(}
\index{point neighborhood worklet|(}
\index{neighborhood worklet|(}
\index{map point neighborhood|(}

A worklet deriving \vtkmworklet{WorkletPointNeighborhood} performs a mapping operation that applies a function (the operator in the worklet) on all the points of a \textidentifier{DataSet}.
While operating on the point, the worklet has access to field values on nearby points within a neighborhood.

A point neighborhood worklet supports the following tags in the parameters of its \controlsignature.

\begin{description}
\item[\sigtag{CellSetIn}]
  This tag represents the cell set that defines the collection of points the map will operate on.
  A \sigtag{CellSetIn} argument expects a \vtkmcont{CellSetStructured} object in the associated parameter of the \textidentifier{Invoker}.
  The object could also be stored in an \textidentifier{UnknownCellSet}, but it is an error to use any object other than \textidentifier{CellSetStructured}.

  There must be exactly one \sigtag{CellSetIn} argument, and the worklet's \inputdomain must be set to this argument.

\item[\sigtag{FieldIn}]
  This tag represents an input field that is associated with the points.
  A \sigtag{FieldIn} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The size of the array must be exactly the number of points.
  Each invocation of the worklet gets a single value out of this array.

\item[\sigtag{FieldInNeighborhood}]
  This tag represents an input field that is associated with the points.
  A \sigtag{FieldInNeighborhood} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the \textidentifier{Invoker}.
  The size of the array must be exactly the number of points.

  What differentiates \sigtag{FieldInNeighborhood} from \sigtag{FieldIn} is that \sigtag{FieldInNeighborhood} allows the worklet function to access the field value at the point it is visiting and the field values in the neighborhood around it.
  Thus, instead of getting a single value out of the array, each invocation of the worklet gets a \vtkmexec{FieldNeighborhood} object.
  \textidentifier{FieldNeighborhood} objects are described in the Neighborhood Information section starting on page \pageref{sec:NeighborhoodInformation}.

\item[\sigtag{FieldOut}]
  This tag represents an output field, which is necessarily associated with points.
  A \sigtag{FieldOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

\item[\sigtag{FieldInOut}]
  This tag represents field that is both an input and an output, which is necessarily associated with points.
  A \sigtag{FieldInOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  Each invocation of the worklet gets a single value out of this array, which is replaced by the resulting value after the worklet completes.

  \commoncontrolsignaturetags
\end{description}

A point neighborhood worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{Boundary}]
  This tag produces a \vtkmexecarg{BoundaryState} object, which provides information about where the local neighborhood is in relationship to the full mesh.
  \textidentifier{BoundaryState} objects are described in the Neighborhood Information section starting on page \pageref{sec:NeighborhoodInformation}.

  \commonexecutionsignaturetags
\end{description}

\subsection{Neighborhood Information}
\label{sec:NeighborhoodInformation}

As stated earlier in this section, what makes a \textidentifier{WorkletPointNeighborhood} worklet special is its ability to get field information in a neighborhood surrounding a point rather than just the point itself.
This is done using the special \sigtag{FieldInNeighborhood} \controlsignature tag.
When you use this tag, rather than getting the single field value for the point, you get a \vtkmexec{FieldNeighborhood} object.

The \textidentifier{FieldNeighborhood} class (which has a single template argument of the array portal type values are stored in) contains a \classmember*{FieldNeighborhood}{Get} method that retrieves a field value relative to the local neighborhood.
\classmember{FieldNeighborhood}{Get} takes the $i$, $j$, $k$ index of the point with respect to the local point.
So, calling \classmember{FieldNeighborhood}{Get}\textcode{(0,0,0)} retrieves at the point being visited.
Likewise, \classmember*{FieldNeighborhood}{Get}\textcode{(-1,0,0)} gets the value to the ``left'' of the point visited and \classmember*{FieldNeighborhood}{Get}\textcode{(1,0,0)} gets the value to the ``right.''
\classmember{FieldNeighborhood}{Get} is overloaded to accept the index as either three separate \vtkm{IdComponent} values or a single \vtkm{Vec}\tparams{\vtkm{IdComponent},3}.

\vtkmlisting{Retrieve neighborhood field value.}{GetNeighborhoodFieldValue.cxx}

When performing operations on a neighborhood within the mesh, it is often important to know whether the expected neighborhood is contained completely within the mesh or whether the neighborhood extends beyond the borders of the mesh.
This can be queried using a \vtkmexec{BoundaryState} object, which is provided when a \sigtag{Boundary} tag is listed in the \executionsignature.

Generally, \textidentifier{BoundaryState} allows you to specify the size of the neighborhood at runtime.
The neighborhood size is specified by a \index{neighborhood worklet!radius}\keyterm{radius}.
The radius specifies the number of items in each direction the neighborhood extends.
So, for example, a point neighborhood with radius 1 would contain a $3\times3\times3$ neighborhood centered around the point.
Likewise, a point neighborhood with radius 2 would contain a $5\times5\times5$ neighborhood centered around the point.
\textidentifier{BoundaryState} provides several methods to determine if the neighborhood is contained in the mesh.

\begin{description}
\item[\classmember*{BoundaryState}{MinNeighborIndices}]
  Given a radius for the neighborhood, returns a \vtkm{Vec}\tparams{\vtkm{IdComponent},3} for the ``lower left'' (minimum) index.
  If the visited point is in the middle of the mesh, the returned triplet is the negative radius for all components.
  But if the visited point is near the mesh boundary, then the minimum index will be clipped.

  For example, if the visited point is at $[5,5,5]$ and \classmember*{BoundaryState}{MinNeighborIndices}\textcode{(2)} is called, then $[-2,-2,-2]$ is returned.
  However, if the visited point is at $[0,1,2]$ and \classmember*{BoundaryState}{MinNeighborIndices}\textcode{(2)} is called, then $[0,-1,-2]$ is returned.

\item[\classmember*{BoundaryState}{MaxNeighborIndices}]
  Given a radius for the neighborhood, returns a \vtkm{Vec}\tparams{\vtkm{IdComponent},3} for the ``upper right'' (maximum) index.
  If the visited point is in the middle of the mesh, the returned triplet is the negative radius for all components.
  But if the visited point is near the mesh boundary, then the maximum index will be clipped.

  For example, if the visited point is at $[5,5,5]$ in a $10^3$ mesh and \classmember*{BoundaryState}{MaxNeighborIndices}\textcode{(2)} is called, then $[2,2,2]$ is returned.
  However, if the visited point is at $[7, 8, 9]$ in the same mesh and \classmember*{BoundaryState}{MaxNeighborIndices}\textcode{(2)} is called, then $[2, 1, 0]$ is returned.

\item[\classmember*{BoundaryState}{InBoundary}]
  Given a radius for the neighborhood, returns true if the neighborhood is contained completely within the boundary of the mesh, false otherwise.

\item[\classmember*{BoundaryState}{InXBoundary}]
  Given a radius for the neighborhood, returns false if the neighborhood extends beyond the edge of the mesh in the positive or negative $x$ (I) direction, true otherwise.

\item[\classmember*{BoundaryState}{InYBoundary}]
  Given a radius for the neighborhood, returns false if the neighborhood extends beyond the edge of the mesh in the positive or negative $y$ (J) direction, true otherwise.

\item[\classmember*{BoundaryState}{InZBoundary}]
  Given a radius for the neighborhood, returns false if the neighborhood extends beyond the edge of the mesh in the positive or negative $z$ (K) direction, true otherwise.
\end{description}

The \classmember{BoundaryState}{MinNeighborIndices} and \classmember{BoundaryState}{MaxNeighborIndices} are particularly useful for iterating over the valid portion of the neighborhood.

\vtkmlisting{Iterating over the valid portion of a neighborhood.}{GetNeighborhoodBoundary.cxx}

\subsection{Convolving Small Kernels}

A common use case for point neighborhood worklets is to convolve a small kernel with a structured mesh.
A very simple example of this is averaging out the values the values within some distance to the central point.
This has the effect of smoothing out the field (although smoothing filters with better properties exist).
The following example shows a worklet that applies this simple ``box'' averaging.

\vtkmlisting{Implementation and use of a point neighborhood worklet.}{UseWorkletPointNeighborhood.cxx}

\index{map point neighborhood|)}
\index{neighborhood worklet|)}
\index{point neighborhood worklet|)}
\index{worklet types!point neighborhood|)}

\section{Reduce by Key}
\label{sec:ReduceByKey}

\index{worklet types!reduce by key|(}
\index{reduce by key worklet|(}

A worklet deriving \vtkmworklet{WorkletReduceByKey} operates on an array of keys and one or more associated arrays of values.
When a reduce by key worklet is invoked, all identical keys are collected and the worklet is called once for each unique key.
Each worklet invocation is given a \Veclike containing all values associated with the unique key.
Reduce by key worklets are very useful for combining like items such as shared topology elements or coincident points.

\begin{figure}[htb]
  \centering
  \includegraphics{images/ReduceByKeys}
  \caption{The collection of values for a reduce by key worklet.}
  \label{fig:ReduceByKey}
\end{figure}

Figure~\ref{fig:ReduceByKey} show a pictorial representation of how \VTKm collects data for a reduce by key worklet.
All calls to a reduce by key worklet has exactly one array of keys.
The key array in this example has 4 unique keys: 0, 1, 2, 4.
These 4 unique keys will result in 4 calls to the worklet function.
This example also has 2 arrays of values associated with the keys.
(A reduce by keys worklet can have any number of values arrays.)

When the worklet is invoked, all these common keys will be collected with their associated values.
The parenthesis operator of the worklet will be called once per each unique key.
The worklet call will be given a \Veclike containing all values that have the key.

A reduce by key worklet supports the following tags in the parameters of its \controlsignature.

\begin{description}
\item[\sigtag{KeysIn}]
  This tag represents the input keys.
  A \sigtag{KeysIn} argument expects a \vtkmworklet{Keys} object in the associated parameter of the \textidentifier{Invoker}.
  The \textidentifier{Keys} object, which wraps around an \textidentifier{ArrayHandle} containing the keys and manages the auxiliary structures for collecting like keys, is described later in this section.

  Each invocation of the worklet gets a single unique key.

  A \textidentifier{WorkletReduceByKey} object must have exactly one \sigtag{KeysIn} parameter in its \controlsignature, and the \inputdomain must point to the \sigtag{KeysIn} parameter.

\item[\sigtag{ValuesIn}]
  This tag represents a set of input values that are associated with the keys.
  A \sigtag{ValuesIn} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The number of values in this array must be equal to the size of the array used with the \sigtag{KeysIn} argument.
  Each invocation of the worklet gets a \Veclike object containing all the values associated with the unique key.

\item[\sigtag{ValuesInOut}]
  This tag behaves the same as \sigtag{ValuesIn} except that the worklet may write values back into the \Veclike object, and these values will be placed back in their original locations in the array.
  Use of \sigtag{ValuesInOut} is rare.

\item[\sigtag{ValuesOut}]
  This tag behaves the same as \sigtag{ValuesInOut} except that the array is resized appropriately and no input values are passed to the worklet.
  As with \sigtag{ValuesInOut}, values the worklet writes to its \Veclike object get placed in the location of the original arrays.
  Use of \sigtag{ValuesOut} is rare.

\item[\sigtag{ReducedValuesOut}]
  This tag represents the resulting reduced values.
  A \sigtag{ReducedValuesOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The array is resized before scheduling begins, and each invocation of the worklet sets a single value in the array.

\item[\sigtag{ReducedValuesIn}]
  This tag represents input values that come from (typically) from a previous invocation of a reduce by key.
  A \sigtag{ReducedValuesOut} argument expects an \textidentifier{ArrayHandle} or an \textidentifier{UnknownArrayHandle} in the associated parameter of the \textidentifier{Invoker}.
  The number of values in the array must equal the number of \emph{unique} keys.

  A \sigtag{ReducedValuesIn} argument is usually used to pass reduced values from one invocation of a reduce by key worklet to another invocation of a reduced by key worklet such as in an algorithm that requires iterative steps.

\item[\sigtag{ReducedValuesInOut}]
  This tag behaves the same as \sigtag{ReducedValuesIn} except that the worklet may write values back into the array.
  Make sure that the associated parameter to the worklet operator is a reference so that the changed value gets written back to the array.

  \commoncontrolsignaturetags
\end{description}

A reduce by key worklet supports the following tags in the parameters of its \executionsignature.

\begin{description}
  \numericexecutionsignaturetags

\item[\sigtag{ValueCount}]
  This tag produces a \vtkm{IdComponent} that is equal to the number of times the key associated with this call to the worklet occurs in the input.
  This is the same size as the \Veclike objects provided by \sigtag{ValuesIn} arguments.

  \commonexecutionsignaturetags
\end{description}

As stated earlier, the reduce by key worklet is useful for collected like values.
To demonstrate the reduce by key worklet, we will create a simple mechanism to generate a \index{histogram}histogram in parallel.
(\VTKm comes with its own histogram implementation, but we create our own version here for a simple example.)
The way we can use the reduce by key worklet to compute a histogram is to first identify which bin of the histogram each value is in, and then use the bin identifiers as the keys to collect the information.
To help with this example, we will first create a helper class named \textcode{BinScalars} that helps us manage the bins.

\vtkmlisting{A helper class to manage histogram bins.}{BinScalars.cxx}

Using this helper class, we can easily create a simple map worklet that takes values, identifies a bin, and writes that result out to an array that can be used as keys.

\vtkmlisting{A simple map worklet to identify histogram bins, which will be used as keys.}{IdentifyBins.cxx}

Once you generate an array to be used as keys, you need to make a \vtkmworklet{Keys} object.
The \textidentifier{Keys} object is what will be passed to the \textidentifier{Invoker} for the argument associated with the \sigtag{KeysIn} \controlsignature tag.
This of course happens in the control environment after calling the \textidentifier{Invoker} for our worklet for generating the keys.

\vtkmlisting{Creating a \protect\vtkmworklet{Keys} object.}{CreateKeysObject.cxx}

Now that we have our keys, we are finally ready for our reduce by key worklet.
A histogram is simply a count of the number of elements in a bin.
In this case, we do not really need any values for the keys.
We just need the size of the bin, which can be identified with the internally calculated \sigtag{ValueCount}.

A complication we run into with this histogram filter is that it is possible for a bin to be empty.
If a bin is empty, there will be no key associated with that bin, and the \textidentifier{Invoker} will not call the worklet for that bin/key.
To manage this case, we have to initialize an array with 0's and then fill in the non-zero entities with our reduce by key worklet.
We can find the appropriate entry into the array by using the key, which is actually the bin identifier, which doubles as an index into the histogram.
The following example gives the implementation for the reduce by key worklet that fills in positive values of the histogram.

\vtkmlisting{A reduce by key worklet to write histogram bin counts.}{CountBins.cxx}

The previous example demonstrates the basic usage of the reduce by key worklet to count common keys.
A more common use case is to collect values associated with those keys, do an operation on those values, and provide a ``reduced'' value for each unique key.
The following example demonstrates such an operation by providing a worklet that finds the average of all values in a particular bin rather than counting them.

\vtkmlisting{A worklet that averages all values with a common key.}{AverageBins.cxx}

To complete the code required to average all values that fall into the same bin, the following example shows the full code required to invoke such a worklet.
Note that this example repeats much of the previous examples, but shows it in a more complete context.

\vtkmlisting{Using a reduce by key worklet to average values falling into the same bin.}{CombineSimilarValues.cxx}

\index{reduce by key worklet|)}
\index{worklet types!reduce by key|)}


\index{worklet types|)}


\index{worklet!creating|)}
\index{worklet|)}
