this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2009
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <climits>
35#include <cmath>
36
37namespace Gecode { namespace Int { namespace Sequence {
38
39 /// Simple bitsets for recording violations
40 class Violations : public Support::BitSetBase {
41 protected:
42 /// The (possibly) first set bit (set is empty if fst == sz)
43 mutable unsigned int fst;
44 public:
45 /// Default constructor
46 Violations(void);
47 /// Initialize violation set for \a n violations
48 void init(Space& home, unsigned int n);
49 /// Update violation set during cloning
50 void update(Space& home, Violations& v);
51 /// Return whether set is empty
52 bool empty(void) const;
53 /// Add \a i to violation set
54 void add(unsigned int i);
55 /// Get first element from violation set and remove it
56 unsigned int get(void);
57 };
58
59
60 forceinline
61 Violations::Violations(void) : fst(0) {}
62
63 forceinline void
64 Violations::init(Space& home, unsigned int n) {
65 Support::BitSetBase::init(home,n);
66 fst=size();
67 }
68
69 forceinline bool
70 Violations::empty(void) const {
71 fst = next(fst);
72 return fst >= size();
73 }
74
75 forceinline void
76 Violations::update(Space& home, Violations& v) {
77 assert(v.empty());
78 init(home,v.size());
79 }
80
81 forceinline void
82 Violations::add(unsigned int i) {
83 set(i); if (i < fst) fst = i;
84 }
85
86 forceinline unsigned int
87 Violations::get(void) {
88 assert(!empty());
89 fst = next(fst);
90 assert(Support::BitSetBase::get(fst));
91 clear(fst); fst++;
92 return fst-1;
93 }
94
95}}}
96
97// STATISTICS: int-prop