Generated on Wed Jan 4 17:49:22 2006 for Gecode by doxygen 1.4.6

Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared > Class Template Reference
[Integer propagators]

#include <sortedness.hh>

Inherits Gecode::Propagator.

List of all members.


Detailed Description

template<class View, class Tuple, bool Perm, bool shared>
class Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >

Bounds consistent sortedness propagator.

[Reference]
The algorithm is taken from:
Sven Thiel: Efficient Algorithms for Constraint Propagation and for Processing Tree Descriptions (pages 39 to 59) [http://www.mpi-sb.mpg.de/~sthiel/thesis.pdf]
Requires
 #include "int/sortedness.hh" 
and
 #include "int/distinct.hh" 
. The latter is required for the extended version of sortedness including permutation views.

Definition at line 54 of file sortedness.hh.

Public Member Functions

virtual ~Sortedness (void)
 Destructor.
virtual Actorcopy (Space *home, bool share)
 Copy propagator during cloning.
virtual PropCost cost (void) const
 Cost function returning PC_LINEAR_HI.
virtual ExecStatus propagate (Space *home)
 Perform propagation.

Static Public Member Functions

static ExecStatus post (Space *, ViewArray< Tuple > &, ViewArray< View > &)
 Post propagator for the views xz and y.

Protected Member Functions

 Sortedness (Space *, ViewArray< Tuple > &, ViewArray< View > &)
 Constructor for posting.
 Sortedness (Space *home, bool share, Sortedness< View, Tuple, Perm, shared > &p)
 Constructor for cloning.

Protected Attributes

ViewArray< Tuple > xz
 Views to be sorted.
ViewArray< View > y
 Views denoting the sorted version of x.
ViewArray< View > w
 original y array
int reachable
 connection to dropped view


Constructor & Destructor Documentation

template<class View, class Tuple, bool Perm, bool shared>
Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::Sortedness Space ,
ViewArray< Tuple > &  ,
ViewArray< View > & 
[protected]
 

Constructor for posting.

Definition at line 402 of file sortedness.icc.

template<class View, class Tuple, bool Perm, bool shared>
Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::Sortedness Space home,
bool  share,
Sortedness< View, Tuple, Perm, shared > &  p
[protected]
 

Constructor for cloning.

Definition at line 392 of file sortedness.icc.

template<class View, class Tuple, bool Perm, bool shared>
Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::~Sortedness void   )  [virtual]
 

Destructor.

Definition at line 410 of file sortedness.icc.


Member Function Documentation

template<class View, class Tuple, bool Perm, bool shared>
Actor * Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::copy Space home,
bool  share
[virtual]
 

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 416 of file sortedness.icc.

template<class View, class Tuple, bool Perm, bool shared>
PropCost Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::cost void   )  const [virtual]
 

Cost function returning PC_LINEAR_HI.

Implements Gecode::Propagator.

Definition at line 421 of file sortedness.icc.

template<class View, class Tuple, bool Perm, bool shared>
ExecStatus Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::propagate Space home  )  [virtual]
 

Perform propagation.

Implements Gecode::Propagator.

Definition at line 427 of file sortedness.icc.

template<class View, class Tuple, bool Perm, bool shared>
ExecStatus Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::post Space ,
ViewArray< Tuple > &  ,
ViewArray< View > & 
[static]
 

Post propagator for the views xz and y.

Definition at line 630 of file sortedness.icc.


Member Data Documentation

template<class View, class Tuple, bool Perm, bool shared>
ViewArray<Tuple> Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::xz [protected]
 

Views to be sorted.

If Tuple is instantiated to ViewTuple<View,2>, $xz_i$ is a pair $(x_i, z_i)$, where $x_i$ denotes an unsorted view and $z_i$ is the explicit permutation view mapping $x_i$ to its unsorted counterpart $y_{z_i}$. If Tuple is instantiated to ViewTuple<View,1>, $xz_i$ is the unsorted view $x_i$ lifted to a ViewTuple.

Definition at line 69 of file sortedness.hh.

template<class View, class Tuple, bool Perm, bool shared>
ViewArray<View> Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::y [protected]
 

Views denoting the sorted version of x.

Definition at line 72 of file sortedness.hh.

template<class View, class Tuple, bool Perm, bool shared>
ViewArray<View> Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::w [protected]
 

original y array

Definition at line 74 of file sortedness.hh.

template<class View, class Tuple, bool Perm, bool shared>
int Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm, shared >::reachable [protected]
 

connection to dropped view

Definition at line 76 of file sortedness.hh.


The documentation for this class was generated from the following files: