00001
00032 #ifndef LL_LLPTRSKIPMAP_H
00033 #define LL_LLPTRSKIPMAP_H
00034
00035 #include "llerror.h"
00036 #include "llrand.h"
00037
00038 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH = 8>
00039 class LLPtrSkipMapNode
00040 {
00041 public:
00042 LLPtrSkipMapNode()
00043 {
00044 S32 i;
00045 for (i = 0; i < BINARY_DEPTH; i++)
00046 {
00047 mForward[i] = NULL;
00048 }
00049
00050 U8 *zero = (U8 *)&mIndex;
00051
00052 for (i = 0; i < (S32)sizeof(INDEX_T); i++)
00053 {
00054 *(zero + i) = 0;
00055 }
00056
00057 zero = (U8 *)&mData;
00058
00059 for (i = 0; i < (S32)sizeof(DATA_T); i++)
00060 {
00061 *(zero + i) = 0;
00062 }
00063 }
00064
00065 LLPtrSkipMapNode(const INDEX_T &index)
00066 : mIndex(index)
00067 {
00068
00069 S32 i;
00070 for (i = 0; i < BINARY_DEPTH; i++)
00071 {
00072 mForward[i] = NULL;
00073 }
00074
00075 U8 *zero = (U8 *)&mData;
00076
00077 for (i = 0; i < (S32)sizeof(DATA_T); i++)
00078 {
00079 *(zero + i) = 0;
00080 }
00081 }
00082
00083 LLPtrSkipMapNode(const INDEX_T &index, DATA_T datap)
00084 : mIndex(index)
00085 {
00086
00087 S32 i;
00088 for (i = 0; i < BINARY_DEPTH; i++)
00089 {
00090 mForward[i] = NULL;
00091 }
00092
00093 mData = datap;
00094 }
00095
00096 ~LLPtrSkipMapNode()
00097 {
00098 }
00099
00100
00101 void deleteData()
00102 {
00103 delete mData;
00104 mData = 0;
00105 }
00106
00107
00108 void removeData()
00109 {
00110 mData = 0;
00111 }
00112
00113 INDEX_T mIndex;
00114 DATA_T mData;
00115 LLPtrSkipMapNode *mForward[BINARY_DEPTH];
00116
00117 private:
00118
00119 LLPtrSkipMapNode(const LLPtrSkipMapNode &);
00120 LLPtrSkipMapNode &operator=(const LLPtrSkipMapNode &rhs);
00121 };
00122
00123
00124
00125 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH = 8>
00126 class LLPtrSkipMap
00127 {
00128 public:
00129 typedef BOOL (*compare)(const DATA_T& first, const DATA_T& second);
00130 typedef compare insert_func;
00131 typedef compare equals_func;
00132
00133 void init();
00134
00135
00136 LLPtrSkipMap();
00137
00138
00139 LLPtrSkipMap(insert_func insert_first, equals_func equals);
00140
00141 ~LLPtrSkipMap();
00142
00143 void setInsertFirst(insert_func insert_first);
00144 void setEquals(equals_func equals);
00145
00146 DATA_T &addData(const INDEX_T &index, DATA_T datap);
00147 DATA_T &addData(const INDEX_T &index);
00148 DATA_T &getData(const INDEX_T &index);
00149 DATA_T &operator[](const INDEX_T &index);
00150
00151
00152
00153 DATA_T &getData(const INDEX_T &index, BOOL &b_new_entry);
00154
00155
00156 BOOL getInterval(const INDEX_T &index, INDEX_T &index_before, INDEX_T &index_after,
00157 DATA_T &data_before, DATA_T &data_after );
00158
00159
00160 BOOL checkData(const INDEX_T &index);
00161
00162
00163
00164 BOOL checkKey(const INDEX_T &index);
00165
00166
00167
00168
00169 DATA_T getIfThere(const INDEX_T &index);
00170
00171 INDEX_T reverseLookup(const DATA_T datap);
00172
00173
00174 S32 getLength();
00175
00176 BOOL removeData(const INDEX_T &index);
00177 BOOL deleteData(const INDEX_T &index);
00178
00179
00180 void removeAllData();
00181 void deleteAllData();
00182
00183
00184 void resetList();
00185
00186
00187 DATA_T getCurrentDataWithoutIncrement();
00188
00189
00190 DATA_T getCurrentData();
00191
00192
00193 DATA_T getNextData();
00194
00195 INDEX_T getNextKey();
00196
00197
00198 INDEX_T getCurrentKeyWithoutIncrement();
00199
00200
00201
00202 void removeCurrentData();
00203
00204 void deleteCurrentData();
00205
00206
00207 DATA_T getFirstData();
00208
00209 INDEX_T getFirstKey();
00210
00211 static BOOL defaultEquals(const INDEX_T &first, const INDEX_T &second)
00212 {
00213 return first == second;
00214 }
00215
00216 private:
00217
00218 LLPtrSkipMap(const LLPtrSkipMap &);
00219 LLPtrSkipMap &operator=(const LLPtrSkipMap &);
00220
00221 private:
00222 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> mHead;
00223 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mUpdate[BINARY_DEPTH];
00224 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mCurrentp;
00225 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *mCurrentOperatingp;
00226 S32 mLevel;
00227 BOOL (*mInsertFirst)(const INDEX_T &first, const INDEX_T &second);
00228 BOOL (*mEquals)(const INDEX_T &first, const INDEX_T &second);
00229 S32 mNumberOfSteps;
00230 };
00231
00233
00234
00235
00236
00237
00238 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00239 inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::LLPtrSkipMap()
00240 : mInsertFirst(NULL),
00241 mEquals(defaultEquals),
00242 mNumberOfSteps(0)
00243 {
00244 if (BINARY_DEPTH < 2)
00245 {
00246 llerrs << "Trying to create skip list with too little depth, "
00247 "must be 2 or greater" << llendl;
00248 }
00249 S32 i;
00250 for (i = 0; i < BINARY_DEPTH; i++)
00251 {
00252 mUpdate[i] = NULL;
00253 }
00254 mLevel = 1;
00255 mCurrentp = *(mHead.mForward);
00256 mCurrentOperatingp = *(mHead.mForward);
00257 }
00258
00259 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00260 inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::LLPtrSkipMap(insert_func insert_first,
00261 equals_func equals)
00262 : mInsertFirst(insert_first),
00263 mEquals(equals),
00264 mNumberOfSteps(0)
00265 {
00266 if (BINARY_DEPTH < 2)
00267 {
00268 llerrs << "Trying to create skip list with too little depth, "
00269 "must be 2 or greater" << llendl;
00270 }
00271 mLevel = 1;
00272 S32 i;
00273 for (i = 0; i < BINARY_DEPTH; i++)
00274 {
00275 mHead.mForward[i] = NULL;
00276 mUpdate[i] = NULL;
00277 }
00278 mCurrentp = *(mHead.mForward);
00279 mCurrentOperatingp = *(mHead.mForward);
00280 }
00281
00282 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00283 inline LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::~LLPtrSkipMap()
00284 {
00285 removeAllData();
00286 }
00287
00288 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00289 inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::setInsertFirst(insert_func insert_first)
00290 {
00291 mInsertFirst = insert_first;
00292 }
00293
00294 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00295 inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::setEquals(equals_func equals)
00296 {
00297 mEquals = equals;
00298 }
00299
00300 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00301 inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::addData(const INDEX_T &index, DATA_T datap)
00302 {
00303 S32 level;
00304 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00305 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00306
00307
00308 if (mInsertFirst)
00309 {
00310 for (level = mLevel - 1; level >= 0; level--)
00311 {
00312 temp = *(current->mForward + level);
00313 while ( (temp)
00314 &&(mInsertFirst(temp->mIndex, index)))
00315 {
00316 current = temp;
00317 temp = *(current->mForward + level);
00318 }
00319 *(mUpdate + level) = current;
00320 }
00321 }
00322 else
00323 {
00324 for (level = mLevel - 1; level >= 0; level--)
00325 {
00326 temp = *(current->mForward + level);
00327 while ( (temp)
00328 &&(temp->mIndex < index))
00329 {
00330 current = temp;
00331 temp = *(current->mForward + level);
00332 }
00333 *(mUpdate + level) = current;
00334 }
00335 }
00336
00337
00338 current = *current->mForward;
00339
00340
00341 if ( (current)
00342 &&(mEquals(current->mIndex, index)))
00343 {
00344 current->mData = datap;
00345 return current->mData;
00346 }
00347
00348
00349 S32 newlevel;
00350 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00351 {
00352 if (ll_frand() < 0.5f)
00353 {
00354 break;
00355 }
00356 }
00357
00358 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode
00359 = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index, datap);
00360
00361 if (newlevel > mLevel)
00362 {
00363 mHead.mForward[mLevel] = NULL;
00364 mUpdate[mLevel] = &mHead;
00365 mLevel = newlevel;
00366 }
00367
00368 for (level = 0; level < newlevel; level++)
00369 {
00370 snode->mForward[level] = mUpdate[level]->mForward[level];
00371 mUpdate[level]->mForward[level] = snode;
00372 }
00373 return snode->mData;
00374 }
00375
00376 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00377 inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::addData(const INDEX_T &index)
00378 {
00379 S32 level;
00380 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00381 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00382
00383
00384 if (mInsertFirst)
00385 {
00386 for (level = mLevel - 1; level >= 0; level--)
00387 {
00388 temp = *(current->mForward + level);
00389 while ( (temp)
00390 &&(mInsertFirst(temp->mIndex, index)))
00391 {
00392 current = temp;
00393 temp = *(current->mForward + level);
00394 }
00395 *(mUpdate + level) = current;
00396 }
00397 }
00398 else
00399 {
00400 for (level = mLevel - 1; level >= 0; level--)
00401 {
00402 temp = *(current->mForward + level);
00403 while ( (temp)
00404 &&(temp->mIndex < index))
00405 {
00406 current = temp;
00407 temp = *(current->mForward + level);
00408 }
00409 *(mUpdate + level) = current;
00410 }
00411 }
00412
00413
00414 current = *current->mForward;
00415
00416
00417 S32 newlevel;
00418 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00419 {
00420 if (ll_frand() < 0.5f)
00421 break;
00422 }
00423
00424 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode
00425 = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index);
00426
00427 if (newlevel > mLevel)
00428 {
00429 mHead.mForward[mLevel] = NULL;
00430 mUpdate[mLevel] = &mHead;
00431 mLevel = newlevel;
00432 }
00433
00434 for (level = 0; level < newlevel; level++)
00435 {
00436 snode->mForward[level] = mUpdate[level]->mForward[level];
00437 mUpdate[level]->mForward[level] = snode;
00438 }
00439 return snode->mData;
00440 }
00441
00442 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00443 inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getData(const INDEX_T &index)
00444 {
00445 S32 level;
00446 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00447 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00448
00449 mNumberOfSteps = 0;
00450
00451
00452 if (mInsertFirst)
00453 {
00454 for (level = mLevel - 1; level >= 0; level--)
00455 {
00456 temp = *(current->mForward + level);
00457 while ( (temp)
00458 &&(mInsertFirst(temp->mIndex, index)))
00459 {
00460 current = temp;
00461 temp = *(current->mForward + level);
00462 mNumberOfSteps++;
00463 }
00464 *(mUpdate + level) = current;
00465 }
00466 }
00467 else
00468 {
00469 for (level = mLevel - 1; level >= 0; level--)
00470 {
00471 temp = *(current->mForward + level);
00472 while ( (temp)
00473 &&(temp->mIndex < index))
00474 {
00475 current = temp;
00476 temp = *(current->mForward + level);
00477 mNumberOfSteps++;
00478 }
00479 *(mUpdate + level) = current;
00480 }
00481 }
00482
00483
00484 current = *current->mForward;
00485 mNumberOfSteps++;
00486
00487 if ( (current)
00488 &&(mEquals(current->mIndex, index)))
00489 {
00490
00491 return current->mData;
00492 }
00493
00494
00495 S32 newlevel;
00496 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00497 {
00498 if (ll_frand() < 0.5f)
00499 break;
00500 }
00501
00502 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *snode
00503 = new LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>(index);
00504
00505 if (newlevel > mLevel)
00506 {
00507 mHead.mForward[mLevel] = NULL;
00508 mUpdate[mLevel] = &mHead;
00509 mLevel = newlevel;
00510 }
00511
00512 for (level = 0; level < newlevel; level++)
00513 {
00514 snode->mForward[level] = mUpdate[level]->mForward[level];
00515 mUpdate[level]->mForward[level] = snode;
00516 }
00517
00518 return snode->mData;
00519 }
00520
00521 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00522 inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getInterval(const INDEX_T &index,
00523 INDEX_T &index_before,
00524 INDEX_T &index_after,
00525 DATA_T &data_before,
00526 DATA_T &data_after)
00527 {
00528 S32 level;
00529 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00530 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00531
00532 mNumberOfSteps = 0;
00533
00534
00535 if (mInsertFirst)
00536 {
00537 for (level = mLevel - 1; level >= 0; level--)
00538 {
00539 temp = *(current->mForward + level);
00540 while ( (temp)
00541 &&(mInsertFirst(temp->mIndex, index)))
00542 {
00543 current = temp;
00544 temp = *(current->mForward + level);
00545 mNumberOfSteps++;
00546 }
00547 *(mUpdate + level) = current;
00548 }
00549 }
00550 else
00551 {
00552 for (level = mLevel - 1; level >= 0; level--)
00553 {
00554 temp = *(current->mForward + level);
00555 while ( (temp)
00556 &&(temp->mIndex < index))
00557 {
00558 current = temp;
00559 temp = *(current->mForward + level);
00560 mNumberOfSteps++;
00561 }
00562 *(mUpdate + level) = current;
00563 }
00564 }
00565
00566 BOOL both_found = TRUE;
00567
00568 if (current != &mHead)
00569 {
00570 index_before = current->mIndex;
00571 data_before = current->mData;
00572 }
00573 else
00574 {
00575 data_before = 0;
00576 index_before = 0;
00577 both_found = FALSE;
00578 }
00579
00580
00581 mNumberOfSteps++;
00582 current = *current->mForward;
00583
00584 if (current)
00585 {
00586 data_after = current->mData;
00587 index_after = current->mIndex;
00588 }
00589 else
00590 {
00591 data_after = 0;
00592 index_after = 0;
00593 both_found = FALSE;
00594 }
00595
00596 return both_found;
00597 }
00598
00599
00600 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00601 inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::operator[](const INDEX_T &index)
00602 {
00603
00604 return getData(index);
00605 }
00606
00607
00608
00609 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00610 inline DATA_T &LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getData(const INDEX_T &index, BOOL &b_new_entry)
00611 {
00612 S32 level;
00613 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00614 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00615
00616 mNumberOfSteps = 0;
00617
00618
00619 if (mInsertFirst)
00620 {
00621 for (level = mLevel - 1; level >= 0; level--)
00622 {
00623 temp = *(current->mForward + level);
00624 while ( (temp)
00625 &&(mInsertFirst(temp->mIndex, index)))
00626 {
00627 current = temp;
00628 temp = *(current->mForward + level);
00629 mNumberOfSteps++;
00630 }
00631 *(mUpdate + level) = current;
00632 }
00633 }
00634 else
00635 {
00636 for (level = mLevel - 1; level >= 0; level--)
00637 {
00638 temp = *(current->mForward + level);
00639 while ( (temp)
00640 &&(temp->mIndex < index))
00641 {
00642 current = temp;
00643 temp = *(current->mForward + level);
00644 mNumberOfSteps++;
00645 }
00646 *(mUpdate + level) = current;
00647 }
00648 }
00649
00650
00651 mNumberOfSteps++;
00652 current = *current->mForward;
00653
00654 if ( (current)
00655 &&(mEquals(current->mIndex, index)))
00656 {
00657
00658 return current->mData;
00659 }
00660 b_new_entry = TRUE;
00661 addData(index);
00662
00663 return current->mData;
00664 }
00665
00666
00667 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00668 inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::checkData(const INDEX_T &index)
00669 {
00670 S32 level;
00671 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00672 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00673
00674
00675 if (mInsertFirst)
00676 {
00677 for (level = mLevel - 1; level >= 0; level--)
00678 {
00679 temp = *(current->mForward + level);
00680 while ( (temp)
00681 &&(mInsertFirst(temp->mIndex, index)))
00682 {
00683 current = temp;
00684 temp = *(current->mForward + level);
00685 }
00686 *(mUpdate + level) = current;
00687 }
00688 }
00689 else
00690 {
00691 for (level = mLevel - 1; level >= 0; level--)
00692 {
00693 temp = *(current->mForward + level);
00694 while ( (temp)
00695 &&(temp->mIndex < index))
00696 {
00697 current = temp;
00698 temp = *(current->mForward + level);
00699 }
00700 *(mUpdate + level) = current;
00701 }
00702 }
00703
00704
00705 current = *current->mForward;
00706
00707 if (current)
00708 {
00709
00710 if (current->mData)
00711 {
00712 return mEquals(current->mIndex, index);
00713 }
00714 }
00715
00716 return FALSE;
00717 }
00718
00719
00720
00721 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00722 inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::checkKey(const INDEX_T &index)
00723 {
00724 S32 level;
00725 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00726 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00727
00728
00729 if (mInsertFirst)
00730 {
00731 for (level = mLevel - 1; level >= 0; level--)
00732 {
00733 temp = *(current->mForward + level);
00734 while ( (temp)
00735 &&(mInsertFirst(temp->mIndex, index)))
00736 {
00737 current = temp;
00738 temp = *(current->mForward + level);
00739 }
00740 *(mUpdate + level) = current;
00741 }
00742 }
00743 else
00744 {
00745 for (level = mLevel - 1; level >= 0; level--)
00746 {
00747 temp = *(current->mForward + level);
00748 while ( (temp)
00749 &&(temp->mIndex < index))
00750 {
00751 current = temp;
00752 temp = *(current->mForward + level);
00753 }
00754 *(mUpdate + level) = current;
00755 }
00756 }
00757
00758
00759 current = *current->mForward;
00760
00761 if (current)
00762 {
00763 return mEquals(current->mIndex, index);
00764 }
00765
00766 return FALSE;
00767 }
00768
00769
00770
00771
00772 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00773 inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getIfThere(const INDEX_T &index)
00774 {
00775 S32 level;
00776 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00777 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00778
00779 mNumberOfSteps = 0;
00780
00781
00782 if (mInsertFirst)
00783 {
00784 for (level = mLevel - 1; level >= 0; level--)
00785 {
00786 temp = *(current->mForward + level);
00787 while ( (temp)
00788 &&(mInsertFirst(temp->mIndex, index)))
00789 {
00790 current = temp;
00791 temp = *(current->mForward + level);
00792 mNumberOfSteps++;
00793 }
00794 *(mUpdate + level) = current;
00795 }
00796 }
00797 else
00798 {
00799 for (level = mLevel - 1; level >= 0; level--)
00800 {
00801 temp = *(current->mForward + level);
00802 while ( (temp)
00803 &&(temp->mIndex < index))
00804 {
00805 current = temp;
00806 temp = *(current->mForward + level);
00807 mNumberOfSteps++;
00808 }
00809 *(mUpdate + level) = current;
00810 }
00811 }
00812
00813
00814 mNumberOfSteps++;
00815 current = *current->mForward;
00816
00817 if (current)
00818 {
00819 if (mEquals(current->mIndex, index))
00820 {
00821 return current->mData;
00822 }
00823 }
00824
00825
00826 return (DATA_T)0;
00827 }
00828
00829 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00830 inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::reverseLookup(const DATA_T datap)
00831 {
00832 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00833
00834 while (current)
00835 {
00836 if (datap == current->mData)
00837 {
00838
00839 return current->mIndex;
00840 }
00841 current = *current->mForward;
00842 }
00843
00844
00845 return INDEX_T();
00846 }
00847
00848
00849 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00850 inline S32 LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getLength()
00851 {
00852 U32 length = 0;
00853 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH>* temp;
00854 for (temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
00855 {
00856 length++;
00857 }
00858
00859 return length;
00860 }
00861
00862 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00863 inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeData(const INDEX_T &index)
00864 {
00865 S32 level;
00866 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00867 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00868
00869
00870 if (mInsertFirst)
00871 {
00872 for (level = mLevel - 1; level >= 0; level--)
00873 {
00874 temp = *(current->mForward + level);
00875 while ( (temp)
00876 &&(mInsertFirst(temp->mIndex, index)))
00877 {
00878 current = temp;
00879 temp = *(current->mForward + level);
00880 }
00881 *(mUpdate + level) = current;
00882 }
00883 }
00884 else
00885 {
00886 for (level = mLevel - 1; level >= 0; level--)
00887 {
00888 temp = *(current->mForward + level);
00889 while ( (temp)
00890 &&(temp->mIndex < index))
00891 {
00892 current = temp;
00893 temp = *(current->mForward + level);
00894 }
00895 *(mUpdate + level) = current;
00896 }
00897 }
00898
00899
00900 current = *current->mForward;
00901
00902 if (!current)
00903 {
00904
00905
00906 return FALSE;
00907 }
00908
00909
00910 if (!mEquals(current->mIndex, index))
00911 {
00912
00913
00914 return FALSE;
00915 }
00916 else
00917 {
00918
00919 if (current == mCurrentp)
00920 {
00921 mCurrentp = *current->mForward;
00922 }
00923
00924 if (current == mCurrentOperatingp)
00925 {
00926 mCurrentOperatingp = *current->mForward;
00927 }
00928
00929 for (level = 0; level < mLevel; level++)
00930 {
00931 if (*((*(mUpdate + level))->mForward + level) != current)
00932 {
00933
00934 break;
00935 }
00936 *((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
00937 }
00938
00939
00940 current->removeData();
00941 delete current;
00942
00943
00944 while ( (mLevel > 1)
00945 &&(!*(mHead.mForward + mLevel - 1)))
00946 {
00947 mLevel--;
00948 }
00949 }
00950
00951 return TRUE;
00952 }
00953
00954 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
00955 inline BOOL LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteData(const INDEX_T &index)
00956 {
00957 S32 level;
00958 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *current = &mHead;
00959 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
00960
00961
00962 if (mInsertFirst)
00963 {
00964 for (level = mLevel - 1; level >= 0; level--)
00965 {
00966 temp = *(current->mForward + level);
00967 while ( (temp)
00968 &&(mInsertFirst(temp->mIndex, index)))
00969 {
00970 current = temp;
00971 temp = *(current->mForward + level);
00972 }
00973 *(mUpdate + level) = current;
00974 }
00975 }
00976 else
00977 {
00978 for (level = mLevel - 1; level >= 0; level--)
00979 {
00980 temp = *(current->mForward + level);
00981 while ( (temp)
00982 &&(temp->mIndex < index))
00983 {
00984 current = temp;
00985 temp = *(current->mForward + level);
00986 }
00987 *(mUpdate + level) = current;
00988 }
00989 }
00990
00991
00992 current = *current->mForward;
00993
00994 if (!current)
00995 {
00996
00997
00998 return FALSE;
00999 }
01000
01001
01002 if (!mEquals(current->mIndex, index))
01003 {
01004
01005
01006 return FALSE;
01007 }
01008 else
01009 {
01010
01011 if (current == mCurrentp)
01012 {
01013 mCurrentp = *current->mForward;
01014 }
01015
01016 if (current == mCurrentOperatingp)
01017 {
01018 mCurrentOperatingp = *current->mForward;
01019 }
01020
01021 for (level = 0; level < mLevel; level++)
01022 {
01023 if (*((*(mUpdate + level))->mForward + level) != current)
01024 {
01025
01026 break;
01027 }
01028 *((*(mUpdate + level))->mForward + level) = *(current->mForward + level);
01029 }
01030
01031
01032 current->deleteData();
01033 delete current;
01034
01035
01036 while ( (mLevel > 1)
01037 &&(!*(mHead.mForward + mLevel - 1)))
01038 {
01039 mLevel--;
01040 }
01041 }
01042
01043 return TRUE;
01044 }
01045
01046
01047 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01048 void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeAllData()
01049 {
01050 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
01051
01052 mCurrentp = *(mHead.mForward);
01053
01054 while (mCurrentp)
01055 {
01056 temp = mCurrentp->mForward[0];
01057 mCurrentp->removeData();
01058 delete mCurrentp;
01059 mCurrentp = temp;
01060 }
01061
01062 S32 i;
01063 for (i = 0; i < BINARY_DEPTH; i++)
01064 {
01065 mHead.mForward[i] = NULL;
01066 mUpdate[i] = NULL;
01067 }
01068
01069 mCurrentp = *(mHead.mForward);
01070 mCurrentOperatingp = *(mHead.mForward);
01071 }
01072
01073 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01074 inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteAllData()
01075 {
01076 LLPtrSkipMapNode<INDEX_T, DATA_T, BINARY_DEPTH> *temp;
01077
01078 mCurrentp = *(mHead.mForward);
01079
01080 while (mCurrentp)
01081 {
01082 temp = mCurrentp->mForward[0];
01083 mCurrentp->deleteData();
01084 delete mCurrentp;
01085 mCurrentp = temp;
01086 }
01087
01088 S32 i;
01089 for (i = 0; i < BINARY_DEPTH; i++)
01090 {
01091 mHead.mForward[i] = NULL;
01092 mUpdate[i] = NULL;
01093 }
01094
01095 mCurrentp = *(mHead.mForward);
01096 mCurrentOperatingp = *(mHead.mForward);
01097 }
01098
01099
01100 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01101 inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::resetList()
01102 {
01103 mCurrentp = *(mHead.mForward);
01104 mCurrentOperatingp = *(mHead.mForward);
01105 }
01106
01107
01108
01109 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01110 inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentDataWithoutIncrement()
01111 {
01112 if (mCurrentOperatingp)
01113 {
01114 return mCurrentOperatingp->mData;
01115 }
01116 else
01117 {
01118
01119 return (DATA_T)0;
01120 }
01121 }
01122
01123
01124 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01125 inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentData()
01126 {
01127 if (mCurrentp)
01128 {
01129 mCurrentOperatingp = mCurrentp;
01130 mCurrentp = mCurrentp->mForward[0];
01131 return mCurrentOperatingp->mData;
01132 }
01133 else
01134 {
01135
01136 return (DATA_T)0;
01137 }
01138 }
01139
01140
01141 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01142 inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getNextData()
01143 {
01144 if (mCurrentp)
01145 {
01146 mCurrentOperatingp = mCurrentp;
01147 mCurrentp = mCurrentp->mForward[0];
01148 return mCurrentOperatingp->mData;
01149 }
01150 else
01151 {
01152
01153 return (DATA_T)0;
01154 }
01155 }
01156
01157 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01158 inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getNextKey()
01159 {
01160 if (mCurrentp)
01161 {
01162 mCurrentOperatingp = mCurrentp;
01163 mCurrentp = mCurrentp->mForward[0];
01164 return mCurrentOperatingp->mIndex;
01165 }
01166 else
01167 {
01168 return mHead.mIndex;
01169 }
01170 }
01171
01172
01173 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01174 inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getCurrentKeyWithoutIncrement()
01175 {
01176 if (mCurrentOperatingp)
01177 {
01178 return mCurrentOperatingp->mIndex;
01179 }
01180 else
01181 {
01182
01183 return (INDEX_T)0;
01184 }
01185 }
01186
01187
01188
01189
01190 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01191 inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::removeCurrentData()
01192 {
01193 if (mCurrentOperatingp)
01194 {
01195 removeData(mCurrentOperatingp->mIndex);
01196 }
01197 }
01198
01199 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01200 inline void LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::deleteCurrentData()
01201 {
01202 if (mCurrentOperatingp)
01203 {
01204 deleteData(mCurrentOperatingp->mIndex);
01205 }
01206 }
01207
01208
01209 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01210 inline DATA_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getFirstData()
01211 {
01212 mCurrentp = *(mHead.mForward);
01213 mCurrentOperatingp = *(mHead.mForward);
01214 if (mCurrentp)
01215 {
01216 mCurrentOperatingp = mCurrentp;
01217 mCurrentp = mCurrentp->mForward[0];
01218 return mCurrentOperatingp->mData;
01219 }
01220 else
01221 {
01222
01223 return (DATA_T)0;
01224 }
01225 }
01226
01227 template <class INDEX_T, class DATA_T, S32 BINARY_DEPTH>
01228 inline INDEX_T LLPtrSkipMap<INDEX_T, DATA_T, BINARY_DEPTH>::getFirstKey()
01229 {
01230 mCurrentp = *(mHead.mForward);
01231 mCurrentOperatingp = *(mHead.mForward);
01232 if (mCurrentp)
01233 {
01234 mCurrentOperatingp = mCurrentp;
01235 mCurrentp = mCurrentp->mForward[0];
01236 return mCurrentOperatingp->mIndex;
01237 }
01238 else
01239 {
01240 return mHead.mIndex;
01241 }
01242 }
01243
01244 #endif