Generated on Thu Feb 14 2013 20:59:32 for Gecode by doxygen 1.8.3.1
tree.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2011-05-26 00:56:41 +1000 (Thu, 26 May 2011) $ by $Author: schulte $
13  * $Revision: 12022 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Int {
41 
42  forceinline int
43  plus(int x, int y) {
44  assert(y != -Int::Limits::infinity);
45  return (x == -Int::Limits::infinity) ? x : x+y;
46  }
47 
48  forceinline double
49  plus(double x, double y) {
50  assert(y != -Int::Limits::double_infinity);
51  return (x == -Int::Limits::double_infinity) ? x : x+y;
52  }
53 
54  forceinline double
55  div(double x, double y) {
56  assert(y != -Int::Limits::double_infinity);
57  return (x == -Int::Limits::double_infinity) ? x : x / y;
58  }
59 
60  template<class TaskView, class Node>
61  forceinline int
63  return tasks.size()-1;
64  }
65  template<class TaskView, class Node>
66  forceinline int
68  return 2*tasks.size() - 1;
69  }
70 
71  template<class TaskView, class Node>
72  forceinline bool
74  return i == 0;
75  }
76  template<class TaskView, class Node>
77  forceinline bool
79  return i >= n_inner();
80  }
81  template<class TaskView, class Node>
82  forceinline int
84  return 2*(i+1) - 1;
85  }
86  template<class TaskView, class Node>
87  forceinline bool
89  assert(!n_root(i));
90  // A left node has an odd number
91  return (i & 1) != 0;
92  }
93  template<class TaskView, class Node>
94  forceinline int
96  return 2*(i+1);
97  }
98  template<class TaskView, class Node>
99  forceinline bool
101  assert(!n_root(i));
102  // A left node has an even number
103  return (i & 1) == 0;
104  }
105  template<class TaskView, class Node>
106  forceinline int
108  return (i+1)/2 - 1;
109  }
110 
111  template<class TaskView, class Node>
112  forceinline Node&
114  return node[_leaf[i]];
115  }
116 
117  template<class TaskView, class Node>
118  forceinline const Node&
120  return node[0];
121  }
122 
123  template<class TaskView, class Node>
124  forceinline void
126  for (int i=n_inner(); i--; )
127  node[i].init(node[n_left(i)],node[n_right(i)]);
128  }
129 
130  template<class TaskView, class Node>
131  forceinline void
133  for (int i=n_inner(); i--; )
134  node[i].update(node[n_left(i)],node[n_right(i)]);
135  }
136 
137  template<class TaskView, class Node>
138  forceinline void
140  if (l)
141  i = _leaf[i];
142  assert(!n_root(i));
143  do {
144  i = n_parent(i);
145  node[i].update(node[n_left(i)],node[n_right(i)]);
146  } while (!n_root(i));
147  }
148 
149  template<class TaskView, class Node>
152  const TaskViewArray<TaskView>& t)
153  : tasks(t),
154  node(r.alloc<Node>(n_nodes())),
155  _leaf(r.alloc<int>(tasks.size())) {
156  // Compute a sorting map to order by non decreasing est
157  int* map = r.alloc<int>(tasks.size());
158  sort<TaskView,STO_EST,true>(map, tasks);
159  // Compute inverse of sorting map
160  for (int i=tasks.size(); i--; )
161  _leaf[map[i]] = i;
162  r.free<int>(map,tasks.size());
163  // Compute index of first leaf in tree: the next larger power of two
164  int fst = 1;
165  while (fst < tasks.size())
166  fst <<= 1;
167  fst--;
168  // Remap task indices to leaf indices
169  for (int i=tasks.size(); i--; )
170  if (_leaf[i] + fst >= n_nodes())
171  _leaf[i] += fst - tasks.size();
172  else
173  _leaf[i] += fst;
174  }
175 
176  template<class TaskView, class Node> template<class Node2>
179  const TaskTree<TaskView,Node2>& t)
180  : tasks(t.tasks),
181  node(r.alloc<Node>(n_nodes())),
182  _leaf(r.alloc<int>(tasks.size())) {
183  for (int i=tasks.size(); i--; )
184  _leaf[i] = t._leaf[i];
185  }
186 
187 }}
188 
189 // STATISTICS: int-prop