← Back to branch summary

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

« back to all changes in this revision

Viewing changes to iter/ranges-union.icc

  • 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:
iter/ranges-union.icc
 
1
/*
 
2
 *  Main authors:
 
3
 *     Christian Schulte <schulte@gecode.org>
 
4
 *
 
5
 *  Copyright:
 
6
 *     Christian Schulte, 2004
 
7
 *
 
8
 *  Last modified:
 
9
 *     $Date: 2005-07-29 21:55:06 +0200 (Fri, 29 Jul 2005) $ by $Author: schulte $
 
10
 *     $Revision: 2085 $
 
11
 *
 
12
 *  This file is part of Gecode, the generic constraint
 
13
 *  development environment:
 
14
 *     http://www.gecode.org
 
15
 *
 
16
 *  See the file "LICENSE" for information on usage and
 
17
 *  redistribution of this file, and for a
 
18
 *     DISCLAIMER OF ALL WARRANTIES.
 
19
 *
 
20
 */
 
21
 
 
22
#include "support/static-pqueue.hh"
 
23
 
 
24
namespace Gecode { namespace Iter { namespace Ranges {
 
25
 
 
26
  /**
 
27
   * \brief Range iterator for computing union (binary)
 
28
   *
 
29
   * Requires \code #include "iter.hh" \endcode
 
30
   * \ingroup FuncIterRanges
 
31
   */
 
32
 
 
33
  template <class I, class J>
 
34
  class Union : public MinMax {
 
35
    /// First iterator
 
36
    I i; 
 
37
    /// Second iterator
 
38
    J j;
 
39
  public:
 
40
    /// \name Constructors and initialization
 
41
    //@{
 
42
    /// Default constructor
 
43
    Union(void);
 
44
    /// Initialize with iterator \a i and \a j
 
45
    Union(I& i, J& j);
 
46
    /// Initialize with iterator \a i and \a j
 
47
    void init(I& i, J& j);
 
48
    //@}
 
49
 
 
50
    /// \name Iteration control
 
51
    //@{
 
52
    /// Move iterator to next range (if possible)
 
53
    void operator++(void);
 
54
    //@}
 
55
  };
 
56
 
 
57
 
 
58
  /**
 
59
   * \brief Range iterator for union for any number of iterators
 
60
   * \ingroup FuncIterRanges
 
61
   */
 
62
 
 
63
  template <class I>
 
64
  class NaryUnion : public MinMax {
 
65
  protected:
 
66
    /// Order for iterators: by increasing minimum of next range
 
67
    class RangeUnionOrder {
 
68
    public:
 
69
      bool operator()(const I&, const I&) const;
 
70
    };
 
71
    /// Instance for order
 
72
    RangeUnionOrder order;
 
73
    /// Priority queue to give access to next range
 
74
    Support::PQueue<I,RangeUnionOrder> r;
 
75
  public:
 
76
    /// \name Constructors and initialization
 
77
    //@{
 
78
    /// Default constructor
 
79
    NaryUnion(void);
 
80
    /// Initialize with \a n iterators in \a i
 
81
    NaryUnion(I* i, int n);
 
82
    /// Initialize with \a n iterators in \a i
 
83
    void init(I* i, int n);
 
84
    //@}
 
85
 
 
86
    /// \name Iteration control
 
87
    //@{
 
88
    /// Move iterator to next range (if possible)
 
89
    void operator++(void);
 
90
    //@}
 
91
  };
 
92
 
 
93
 
 
94
 
 
95
  /*
 
96
   * Binary union
 
97
   *
 
98
   */
 
99
 
 
100
  template <class I, class J>
 
101
  inline void
 
102
  Union<I,J>::operator++(void) {
 
103
    if (!i() && !j()) {
 
104
      finish(); return;
 
105
    }
 
106
    if (!i()) {
 
107
      mi = j.min(); ma = j.max(); ++j; return;
 
108
    }
 
109
    if (!j()) {
 
110
      mi = i.min(); ma = i.max(); ++i; return;
 
111
    }
 
112
    if (i.min() < j.min()) {
 
113
      mi = i.min(); ma = i.max(); ++i;
 
114
    } else {
 
115
      mi = j.min(); ma = j.max(); ++j;
 
116
    }
 
117
    bool goOn;
 
118
    do {
 
119
      goOn = false;
 
120
      if (i() && (i.min() <= ma+1)) {
 
121
        ma = std::max(ma,i.max()); ++i; goOn=true;
 
122
      }
 
123
      if (j() && (j.min() <= ma+1)) {
 
124
        ma = std::max(ma,j.max()); ++j; goOn=true;
 
125
      }
 
126
    } while (goOn);
 
127
  }
 
128
 
 
129
 
 
130
  template <class I, class J>
 
131
  forceinline
 
132
  Union<I,J>::Union(void) {}
 
133
 
 
134
  template <class I, class J>
 
135
  forceinline
 
136
  Union<I,J>::Union(I& i0, J& j0)
 
137
    : i(i0), j(j0) {
 
138
    operator++();
 
139
  }
 
140
 
 
141
  template <class I, class J>
 
142
  forceinline void
 
143
  Union<I,J>::init(I& i0, J& j0) {
 
144
    i = i0; j = j0;
 
145
    operator++();
 
146
  }
 
147
 
 
148
 
 
149
 
 
150
  /*
 
151
   * Nary Union
 
152
   *
 
153
   */
 
154
 
 
155
  template <class I>
 
156
  forceinline bool
 
157
  NaryUnion<I>::RangeUnionOrder::operator()(const I& a, const I& b) const {
 
158
    return a.min() > b.min();
 
159
  }
 
160
 
 
161
  template <class I>
 
162
  inline void
 
163
  NaryUnion<I>::operator++(void) {
 
164
    if (r.empty()) {
 
165
      finish(); return;
 
166
    }
 
167
    mi = r.top().min();
 
168
    ma = r.top().max();
 
169
    do {
 
170
      if (ma < r.top().max())
 
171
        ma = r.top().max();
 
172
      ++(r.top());
 
173
      if (!(r.top())()) {
 
174
        r.remove();
 
175
        if (r.empty())
 
176
          return;
 
177
      } else {
 
178
        r.fix();
 
179
      }
 
180
    } while (ma+1 >= r.top().min());
 
181
  }
 
182
 
 
183
 
 
184
  template <class I>
 
185
  forceinline
 
186
  NaryUnion<I>::NaryUnion(void) {}
 
187
 
 
188
  template <class I>
 
189
  inline
 
190
  NaryUnion<I>::NaryUnion(I* r0, int n)
 
191
    : r(n,order) {
 
192
    for (int i = n; i--; )
 
193
      if (r0[i]())
 
194
        r.insert(r0[i]);
 
195
    operator++();
 
196
  }
 
197
 
 
198
  template <class I>
 
199
  inline void
 
200
  NaryUnion<I>::init(I* r0, int n) {
 
201
    r.init(n,order);
 
202
    for (int i = n; i--; )
 
203
      if (r0[i]())
 
204
        r.insert(r0[i]);
 
205
    operator++();
 
206
  }
 
207
 
 
208
}}}
 
209
 
 
210
// STATISTICS: iter-any
 
211