| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/TeRedBlackTree.h
Go to the documentation of this file.

    00001 /************************************************************************************
    00002 TerraLib - a library for developing GIS applications.
    00003 Copyright © 2001-2007 INPE and Tecgraf/PUC-Rio.
    00004
    00005 This code is part of the TerraLib library.
    00006 This library is free software; you can redistribute it and/or
    00007 modify it under the terms of the GNU Lesser General Public
    00008 License as published by the Free Software Foundation; either
    00009 version 2.1 of the License, or (at your option) any later version.
    00010
    00011 You should have received a copy of the GNU Lesser General Public
    00012 License along with this library.
    00013
    00014 The authors reassure the license terms regarding the warranties.
    00015 They specifically disclaim any warranties, including, but not limited to,
    00016 the implied warranties of merchantability and fitness for a particular purpose.
    00017 The library provided hereunder is on an "as is" basis, and the authors have no
    00018 obligation to provide maintenance, support, updates, enhancements, or modifications.
    00019 In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
    00020 indirect, special, incidental, or consequential damages arising out of the use
    00021 of this library and its documentation.
    00022 *************************************************************************************/
    00028 #ifndef  __TERRALIB_INTERNAL_RED_BLACK_TREE_H
    00029 #define  __TERRALIB_INTERNAL_RED_BLACK_TREE_H
    00030
    00031 //STL's include
    00032 #include <string>
    00033
    00034 //TerraLib's include
    00035 #include "TeUtils.h"
    00036
    00037 using namespace std;
    00038
    00039 #define PRINT
    00040
    00043 namespace TeREDBLACK
    00044 {
    00045
    00047            enum TeRBNodeColor { TeREDNODE, TeBLACKNODE };
    00048
    00050
    00058            template<class T>
    00059            class TeRedBlackNode
    00060            {
    00061                       public:
    00062
    00064                                  typedef T TeRedBlackNodeData;
    00065
    00067                                  T data_;
    00068
    00070                                  TeRedBlackNode* left_;
    00071
    00073                                  TeRedBlackNode* right_;
    00074
    00076                                  TeRedBlackNode* parent_;
    00077
    00079                                  TeRBNodeColor color_;
    00080
    00082                                  TeRedBlackNode(const TeRBNodeColor& color = TeREDNODE)
    00083                                             : left_(0), right_(0), parent_(0), color_(color)
    00084                                  {
    00085                                  }
    00086
    00088                                  TeRedBlackNode(T& d, const TeRBNodeColor& color = TeREDNODE)
    00089                                             : data_(d), left_(0), right_(0), parent_(0), color_(color)
    00090                                  {
    00091                                  }
    00092
    00093
    00094                       private:
    00095
    00097                                  TeRedBlackNode(const TeRedBlackNode& other);
    00098
    00099                                  // No copy allowed
    00100                                  TeRedBlackNode& operator=(const TeRedBlackNode& other);
    00101            };
    00102
    00104
    00115            template<class NODE>
    00116            class TeRBTree
    00117            {
    00118                       private:
    00119
    00121                                  TeRBTree(const TeRBTree& other);
    00122
    00124                                  TeRBTree& operator=(const TeRBTree& other);
    00125
    00126                       protected:
    00127
    00128                                  NODE* nil_;
    00129                                  NODE* root_;
    00130                                  unsigned int nodeCount_;
    00131
    00132                       public:
    00133
    00135                                  typedef NODE* REDBLACKNODEPOINTER;
    00136
    00138                                  typedef typename NODE::TeRedBlackNodeData TeRedBlackNodeData;
    00139
    00141                                  TeRBTree()
    00142                                             : nodeCount_(0)
    00143                                  {
    00144                                             nil_ = new NODE();
    00145                                             nil_->color_ = TeBLACKNODE;
    00146
    00147                                             root_ = nil_;
    00148
    00149                                  }
    00150
    00152                                  virtual ~TeRBTree()
    00153                                  {
    00154                                             Clear();
    00155
    00156                                             if(nil_)
    00157                                                        delete nil_;
    00158                                  }
    00159
    00161                                  bool IsEmpty(void) const
    00162                                  {
    00163                                             return root_ == nil_;
    00164                                  }
    00165
    00167                                  unsigned int Size(void) const
    00168                                  {
    00169                                             return nodeCount_;
    00170                                  }
    00171
    00173                                  virtual void Delete(NODE* z)
    00174                                  {
    00175                                             if(z)
    00176                                             {
    00177                                                        // z has at most one non-null child. y == z.
    00178                                                        // x might be null.
    00179                                                        // z has exactly one non-null child.  y == z.
    00180                                                        // x is not null.
    00181                                                        // z has two non-null children.  Set y to
    00182                                                        //   z's successor.  x might be null.
    00183                                                        NODE* y = ((z->left_ == nil_) || (z->right_ == nil_)) ? z : Successor(z);
    00184                                                        NODE* x = (y->left_  != nil_) ?  y->left_ : y->right_;
    00185                                                        NODE* x_parent = 0;
    00186
    00187                                                        if(y != z) // relink y in place of z.  y is z's successor
    00188                                                        {
    00189                                                                   z->left_->parent_ = y;
    00190                                                                   y->left_ = z->left_;
    00191                                                                   if(y != z->right_)
    00192                                                                   {
    00193                                                                              x_parent = y->parent_;
    00194
    00195                                                                              if(x != nil_)
    00196                                                                                         x->parent_ = y->parent_;
    00197
    00198                                                                              y->parent_->left_ = x;      // y must be a left child
    00199                                                                              y->right_ = z->right_;
    00200                                                                              z->right_->parent_ = y;
    00201                                                                   }
    00202                                                                   else
    00203                                                                              x_parent = y;
    00204
    00205                                                                   if(root_ == z)
    00206                                                                              root_ = y;
    00207                                                                   else
    00208                                                                              if(z->parent_->left_ == z)
    00209                                                                                         z->parent_->left_ = y;
    00210                                                                              else
    00211                                                                                         z->parent_->right_ = y;
    00212
    00213                                                                   y->parent_ = z->parent_;
    00214
    00215                                                                   TeRBNodeColor aux_color = y->color_;
    00216                                                                   y->color_ = z->color_;
    00217                                                                   z->color_ = aux_color;
    00218
    00219                                                                   y = z;
    00220
    00221                                                                   // y now points to node to be actually deleted
    00222                                                        }
    00223                                                        else
    00224                                                        {                        // y == z
    00225                                                                   x_parent = y->parent_;
    00226                                                                   if(x != nil_)
    00227                                                                              x->parent_ = y->parent_;
    00228
    00229                                                                   if(root_ == z)
    00230                                                                              root_ = x;
    00231                                                                   else
    00232                                                                              if(z->parent_->left_ == z)
    00233                                                                                         z->parent_->left_ = x;
    00234                                                                              else
    00235                                                                                         z->parent_->right_ = x;
    00236                                                        }
    00237
    00238                                                        if(y->color_ == TeBLACKNODE)
    00239                                                                   DeleteFixUp(x, x_parent, root_);
    00240
    00241                                                        delete y;
    00242
    00243                                                        nodeCount_--;
    00244                                             }
    00245
    00246                                             return;
    00247                                  }
    00248
    00250                                  virtual NODE* Successor(NODE* x) const
    00251                                  {
    00252                                             if(x)
    00253                                             {
    00254                                                        if(x->right_ != nil_)
    00255                                                        {
    00256                                                                   x = x->right_;
    00257
    00258                                                                   while(x->left_ != nil_)
    00259                                                                              x = x->left_;
    00260
    00261                                                                   return x;
    00262                                                        }
    00263
    00264                                                        NODE* y = x->parent_;
    00265
    00266                                                        while((y != nil_) && (x == y->right_))
    00267                                                        {
    00268                                                                   x = y;
    00269                                                                   y = y->parent_;
    00270                                                        }
    00271
    00272                                                        if(y == nil_)
    00273                                                                   return 0;
    00274
    00275                                                        return y;
    00276                                             }
    00277
    00278                                             return 0;
    00279                                  }
    00280
    00282                                  virtual NODE* Predecessor(NODE* x) const
    00283                                  {
    00284                                             if(x)
    00285                                             {
    00286                                                        if(x->left_ != nil_)
    00287                                                        {
    00288                                                                   x = x->left_;
    00289
    00290                                                                   while(x->right_ != nil_)
    00291                                                                              x = x->right_;
    00292
    00293                                                                   return x;
    00294                                                        }
    00295
    00296                                                        NODE* y = x->parent_;
    00297
    00298                                                        while((y != nil_) && (x == y->left_))
    00299                                                        {
    00300                                                                   x = y;
    00301                                                                   y = y->parent_;
    00302                                                        }
    00303
    00304                                                        if(y == nil_)
    00305                                                                   return 0;
    00306
    00307                                                        return y;
    00308                                             }
    00309
    00310                                             return 0;
    00311                                  }
    00312
    00314                                  NODE* First(void) const
    00315                                  {
    00316                                             if(IsEmpty())
    00317                                                        return 0;
    00318
    00319                                             NODE *x = root_;
    00320
    00321                                             while(x->left_ != nil_)
    00322                                                        x = x->left_;
    00323
    00324                                             return x;
    00325                                  }
    00326
    00328                                  NODE* Last(void) const
    00329                                  {
    00330                                             if(IsEmpty())
    00331                                                        return 0;
    00332
    00333                                             NODE *x = root_;
    00334
    00335                                             while(x->right_ != nil_)
    00336                                                        x = x->right_;
    00337
    00338                                             return x;
    00339                                  }
    00340
    00342                                  virtual bool GetFirst(TeRedBlackNodeData& d)
    00343                                  {
    00344                                             NODE *x = First();
    00345
    00346                                             if(x)
    00347                                             {
    00348                                                                   d = x->data_;
    00349
    00350                                                                   Delete(x);
    00351
    00352                                                                   return true;
    00353                                             }
    00354
    00355                                             return false;
    00356                                  }
    00357
    00359                                  void Clear(void)
    00360                                  {
    00361                                             if(!IsEmpty())
    00362                                             {
    00363                                                        Erase(root_);
    00364
    00365                                                        root_ = nil_;
    00366                                             }
    00367
    00368                                             return;
    00369                                  }
    00370
    00372                                  virtual void WriteToFile(const string& fileName) const
    00373                                  {
    00374                                             string strRepres = "";
    00375
    00376                                             WriteToFile(root_, strRepres);
    00377
    00378                                             TeWriteToFile(fileName, strRepres, "w");
    00379
    00380                                             return;
    00381                                  }
    00382
    00383                       protected:
    00384
    00386                                  virtual void LeftRotate(NODE* x, NODE*& root)
    00387                                  {
    00388                                             NODE* y = x->right_;
    00389
    00390                                             x->right_ = y->left_;
    00391
    00392                                             if(y->left_ != nil_)
    00393                                                        y->left_->parent_ = x;
    00394
    00395                                             y->parent_ = x->parent_;
    00396
    00397
    00398                                             if(x == root)
    00399                                                        root = y;
    00400                                             else
    00401                                             {
    00402                                                        if(x == x->parent_->left_)
    00403                                                                   x->parent_->left_ = y;
    00404                                                        else
    00405                                                                   x->parent_->right_ = y;
    00406                                             }
    00407
    00408                                             y->left_ = x;
    00409                                             x->parent_ = y;
    00410
    00411                                             return;
    00412                                  }
    00413
    00415                                  virtual void RightRotate(NODE* y, NODE*& root)
    00416                                  {
    00417                                             NODE* x = y->left_;
    00418
    00419                                             y->left_ = x->right_;
    00420
    00421                                             if(x->right_ != nil_)
    00422                                                        x->right_->parent_ = y;
    00423
    00424                                             x->parent_ = y->parent_;
    00425
    00426                                             if(y == root)
    00427                                                        root = x;
    00428                                             else
    00429                                             {
    00430                                                        if(y == y->parent_->right_)
    00431                                                                   y->parent_->right_ = x;
    00432                                                        else
    00433                                                                   y->parent_->left_ = x;
    00434                                             }
    00435
    00436                                             x->right_ = y;
    00437                                             y->parent_ = x;
    00438
    00439                                             return;
    00440                                  }
    00441
    00443                                  void InsertFixUp(NODE*& n, NODE*& root)
    00444                                  {
    00445                                             n->color_ = TeREDNODE;
    00446
    00447                                             NODE* y;
    00448
    00449                                             while ((n != root) && (n->parent_->color_ == TeREDNODE))
    00450                                             {
    00451                                                        if(n->parent_ == n->parent_->parent_->left_)
    00452                                                        {
    00453                                                                   y = n->parent_->parent_->right_;
    00454                                                                   if(y->color_ == TeREDNODE)
    00455                                                                   {
    00456                                                                              n->parent_->color_ = TeBLACKNODE;
    00457                                                                              y->color_ = TeBLACKNODE;
    00458                                                                              n = n->parent_->parent_;
    00459                                                                              n->color_ = TeREDNODE;
    00460                                                                   }
    00461                                                                   else
    00462                                                                   {
    00463                                                                              if(n == n->parent_->right_)
    00464                                                                              {
    00465                                                                                         n = n->parent_;
    00466                                                                                         LeftRotate(n, root);
    00467                                                                              }
    00468
    00469                                                                              n->parent_->color_ = TeBLACKNODE;
    00470                                                                              n->parent_->parent_->color_ = TeREDNODE;
    00471                                                                              RightRotate(n->parent_->parent_, root);
    00472                                                                   }
    00473                                                        }
    00474                                                        else
    00475                                                        {
    00476                                                                   y = n->parent_->parent_->left_;
    00477                                                                   if(y->color_ == TeREDNODE)
    00478                                                                   {
    00479                                                                              n->parent_->color_ = TeBLACKNODE;
    00480                                                                              y->color_ = TeBLACKNODE;
    00481                                                                              n = n->parent_->parent_;
    00482                                                                              n->color_ = TeREDNODE;
    00483                                                                   }
    00484                                                                   else
    00485                                                                   {
    00486                                                                              if(n == n->parent_->left_)
    00487                                                                              {
    00488                                                                                         n = n->parent_;
    00489                                                                                         RightRotate(n, root);
    00490                                                  }
    00491
    00492                                                                              n->parent_->color_ = TeBLACKNODE;
    00493                                                                              n->parent_->parent_->color_ = TeREDNODE;
    00494                                                                              LeftRotate(n->parent_->parent_, root);
    00495                                                                   }
    00496                                                        }
    00497                                             }
    00498
    00499                                             root->color_ = TeBLACKNODE;
    00500
    00501                                             return;
    00502                                  }
    00503
    00505                                  void DeleteFixUp(NODE* x, NODE* x_parent, NODE*& root)
    00506                                  {
    00507                                             while((x != root) && (x == nil_ || x->color_ == TeBLACKNODE))
    00508                                             {
    00509                                                        if(x == x_parent->left_)
    00510                                                        {
    00511                                                                   NODE *w = x_parent->right_;
    00512
    00513                                                                   if(w->color_ == TeREDNODE)
    00514                                                     {
    00515                                                                              w->color_ = TeBLACKNODE;
    00516                                                                              x_parent->color_ = TeREDNODE;
    00517                                                                              LeftRotate(x_parent, root);
    00518                                                                              w = x_parent->right_;
    00519                                                     }
    00520
    00521                                                                   if((w->left_ == nil_ || w->left_->color_ == TeBLACKNODE) && (w->right_ == nil_ || w->right_->color_ == TeBLACKNODE))
    00522                                                                   {
    00523                                                                              w->color_ = TeREDNODE;
    00524                                                                              x = x_parent;
    00525                                                                              x_parent = x_parent->parent_;
    00526                                                                   }
    00527                                                                   else
    00528                                                     {
    00529                                                                              if(w->right_ == nil_ || w->right_->color_ == TeBLACKNODE)
    00530                                                                {
    00531                                                                                         if(w->left_ != nil_)
    00532                                                                                                    w->left_->color_ = TeBLACKNODE;
    00533
    00534                                                                                         w->color_ = TeREDNODE;
    00535                                                                                         RightRotate(w, root);
    00536                                                                                         w = x_parent->right_;
    00537                                                                       }
    00538
    00539                                                                              w->color_ = x_parent->color_;
    00540                                                                              x_parent->color_ = TeBLACKNODE;
    00541
    00542                                                                              if(w->right_ != nil_)
    00543                                                                                         w->right_->color_ = TeBLACKNODE;
    00544
    00545                                                                              LeftRotate(x_parent, root);
    00546
    00547                                                                              break;
    00548                                                                   }
    00549                                                        }
    00550                                                        else
    00551                                                 {
    00552                                                                   NODE* w = x_parent->left_;
    00553
    00554                                                                   if(w->color_ == TeREDNODE)
    00555                                                     {
    00556                                                                              w->color_ = TeBLACKNODE;
    00557                                                                              x_parent->color_ = TeREDNODE;
    00558                                                                              RightRotate(x_parent, root);
    00559                                                                              w = x_parent->left_;
    00560                                                                   }
    00561
    00562                                                                   if((w->left_ == nil_ || w->left_->color_ == TeBLACKNODE) && (w->right_ == nil_ || w->right_->color_ == TeBLACKNODE))
    00563                                                                   {
    00564                                                                              w->color_ = TeREDNODE;
    00565                                                                              x = x_parent;
    00566                                                                              x_parent = x_parent->parent_;
    00567                                                                   }
    00568                                                                   else
    00569                                                                   {
    00570                                                                              if(w->left_ == nil_ || w->left_->color_ == TeBLACKNODE)
    00571                                                         {
    00572                                                                                         if(w->right_ != nil_)
    00573                                                                                                    w->right_->color_ = TeBLACKNODE;
    00574
    00575                                                                                         w->color_ = TeREDNODE;
    00576                                                                                         LeftRotate(w, root);
    00577                                                                                         w = x_parent->left_;
    00578                                                                              }
    00579
    00580                                                                              w->color_ = x_parent->color_;
    00581                                                                              x_parent->color_ = TeBLACKNODE;
    00582
    00583                                                                              if(w->left_ != nil_)
    00584                                                                                         w->left_->color_ = TeBLACKNODE;
    00585
    00586                                                                              RightRotate(x_parent, root);
    00587
    00588                                                                              break;
    00589                                                                   }
    00590                                                        }
    00591                                             }
    00592
    00593                                             if(x != nil_)
    00594                                                        x->color_ = TeBLACKNODE;
    00595                                  }
    00596
    00598                                  virtual void WriteToFile(NODE* n, string& strRepres) const
    00599                                  {
    00600                                             if(n != nil_)
    00601                                             {
    00602                                                        WriteToFile(n->left_, strRepres);
    00603
    00604                                                        strRepres += n->data_.ToString();
    00605                                                        strRepres += '\n';
    00606
    00607                                                        WriteToFile(n->right_, strRepres);
    00608                                             }
    00609
    00610                                             return;
    00611                                  }
    00612
    00614                                  void Erase(NODE* n)
    00615                                  {
    00616                                             if(n != nil_)
    00617                                             {
    00618                                                        Erase(n->left_);
    00619                                                        Erase(n->right_);
    00620
    00621                                                        delete n;
    00622
    00623                                                        nodeCount_--;
    00624                                             }
    00625
    00626                                             return;
    00627                                  }
    00628
    00629                       public:
    00630
    00632                                  template<class Node_i> class internal_iterator
    00633                                  {
    00634                                             protected:
    00635
    00637                                                        TeRBTree<Node_i>* tree_;
    00638
    00640                                                        Node_i* node_;
    00641
    00642                                             public:
    00643
    00645                                                        void invalid(void)
    00646                                                        {
    00647                                                                   node_ = 0;
    00648                                                                   return;
    00649                                                        }
    00650
    00652                                                        Node_i* getNode(void) const
    00653                                                        {
    00654                                                                   return node_;
    00655                                                        }
    00656
    00657                                             public:
    00658
    00660                                                        internal_iterator()
    00661                                                                   : node_(0), tree_(0)
    00662                                                        {
    00663                                                        }
    00664
    00666                                                        internal_iterator(TeRBTree<Node_i>* tree, Node_i* n)
    00667                                                                   : tree_(tree), node_(n)
    00668                                                        {
    00669                                                        }
    00670
    00672                                                        virtual ~internal_iterator()
    00673                                                        {
    00674                                                        }
    00675
    00677                                                        typename Node_i::TeRedBlackNodeData* operator->() const
    00678                                                        {
    00679                                                                   return &node_->data_;
    00680                                                        }
    00681
    00683                                                        typename Node_i::TeRedBlackNodeData& operator*() const
    00684                                                        {
    00685                                                                   return node_->data_;
    00686                                                        }
    00687
    00689                                                        internal_iterator& operator++()
    00690                                                        {
    00691                                                                   node_ = tree_->Successor(node_);
    00692
    00693
    00694                                                                   return *this;
    00695                                                        }
    00696
    00698                                                        internal_iterator operator++(int)
    00699                                                        {
    00700                                                                   internal_iterator temp = *this;
    00701                                                                   ++(*this);
    00702
    00703                                                                   return temp;
    00704                                                        }
    00705
    00707                                                        internal_iterator& operator--()
    00708                                                        {
    00709                                                                   node_ = tree_->Predecessor(node_);
    00710
    00711
    00712                                                                   return *this;
    00713                                                        }
    00714
    00716                                                        internal_iterator operator--(int)
    00717                                                        {
    00718                                                                   internal_iterator temp = *this;
    00719                                                                   --(*this);
    00720                                                                   return temp;
    00721                                                        }
    00722
    00724                                                        bool operator==(const internal_iterator& other) const
    00725                                                        {
    00726                                                                   return (this->node_ == other.node_);
    00727                                                        }
    00728
    00730                                                        bool operator!=(const internal_iterator& other) const
    00731                                                        {
    00732                                                                   return(this->node_ != other.node_);
    00733                                                        }
    00734                                  };
    00735
    00737                                  typedef internal_iterator<NODE> iterator;
    00738
    00740                                  iterator begin(void)
    00741                                  {
    00742                                             return iterator(this, First());
    00743                                  }
    00744
    00746                                  iterator end(void)
    00747                                  {
    00748                                             return iterator(this, 0);
    00749                                  }
    00750
    00752                                  void erase(iterator& it)
    00753                                  {
    00754                                             Delete(it.getNode());
    00755
    00756                                             it.invalid();
    00757
    00758                                             return;
    00759                                  }
    00760            };
    00761
    00762 }                     // end namespace TeREDBLACK
    00763 #endif     // __TERRALIB_INTERNAL_RED_BLACK_TREE_H

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines