1// This may look like C code, but it is really -*- C++ -*- 2/* 3Copyright (C) 1988 Free Software Foundation 4 written by Doug Lea (dl@rocky.oswego.edu) 5 6This file is part of GNU CC. 7 8GNU CC is distributed in the hope that it will be useful, 9but WITHOUT ANY WARRANTY. No author or distributor 10accepts responsibility to anyone for the consequences of using it 11or for whether it serves any particular purpose or works at all, 12unless he says so in writing. Refer to the GNU CC General Public 13License for full details. 14 15Everyone is granted permission to copy, modify and redistribute 16GNU CC, but only under the conditions described in the 17GNU CC General Public License. A copy of this license is 18supposed to have been given to you along with GNU CC so you 19can know your rights and responsibilities. It should be in a 20file named COPYING. Among other things, the copyright notice 21and this notice must be preserved on all copies. 22*/ 23 24#ifdef __GNUG__ 25#pragma implementation 26#endif 27#include <stream.h> 28#include <assert.h> 29#include "<T>.SplaySet.h" 30 31 32/* 33 34 struct to simulate the special `null' node in the Sleater & Tarjan JACM 1985 35 splay tree algorithms 36 37 All routines use a version of their `simple top-down' splay alg. (p 669) 38 39*/ 40 41struct _dummySplayNode 42{ 43 <T>SplayNode* lt; 44 <T>SplayNode* rt; 45 <T>SplayNode* par; 46} _dummy_null; 47 48 49/* 50 traversal primitives 51*/ 52 53 54<T>SplayNode* <T>SplaySet::leftmost() 55{ 56 <T>SplayNode* t = root; 57 if (t != 0) while (t->lt != 0) t = t->lt; 58 return t; 59} 60 61<T>SplayNode* <T>SplaySet::rightmost() 62{ 63 <T>SplayNode* t = root; 64 if (t != 0) while (t->rt != 0) t = t->rt; 65 return t; 66} 67 68<T>SplayNode* <T>SplaySet::succ(<T>SplayNode* t) 69{ 70 if (t == 0) 71 return 0; 72 if (t->rt != 0) 73 { 74 t = t->rt; 75 while (t->lt != 0) t = t->lt; 76 return t; 77 } 78 else 79 { 80 for (;;) 81 { 82 if (t->par == 0 || t == t->par->lt) 83 return t->par; 84 else 85 t = t->par; 86 } 87 } 88} 89 90<T>SplayNode* <T>SplaySet::pred(<T>SplayNode* t) 91{ 92 if (t == 0) 93 return 0; 94 else if (t->lt != 0) 95 { 96 t = t->lt; 97 while (t->rt != 0) t = t->rt; 98 return t; 99 } 100 else 101 { 102 for (;;) 103 { 104 if (t->par == 0 || t == t->par->rt) 105 return t->par; 106 else 107 t = t->par; 108 } 109 } 110} 111 112 113Pix <T>SplaySet::seek(<T&> key) 114{ 115 <T>SplayNode* t = root; 116 if (t == 0) 117 return 0; 118 119 int comp = <T>CMP(key, t->item); 120 if (comp == 0) 121 return Pix(t); 122 123 <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null); 124 <T>SplayNode* l = dummy; 125 <T>SplayNode* r = dummy; 126 dummy->rt = dummy->lt = dummy->par = 0; 127 128 while (comp != 0) 129 { 130 if (comp > 0) 131 { 132 <T>SplayNode* tr = t->rt; 133 if (tr == 0) 134 break; 135 else 136 { 137 comp = <T>CMP(key, tr->item); 138 if (comp <= 0 || tr->rt == 0) 139 { 140 l->rt = t; t->par = l; 141 l = t; 142 t = tr; 143 if (comp >= 0) 144 break; 145 } 146 else 147 { 148 if ((t->rt = tr->lt) != 0) t->rt->par = t; 149 tr->lt = t; t->par = tr; 150 l->rt = tr; tr->par = l; 151 l = tr; 152 t = tr->rt; 153 comp = <T>CMP(key, t->item); 154 } 155 } 156 } 157 else 158 { 159 <T>SplayNode* tl = t->lt; 160 if (tl == 0) 161 break; 162 else 163 { 164 comp = <T>CMP(key, tl->item); 165 if (comp >= 0 || tl->lt == 0) 166 { 167 r->lt = t; t->par = r; 168 r = t; 169 t = tl; 170 if (comp <= 0) 171 break; 172 } 173 else 174 { 175 if ((t->lt = tl->rt) != 0) t->lt->par = t; 176 tl->rt = t; t->par = tl; 177 r->lt = tl; tl->par = r; 178 r = tl; 179 t = tl->lt; 180 comp = <T>CMP(key, t->item); 181 } 182 } 183 } 184 } 185 if ((r->lt = t->rt) != 0) r->lt->par = r; 186 if ((l->rt = t->lt) != 0) l->rt->par = l; 187 if ((t->lt = dummy->rt) != 0) t->lt->par = t; 188 if ((t->rt = dummy->lt) != 0) t->rt->par = t; 189 t->par = 0; 190 root = t; 191 return (comp == 0) ? Pix(t) : 0; 192} 193 194 195 196Pix <T>SplaySet::add(<T&> item) 197{ 198 <T>SplayNode* t = root; 199 if (t == 0) 200 { 201 ++count; 202 root = new <T>SplayNode(item); 203 return Pix(root); 204 } 205 int comp = <T>CMP(item, t->item); 206 if (comp == 0) 207 return Pix(t); 208 209 <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null); 210 <T>SplayNode* l = dummy; 211 <T>SplayNode* r = dummy; 212 dummy->rt = dummy->lt = dummy->par = 0; 213 214 while (comp != 0) 215 { 216 if (comp > 0) 217 { 218 <T>SplayNode* tr = t->rt; 219 if (tr == 0) 220 { 221 ++count; 222 tr = new <T>SplayNode(item); 223 comp = 0; 224 } 225 else 226 comp = <T>CMP(item, tr->item); 227 228 if (comp <= 0) 229 { 230 l->rt = t; t->par = l; 231 l = t; 232 t = tr; 233 } 234 else 235 { 236 <T>SplayNode* trr = tr->rt; 237 if (trr == 0) 238 { 239 ++count; 240 trr = new <T>SplayNode(item); 241 comp = 0; 242 } 243 else 244 comp = <T>CMP(item, trr->item); 245 246 if ((t->rt = tr->lt) != 0) t->rt->par = t; 247 tr->lt = t; t->par = tr; 248 l->rt = tr; tr->par = l; 249 l = tr; 250 t = trr; 251 } 252 } 253 else 254 { 255 <T>SplayNode* tl = t->lt; 256 if (tl == 0) 257 { 258 ++count; 259 tl = new <T>SplayNode(item); 260 comp = 0; 261 } 262 else 263 comp = <T>CMP(item, tl->item); 264 265 if (comp >= 0) 266 { 267 r->lt = t; t->par = r; 268 r = t; 269 t = tl; 270 } 271 else 272 { 273 <T>SplayNode* tll = tl->lt; 274 if (tll == 0) 275 { 276 ++count; 277 tll = new <T>SplayNode(item); 278 comp = 0; 279 } 280 else 281 comp = <T>CMP(item, tll->item); 282 283 if ((t->lt = tl->rt) != 0) t->lt->par = t; 284 tl->rt = t; t->par = tl; 285 r->lt = tl; tl->par = r; 286 r = tl; 287 t = tll; 288 } 289 } 290 } 291 if ((r->lt = t->rt) != 0) r->lt->par = r; 292 if ((l->rt = t->lt) != 0) l->rt->par = l; 293 if ((t->lt = dummy->rt) != 0) t->lt->par = t; 294 if ((t->rt = dummy->lt) != 0) t->rt->par = t; 295 t->par = 0; 296 root = t; 297 return Pix(root); 298} 299 300void <T>SplaySet::del(<T&> key) 301{ 302 <T>SplayNode* t = (<T>SplayNode*)(seek(key)); 303 if (t == 0) return; 304 305 <T>SplayNode* p = t->par; 306 307 --count; 308 if (t->rt == 0) 309 { 310 if (t == root) 311 { 312 if ((root = t->lt) != 0) root->par = 0; 313 } 314 else if (t == p->lt) 315 { 316 if ((p->lt = t->lt) != 0) p->lt->par = p; 317 } 318 else 319 if ((p->rt = t->lt) != 0) p->rt->par = p; 320 } 321 else 322 { 323 <T>SplayNode* r = t->rt; 324 <T>SplayNode* l = r->lt; 325 for(;;) 326 { 327 if (l == 0) 328 { 329 if (t == root) 330 { 331 root = r; 332 r->par = 0; 333 } 334 else if (t == p->lt) 335 { 336 p->lt = r; 337 r->par = p; 338 } 339 else 340 { 341 p->rt = r; 342 r->par = p; 343 } 344 if ((r->lt = t->lt) != 0) r->lt->par = r; 345 break; 346 } 347 else 348 { 349 if ((r->lt = l->rt) != 0) r->lt->par = r; 350 l->rt = r; r->par = l; 351 r = l; 352 l = l->lt; 353 } 354 } 355 } 356 delete t; 357} 358 359 360void <T>SplaySet::_kill(<T>SplayNode* t) 361{ 362 if (t != 0) 363 { 364 _kill(t->lt); 365 _kill(t->rt); 366 delete t; 367 } 368} 369 370 371<T>SplayNode* <T>SplaySet::_copy(<T>SplayNode* t) 372{ 373 if (t != 0) 374 { 375 <T>SplayNode* l = _copy(t->lt); 376 <T>SplayNode* r = _copy(t->rt); 377 <T>SplayNode* x = new <T>SplayNode(t->item, l, r); 378 if (l != 0) l->par = x; 379 if (r != 0) r->par = x; 380 return x; 381 } 382 else 383 return 0; 384} 385 386/* relationals */ 387 388int <T>SplaySet::operator == (<T>SplaySet& y) 389{ 390 if (count != y.count) 391 return 0; 392 else 393 { 394 <T>SplayNode* t = leftmost(); 395 <T>SplayNode* u = y.leftmost(); 396 for (;;) 397 { 398 if (t == 0) 399 return 1; 400 else if (!<T>EQ(t->item, u->item)) 401 return 0; 402 else 403 { 404 t = succ(t); 405 u = y.succ(u); 406 } 407 } 408 } 409} 410 411int <T>SplaySet::operator <= (<T>SplaySet& y) 412{ 413 if (count > y.count) 414 return 0; 415 else 416 { 417 <T>SplayNode* t = leftmost(); 418 <T>SplayNode* u = y.leftmost(); 419 for (;;) 420 { 421 if (t == 0) 422 return 1; 423 else if (u == 0) 424 return 0; 425 int cmp = <T>CMP(t->item, u->item); 426 if (cmp == 0) 427 { 428 t = succ(t); 429 u = y.succ(u); 430 } 431 else if (cmp < 0) 432 return 0; 433 else 434 u = y.succ(u); 435 } 436 } 437} 438 439 440void <T>SplaySet::operator |=(<T>SplaySet& y) 441{ 442 if (&y == this) return; 443 <T>SplayNode* u = y.leftmost(); 444 while (u != 0) 445 { 446 add(u->item); 447 u = y.succ(u); 448 } 449} 450 451void <T>SplaySet::operator &= (<T>SplaySet& y) 452{ 453 if (y.count == 0) 454 clear(); 455 else if (&y != this && count != 0) 456 { 457 <T>SplayNode* t = leftmost(); 458 while (t != 0) 459 { 460 <T>SplayNode* s = succ(t); 461 if (y.seek(t->item) == 0) del(t->item); 462 t = s; 463 } 464 } 465} 466 467 468void <T>SplaySet::operator -=(<T>SplaySet& y) 469{ 470 if (&y == this) 471 clear(); 472 else if (y.count != 0) 473 { 474 <T>SplayNode* t = leftmost(); 475 while (t != 0) 476 { 477 <T>SplayNode* s = succ(t); 478 if (y.seek(t->item) != 0) del(t->item); 479 t = s; 480 } 481 } 482} 483 484int <T>SplaySet::OK() 485{ 486 int v = 1; 487 if (root == 0) 488 v = count == 0; 489 else 490 { 491 int n = 1; 492 <T>SplayNode* trail = leftmost(); 493 <T>SplayNode* t = succ(trail); 494 while (t != 0) 495 { 496 ++n; 497 v &= <T>CMP(trail->item, t->item) < 0; 498 trail = t; 499 t = succ(t); 500 } 501 v &= n == count; 502 } 503 if (!v) error("invariant failure"); 504 return v; 505} 506