m-group.tex.in

% -*- mode: LaTeX; -*- 
\chapter{Groups and tracing}
\label{chap:m:group}

Groups are a means to control certain execution aspects of
propagators and branchers. Tracing can be used for tracing
constraint propagation on variables as well as the general
execution of propagators and branchers. Groups are ultimately
linked to tracing, as the generated traces can be filtered
according to group membership.

\paragraph{Overview.}

\mbox{}\autoref{sec:m:group:prop} explains groups of propagators,
whereas \autoref{sec:m:group:branch} explains groups of
branchers. Tracing variables is explained in
\autoref{sec:m:group:vartrace} and general tracing in
\autoref{sec:m:group:trace}.  \autoref{sec:m:group:vartracers}
shows how variable tracers and \autoref{sec:m:group:tracers} shows
how general tracers (the objects that process trace information)
can be programmed.

\section{Propagator groups}
\label{sec:m:group:prop}

Each propagator belongs to exactly one \emph{propagator group} of
type \gecoderef[class]{PropagatorGroup}. When a propagator is
created, it is added to a group. Group membership of a propagator
remains stable during copying of spaces.

\paragraph{Adding propagators to groups.}

The following code creates a propagator group~\?pg?:
\begin{code}
PropagatorGroup pg;
\end{code}
A propagator can be added to the group~\?pg? by passing the group
as additional information adjoined to the \?home? information when
the propagator is posted. For example, when assuming that \?home?
refers to a space of type \?Space&?, then
\begin{code}
distinct(home(pg), x);
\end{code}
adds all propagators created by the constraint post function
\?distinct()? to the propagator group~\?pg?. Equivalently, one
can also use:
\begin{code}
distinct(pg(home), x);
\end{code}

If no propagator group is specified when a propagator is created,
then the propagator is added to the default propagator group
\?PropagatorGroup::def?. 

\paragraph{Moving propagators between groups.}

Propagators can be moved from one group to another. For
example, if \?pga? and~\?pgb? are propagator groups, then
\begin{code}
pga.move(home,pgb);
\end{code}
moves all propagators from group \?pgb? into group \?pga?. An
individual propagator~\?p? (of type \?Propagator&?) can also be
moved into a propagator group \?pg? by
\begin{code}
pg.move(home,p);
\end{code}

A propagator~\?p? can also be moved by giving its
identity \?p.id()?. For example, the following is equivalent to the
previous example:
\begin{code}
unsigned int id = p.id();
pg.move(home,id);
\end{code}
If no propagator with a given id exists, an exception of type
\gecoderef[class]{UnknownPropagator} is thrown.

In order to remove a propagator from its group or all propagators
of a group from their group, one can use the default group. For
example, if \?pg? is a propagator group, all of its propagators
are removed from \?pg? by
\begin{code}
PropagatorGroup::def.move(home,pg);
\end{code}

Move operations can be concatenated as they return their group. For
example, if \?pg? is a propagator group and \?p? and \?q? are
two propagators, then
\begin{code}
pg.move(p).move(q);
\end{code}
moves both~\?p? and~\?q? to \?pg?.

\paragraph{Operations on propagator groups.}

The number of propagators in a group can be computed by the
\?size()? member function. The following expression:
\begin{code}
pg.size(home)
\end{code}
evaluates to the number of propagators in the group \?pg?. Each
group has a unique identifier of type \?unsigned int? which can
be accessed by:
\begin{code}
pg.id()
\end{code}

One can iterate over all propagators in a group. For example,
\begin{code}
for (Propagators p(home,pg); p() ++p)
  std::cout << p.propagator.id() << ' ' << std::endl;
\end{code}
%>>
prints the unique identifier of each propagator contained in
group \?pg?. A propagator also provides access to the
group it belongs to, assume that \?p? is of type \?Propagator&?,
then
\begin{code}
p.group()
\end{code}
evaluates to the group \?p? belongs to.

The propagators of a group can be disabled and enabled. By
\begin{code}
pg.disable(home);
\end{code}
all propagators in \?pg? are disabled in that they are not any
longer performing any propagation (for more details on disabling
and enabling propagators, see also
\autoref{par:p:started:disable}). Similarly, propagators can be
enabled by
\begin{code}
pg.enable(home);
\end{code}

