Generated on Thu Jul 6 07:06:49 2006 for Gecode by doxygen 1.4.7

reco-stack.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2003
00007  *
00008  *  Last modified:
00009  *     $Date: 2006-03-30 19:42:28 +0200 (Thu, 30 Mar 2006) $ by $Author: schulte $
00010  *     $Revision: 3141 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 namespace Gecode { namespace Search {
00023 
00024   /*
00025    * Node for recomputation
00026    *
00027    */
00028 
00029   forceinline
00030   ReCoNode::ReCoNode(Space* s, Space* c, unsigned int a)
00031     : _space(c), _alt(0), _last(a-1), _desc(s->description()) {}
00032 
00033 
00034   forceinline Space*
00035   ReCoNode::space(void) const {
00036     return _space;
00037   }
00038   forceinline void
00039   ReCoNode::space(Space* s) {
00040     _space = s;
00041   }
00042 
00043   forceinline unsigned int
00044   ReCoNode::alt(void) const {
00045     return _alt;
00046   }
00047   forceinline void
00048   ReCoNode::alt(unsigned int a) {
00049     _alt = a;
00050   }
00051 
00052   forceinline bool
00053   ReCoNode::rightmost(void) const {
00054     return _alt == _last;
00055   }
00056   forceinline void
00057   ReCoNode::next(void) {
00058     _alt++;
00059   }
00060 
00061   forceinline BranchingDesc*
00062   ReCoNode::desc(void) const {
00063     return _desc;
00064   }
00065   forceinline void
00066   ReCoNode::desc(BranchingDesc* d) {
00067     _desc = d;
00068   }
00069 
00070   forceinline void
00071   ReCoNode::dispose(void) {
00072     delete _space;
00073     delete _desc;
00074   }
00075 
00076   forceinline unsigned int
00077   ReCoNode::share(void) {
00078     return _last--;
00079   }
00080 
00081 
00082   /*
00083    * Depth-first stack with recomputation
00084    *
00085    */
00086 
00087   forceinline
00088   ReCoStack::ReCoStack(unsigned int a_d0) : a_d(a_d0) {}
00089 
00090   forceinline BranchingDesc*
00091   ReCoStack::push(Space* s, Space* c, unsigned int alt) {
00092     ReCoNode sn(s,c,alt);
00093     Support::DynamicStack<ReCoNode>::push(sn);
00094     return sn.desc();
00095   }
00096 
00097   forceinline bool
00098   ReCoStack::next(EngineCtrl& stat) {
00099     // Generate path for next node and return whether node exists.
00100     while (!empty()) {
00101       if (top().rightmost()) {
00102         stat.pop(top().space(),top().desc());
00103         pop().dispose();
00104       } else {
00105         top().next();
00106         return true;
00107       }
00108     }
00109     return false;
00110   }
00111 
00112   inline void
00113   ReCoStack::reset(void) {
00114     while (!empty())
00115       pop().dispose();
00116   }
00117 
00118 }}
00119 
00120 // STATISTICS: search-any