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
00035
00036
00037
00038 namespace Gecode { namespace Gist {
00039
00040 template<class T>
00041 void
00042 NodeAllocatorBase<T>::allocate(void) {
00043 cur_b++;
00044 cur_t = 0;
00045 if (cur_b==n) {
00046 int oldn = n;
00047 n = static_cast<int>(n*1.5+1.0);
00048 b = heap.realloc<Block*>(b,oldn,n);
00049 }
00050 b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
00051 }
00052
00053 template<class T>
00054 NodeAllocatorBase<T>::NodeAllocatorBase(bool bab)
00055 : _bab(bab) {
00056 b = heap.alloc<Block*>(10);
00057 n = 10;
00058 cur_b = -1;
00059 cur_t = NodeBlockSize-1;
00060 }
00061
00062 template<class T>
00063 NodeAllocatorBase<T>::~NodeAllocatorBase(void) {
00064 for (int i=cur_b+1; i--;)
00065 heap.rfree(b[i]);
00066 heap.free<Block*>(b,n);
00067 }
00068
00069 template<class T>
00070 forceinline int
00071 NodeAllocatorBase<T>::allocate(int p) {
00072 cur_t++;
00073 if (cur_t==NodeBlockSize)
00074 allocate();
00075 new (&b[cur_b]->b[cur_t]) T(p);
00076 b[cur_b]->best[cur_t] = -1;
00077 return cur_b*NodeBlockSize+cur_t;
00078 }
00079
00080 template<class T>
00081 forceinline int
00082 NodeAllocatorBase<T>::allocate(Space* root) {
00083 cur_t++;
00084 if (cur_t==NodeBlockSize)
00085 allocate();
00086 new (&b[cur_b]->b[cur_t]) T(root);
00087 b[cur_b]->best[cur_t] = -1;
00088 return cur_b*NodeBlockSize+cur_t;
00089 }
00090
00091 template<class T>
00092 forceinline T*
00093 NodeAllocatorBase<T>::operator [](int i) const {
00094 assert(i/NodeBlockSize < n);
00095 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
00096 return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
00097 }
00098
00099 template<class T>
00100 forceinline T*
00101 NodeAllocatorBase<T>::best(int i) const {
00102 assert(i/NodeBlockSize < n);
00103 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
00104 int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
00105 return bi == -1 ? NULL : (*this)[bi];
00106 }
00107
00108 template<class T>
00109 forceinline void
00110 NodeAllocatorBase<T>::setBest(int i, int best) {
00111 assert(i/NodeBlockSize < n);
00112 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
00113 b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
00114 }
00115
00116 template<class T>
00117 forceinline bool
00118 NodeAllocatorBase<T>::bab(void) const {
00119 return _bab;
00120 }
00121
00122 template<class T>
00123 forceinline bool
00124 NodeAllocatorBase<T>::showLabels(void) const {
00125 return !labels.isEmpty();
00126 }
00127
00128 template<class T>
00129 bool
00130 NodeAllocatorBase<T>::hasLabel(T* n) const {
00131 return labels.contains(n);
00132 }
00133
00134 template<class T>
00135 void
00136 NodeAllocatorBase<T>::setLabel(T* n, const QString& l) {
00137 labels[n] = l;
00138 }
00139
00140 template<class T>
00141 void
00142 NodeAllocatorBase<T>::clearLabel(T* n) {
00143 labels.remove(n);
00144 }
00145
00146 template<class T>
00147 QString
00148 NodeAllocatorBase<T>::getLabel(T* n) const {
00149 return labels.value(n);
00150 }
00151
00152 forceinline unsigned int
00153 Node::getTag(void) const {
00154 return static_cast<unsigned int>
00155 (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
00156 }
00157
00158 forceinline void
00159 Node::setTag(unsigned int tag) {
00160 assert(tag <= 3);
00161 assert(getTag() == UNDET);
00162 childrenOrFirstChild = reinterpret_cast<void*>
00163 ( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
00164 }
00165
00166 forceinline void*
00167 Node::getPtr(void) const {
00168 return reinterpret_cast<void*>
00169 (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
00170 }
00171
00172 forceinline int
00173 Node::getFirstChild(void) const {
00174 return static_cast<int>
00175 ((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
00176 }
00177
00178 forceinline
00179 Node::Node(int p, bool failed) : parent(p) {
00180 childrenOrFirstChild = NULL;
00181 noOfChildren = 0;
00182 setTag(failed ? LEAF : UNDET);
00183 }
00184
00185 forceinline int
00186 Node::getParent(void) const {
00187 return parent;
00188 }
00189
00190 forceinline VisualNode*
00191 Node::getParent(const NodeAllocator& na) const {
00192 return parent < 0 ? NULL : na[parent];
00193 }
00194
00195 forceinline bool
00196 Node::isUndetermined(void) const { return getTag() == UNDET; }
00197
00198 forceinline int
00199 Node::getChild(int n) const {
00200 assert(getTag() != UNDET && getTag() != LEAF);
00201 if (getTag() == TWO_CHILDREN) {
00202 assert(n != 1 || noOfChildren <= 0);
00203 return n == 0 ? getFirstChild() : -noOfChildren;
00204 }
00205 assert(n < noOfChildren);
00206 return static_cast<int*>(getPtr())[n];
00207 }
00208
00209 forceinline VisualNode*
00210 Node::getChild(const NodeAllocator& na, int n) const {
00211 return na[getChild(n)];
00212 }
00213
00214 forceinline bool
00215 Node::isRoot(void) const { return parent == -1; }
00216
00217 forceinline unsigned int
00218 Node::getNumberOfChildren(void) const {
00219 switch (getTag()) {
00220 case UNDET:
00221 case LEAF:
00222 return 0;
00223 case TWO_CHILDREN:
00224 return (noOfChildren <= 0) ? 2 : 1;
00225 default:
00226 return static_cast<unsigned int>(noOfChildren);
00227 }
00228 }
00229
00230 forceinline int
00231 Node::getIndex(const NodeAllocator& na) const {
00232 if (parent==-1)
00233 return 0;
00234 Node* p = na[parent];
00235 for (int i=p->getNumberOfChildren(); i--;)
00236 if (p->getChild(na,i) == this)
00237 return p->getChild(i);
00238 GECODE_NEVER;
00239 return -1;
00240 }
00241
00242 }}
00243
00244