By default, enabling a disabled propagator will schedule the
propagator for execution if necessary. Hence, next time the
\?status()? function of the propagator's home space is executed,
the propagator will be executed again. It is also possible to
enable propagators in a group without scheduling them by:
\begin{code}
pg.enable(home,false);
\end{code}

All propagators in a group can be killed by
\begin{code}
pg.kill(home);
\end{code}

\paragraph{Groups for all propagators.}

For convenience, there is one special propagator group
\?PropagatorGroup::all? which refers to all propagators in a
space (one can think of it as the union of all propagator
groups). For example,
\begin{code}
PropagatorGroup::all.size(home)
\end{code}
evaluates to the number of all propagators in the space \?home?.


\section{Brancher groups}
\label{sec:m:group:branch}

Brancher groups contain branchers and each brancher belongs to
exactly one brancher group of type
\gecoderef[class]{BrancherGroup}. Brancher groups are 
similar to propagator groups as described in the previous
section:
\begin{itemize}
\item A brancher group \?bg? is created as follows:
\begin{smallcode}
BrancherGroup bg;
\end{smallcode}
\item  A brancher is added to the group \?bg? by passing the group
as additional information adjoined to the \?home? information when
the propagator is posted. For example, the brancher created by
\begin{smallcode}
branch(home(bg), x, INT_VAR_NONE(), INT_VAL_MIN());
\end{smallcode}
adds the newly created brancher created to the brancher group \?bg?. Equivalently, one
can also write \?bg(home)? instead of \?home(bg)?.
\item Brancher groups provide \?move()? functions for
  moving branchers into brancher groups that are analogous to the
  \?move()? functions for propagator groups.
\item
If no brancher group is specified,
branchers are added to the default group
\?BrancherGroup::def?. 
\item The number of branchers in a group can be computed by the
\?size()? member function. Each
group has a unique identifier of type \?unsigned int? which can
be accessed by \?bg.id()?.
\item One can iterate over all branchers in a group by using the
  iterator class \gecoderef[class]{Branchers}.
\item Each brancher provides access to the
group it belongs to, assume that \?b? is of type \?Brancher&?,
then 
\begin{smallcode}
b.group()
\end{smallcode}
evaluates to the group \?b? belongs to.
\item 
All branchers in a group can be killed by
\begin{smallcode}
bg.kill(home);
\end{smallcode}
\item There is one special brancher group
\?BrancherGroup::all? which refers to all branchers in a space.
\end{itemize}

\section{Variable tracing}
\label{sec:m:group:vartrace}

Gecode offers support to trace constraint propagation on an array
of variables. Variable tracing distinguishes two components: a
\emph{variable trace recorder} that records information about
relevant events during constraint propagation and a
\emph{variable tracer} that processes the recorded trace
information. A very simple variable tracer instance would just
print some textual information about recorded trace events. In
fact, Gecode offers default tracers for each variable type that
comes with Gecode that just print to an output stream of type
\?std::ostream?.

\subsection{Creating a variable trace recorder}

A variable trace recorder can be created by calling the
overloaded function \?trace()? together with an array of
variables. For example,
\begin{code}
trace(home, x);
\end{code}
creates a variable trace recorder for an array of variables \?x?.
Here, \?x? can be an array of integer, Boolean, set, or float
variables.

The variable trace recorder records the following events:
\begin{itemize}
\item A single \emph{init-event} providing some information about
  the variables for which the variable trace recorder will record
  information.
\item Each time the domain of a variable changes, a
  \emph{prune-event} is recorded.  The variable trace recorder
  provides information about which variable has been changed, how
  the variable has been changed, and on behalf of which entity (a
  propagator, a brancher, or a constraint post function
  performing pruning outside a propagator or brancher) the
  variable has been changed.
\item A \emph{fixpoint-event} is recorded when the space
  containing the variable trace recorder reaches a fixpoint,
  triggered by the execution of the space's \?status()? function.
\item A \emph{failure-event} is recorded when the space
  containing the variable trace recorder fails, triggered by the
  execution of the space's \?status()? function.
\item A \emph{done-event} that is recorded when all of the
  variable trace recorder's variables have been assigned and
  hence no further recording is needed. Note that this event can
  occur only once per space, however when using tracing during
  search the event might occur several times for different
  spaces.
\end{itemize}

The information that is recorded for each event depends on the
variable trace recorder's variable type.
 
