include/irrMap.h

   1 // Copyright (C) 2006-2012 by Kat'Oun\r
   2 // This file is part of the "Irrlicht Engine".\r
   3 // For conditions of distribution and use, see copyright notice in irrlicht.h\r
   4 \r
   5 #ifndef __IRR_MAP_H_INCLUDED__\r
   6 #define __IRR_MAP_H_INCLUDED__\r
   7 \r
   8 #include "irrTypes.h"\r
   9 #include "irrMath.h"\r
  10 \r
  11 namespace irr\r
  12 {\r
  13 namespace core\r
  14 {\r
  15 \r
  16 //! map template for associative arrays using a red-black tree\r
  17 template <class KeyType, class ValueType>\r
  18 class map\r
  19 {\r
  20         //! red/black tree for map\r
  21         template <class KeyTypeRB, class ValueTypeRB>\r
  22         class RBTree\r
  23         {\r
  24         public:\r
  25 \r
  26                 RBTree(const KeyTypeRB& k, const ValueTypeRB& v)\r
  27                         : LeftChild(0), RightChild(0), Parent(0), Key(k),\r
  28                                 Value(v), IsRed(true) {}\r
  29 \r
  30                 void setLeftChild(RBTree* p)\r
  31                 {\r
  32                         LeftChild=p;\r
  33                         if (p)\r
  34                                 p->setParent(this);\r
  35                 }\r
  36 \r
  37                 void setRightChild(RBTree* p)\r
  38                 {\r
  39                         RightChild=p;\r
  40                         if (p)\r
  41                                 p->setParent(this);\r
  42                 }\r
  43 \r
  44                 void setParent(RBTree* p) { Parent=p; }\r
  45 \r
  46                 void setValue(const ValueTypeRB& v) { Value = v; }\r
  47 \r
  48                 void setRed() { IsRed = true; }\r
  49                 void setBlack() { IsRed = false; }\r
  50 \r
  51                 RBTree* getLeftChild() const { return LeftChild; }\r
  52                 RBTree* getRightChild() const { return RightChild; }\r
  53                 RBTree* getParent() const { return Parent; }\r
  54 \r
  55                 const ValueTypeRB& getValue() const\r
  56                 {\r
  57                         return Value;\r
  58                 }\r
  59 \r
  60                 ValueTypeRB& getValue()\r
  61                 {\r
  62                         return Value;\r
  63                 }\r
  64 \r
  65                 const KeyTypeRB& getKey() const\r
  66                 {\r
  67                         return Key;\r
  68                 }\r
  69 \r
  70                 bool isRoot() const\r
  71                 {\r
  72                         return Parent==0;\r
  73                 }\r
  74 \r
  75                 bool isLeftChild() const\r
  76                 {\r
  77                         return (Parent != 0) && (Parent->getLeftChild()==this);\r
  78                 }\r
  79 \r
  80                 bool isRightChild() const\r
  81                 {\r
  82                         return (Parent!=0) && (Parent->getRightChild()==this);\r
  83                 }\r
  84 \r
  85                 bool isLeaf() const\r
  86                 {\r
  87                         return (LeftChild==0) && (RightChild==0);\r
  88                 }\r
  89 \r
  90                 unsigned int getLevel() const\r
  91                 {\r
  92                         if (isRoot())\r
  93                                 return 1;\r
  94                         else\r
  95                                 return getParent()->getLevel() + 1;\r
  96                 }\r
  97 \r
  98 \r
  99                 bool isRed() const\r
 100                 {\r
 101                         return IsRed;\r
 102                 }\r
 103 \r
 104                 bool isBlack() const\r
 105                 {\r
 106                         return !IsRed;\r
 107                 }\r
 108 \r
 109         private:\r
 110                 RBTree();\r
 111 \r
 112                 RBTree* LeftChild;\r
 113                 RBTree* RightChild;\r
 114 \r
 115                 RBTree* Parent;\r
 116 \r
 117                 KeyTypeRB Key;\r
 118                 ValueTypeRB Value;\r
 119 \r
 120                 bool IsRed;\r
 121         }; // RBTree\r
 122 \r
 123         public:\r
 124 \r
 125         typedef RBTree<KeyType,ValueType> Node;\r
 126         // We need the forward declaration for the friend declaration\r
 127         class ConstIterator;\r
 128 \r
 129         //! Normal Iterator\r
 130         class Iterator\r
 131         {\r
 132                 friend class ConstIterator;\r
 133         public:\r
 134 \r
 135                 Iterator() : Root(0), Cur(0) {}\r
 136 \r
 137                 // Constructor(Node*)\r
 138                 Iterator(Node* root) : Root(root)\r
 139                 {\r
 140                         reset();\r
 141                 }\r
 142 \r
 143                 void reset(bool atLowest=true)\r
 144                 {\r
 145                         if (atLowest)\r
 146                                 Cur = getMin(Root);\r
 147                         else\r
 148                                 Cur = getMax(Root);\r
 149                 }\r
 150 \r
 151                 bool atEnd() const\r
 152                 {\r
 153                         return Cur==0;\r
 154                 }\r
 155 \r
 156                 Node* getNode() const\r
 157                 {\r
 158                         return Cur;\r
 159                 }\r
 160 \r
 161                 void operator++(int)\r
 162                 {\r
 163                         inc();\r
 164                 }\r
 165 \r
 166                 void operator--(int)\r
 167                 {\r
 168                         dec();\r
 169                 }\r
 170 \r
 171                 Node* operator->()\r
 172                 {\r
 173                         return getNode();\r
 174                 }\r
 175 \r
 176                 Node& operator*()\r
 177                 {\r
 178                         _IRR_DEBUG_BREAK_IF(atEnd()) // access violation\r
 179 \r
 180                         return *Cur;\r
 181                 }\r
 182 \r
 183         private:\r
 184 \r
 185                 Node* getMin(Node* n) const\r
 186                 {\r
 187                         while(n && n->getLeftChild())\r
 188                                 n = n->getLeftChild();\r
 189                         return n;\r
 190                 }\r
 191 \r
 192                 Node* getMax(Node* n) const\r
 193                 {\r
 194                         while(n && n->getRightChild())\r
 195                                 n = n->getRightChild();\r
 196                         return n;\r
 197                 }\r
 198 \r
 199                 void inc()\r
 200                 {\r
 201                         // Already at end?\r
 202                         if (Cur==0)\r
 203                                 return;\r
 204 \r
 205                         if (Cur->getRightChild())\r
 206                         {\r
 207                                 // If current node has a right child, the next higher node is the\r
 208                                 // node with lowest key beneath the right child.\r
 209                                 Cur = getMin(Cur->getRightChild());\r
 210                         }\r
 211                         else if (Cur->isLeftChild())\r
 212                         {\r
 213                                 // No right child? Well if current node is a left child then\r
 214                                 // the next higher node is the parent\r
 215                                 Cur = Cur->getParent();\r
 216                         }\r
 217                         else\r
 218                         {\r
 219                                 // Current node neither is left child nor has a right child.\r
 220                                 // I.e. it is either right child or root\r
 221                                 // The next higher node is the parent of the first non-right\r
 222                                 // child (i.e. either a left child or the root) up in the\r
 223                                 // hierarchy. Root's parent is 0.\r
 224                                 while(Cur->isRightChild())\r
 225                                         Cur = Cur->getParent();\r
 226                                 Cur = Cur->getParent();\r
 227                         }\r
 228                 }\r
 229 \r
 230                 void dec()\r
 231                 {\r
 232                         // Already at end?\r
 233                         if (Cur==0)\r
 234                                 return;\r
 235 \r
 236                         if (Cur->getLeftChild())\r
 237                         {\r
 238                                 // If current node has a left child, the next lower node is the\r
 239                                 // node with highest key beneath the left child.\r
 240                                 Cur = getMax(Cur->getLeftChild());\r
 241                         }\r
 242                         else if (Cur->isRightChild())\r
 243                         {\r
 244                                 // No left child? Well if current node is a right child then\r
 245                                 // the next lower node is the parent\r
 246                                 Cur = Cur->getParent();\r
 247                         }\r
 248                         else\r
 249                         {\r
 250                                 // Current node neither is right child nor has a left child.\r
 251                                 // It is either left child or root\r
 252                                 // The next higher node is the parent of the first non-left\r
 253                                 // child (i.e. either a right child or the root) up in the\r
 254                                 // hierarchy. Root's parent is 0.\r
 255 \r
 256                                 while(Cur->isLeftChild())\r
 257                                         Cur = Cur->getParent();\r
 258                                 Cur = Cur->getParent();\r
 259                         }\r
 260                 }\r
 261 \r
 262                 Node* Root;\r
 263                 Node* Cur;\r
 264         }; // Iterator\r
 265 \r
 266         //! Const Iterator\r
 267         class ConstIterator\r
 268         {\r
 269                 friend class Iterator;\r
 270         public:\r
 271 \r
 272                 ConstIterator() : Root(0), Cur(0) {}\r
 273 \r
 274                 // Constructor(Node*)\r
 275                 ConstIterator(const Node* root) : Root(root)\r
 276                 {\r
 277                         reset();\r
 278                 }\r
 279 \r
 280                 // Constructor(Iterator)\r
 281                 ConstIterator(const Iterator& src) : Root(src.Root), Cur(src.Cur) {}\r
 282 \r
 283                 void reset(bool atLowest=true)\r
 284                 {\r
 285                         if (atLowest)\r
 286                                 Cur = getMin(Root);\r
 287                         else\r
 288                                 Cur = getMax(Root);\r
 289                 }\r
 290 \r
 291                 bool atEnd() const\r
 292                 {\r
 293                         return Cur==0;\r
 294                 }\r
 295 \r
 296                 const Node* getNode() const\r
 297                 {\r
 298                         return Cur;\r
 299                 }\r
 300 \r
 301                 void operator++(int)\r
 302                 {\r
 303                         inc();\r
 304                 }\r
 305 \r
 306                 void operator--(int)\r
 307                 {\r
 308                         dec();\r
 309                 }\r
 310 \r
 311                 const Node* operator->()\r
 312                 {\r
 313                         return getNode();\r
 314                 }\r
 315 \r
 316                 const Node& operator*()\r
 317                 {\r
 318                         _IRR_DEBUG_BREAK_IF(atEnd()) // access violation\r
 319 \r
 320                         return *Cur;\r
 321                 }\r
 322 \r
 323         private:\r
 324 \r
 325                 const Node* getMin(const Node* n) const\r
 326                 {\r
 327                         while(n && n->getLeftChild())\r
 328                                 n = n->getLeftChild();\r
 329                         return n;\r
 330                 }\r
 331 \r
 332                 const Node* getMax(const Node* n) const\r
 333                 {\r
 334                         while(n && n->getRightChild())\r
 335                                 n = n->getRightChild();\r
 336                         return n;\r
 337                 }\r
 338 \r
 339                 void inc()\r
 340                 {\r
 341                         // Already at end?\r
 342                         if (Cur==0)\r
 343                                 return;\r
 344 \r
 345                         if (Cur->getRightChild())\r
 346                         {\r
 347                                 // If current node has a right child, the next higher node is the\r
 348                                 // node with lowest key beneath the right child.\r
 349                                 Cur = getMin(Cur->getRightChild());\r
 350                         }\r
 351                         else if (Cur->isLeftChild())\r
 352                         {\r
 353                                 // No right child? Well if current node is a left child then\r
 354                                 // the next higher node is the parent\r
 355                                 Cur = Cur->getParent();\r
 356                         }\r
 357                         else\r
 358                         {\r
 359                                 // Current node neither is left child nor has a right child.\r
 360                                 // It is either right child or root\r
 361                                 // The next higher node is the parent of the first non-right\r
 362                                 // child (i.e. either a left child or the root) up in the\r
 363                                 // hierarchy. Root's parent is 0.\r
 364                                 while(Cur->isRightChild())\r
 365                                         Cur = Cur->getParent();\r
 366                                 Cur = Cur->getParent();\r
 367                         }\r
 368                 }\r
 369 \r
 370                 void dec()\r
 371                 {\r
 372                         // Already at end?\r
 373                         if (Cur==0)\r
 374                                 return;\r
 375 \r
 376                         if (Cur->getLeftChild())\r
 377                         {\r
 378                                 // If current node has a left child, the next lower node is the\r
 379                                 // node with highest key beneath the left child.\r
 380                                 Cur = getMax(Cur->getLeftChild());\r
 381                         }\r
 382                         else if (Cur->isRightChild())\r
 383                         {\r
 384                                 // No left child? Well if current node is a right child then\r
 385                                 // the next lower node is the parent\r
 386                                 Cur = Cur->getParent();\r
 387                         }\r
 388                         else\r
 389                         {\r
 390                                 // Current node neither is right child nor has a left child.\r
 391                                 // It is either left child or root\r
 392                                 // The next higher node is the parent of the first non-left\r
 393                                 // child (i.e. either a right child or the root) up in the\r
 394                                 // hierarchy. Root's parent is 0.\r
 395 \r
 396                                 while(Cur->isLeftChild())\r
 397                                         Cur = Cur->getParent();\r
 398                                 Cur = Cur->getParent();\r
 399                         }\r
 400                 }\r
 401 \r
 402                 const Node* Root;\r
 403                 const Node* Cur;\r
 404         }; // ConstIterator\r
 405 \r
 406 \r
 407         //! Parent First Iterator.\r
 408         /** Traverses the tree from top to bottom. Typical usage is\r
 409         when storing the tree structure, because when reading it\r
 410         later (and inserting elements) the tree structure will\r
 411         be the same. */\r
 412         class ParentFirstIterator\r
 413         {\r
 414         public:\r
 415 \r
 416         ParentFirstIterator() : Root(0), Cur(0) {}\r
 417 \r
 418         explicit ParentFirstIterator(Node* root) : Root(root), Cur(0)\r
 419         {\r
 420                 reset();\r
 421         }\r
 422 \r
 423         void reset()\r
 424         {\r
 425                 Cur = Root;\r
 426         }\r
 427 \r
 428         bool atEnd() const\r
 429         {\r
 430                 return Cur==0;\r
 431         }\r
 432 \r
 433         Node* getNode()\r
 434         {\r
 435                 return Cur;\r
 436         }\r
 437 \r
 438         void operator++(int)\r
 439         {\r
 440                 inc();\r
 441         }\r
 442 \r
 443         Node* operator -> ()\r
 444         {\r
 445                 return getNode();\r
 446         }\r
 447 \r
 448         Node& operator* ()\r
 449         {\r
 450                 _IRR_DEBUG_BREAK_IF(atEnd()) // access violation\r
 451 \r
 452                 return *getNode();\r
 453         }\r
 454 \r
 455         private:\r
 456 \r
 457         void inc()\r
 458         {\r
 459                 // Already at end?\r
 460                 if (Cur==0)\r
 461                         return;\r
 462 \r
 463                 // First we try down to the left\r
 464                 if (Cur->getLeftChild())\r
 465                 {\r
 466                         Cur = Cur->getLeftChild();\r
 467                 }\r
 468                 else if (Cur->getRightChild())\r
 469                 {\r
 470                         // No left child? The we go down to the right.\r
 471                         Cur = Cur->getRightChild();\r
 472                 }\r
 473                 else\r
 474                 {\r
 475                         // No children? Move up in the hierarchy until\r
 476                         // we either reach 0 (and are finished) or\r
 477                         // find a right uncle.\r
 478                         while (Cur!=0)\r
 479                         {\r
 480                                 // But if parent is left child and has a right "uncle" the parent\r
 481                                 // has already been processed but the uncle hasn't. Move to\r
 482                                 // the uncle.\r
 483                                 if (Cur->isLeftChild() && Cur->getParent()->getRightChild())\r
 484                                 {\r
 485                                         Cur = Cur->getParent()->getRightChild();\r
 486                                         return;\r
 487                                 }\r
 488                                 Cur = Cur->getParent();\r
 489                         }\r
 490                 }\r
 491         }\r
 492 \r
 493         Node* Root;\r
 494         Node* Cur;\r
 495 \r
 496         }; // ParentFirstIterator\r
 497 \r
 498 \r
 499         //! Parent Last Iterator\r
 500         /** Traverse the tree from bottom to top.\r
 501         Typical usage is when deleting all elements in the tree\r
 502         because you must delete the children before you delete\r
 503         their parent. */\r
 504         class ParentLastIterator\r
 505         {\r
 506         public:\r
 507 \r
 508                 ParentLastIterator() : Root(0), Cur(0) {}\r
 509 \r
 510                 explicit ParentLastIterator(Node* root) : Root(root), Cur(0)\r
 511                 {\r
 512                         reset();\r
 513                 }\r
 514 \r
 515                 void reset()\r
 516                 {\r
 517                         Cur = getMin(Root);\r
 518                 }\r
 519 \r
 520                 bool atEnd() const\r
 521                 {\r
 522                         return Cur==0;\r
 523                 }\r
 524 \r
 525                 Node* getNode()\r
 526                 {\r
 527                         return Cur;\r
 528                 }\r
 529 \r
 530                 void operator++(int)\r
 531                 {\r
 532                         inc();\r
 533                 }\r
 534 \r
 535                 Node* operator -> ()\r
 536                 {\r
 537                         return getNode();\r
 538                 }\r
 539 \r
 540                 Node& operator* ()\r
 541                 {\r
 542                         _IRR_DEBUG_BREAK_IF(atEnd()) // access violation\r
 543 \r
 544                         return *getNode();\r
 545                 }\r
 546         private:\r
 547 \r
 548                 Node* getMin(Node* n)\r
 549                 {\r
 550                         while(n!=0 && (n->getLeftChild()!=0 || n->getRightChild()!=0))\r
 551                         {\r
 552                                 if (n->getLeftChild())\r
 553                                         n = n->getLeftChild();\r
 554                                 else\r
 555                                         n = n->getRightChild();\r
 556                         }\r
 557                         return n;\r
 558                 }\r
 559 \r
 560                 void inc()\r
 561                 {\r
 562                         // Already at end?\r
 563                         if (Cur==0)\r
 564                                 return;\r
 565 \r
 566                         // Note: Starting point is the node as far down to the left as possible.\r
 567 \r
 568                         // If current node has an uncle to the right, go to the\r
 569                         // node as far down to the left from the uncle as possible\r
 570                         // else just go up a level to the parent.\r
 571                         if (Cur->isLeftChild() && Cur->getParent()->getRightChild())\r
 572                         {\r
 573                                 Cur = getMin(Cur->getParent()->getRightChild());\r
 574                         }\r
 575                         else\r
 576                                 Cur = Cur->getParent();\r
 577                 }\r
 578 \r
 579                 Node* Root;\r
 580                 Node* Cur;\r
 581         }; // ParentLastIterator\r
 582 \r
 583 \r
 584         // AccessClass is a temporary class used with the [] operator.\r
 585         // It makes it possible to have different behavior in situations like:\r
 586         // myTree["Foo"] = 32;\r
 587         // If "Foo" already exists update its value else insert a new element.\r
 588         // int i = myTree["Foo"]\r
 589         // If "Foo" exists return its value.\r
 590         class AccessClass\r
 591         {\r
 592                 // Let map be the only one who can instantiate this class.\r
 593                 friend class map<KeyType, ValueType>;\r
 594 \r
 595         public:\r
 596 \r
 597                 // Assignment operator. Handles the myTree["Foo"] = 32; situation\r
 598                 void operator=(const ValueType& value)\r
 599                 {\r
 600                         // Just use the Set method, it handles already exist/not exist situation\r
 601                         Tree.set(Key,value);\r
 602                 }\r
 603 \r
 604                 // ValueType operator\r
 605                 operator ValueType()\r
 606                 {\r
 607                         Node* node = Tree.find(Key);\r
 608 \r
 609                         // Not found\r
 610                         _IRR_DEBUG_BREAK_IF(node==0) // access violation\r
 611 \r
 612                         return node->getValue();\r
 613                 }\r
 614 \r
 615         private:\r
 616 \r
 617                 AccessClass(map& tree, const KeyType& key) : Tree(tree), Key(key) {}\r
 618 \r
 619                 AccessClass();\r
 620 \r
 621                 map& Tree;\r
 622                 const KeyType& Key;\r
 623         }; // AccessClass\r
 624 \r
 625 \r
 626         // Constructor.\r
 627         map() : Root(0), Size(0) {}\r
 628 \r
 629         // Destructor\r
 630         ~map()\r
 631         {\r
 632                 clear();\r
 633         }\r
 634 \r
 635         // typedefs\r
 636         typedef KeyType key_type;\r
 637         typedef ValueType value_type;\r
 638         typedef u32 size_type;\r
 639 \r
 640         //------------------------------\r
 641         // Public Commands\r
 642         //------------------------------\r
 643 \r
 644         //! Inserts a new node into the tree\r
 645         /** \param keyNew: the index for this value\r
 646         \param v: the value to insert\r
 647         \return True if successful, false if it fails (already exists) */\r
 648         bool insert(const KeyType& keyNew, const ValueType& v)\r
 649         {\r
 650                 // First insert node the "usual" way (no fancy balance logic yet)\r
 651                 Node* newNode = new Node(keyNew,v);\r
 652                 if (!insert(newNode))\r
 653                 {\r
 654                         delete newNode;\r
 655                         return false;\r
 656                 }\r
 657 \r
 658                 // Then attend a balancing party\r
 659                 while (!newNode->isRoot() && (newNode->getParent()->isRed()))\r
 660                 {\r
 661                         if (newNode->getParent()->isLeftChild())\r
 662                         {\r
 663                                 // If newNode is a left child, get its right 'uncle'\r
 664                                 Node* newNodesUncle = newNode->getParent()->getParent()->getRightChild();\r
 665                                 if ( newNodesUncle!=0 && newNodesUncle->isRed())\r
 666                                 {\r
 667                                         // case 1 - change the colors\r
 668                                         newNode->getParent()->setBlack();\r
 669                                         newNodesUncle->setBlack();\r
 670                                         newNode->getParent()->getParent()->setRed();\r
 671                                         // Move newNode up the tree\r
 672                                         newNode = newNode->getParent()->getParent();\r
 673                                 }\r
 674                                 else\r
 675                                 {\r
 676                                         // newNodesUncle is a black node\r
 677                                         if ( newNode->isRightChild())\r
 678                                         {\r
 679                                                 // and newNode is to the right\r
 680                                                 // case 2 - move newNode up and rotate\r
 681                                                 newNode = newNode->getParent();\r
 682                                                 rotateLeft(newNode);\r
 683                                         }\r
 684                                         // case 3\r
 685                                         newNode->getParent()->setBlack();\r
 686                                         newNode->getParent()->getParent()->setRed();\r
 687                                         rotateRight(newNode->getParent()->getParent());\r
 688                                 }\r
 689                         }\r
 690                         else\r
 691                         {\r
 692                                 // If newNode is a right child, get its left 'uncle'\r
 693                                 Node* newNodesUncle = newNode->getParent()->getParent()->getLeftChild();\r
 694                                 if ( newNodesUncle!=0 && newNodesUncle->isRed())\r
 695                                 {\r
 696                                         // case 1 - change the colors\r
 697                                         newNode->getParent()->setBlack();\r
 698                                         newNodesUncle->setBlack();\r
 699                                         newNode->getParent()->getParent()->setRed();\r
 700                                         // Move newNode up the tree\r
 701                                         newNode = newNode->getParent()->getParent();\r
 702                                 }\r
 703                                 else\r
 704                                 {\r
 705                                         // newNodesUncle is a black node\r
 706                                         if (newNode->isLeftChild())\r
 707                                         {\r
 708                                                 // and newNode is to the left\r
 709                                                 // case 2 - move newNode up and rotate\r
 710                                                 newNode = newNode->getParent();\r
 711                                                 rotateRight(newNode);\r
 712                                         }\r
 713                                         // case 3\r
 714                                         newNode->getParent()->setBlack();\r
 715                                         newNode->getParent()->getParent()->setRed();\r
 716                                         rotateLeft(newNode->getParent()->getParent());\r
 717                                 }\r
 718 \r
 719                         }\r
 720                 }\r
 721                 // Color the root black\r
 722                 Root->setBlack();\r
 723                 return true;\r
 724         }\r
 725 \r
 726         //! Replaces the value if the key already exists, otherwise inserts a new element.\r
 727         /** \param k The index for this value\r
 728         \param v The new value of */\r
 729         void set(const KeyType& k, const ValueType& v)\r
 730         {\r
 731                 Node* p = find(k);\r
 732                 if (p)\r
 733                         p->setValue(v);\r
 734                 else\r
 735                         insert(k,v);\r
 736         }\r
 737 \r
 738         //! Removes a node from the tree and returns it.\r
 739         /** The returned node must be deleted by the user\r
 740         \param k the key to remove\r
 741         \return A pointer to the node, or 0 if not found */\r
 742         Node* delink(const KeyType& k)\r
 743         {\r
 744                 Node* p = find(k);\r
 745                 if (p == 0)\r
 746                         return 0;\r
 747 \r
 748                 // Rotate p down to the left until it has no right child, will get there\r
 749                 // sooner or later.\r
 750                 while(p->getRightChild())\r
 751                 {\r
 752                         // "Pull up my right child and let it knock me down to the left"\r
 753                         rotateLeft(p);\r
 754                 }\r
 755                 // p now has no right child but might have a left child\r
 756                 Node* left = p->getLeftChild();\r
 757 \r
 758                 // Let p's parent point to p's child instead of point to p\r
 759                 if (p->isLeftChild())\r
 760                         p->getParent()->setLeftChild(left);\r
 761 \r
 762                 else if (p->isRightChild())\r
 763                         p->getParent()->setRightChild(left);\r
 764 \r
 765                 else\r
 766                 {\r
 767                         // p has no parent => p is the root.\r
 768                         // Let the left child be the new root.\r
 769                         setRoot(left);\r
 770                 }\r
 771 \r
 772                 // p is now gone from the tree in the sense that\r
 773                 // no one is pointing at it, so return it.\r
 774 \r
 775                 --Size;\r
 776                 return p;\r
 777         }\r
 778 \r
 779         //! Removes a node from the tree and deletes it.\r
 780         /** \return True if the node was found and deleted */\r
 781         bool remove(const KeyType& k)\r
 782         {\r
 783                 Node* p = find(k);\r
 784                 return remove(p);\r
 785         }\r
 786 \r
 787         //! Removes a node from the tree and deletes it.\r
 788         /** \return True if the node was found and deleted */\r
 789         bool remove(Node* p)\r
 790         {\r
 791                 if (p == 0)\r
 792                 {\r
 793                         return false;\r
 794                 }\r
 795 \r
 796                 // Rotate p down to the left until it has no right child, will get there\r
 797                 // sooner or later.\r
 798                 while(p->getRightChild())\r
 799                 {\r
 800                         // "Pull up my right child and let it knock me down to the left"\r
 801                         rotateLeft(p);\r
 802                 }\r
 803                 // p now has no right child but might have a left child\r
 804                 Node* left = p->getLeftChild();\r
 805 \r
 806                 // Let p's parent point to p's child instead of point to p\r
 807                 if (p->isLeftChild())\r
 808                         p->getParent()->setLeftChild(left);\r
 809 \r
 810                 else if (p->isRightChild())\r
 811                         p->getParent()->setRightChild(left);\r
 812 \r
 813                 else\r
 814                 {\r
 815                         // p has no parent => p is the root.\r
 816                         // Let the left child be the new root.\r
 817                         setRoot(left);\r
 818                 }\r
 819 \r
 820                 // p is now gone from the tree in the sense that\r
 821                 // no one is pointing at it. Let's get rid of it.\r
 822                 delete p;\r
 823 \r
 824                 --Size;\r
 825                 return true;\r
 826         }\r
 827 \r
 828         //! Clear the entire tree\r
 829         void clear()\r
 830         {\r
 831                 ParentLastIterator i(getParentLastIterator());\r
 832 \r
 833                 while(!i.atEnd())\r
 834                 {\r
 835                         Node* p = i.getNode();\r
 836                         i++; // Increment it before it is deleted\r
 837                                 // else iterator will get quite confused.\r
 838                         delete p;\r
 839                 }\r
 840                 Root = 0;\r
 841                 Size= 0;\r
 842         }\r
 843 \r
 844         //! Is the tree empty?\r
 845         //! \return Returns true if empty, false if not\r
 846         bool empty() const\r
 847         {\r
 848                 return Root == 0;\r
 849         }\r
 850 \r
 851         //! \deprecated Use empty() instead. This method may be removed by Irrlicht 1.9\r
 852         _IRR_DEPRECATED_ bool isEmpty() const\r
 853         {\r
 854                 return empty();\r
 855         }\r
 856 \r
 857         //! Search for a node with the specified key.\r
 858         //! \param keyToFind: The key to find\r
 859         //! \return Returns 0 if node couldn't be found.\r
 860         Node* find(const KeyType& keyToFind) const\r
 861         {\r
 862                 Node* pNode = Root;\r
 863 \r
 864                 while(pNode!=0)\r
 865                 {\r
 866                         const KeyType& key=pNode->getKey();\r
 867 \r
 868                         if (keyToFind == key)\r
 869                                 return pNode;\r
 870                         else if (keyToFind < key)\r
 871                                 pNode = pNode->getLeftChild();\r
 872                         else //keyToFind > key\r
 873                                 pNode = pNode->getRightChild();\r
 874                 }\r
 875 \r
 876                 return 0;\r
 877         }\r
 878 \r
 879         //! Gets the root element.\r
 880         //! \return Returns a pointer to the root node, or\r
 881         //! 0 if the tree is empty.\r
 882         Node* getRoot() const\r
 883         {\r
 884                 return Root;\r
 885         }\r
 886 \r
 887         //! Returns the number of nodes in the tree.\r
 888         u32 size() const\r
 889         {\r
 890                 return Size;\r
 891         }\r
 892 \r
 893         //! Swap the content of this map container with the content of another map\r
 894         /** Afterwards this object will contain the content of the other object and the other\r
 895         object will contain the content of this object. Iterators will afterwards be valid for\r
 896         the swapped object.\r
 897         \param other Swap content with this object */\r
 898         void swap(map<KeyType, ValueType>& other)\r
 899         {\r
 900                 core::swap(Root, other.Root);\r
 901                 core::swap(Size, other.Size);\r
 902         }\r
 903 \r
 904         //------------------------------\r
 905         // Public Iterators\r
 906         //------------------------------\r
 907 \r
 908         //! Returns an iterator\r
 909         Iterator getIterator() const\r
 910         {\r
 911                 Iterator it(getRoot());\r
 912                 return it;\r
 913         }\r
 914 \r
 915         //! Returns a Constiterator\r
 916         ConstIterator getConstIterator() const\r
 917         {\r
 918                 Iterator it(getRoot());\r
 919                 return it;\r
 920         }\r
 921 \r
 922         //! Returns a ParentFirstIterator.\r
 923         //! Traverses the tree from top to bottom. Typical usage is\r
 924         //! when storing the tree structure, because when reading it\r
 925         //! later (and inserting elements) the tree structure will\r
 926         //! be the same.\r
 927         ParentFirstIterator getParentFirstIterator() const\r
 928         {\r
 929                 ParentFirstIterator it(getRoot());\r
 930                 return it;\r
 931         }\r
 932 \r
 933         //! Returns a ParentLastIterator to traverse the tree from\r
 934         //! bottom to top.\r
 935         //! Typical usage is when deleting all elements in the tree\r
 936         //! because you must delete the children before you delete\r
 937         //! their parent.\r
 938         ParentLastIterator getParentLastIterator() const\r
 939         {\r
 940                 ParentLastIterator it(getRoot());\r
 941                 return it;\r
 942         }\r
 943 \r
 944         //------------------------------\r
 945         // Public Operators\r
 946         //------------------------------\r
 947 \r
 948         //! operator [] for access to elements\r
 949         /** for example myMap["key"] */\r
 950         AccessClass operator[](const KeyType& k)\r
 951         {\r
 952                 return AccessClass(*this, k);\r
 953         }\r
 954         private:\r
 955 \r
 956         //------------------------------\r
 957         // Disabled methods\r
 958         //------------------------------\r
 959         // Copy constructor and assignment operator deliberately\r
 960         // defined but not implemented. The tree should never be\r
 961         // copied, pass along references to it instead.\r
 962         explicit map(const map& src);\r
 963         map& operator = (const map& src);\r
 964 \r
 965         //! Set node as new root.\r
 966         /** The node will be set to black, otherwise core dumps may arise\r
 967         (patch provided by rogerborg).\r
 968         \param newRoot Node which will be the new root\r
 969         */\r
 970         void setRoot(Node* newRoot)\r
 971         {\r
 972                 Root = newRoot;\r
 973                 if (Root != 0)\r
 974                 {\r
 975                         Root->setParent(0);\r
 976                         Root->setBlack();\r
 977                 }\r
 978         }\r
 979 \r
 980         //! Insert a node into the tree without using any fancy balancing logic.\r
 981         /** \return false if that key already exist in the tree. */\r
 982         bool insert(Node* newNode)\r
 983         {\r
 984                 bool result=true; // Assume success\r
 985 \r
 986                 if (Root==0)\r
 987                 {\r
 988                         setRoot(newNode);\r
 989                         Size = 1;\r
 990                 }\r
 991                 else\r
 992                 {\r
 993                         Node* pNode = Root;\r
 994                         const KeyType& keyNew = newNode->getKey();\r
 995                         while (pNode)\r
 996                         {\r
 997                                 const KeyType& key=pNode->getKey();\r
 998 \r
 999                                 if (keyNew == key)\r
1000                                 {\r
1001                                         result = false;\r
1002                                         pNode = 0;\r
1003                                 }\r
1004                                 else if (keyNew < key)\r
1005                                 {\r
1006                                         if (pNode->getLeftChild() == 0)\r
1007                                         {\r
1008                                                 pNode->setLeftChild(newNode);\r
1009                                                 pNode = 0;\r
1010                                         }\r
1011                                         else\r
1012                                                 pNode = pNode->getLeftChild();\r
1013                                 }\r
1014                                 else // keyNew > key\r
1015                                 {\r
1016                                         if (pNode->getRightChild()==0)\r
1017                                         {\r
1018                                                 pNode->setRightChild(newNode);\r
1019                                                 pNode = 0;\r
1020                                         }\r
1021                                         else\r
1022                                         {\r
1023                                                 pNode = pNode->getRightChild();\r
1024                                         }\r
1025                                 }\r
1026                         }\r
1027 \r
1028                         if (result)\r
1029                                 ++Size;\r
1030                 }\r
1031 \r
1032                 return result;\r
1033         }\r
1034 \r
1035         //! Rotate left.\r
1036         //! Pull up node's right child and let it knock node down to the left\r
1037         void rotateLeft(Node* p)\r
1038         {\r
1039                 Node* right = p->getRightChild();\r
1040 \r
1041                 p->setRightChild(right->getLeftChild());\r
1042 \r
1043                 if (p->isLeftChild())\r
1044                         p->getParent()->setLeftChild(right);\r
1045                 else if (p->isRightChild())\r
1046                         p->getParent()->setRightChild(right);\r
1047                 else\r
1048                         setRoot(right);\r
1049 \r
1050                 right->setLeftChild(p);\r
1051         }\r
1052 \r
1053         //! Rotate right.\r
1054         //! Pull up node's left child and let it knock node down to the right\r
1055         void rotateRight(Node* p)\r
1056         {\r
1057                 Node* left = p->getLeftChild();\r
1058 \r
1059                 p->setLeftChild(left->getRightChild());\r
1060 \r
1061                 if (p->isLeftChild())\r
1062                         p->getParent()->setLeftChild(left);\r
1063                 else if (p->isRightChild())\r
1064                         p->getParent()->setRightChild(left);\r
1065                 else\r
1066                         setRoot(left);\r
1067 \r
1068                 left->setRightChild(p);\r
1069         }\r
1070 \r
1071         //------------------------------\r
1072         // Private Members\r
1073         //------------------------------\r
1074         Node* Root; // The top node. 0 if empty.\r
1075         u32 Size; // Number of nodes in the tree\r
1076 };\r
1077 \r
1078 } // end namespace core\r
1079 } // end namespace irr\r
1080 \r
1081 #endif // __IRR_MAP_H_INCLUDED__\r
1082 \r