00001
00031 #ifndef LL_LLSKIPLIST_H
00032 #define LL_LLSKIPLIST_H
00033
00034 #include "llrand.h"
00035 #include "llrand.h"
00036
00037
00038
00039 template <class DATA_TYPE, S32 BINARY_DEPTH = 10>
00040 class LLSkipList
00041 {
00042 public:
00043 typedef BOOL (*compare)(const DATA_TYPE& first, const DATA_TYPE& second);
00044 typedef compare insert_func;
00045 typedef compare equals_func;
00046
00047 void init();
00048
00049
00050 LLSkipList();
00051
00052
00053 LLSkipList(insert_func insert_first, equals_func equals);
00054 ~LLSkipList();
00055
00056 inline void setInsertFirst(insert_func insert_first);
00057 inline void setEquals(equals_func equals);
00058
00059 inline BOOL addData(const DATA_TYPE& data);
00060 inline BOOL checkData(const DATA_TYPE& data);
00061
00062
00063 inline S32 getLength() const;
00064
00065 inline BOOL moveData(const DATA_TYPE& data, LLSkipList *newlist);
00066
00067 inline BOOL removeData(const DATA_TYPE& data);
00068
00069
00070 inline void removeAllNodes();
00071
00072
00073 inline void resetList();
00074
00075
00076 inline DATA_TYPE getCurrentData();
00077
00078
00079 inline DATA_TYPE getNextData();
00080
00081
00082
00083 inline void removeCurrentData();
00084
00085
00086 inline DATA_TYPE getFirstData();
00087
00088 class LLSkipNode
00089 {
00090 public:
00091 LLSkipNode()
00092 : mData(0)
00093 {
00094 S32 i;
00095 for (i = 0; i < BINARY_DEPTH; i++)
00096 {
00097 mForward[i] = NULL;
00098 }
00099 }
00100
00101 LLSkipNode(DATA_TYPE data)
00102 : mData(data)
00103 {
00104 S32 i;
00105 for (i = 0; i < BINARY_DEPTH; i++)
00106 {
00107 mForward[i] = NULL;
00108 }
00109 }
00110
00111 ~LLSkipNode()
00112 {
00113 }
00114
00115 DATA_TYPE mData;
00116 LLSkipNode *mForward[BINARY_DEPTH];
00117
00118 private:
00119
00120 LLSkipNode(const LLSkipNode &);
00121 LLSkipNode &operator=(const LLSkipNode &);
00122 };
00123
00124 static BOOL defaultEquals(const DATA_TYPE& first, const DATA_TYPE& second)
00125 {
00126 return first == second;
00127 }
00128
00129 private:
00130 LLSkipNode mHead;
00131 LLSkipNode *mUpdate[BINARY_DEPTH];
00132 LLSkipNode *mCurrentp;
00133 LLSkipNode *mCurrentOperatingp;
00134 S32 mLevel;
00135 insert_func mInsertFirst;
00136 equals_func mEquals;
00137
00138 private:
00139
00140 LLSkipList(const LLSkipList &);
00141 LLSkipList &operator=(const LLSkipList &);
00142 };
00143
00144
00146
00147
00148
00149
00150
00151
00152 template <class DATA_TYPE, S32 BINARY_DEPTH>
00153 inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::init()
00154 {
00155 S32 i;
00156 for (i = 0; i < BINARY_DEPTH; i++)
00157 {
00158 mHead.mForward[i] = NULL;
00159 mUpdate[i] = NULL;
00160 }
00161 mLevel = 1;
00162 mCurrentp = *(mHead.mForward);
00163 mCurrentOperatingp = *(mHead.mForward);
00164 }
00165
00166
00167
00168 template <class DATA_TYPE, S32 BINARY_DEPTH>
00169 inline LLSkipList<DATA_TYPE, BINARY_DEPTH>::LLSkipList()
00170 : mInsertFirst(NULL),
00171 mEquals(defaultEquals)
00172 {
00173 init();
00174 }
00175
00176
00177 template <class DATA_TYPE, S32 BINARY_DEPTH>
00178 inline LLSkipList<DATA_TYPE, BINARY_DEPTH>::LLSkipList(insert_func insert,
00179 equals_func equals)
00180 : mInsertFirst(insert),
00181 mEquals(equals)
00182 {
00183 init();
00184 }
00185
00186 template <class DATA_TYPE, S32 BINARY_DEPTH>
00187 inline LLSkipList<DATA_TYPE, BINARY_DEPTH>::~LLSkipList()
00188 {
00189 removeAllNodes();
00190 }
00191
00192 template <class DATA_TYPE, S32 BINARY_DEPTH>
00193 inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::setInsertFirst(insert_func insert_first)
00194 {
00195 mInsertFirst = insert_first;
00196 }
00197
00198 template <class DATA_TYPE, S32 BINARY_DEPTH>
00199 inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::setEquals(equals_func equals)
00200 {
00201 mEquals = equals;
00202 }
00203
00204 template <class DATA_TYPE, S32 BINARY_DEPTH>
00205 inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::addData(const DATA_TYPE& data)
00206 {
00207 S32 level;
00208 LLSkipNode *current = &mHead;
00209 LLSkipNode *temp;
00210
00211 if (mInsertFirst)
00212 {
00213 for (level = mLevel - 1; level >= 0; level--)
00214 {
00215 temp = *(current->mForward + level);
00216 while ( (temp)
00217 &&(mInsertFirst(temp->mData, data)))
00218 {
00219 current = temp;
00220 temp = *(current->mForward + level);
00221 }
00222 *(mUpdate + level) = current;
00223 }
00224 }
00225 else
00226 {
00227 for (level = mLevel - 1; level >= 0; level--)
00228 {
00229 temp = *(current->mForward + level);
00230 while ( (temp)
00231 &&(temp->mData < data))
00232 {
00233 current = temp;
00234 temp = *(current->mForward + level);
00235 }
00236 *(mUpdate + level) = current;
00237 }
00238 }
00239
00240 current = *current->mForward;
00241
00242
00243 S32 newlevel;
00244 for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++)
00245 {
00246 if (ll_frand() < 0.5f)
00247 break;
00248 }
00249
00250 LLSkipNode *snode = new LLSkipNode(data);
00251
00252 if (newlevel > mLevel)
00253 {
00254 mHead.mForward[mLevel] = NULL;
00255 mUpdate[mLevel] = &mHead;
00256 mLevel = newlevel;
00257 }
00258
00259 for (level = 0; level < newlevel; level++)
00260 {
00261 snode->mForward[level] = mUpdate[level]->mForward[level];
00262 mUpdate[level]->mForward[level] = snode;
00263 }
00264 return TRUE;
00265 }
00266
00267 template <class DATA_TYPE, S32 BINARY_DEPTH>
00268 inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::checkData(const DATA_TYPE& data)
00269 {
00270 S32 level;
00271 LLSkipNode *current = &mHead;
00272 LLSkipNode *temp;
00273
00274 if (mInsertFirst)
00275 {
00276 for (level = mLevel - 1; level >= 0; level--)
00277 {
00278 temp = *(current->mForward + level);
00279 while ( (temp)
00280 &&(mInsertFirst(temp->mData, data)))
00281 {
00282 current = temp;
00283 temp = *(current->mForward + level);
00284 }
00285 *(mUpdate + level) = current;
00286 }
00287 }
00288 else
00289 {
00290 for (level = mLevel - 1; level >= 0; level--)
00291 {
00292 temp = *(current->mForward + level);
00293 while ( (temp)
00294 &&(temp->mData < data))
00295 {
00296 current = temp;
00297 temp = *(current->mForward + level);
00298 }
00299 *(mUpdate + level) = current;
00300 }
00301 }
00302
00303 current = *current->mForward;
00304
00305
00306 if (current)
00307 {
00308 return mEquals(current->mData, data);
00309 }
00310
00311 return FALSE;
00312 }
00313
00314
00315 template <class DATA_TYPE, S32 BINARY_DEPTH>
00316 inline S32 LLSkipList<DATA_TYPE, BINARY_DEPTH>::getLength() const
00317 {
00318 U32 length = 0;
00319 for (LLSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0])
00320 {
00321 length++;
00322 }
00323 return length;
00324 }
00325
00326
00327 template <class DATA_TYPE, S32 BINARY_DEPTH>
00328 inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::moveData(const DATA_TYPE& data, LLSkipList *newlist)
00329 {
00330 BOOL removed = removeData(data);
00331 BOOL added = newlist->addData(data);
00332 return removed && added;
00333 }
00334
00335
00336 template <class DATA_TYPE, S32 BINARY_DEPTH>
00337 inline BOOL LLSkipList<DATA_TYPE, BINARY_DEPTH>::removeData(const DATA_TYPE& data)
00338 {
00339 S32 level;
00340 LLSkipNode *current = &mHead;
00341 LLSkipNode *temp;
00342
00343 if (mInsertFirst)
00344 {
00345 for (level = mLevel - 1; level >= 0; level--)
00346 {
00347 temp = *(current->mForward + level);
00348 while ( (temp)
00349 &&(mInsertFirst(temp->mData, data)))
00350 {
00351 current = temp;
00352 temp = *(current->mForward + level);
00353 }
00354 *(mUpdate + level) = current;
00355 }
00356 }
00357 else
00358 {
00359 for (level = mLevel - 1; level >= 0; level--)
00360 {
00361 temp = *(current->mForward + level);
00362 while ( (temp)
00363 &&(temp->mData < data))
00364 {
00365 current = temp;
00366 temp = *(current->mForward + level);
00367 }
00368 *(mUpdate + level) = current;
00369 }
00370 }
00371
00372 current = *current->mForward;
00373
00374
00375 if (!current)
00376 {
00377
00378 return FALSE;
00379 }
00380
00381
00382 if (!mEquals(current->mData, data))
00383 {
00384
00385 return FALSE;
00386 }
00387 else
00388 {
00389
00390 if (current == mCurrentp)
00391 {
00392 mCurrentp = current->mForward[0];
00393 }
00394
00395 if (current == mCurrentOperatingp)
00396 {
00397 mCurrentOperatingp = current->mForward[0];
00398 }
00399
00400 for (level = 0; level < mLevel; level++)
00401 {
00402 if (mUpdate[level]->mForward[level] != current)
00403 {
00404
00405 break;
00406 }
00407 mUpdate[level]->mForward[level] = current->mForward[level];
00408 }
00409
00410
00411 delete current;
00412
00413
00414 while ( (mLevel > 1)
00415 &&(!mHead.mForward[mLevel - 1]))
00416 {
00417 mLevel--;
00418 }
00419 }
00420 return TRUE;
00421 }
00422
00423
00424 template <class DATA_TYPE, S32 BINARY_DEPTH>
00425 inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::removeAllNodes()
00426 {
00427 LLSkipNode *temp;
00428
00429 mCurrentp = *(mHead.mForward);
00430
00431 while (mCurrentp)
00432 {
00433 temp = mCurrentp->mForward[0];
00434 delete mCurrentp;
00435 mCurrentp = temp;
00436 }
00437
00438 S32 i;
00439 for (i = 0; i < BINARY_DEPTH; i++)
00440 {
00441 mHead.mForward[i] = NULL;
00442 mUpdate[i] = NULL;
00443 }
00444
00445 mCurrentp = *(mHead.mForward);
00446 mCurrentOperatingp = *(mHead.mForward);
00447 }
00448
00449
00450 template <class DATA_TYPE, S32 BINARY_DEPTH>
00451 inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::resetList()
00452 {
00453 mCurrentp = *(mHead.mForward);
00454 mCurrentOperatingp = *(mHead.mForward);
00455 }
00456
00457
00458 template <class DATA_TYPE, S32 BINARY_DEPTH>
00459 inline DATA_TYPE LLSkipList<DATA_TYPE, BINARY_DEPTH>::getCurrentData()
00460 {
00461 if (mCurrentp)
00462 {
00463 mCurrentOperatingp = mCurrentp;
00464 mCurrentp = mCurrentp->mForward[0];
00465 return mCurrentOperatingp->mData;
00466 }
00467 else
00468 {
00469
00470 return (DATA_TYPE)0;
00471 }
00472 }
00473
00474
00475 template <class DATA_TYPE, S32 BINARY_DEPTH>
00476 inline DATA_TYPE LLSkipList<DATA_TYPE, BINARY_DEPTH>::getNextData()
00477 {
00478 if (mCurrentp)
00479 {
00480 mCurrentOperatingp = mCurrentp;
00481 mCurrentp = mCurrentp->mForward[0];
00482 return mCurrentOperatingp->mData;
00483 }
00484 else
00485 {
00486
00487 return (DATA_TYPE)0;
00488 }
00489 }
00490
00491
00492
00493 template <class DATA_TYPE, S32 BINARY_DEPTH>
00494 inline void LLSkipList<DATA_TYPE, BINARY_DEPTH>::removeCurrentData()
00495 {
00496 if (mCurrentOperatingp)
00497 {
00498 removeData(mCurrentOperatingp->mData);
00499 }
00500 }
00501
00502
00503 template <class DATA_TYPE, S32 BINARY_DEPTH>
00504 inline DATA_TYPE LLSkipList<DATA_TYPE, BINARY_DEPTH>::getFirstData()
00505 {
00506 mCurrentp = *(mHead.mForward);
00507 mCurrentOperatingp = *(mHead.mForward);
00508 if (mCurrentp)
00509 {
00510 mCurrentOperatingp = mCurrentp;
00511 mCurrentp = mCurrentp->mForward[0];
00512 return mCurrentOperatingp->mData;
00513 }
00514 else
00515 {
00516
00517 return (DATA_TYPE)0;
00518 }
00519 }
00520
00521
00522 #endif