\subsection{Default variable tracers}

The following paragraphs explain the information printed by the
default variable tracer for a given variable type.

\paragraph{Integer and Boolean variables.}

\begin{figure}
\begin{cmd}
SEND+MORE=MONEY
trace<Int>::init(id:0) slack: 100.00% (72 values)
trace<Int>::prune(id:0): [0] = [1..9] - {0} by post()
trace<Int>::prune(id:0): [4] = [1..9] - {0} by post()
trace<Int>::prune(id:0): [0] = 9 - {1..8} by propagator(id:2)
  ...
trace<Int>::fix(id:0) slack: 33.33% - 66.67%
  ...
trace<Int>::done(id:0) slack: 0%
        {9, 5, 6, 7, 1, 0, 8, 2}
trace<Int>::prune(id:0): [1] = [6..7] - {5} by brancher(id:1)
  ...
\end{cmd}
\caption{Abridged output for variable tracing Send More Money}
\label{fig:m:group:varsmm}
\end{figure}

Running the \gecoderef[example]{money} (see
\autoref{chap:m:started} and \autoref{chap:m:comfy} for the Send
More Money problem) with the commandline option \?-trace all?
(trace events to be recorded can be specified on the command
line, see \autoref{sec:m:driver:options}), the default variable
tracer for integer variables prints information about all trace
events to \?std::cerr?. An excerpt of the information printed is
shown in \autoref{fig:m:group:varsmm} where the variable trace recorder has
been posted with
\begin{code}
trace(home, le);
\end{code}
where \?le? is the array of eight variables used in Send More Money.

\tip{Enabling tracing with a commandline option}{
As mentioned above, the Gecode driver offers
also support for tracing. If \?opt? is an object of class
\gecoderef[class]{Options}, then adding the following code
\begin{code}
if (opt.trace() != 0)
  trace(home, x, opt.trace());
\end{code}
enables variable tracing if the \?-trace? commandline option is
used. The option takes \?all? as value for tracing all events as
well as a comma-separated list of \?init?, \?prune?, \?fix?,
\?fail?, and \?done?  for the respective event types. Also
general tracing can be controlled by this commandline option, see
\autoref{sec:m:group:trace}.  }

The output for each event starts with the information
\begin{cmd}
trace<Int>::
\end{code}
signaling that integer variables are being traced. After that,
the type of event is shown (\?init?, \?prune?, \?fix? for
fixpoint, \?fail? for failure, or \?done?). This is followed by information
about the identifier of the variable trace recorder (a variable
trace recorder is in fact a propagator and hence has a unique
identifier, see \autoref{sec:m:group:traceonoff}). If the
variable trace recorder belongs to a propagator group different
from the default propagator group, also the identifier of the
respective propagator group is printed.

The information for each event type is as follows:
\begin{itemize}
\item For an init-event, the total slack of all variables is
  shown where the slack of a variable is the number of values
  that must be removed before the variable becomes assigned to a
  single value. This information serves as a measure of how much
  propagation is still to be done.
\item For a prune-event, it is printed which variable has been
  pruned where the variable is identified by its position in the
  variable array of the variable trace recorder (for example, the
  first prune event in \autoref{fig:m:group:varsmm} shows \?[0]? as
  the variable at position~\?0? has been pruned).

  Next, the current domain of the variable is printed (that is,
  \?[1..9]?) and that the value \?0? has been pruned (that is,
  \?- {0}?).

  This is followed by information which entity has pruned the variable: a
  constraint post function (as is the case for the first two
  prune-events in \autoref{fig:m:group:varsmm}), a propagator (as is
  the case for the third prune-event in
  \autoref{fig:m:group:varsmm}), a brancher (as is the case for the
  last prune-event in \autoref{fig:m:group:varsmm}), or unknown. In
  case the prune-event has been caused by a propagator or
  brancher, their identifiers are shown. In case the propagator
  or brancher belong to a group different from the respective
  default group, also the group's identifier is shown. This is
  also true if the event has been caused by a constraint post
  function where some group information had been passed to the
  constraint post function.
\item For a fixpoint-event, the current slack and its change
  since the last fixpoint are shown.
\item For a failure-event, the current slack and its change since
  the last fixpoint are shown.
