00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #include "stdafx.h"
00021
00022 #include <stdio.h>
00023 #include <stdlib.h>
00024 #include <iostream>
00025 #include <math.h>
00026 #include "gul_types.h"
00027 #include "guma_sorting.h"
00028
00029
00030 namespace guma {
00031
00032 using gul::Ptr;
00033 using std::cout;
00034
00035
00036
00037
00038 GULAPI void HeapSort( size_t nelem, size_t elsize, void *elptr,
00039 int (*usrfunc)( void *, void *, void *), void *usrdata )
00040 {
00041 char *ra, *rra;
00042 size_t n = nelem, l, ir, i, j;
00043
00044 rra = (char *)alloca( elsize );
00045 if( rra == NULL ) return;
00046
00047 ra = (char *)elptr;
00048
00049 if( n < 2 ) return;
00050 l = (n >> 1) + 1;
00051 ir = n;
00052
00053 for(;;)
00054 {
00055 if( l > 1 )
00056 {
00057 memcpy( rra, &ra[(l-2)*elsize], elsize );
00058 l--;
00059 }
00060 else
00061 {
00062 memcpy( rra, &ra[(ir-1)*elsize], elsize );
00063 memcpy( &ra[(ir-1)*elsize], ra, elsize );
00064 if( --ir == 1 )
00065 {
00066 memcpy( ra, rra, elsize );
00067 break;
00068 }
00069 }
00070 i = l;
00071 j = l+l;
00072
00073 while( j <= ir )
00074 {
00075 if( (j < ir) &&
00076 (usrfunc( &ra[(j-1)*elsize], &ra[j*elsize], usrdata ) < 0) )
00077 j++;
00078
00079 if( usrfunc(rra, &ra[(j-1)*elsize], usrdata) < 0 )
00080 {
00081 memcpy( &ra[(i-1)*elsize], &ra[(j-1)*elsize], elsize );
00082 i = j;
00083 j <<= 1;
00084 }
00085 else
00086 j = ir + 1;
00087 }
00088 memcpy( &ra[(i-1)*elsize], rra, elsize );
00089 }
00090 return;
00091 }
00092
00093 GULAPI void PtrHeapSort( size_t nelem, void **elptr,
00094 int (*usrfunc)( void *, void *, void *), void *usrdata )
00095 {
00096 void **ra, *rra;
00097 size_t n = nelem, l, ir, i, j;
00098
00099 ra = elptr;
00100
00101 if( n < 2 ) return;
00102 l = (n >> 1) + 1;
00103 ir = n;
00104
00105 for(;;)
00106 {
00107 if( l > 1 )
00108 {
00109 rra = ra[l-2];
00110 l--;
00111 }
00112 else
00113 {
00114 rra = ra[ir-1];
00115 ra[ir-1] = ra[0];
00116
00117 if( --ir == 1 )
00118 {
00119 ra[0] = rra;
00120 break;
00121 }
00122 }
00123 i = l;
00124 j = l+l;
00125
00126 while( j <= ir )
00127 {
00128 if( (j < ir) &&
00129 (usrfunc( ra[j-1], ra[j], usrdata ) < 0) )
00130 j++;
00131
00132 if( usrfunc( rra, ra[j-1], usrdata) < 0 )
00133 {
00134 ra[i-1] = ra[j-1];
00135 i = j;
00136 j <<= 1;
00137 }
00138 else
00139 j = ir + 1;
00140 }
00141
00142 ra[i-1] = rra;
00143 }
00144 }
00145
00146
00147 GULAPI void heapsort( int nA, Ptr<void *>& A ) { _heapsort( nA, A ); }
00148 GULAPI void heapsort( int nA, Ptr<int>& A ) { _heapsort( nA, A ); }
00149
00150
00151 GULAPI int BinarySearch( int x, int nA, const gul::Ptr<int>& A )
00152 { return _BinarySearch( x, nA, A); }
00153 GULAPI int BinarySearch( void *x, int nA, const gul::Ptr<void *>& A )
00154 { return _BinarySearch( x, nA, A); }
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 GULAPI void InitBBT( BBTNode *head )
00167 {
00168 head->F.b = 1;
00169 head->F.l = 0;
00170
00171 (*((int *)(&head->left))) = 0;
00172 head->right = NULL;
00173 }
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183 GULAPI int SearchElementInBBT( BBTNode *head, void *key,
00184 int compare( void *, void * ),
00185 BBTNode **element )
00186 {
00187 int result;
00188 BBTNode *P,*el;
00189
00190 el = head;
00191 result = 1;
00192 P = head->right;
00193
00194 while( P != NULL )
00195 {
00196 el = P;
00197 result = compare( key, P->key );
00198
00199 if( result < 0 )
00200 {
00201 P = P->left;
00202 }
00203 else if( result > 0 )
00204 {
00205 P = P->right;
00206 }
00207 else
00208 break;
00209 }
00210
00211 *element = el;
00212 return(result);
00213 }
00214
00215
00216
00217
00218
00219 GULAPI BBTNode *SearchSuccessorInBBT( BBTNode *element, BBTNode *head )
00220 {
00221 BBTNode *N = element, *L, *P;
00222
00223 if( N->right )
00224 {
00225 N = N->right;
00226 for(;;)
00227 {
00228 L = N->left;
00229 if( L == NULL ) return N;
00230 N = L;
00231 }
00232 }
00233 else
00234 {
00235 for(;;)
00236 {
00237 if( N == head ) return NULL;
00238 P = N->parent;
00239 if( N->F.l == -1 ) return P;
00240 N = P;
00241 }
00242 }
00243 }
00244
00245
00246
00247
00248
00249 GULAPI BBTNode *SearchPredecessorInBBT( BBTNode *element, BBTNode *head )
00250 {
00251 BBTNode *N = element, *R, *P;
00252
00253 if( N->left )
00254 {
00255 N = N->left;
00256 for(;;)
00257 {
00258 R = N->right;
00259 if( R == NULL ) return N;
00260 N = R;
00261 }
00262 }
00263 else
00264 {
00265 for(;;)
00266 {
00267 P = N->parent;
00268 if( P == head ) return NULL;
00269 if( N->F.l == +1 ) return P;
00270 N = P;
00271 }
00272 }
00273 }
00274
00275
00276
00277
00278
00279
00280
00281 GULAPI void InsertElementIntoBBT( BBTNode *element,
00282 BBTNode *where, int side, BBTNode *head )
00283 {
00284 BBTNode *Q, *Pk, *Pk_1, *A, *B, *X;
00285 int ak, ak_1;
00286
00287 Q = element;
00288 Q->left = Q->right = NULL;
00289 Q->F.b = 0;
00290
00291 Pk = where;
00292 ak = side;
00293
00294 if( ak == -1 )
00295 {
00296 Pk->left = Q;
00297 if( Pk->left != NULL )
00298 {
00299 Pk->left->parent = Pk;
00300 Pk->left->F.l = -1;
00301 }
00302 }
00303 else
00304 {
00305 Pk->right = Q;
00306 if( Pk->right != NULL )
00307 {
00308 Pk->right->parent = Pk;
00309 Pk->right->F.l = 1;
00310 }
00311 }
00312
00313 while( (Pk->F.b == 0) && (Pk != head) )
00314 {
00315 Pk->F.b = ak;
00316 ak = Pk->F.l;
00317 Pk = Pk->parent;
00318 }
00319
00320 if( Pk == head )
00321 {
00322 (*((int *)(&head->left)))++;
00323 return;
00324 }
00325
00326 if( ak == -1 )
00327 {
00328 A = Pk;
00329 Pk_1 = Pk->parent;
00330 ak_1 = Pk->F.l;
00331
00332 if( A->F.b == 1 )
00333 {
00334 A->F.b = 0;
00335 return;
00336 }
00337 else
00338 {
00339 B = Pk->left;
00340
00341 if( B->F.b == -1 )
00342 {
00343 A->left = B->right;
00344 if( A->left != NULL )
00345 {
00346 A->left->parent = A;
00347 A->left->F.l = -1;
00348 }
00349
00350 B->right = A;
00351 if( B->right != NULL )
00352 {
00353 B->right->parent = B;
00354 B->right->F.l = 1;
00355 }
00356
00357 A->F.b = B->F.b = 0;
00358
00359 ak = ak_1;
00360 Pk = Pk_1;
00361
00362 if( ak == -1 )
00363 {
00364 Pk->left = B;
00365 if( Pk->left != NULL )
00366 {
00367 Pk->left->parent = Pk;
00368 Pk->left->F.l = -1;
00369 }
00370 }
00371 else
00372 {
00373 Pk->right = B;
00374 if( Pk->right != NULL )
00375 {
00376 Pk->right->parent = Pk;
00377 Pk->right->F.l = 1;
00378 }
00379 }
00380
00381 return;
00382 }
00383 else
00384 {
00385 X = B->right;
00386
00387 A->left = X->right;
00388 if( A->left != NULL )
00389 {
00390 A->left->parent = A;
00391 A->left->F.l = -1;
00392 }
00393
00394 B->right = X->left;
00395 if( B->right != NULL )
00396 {
00397 B->right->parent = B;
00398 B->right->F.l = 1;
00399 }
00400
00401 X->left = B;
00402 if( X->left != NULL )
00403 {
00404 X->left->parent = X;
00405 X->left->F.l = -1;
00406 }
00407
00408 X->right = A;
00409 if( X->right != NULL )
00410 {
00411 X->right->parent = X;
00412 X->right->F.l = 1;
00413 }
00414
00415 if( X->F.b == 1 )
00416 {
00417 B->F.b = -1;
00418 A->F.b = 0;
00419 }
00420 else if( X->F.b == -1 )
00421 {
00422 B->F.b = 0;
00423 A->F.b = 1;
00424 }
00425 else
00426 {
00427 B->F.b = 0;
00428 A->F.b = 0;
00429 }
00430 X->F.b = 0;
00431
00432 ak = ak_1;
00433 Pk = Pk_1;
00434
00435 if( ak == -1 )
00436 {
00437 Pk->left = X;
00438 if( Pk->left != NULL )
00439 {
00440 Pk->left->parent = Pk;
00441 Pk->left->F.l = -1;
00442 }
00443 }
00444 else
00445 {
00446 Pk->right = X;
00447 if( Pk->right != NULL )
00448 {
00449 Pk->right->parent = Pk;
00450 Pk->right->F.l = 1;
00451 }
00452 }
00453
00454 return;
00455 }
00456 }
00457 }
00458
00459
00460 else
00461 {
00462 A = Pk;
00463 Pk_1 = Pk->parent;
00464 ak_1 = Pk->F.l;
00465
00466 if( A->F.b == -1 )
00467 {
00468 A->F.b = 0;
00469 return;
00470 }
00471 else
00472 {
00473 B = Pk->right;
00474
00475 if( B->F.b == 1 )
00476 {
00477 A->right = B->left;
00478 if( A->right != NULL )
00479 {
00480 A->right->parent = A;
00481 A->right->F.l = 1;
00482 }
00483
00484 B->left = A;
00485 if( B->left != NULL )
00486 {
00487 B->left->parent = B;
00488 B->left->F.l = -1;
00489 }
00490
00491 A->F.b = B->F.b = 0;
00492
00493 ak = ak_1;
00494 Pk = Pk_1;
00495
00496 if( ak == -1 )
00497 {
00498 Pk->left = B;
00499 if( Pk->left != NULL )
00500 {
00501 Pk->left->parent = Pk;
00502 Pk->left->F.l = -1;
00503 }
00504 }
00505 else
00506 {
00507 Pk->right = B;
00508 if( Pk->right != NULL )
00509 {
00510 Pk->right->parent = Pk;
00511 Pk->right->F.l = 1;
00512 }
00513 }
00514
00515 return;
00516 }
00517 else
00518 {
00519 X = B->left;
00520
00521 A->right = X->left;
00522 if( A->right != NULL )
00523 {
00524 A->right->parent = A;
00525 A->right->F.l = 1;
00526 }
00527
00528 B->left = X->right;
00529 if( B->left != NULL )
00530 {
00531 B->left->parent = B;
00532 B->left->F.l = -1;
00533 }
00534
00535 X->right = B;
00536 if( X->right != NULL )
00537 {
00538 X->right->parent = X;
00539 X->right->F.l = 1;
00540 }
00541
00542 X->left = A;
00543 if( X->left != NULL )
00544 {
00545 X->left->parent = X;
00546 X->left->F.l = -1;
00547 }
00548
00549 if( X->F.b == -1 )
00550 {
00551 B->F.b = 1;
00552 A->F.b = 0;
00553 }
00554 else if( X->F.b == 1 )
00555 {
00556 B->F.b = 0;
00557 A->F.b = -1;
00558 }
00559 else
00560 {
00561 B->F.b = 0;
00562 A->F.b = 0;
00563 }
00564 X->F.b = 0;
00565
00566 ak = ak_1;
00567 Pk = Pk_1;
00568
00569 if( ak == -1 )
00570 {
00571 Pk->left = X;
00572 if( Pk->left != NULL )
00573 {
00574 Pk->left->parent = Pk;
00575 Pk->left->F.l = -1;
00576 }
00577 }
00578 else
00579 {
00580 Pk->right = X;
00581 if( Pk->right != NULL )
00582 {
00583 Pk->right->parent = Pk;
00584 Pk->right->F.l = 1;
00585 }
00586 }
00587
00588 return;
00589 }
00590 }
00591 }
00592 }
00593
00594
00595
00596
00597
00598
00599
00600
00601 GULAPI void DeleteElementFromBBT( BBTNode *element, BBTNode *head )
00602 {
00603 BBTNode *P,*Q,*Pk,*Pk_1,*A,*B,*X;
00604 int ak, ak_1, ak_ini;
00605
00606 P = head->right;
00607 if( P == NULL ) return;
00608
00609 P = Q = element;
00610
00611 if( P->right == NULL )
00612 {
00613 Pk = P;
00614 ak = 1;
00615 Pk_1 = Pk->parent;
00616 ak_1 = ak_ini = Pk->F.l;
00617 }
00618 else if( P->left == NULL )
00619 {
00620 Pk = P;
00621 ak = -1;
00622 Pk_1 = Pk->parent;
00623 ak_1 = ak_ini = Pk->F.l;
00624 }
00625 else
00626 {
00627 P = P->right;
00628
00629 if( P->left == NULL )
00630 {
00631 Pk = Q;
00632
00633 if( Q->F.l == 1 )
00634 {
00635 Q->parent->right = P;
00636 P->F.l = 1;
00637 }
00638 else
00639 {
00640 Q->parent->left = P;
00641 P->F.l = -1;
00642 }
00643 P->parent = Q->parent;
00644 P->F.b = Q->F.b;
00645
00646 ak = 1;
00647 Pk_1 = P;
00648 ak_1 = -1;
00649 ak_ini = 1;
00650 }
00651 else
00652 {
00653 do
00654 {
00655 Pk = P;
00656 P = P->left;
00657 }
00658 while( P != NULL );
00659
00660 ak = -1;
00661 Pk_1 = Pk->parent;
00662 ak_1 = ak_ini = Pk->F.l;
00663 }
00664 }
00665
00666
00667
00668 if( ak_1 == -1 )
00669 {
00670 Pk_1->left = (ak == -1 ? Pk->right : Pk->left);
00671 if( Pk_1->left != NULL )
00672 {
00673 Pk_1->left->parent = Pk_1;
00674 Pk_1->left->F.l = -1;
00675 }
00676 }
00677 else
00678 {
00679 Pk_1->right = (ak == -1 ? Pk->right : Pk->left);
00680 if( Pk_1->right != NULL )
00681 {
00682 Pk_1->right->parent = Pk_1;
00683 Pk_1->right->F.l = 1;
00684 }
00685 }
00686
00687 if( Pk != Q )
00688 {
00689 Pk->left = Q->left;
00690 if( Pk->left != NULL )
00691 Pk->left->parent = Pk;
00692 Pk->right = Q->right;
00693 if( Pk->right != NULL )
00694 Pk->right->parent = Pk;
00695
00696 Pk->F.b = Q->F.b;
00697
00698 Pk->parent = Q->parent;
00699 Pk->F.l = Q->F.l;
00700 if( Pk->F.l == -1 )
00701 Pk->parent->left = Pk;
00702 else
00703 Pk->parent->right = Pk;
00704 }
00705
00706
00707
00708
00709 ak = ak_ini;
00710 Pk = Pk_1;
00711
00712 while( 1 )
00713 {
00714 if( Pk == head )
00715 {
00716 (*((int *)&head->left))--;
00717 break;
00718 }
00719 else if( Pk->F.b == ak )
00720 {
00721 Pk->F.b = 0;
00722
00723 ak = Pk->F.l;
00724 Pk = Pk->parent;
00725 }
00726 else if( Pk->F.b == 0 )
00727 {
00728 Pk->F.b = -ak;
00729 break;
00730 }
00731 else
00732 {
00733 if( ak == -1 )
00734 {
00735 A = Pk;
00736 ak_1 = Pk->F.l;
00737 Pk_1 = Pk->parent;
00738
00739 B = A->right;
00740
00741 if( B->F.b == 1 )
00742 {
00743 A->right = B->left;
00744 if( A->right != NULL )
00745 {
00746 A->right->parent = A;
00747 A->right->F.l = 1;
00748 }
00749
00750 B->left = A;
00751 if( B->left != NULL )
00752 {
00753 B->left->parent = B;
00754 B->left->F.l = -1;
00755 }
00756
00757 A->F.b = B->F.b = 0;
00758
00759 ak = ak_1;
00760 Pk = Pk_1;
00761
00762 if( ak == -1 )
00763 {
00764 Pk->left = B;
00765 if( Pk->left != NULL )
00766 {
00767 Pk->left->parent = Pk;
00768 Pk->left->F.l = -1;
00769 }
00770 }
00771 else
00772 {
00773 Pk->right = B;
00774 if( Pk->right != NULL )
00775 {
00776 Pk->right->parent = Pk;
00777 Pk->right->F.l = 1;
00778 }
00779 }
00780 }
00781 else if( B->F.b == -1 )
00782 {
00783 X = B->left;
00784
00785 A->right = X->left;
00786 if( A->right != NULL )
00787 {
00788 A->right->parent = A;
00789 A->right->F.l = 1;
00790 }
00791
00792 B->left = X->right;
00793 if( B->left != NULL )
00794 {
00795 B->left->parent = B;
00796 B->left->F.l = -1;
00797 }
00798
00799 X->left = A;
00800 if( X->left != NULL )
00801 {
00802 X->left->parent = X;
00803 X->left->F.l = -1;
00804 }
00805
00806 X->right = B;
00807 if( X->right != NULL )
00808 {
00809 X->right->parent = X;
00810 X->right->F.l = 1;
00811 }
00812
00813 if( X->F.b == -1 )
00814 {
00815 A->F.b = 0;
00816 B->F.b = 1;
00817 }
00818 else if( X->F.b == 1 )
00819 {
00820 A->F.b = -1;
00821 B->F.b = 0;
00822 }
00823 else
00824 {
00825 A->F.b = 0;
00826 B->F.b = 0;
00827 }
00828 X->F.b = 0;
00829
00830 ak = ak_1;
00831 Pk = Pk_1;
00832
00833 if( ak == -1 )
00834 {
00835 Pk->left = X;
00836 if( Pk->left != NULL )
00837 {
00838 Pk->left->parent = Pk;
00839 Pk->left->F.l = -1;
00840 }
00841 }
00842 else
00843 {
00844 Pk->right = X;
00845 if( Pk->right != NULL )
00846 {
00847 Pk->right->parent = Pk;
00848 Pk->right->F.l = 1;
00849 }
00850 }
00851 }
00852 else
00853 {
00854 A->right = B->left;
00855 if( A->right != NULL )
00856 {
00857 A->right->parent = A;
00858 A->right->F.l = 1;
00859 }
00860
00861 B->left = A;
00862 if( B->left != NULL )
00863 {
00864 B->left->parent = B;
00865 B->left->F.l = -1;
00866 }
00867
00868 B->F.b = -1;
00869
00870 ak = ak_1;
00871 Pk = Pk_1;
00872
00873 if( ak == -1 )
00874 {
00875 Pk->left = B;
00876 if( Pk->left != NULL )
00877 {
00878 Pk->left->parent = Pk;
00879 Pk->left->F.l = -1;
00880 }
00881 }
00882 else
00883 {
00884 Pk->right = B;
00885 if( Pk->right != NULL )
00886 {
00887 Pk->right->parent = Pk;
00888 Pk->right->F.l = 1;
00889 }
00890 }
00891
00892 break;
00893 }
00894
00895
00896 }
00897 else
00898 {
00899 A = Pk;
00900 ak_1 = Pk->F.l;
00901 Pk_1 = Pk->parent;
00902
00903 B = A->left;
00904
00905 if( B->F.b == -1 )
00906 {
00907 A->left = B->right;
00908 if( A->left != NULL )
00909 {
00910 A->left->parent = A;
00911 A->left->F.l = -1;
00912 }
00913
00914 B->right = A;
00915 if( B->right != NULL )
00916 {
00917 B->right->parent = B;
00918 B->right->F.l = 1;
00919 }
00920
00921 A->F.b = B->F.b = 0;
00922
00923 ak = ak_1;
00924 Pk = Pk_1;
00925
00926 if( ak == -1 )
00927 {
00928 Pk->left = B;
00929 if( Pk->left != NULL )
00930 {
00931 Pk->left->parent = Pk;
00932 Pk->left->F.l = -1;
00933 }
00934 }
00935 else
00936 {
00937 Pk->right = B;
00938 if( Pk->right != NULL )
00939 {
00940 Pk->right->parent = Pk;
00941 Pk->right->F.l = 1;
00942 }
00943 }
00944 }
00945 else if( B->F.b == 1 )
00946 {
00947 X = B->right;
00948
00949 A->left = X->right;
00950 if( A->left != NULL )
00951 {
00952 A->left->parent = A;
00953 A->left->F.l = -1;
00954 }
00955
00956 B->right = X->left;
00957 if( B->right != NULL )
00958 {
00959 B->right->parent = B;
00960 B->right->F.l = 1;
00961 }
00962
00963 X->right = A;
00964 if( X->right != NULL )
00965 {
00966 X->right->parent = X;
00967 X->right->F.l = 1;
00968 }
00969
00970 X->left = B;
00971 if( X->left != NULL )
00972 {
00973 X->left->parent = X;
00974 X->left->F.l = -1;
00975 }
00976
00977 if( X->F.b == 1 )
00978 {
00979 A->F.b = 0;
00980 B->F.b = -1;
00981 }
00982 else if( X->F.b == -1 )
00983 {
00984 A->F.b = 1;
00985 B->F.b = 0;
00986 }
00987 else
00988 {
00989 A->F.b = 0;
00990 B->F.b = 0;
00991 }
00992 X->F.b = 0;
00993
00994 ak = ak_1;
00995 Pk = Pk_1;
00996
00997 if( ak == -1 )
00998 {
00999 Pk->left = X;
01000 if( Pk->left != NULL )
01001 {
01002 Pk->left->parent = Pk;
01003 Pk->left->F.l = -1;
01004 }
01005 }
01006 else
01007 {
01008 Pk->right = X;
01009 if( Pk->right != NULL )
01010 {
01011 Pk->right->parent = Pk;
01012 Pk->right->F.l = 1;
01013 }
01014 }
01015 }
01016 else
01017 {
01018 A->left = B->right;
01019 if( A->left != NULL )
01020 {
01021 A->left->parent = A;
01022 A->left->F.l = -1;
01023 }
01024
01025 B->right = A;
01026 if( B->right != NULL )
01027 {
01028 B->right->parent = B;
01029 B->right->F.l = 1;
01030 }
01031
01032 B->F.b = 1;
01033
01034 ak = ak_1;
01035 Pk = Pk_1;
01036
01037 if( ak == -1 )
01038 {
01039 Pk->left = B;
01040 if( Pk->left != NULL )
01041 {
01042 Pk->left->parent = Pk;
01043 Pk->left->F.l = -1;
01044 }
01045 }
01046 else
01047 {
01048 Pk->right = B;
01049 if( Pk->right != NULL )
01050 {
01051 Pk->right->parent = Pk;
01052 Pk->right->F.l = 1;
01053 }
01054 }
01055
01056 break;
01057 }
01058 }
01059 }
01060 }
01061
01062 return;
01063 }
01064
01065
01066
01067
01068
01069 GULAPI void DumpBBTTree( BBTNode *node, int level,
01070 void dumpkey_func( void * ) )
01071 {
01072 int i;
01073
01074 if( node == NULL )
01075 return;
01076
01077 if( node->left != NULL )
01078 DumpBBTTree( node->left, level+4, dumpkey_func );
01079
01080 for( i = 0; i < level; i++ )
01081 {
01082 cout << " ";
01083 }
01084
01085 if( node->key != NULL )
01086 dumpkey_func( node->key );
01087 cout << "\n";
01088
01089 if( node->right != NULL )
01090 DumpBBTTree( node->right, level+4, dumpkey_func );
01091 }
01092
01093
01094
01095
01096
01097 GULAPI void DumpBBTNode( BBTNode *node, int level )
01098 {
01099 int i;
01100
01101 if( node == NULL )
01102 return;
01103
01104 if( node->left != NULL )
01105 DumpBBTNode( node->left, level+4 );
01106
01107 for( i = 0; i < level; i++ )
01108 {
01109 cout << " ";
01110 }
01111 cout << (void *)node << ":[b:" << node->F.b << ", l:" << node->F.l <<
01112 "] (l=" << (void *)node->left << ", r=" <<
01113 (void *)node->right << ", p=" << (void *)node->parent << ")\n";
01114
01115 if( node->right != NULL )
01116 DumpBBTNode( node->right, level+4 );
01117 }
01118
01119
01120 }
01121
01122
01123
01124
01125
01126
01127
01128
01129
01130