← Back to branch summary

~ubuntu-branches/ubuntu/natty/gecode/natty

« back to all changes in this revision

Viewing changes to set/convex/hull.cc

  • Committer: Bazaar Package Importer
  • Author(s): Kari Pahula
  • Date: 2005-12-24 07:51:25 UTC
  • Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
set/convex/hull.cc
 
1
/*
 
2
 *  Main authors:
 
3
 *     Guido Tack <tack@gecode.org>
 
4
 *     Christian Schulte <schulte@gecode.org>
 
5
 *
 
6
 *  Contributing authors:
 
7
 *     Gabor Szokoli <szokoli@gecode.org>
 
8
 *
 
9
 *  Copyright:
 
10
 *     Guido Tack, 2004
 
11
 *     Christian Schulte, 2004
 
12
 *     Gabor Szokoli, 2004
 
13
 *
 
14
 *  Last modified:
 
15
 *     $Date: 2005-11-24 18:03:01 +0100 (Thu, 24 Nov 2005) $ by $Author: tack $
 
16
 *     $Revision: 2639 $
 
17
 *
 
18
 *  This file is part of Gecode, the generic constraint
 
19
 *  development environment:
 
20
 *     http://www.gecode.org
 
21
 *
 
22
 *  See the file "LICENSE" for information on usage and
 
23
 *  redistribution of this file, and for a
 
24
 *     DISCLAIMER OF ALL WARRANTIES.
 
25
 *
 
26
 */
 
27
 
 
28
#include "set.hh"
 
29
#include "set/convex.hh"
 
30
 
 
31
namespace Gecode { namespace Set { namespace Convex {
 
32
 
 
33
  Actor*
 
34
  ConvexHull::copy(Space* home, bool share) {
 
35
    return new (home) ConvexHull(home,share,*this);
 
36
  }
 
37
 
 
38
  PropCost
 
39
  ConvexHull::cost(void) const {
 
40
    return PC_BINARY_HI;
 
41
  }
 
42
 
 
43
  ConvexHull::~ConvexHull(void) {
 
44
    x0.cancel(this,PC_SET_CGLB);
 
45
    x1.cancel(this,PC_SET_ANY);
 
46
  }
 
47
 
 
48
  ExecStatus
 
49
  ConvexHull::propagate(Space* home) {
 
50
    //x1 is the convex hull of x0
 
51
 
 
52
    GECODE_ME_CHECK( x1.cardMin(home,x0.cardMin()) );
 
53
    GECODE_ME_CHECK( x0.cardMax(home,x1.cardMax()) );
 
54
 
 
55
    do {
 
56
 
 
57
      //intersect x1 with (x0.lubMin(),x0.lubMax())
 
58
      //This empties x1 if x0.ub is empty. twice.
 
59
      GECODE_ME_CHECK( x1.exclude(home,Limits::Set::int_min,
 
60
                                  x0.lubMin()-1) );
 
61
      GECODE_ME_CHECK( x1.exclude(home,x0.lubMax()+1,
 
62
                                  Limits::Set::int_max) );
 
63
 
 
64
      int minElement = std::min(x1.glbMin(),x0.glbMin());
 
65
      int maxElement = std::max(x1.glbMax(),x0.glbMax());
 
66
 
 
67
      if (minElement<maxElement) {
 
68
        GECODE_ME_CHECK( x1.include(home, minElement, maxElement));
 
69
      }
 
70
 
 
71
      unsigned int cardMin = x1.cardMin();
 
72
 
 
73
      LubRanges<SetView> ubRangeIt(x1);
 
74
      Iter::Ranges::Cache< LubRanges<SetView> > ubRangeItC(ubRangeIt);
 
75
      for (;ubRangeItC();++ubRangeItC){
 
76
        if (ubRangeItC.width() < cardMin
 
77
            || ubRangeItC.min() > minElement //No need to test for empty lb.
 
78
            || ubRangeItC.max() < maxElement
 
79
            ) {
 
80
          GECODE_ME_CHECK( x1.exclude(home,
 
81
                                      ubRangeItC.min(), ubRangeItC.max()) );
 
82
        }
 
83
      }
 
84
 
 
85
      LubRanges<SetView> ubRangeIt2(x1);
 
86
      GECODE_ME_CHECK(x0.intersectI(home,ubRangeIt2) );
 
87
 
 
88
      if (x1.lubMin()!=BndSet::MIN_OF_EMPTY) {
 
89
        if(x1.lubMin()==x1.glbMin()) {
 
90
              GECODE_ME_CHECK(x0.include(home,x1.lubMin()));
 
91
        }
 
92
        if(x1.lubMax()==x1.glbMax()) {
 
93
              GECODE_ME_CHECK(x0.include(home,x1.lubMax()));
 
94
        }
 
95
      }
 
96
    } while(x0.assigned()&&!x1.assigned());
 
97
    
 
98
    //If x0 is assigned, x1 should be too.
 
99
    assert(x1.assigned() || !x0.assigned());
 
100
 
 
101
    if (x1.assigned()) {
 
102
      return ES_SUBSUMED;
 
103
    }
 
104
 
 
105
    return shared(x0,x1) ? ES_NOFIX : ES_FIX;
 
106
  }
 
107
 
 
108
}}}
 
109
 
 
110
// STATISTICS: set-prop