\item For a done-event, the current slack is shown
  (unsurprisingly, the slack is $0\%$ as all variables have been
  assigned).
\end{itemize}

The information printed by the default variable tracer for
Boolean variables is exactly the same as for integer variables.

Defining custom variable tracers is straightforward, this is
explained in \autoref{sec:m:group:vartracers}.

\paragraph{Set variables.}

The information printed for init-, fixpoint-, failure-, and
done-events for set variables is analogous to the information for
integer variables. The slack of a set variable here is defined as
the number of values that can be still included in or excluded
from the set variable (that is, it corresponds to
\?x.unknownSize()? where \?x? is a set variable of type
\gecoderef[class]{SetVar}).

For a prune-event, it is shown which values have been included in
the set and which values have been excluded from the set. For
example in
\begin{cmd}
trace<Set>::prune(id:0): [0] = {1..6} + {6..6} - {} by brancher(id:1)
\end{cmd}
the value \?6? has been included into the variable and no value
has been excluded whereas in
\begin{cmd}
trace<Set>::prune(id:0): [1] = {1..3} + {} - {4..6} by propagator(id:1)
\end{cmd}
the values \?4?, \?5?, and \?6? have been excluded. You can
try the \gecoderef[example]{hamming} example that supports tracing.

\paragraph{Float variables.}

For float variables, the slack is defined as the width of the
variable domain. The information printed for the events is
analogous to the information for integer variables, where for a
prune-event the interval containing the pruned values is printed.

For an example that supports tracing for float variables, you
might want to try the \gecoderef[example]{descartes-folium} example.

\subsection{Using trace filters}
\label{sec:m:group:filters}

The amount of prune-events that are generated during tracing can
be prohibitive and often one is only interested in events
generated by a subset of the propagators, branchers, or post
functions. Therefore, one can pass as an optional argument a
\emph{trace filter} of type \gecoderef[class]{TraceFilter}
defined by a \emph{trace filter expression} (or \emph{TFE}) of type
\gecoderef[class]{TFE} to a trace recorder.

\begin{samepage}
Assume that \?pga? and \?pgb? are two propagator groups and
\?bg? is a brancher group. Then
\begin{code}
trace(home, x, pga);
\end{code}
\end{samepage}
traces only prune-events that have been caused by a
propagator or a post function associated with the group
\?pga?. Prune-events caused by propagators or post functions from
groups \?pga? and \?pgb? are traced by
\begin{code}
trace(home, x, pga+pgb);
\end{code}
Likewise, prune-events caused by branchers in the group \?bg? or
by propagators or post functions not associated with \?pga? are
traced by
\begin{code}
trace(home, x, bg-pga);
\end{code}
The following only traces post functions associated with \?pga?
and propagators included in \?pgb?:
\begin{code}
trace(home, x, post(pga)+propagator(pgb));
\end{code}

In summary, TFEs can be constructed from the
unary and binary operators~\?+? and~\?-? and the functions
\?post()? and \?propagator()? taking a propagator group as
argument.

\subsection{Selecting the events to trace}

When creating a trace recorder, it can be defined which events
should be recorded by providing an additional argument. For
example
\begin{code}
trace(home, x, TE_PRUNE);
\end{code}
only records prune-events, whereas
\begin{code}
trace(home, x, TE_PRUNE | TE_FIX);
\end{code}
records prune- and fixpoint-events. All events (the default)
are recorded by
\begin{code}
trace(home, x,
      TE_INIT | TE_PRUNE | TE_FIX | TE_FAIL | TE_DONE);
\end{code}


\subsection{Enabling and disabling variable trace recorders}
\label{sec:m:group:traceonoff}

A variable trace recorder is implemented by a propagator, hence
it can be controlled by propagator groups. In particular, a
variable trace recorder can be disabled and enabled.

For example, by creating a propagator group~\?t? by
\begin{code}
PropagatorGroup t;
\end{code}
\begin{samepage}
  and then creating a variable trace recorder so that it belongs
  to the group~\?t? by
\begin{code}
trace(home(t), x);
\end{code}
\end{samepage}
the variable trace recorder can be controlled through the group~\?t?.
\begin{samepage}
For example, the variable trace recorder can be disabled by
\begin{code}
t.disable(home);
\end{code}
\end{samepage}
and the later enabled by
\begin{code}
t.enable(home);
\end{code}
One can easily add several variable trace recorders (either
for different variables or different variable types) to the same
propagator group and jointly control all variable trace recorders in
that group.


\section{General tracing}
\label{sec:m:group:trace}

In addition to variable tracing, Gecode offers support to trace
the execution of propagators and branchers. Like with variable
tracing, \emph{general tracing} distinguishes two components: a
\emph{general trace recorder} (or, \emph{trace recorder} for
short) that records information about relevant events during
constraint propagation as well as branching, and a \emph{general
  tracer} (or, \emph{tracer} for short) that processes the
recorded trace information.

\subsection{Creating a general trace recorder}

A trace recorder can be created by calling the
overloaded function \?trace()?. For example,
\begin{code}
trace(home);
\end{code}
creates a trace recorder.

A general trace recorder records the following events:
\begin{itemize}
\item Each time a constraint is posted, a \emph{post-event} is
  recorded. The recorder provides information whether posting
  has lead to failure, the posted constraint is subsumed (that is, no
  propagator has been  posted for the constraint), or one or
  several propagators have been created. 
\item Each time a propagator is executed, a
  \emph{propagate-event} is recorded.  The recorder provides
  information about which propagator has been executed and what
  the status of the execution is (that is, whether the propagator
  computed a fixpoint, did not compute a fixpoint, became
  subsumed, or resulted in failure).
\item Each time a commit operation on a brancher is executed, a
  \emph{commit-event} is recorded.
\end{itemize}
 
\subsection{Default general tracers}

The following paragraphs explain the information printed by the
default general tracer.

\begin{figure}
\begin{cmd}
SEND+MORE=MONEY
trace::post(s:posted(1))
trace::post(s:subsumed)
  ...
trace::propagate(id:2,s:fix)
  ...
trace::commit(id:1)
        var[1] = 4
trace::propagate(id:2,s:subsumed)
  ...
trace::propagate(id:1,s:failed)
  ...
\end{cmd}
\caption{Abridged output for general tracing of Send More Money}
\label{fig:m:group:smm}
\end{figure}

Running the \gecoderef[example]{money} (see
\autoref{chap:m:started} and \autoref{chap:m:comfy} for the Send
More Money problem) with the commandline option \?-trace propagate,commit?
(trace events to be recorded can be specified on the command
line, see \autoref{sec:m:driver:options}), the default
tracer prints information about all trace
events to \?std::cerr?. An excerpt of the information printed is
shown in \autoref{fig:m:group:smm} where the trace recorder has
been posted with
\begin{code}
trace(home);
\end{code}

The output for each event starts with the information
\begin{cmd}
trace::
\end{code}
After that, the type of event is shown (\?propagate?, 
\?choice?, or \?post?).

The information for each event type is as follows:
\begin{itemize}
\item For a propagate-event, the propagator identifier is
  printed, potentially followed by the propagator group. This is
  followed by status information.
\item For a choice-event, the brancher identifier is printed,
  potentially followed by the brancher group. This is followed by
  information which alternative the brancher has been committed
  to, see also \autoref{sec:m:branch:print}.
\item For a post-event, 
  potentially the propagator group is printed. This is followed by
  status information.
\end{itemize}

Defining custom general tracers is straightforward, this is
explained in \autoref{sec:m:group:tracers}.

\paragraph{Additional features.}

Like for variable tracers, general tracers can also be controlled
by trace filters (see \autoref{sec:m:group:filters}) and can be
disabled (see \autoref{sec:m:group:traceonoff}).

When creating a trace recorder, it can be defined which events
should be recorded by providing an additional argument. For
example,
\begin{code}
trace(home, TE_PROPAGATE);
\end{code}
only records propagate-events, whereas
\begin{code}
trace(home, TE_CHOICE);
\end{code}
only records choice-events. All events (the default)
are recorded by
\begin{code}
trace(home, TE_POST | TE_PROPAGATE | TE_CHOICE);
\end{code}

\section{Programming variable tracers}
\label{sec:m:group:vartracers}

Programming variable tracers is straightforward and is done by
inheriting from a class that depends on the variable type and
implements one virtual member function for each trace event type.
These virtual member functions are called when an event of that
type is being recorded and the event type has been selected for
tracing. For integer variables, the tracer class to inherit from
is \gecoderef[typedef]{IntTracer}, for Boolean variables
\gecoderef[typedef]{BoolTracer}, for set variables
\gecoderef[typedef]{SetTracer}, and for float variables
\gecoderef[typedef]{FloatTracer}.

In the following we are discussing variable tracers for integer
and Boolean variables in some detail in
\autoref{sec:m:group:tracers:int} and summarize variable tracers
for set and float variables in \autoref{sec:m:group:tracers:set}
and \autoref{sec:m:group:tracers:float} respectively.

\subsection{Tracers for integer and Boolean variables}
\label{sec:m:group:tracers:int}


\begin{figure}
\insertlitcode{integer variable tracer}
\caption{An integer variable tracer printing to \?std::cout?}
\label{fig:m:group:tracer}
\end{figure}

The example tracer we discuss is implemented by a class
\?StdCoutIntTracer?, prints trace information to \?std::cout?,
and is shown in \autoref{fig:m:group:tracer}. The \?init()?,
\?fail()?, and \?done()? member functions are not discussed as
they are similar to the member function \?fix()? which is
discussed below.

\paragraph{Printing propagator information.}

The example tracer prints information about propagators and
branchers using overloaded static member functions \?ids()? (for
identifiers). Printing information about propagators is
implemented as follows:
\insertlitcode{integer variable tracer:print propagator information}

The function always prints the identifier \?p.id()? of the
propagator \?p?. If~\?p? is in a propagator group \?p.group()?
which is different from the default propagator group (tested by
the \?in()? function of a propagator group), then also the group
identifier is printed. The overloaded function \?ids()? for
branchers is identical and hence only shown in abbreviation in
\autoref{fig:m:group:tracer}.

\paragraph{Printing variable trace information.}

The member function \?prune()? receives as an argument a
reference to an object of class \gecoderef[class]{ViewTraceInfo}
providing information about which entity triggered the
corresponding prune-event. The following function illustrates the
information provided by an object of class
\gecoderef[class]{ViewTraceInfo}. 
\insertlitcode{integer variable tracer:print view trace information}

\paragraph{Printing prune-events.}

A \?prune()? member function takes arguments that provide
information about \emph{what} is being pruned (this is given by
the integer~\?i? as the position of the variable in the array
passed to the \?trace()? function), \emph{how} the variable has
been pruned (this is given by the argument~\?d? of class
\gecoderef[class]{IntTraceDelta}), and by \emph{whom} (this is
given by the class \gecoderef[class]{ViewTraceInfo},
which has been discussed in the previous paragraph). It also gets
access to the trace recorder of type
\gecoderef[typedef]{IntTraceRecorder}. 

\begin{samepage}
The example \?prune()?
function prints information as follows:
\insertlitcode{integer variable tracer:prune event}
\end{samepage}

As can be seen, the argument~\?d? of type
\gecoderef[class]{IntTraceDelta} is a range iterator with the
same interface as described in \autoref{sec:m:int:iter} and
iterates of the integer ranges that correspond to the values that
have been removed. The trace
recorder~\?t? provides access to its variables through the array
operator \?[]?.

\paragraph{Printing fixpoint-events.}

The \?fix()? function also receives an argument of type
\gecoderef[typedef]{IntTraceRecorder} as shown here:
\insertlitcode{integer variable tracer:fixpoint event}
The integer trace recorder~\?t? provides access to \emph{slack}
information about all of its variables through a \?slack()?
member function. 

For integer variables, the 
slack is the number of values that still need to be pruned before
all variables become assigned and is of type 
\?unsigned long long int?. Here, the function \?initial()? of
\?t.slack()? returns the initial slack when the trace recorder
has been created, \?previous()? returns the slack at the previous
fixpoint (or, the initial slack if it is the first fixpoint), and
\?current()? returns the current slack.

Note that the slack information is only updated when a fixpoint-,
init-, or done-event occurs.

\tip{Naming propagators, branchers, variables, and groups}{
\label{tip:m:group:name}%
Note that all entities relevant for tracing carry a \emph{unique}
and \emph{global} identity: propagators, branchers, propagator groups, and
brancher groups all provide a function \?id()? that returns a
unique identifier for that entity of type \?unsigned int?. The
identity is global in that it does not change when a space is
being cloned during search. Hence naming entities through a hash
table mapping identities to user-defined names is straightforward.
}

