Generated on Fri Oct 19 11:24:59 2018 for Gecode by doxygen 1.6.3

node.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2006
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  * Permission is hereby granted, free of charge, to any person obtaining
00014  * a copy of this software and associated documentation files (the
00015  * "Software"), to deal in the Software without restriction, including
00016  * without limitation the rights to use, copy, modify, merge, publish,
00017  * distribute, sublicense, and/or sell copies of the Software, and to
00018  * permit persons to whom the Software is furnished to do so, subject to
00019  * the following conditions:
00020  *
00021  * The above copyright notice and this permission notice shall be
00022  * included in all copies or substantial portions of the Software.
00023  *
00024  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 namespace Gecode { namespace Gist {
00035 
00036   template<class T>
00037   void
00038   NodeAllocatorBase<T>::allocate(void) {
00039     cur_b++;
00040     cur_t = 0;
00041     if (cur_b==n) {
00042       int oldn = n;
00043       n = static_cast<int>(n*1.5+1.0);
00044       b = heap.realloc<Block*>(b,oldn,n);
00045     }
00046     b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
00047   }
00048 
00049   template<class T>
00050   NodeAllocatorBase<T>::NodeAllocatorBase(bool bab)
00051     : _bab(bab) {
00052     b = heap.alloc<Block*>(10);
00053     n = 10;
00054     cur_b = -1;
00055     cur_t = NodeBlockSize-1;
00056   }
00057 
00058   template<class T>
00059   NodeAllocatorBase<T>::~NodeAllocatorBase(void) {
00060     for (int i=cur_b+1; i--;)
00061       heap.rfree(b[i]);
00062     heap.free<Block*>(b,n);
00063   }
00064 
00065   template<class T>
00066   forceinline int
00067   NodeAllocatorBase<T>::allocate(int p) {
00068     cur_t++;
00069     if (cur_t==NodeBlockSize)
00070       allocate();
00071     new (&b[cur_b]->b[cur_t]) T(p);
00072     b[cur_b]->best[cur_t] = -1;
00073     return cur_b*NodeBlockSize+cur_t;
00074   }
00075 
00076   template<class T>
00077   forceinline int
00078   NodeAllocatorBase<T>::allocate(Space* root) {
00079     cur_t++;
00080     if (cur_t==NodeBlockSize)
00081       allocate();
00082     new (&b[cur_b]->b[cur_t]) T(root);
00083     b[cur_b]->best[cur_t] = -1;
00084     return cur_b*NodeBlockSize+cur_t;
00085   }
00086 
00087   template<class T>
00088   forceinline T*
00089   NodeAllocatorBase<T>::operator [](int i) const {
00090     assert(i/NodeBlockSize < n);
00091     assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
00092     return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
00093   }
00094 
00095   template<class T>
00096   forceinline T*
00097   NodeAllocatorBase<T>::best(int i) const {
00098     assert(i/NodeBlockSize < n);
00099     assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
00100     int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
00101     return bi == -1 ? NULL : (*this)[bi];
00102   }
00103 
00104   template<class T>
00105   forceinline void
00106   NodeAllocatorBase<T>::setBest(int i, int best) {
00107     assert(i/NodeBlockSize < n);
00108     assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
00109     b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
00110   }
00111 
00112   template<class T>
00113   forceinline bool
00114   NodeAllocatorBase<T>::bab(void) const {
00115     return _bab;
00116   }
00117 
00118   template<class T>
00119   forceinline bool
00120   NodeAllocatorBase<T>::showLabels(void) const {
00121     return !labels.isEmpty();
00122   }
00123 
00124   template<class T>
00125   bool
00126   NodeAllocatorBase<T>::hasLabel(T* n) const {
00127     return labels.contains(n);
00128   }
00129 
00130   template<class T>
00131   void
00132   NodeAllocatorBase<T>::setLabel(T* n, const QString& l) {
00133     labels[n] = l;
00134   }
00135 
00136   template<class T>
00137   void
00138   NodeAllocatorBase<T>::clearLabel(T* n) {
00139     labels.remove(n);
00140   }
00141 
00142   template<class T>
00143   QString
00144   NodeAllocatorBase<T>::getLabel(T* n) const {
00145     return labels.value(n);
00146   }
00147 
00148   forceinline unsigned int
00149   Node::getTag(void) const {
00150     return static_cast<unsigned int>
00151       (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
00152   }
00153 
00154   forceinline void
00155   Node::setTag(unsigned int tag) {
00156     assert(tag <= 3);
00157     assert(getTag() == UNDET);
00158     childrenOrFirstChild = reinterpret_cast<void*>
00159       ( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
00160   }
00161 
00162   forceinline void*
00163   Node::getPtr(void) const {
00164     return reinterpret_cast<void*>
00165       (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
00166   }
00167 
00168   forceinline int
00169   Node::getFirstChild(void) const {
00170     return static_cast<int>
00171       ((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
00172   }
00173 
00174   forceinline
00175   Node::Node(int p, bool failed) : parent(p) {
00176     childrenOrFirstChild = NULL;
00177     noOfChildren = 0;
00178     setTag(failed ? LEAF : UNDET);
00179   }
00180 
00181   forceinline int
00182   Node::getParent(void) const {
00183     return parent;
00184   }
00185 
00186   forceinline VisualNode*
00187   Node::getParent(const NodeAllocator& na) const {
00188     return parent < 0 ? NULL : na[parent];
00189   }
00190 
00191   forceinline bool
00192   Node::isUndetermined(void) const { return getTag() == UNDET; }
00193 
00194   forceinline int
00195   Node::getChild(int n) const {
00196     assert(getTag() != UNDET && getTag() != LEAF);
00197     if (getTag() == TWO_CHILDREN) {
00198       assert(n != 1 || noOfChildren <= 0);
00199       return n == 0 ? getFirstChild() : -noOfChildren;
00200     }
00201     assert(n < noOfChildren);
00202     return static_cast<int*>(getPtr())[n];
00203   }
00204 
00205   forceinline VisualNode*
00206   Node::getChild(const NodeAllocator& na, int n) const {
00207     return na[getChild(n)];
00208   }
00209 
00210   forceinline bool
00211   Node::isRoot(void) const { return parent == -1; }
00212 
00213   forceinline unsigned int
00214   Node::getNumberOfChildren(void) const {
00215     switch (getTag()) {
00216     case UNDET:
00217     case LEAF:
00218       return 0;
00219     case TWO_CHILDREN:
00220       return (noOfChildren <= 0) ? 2 : 1;
00221     default:
00222       return static_cast<unsigned int>(noOfChildren);
00223     }
00224   }
00225 
00226   forceinline int
00227   Node::getIndex(const NodeAllocator& na) const {
00228     if (parent==-1)
00229       return 0;
00230     Node* p = na[parent];
00231     for (int i=p->getNumberOfChildren(); i--;)
00232       if (p->getChild(na,i) == this)
00233         return p->getChild(i);
00234     GECODE_NEVER;
00235     return -1;
00236   }
00237 
00238 }}
00239 
00240 // STATISTICS: gist-any