Generated on Thu Mar 16 2017 03:24:22 for Gecode by doxygen 1.8.13
core.cpp
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  *
6  * Copyright:
7  * Christian Schulte, 2002
8  *
9  * Last modified:
10  * $Date: 2016-09-02 16:22:37 +0200 (Fri, 02 Sep 2016) $ by $Author: schulte $
11  * $Revision: 15164 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <gecode/kernel.hh>
39 
40 namespace Gecode {
41 
42  /*
43  * Variable type disposer
44  *
45  */
46  void
48 
50 
51 
52 
53  /*
54  * Actor
55  *
56  */
57  Actor* Actor::sentinel;
58 
59  Actor::~Actor(void) {
60  assert(false);
61  }
62 
63 
64  /*
65  * Propagator
66  *
67  */
70  assert(false);
71  return ES_FAILED;
72  }
73 
74 
75  /*
76  * No-goods
77  *
78  */
79  void
80  NoGoods::post(Space&) const {
81  }
82 
84 
85  /*
86  * Brancher
87  *
88  */
89  NGL*
90  Brancher::ngl(Space&, const Choice&, unsigned int) const {
91  return NULL;
92  }
93 
94  void
95  Brancher::print(const Space&, const Choice&, unsigned int,
96  std::ostream&) const {
97  }
98 
99 
100  /*
101  * Space: Misc
102  *
103  */
104  StatusStatistics Space::unused_status;
105  CloneStatistics Space::unused_clone;
106  CommitStatistics Space::unused_commit;
107 
108 #ifdef GECODE_HAS_VAR_DISPOSE
110 #endif
111 
113  : sm(new SharedMemory), mm(sm), _wmp_afc(0U) {
114 #ifdef GECODE_HAS_VAR_DISPOSE
115  for (int i=0; i<AllVarConf::idx_d; i++)
116  _vars_d[i] = NULL;
117 #endif
118  // Initialize propagator and brancher links
119  pl.init();
120  bl.init();
121  b_status = b_commit = Brancher::cast(&bl);
122  // Initialize array for forced deletion to be empty
123  d_fst = d_cur = d_lst = NULL;
124  // Initialize space as stable but not failed
125  pc.p.active = &pc.p.queue[0]-1;
126  // Initialize propagator queues
127  for (int i=0; i<=PropCost::AC_MAX; i++)
128  pc.p.queue[i].init();
129  pc.p.bid = reserved_bid+1;
130  pc.p.n_sub = 0;
131  }
132 
133  void
134  Space::notice(Actor& a, ActorProperty p, bool duplicate) {
135  if (p & AP_DISPOSE) {
136  if (duplicate && (d_fst != NULL)) {
137  for (Actor** f = d_fst; f < d_cur; f++)
138  if (&a == *f)
139  return;
140  }
141  if (d_cur == d_lst) {
142  // Resize
143  if (d_fst == NULL) {
144  // Create new array
145  d_fst = alloc<Actor*>(4);
146  d_cur = d_fst;
147  d_lst = d_fst+4;
148  } else {
149  // Resize existing array
150  unsigned int n = static_cast<unsigned int>(d_lst - d_fst);
151  assert(n != 0);
152  d_fst = realloc<Actor*>(d_fst,n,2*n);
153  d_cur = d_fst+n;
154  d_lst = d_fst+2*n;
155  }
156  }
157  *(d_cur++) = &a;
158  } else if (p & AP_WEAKLY) {
159  if (wmp() == 0)
160  wmp(2);
161  else
162  wmp(wmp()+1);
163  }
164  }
165 
166  void
167  Space::ignore(Actor& a, ActorProperty p, bool duplicate) {
168  if (p & AP_DISPOSE) {
169  // Check wether array has already been discarded as space
170  // deletion is already in progress
171  if (d_fst == NULL)
172  return;
173  Actor** f = d_fst;
174  if (duplicate) {
175  while (f < d_cur)
176  if (&a == *f)
177  break;
178  else
179  f++;
180  if (f == d_cur)
181  return;
182  } else {
183  while (&a != *f)
184  f++;
185  }
186  *f = *(--d_cur);
187  } else if (p & AP_WEAKLY) {
188  assert(wmp() > 1U);
189  wmp(wmp()-1);
190  }
191  }
192 
193  void
194  Space::flush(void) {
195  // Flush malloc cache
196  sm->flush();
197  }
198 
200  // Mark space as failed
201  fail();
202  // Delete actors that must be deleted
203  {
204  Actor** a = d_fst;
205  Actor** e = d_cur;
206  // So that d_unforce knows that deletion is in progress
207  d_fst = NULL;
208  while (a < e) {
209  (void) (*a)->dispose(*this);
210  a++;
211  }
212  }
213 #ifdef GECODE_HAS_VAR_DISPOSE
214  // Delete variables that were registered for disposal
215  for (int i=AllVarConf::idx_d; i--;)
216  if (_vars_d[i] != NULL)
217  vd[i]->dispose(*this, _vars_d[i]);
218 #endif
219  // Release memory from memory manager
220  mm.release(sm);
221  // Release shared memory
222  if (sm->release())
223  delete sm;
224  }
225 
226 
227 
228  /*
229  * Space: propagation
230  *
231  */
232 
236  // Check whether space is failed
237  if (failed())
238  goto exit;
239  assert(pc.p.active <= &pc.p.queue[PropCost::AC_MAX+1]);
240  // Check whether space is stable but not failed
241  if (pc.p.active >= &pc.p.queue[0]) {
242  Propagator* p;
243  ModEventDelta med_o;
244  goto unstable;
245  execute:
246  stat.propagate++;
247  if (p->disabled())
248  goto put_into_idle;
249  pc.p.ei.propagator(*p);
250  // Keep old modification event delta
251  med_o = p->u.med;
252  // Clear med but leave propagator in queue
253  p->u.med = 0;
254  switch (p->propagate(*this,med_o)) {
255  case ES_FAILED:
256  // Count failure
257  if (afc_enabled())
258  gpi.fail(p->gpi());
259  // Mark as failed
260  fail(); s = SS_FAILED; goto exit;
261  case ES_NOFIX:
262  // Find next, if possible
263  if (p->u.med != 0) {
264  unstable:
265  // There is at least one propagator in a queue
266  do {
267  assert(pc.p.active >= &pc.p.queue[0]);
268  // First propagator or link back to queue
269  ActorLink* fst = pc.p.active->next();
270  if (pc.p.active != fst) {
271  p = Propagator::cast(fst);
272  goto execute;
273  }
274  pc.p.active--;
275  } while (true);
276  GECODE_NEVER;
277  }
278  // Fall through
279  case ES_FIX:
280  put_into_idle:
281  // Clear med
282  p->u.med = 0;
283  // Put into idle queue
284  p->unlink(); pl.head(p);
285  stable_or_unstable:
286  // There might be a propagator in the queue
287  do {
288  assert(pc.p.active >= &pc.p.queue[0]);
289  // First propagator or link back to queue
290  ActorLink* fst = pc.p.active->next();
291  if (pc.p.active != fst) {
292  p = Propagator::cast(fst);
293  goto execute;
294  }
295  } while (--pc.p.active >= &pc.p.queue[0]);
296  assert(pc.p.active < &pc.p.queue[0]);
297  goto stable;
298  case __ES_SUBSUMED:
299  p->unlink(); rfree(p,p->u.size);
300  goto stable_or_unstable;
301  case __ES_PARTIAL:
302  // Schedule propagator with specified propagator events
303  assert(p->u.med != 0);
304  enqueue(p);
305  goto unstable;
306  default:
307  GECODE_NEVER;
308  }
309  }
310  stable:
311  pc.p.ei.other();
312  /*
313  * Find the next brancher that has still alternatives left
314  *
315  * It is important to note that branchers reporting to have no more
316  * alternatives left cannot be deleted. They cannot be deleted
317  * as there might be choices to be used in commit
318  * that refer to one of these branchers. This e.g. happens when
319  * we combine branch-and-bound search with adaptive recomputation: during
320  * recomputation, a copy is constrained to be better than the currently
321  * best solution, then the first half of the choices are posted,
322  * and a fixpoint computed (for storing in the middle of the path). Then
323  * the remaining choices are posted, and because of the additional
324  * constraints that the space must be better than the previous solution,
325  * the corresponding Branchers may already have no alternatives left.
326  *
327  * The same situation may arise due to weakly monotonic propagators.
328  *
329  * A brancher reporting that no more alternatives exist is exhausted.
330  * All exhausted branchers will be left of the current pointer b_status.
331  * Only when it is known that no more choices
332  * can be used for commit an exhausted brancher can actually be deleted.
333  * This becomes known when choice is called.
334  */
335  while (b_status != Brancher::cast(&bl))
336  if (b_status->status(*this)) {
337  // Brancher still has choices to generate
338  s = SS_BRANCH; goto exit;
339  } else {
340  // Brancher is exhausted
341  b_status = Brancher::cast(b_status->next());
342  }
343  // No brancher with alternatives left, space is solved
344  s = SS_SOLVED;
345  exit:
346  stat.wmp = (wmp() > 0U);
347  if (wmp() == 1U)
348  wmp(0U);
349  return s;
350  }
351 
352 
353  const Choice*
355  if (!stable())
356  throw SpaceNotStable("Space::choice");
357  if (failed() || (b_status == Brancher::cast(&bl))) {
358  // There are no more choices to be generated
359  // Delete all branchers
360  Brancher* b = Brancher::cast(bl.next());
361  while (b != Brancher::cast(&bl)) {
362  Brancher* d = b;
363  b = Brancher::cast(b->next());
364  rfree(d,d->dispose(*this));
365  }
366  bl.init();
367  b_status = b_commit = Brancher::cast(&bl);
368  return NULL;
369  }
370  /*
371  * The call to choice() says that no older choices
372  * can be used. Hence, all branchers that are exhausted can be deleted.
373  */
374  Brancher* b = Brancher::cast(bl.next());
375  while (b != b_status) {
376  Brancher* d = b;
377  b = Brancher::cast(b->next());
378  d->unlink();
379  rfree(d,d->dispose(*this));
380  }
381  // Make sure that b_commit does not point to a deleted brancher!
382  b_commit = b_status;
383  return b_status->choice(*this);
384  }
385 
386  const Choice*
387  Space::choice(Archive& e) const {
388  unsigned int id; e >> id;
389  Brancher* b_cur = Brancher::cast(bl.next());
390  while (b_cur != Brancher::cast(&bl)) {
391  if (id == b_cur->id())
392  return b_cur->choice(*this,e);
393  b_cur = Brancher::cast(b_cur->next());
394  }
395  throw SpaceNoBrancher("Space::choice");
396  }
397 
398  void
399  Space::_commit(const Choice& c, unsigned int a) {
400  if (a >= c.alternatives())
401  throw SpaceIllegalAlternative("Space::commit");
402  if (failed())
403  return;
404  if (Brancher* b = brancher(c.bid)) {
405  // There is a matching brancher
406  pc.p.ei.brancher(*b);
407  ExecStatus es = b->commit(*this,c,a);
408  pc.p.ei.other();
409  if (es == ES_FAILED)
410  fail();
411  } else {
412  // There is no matching brancher!
413  throw SpaceNoBrancher("Space::commit");
414  }
415  }
416 
417  void
418  Space::_trycommit(const Choice& c, unsigned int a) {
419  if (a >= c.alternatives())
420  throw SpaceIllegalAlternative("Space::commit");
421  if (failed())
422  return;
423  if (Brancher* b = brancher(c.bid)) {
424  // There is a matching brancher
425  pc.p.ei.brancher(*b);
426  ExecStatus es = b->commit(*this,c,a);
427  pc.p.ei.other();
428  if (es == ES_FAILED)
429  fail();
430  }
431  }
432 
433  NGL*
434  Space::ngl(const Choice& c, unsigned int a) {
435  if (a >= c.alternatives())
436  throw SpaceIllegalAlternative("Space::ngl");
437  if (failed())
438  return NULL;
439  if (Brancher* b = brancher(c.bid)) {
440  // There is a matching brancher
441  return b->ngl(*this,c,a);
442  } else {
443  return NULL;
444  }
445  }
446 
447  void
448  Space::print(const Choice& c, unsigned int a, std::ostream& o) const {
449  if (a >= c.alternatives())
450  throw SpaceIllegalAlternative("Space::print");
451  if (failed())
452  return;
453  if (Brancher* b = const_cast<Space&>(*this).brancher(c.bid)) {
454  // There is a matching brancher
455  b->print(*this,c,a,o);
456  } else {
457  // There is no matching brancher!
458  throw SpaceNoBrancher("Space::print");
459  }
460  }
461 
462  void
463  Space::kill_brancher(unsigned int id) {
464  if (failed())
465  return;
466  for (Brancher* b = Brancher::cast(bl.next());
467  b != Brancher::cast(&bl); b = Brancher::cast(b->next()))
468  if (b->id() == id) {
469  kill(*b);
470  return;
471  }
472  }
473 
474 
475  /*
476  * Space cloning
477  *
478  * Cloning is performed in two steps:
479  * - The space itself is copied by the copy constructor. This
480  * also copies all propagators, branchers, and variables.
481  * The copied variables are recorded.
482  * - In the second step the dependency information of the recorded
483  * variables is updated and their forwarding information is reset.
484  *
485  */
486  Space::Space(bool share, Space& s)
487  : sm(s.sm->copy(share)),
488  mm(sm,s.mm,s.pc.p.n_sub*sizeof(Propagator**)),
489  gpi(s.gpi),
490  d_fst(&Actor::sentinel),
491  _wmp_afc(s._wmp_afc) {
492 #ifdef GECODE_HAS_VAR_DISPOSE
493  for (int i=0; i<AllVarConf::idx_d; i++)
494  _vars_d[i] = NULL;
495 #endif
496  for (int i=0; i<AllVarConf::idx_c; i++)
497  pc.c.vars_u[i] = NULL;
498  pc.c.vars_noidx = NULL;
499  pc.c.shared = NULL;
500  pc.c.local = NULL;
501  // Copy all propagators
502  {
503  ActorLink* p = &pl;
504  ActorLink* e = &s.pl;
505  for (ActorLink* a = e->next(); a != e; a = a->next()) {
506  Actor* c = Actor::cast(a)->copy(*this,share);
507  // Link copied actor
508  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
509  // Note that forwarding is done in the constructors
510  p = c;
511  }
512  // Link last actor
513  p->next(&pl); pl.prev(p);
514  }
515  // Copy all branchers
516  {
517  ActorLink* p = &bl;
518  ActorLink* e = &s.bl;
519  for (ActorLink* a = e->next(); a != e; a = a->next()) {
520  Actor* c = Actor::cast(a)->copy(*this,share);
521  // Link copied actor
522  p->next(ActorLink::cast(c)); ActorLink::cast(c)->prev(p);
523  // Note that forwarding is done in the constructors
524  p = c;
525  }
526  // Link last actor
527  p->next(&bl); bl.prev(p);
528  }
529  // Setup brancher pointers
530  if (s.b_status == &s.bl) {
531  b_status = Brancher::cast(&bl);
532  } else {
533  b_status = Brancher::cast(s.b_status->prev());
534  }
535  if (s.b_commit == &s.bl) {
536  b_commit = Brancher::cast(&bl);
537  } else {
538  b_commit = Brancher::cast(s.b_commit->prev());
539  }
540  }
541 
542  Space*
543  Space::_clone(bool share_data, bool share_info) {
544  if (failed())
545  throw SpaceFailed("Space::clone");
546  if (!stable())
547  throw SpaceNotStable("Space::clone");
548 
549  // Copy all data structures (which in turn will invoke the constructor)
550  Space* c = copy(share_data);
551 
552  if (c->d_fst != &Actor::sentinel)
553  throw SpaceNotCloned("Space::clone");
554 
555  // Setup array for actor disposal in c
556  {
557  unsigned int n = static_cast<unsigned int>(d_cur - d_fst);
558  if (n == 0) {
559  // No actors
560  c->d_fst = c->d_cur = c->d_lst = NULL;
561  } else {
562  // Leave one entry free
563  c->d_fst = c->alloc<Actor*>(n+1);
564  c->d_cur = c->d_fst;
565  c->d_lst = c->d_fst+n+1;
566  for (Actor** d_fst_iter = d_fst; d_fst_iter != d_cur; d_fst_iter++) {
567  if ((*d_fst_iter)->prev())
568  *(c->d_cur++) = Actor::cast((*d_fst_iter)->prev());
569  }
570  }
571  }
572 
573  // Update variables without indexing structure
575  static_cast<VarImp<NoIdxVarImpConf>*>(c->pc.c.vars_noidx);
576  while (x != NULL) {
577  VarImp<NoIdxVarImpConf>* n = x->next();
578  x->b.base = NULL; x->u.idx[0] = 0;
579  if (sizeof(ActorLink**) > sizeof(unsigned int))
580  *(1+&x->u.idx[0]) = 0;
581  x = n;
582  }
583  // Update variables with indexing structure
584  c->update(static_cast<ActorLink**>(c->mm.subscriptions()));
585 
586  // Re-establish prev links (reset forwarding information)
587  {
588  ActorLink* p_a = &pl;
589  ActorLink* c_a = p_a->next();
590  // First update propagators and advisors
591  while (c_a != &pl) {
592  Propagator* p = Propagator::cast(c_a);
593  if (p->u.advisors != NULL) {
594  ActorLink* a = p->u.advisors;
595  p->u.advisors = NULL;
596  do {
597  a->prev(p); a = a->next();
598  } while (a != NULL);
599  }
600  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
601  }
602  }
603  {
604  ActorLink* p_a = &bl;
605  ActorLink* c_a = p_a->next();
606  // Update branchers
607  while (c_a != &bl) {
608  c_a->prev(p_a); p_a = c_a; c_a = c_a->next();
609  }
610  }
611 
612  // Reset links for shared objects
613  for (SharedHandle::Object* s = c->pc.c.shared; s != NULL; s = s->next)
614  s->fwd = NULL;
615 
616  // Reset links for local objects
617  for (ActorLink* l = c->pc.c.local; l != NULL; l = l->next())
618  l->prev(NULL);
619 
620  // Initialize propagator queue
621  c->pc.p.active = &c->pc.p.queue[0]-1;
622  for (int i=0; i<=PropCost::AC_MAX; i++)
623  c->pc.p.queue[i].init();
624  // Copy propagation only data
625  c->pc.p.n_sub = pc.p.n_sub;
626  c->pc.p.bid = pc.p.bid;
627 
628  if (!share_info) {
629  // Re-allocate afc information
630  for (ActorLink* c_a = c->pl.next(); c_a != &c->pl; c_a = c_a->next()) {
631  Propagator* p = Propagator::cast(c_a);
632  GPI::Info* gpi = c->gpi.allocate(p->gpi().gid);
633  if (p->disabled())
634  p->gpi_disabled = Support::mark(gpi);
635  else
636  p->gpi_disabled = gpi;
637  }
638  }
639  // Reset execution information
640  c->pc.p.ei.other(); pc.p.ei.other();
641 
642  return c;
643  }
644 
645  void
647  }
648 
649  bool
650  Space::master(const MetaInfo& mi) {
651  switch (mi.type()) {
652  case MetaInfo::RESTART:
653  if (mi.last() != NULL)
654  constrain(*mi.last());
655  mi.nogoods().post(*this);
656  // Perform a restart even if a solution has been found
657  return true;
658  case MetaInfo::PORTFOLIO:
659  // Kill all branchers
660  BrancherGroup::all.kill(*this);
661  return true;
662  default: GECODE_NEVER;
663  return true;
664  }
665  }
666 
667  bool
669  return true;
670  }
671 
672 
673  void
674  LocalObject::fwdcopy(Space& home, bool share) {
675  ActorLink::cast(this)->prev(copy(home,share));
676  next(home.pc.c.local);
677  home.pc.c.local = this;
678  }
679 
680  void
682  e << id();
683  }
684 
685  void
686  Space::afc_decay(double d) {
687  afc_enable();
688  // Commit outstanding decay operations
689  if (gpi.decay() != 1.0)
690  for (Propagators p(*this); p(); ++p)
691  (void) gpi.afc(p.propagator().gpi());
692  gpi.decay(d);
693  }
694 
695  void
696  Space::afc_set(double a) {
697  afc_enable();
698  for (Propagators p(*this); p(); ++p)
699  gpi.set(p.propagator().gpi(),a);
700  }
701 
702 
703  bool
704  NGL::notice(void) const {
705  return false;
706  }
707 
708  NGL::~NGL(void) {
709  }
710 
711 
712  /*
713  * Groups
714  */
715 
716  Group Group::all(GROUPID_ALL);
717  Group Group::def(GROUPID_DEF);
718 
721 
722  BrancherGroup BrancherGroup::all(GROUPID_ALL);
723  BrancherGroup BrancherGroup::def(GROUPID_DEF);
724 
725  unsigned int Group::next = GROUPID_DEF+1;
727 
728 
729  Group::Group(void) {
730  m.acquire();
731  gid = next++;
732  m.release();
733  if (gid == GROUPID_MAX)
734  throw TooManyGroups("Group::Group");
735  }
736 
737 
740  if ((id() != GROUPID_ALL) && (id() != g.id()))
741  for (Space::Propagators ps(home); ps(); ++ps)
742  if (g.in(ps.propagator().group()))
743  ps.propagator().group(*this);
744  return *this;
745  }
746 
748  PropagatorGroup::move(Space& home, unsigned int pid) {
749  if (id() == GROUPID_ALL)
750  return *this;
751  for (Space::Propagators ps(home); ps(); ++ps)
752  if (ps.propagator().id() == pid) {
753  ps.propagator().group(*this);
754  return *this;
755  }
756  throw UnknownPropagator("PropagatorGroup::move");
757  GECODE_NEVER;
758  return *this;
759  }
760 
761  unsigned int
763  if (home.failed())
764  return 0;
765  unsigned int n=0;
766  for (Space::Propagators ps(home); ps(); ++ps)
767  if (in(ps.propagator().group()))
768  n++;
769  return n;
770  }
771 
772  void
774  if (home.failed())
775  return;
776  Space::Propagators ps(home);
777  while (ps()) {
778  Propagator& p = ps.propagator();
779  ++ps;
780  if (in(p.group()))
781  home.kill(p);
782  }
783  }
784 
785  void
787  if (home.failed())
788  return;
789  for (Space::Propagators ps(home); ps(); ++ps)
790  if (in(ps.propagator().group()))
791  ps.propagator().disable();
792  }
793 
794  void
796  if (home.failed())
797  return;
798  if (s) {
799  Space::Propagators ps(home);
800  while (ps()) {
801  Propagator& p = ps.propagator();
802  ++ps;
803  if (in(p.group())) {
804  p.enable();
805  p.reschedule(home);
806  }
807  }
808  } else {
809  for (Space::Propagators ps(home); ps(); ++ps)
810  if (in(ps.propagator().group()))
811  ps.propagator().enable();
812  }
813  }
814 
815 
818  if ((id() != GROUPID_ALL) && (id() != g.id()))
819  for (Space::Branchers bs(home); bs(); ++bs)
820  if (g.in(bs.brancher().group()))
821  bs.brancher().group(*this);
822  return *this;
823  }
824 
826  BrancherGroup::move(Space& home, unsigned int bid) {
827  if (id() == GROUPID_ALL)
828  return *this;
829  for (Space::Branchers bs(home); bs(); ++bs)
830  if (bs.brancher().id() == bid) {
831  bs.brancher().group(*this);
832  return *this;
833  }
834  throw UnknownBrancher("BrancherGroup::move");
835  GECODE_NEVER;
836  return *this;
837  }
838 
839  unsigned int
840  BrancherGroup::size(Space& home) const {
841  if (home.failed())
842  return 0;
843  unsigned int n=0;
844  for (Space::Branchers bs(home); bs(); ++bs)
845  if (in(bs.brancher().group()))
846  n++;
847  return n;
848  }
849 
850  void
852  if (home.failed())
853  return;
854  Space::Branchers bs(home);
855  while (bs()) {
856  Brancher& b = bs.brancher();
857  ++bs;
858  if (in(b.group()))
859  home.kill(b);
860  }
861  }
862 
863 
864 }
865 
866 // STATISTICS: kernel-core
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3689
friend class Branchers
Definition: core.hpp:1679
Base-class for variable implementations.
Definition: core.hpp:230
virtual Space * copy(bool share)=0
Copying member function.
Space must be branched (at least one brancher left)
Definition: core.hpp:1613
unsigned int bid
Id of next brancher to be created.
Definition: core.hpp:1752
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
static BrancherGroup all
Group of all branchers.
Definition: core.hpp:896
bool in(Group a) const
Check whether actor group a is included in this group.
Definition: core.hpp:4737
void afc_set(double a)
Reset AFC to a.
Definition: core.cpp:696
virtual void print(const Space &home, const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition: core.cpp:95
void kill(Space &home)
Kill all branchers in a group.
Definition: core.cpp:851
Actor must always be disposed.
Definition: core.hpp:626
Gecode::ActorLink * advisors
A list of advisors (used during cloning)
Definition: core.hpp:1026
SpaceStatus
Space status
Definition: core.hpp:1610
virtual void reschedule(Space &home)=0
Schedule function.
Group of branchers.
Definition: core.hpp:848
void * subscriptions(void) const
Get the memory area for subscriptions.
void disable(Space &home)
Disable all propagators in a group.
Definition: core.cpp:786
static PropagatorGroup all
Group of all propagators.
Definition: core.hpp:838
static BrancherGroup def
Group of branchers not in any user-defined group.
Definition: core.hpp:899
Statistics for execution of commit
Definition: core.hpp:1656
virtual void post(Space &home) const
Post no-goods.
Definition: core.cpp:80
Exception: unknown brancher
Definition: exception.hpp:104
virtual NGL * ngl(Space &home, const Choice &c, unsigned int a) const
Create no-good literal for choice c and alternative a.
Definition: core.cpp:90
Base-class for propagators.
Definition: core.hpp:1012
Internal: propagator is subsumed, do not use.
Definition: core.hpp:537
Information is provided by a restart-based engine.
Definition: core.hpp:1547
Exception: Commit with illegal alternative
Definition: exception.hpp:76
Base-class for advisors.
Definition: core.hpp:1212
bool wmp
Whether a weakly monotonic propagator might have been executed.
Definition: core.hpp:1625
Exception: too many groups
Definition: exception.hpp:83
Exception: Operation on failed space invoked
Definition: exception.hpp:48
static Group def
Group of actors not in any user-defined group.
Definition: core.hpp:771
void kill(Space &home)
Kill all propagators in a group.
Definition: core.cpp:773
void * mark(void *p)
Return marked pointer for p.
BrancherGroup & move(Space &home, BrancherGroup g)
Move branchers from group g to this group.
Definition: core.cpp:817
Base-class for variable implementations.
Definition: core.hpp:245
unsigned long int propagate
Number of propagator executions.
Definition: core.hpp:1623
Propagation has computed fixpoint.
Definition: core.hpp:541
unsigned int id(void) const
Return a unique id for the group.
Definition: core.hpp:4755
Computation spaces.
Definition: core.hpp:1672
virtual bool status(const Space &home) const =0
Check status of brancher, return true if alternatives left.
unsigned int size(Space &home) const
Return number of propagators in a group.
Definition: core.cpp:762
Base-class for both propagators and branchers.
Definition: core.hpp:682
Statistics for execution of status
Definition: core.hpp:1620
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2783
virtual ~Actor(void)
To avoid warnings.
Definition: core.cpp:59
PropagatorGroup & move(Space &home, PropagatorGroup g)
Move propagators from group g to this group.
Definition: core.cpp:739
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition: core.cpp:448
void decay(double d)
Set decay factor to d.
Definition: gpi.hpp:348
Maximal cost value.
Definition: core.hpp:570
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Base-class for branchers.
Definition: core.hpp:1364
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
BrancherGroup group(void) const
Return group brancher belongs to.
Definition: core.hpp:3553
Exception: Operation on not stable space invoked
Definition: exception.hpp:55
double afc_decay(void) const
Return AFC decay factor.
Definition: core.hpp:3276
struct Gecode::Space::@55::@56 p
Data only available during propagation or branching.
void release(SharedMemory *sm)
Release all allocated heap chunks.
Execution has resulted in failure.
Definition: core.hpp:538
const Space * last(void) const
Return last solution found (possibly NULL)
Definition: core.hpp:3118
Exception: unknown propagator
Definition: exception.hpp:90
Info * allocate(unsigned int gid)
Allocate new actor info.
Definition: gpi.hpp:356
Statistics for execution of clone
Definition: core.hpp:1640
Type type(void) const
Return type of information.
Definition: core.hpp:3099
unsigned int size(Space &home) const
Return number of branchers in a group.
Definition: core.cpp:840
bool failed(void) const
Check whether space is failed.
Definition: core.hpp:3963
ModEventDelta med
A set of modification events (used during propagation)
Definition: core.hpp:1022
unsigned int n_sub
Number of subscriptions.
Definition: core.hpp:1754
void fail(void)
Fail space.
Definition: core.hpp:3949
Group(void)
Constructor.
Definition: core.cpp:729
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:646
virtual ~Space(void)
Destructor.
Definition: core.cpp:199
bool stable(void) const
Return if space is stable (at fixpoint or failed)
Definition: core.hpp:3972
virtual const Choice * choice(Space &home)=0
Return choice.
void set(Info &c, double a)
Set failure count to a.
Definition: gpi.hpp:320
PropagatorGroup group(void) const
Return group propagator belongs to.
Definition: core.hpp:3468
void flush(void)
Flush cached memory blocks.
Definition: core.cpp:194
size_t size
The size of the propagator (used during subsumption)
Definition: core.hpp:1024
static Support::Mutex m
Mutex for protection.
Definition: core.hpp:746
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Advise function.
Definition: core.cpp:69
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition: core.cpp:668
Group baseclass for controlling actors.
Definition: core.hpp:727
bool disabled(void) const
Whether propagator is currently disabled.
Definition: core.hpp:3412
Exception: Copy constructor did not call base class copy constructor
Definition: exception.hpp:62
Information is provided by a portfolio-based engine.
Definition: core.hpp:1549
static unsigned int next
Next group id.
Definition: core.hpp:743
IntPropLevel sm(IntPropLevel ipl)
Extract speed or memory from propagation level.
Definition: ipl.hpp:47
double afc(Info &c)
Return failure count.
Definition: gpi.hpp:328
const NoGoods & nogoods(void) const
Return no-goods recorded from restart.
Definition: core.hpp:3123
unsigned int id(void) const
Return brancher id.
Definition: core.hpp:3548
static PropagatorGroup def
Group of propagators not in any user-defined group.
Definition: core.hpp:841
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:277
Space(void)
Default constructor.
Definition: core.cpp:112
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition: core.cpp:167
static const int idx_c
Index for cloning.
Definition: var-type.hpp:459
virtual void archive(Archive &e) const
Archive into e.
Definition: core.cpp:681
Choice for performing commit
Definition: core.hpp:1332
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition: core.cpp:134
unsigned int gid
Group identifier.
Definition: gpi.hpp:51
struct Gecode::Space::@55::@57 c
Data available only during copying.
No-goods recorded from restarts.
Definition: core.hpp:1517
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3281
Archive representation
Definition: archive.hpp:45
Exception: Commit when no brancher present
Definition: exception.hpp:69
ExecStatus
Definition: core.hpp:536
void enable(Space &home, bool s=true)
Enable all propagators in a group.
Definition: core.cpp:795
void enable(void)
Enable propagator.
Definition: core.hpp:3422
virtual bool notice(void) const
Whether dispose must always be called (returns false)
Definition: core.cpp:704
void fail(Info &c)
Increment failure count.
Definition: gpi.hpp:312
virtual bool master(const MetaInfo &mi)
Master configuration function for meta search engines.
Definition: core.cpp:650
virtual ~NGL(void)
To avoid warnings.
Definition: core.cpp:708
static NoGoods eng
Empty no-goods.
Definition: core.hpp:1535
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:234
Internal: propagator has computed partial fixpoint, do not use.
Definition: core.hpp:543
The shared object.
Definition: core.hpp:88
Propagation has not computed fixpoint.
Definition: core.hpp:539
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)=0
Propagation function.
virtual void dispose(Space &home, VarImpBase *x)
Dispose list of variable implementations starting at x.
Definition: core.cpp:47
Gecode toplevel namespace
static Group all
Group of all actors.
Definition: core.hpp:768
Information passed by meta search engines.
Definition: core.hpp:1542
friend class Propagators
Definition: core.hpp:1676
Class for storing timed-decay value.
Definition: gpi.hpp:46
Group of propagators.
Definition: core.hpp:778
ActorProperty
Actor properties.
Definition: core.hpp:617
virtual ~VarImpDisposerBase(void)
Destructor (not used)
Definition: core.cpp:49
Space is failed
Definition: core.hpp:1611
const Choice * choice(void)
Create new choice for current brancher.
Definition: core.cpp:354
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
static const int idx_d
Index for dispose.
Definition: var-type.hpp:461
Shared object for several memory areas.
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
NGL * ngl(const Choice &c, unsigned int a)
Create no-good literal for choice c and alternative a.
Definition: core.cpp:434
void flush(void)
Flush all cached memory.
Base class for Variable type disposer.
Definition: core.hpp:253
GPI::Info & gpi(void)
Provide access to global propagator information.
Definition: core.hpp:3427
void rfree(void *p, size_t s)
Free memory previously allocated with alloc (might be reused later)
Definition: core.hpp:2749
bool release(void)
Release by one space.
Space is solved (no brancher left)
Definition: core.hpp:1612
No-good literal recorded during search.
Definition: core.hpp:1260