property_map.cpp
00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
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
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
00083
00084
00085 if (right) {
00086 PropertyMapNode *n = right;
00087 while (n->left)
00088 n = n->left;
00089 return n;
00090 }
00091
00092
00093
00094 PropertyMapNode *n = this;
00095 while (n->parent && n->parent->right == n) {
00096
00097 n = n->parent;
00098 }
00099 if (n->parent && n->parent->left == n) {
00100
00101 return n->parent;
00102 }
00103
00104 return 0;
00105 }
00106
00107
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
00134 if (!root) {
00135 root = new PropertyMapNode(name, value, attr, 0);
00136 return;
00137 }
00138
00139
00140 PropertyMapNode *parent = root;
00141 int isLeft = false;
00142 while (true) {
00143 int cmp = uscompare(name, parent->name);
00144 if (cmp < 0) {
00145
00146 isLeft = true;
00147 if (!parent->left)
00148 break;
00149 else
00150 parent = parent->left;
00151 }
00152 else if (cmp > 0) {
00153
00154 isLeft = false;
00155 if (!parent->right)
00156 break;
00157 else
00158 parent = parent->right;
00159 }
00160 else {
00161
00162 parent->value = value;
00163 return;
00164 }
00165 }
00166
00167
00168
00169
00170 if (isLeft) {
00171
00172 parent->left = new PropertyMapNode(name, value, attr, parent);
00173 }
00174 else {
00175
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);
00185 node = p;
00186 }
00187 }
00188
00189 void PropertyMap::remove(const UString &name)
00190 {
00191 PropertyMapNode *node = getNode(name);
00192 if (!node)
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)
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
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
00325
00326 parent = node->parent;
00327
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);
00354 else if (parent)
00355 updateHeight(parent);
00356 else if (root)
00357 updateHeight(root);
00358
00359
00360
00361 PropertyMapNode *bal = parent;
00362 while (bal) {
00363 PropertyMapNode *p = bal->parent;
00364 balance(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
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);
00386 }
00387 else {
00388
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
00401 rotateRR(node);
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
00415 if (node->parent)
00416 updateHeight(node->parent);
00417 }
00418
00419 void PropertyMap::rotateRR(PropertyMapNode* &node)
00420 {
00421
00422
00423
00424
00425
00426
00427
00428
00429
00430
00431
00432
00433 PropertyMapNode *a = node;
00434 PropertyMapNode *b = node->right;
00435
00436 PropertyMapNode *parent = a->parent;
00437
00438 bool isLeft = (parent && a == parent->left);
00439
00440
00441 a->setRight(b->left);
00442 b->setLeft(a);
00443
00444
00445 node = b;
00446 if (parent) {
00447 if (isLeft)
00448 parent->setLeft(b);
00449 else
00450 parent->setRight(b);
00451 }
00452 else {
00453
00454 root = b;
00455 }
00456
00457 updateHeight(a);
00458 updateHeight(b);
00459 }
00460
00461
00462 void PropertyMap::rotateLL(PropertyMapNode* &node)
00463 {
00464
00465
00466
00467
00468
00469
00470
00471
00472
00473
00474
00475
00476
00477 PropertyMapNode *a = node;
00478 PropertyMapNode *b = node->left;
00479
00480 PropertyMapNode *parent = a->parent;
00481
00482 bool isLeft = (parent && a == parent->left);
00483
00484
00485 a->setLeft(b->right);
00486 b->setRight(a);
00487
00488
00489 node = b;
00490 if (parent) {
00491 if (isLeft)
00492 parent->setLeft(b);
00493 else
00494 parent->setRight(b);
00495 }
00496 else {
00497
00498 root = b;
00499 }
00500
00501 updateHeight(a);
00502 updateHeight(b);
00503 }
00504
00505 void PropertyMap::rotateRL(PropertyMapNode* &node)
00506 {
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
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
00536
00537
00538
00539
00540
00541
00542
00543
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 }
This file is part of the documentation for kdelibs Version 3.1.0.