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 #include "dart.hh"
00026 #include <cassert>
00027 #include <cstdlib>
00028
00029 namespace GMap3d
00030 {
00031
00032 INLINE
00033 CDart* CGMapBasic::getFirstDart() const
00034 {
00035 return FFirstDart;
00036 }
00037
00038 INLINE
00039 void CGMapBasic::setFirstDart(CDart* ADart)
00040 {
00041 FFirstDart = ADart;
00042 }
00043
00044 INLINE
00045 CDart* CGMapBasic::newDart()
00046 {
00047 return new CDart(FMaskMarks);
00048 }
00049
00050 INLINE
00051 void CGMapBasic::delDart(CDart* ADart)
00052 {
00053 delete ADart;
00054 }
00055
00056 INLINE
00057 CDart* CGMapBasic::addMapDart()
00058 {
00059 CDart* ADart = newDart();
00060
00061 assert(ADart != NULL);
00062
00063
00064 if ( getFirstDart()!=NULL )
00065 {
00066 getFirstDart()->setPrev(ADart);
00067 ADart->setNext(getFirstDart());
00068 }
00069
00070 setFirstDart(ADart);
00071
00072 return ADart;
00073 }
00074
00075 INLINE
00076 void CGMapBasic::delMapDart(CDart* ADart)
00077 {
00078 assert( ADart!=NULL );
00079
00080 if ( getFirstDart()==ADart )
00081 {
00082 assert( ADart->getPrev()==NULL );
00083 setFirstDart(ADart->getNext());
00084 }
00085 else
00086 {
00087 assert( ADart->getPrev()!=NULL );
00088 ADart->getPrev()->setNext(ADart->getNext());
00089 }
00090
00091 if ( ADart->getNext()!=NULL )
00092 ADart->getNext()->setPrev(ADart->getPrev());
00093
00094 delDart(ADart);
00095 }
00096
00097 INLINE
00098 void CGMapBasic::randomizeDarts()
00099 {
00100 CDart* first = getFirstDart();
00101
00102 if (first==NULL) return;
00103
00104 CDart* current = first->getNext();
00105 CDart* tmp;
00106 CDart* next;
00107 int i, dejaTraite = 1;
00108
00109 if ( first==NULL ) return;
00110
00111 srand(time(NULL));
00112
00113 first->setNext(NULL);
00114
00115 while ( current!=NULL )
00116 {
00117 next = current->getNext();
00118
00119 i = rand()%dejaTraite;
00120 tmp = first;
00121 while ( i!=0 ) { tmp=tmp->getNext(); --i; }
00122 assert( tmp!=NULL );
00123
00124 current->setPrev( tmp->getPrev() );
00125 current->setNext( tmp );
00126 if ( tmp==first )
00127 first=current;
00128 else
00129 tmp->getPrev()->setNext(current);
00130
00131 tmp->setPrev( current );
00132
00133 current = next;
00134 ++dejaTraite;
00135 }
00136
00137 setFirstDart(first);
00138 }
00139
00140 INLINE
00141 void CGMapBasic::removeAllDarts()
00142 {
00143 CDart* d = getFirstDart();
00144 CDart* tmp;
00145
00146 while ( d!=NULL )
00147 {
00148 tmp = d;
00149 d = d->getNext();
00150 delDart(tmp);
00151 }
00152 setFirstDart(NULL);
00153 }
00154
00155 INLINE
00156 void CGMapBasic::empty()
00157 {
00158 removeAllDarts();
00159
00160
00161 FMaskMarks.reset();
00162 FUsedMarks.reset();
00163 FUsedOrbits.reset();
00164 FUsedDirectInfo.reset();
00165
00166 FNbUsedMarks = 0;
00167 FNbUsedDirectInfos = 0;
00168
00169 #ifndef NDEBUG
00170 FMaxNbUsedMarks = 0;
00171 FMaxNbUsedDirectInfos = 0;
00172 #endif // NDEBUG
00173
00174 int i;
00175
00176 for (i=0; i<NB_MARKS; ++i)
00177 FMarks[i] = i;
00178
00179 for (i=0; i<NB_DIRECT_INFO; ++i)
00180 FDirectInfos[i] = i;
00181 }
00182
00183 INLINE
00184 CGMapBasic::CGMapBasic() :
00185 FFirstDart(NULL)
00186 {
00187 empty();
00188 }
00189
00190 INLINE
00191 bool CGMapBasic::isFree(const CDart* ADart, int ADimension) const
00192 {
00193 return ADart->isFree(ADimension);
00194 }
00195
00196 INLINE
00197 bool CGMapBasic::isFree0(const CDart* ADart) const
00198 {
00199 return ADart->isFree0();
00200 }
00201
00202 INLINE
00203 bool CGMapBasic::isFree1(const CDart* ADart) const
00204 {
00205 return ADart->isFree1();
00206 }
00207
00208 INLINE
00209 bool CGMapBasic::isFree2(const CDart* ADart) const
00210 {
00211 return ADart->isFree2();
00212 }
00213
00214 INLINE
00215 bool CGMapBasic::isFree3(const CDart* ADart) const
00216 {
00217 return ADart->isFree3();
00218 }
00219
00220 INLINE
00221 CDart* CGMapBasic::alpha(const CDart* ADart, int ADimension) const
00222 {
00223 return ADart->getAlpha(ADimension);
00224 }
00225
00226 INLINE
00227 CDart* CGMapBasic::alpha0(const CDart* ADart) const
00228 {
00229 return ADart->getAlpha0();
00230 }
00231
00232 INLINE
00233 CDart* CGMapBasic::alpha1(const CDart* ADart) const
00234 {
00235 return ADart->getAlpha1();
00236 }
00237
00238 INLINE
00239 CDart* CGMapBasic::alpha2(const CDart* ADart) const
00240 {
00241 return ADart->getAlpha2();
00242 }
00243
00244 INLINE
00245 CDart* CGMapBasic::alpha3(const CDart* ADart) const
00246 {
00247 return ADart->getAlpha3();
00248 }
00249
00250 INLINE
00251 int CGMapBasic::getNewDirectInfo()
00252 {
00253 #ifndef NDEBUG
00254 if (FNbUsedDirectInfos == NB_DIRECT_INFO)
00255
00256 assert(false);
00257
00258 if (FNbUsedDirectInfos == FMaxNbUsedDirectInfos)
00259 FMaxNbUsedDirectInfos = FNbUsedDirectInfos + 1;
00260 #endif // NDEBUG
00261
00262 int directInfo = FDirectInfos[FNbUsedDirectInfos ++];
00263 FUsedDirectInfo.set(directInfo, true);
00264 return directInfo;
00265 }
00266
00267 INLINE
00268 void CGMapBasic::freeDirectInfo(int ADirectIndex)
00269 {
00270 assert(0 <= ADirectIndex && ADirectIndex < NB_DIRECT_INFO);
00271 assert(FUsedDirectInfo[ADirectIndex]);
00272
00273 FUsedDirectInfo.set(ADirectIndex, false);
00274 FDirectInfos[-- FNbUsedDirectInfos] = ADirectIndex;
00275 }
00276
00277 INLINE
00278 void* CGMapBasic::getDirectInfo(CDart* ADart, int ADirectIndex) const
00279 {
00280 assert( FUsedDirectInfo[ADirectIndex] );
00281
00282 return ADart->getDirectInfo(ADirectIndex);
00283 }
00284
00285 INLINE
00286 void CGMapBasic::setDirectInfo(CDart* ADart, int ADirectIndex, void* APointer)
00287 {
00288 assert( FUsedDirectInfo[ADirectIndex] );
00289
00290 ADart->setDirectInfo(ADirectIndex, APointer);
00291 }
00292
00293 INLINE
00294 bool CGMapBasic::getMaskMark(int AMarkNumber) const
00295 {
00296 return FMaskMarks[AMarkNumber];
00297 }
00298
00299 INLINE
00300 int CGMapBasic::getNbUsedMarks() const
00301 {
00302 return FNbUsedMarks;
00303 }
00304
00305 INLINE
00306 void CGMapBasic::setMarks(CDart* ADart, const std::bitset<NB_MARKS> & AMarks) const
00307 {
00308 ADart->setMarks(AMarks ^ FMaskMarks);
00309 }
00310
00311 INLINE
00312 std::bitset<NB_MARKS> CGMapBasic::getMarks(CDart* ADart) const
00313 {
00314 return ADart->getMarks() ^ FMaskMarks;
00315 }
00316
00317 INLINE
00318 int CGMapBasic::getNewMark()
00319 {
00320 #ifndef NDEBUG
00321 if ( FNbUsedMarks==NB_MARKS )
00322
00323 assert(false);
00324
00325 if (FNbUsedMarks==FMaxNbUsedMarks)
00326 FMaxNbUsedMarks = FNbUsedMarks + 1;
00327 #endif // NDEBUG
00328
00329 int mark = FMarks[FNbUsedMarks++];
00330 FUsedMarks.set(mark, true);
00331 return mark;
00332 }
00333
00334 INLINE
00335 void CGMapBasic::negateMaskMark(int AMarkNumber)
00336 {
00337 assert(FUsedMarks[AMarkNumber]);
00338
00339 FMaskMarks.flip(AMarkNumber);
00340 }
00341
00342 INLINE
00343 bool CGMapBasic::isMarked(const CDart* ADart, int AMarkNumber) const
00344 {
00345 assert(FUsedMarks[AMarkNumber]);
00346
00347 return ADart->getMark(AMarkNumber)!=getMaskMark(AMarkNumber);
00348 }
00349
00350 INLINE
00351 void CGMapBasic::setMarkTo(CDart* ADart, int AMarkNumber, bool AState)
00352 {
00353 assert(FUsedMarks[AMarkNumber]);
00354
00355 ADart->setMark(AMarkNumber, AState ^ FMaskMarks[AMarkNumber]);
00356 }
00357
00358 INLINE
00359 void CGMapBasic::setMark(CDart* ADart, int AMarkNumber)
00360 {
00361 setMarkTo(ADart, AMarkNumber, true);
00362 }
00363
00364 INLINE
00365 void CGMapBasic::unsetMark(CDart* ADart, int AMarkNumber)
00366 {
00367 setMarkTo(ADart, AMarkNumber, false);
00368 }
00369
00370 INLINE
00371 bool CGMapBasic::isWholeMapUnmarked(int AMarkNumber)
00372 {
00373 for (CDart* current = FFirstDart; current!=NULL; current = current->getNext())
00374 if (isMarked(current, AMarkNumber))
00375 return false;
00376
00377 return true;
00378 }
00379
00380 INLINE
00381 void CGMapBasic::freeMark(int AMarkNumber)
00382 {
00383
00384
00385
00386 assert( 0<=AMarkNumber && AMarkNumber<NB_MARKS );
00387 assert( FUsedMarks[AMarkNumber] );
00388
00389 FUsedMarks.set(AMarkNumber, false);
00390 FMarks[-- FNbUsedMarks] = AMarkNumber;
00391 }
00392
00393 INLINE
00394 bool CGMapBasic::isOrbitUsed(TOrbit AOrbit) const
00395 {
00396 return FUsedOrbits[static_cast<int>(AOrbit)];
00397 }
00398
00399 INLINE
00400 bool CGMapBasic::isOrbitUsed(CDart* ADart, TOrbit AOrbit) const
00401 {
00402 return ADart->isOrbitUsed(AOrbit);
00403 }
00404
00405 INLINE
00406 void CGMapBasic::setOrbitUsed(TOrbit AOrbit)
00407 {
00408 FUsedOrbits.set(static_cast<int>(AOrbit), true);
00409 }
00410
00411 INLINE
00412 void CGMapBasic::unsetOrbitUsed(TOrbit AOrbit)
00413 {
00414
00415
00416
00417 #ifndef NDEBUG
00418
00419
00420
00421 #endif // NDEBUG
00422
00423 FUsedOrbits.set(static_cast<int>(AOrbit), false);
00424 }
00425
00426 INLINE
00427 void CGMapBasic::linkAlpha(CDart* ADart1, CDart* ADart2, int ADimension)
00428 {
00429 assert( ADart1!=NULL && ADart2!=NULL);
00430
00431 ADart1->setAlpha(ADart2, ADimension);
00432 ADart2->setAlpha(ADart1, ADimension);
00433 }
00434
00435 INLINE
00436 void CGMapBasic::linkAlpha0(CDart* ADart1, CDart* ADart2)
00437 {
00438 linkAlpha(ADart1, ADart2, 0);
00439 }
00440
00441 INLINE
00442 void CGMapBasic::linkAlpha1(CDart* ADart1, CDart* ADart2)
00443 {
00444 linkAlpha(ADart1, ADart2, 1);
00445 }
00446
00447 INLINE
00448 void CGMapBasic::linkAlpha2(CDart* ADart1, CDart* ADart2)
00449 {
00450 linkAlpha(ADart1, ADart2, 2);
00451 }
00452
00453 INLINE
00454 void CGMapBasic::linkAlpha3(CDart* ADart1, CDart* ADart2)
00455 {
00456 linkAlpha(ADart1, ADart2, 3);
00457 }
00458
00459 INLINE
00460 void CGMapBasic::unlinkAlpha(CDart* ADart, int ADimension)
00461 {
00462 assert( ADart!=NULL );
00463
00464 ADart->getAlpha(ADimension)->setFree(ADimension);
00465 ADart->setFree(ADimension);
00466 }
00467
00468 INLINE
00469 void CGMapBasic::unlinkAlpha0(CDart* ADart)
00470 {
00471 unlinkAlpha(ADart, 0);
00472 }
00473
00474 INLINE
00475 void CGMapBasic::unlinkAlpha1(CDart* ADart)
00476 {
00477 unlinkAlpha(ADart, 1);
00478 }
00479
00480 INLINE
00481 void CGMapBasic::unlinkAlpha2(CDart* ADart)
00482 {
00483 unlinkAlpha(ADart, 2);
00484 }
00485
00486 INLINE
00487 void CGMapBasic::unlinkAlpha3(CDart* ADart)
00488 {
00489 unlinkAlpha(ADart, 3);
00490 }
00491
00492 }
00493