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>.SplayPQ.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>SplayPQ::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>SplayPQ::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>SplayPQ::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>SplayPQ::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>SplayPQ::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 195Pix <T>SplayPQ::enq(<T&> item) 196{ 197 ++count; 198 <T>SplayNode* newnode = new <T>SplayNode(item); 199 <T>SplayNode* t = root; 200 if (t == 0) 201 { 202 root = newnode; 203 return Pix(root); 204 } 205 206 int comp = <T>CMP(item, t->item); 207 208 <T>SplayNode* dummy = (<T>SplayNode*)(&_dummy_null); 209 <T>SplayNode* l = dummy; 210 <T>SplayNode* r = dummy; 211 dummy->rt = dummy->lt = dummy->par = 0; 212 213 int done = 0; 214 while (!done) 215 { 216 if (comp >= 0) 217 { 218 <T>SplayNode* tr = t->rt; 219 if (tr == 0) 220 { 221 tr = newnode; 222 comp = 0; done = 1; 223 } 224 else 225 comp = <T>CMP(item, tr->item); 226 227 if (comp <= 0) 228 { 229 l->rt = t; t->par = l; 230 l = t; 231 t = tr; 232 } 233 else 234 { 235 <T>SplayNode* trr = tr->rt; 236 if (trr == 0) 237 { 238 trr = newnode; 239 comp = 0; done = 1; 240 } 241 else 242 comp = <T>CMP(item, trr->item); 243 244 if ((t->rt = tr->lt) != 0) t->rt->par = t; 245 tr->lt = t; t->par = tr; 246 l->rt = tr; tr->par = l; 247 l = tr; 248 t = trr; 249 } 250 } 251 else 252 { 253 <T>SplayNode* tl = t->lt; 254 if (tl == 0) 255 { 256 tl = newnode; 257 comp = 0; done = 1; 258 } 259 else 260 comp = <T>CMP(item, tl->item); 261 262 if (comp >= 0) 263 { 264 r->lt = t; t->par = r; 265 r = t; 266 t = tl; 267 } 268 else 269 { 270 <T>SplayNode* tll = tl->lt; 271 if (tll == 0) 272 { 273 tll = newnode; 274 comp = 0; done = 1; 275 } 276 else 277 comp = <T>CMP(item, tll->item); 278 279 if ((t->lt = tl->rt) != 0) t->lt->par = t; 280 tl->rt = t; t->par = tl; 281 r->lt = tl; tl->par = r; 282 r = tl; 283 t = tll; 284 } 285 } 286 } 287 if ((r->lt = t->rt) != 0) r->lt->par = r; 288 if ((l->rt = t->lt) != 0) l->rt->par = l; 289 if ((t->lt = dummy->rt) != 0) t->lt->par = t; 290 if ((t->rt = dummy->lt) != 0) t->rt->par = t; 291 t->par = 0; 292 root = t; 293 return Pix(root); 294} 295 296 297void <T>SplayPQ::del(Pix pix) 298{ 299 <T>SplayNode* t = (<T>SplayNode*)pix; 300 if (t == 0) return; 301 302 <T>SplayNode* p = t->par; 303 304 --count; 305 if (t->rt == 0) 306 { 307 if (t == root) 308 { 309 if ((root = t->lt) != 0) root->par = 0; 310 } 311 else if (t == p->lt) 312 { 313 if ((p->lt = t->lt) != 0) p->lt->par = p; 314 } 315 else 316 if ((p->rt = t->lt) != 0) p->rt->par = p; 317 } 318 else 319 { 320 <T>SplayNode* r = t->rt; 321 <T>SplayNode* l = r->lt; 322 for(;;) 323 { 324 if (l == 0) 325 { 326 if (t == root) 327 { 328 root = r; 329 r->par = 0; 330 } 331 else if (t == p->lt) 332 { 333 p->lt = r; 334 r->par = p; 335 } 336 else 337 { 338 p->rt = r; 339 r->par = p; 340 } 341 if ((r->lt = t->lt) != 0) r->lt->par = r; 342 break; 343 } 344 else 345 { 346 if ((r->lt = l->rt) != 0) r->lt->par = r; 347 l->rt = r; r->par = l; 348 r = l; 349 l = l->lt; 350 } 351 } 352 } 353 delete t; 354} 355 356<T>& <T>SplayPQ::front() 357{ 358 if (root == 0) 359 error ("min: empty tree\n"); 360// else 361 { 362 <T>SplayNode* t = root; 363 <T>SplayNode* l = root->lt; 364 for(;;) 365 { 366 if (l == 0) 367 { 368 root = t; 369 root->par = 0; 370 return root->item; 371 } 372 else 373 { 374 if ((t->lt = l->rt) != 0) t->lt->par = t; 375 l->rt = t; t->par = l; 376 t = l; 377 l = l->lt; 378 } 379 } 380 } 381} 382 383void <T>SplayPQ::del_front() 384{ 385 if (root != 0) 386 { 387 --count; 388 <T>SplayNode* t = root; 389 <T>SplayNode* l = root->lt; 390 if (l == 0) 391 { 392 if ((root = t->rt) != 0) root->par = 0; 393 delete t; 394 } 395 else 396 { 397 for(;;) 398 { 399 <T>SplayNode* ll = l->lt; 400 if (ll == 0) 401 { 402 if ((t->lt = l->rt) != 0) t->lt->par = t; 403 delete l; 404 break; 405 } 406 else 407 { 408 <T>SplayNode* lll = ll->lt; 409 if (lll == 0) 410 { 411 if ((l->lt = ll->rt) != 0) l->lt->par = l; 412 delete ll; 413 break; 414 } 415 else 416 { 417 t->lt = ll; ll->par = t; 418 if ((l->lt = ll->rt) != 0) l->lt->par = l; 419 ll->rt = l; l->par = ll; 420 t = ll; 421 l = lll; 422 } 423 } 424 } 425 } 426 } 427} 428 429<T> <T>SplayPQ::deq() 430{ 431 if (root == 0) 432 error("deq: empty tree"); 433// else 434 { 435 --count; 436 <T>SplayNode* t = root; 437 <T>SplayNode* l = root->lt; 438 if (l == 0) 439 { 440 if ((root = t->rt) != 0) root->par = 0; 441 <T> res = t->item; 442 delete t; 443 return res; 444 } 445 else 446 { 447 for(;;) 448 { 449 <T>SplayNode* ll = l->lt; 450 if (ll == 0) 451 { 452 if ((t->lt = l->rt) != 0) t->lt->par = t; 453 <T> res = l->item; 454 delete l; 455 return res; 456 } 457 else 458 { 459 <T>SplayNode* lll = ll->lt; 460 if (lll == 0) 461 { 462 if ((l->lt = ll->rt) != 0) l->lt->par = l; 463 <T> res = ll->item; 464 delete ll; 465 return res; 466 } 467 else 468 { 469 t->lt = ll; ll->par = t; 470 if ((l->lt = ll->rt) != 0) l->lt->par = l; 471 ll->rt = l; l->par = ll; 472 t = ll; 473 l = lll; 474 } 475 } 476 } 477 } 478 } 479} 480 481 482void <T>SplayPQ::_kill(<T>SplayNode* t) 483{ 484 if (t != 0) 485 { 486 _kill(t->lt); 487 _kill(t->rt); 488 delete t; 489 } 490} 491 492 493<T>SplayNode* <T>SplayPQ::_copy(<T>SplayNode* t) 494{ 495 if (t != 0) 496 { 497 <T>SplayNode* l = _copy(t->lt); 498 <T>SplayNode* r = _copy(t->rt); 499 <T>SplayNode* x = new <T>SplayNode(t->item, l, r); 500 if (l != 0) l->par = x; 501 if (r != 0) r->par = x; 502 return x; 503 } 504 else 505 return 0; 506} 507 508int <T>SplayPQ::OK() 509{ 510 int v = 1; 511 if (root == 0) 512 v = count == 0; 513 else 514 { 515 int n = 1; 516 <T>SplayNode* trail = leftmost(); 517 <T>SplayNode* t = succ(trail); 518 while (t != 0) 519 { 520 ++n; 521 v &= <T>CMP(trail->item, t->item) < 0; 522 trail = t; 523 t = succ(t); 524 } 525 v &= n == count; 526 } 527 if (!v) error("invariant failure"); 528 return v; 529} 530