Generated on Wed Nov 1 15:05:20 2006 for Gecode by doxygen 1.4.5
Gecode::Int::Sortedness::Sortedness

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

#include <sortedness.hh>

Inherits Gecode::Propagator.

List of all members.

Detailed Description

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

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 "gecode/int/sortedness.hh"
and
 #include "gecode/int/distinct.hh"
. The latter is required for the extended version of sortedness including permutation views.

Note:
The sortedness propagator does not support sharing!

Definition at line 54 of file sortedness.hh.

Public Member Functions

virtual size_t dispose (Space *home)
 Delete propagator and return its size.
virtual Actor * copy (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 > &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>
Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm >::Sortedness (  Space *  ,
ViewArray< Tuple > &  ,
ViewArray< View > & 
)  [protected]
 

Constructor for posting.

Definition at line 397 of file sortedness.icc.

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

Constructor for cloning.

Definition at line 387 of file sortedness.icc.

Member Function Documentation

template<class View, class Tuple, bool Perm>
size_t Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm >::dispose (  Space *  home  )  [virtual]
 

Delete propagator and return its size.

Reimplemented from Gecode::Actor.

Definition at line 406 of file sortedness.icc.

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

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 415 of file sortedness.icc.

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

Cost function returning PC_LINEAR_HI.

Implements Gecode::Propagator.

Definition at line 420 of file sortedness.icc.

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

Perform propagation.

Implements Gecode::Propagator.

Definition at line 426 of file sortedness.icc.

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

Post propagator for the views xz and y.

Definition at line 705 of file sortedness.icc.

Member Data Documentation

template<class View, class Tuple, bool Perm>
ViewArray<Tuple> Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm >::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>
ViewArray<View> Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm >::y [protected]
 

Views denoting the sorted version of x.

Definition at line 72 of file sortedness.hh.

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

original y array

Definition at line 74 of file sortedness.hh.

template<class View, class Tuple, bool Perm>
int Gecode::Int::Sortedness::Sortedness< View, Tuple, Perm >::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: