ALStructure.cpp
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 #include <iostream>
00037
00038 #include "ALStructure.h"
00039
00040
00041 ALStructure::ALStructure()
00042 : size(0),
00043 sentinel(0, 0, 0, 0, 0),
00044 raHead(&sentinel),
00045 decHead(&sentinel),
00046 tail(&sentinel),
00047 rootNode(0)
00048 {
00049 rootNode = new ALNode(&sentinel, 0, 0);
00050 }
00051
00052 ALStructure::~ALStructure()
00053 {
00054 delete rootNode;
00055 }
00056
00057
00058
00059 ALElement * ALStructure::findLeastGE(double ra)
00060 {
00061 return findLowerBound(ra, true);
00062 }
00063
00064
00065
00066 ALElement * ALStructure::findLeastG(double ra)
00067 {
00068 return findLowerBound(ra, false);
00069 }
00070
00071
00072
00073
00074
00075 ALElement * ALStructure::findLowerBound(double ra, bool allowEquality)
00076 {
00077
00078 ALNode * currentNode = rootNode;
00079
00080
00081 ALElement * bestSoFar = 0;
00082
00083
00084 while (currentNode != 0)
00085 {
00086 ALElement * i = currentNode->getElement();
00087
00088 if (i == tail)
00089 {
00090
00091
00092
00093 bestSoFar = i;
00094 currentNode = currentNode->getLeftChild();
00095 }
00096 else
00097 {
00098
00099 ActiveObject * content = i->getContent();
00100 double contentRa = content->getObject()->getRa();
00101 if (contentRa > ra)
00102 {
00103
00104
00105
00106
00107
00108 bestSoFar = i;
00109 currentNode = currentNode->getLeftChild();
00110 }
00111 else if (contentRa < ra)
00112 {
00113
00114
00115 currentNode = currentNode->getRightChild();
00116 }
00117 else if (allowEquality)
00118 {
00119
00120
00121
00122
00123
00124
00125
00126
00127 bestSoFar = i;
00128 currentNode = currentNode->getLeftChild();
00129 }
00130 else
00131 {
00132
00133
00134
00135 currentNode = currentNode->getRightChild();
00136 }
00137 }
00138 }
00139
00140
00141
00142
00143 return bestSoFar;
00144 }
00145
00146
00147
00148 void ALStructure::remove(ALElement * element)
00149 {
00150 ALElement * prevRa = element->getPrevRa();
00151 ALElement * nextRa = element->getNextRa();
00152 ALElement * prevDec = element->getPrevDec();
00153 ALElement * nextDec = element->getNextDec();
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163 nextRa->setPrevRa(prevRa);
00164 if (prevRa == 0)
00165 raHead = nextRa;
00166 else
00167 prevRa->setNextRa(nextRa);
00168
00169 nextDec->setPrevDec(prevDec);
00170
00171 if (prevDec == 0)
00172 decHead = nextDec;
00173 else
00174 prevDec->setNextDec(nextDec);
00175
00176
00177 removeNode(element);
00178
00179 delete element;
00180
00181 size--;
00182 }
00183
00184 void ALStructure::removeNode(ALElement * element)
00185 {
00186 ALNode * target;
00187
00188 if (rootNode->getElement() == element)
00189 {
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212 std::cout << "Error: trying to delete the sentinel!\n";
00213 }
00214 else
00215 {
00216 ALNode * parent;
00217 Child child;
00218
00219
00220
00221
00222 findNode(element, rootNode, &parent, &child);
00223
00224
00225 if (child == left)
00226 target = parent->getLeftChild();
00227 else
00228 target = parent->getRightChild();
00229
00230 if ((target->getLeftChild() == 0) &&
00231 (target->getRightChild() == 0))
00232 {
00233
00234 if (child == left)
00235 parent->setLeftChild(0);
00236 else
00237 parent->setRightChild(0);
00238 }
00239 else if (target->getRightChild() == 0)
00240 {
00241
00242 if (child == left)
00243 parent->setLeftChild(target->getLeftChild());
00244 else
00245 parent->setRightChild(target->getLeftChild());
00246 }
00247 else if (target->getLeftChild() == 0)
00248 {
00249
00250 if (child == left)
00251 parent->setLeftChild(target->getRightChild());
00252 else
00253 parent->setRightChild(target->getRightChild());
00254 }
00255 else
00256 {
00257
00258 ALNode * successor = grabSuccessor(target);
00259
00260
00261 if (child == left)
00262 parent->setLeftChild(successor);
00263 else
00264 parent->setRightChild(successor);
00265
00266
00267 successor->setLeftChild(target->getLeftChild());
00268 }
00269 delete target;
00270 }
00271 }
00272
00273
00274
00275
00276
00277
00278 void ALStructure::findNode(ALElement * element,
00279 ALNode * root,
00280 ALNode * * parent,
00281 ALStructure::Child * child)
00282 {
00283
00284
00285 ActiveObject * content = element->getContent();
00286 ActiveObject * rootContent = root->getElement()->getContent();
00287
00288
00289
00290
00291 int comp;
00292 if (rootContent == 0)
00293 comp = -1;
00294 else if (content->getObject()->getRa() < rootContent->getObject()->getRa())
00295 comp = -1;
00296 else if (content->getObject()->getRa() > rootContent->getObject()->getRa())
00297 comp = 1;
00298 else
00299 comp = 0;
00300
00301 if (comp <= 0)
00302 {
00303
00304 ALNode * leftChild = root->getLeftChild();
00305 if (leftChild != 0)
00306 {
00307
00308
00309 if (leftChild->getElement() == element)
00310 {
00311
00312 *parent = root;
00313 *child = left;
00314 return;
00315 }
00316
00317
00318
00319 findNode(element, leftChild, parent, child);
00320
00321
00322
00323 if (*parent != 0)
00324 return;
00325 }
00326 }
00327
00328 if (comp >= 0)
00329 {
00330
00331 ALNode * rightChild = root->getRightChild();
00332 if (rightChild != 0)
00333 {
00334
00335
00336 if (rightChild->getElement() == element)
00337 {
00338
00339 *parent = root;
00340 *child = right;
00341 return;
00342 }
00343
00344
00345
00346 findNode(element, rightChild, parent, child);
00347
00348
00349
00350 if (*parent != 0)
00351 return;
00352 }
00353 }
00354
00355
00356
00357 *parent = 0;
00358
00359 return;
00360 }
00361
00362
00363 ALNode * ALStructure::grabSuccessor(ALNode * delNode)
00364 {
00365 ALNode * successorParent = delNode;
00366 ALNode * successor = delNode;
00367 ALNode * current = delNode->getRightChild();
00368
00369 while (current != 0)
00370 {
00371 successorParent = successor;
00372 successor = current;
00373 current = current->getLeftChild();
00374 }
00375
00376 if (successor != delNode->getRightChild())
00377 {
00378 successorParent->setLeftChild(successor->getRightChild());
00379 successor->setRightChild(delNode->getRightChild());
00380 }
00381
00382 return successor;
00383 }
00384
00385
00386
00387
00388
00389
00390
00391 void ALStructure::add(ActiveObject * object)
00392 {
00393 ALNode * currentNode = rootNode;
00394 ALNode * parentNode;
00395
00396 double ra = object->getObject()->getRa();
00397
00398
00399 while (true)
00400 {
00401 parentNode = currentNode;
00402 ALElement * element = currentNode->getElement();
00403 if (element == tail)
00404 {
00405
00406
00407 currentNode = currentNode->getLeftChild();
00408 if (currentNode == 0)
00409 {
00410
00411
00412 ALElement * newElement = insertNew(object, parentNode->getElement(), tail);
00413
00414
00415 ALNode * newNode = new ALNode(newElement, 0, 0);
00416 parentNode->setLeftChild(newNode);
00417 return;
00418 }
00419 }
00420 else
00421 {
00422
00423
00424
00425 ActiveObject * current = element->getContent();
00426 if (ra < current->getObject()->getRa())
00427 {
00428
00429 currentNode = currentNode->getLeftChild();
00430 if (currentNode == 0)
00431 {
00432
00433
00434 ALElement * newElement = insertNew(object, parentNode->getElement(), tail);
00435
00436
00437 ALNode * newNode = new ALNode(newElement, 0, 0);
00438 parentNode->setLeftChild(newNode);
00439 return;
00440 }
00441 }
00442 else
00443 {
00444
00445 currentNode = currentNode->getRightChild();
00446 if (currentNode == 0)
00447 {
00448
00449
00450 ALElement * newElement = insertNew(object, parentNode->getElement()->getNextRa(), tail);
00451
00452
00453 ALNode * newNode = new ALNode(newElement, 0, 0);
00454 parentNode->setRightChild(newNode);
00455 return;
00456 }
00457 }
00458 }
00459 }
00460 }
00461
00462
00463
00464
00465
00466
00467 ALElement * ALStructure::insertNew(ActiveObject * object,
00468 ALElement * nextRa,
00469 ALElement * nextDec)
00470 {
00471
00472 ALElement * prevRa = nextRa->getPrevRa();
00473 ALElement * prevDec = nextDec->getPrevDec();
00474
00475
00476 ALElement * element = new ALElement(object, prevRa, nextRa, prevDec, nextDec);
00477
00478
00479 nextRa->setPrevRa(element);
00480 nextDec->setPrevDec(element);
00481
00482
00483
00484
00485 if (prevRa == 0)
00486 {
00487 raHead = element;
00488 }
00489 else
00490 {
00491 prevRa->setNextRa(element);
00492 }
00493
00494
00495
00496
00497 if (prevDec == 0)
00498 {
00499 decHead = element;
00500 }
00501 else
00502 {
00503 prevDec->setNextDec(element);
00504 }
00505
00506 size++;
00507
00508 return element;
00509 }
00510
00511 unsigned int ALStructure::getSize()
00512 {
00513 return size;
00514 }