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