kjs Library API Documentation

property_map.cpp

00001 // -*- c-basic-offset: 2 -*-
00002 /*
00003  *  This file is part of the KDE libraries
00004  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
00005  *
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 of the License, or (at your option) any later version.
00010  *
00011  *  This library is distributed in the hope that it will be useful,
00012  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  *  Lesser General Public License for more details.
00015  *
00016  *  You should have received a copy of the GNU Lesser General Public License
00017  *  along with this library; see the file COPYING.LIB.  If not, write to
00018  *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00019  *  Boston, MA 02111-1307, USA.
00020  *
00021  */
00022 
00023 
00024 #include "property_map.h"
00025 
00026 #include <string.h>
00027 #include <assert.h>
00028 #include <stdio.h>
00029 
00030 using namespace KJS;
00031 
00032 // ------------------------------ PropertyMapNode ------------------------------
00033 
00034 void PropertyMapNode::setLeft(PropertyMapNode *newLeft)
00035 {
00036   if (left)
00037     left->setParent(0);
00038   left = newLeft;
00039   if (left)
00040     left->setParent(this);
00041 }
00042 
00043 void PropertyMapNode::setRight(PropertyMapNode *newRight)
00044 {
00045   if (right)
00046     right->setParent(0);
00047   right = newRight;
00048   if (right)
00049     right->setParent(this);
00050 }
00051 
00052 void PropertyMapNode::setParent(PropertyMapNode *newParent)
00053 {
00054   if (parent) {
00055     //assert(this == parent->left || this == parent->right);
00056     if (this == parent->left)
00057       parent->left = 0;
00058     else
00059       parent->right = 0;
00060   }
00061   parent = newParent;
00062 }
00063 
00064 PropertyMapNode *PropertyMapNode::findMax()
00065 {
00066   PropertyMapNode *max = this;
00067   while (max->right)
00068     max = max->right;
00069   return max;
00070 }
00071 
00072 PropertyMapNode *PropertyMapNode::findMin()
00073 {
00074   PropertyMapNode *min = this;
00075   while (min->left)
00076     min = min->left;
00077   return min;
00078 }
00079 
00080 PropertyMapNode *PropertyMapNode::next()
00081 {
00082   // find the next node, going from lowest name to highest name
00083 
00084   // We have a right node. Starting from our right node, keep going left as far as we can
00085   if (right) {
00086     PropertyMapNode *n = right;
00087     while (n->left)
00088       n = n->left;
00089     return n;
00090   }
00091 
00092   // We have no right node. Keep going up to the left, until we find a node that has a parent
00093   // to the right. If we find one, go to it. Otherwise, we have reached the end.
00094   PropertyMapNode *n = this;
00095   while (n->parent && n->parent->right == n) {
00096     // parent is to our left
00097     n = n->parent;
00098   }
00099   if (n->parent && n->parent->left == n) {
00100     // parent is to our right
00101     return n->parent;
00102   }
00103 
00104   return 0;
00105 }
00106 
00107 // ------------------------------ PropertyMap ----------------------------------
00108 
00109 int KJS::uscompare(const UString &s1, const UString &s2)
00110 {
00111   int len1 = s1.size();
00112   int len2 = s2.size();
00113   if (len1 < len2)
00114     return -1;
00115   else if (len1 > len2)
00116     return 1;
00117   else
00118     return memcmp(s1.data(), s2.data(), len1*sizeof(UChar));
00119 }
00120 
00121 PropertyMap::PropertyMap()
00122 {
00123   root = 0;
00124 }
00125 
00126 PropertyMap::~PropertyMap()
00127 {
00128   clear();
00129 }
00130 
00131 void PropertyMap::put(const UString &name, ValueImp *value, int attr)
00132 {
00133   // if not root; make the root the new node
00134   if (!root) {
00135     root = new PropertyMapNode(name, value, attr, 0);
00136     return;
00137   }
00138 
00139   // try to find the parent node
00140   PropertyMapNode *parent = root;
00141   int isLeft = false;
00142   while (true) {
00143     int cmp = uscompare(name, parent->name);
00144     if (cmp < 0) {
00145       // traverse to left node (if any)
00146       isLeft = true;
00147       if (!parent->left)
00148         break;
00149       else
00150         parent = parent->left;
00151     }
00152     else if (cmp > 0) {
00153       // traverse to right node (if any)
00154       isLeft = false;
00155       if (!parent->right)
00156         break;
00157       else
00158         parent = parent->right;
00159     }
00160     else {
00161       // a node with this name already exists; just replace the value
00162       parent->value = value;
00163       return;
00164     }
00165   }
00166 
00167   // we found the parent
00168   //assert(parent);
00169 
00170   if (isLeft) {
00171     //assert(!parent->left);
00172     parent->left = new PropertyMapNode(name, value, attr, parent);
00173   }
00174   else {
00175     //assert(!parent->right);
00176     parent->right = new PropertyMapNode(name, value, attr, parent);
00177   }
00178   updateHeight(parent);
00179 
00180 
00181   PropertyMapNode *node = parent;
00182   while (node) {
00183     PropertyMapNode *p = node->parent;
00184     balance(node); // may change node
00185     node = p;
00186   }
00187 }
00188 
00189 void PropertyMap::remove(const UString &name)
00190 {
00191   PropertyMapNode *node = getNode(name);
00192   if (!node) // name not in tree
00193     return;
00194 
00195   PropertyMapNode *removed = remove(node);
00196   if (removed)
00197     delete node;
00198 }
00199 
00200 ValueImp *PropertyMap::get(const UString &name) const
00201 {
00202   const PropertyMapNode *n = getNode(name);
00203   return n ? n->value : 0;
00204 }
00205 
00206 void PropertyMap::clear(PropertyMapNode *node)
00207 {
00208   if (node == 0)
00209     node = root;
00210   if (node == 0) // nothing to do
00211     return;
00212 
00213   if (node->left)
00214     clear(node->left);
00215   if (node->right)
00216     clear(node->right);
00217   if (node == root)
00218     root = 0;
00219   delete node;
00220 }
00221 
00222 void PropertyMap::dump(const PropertyMapNode *node, int indent) const
00223 {
00224   if (!node && indent > 0)
00225     return;
00226   if (!node)
00227     node = root;
00228   if (!node)
00229     return;
00230 
00231   assert(!node->right || node->right->parent == node);
00232   dump(node->right, indent+1);
00233   for (int i = 0; i < indent; i++) {
00234     printf("    ");
00235   }
00236   printf("[%d] %s\n", node->height, node->name.ascii());
00237   assert(!node->left || node->left->parent == node);
00238   dump(node->left, indent+1);
00239 }
00240 
00241 void PropertyMap::checkTree(const PropertyMapNode *node) const
00242 {
00243   if (!root)
00244     return;
00245   if (node == 0)
00246     node = root;
00247   if (node == root) {
00248     assert(!node->parent);
00249   }
00250   assert(!node->right || node->right->parent == node);
00251   assert(!node->left || node->left->parent == node);
00252   assert(node->left != node);
00253   assert(node->right != node);
00254   if (node->left && node->right)
00255     assert(node->left != node->right);
00256 
00257   PropertyMapNode *n = node->parent;
00258   while (n) {
00259     assert(n != node);
00260     n = n->parent;
00261   }
00262 
00263   if (node->right)
00264     checkTree(node->right);
00265   if (node->left)
00266     checkTree(node->left);
00267 }
00268 
00269 PropertyMapNode *PropertyMap::getNode(const UString &name) const
00270 {
00271   PropertyMapNode *node = root;
00272 #if 1 // optimized version of ...
00273   int len1 = name.size();
00274   int ulen = len1 * sizeof(UChar);
00275   const UChar* const data1 = name.data();
00276   while (node) {
00277     int diff = len1 - node->name.size();
00278     if (diff == 0 && (diff = memcmp(data1, node->name.data(), ulen)) == 0)
00279     return node;
00280     node = diff < 0 ? node->left : node->right;
00281   }
00282 #else // this one
00283     while (node) {
00284       int cmp = uscompare(name, node->name);
00285       if (cmp == 0)
00286     return node;
00287       node = cmp < 0 ? node->left : node->right;
00288     }
00289 #endif
00290   return 0;
00291 }
00292 
00293 PropertyMapNode *PropertyMap::first() const
00294 {
00295   if (!root)
00296     return 0;
00297 
00298   PropertyMapNode *node = root;
00299   while (node->left)
00300     node = node->left;
00301   return node;
00302 }
00303 
00304 PropertyMapNode * PropertyMap::remove(PropertyMapNode *node)
00305 {
00306   PropertyMapNode *parent = node->parent;
00307   //assert(!parent || (node == parent->left || node == parent->right));
00308   bool isLeft = (parent && node == parent->left);
00309 
00310   PropertyMapNode *replace = 0;
00311   if (node->left && node->right) {
00312     PropertyMapNode *maxLeft = node->left->findMax();
00313     if (maxLeft == node->left) {
00314       maxLeft->setRight(node->right);
00315       replace = maxLeft;
00316     }
00317     else {
00318       remove(maxLeft);
00319 
00320       maxLeft->setLeft(node->left);
00321       maxLeft->setRight(node->right);
00322       replace = maxLeft;
00323     }
00324     // removing maxLeft could have re-balanced the tree, so recalculate
00325     // parent again
00326     parent = node->parent;
00327     //assert(!parent || (node == parent->left || node == parent->right));
00328     isLeft = (parent && node == parent->left);
00329   }
00330   else if (node->left) {
00331     replace = node->left;
00332   }
00333   else if (node->right) {
00334     replace = node->right;
00335   }
00336   else {
00337     replace = 0;
00338   }
00339 
00340   if (parent) {
00341     if (isLeft)
00342       parent->setLeft(replace);
00343     else
00344       parent->setRight(replace);
00345   }
00346   else {
00347     root = replace;
00348     if (replace)
00349       replace->parent = 0;
00350   }
00351 
00352   if (replace)
00353     updateHeight(replace); // will also update parent's height
00354   else if (parent)
00355     updateHeight(parent);
00356   else if (root)
00357     updateHeight(root);
00358 
00359 
00360   // balance the tree
00361   PropertyMapNode *bal = parent;
00362   while (bal) {
00363     PropertyMapNode *p = bal->parent;
00364     balance(bal); // may change bal
00365     bal = p;
00366   }
00367 
00368   return node;
00369 }
00370 
00371 void PropertyMap::balance(PropertyMapNode* node)
00372 {
00373   int lheight = node->left ? node->left->height : 0;
00374   int rheight = node->right ? node->right->height : 0;
00375 
00376   int bal = rheight-lheight;
00377 
00378   if (bal < -1) {
00379     //assert(node->left);
00380     int llheight = node->left->left ? node->left->left->height : 0;
00381     int lrheight = node->left->right ? node->left->right->height : 0;
00382     int lbal = lrheight - llheight;
00383 
00384     if (lbal < 0) {
00385       rotateLL(node); // LL rotation
00386     }
00387     else {
00388       // lbal >= 0
00389       rotateLR(node);
00390     }
00391   }
00392   else if (bal > 1) {
00393     int rlheight = node->right->left ? node->right->left->height : 0;
00394     int rrheight = node->right->right ? node->right->right->height : 0;
00395     int rbal = rrheight - rlheight;
00396     if (rbal < 0) {
00397       rotateRL(node);
00398     }
00399     else {
00400       // rbal >= 0
00401       rotateRR(node); // RR rotateion
00402     }
00403   }
00404 }
00405 
00406 void PropertyMap::updateHeight(PropertyMapNode* &node)
00407 {
00408   int lheight = node->left ? node->left->height : 0;
00409   int rheight = node->right ? node->right->height : 0;
00410   if (lheight > rheight)
00411     node->height = lheight+1;
00412   else
00413     node->height = rheight+1;
00414   //assert(node->parent != node);
00415   if (node->parent)
00416     updateHeight(node->parent);
00417 }
00418 
00419 void PropertyMap::rotateRR(PropertyMapNode* &node)
00420 {
00421   /*
00422     Perform a RR ("single left") rotation, e.g.
00423 
00424       a                b
00425      / \              / \
00426     X   b     -->    a   Z
00427        / \          / \
00428       Y   Z        X   Y
00429   */
00430 
00431   // Here, node is initially a, will be replaced with b
00432 
00433   PropertyMapNode *a = node;
00434   PropertyMapNode *b = node->right;
00435 
00436   PropertyMapNode *parent = a->parent;
00437   //assert(!parent || (a == parent->left || a == parent->right));
00438   bool isLeft = (parent && a == parent->left);
00439 
00440   // do the rotation
00441   a->setRight(b->left);
00442   b->setLeft(a);
00443 
00444   // now node is b
00445   node = b;
00446   if (parent) {
00447     if (isLeft)
00448       parent->setLeft(b);
00449     else
00450       parent->setRight(b);
00451   }
00452   else {
00453     // a was the root node
00454     root = b;
00455   }
00456 
00457   updateHeight(a);
00458   updateHeight(b);
00459 }
00460 
00461 
00462 void PropertyMap::rotateLL(PropertyMapNode* &node)
00463 {
00464   /*
00465     Perform a LL ("single right") rotation, e.g.
00466 
00467 
00468         a              b
00469        / \            / \
00470       b   Z   -->    X   a
00471      / \                / \
00472     X   Y              Y   Z
00473   */
00474 
00475   // Here, node is initially a, will be replaced with b
00476 
00477   PropertyMapNode *a = node;
00478   PropertyMapNode *b = node->left;
00479 
00480   PropertyMapNode *parent = a->parent;
00481   //assert(!parent || (a == parent->left || a == parent->right));
00482   bool isLeft = (parent && a == parent->left);
00483 
00484   // do the rotation
00485   a->setLeft(b->right);
00486   b->setRight(a);
00487 
00488   // now node is b
00489   node = b;
00490   if (parent) {
00491     if (isLeft)
00492       parent->setLeft(b);
00493     else
00494       parent->setRight(b);
00495   }
00496   else {
00497     // a was the root node
00498     root = b;
00499   }
00500 
00501   updateHeight(a);
00502   updateHeight(b);
00503 }
00504 
00505 void PropertyMap::rotateRL(PropertyMapNode* &node)
00506 {
00507   /*
00508     Perform a RL ("double left") rotation, e.g.
00509 
00510         a                   a                          b
00511       /   \      LL on c  /   \          RR on b     /   \
00512      W      c      -->   W      b          -->     a       c
00513            / \                 / \                / \     / \
00514           b   Z               X   c              W   X   Y   Z
00515          / \                     / \
00516         X   Y                   Y   Z
00517 
00518   */
00519 
00520   PropertyMapNode *a = node;
00521   PropertyMapNode *c = node->right;
00522   PropertyMapNode *b = node->right->left;
00523 
00524   rotateLL(c);
00525   rotateRR(b);
00526 
00527   updateHeight(a);
00528   updateHeight(c);
00529   updateHeight(b);
00530 }
00531 
00532 void PropertyMap::rotateLR(PropertyMapNode* &node)
00533 {
00534   /*
00535     Perform a LR ("double right") rotation, e.g.
00536 
00537           a                         a                      b
00538         /   \    RR on c          /   \     LL on a      /   \
00539       c       Z    -->          b       Z     -->      c       a
00540      / \                       / \                    / \     / \
00541     W   b                     c   Y                  W   X   Y   Z
00542        / \                   / \
00543       X   Y                 W   X
00544   */
00545 
00546   PropertyMapNode *a = node;
00547   PropertyMapNode *c = node->left;
00548   PropertyMapNode *b = node->left->right;
00549 
00550   rotateRR(c);
00551   rotateLL(a);
00552 
00553   updateHeight(c);
00554   updateHeight(a);
00555   updateHeight(b);
00556 }
KDE Logo
This file is part of the documentation for kdelibs Version 3.1.4.
Documentation copyright © 1996-2002 the KDE developers.
Generated on Sun Feb 27 22:15:18 2005 by doxygen 1.3.4 written by Dimitri van Heesch, © 1997-2001