\paragraph{Variable tracers for Boolean variables.}

Variable tracers for Boolean variables are exactly like variable
tracers for integer variables: a Boolean variable trace recorder is of
type \gecoderef[typedef]{BoolTraceRecorder}, the trace delta is
also a range iterator of class \gecoderef[class]{BoolTraceDelta},
and the slack is defined as for integer variables and is also of
type \?unsigned long long int?.

\paragraph{Memory and concurrency properties of tracers.}

There is no automatic memory management for tracers, the user is
responsible for creating and deleting tracers. A tracer can be used
across several threads where it is ensured that the execution of
a trace function is synchronized in that at most one thread
executes any trace function at any given time.

\subsection{Variable tracers for set variables}
\label{sec:m:group:tracers:set}

The types and classes for set variable tracers are as follows:
\begin{itemize}
\item The variable trace recorder is of type
  \gecoderef[typedef]{SetTraceRecorder}.
\item The trace delta information is of class
  \gecoderef[class]{SetTraceDelta} which implements two member
  functions \?glb()? (for greatest lower bound) and \?lub()? (for
  least upper bound) which return range iterators. The function
  \?glb()? returns a range iterator of class
  \gecoderef[class]{SetTraceDelta::Glb} which iterates over the
  values that have been included into a set variable by a prune-event. The
  function \?lub()? returns a range iterator of class
  \gecoderef[class]{SetTraceDelta::Lub} which iterates over the
  values that have been excluded from a set variable by a prune-event.
\item The slack of a set variable is defined as the number of
  values where membership has not been decided and is of type
\?unsigned long long int?.
\end{itemize}

\subsection{Variable tracers for float variables}
\label{sec:m:group:tracers:float}

The types and classes for float variable tracers are as follows:
\begin{itemize}
\item The variable trace recorder is of type
  \gecoderef[typedef]{FloatTraceRecorder}.
\item The trace delta information is of class
  \gecoderef[class]{FloatTraceDelta} which implements two member
  functions \?min()? and \?max()? defining the interval of float
  values that have been pruned.
\item The slack of a float variable is defined as its width and
  is of type \gecoderef[typedef]{FloatNum}.

\end{itemize}


\section{Programming general tracers}
\label{sec:m:group:tracers}

Programming general tracers is straightforward and is done by
inheriting from the class \gecoderef[class]{Tracer} that
implements one virtual member function for each trace event type.
These virtual member functions are called when an event of that
type is being recorded and the event type has been selected for
tracing.

\begin{figure}
\insertlitcode{general tracer}
\caption{A general tracer printing to \?std::cout?}
\label{fig:m:group:gtracer}
\end{figure}

The example tracer we discuss is implemented by a class
\?StdCoutTracer?, prints trace information to \?std::cout?,
and is shown in \autoref{fig:m:group:gtracer}.

The virtual member function \?commit()? takes a space and an
object \?cti? of class \gecoderef[class]{CommitTraceInfo} as
input. Information about the brancher, the choice, and the
alternative to commit to can be accessed through the member
functions of \?cti?.

The virtual member function \?post()? takes a space and an
object \?pti? of class \gecoderef[class]{PostTraceInfo} as
input. Information about propagator group, status, and the number
of posted propagators can be accessed through the member
functions of \?pti?.

The virtual member function \?propagate()? takes a space and an
object \?pti? of class \gecoderef[class]{PropagateTraceInfo} as
input. Information about the propagator and the status of
propagation can be accessed through the member functions of
\?pti?.

\begin{litcode}{general tracer}{schulte}
\begin{litblock}{anonymous}
#include <gecode/kernel.hh>
#include <iomanip>

using namespace Gecode;

\end{litblock}
class StdCoutTracer : public Tracer {
public:
  virtual void post(const Space& home,
                    const PostTraceInfo& pti) {
    std::cout << "trace::" << pti << std::endl;
  }
  virtual void propagate(const Space& home,
                         const PropagateTraceInfo& pti) {
    std::cout << "trace::" << pti << std::endl;
  }
  virtual void commit(const Space& home,
                      const CommitTraceInfo& cti) {
    std::cout << "trace::" << cti << std::endl
              << '\t';
    cti.brancher().print(home, cti.choice(), cti.alternative(),
                         std::cout);
    std::cout << std::endl;
  }
};
\end{litcode}


\begin{litcode}{integer variable tracer}{schulte}
\begin{litblock}{anonymous}
#include <gecode/int.hh>
#include <iomanip>

using namespace Gecode;

\end{litblock}
class StdCoutIntTracer : public IntTracer {
protected:
  \begin{litblock}{print propagator information}
  static void ids(const Propagator& p) {
    std::cout << "(id:" << p.id();
    if (p.group().in())
      std::cout << ",g:" << p.group().id();
    std::cout << ')';
  }
  \end{litblock}
  static void ids(const Brancher& b) {
    \begin{litblock}{anonymous}
    std::cout << "(id:" << b.id();
    if (b.group().in())
      std::cout << ",g:" << b.group().id();
    std::cout << ')';
    \end{litblock}
  }
  \begin{litblock}{print view trace information}
  static void info(const ViewTraceInfo& vti) {
    switch (vti.what()) {
    case ViewTraceInfo::PROPAGATOR:
      std::cout << "propagator"; ids(vti.propagator());
      break;
    case ViewTraceInfo::BRANCHER:
      std::cout << "brancher"; ids(vti.brancher());
      break;
    case ViewTraceInfo::POST:
      std::cout << "post(";
      if (vti.post().in())
        std::cout << "g:" << vti.post().id();
      std::cout << ')';
      break;
    case ViewTraceInfo::OTHER:
      std::cout << '-';
      break;
    }
  }
  \end{litblock}
public:
  virtual void init(const Space& home, const IntTraceRecorder& t) {
    \begin{litblock}{anonymous}
    std::cout << "trace::init"; ids(t);
    std::cout << " slack: 100.00% (" << t.slack().initial() << " values)"
              << std::endl;
    \end{litblock}
  }
  \begin{litblock}{prune event}
  virtual void prune(const Space& home, const IntTraceRecorder& t,
                     const ViewTraceInfo& vti, int i, IntTraceDelta& d) {
    std::cout << "trace::prune"; ids(t);
    std::cout << ": [" << i << "] = " << t[i] << " - {";
    std::cout << d.min();
    if (d.width() > 1)
      std::cout << ".." << d.max();
    ++d;
    while (d()) {
      \begin{litblock}{anonymous}
      std::cout << ',' << d.min();
      if (d.width() > 1)
        std::cout << ".." << d.max();
      ++d;
      \end{litblock}
    }
    std::cout << "} by "; info(vti);
    std::cout << std::endl;
  }
  \end{litblock}
  \begin{litblock}{fixpoint event}
  virtual void fix(const Space& home, const IntTraceRecorder& t) {
    std::cout << "trace::fix"; ids(t);
    double sl_i = static_cast<double>(t.slack().initial());
    double sl_p = static_cast<double>(t.slack().previous());
    double sl_c = static_cast<double>(t.slack().current());
    \begin{litblock}{anonymous}
    double p_c = 100.0 * (sl_c / sl_i);
    double p_d = 100.0 * (sl_p / sl_i) - p_c;
    std::cout << " slack: "
              << std::showpoint << std::setprecision(4)
              << p_c << "% - "
              << std::showpoint << std::setprecision(4)
              << p_d << '%'
              << std::endl;
    \end{litblock}
  }
  \end{litblock}
  virtual void fail(const Space& home, const IntTraceRecorder& t) {
    \begin{litblock}{anonymous}
    std::cout << "trace::fail"; ids(t);
    double sl_i = static_cast<double>(t.slack().initial());
    double sl_p = static_cast<double>(t.slack().previous());
    double sl_c = static_cast<double>(t.slack().current());
    double p_c = 100.0 * (sl_c / sl_i);
    double p_d = 100.0 * (sl_p / sl_i) - p_c;
    std::cout << " slack: "
              << std::showpoint << std::setprecision(4)
              << p_c << "% - "
              << std::showpoint << std::setprecision(4)
              << p_d << '%'
              << std::endl;
    \end{litblock}
  }
  virtual void done(const Space& home, const IntTraceRecorder& t) {
    \begin{litblock}{anonymous}
    std::cout << "trace::done"; ids(t);
    if (t.group().in())
      std::cout << ",g:" << t.group().id();
    std::cout << ") slack: 0%" << std::endl;
    \end{litblock}
  }
};
\end{litcode}