dyninstAPI/h/BPatch_Set.h

   1 #ifndef _BPatch_Set_h_
   2 #define _BPatch_Set_h_
   3
   4 //ifdef this to nothing if it bothers old broken compilers
   5 #define TYPENAME typename
   6
   7 #if defined(external_templates)
   8 #pragma interface
   9 #endif
  10
  11 /*******************************************************/
  12 /*              header files                           */
  13 /*******************************************************/
  14
  15 #include <assert.h>
  16 #include <stdlib.h>
  17 #include "BPatch_dll.h"
  18
  19 #if !defined(DO_INLINE_P)
  20 #define DO_INLINE_P
  21 #endif
  22
  23 #if !defined(DO_INLINE_F)
  24 #define DO_INLINE_F
  25 #endif
  26
  27 /** template struct that will be used for default compare
  28   * class for BPatch_Set operations.
  29   */
  30
  31 // VG: shouldn't this be a dll export?
  32 template<class T>
  33 struct comparison {
  34         /** default comparison operator
  35           * returns -1 if the first arg < second arg
  36           * returns 1 if the first arg > second arg
  37           * returns 0 if the first arg == second arg
  38           * @param x first argument to be compared
  39           * @param y second argument to be compared
  40           */
  41         int operator()(const T& x, const T& y) const {
  42                 if(x<y) return -1;
  43                 if(x>y) return 1;
  44                 return 0;
  45         }
  46 };
  47
  48 /** template class for BPatch_Set. The implementation is based on red black
  49   * tree implementation for efficiency concerns and for getting sorted
  50   * elements easier. The template depends on two types. The first one is the
  51   * the type of the elements in the BPatch_Set and the second one is the template
  52   * structure that is used to compare the elements of the BPatch_Set. The template
  53   * structure has to overload () for comparison of two elements as explained above
  54   */
  55
  56 #if defined i386_unknown_nt4_0 || defined mips_unknown_ce2_11 //ccw 6 apr 2001
  57
  58 static const bool RED = true;
  59 static const bool BLACK = false;
  60
  61 #endif
  62
  63 template<class T,class Compare = comparison<T> >
  64 class BPATCH_DLL_EXPORT BPatch_Set {
  65 private:
  66
  67 #if ! (defined i386_unknown_nt4_0 || defined mips_unknown_ce2_11) //ccw 6 apr 2001
  68         /** color variable used for red-black tree */
  69         static const bool RED = true;
  70
  71         /** color variable used for red-black tree */
  72         static const bool BLACK = false;
  73 #endif
  74
  75         /** tree implementation structure. Used to implement the RB tree */
  76         typedef struct entry {
  77                 T data;         /* data  element */
  78                 bool color;     /* color of the node true=red,false=blue*/
  79                 struct entry* left; /* left child */
  80                 struct entry* right; /* right child */
  81                 struct entry* parent; /* parent of the node */
  82
  83                 /** constructor for structure */
  84                 entry()
  85                         : color(BLACK),left(NULL),right(NULL),parent(NULL) {}
  86
  87                 /** constructor used for non-nil elements
  88                   * @param e nil entry
  89                   */
  90                 entry(entry* e) //constructor with nil entry
  91                         : color(RED),left(e),right(e),parent(NULL) {}
  92
  93                 /** constructor
  94                   * @param d data element
  95                   * @param e nill entry
  96                   */
  97                 entry(const T& d,entry* e)
  98                         : data(d),color(RED),left(e),right(e),parent(NULL){}
  99
 100                 /** constrcutor
 101                   * @param e the entry structure that will be copied
 102                   */
 103                 entry(const entry& e) : data(e.data),color(e.color),
 104                         left(NULL),right(NULL),parent(NULL) {}
 105         } entry;
 106
 107         /** pointer to define the nil element of the tree NULL is not used
 108           * since some operations need sentinel nil which may have non-nil
 109           * parent.
 110           */
 111         entry* nil;
 112
 113         /** size of the BPatch_Set */
 114         int setSize;
 115
 116         /** pointer to the tree structure */
 117         entry* setData;
 118
 119         /** the structure that will be used for comparisons. Default is the
 120           * the comparsion structure explained above */
 121         Compare compareFunc;
 122
 123         // method that replicates the tree structure of this tree
 124         DO_INLINE_P entry* replicateTree(entry*,entry*,entry*,entry*);
 125
 126         // method that implements left rotattion used by RB tree for balanced
 127         // tree construction and keeps the RBtree properties.
 128         DO_INLINE_P void leftRotate(entry*);
 129
 130         // method that implements right rotattion used by RB tree for balanced
 131         // tree construction and keeps the RBtree properties.
 132         DO_INLINE_P void rightRotate(entry*);
 133
 134         // method that modifies the tree structure after deletion for keeping
 135         // the RBtree properties.
 136         DO_INLINE_P void deleteFixup(entry*);
 137
 138         // insertion to a binary search tree. It returns the new element pointer
 139         // that is inserted. If element is already there it returns NULL
 140         DO_INLINE_P entry* treeInsert(const T&);
 141
 142         // finds the elemnts in the tree that will be replaced with the element
 143         // being deleted in the  deletion. That is the element with the largets
 144         // smallest value than the element being deleted.
 145         DO_INLINE_P entry* treeSuccessor(entry* ) const;
 146
 147         // method that returns the entry pointer for the element that is searched
 148         //for. If the entry is not found then it retuns NULL
 149         DO_INLINE_P entry* find(const T&) const;
 150
 151         // infix traverse of the RB tree. It traverses the tree in ascending order
 152         DO_INLINE_P void traverse(T*,entry*,int&) const;
 153
 154         // deletes the tree structure for deconstructor.
 155         DO_INLINE_P void destroy(entry*);
 156
 157 public:
 158
 159         /** constructor. The default comparison structure is used */
 160         DO_INLINE_F BPatch_Set() : setSize(0)
 161         {
 162                 nil = new entry;
 163                 setData = nil;
 164                 compareFunc = Compare();
 165         }
 166
 167         /** copy constructor.
 168           * @param newBPatch_Set the BPatch_Set which will be copied
 169           */
 170         DO_INLINE_F BPatch_Set(const BPatch_Set<T,Compare>& newBPatch_Set){
 171                 nil = new entry;
 172                 compareFunc = newBPatch_Set.compareFunc;
 173                 setSize = newBPatch_Set.setSize;
 174                 setData = replicateTree(newBPatch_Set.setData,NULL,newBPatch_Set.nil,nil);
 175         }
 176
 177         /** destructor which deletes all tree structure and allocated entries */
 178         DO_INLINE_F ~BPatch_Set()
 179         {
 180                 destroy(setData);
 181                 delete nil;
 182         }
 183
 184         /** returns the cardinality of the tree , number of elements */
 185         DO_INLINE_F int size() const { return setSize; }
 186
 187         /** returns true if tree is empty */
 188         DO_INLINE_F bool empty() const { return (setData == nil); }
 189
 190         /** inserts the element in the tree
 191           * @param 1 element that will be inserted
 192           */
 193         DO_INLINE_F void insert(const T&);
 194
 195         /** removes the element in the tree
 196           * @param 1 element that will be removed
 197           */
 198         DO_INLINE_F void remove(const T&);
 199
 200         /** returns true if the argument is member of the BPatch_Set
 201           * @param e the element that will be searched for
 202           */
 203         DO_INLINE_F bool contains(const T&) const;
 204
 205         /** fill an buffer array with the sorted
 206           * elements of the BPatch_Set in ascending order according to comparison function
 207           * if the BPatch_Set is empty it retuns NULL, other wise it returns
 208           * the input argument.
 209           */
 210         DO_INLINE_F T* elements(T*) const;
 211
 212         /** returns the minimum valued member in the BPatch_Set according to the
 213           * comparison function supplied. If the BPatch_Set is empty it retuns
 214           * any number. Not safe to use for empty sets
 215           */
 216         DO_INLINE_F T minimum() const;
 217
 218         /** returns the maximum valued member in the BPatch_Set according to the
 219           * comparison function supplied. If the BPatch_Set is empty it retuns
 220           * any number. Not safe to use for empty sets
 221           */
 222         DO_INLINE_F T maximum() const;
 223
 224         /** assignment operator for BPatch_Set. It replicate sthe tree
 225           * structure into the new BPatch_Set.
 226           * @param 1 BPatch_Set that will be used in assignment
 227           */
 228         DO_INLINE_F BPatch_Set<T,Compare>& operator= (const BPatch_Set<T,Compare>&);
 229
 230         /** equality comparison for the BPatch_Set
 231           * @param 1 BPatch_Set that will be used equality check
 232           */
 233         DO_INLINE_F bool operator== (const BPatch_Set<T,Compare>&) const;
 234
 235         /** inequality comparison for the BPatch_Set
 236           * @param 1 BPatch_Set that will be used inequality check
 237           */
 238         DO_INLINE_F bool operator!= (const BPatch_Set<T,Compare>&) const;
 239
 240         /** insertion in to the BPatch_Set
 241           * @param 1 element that will be inserted
 242           */
 243         DO_INLINE_F BPatch_Set<T,Compare>& operator+= (const T&);
 244
 245         /** union operation with this BPatch_Set
 246           * @param 1 BPatch_Set that will be used in union operation
 247           */
 248         DO_INLINE_F BPatch_Set<T,Compare>& operator|= (const BPatch_Set<T,Compare>&);
 249
 250         /** intersection operation with this BPatch_Set
 251           * @param 1 BPatch_Set that will be used in intersection operation
 252           */
 253         DO_INLINE_F BPatch_Set<T,Compare>& operator&= (const BPatch_Set<T,Compare>&);
 254
 255         /** difference operation with this BPatch_Set
 256           * @param 1 BPatch_Set that will be used in difference operation
 257           */
 258         DO_INLINE_F BPatch_Set<T,Compare>& operator-= (const BPatch_Set<T,Compare>&);
 259
 260         /** union operation
 261           * @param 1 BPatch_Set that will be used in union operation
 262           */
 263         DO_INLINE_F BPatch_Set<T,Compare> operator| (const BPatch_Set<T,Compare>&) const;
 264
 265         /** intersection operation
 266           * @param 1 BPatch_Set that will be used in intersection operation
 267           */
 268         DO_INLINE_F BPatch_Set<T,Compare> operator& (const BPatch_Set<T,Compare>&) const;
 269
 270         /** difference operation
 271           * @param 1 BPatch_Set that will be used in difference operation
 272           */
 273         DO_INLINE_F BPatch_Set<T,Compare> operator- (const BPatch_Set<T,Compare>&) const;
 274
 275         /** removes the element in the root of the tree
 276           * if the BPatch_Set is empty it return false
 277           * @param e refernce to the element that the value of removed
 278           * element will be copied.
 279           */
 280         DO_INLINE_F bool extract(T&);
 281
 282 };
 283
 284 // VG(06/15/02): VC.NET doesn't like definitions for dll imports
 285 #ifndef BPATCH_DLL_IMPORT
 286
 287 template <class T,class Compare>
 288 DO_INLINE_P
 289 TYPENAME BPatch_Set<T,Compare>::entry*
 290 BPatch_Set<T,Compare>::replicateTree(entry* node,entry* parent,
 291                                      entry* oldNil,entry* newNil)
 292 {
 293         if(node == oldNil)
 294                 return newNil;
 295
 296         entry* newNode = new entry(*node);
 297         newNode->parent = parent;
 298         newNode->left = replicateTree(node->left,newNode,oldNil,newNil);
 299         newNode->right = replicateTree(node->right,newNode,oldNil,newNil);
 300         return newNode;
 301 }
 302
 303 template <class T,class Compare>
 304 DO_INLINE_P
 305 void BPatch_Set<T,Compare>::destroy(entry* node){
 306         if(!node || (node == nil))
 307                 return;
 308         if(node->left != nil)
 309                 destroy(node->left);
 310         if(node->right != nil)
 311                 destroy(node->right);
 312         delete node;
 313 }
 314
 315 template <class T,class Compare>
 316 DO_INLINE_P
 317 void BPatch_Set<T,Compare>::traverse(T* all,entry* node,int& n) const{
 318         if(node == nil)
 319                 return;
 320         if(node->left != nil)
 321                 traverse(all,node->left,n);
 322         if(all)
 323                 all[n++] = node->data;
 324         if(node->right != nil)
 325                 traverse(all,node->right,n);
 326 }
 327 template <class T,class Compare>
 328 DO_INLINE_F T BPatch_Set<T,Compare>::minimum() const{
 329         if(setData == nil)
 330                 return nil->data;
 331         entry* node = setData;
 332         while(node->left != nil)
 333                 node = node->left;
 334         return node->data;
 335 }
 336
 337 template <class T,class Compare>
 338 DO_INLINE_F T BPatch_Set<T,Compare>::maximum() const{
 339         if(setData == nil)
 340                 return nil->data;
 341         entry* node = setData;
 342         while(node->right != nil)
 343                 node = node->right;
 344         return node->data;
 345 }
 346 template <class T,class Compare>
 347 DO_INLINE_F T* BPatch_Set<T,Compare>::elements(T* buffer) const{
 348         if(setData == nil) return NULL;
 349         if(!buffer) return NULL;
 350         int tmp = 0;
 351         traverse(buffer,setData,tmp);
 352         return buffer;
 353 }
 354 template <class T,class Compare>
 355 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator= (const BPatch_Set<T,Compare>& newBPatch_Set){
 356         if(this == &newBPatch_Set)
 357                 return *this;
 358         destroy(setData);
 359         compareFunc = newBPatch_Set.compareFunc;
 360         setSize = newBPatch_Set.setSize;
 361         nil->parent = NULL;
 362         setData = replicateTree(newBPatch_Set.setData,NULL,newBPatch_Set.nil,nil);
 363         return *this;
 364 }
 365 template <class T,class Compare>
 366 DO_INLINE_F bool BPatch_Set<T,Compare>::operator== (const BPatch_Set<T,Compare>& newBPatch_Set) const{
 367         int i;
 368         if(this == &newBPatch_Set)
 369                 return true;
 370         T* all = new T[newBPatch_Set.size()];
 371         newBPatch_Set.elements(all);
 372         for(i=0;i<newBPatch_Set.size();i++)
 373                 if(!contains(all[i]))
 374                         return false;
 375         delete[] all;
 376         all = new T[setSize];
 377         elements(all);
 378         for(i=0;i<setSize;i++)
 379                 if(!newBPatch_Set.contains(all[i]))
 380                         return false;
 381         delete[] all;
 382         return true;
 383 }
 384 template <class T,class Compare>
 385 DO_INLINE_F bool BPatch_Set<T,Compare>::operator!= (const BPatch_Set<T,Compare>& newBPatch_Set) const{
 386         return !(*this == newBPatch_Set);
 387 }
 388 template <class T,class Compare>
 389 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator+= (const T& element){
 390         insert(element);
 391         return *this;
 392 }
 393 template <class T,class Compare>
 394 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator|= (const BPatch_Set<T,Compare>& newBPatch_Set){
 395         if(this == &newBPatch_Set)
 396                 return *this;
 397         T* all = new T[newBPatch_Set.size()];
 398         newBPatch_Set.elements(all);
 399         for(int i=0;i<newBPatch_Set.size();i++)
 400                 insert(all[i]);
 401         delete[] all;
 402         return *this;
 403 }
 404 template <class T,class Compare>
 405 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator&= (const BPatch_Set<T,Compare>& newBPatch_Set){
 406         if(this == &newBPatch_Set)
 407                 return *this;
 408         T* all = new T[setSize];
 409         elements(all);
 410         int s = setSize;
 411         for(int i=0;i<s;i++)
 412                 if(!newBPatch_Set.contains(all[i]))
 413                         remove(all[i]);
 414         delete[] all;
 415         return *this;
 416 }
 417 template <class T,class Compare>
 418 DO_INLINE_F BPatch_Set<T,Compare>& BPatch_Set<T,Compare>::operator-= (const BPatch_Set<T,Compare>& newBPatch_Set){
 419         T* all = new T[setSize];
 420         elements(all);
 421         int s = setSize;
 422         for(int i=0;i<s;i++)
 423                 if(newBPatch_Set.contains(all[i]))
 424                         remove(all[i]);
 425         delete[] all;
 426         return *this;
 427 }
 428 template <class T,class Compare>
 429 DO_INLINE_F BPatch_Set<T,Compare> BPatch_Set<T,Compare>::operator| (const BPatch_Set<T,Compare>& newBPatch_Set) const{
 430         BPatch_Set<T,Compare> ret;
 431         ret |= newBPatch_Set;
 432         ret |= *this;
 433         return ret;
 434 }
 435 template <class T,class Compare>
 436 DO_INLINE_F BPatch_Set<T,Compare> BPatch_Set<T,Compare>::operator& (const BPatch_Set<T,Compare>& newBPatch_Set) const{
 437         BPatch_Set<T,Compare> ret;
 438         ret |= newBPatch_Set;
 439         ret &= *this;
 440         return ret;
 441 }
 442 template <class T,class Compare>
 443 DO_INLINE_F BPatch_Set<T,Compare> BPatch_Set<T,Compare>::operator- (const BPatch_Set<T,Compare>& newBPatch_Set) const{
 444         BPatch_Set<T,Compare> ret;
 445         ret |= *this;
 446         ret -= newBPatch_Set;
 447         return ret;
 448 }
 449
 450 template <class T,class Compare>
 451 DO_INLINE_P
 452 void BPatch_Set<T,Compare>::leftRotate(entry* pivot){
 453         if(!pivot || (pivot == nil))
 454                 return;
 455         entry* y = pivot->right;
 456         if(y == nil)
 457                 return;
 458         pivot->right = y->left;
 459         if(y->left != nil)
 460                 y->left->parent = pivot;
 461         y->parent = pivot->parent;
 462         if(!pivot->parent)
 463                 setData = y;
 464         else if(pivot == pivot->parent->left)
 465                 pivot->parent->left = y;
 466         else
 467                 pivot->parent->right = y;
 468         y->left = pivot;
 469         pivot->parent = y;
 470 }
 471 template <class T,class Compare>
 472 DO_INLINE_P
 473 void BPatch_Set<T,Compare>::rightRotate(entry* pivot){
 474         if(!pivot || (pivot == nil))
 475                 return;
 476         entry* x = pivot->left;
 477         if(x == nil)
 478                 return;
 479         pivot->left = x->right;
 480         if(x->right != nil)
 481                 x->right->parent = pivot;
 482         x->parent = pivot->parent;
 483         if(!pivot->parent)
 484                 setData = x;
 485         else if(pivot == pivot->parent->left)
 486                 pivot->parent->left = x;
 487         else
 488                 pivot->parent->right = x;
 489         x->right = pivot;
 490         pivot->parent = x;
 491 }
 492
 493 template <class T,class Compare>
 494 DO_INLINE_P
 495 TYPENAME BPatch_Set<T,Compare>::entry*
 496 BPatch_Set<T,Compare>::find(const T& element) const{
 497         entry* x = setData;
 498         while(x != nil){
 499                 int check = compareFunc(element,x->data);
 500                 if(check < 0)
 501                         x = x->left;
 502                 else if(check > 0)
 503                         x = x->right;
 504                 else
 505                         return x;
 506         }
 507         return NULL;
 508 }
 509 template <class T,class Compare>
 510 DO_INLINE_F bool BPatch_Set<T,Compare>::contains(const T& element) const{
 511         entry* x = setData;
 512         while(x != nil){
 513                 int check = compareFunc(element,x->data);
 514                 if(check < 0)
 515                         x = x->left;
 516                 else if(check > 0)
 517                         x = x->right;
 518                 else
 519                         return true;
 520         }
 521         return false;
 522 }
 523 /** return pointer if the node is inserted, returns NULL if thevalue is
 524   * already there
 525   */
 526 template <class T,class Compare>
 527 DO_INLINE_P
 528 TYPENAME BPatch_Set<T,Compare>::entry*
 529 BPatch_Set<T,Compare>::treeInsert(const T& element){
 530         entry* y = NULL;
 531         entry* x = setData;
 532         while(x != nil){
 533                 y = x;
 534                 int check = compareFunc(element,x->data);
 535                 if(check < 0)
 536                         x = x->left;
 537                 else if(check > 0)
 538                         x = x->right;
 539                 else
 540                         return NULL;
 541         }
 542         entry* z = new entry(element,nil);
 543         z->parent = y;
 544         if(!y)
 545                 setData = z;
 546         else {
 547                 int check = compareFunc(element,y->data);
 548                 if(check < 0)
 549                         y->left = z;
 550                 else if(check > 0)
 551                         y->right = z;
 552         }
 553         setSize++;
 554         return z;
 555 }
 556 /** finds the minimum value node when x is being deleted */
 557 template <class T,class Compare>
 558 DO_INLINE_P
 559 TYPENAME BPatch_Set<T,Compare>::entry*
 560 BPatch_Set<T,Compare>::treeSuccessor(entry* x) const{
 561         if(!x || (x == nil))
 562                 return NULL;
 563         if(x->right != nil){
 564                 entry* z = x->right;
 565                 while(z->left != nil) z = z->left;
 566                 return z;
 567         }
 568         entry* y = x->parent;
 569         while(y && (x == y->right)){
 570                 x = y;
 571                 y = y->parent;
 572         }
 573         return y;
 574 }
 575 template <class T,class Compare>
 576 DO_INLINE_P
 577 void BPatch_Set<T,Compare>::deleteFixup(entry* x){
 578         while((x != setData) &&
 579               (x->color == BLACK))
 580         {
 581                 if(x == x->parent->left){
 582                         entry* w = x->parent->right;
 583                         if(w->color == RED){
 584                                 w->color = BLACK;
 585                                 x->parent->color = RED;
 586                                 leftRotate(x->parent);
 587                                 w = x->parent->right;
 588                         }
 589                         if((w->left->color == BLACK) &&
 590                            (w->right->color == BLACK)){
 591                                 w->color = RED;
 592                                 x = x->parent;
 593                         }
 594                         else{
 595                                 if(w->right->color == BLACK){
 596                                         w->left->color = BLACK;
 597                                         w->color = RED;
 598                                         rightRotate(w);
 599                                         w = x->parent->right;
 600                                 }
 601                                 w->color = x->parent->color;
 602                                 x->parent->color = BLACK;
 603                                 w->right->color = BLACK;
 604                                 leftRotate(x->parent);
 605                                 x = setData;
 606                         }
 607                 }
 608                 else{
 609                         entry* w = x->parent->left;
 610                         if(w->color == RED){
 611                                 w->color = BLACK;
 612                                 x->parent->color = RED;
 613                                 rightRotate(x->parent);
 614                                 w = x->parent->left;
 615                         }
 616                         if((w->right->color == BLACK) &&
 617                            (w->left->color == BLACK)){
 618                                 w->color = RED;
 619                                 x = x->parent;
 620                         }
 621                         else{
 622                                 if(w->left->color == BLACK){
 623                                         w->right->color = BLACK;
 624                                         w->color = RED;
 625                                         leftRotate(w);
 626                                         w = x->parent->left;
 627                                 }
 628                                 w->color = x->parent->color;
 629                                 x->parent->color = BLACK;
 630                                 w->left->color = BLACK;
 631                                 rightRotate(x->parent);
 632                                 x = setData;
 633                         }
 634                 }
 635         }
 636         x->color = BLACK;
 637 }
 638
 639 template <class T,class Compare>
 640 DO_INLINE_F void BPatch_Set<T,Compare>::insert(const T& element){
 641         entry* x = treeInsert(element);
 642         if(!x) return;
 643         x->color = RED;
 644         while((x != setData) && (x->parent->color == RED)){
 645                 if(x->parent == x->parent->parent->left){
 646                         entry* y = x->parent->parent->right;
 647                         if(y->color == RED){
 648                                 x->parent->color = BLACK;
 649                                 y->color = BLACK;
 650                                 x->parent->parent->color = RED;
 651                                 x = x->parent->parent;
 652                         }
 653                         else{
 654                                 if(x == x->parent->right){
 655                                         x = x->parent;
 656                                         leftRotate(x);
 657                                 }
 658                                 x->parent->color = BLACK;
 659                                 x->parent->parent->color = RED;
 660                                 rightRotate(x->parent->parent);
 661                         }
 662                 }
 663                 else{
 664                         entry* y = x->parent->parent->left;
 665                         if(y->color == RED){
 666                                 x->parent->color = BLACK;
 667                                 y->color = BLACK;
 668                                 x->parent->parent->color = RED;
 669                                 x = x->parent->parent;
 670                         }
 671                         else{
 672                                 if(x == x->parent->left){
 673                                         x = x->parent;
 674                                         rightRotate(x);
 675                                 }
 676                                 x->parent->color = BLACK;
 677                                 x->parent->parent->color = RED;
 678                                 leftRotate(x->parent->parent);
 679                         }
 680                 }
 681         }
 682         setData->color = BLACK;
 683 }
 684 template <class T,class Compare>
 685 DO_INLINE_F void BPatch_Set<T,Compare>::remove(const T& element){
 686         entry* z = find(element);
 687         if(!z)
 688                 return;
 689         entry* y=((z->left == nil)||(z->right == nil)) ? z : treeSuccessor(z);
 690         entry* x=(y->left != nil) ? y->left : y->right;
 691         x->parent = y->parent;
 692         if(!y->parent)
 693                 setData = x;
 694         else if(y == y->parent->left)
 695                 y->parent->left = x;
 696         else
 697                 y->parent->right = x;
 698         if(y != z)
 699                 z->data = y->data;
 700         if(y->color == BLACK)
 701                 deleteFixup(x);
 702         setSize--;
 703         delete y;
 704 }
 705 template <class T,class Compare>
 706 DO_INLINE_F
 707 bool BPatch_Set<T,Compare>::extract(T& element){
 708         element = setData->data;
 709         if(setData == nil)
 710                 return false;
 711         remove(element);
 712         return true;
 713 }
 714
 715 #endif /* BPATCH_DLL_IMPORT */
 716 #endif /* _BPatch_Set_h_ */
 717