node.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
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