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, 2004
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
34namespace Gecode { namespace Iter { namespace Ranges {
35
36 /**
37 * \brief Range iterator for computing set difference
38 *
39 * \ingroup FuncIterRanges
40 */
41
42 template<class I, class J>
43 class Diff : public MinMax {
44 protected:
45 /// Iterator from which to subtract
46 I i;
47 /// Iterator to be subtracted
48 J j;
49 public:
50 /// \name Constructors and initialization
51 //@{
52 /// Default constructor
53 Diff(void);
54 /// Initialize with iterator \a i and \a j
55 Diff(I& i, J& j);
56 /// Initialize with iterator \a i and \a j
57 void init(I& i, J& j);
58 //@}
59
60 /// \name Iteration control
61 //@{
62 /// Move iterator to next range (if possible)
63 void operator ++(void);
64 //@}
65 };
66
67
68
69 template<class I, class J>
70 forceinline void
71 Diff<I,J>::operator ++(void) {
72 // Precondition: mi <= ma
73 // Task: find next mi greater than ma
74 while (true) {
75 if (!i()) break;
76 mi = ma+1;
77 ma = i.max();
78 if (mi > i.max()) {
79 ++i;
80 if (!i()) break;
81 mi = i.min();
82 ma = i.max();
83 }
84 while (j() && (j.max() < mi))
85 ++j;
86 if (j() && (j.min() <= ma)) {
87 // Now the interval [mi ... ma] must be shrunken
88 // Is [mi ... ma] completely consumed?
89 if ((mi >= j.min()) && (ma <= j.max()))
90 continue;
91 // Does [mi ... ma] overlap on the left?
92 if (j.min() <= mi) {
93 mi = j.max()+1;
94 // Search for max!
95 ++j;
96 if (j() && (j.min() <= ma))
97 ma = j.min()-1;
98 } else {
99 ma = j.min()-1;
100 }
101 }
102 return;
103 }
104 finish();
105 }
106
107 template<class I, class J>
108 forceinline
109 Diff<I,J>::Diff(void) {}
110
111 template<class I, class J>
112 forceinline
113 Diff<I,J>::Diff(I& i0, J& j0)
114 : i(i0), j(j0) {
115 if (!i()) {
116 finish();
117 } else {
118 mi = i.min()-1; ma = mi;
119 operator ++();
120 }
121 }
122
123 template<class I, class J>
124 forceinline void
125 Diff<I,J>::init(I& i0, J& j0) {
126 i = i0; j = j0;
127 if (!i()) {
128 finish();
129 } else {
130 mi = i.min()-1; ma = mi;
131 operator ++();
132 }
133 }
134
135}}}
136
137// STATISTICS: iter-any
138