test: triangle.h File Reference

{ \ (Links)->Refs.ParSib = MakeIntoParentRef(Links); \ (Links)->Refs.Child = 0; \ }

{ \ PTRI_SPLAY_LINKS RightChild; \ if ((ParentLinks)->Refs.Child == 0) { \ (ParentLinks)->Refs.Child = MakeIntoLeftChildRef(ChildLinks); \ (ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \ } else { \ RightChild = TriRightChild(ParentLinks); \ (ParentLinks)->Refs.Child = MakeIntoLeftChildRef(ChildLinks); \ (ChildLinks)->Refs.ParSib = MakeIntoSiblingRef(RightChild); \ } \ }

{ \ PTRI_SPLAY_LINKS LeftChild; \ if ((ParentLinks)->Refs.Child == 0) { \ (ParentLinks)->Refs.Child = MakeIntoRightChildRef(ChildLinks); \ (ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \ } else { \ LeftChild = TriLeftChild(ParentLinks); \ LeftChild->Refs.ParSib = MakeIntoSiblingRef(ChildLinks); \ (ChildLinks)->Refs.ParSib = MakeIntoParentRef(ParentLinks); \ } \ }

( \ (TriLeftChild(TriParent(Links)) == (Links)) ? \ TRUE \ : \ FALSE \ )

( \ (TriRightChild(TriParent(Links)) == (Links)) ? \ TRUE \ : \ FALSE \ )

( \ (IsParentRef((Links)->Refs.ParSib) && MakeIntoPointer((Links)->Refs.ParSib) == (Links)) ? \ TRUE \ : \ FALSE \ )

( \ (IsLeftChildRef((Links)->Refs.Child)) ? \ MakeIntoPointer((Links)->Refs.Child) \ : \ 0 \ )

( \ (IsParentRef((Links)->Refs.ParSib)) ? \ MakeIntoPointer((Links)->Refs.ParSib) \ : \ MakeIntoPointer(MakeIntoPointer((Links)->Refs.ParSib)->Refs.ParSib) \ )

( \ (IsRightChildRef((Links)->Refs.Child)) ? \ MakeIntoPointer((Links)->Refs.Child) \ : ( \ (IsLeftChildRef((Links)->Refs.Child) && \ IsSiblingRef(MakeIntoPointer((Links)->Refs.Child)->Refs.ParSib)) ? \ MakeIntoPointer(MakeIntoPointer((Links)->Refs.Child)->Refs.ParSib) \ : \ 0 \ ) \ )

00279 : 00280 00281 This Delete function takes as input a pointer to a splay link in a tree 00282 and deletes that node from the tree. Its function return value is a 00283 pointer to the root the tree. If the tree is now empty, the return 00284 value is NULL. 00285 00286 Arguments: 00287 00288 Links - Supplies the pointer to a splay link in a tree 00289 00290 Return Values: 00291 00292 PRTI_SPLAY_LINKS - Returns a pointer to the root of the splayed tree 00293 00294 --*/ 00295 00296 { 00297 PTRI_SPLAY_LINKS Predecessor; 00298 PTRI_SPLAY_LINKS Parent; 00299 PTRI_SPLAY_LINKS Child; 00300 00301 PULONG ParentChildRef; 00302 00303 // 00304 // First check to see if Links as two children. If it does then swap 00305 // Links with its subtree predecessor. Now we are guaranteed that Links 00306 // has at most one child. 00307 // 00308 00309 if ((TriLeftChild(Links) != NULL) && (TriRightChild(Links) != NULL)) { 00310 00311 // 00312 // get the predecessor, and swap their position in the tree 00313 // 00314 00315 Predecessor = TriSubtreePredecessor(Links); 00316 TriSwapSplayLinks(Predecessor, Links); 00317 00318 } 00319 00320 // 00321 // If Links has no children then delete links by checking if it is 00322 // already the root or has a parent. If it is the root then the 00323 // tree is now empty, otherwise set the appropriate parent's child 00324 // pointer, and possibly sibling, and splay the parent. 00325 // 00326 00327 if ((TriLeftChild(Links) == NULL) && (TriRightChild(Links) == NULL)) { 00328 00329 // 00330 // Links has no children, if it is the root then return NULL 00331 // 00332 00333 if (TriIsRoot(Links)) { 00334 00335 return NULL; 00336 00337 } 00338 00339 // 00340 // Links has no children, check to see if links is an only child 00341 // 00342 00343 Parent = TriParent(Links); 00344 if (MakeIntoPointer(Parent->Refs.Child) == Links && 00345 MakeIntoPointer(Links->Refs.ParSib) == Parent) { 00346 00347 // 00348 // Links has no children and is an only child. So simply make 00349 // our parent have no children and splay our parent. 00350 // 00351 // Parent Parent 00352 // | ==> 00353 // Links 00354 // 00355 00356 Parent->Refs.Child = 0; 00357 return TriSplay(Parent); 00358 00359 } else if (TriIsLeftChild(Links)) { 00360 00361 // 00362 // Links has no children and has a right sibling. So make the 00363 // parent's child Ref be the right sibling, splay the parent. 00364 // 00365 // Parent Parent 00366 // / \ ==> \ 00367 // Links Sibling Sibling 00368 // 00369 00370 Parent->Refs.Child = MakeIntoRightChildRef(Links->Refs.ParSib); 00371 return TriSplay(Parent); 00372 00373 } else { // TriIsRightChild(Links) 00374 00375 // 00376 // Links has no children and has a left sibling. So make link's 00377 // back via its parent into a parent ref of link's parent, and 00378 // splay the parent. 00379 // 00380 // Parent Parent 00381 // / \ / 00382 // Sibling Links ==> Sibling 00383 // 00384 00385 ParentChildRef = TriAddressOfBackRefViaParent(Links); 00386 *ParentChildRef = MakeIntoParentRef(Parent); 00387 return TriSplay(Parent); 00388 00389 } 00390 00391 } 00392 00393 // 00394 // otherwise Links has one child. If it is the root then make the child 00395 // the new root, otherwise link together the child and parent, and splay 00396 // the parent. But first remember who our child is. 00397 // 00398 00399 if (TriLeftChild(Links) != NULL) { 00400 Child = TriLeftChild(Links); 00401 } else { 00402 Child = TriRightChild(Links); 00403 } 00404 00405 // 00406 // If links is the root then we make the child the root and return the 00407 // child. 00408 // 00409 00410 if (TriIsRoot(Links)) { 00411 Child->Refs.ParSib = MakeIntoParentRef(Child); 00412 return Child; 00413 } 00414 00415 // 00416 // Links is not the root, so set links's back ref via its parent to be 00417 // links's child and the set the child's ParSib to be link's ParSib, and 00418 // splay the parent. This will handle the case where link is an only 00419 // or has a sibling on either side. 00420 // 00421 00422 Parent = TriParent(Links); 00423 ParentChildRef = TriAddressOfBackRefViaParent(Links); 00424 SetRefViaPointer(ParentChildRef, Child); 00425 Child->Refs.ParSib = Links->Refs.ParSib; 00426 00427 return TriSplay(Parent); 00428 00429 }

00642 : 00643 00644 This RealPredecessor function takes as input a pointer to a splay link in 00645 a tree and returns a pointer to the predecessor of the input node within 00646 the entire tree. If there is not a predecessor, the return value is NULL. 00647 00648 Arguments: 00649 00650 Links - Supplies the pointer to a splay link in a tree 00651 00652 Return Values: 00653 00654 PRTI_SPLAY_LINKS - Returns a pointer to the predecessor in the entire tree 00655 00656 --*/ 00657 00658 { 00659 PTRI_SPLAY_LINKS Ptr; 00660 00661 // 00662 // first check to see if there is a left subtree to the input link 00663 // if there is then the real predecessor is the right most node in 00664 // the left subtree. That is find and return P in the following diagram 00665 // 00666 // Links 00667 // / 00668 // . 00669 // . 00670 // . 00671 // P 00672 // / 00673 // 00674 00675 if ((Ptr = TriLeftChild(Links)) != NULL) { 00676 00677 while (TriRightChild(Ptr) != NULL) { 00678 Ptr = TriRightChild(Ptr); 00679 } 00680 00681 return Ptr; 00682 00683 } 00684 00685 // 00686 // we do not have a left child so check to see if have a parent and if 00687 // so find the first ancestor that we are a right decendent of. That 00688 // is find and return P in the following diagram 00689 // 00690 // P 00691 // \ 00692 // . 00693 // . 00694 // . 00695 // Links 00696 // 00697 00698 Ptr = Links; 00699 while (TriIsLeftChild(Ptr)) { 00700 Ptr = TriParent(Ptr); 00701 } 00702 00703 if (!TriIsLeftChild(Ptr) && !TriIsRoot(Ptr)) { // (TriIsRightChild(Ptr)) { 00704 return TriParent(Ptr); 00705 } 00706 00707 // 00708 // Otherwise we do not have a real predecessor so we simply return NULL 00709 // 00710 00711 return NULL; 00712 00713 }

00560 : 00561 00562 This RealSuccess function takes as input a pointer to a splay link in a 00563 tree and returns a pointer to the successor of the input node within the 00564 entire tire. If there is not a successor, the return value is NULL. 00565 00566 Arguments: 00567 00568 Links - Supplies the pointer to a splay link in a tree 00569 00570 Return Values: 00571 00572 PRTI_SPLAY_LINKS - Returns a pointer to the successor in the entire tree 00573 00574 --*/ 00575 00576 { 00577 PTRI_SPLAY_LINKS Ptr; 00578 00579 // 00580 // first check to see if there is a right subtree to the input link 00581 // if there is then the real successor is the left most node in 00582 // the right subtree. That is find and return P in the following diagram 00583 // 00584 // Links 00585 // \ 00586 // . 00587 // . 00588 // . 00589 // / 00590 // P 00591 // \ 00592 // 00593 00594 if ((Ptr = TriRightChild(Links)) != NULL) { 00595 00596 while (TriLeftChild(Ptr) != NULL) { 00597 Ptr = TriLeftChild(Ptr); 00598 } 00599 00600 return Ptr; 00601 00602 } 00603 00604 // 00605 // we do not have a right child so check to see if have a parent and if 00606 // so find the first ancestor that we are a left decendent of. That 00607 // is find and return P in the following diagram 00608 // 00609 // P 00610 // / 00611 // . 00612 // . 00613 // . 00614 // Links 00615 // 00616 00617 Ptr = Links; 00618 while (!TriIsLeftChild(Ptr) && !TriIsRoot(Ptr)) { // (TriIsRightChild(Ptr)) { 00619 Ptr = TriParent(Ptr); 00620 } 00621 00622 if (TriIsLeftChild(Ptr)) { 00623 return TriParent(Ptr); 00624 } 00625 00626 // 00627 // Otherwise we do not have a real successor so we simply return NULL 00628 // 00629 00630 return NULL; 00631 00632 }

00119 : 00120 00121 This Splay function takes as input a pointer to a splay link in a tree 00122 and splays the tree. Its function return value is a pointer to the 00123 root of the splayed tree. 00124 00125 Arguments: 00126 00127 Links - Supplies the pointer to a splay link in a tree 00128 00129 Return Values: 00130 00131 PRTI_SPLAY_LINKS - Returns a pointer to the root of the splayed tree 00132 00133 --*/ 00134 00135 { 00136 PTRI_SPLAY_LINKS Parent; 00137 PTRI_SPLAY_LINKS GrandParent; 00138 00139 // 00140 // While Links is not the root we test and rotate until it is the root. 00141 // 00142 00143 while (!TriIsRoot(Links)) { 00144 00145 // 00146 // Get Parent and then check if we don't have a grandparent. 00147 // 00148 00149 Parent = TriParent(Links); 00150 00151 if (TriIsRoot(Parent)) { 00152 00153 // 00154 // No grandparent so check for single rotation 00155 // 00156 00157 if (TriIsLeftChild(Links)) { 00158 00159 // 00160 // do the following single rotation 00161 // 00162 // Parent Links 00163 // / ==> \ 00164 // Links Parent 00165 // 00166 00167 TriRotateRight(Parent); 00168 00169 } else { // TriIsRightChild(Links) 00170 00171 // 00172 // do the following single rotation 00173 // 00174 // 00175 // Parent Links 00176 // \ ==> / 00177 // Links Parent 00178 // 00179 00180 TriRotateLeft(Parent); 00181 00182 } 00183 00184 } else { // !TriIsRoot(Parent) 00185 00186 // 00187 // Get grandparent and check for the four double rotation 00188 // cases 00189 // 00190 00191 GrandParent = TriParent(Parent); 00192 00193 if (TriIsLeftChild(Links)) { 00194 00195 if (TriIsLeftChild(Parent)) { 00196 00197 // 00198 // do the following double rotation 00199 // 00200 // GP L 00201 // / \ 00202 // P ==> P 00203 // / \ 00204 // L GP 00205 // 00206 00207 TriRotateRight(GrandParent); 00208 TriRotateRight(Parent); 00209 00210 } else { // TriIsRightChild(Parent) 00211 00212 // 00213 // do the following double rotation 00214 // 00215 // GP L 00216 // \ / \ 00217 // P ==> GP P 00218 // / 00219 // L 00220 // 00221 00222 TriRotateRight(Parent); 00223 TriRotateLeft(GrandParent); 00224 00225 } 00226 00227 } else { // TriIsRightChild(Links); 00228 00229 if (TriIsLeftChild(Parent)) { 00230 00231 // 00232 // do the following double rotation 00233 // 00234 // GP L 00235 // / / \ 00236 // P ==> P GP 00237 // \ 00238 // L 00239 // 00240 00241 TriRotateLeft(Parent); 00242 TriRotateRight(GrandParent); 00243 00244 } else { // TriIsRightChild(Parent) 00245 00246 // 00247 // do the following double rotation 00248 // 00249 // GP L 00250 // \ / 00251 // P ==> P 00252 // \ / 00253 // L GP 00254 // 00255 00256 TriRotateLeft(GrandParent); 00257 TriRotateLeft(Parent); 00258 00259 } 00260 00261 } 00262 00263 } 00264 00265 } 00266 00267 return Links; 00268 00269 }

00500 : 00501 00502 This SubTreePredecessor function takes as input a pointer to a splay link 00503 in a tree and returns a pointer to the predecessor of the input node of 00504 the subtree rooted at the input node. If there is not a predecessor, 00505 the return value is NULL. 00506 00507 Arguments: 00508 00509 Links - Supplies the pointer to a splay link in a tree 00510 00511 Return Values: 00512 00513 PRTI_SPLAY_LINKS - Returns a pointer to the predecessor in the subtree 00514 00515 --*/ 00516 00517 { 00518 PTRI_SPLAY_LINKS Ptr; 00519 00520 // 00521 // check to see if there is a left subtree to the input link 00522 // if there is then the subtree predecessor is the right most node in 00523 // the left subtree. That is find and return P in the following diagram 00524 // 00525 // Links 00526 // / 00527 // . 00528 // . 00529 // . 00530 // P 00531 // / 00532 // 00533 00534 if ((Ptr = TriLeftChild(Links)) != NULL) { 00535 00536 while (TriRightChild(Ptr) != NULL) { 00537 Ptr = TriRightChild(Ptr); 00538 } 00539 00540 return Ptr; 00541 00542 } 00543 00544 // 00545 // Otherwise we do not have a subtree predecessor so we simply return NULL 00546 // 00547 00548 return NULL; 00549 00550 }

00439 : 00440 00441 This SubTreeSuccessor function takes as input a pointer to a splay link 00442 in a tree and returns a pointer to the successor of the input node of 00443 the subtree rooted at the input node. If there is not a successor, the 00444 return value is NULL. 00445 00446 Arguments: 00447 00448 Links - Supplies the pointer to a splay link in a tree 00449 00450 Return Values: 00451 00452 PRTI_SPLAY_LINKS - Returns a pointer to the successor in the subtree 00453 00454 --*/ 00455 00456 { 00457 PTRI_SPLAY_LINKS Ptr; 00458 00459 // 00460 // check to see if there is a right subtree to the input link 00461 // if there is then the subtree successor is the left most node in 00462 // the right subtree. That is find and return P in the following diagram 00463 // 00464 // Links 00465 // \ 00466 // . 00467 // . 00468 // . 00469 // / 00470 // P 00471 // \ 00472 // 00473 00474 if ((Ptr = TriRightChild(Links)) != NULL) { 00475 00476 while (TriLeftChild(Ptr) != NULL) { 00477 Ptr = TriLeftChild(Ptr); 00478 } 00479 00480 return Ptr; 00481 00482 } 00483 00484 // 00485 // Otherwise we do not have a subtree successor so we simply return NULL 00486 // 00487 00488 return NULL; 00489 00490 }


Classes
union	_TRI_SPLAY_LINKS
Defines
#define	TriInitializeSplayLinks(Links)
#define	TriParent(Links)
#define	TriLeftChild(Links)
#define	TriRightChild(Links)
#define	TriIsRoot(Links)
#define	TriIsLeftChild(Links)
#define	TriIsRightChild(Links)
#define	TriInsertAsLeftChild(ParentLinks, ChildLinks)
#define	TriInsertAsRightChild(ParentLinks, ChildLinks)
#define	IsParentRef(Ulong) (((((ULONG)Ulong) & 1) == 0) && ((Ulong) != 0) ? TRUE : FALSE)
#define	MakeIntoParentRef(Ulong) (((ULONG)Ulong) & 0xfffffffc)
#define	IsSiblingRef(Ulong) ((((ULONG)Ulong) & 1) == 1 ? TRUE : FALSE)
#define	MakeIntoSiblingRef(Ulong) (((ULONG)Ulong) \| 1)
#define	IsLeftChildRef(Ulong) (((((ULONG)Ulong) & 1) == 0) && ((Ulong) != 0) ? TRUE : FALSE)
#define	MakeIntoLeftChildRef(Ulong) (((ULONG)Ulong) & 0xfffffffc)
#define	IsRightChildRef(Ulong) ((((ULONG)Ulong) & 1) == 1 ? TRUE : FALSE)
#define	MakeIntoRightChildRef(Ulong) (((ULONG)Ulong) \| 1)
#define	MakeIntoPointer(Ulong) ((PTRI_SPLAY_LINKS)((Ulong) & 0xfffffffc))
Typedefs
typedef _TRI_SPLAY_LINKS	TRI_SPLAY_LINKS
typedef TRI_SPLAY_LINKS *	PTRI_SPLAY_LINKS
Functions
PTRI_SPLAY_LINKS	TriSplay (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriDelete (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriSubtreeSuccessor (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriSubtreePredecessor (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriRealSuccessor (IN PTRI_SPLAY_LINKS Links)
PTRI_SPLAY_LINKS	TriRealPredecessor (IN PTRI_SPLAY_LINKS Links)

triangle.h File Reference

Classes

Defines

Typedefs

Functions

Define Documentation

Typedef Documentation

Function Documentation