1# Paranoid::Data::AVLTree::AVLNode -- AVL Tree Node Object Class 2# 3# $Id: lib/Paranoid/Data/AVLTree/AVLNode.pm, 2.08 2020/12/31 12:10:06 acorliss Exp $ 4# 5# This software is free software. Similar to Perl, you can redistribute it 6# and/or modify it under the terms of either: 7# 8# a) the GNU General Public License 9# <https://www.gnu.org/licenses/gpl-1.0.html> as published by the 10# Free Software Foundation <http://www.fsf.org/>; either version 1 11# <https://www.gnu.org/licenses/gpl-1.0.html>, or any later version 12# <https://www.gnu.org/licenses/license-list.html#GNUGPL>, or 13# b) the Artistic License 2.0 14# <https://opensource.org/licenses/Artistic-2.0>, 15# 16# subject to the following additional term: No trademark rights to 17# "Paranoid" have been or are conveyed under any of the above licenses. 18# However, "Paranoid" may be used fairly to describe this unmodified 19# software, in good faith, but not as a trademark. 20# 21# (c) 2005 - 2020, Arthur Corliss (corliss@digitalmages.com) 22# (tm) 2008 - 2020, Paranoid Inc. (www.paranoid.com) 23# 24##################################################################### 25 26##################################################################### 27# 28# Environment definitions 29# 30##################################################################### 31 32package Paranoid::Data::AVLTree::AVLNode; 33 34use 5.008; 35 36use strict; 37use warnings; 38use vars qw($VERSION); 39use base qw(Exporter); 40use Paranoid; 41use Carp; 42 43($VERSION) = ( q$Revision: 2.08 $ =~ /(\d+(?:\.\d+)+)/sm ); 44 45use constant AVLKEY => 0; 46use constant AVLVAL => 1; 47use constant AVLRIGHT => 2; 48use constant AVLLEFT => 3; 49use constant AVLRHEIGHT => 4; 50use constant AVLLHEIGHT => 5; 51 52use constant AVLNHEADER => 'AVLNODE:v1:'; 53 54##################################################################### 55# 56# Module code follows 57# 58##################################################################### 59 60sub new { 61 62 # Purpose: Instantiates an AVLNode object 63 # Returns: Object reference if successful, undef otherwise 64 # Usage: $obj = Paranoid::Data::AVLTree::AVLNode->new( 65 # $key, $val 66 # ); 67 68 my $class = shift; 69 my $key = shift; 70 my $val = shift; 71 my $self = []; 72 73 bless $self, $class; 74 if ( defined $key and length $key ) { 75 $$self[AVLKEY] = $key; 76 $$self[AVLVAL] = $val; 77 $$self[AVLRHEIGHT] = 0; 78 $$self[AVLLHEIGHT] = 0; 79 } else { 80 $self = undef; 81 } 82 83 return $self; 84} 85 86sub ioRecord { 87 88 # Purpose: Returns a string record representation of the node 89 # Returns: String 90 # Usage: $record = $obj->ioRecord; 91 92 my $self = shift; 93 my $rv = AVLNHEADER; 94 my ( $ksize, $vsize ); 95 96 { 97 use bytes; 98 $ksize = length $$self[AVLKEY]; 99 $vsize = defined $$self[AVLVAL] ? length $$self[AVLVAL] : -1; 100 } 101 102 $rv .= "$ksize:$vsize:"; 103 $rv .= $$self[AVLKEY]; 104 $rv .= $$self[AVLVAL] if defined $$self[AVLVAL]; 105 106 return $rv; 107} 108 109sub key { 110 111 # Purpose: Returns the node key 112 # Returns: String 113 # Usage: $key = $obj->key; 114 115 my $self = shift; 116 return $$self[AVLKEY]; 117} 118 119sub val { 120 121 # Purpose: Returns the node value 122 # Returns: Scalar/undef 123 # Usage: $val = $node->val; 124 125 my $self = shift; 126 return $$self[AVLVAL]; 127} 128 129sub setVal { 130 131 # Purpose: Sets the node value 132 # Returns: Boolean 133 # Usage: $rv = $obj->setVal($val); 134 135 my $self = shift; 136 my $val = shift; 137 138 $$self[AVLVAL] = $val; 139 140 return 1; 141} 142 143sub right { 144 145 # Purpose: Returns the right-side node reference 146 # Returns: AVLNode ref/undef 147 # Usage: $ref = $obj->right; 148 149 my $self = shift; 150 return $$self[AVLRIGHT]; 151} 152 153sub setRight { 154 155 # Purpose: Sets the right-side node reference 156 # Returns: Boolean 157 # Usage: $rv = $obj->setRight($node); 158 159 my $self = shift; 160 my $val = shift; 161 162 $$self[AVLRIGHT] = $val; 163 $$self[AVLRHEIGHT] = defined $val ? $val->height : 0; 164 165 return 1; 166} 167 168sub left { 169 170 # Purpose: Returns the left-side node reference 171 # Returns: AVLNode ref/undef 172 # Usage: $ref = $obj->left; 173 174 my $self = shift; 175 return $$self[AVLLEFT]; 176} 177 178sub setLeft { 179 180 # Purpose: Sets the left-side node reference 181 # Returns: Boolean 182 # Usage: $rv = $obj->setLeft($node); 183 184 my $self = shift; 185 my $val = shift; 186 187 $$self[AVLLEFT] = $val; 188 $$self[AVLLHEIGHT] = defined $val ? $val->height : 0; 189 190 return 1; 191} 192 193sub incrRHeight { 194 195 # Purpose: Increments the right-side branch height 196 # Returns: Boolean 197 # Usage: $rv = $obj->incrRHeight; 198 199 my $self = shift; 200 201 $$self[AVLRHEIGHT]++; 202 203 return 1; 204} 205 206sub incrLHeight { 207 208 # Purpose: Increments the left-side branch height 209 # Returns: Boolean 210 # Usage: $rv = $obj->incrLHeight; 211 212 my $self = shift; 213 214 $$self[AVLLHEIGHT]++; 215 216 return 1; 217} 218 219sub addRHeight { 220 221 # Purpose: Adds the passed value to the right-side height 222 # Returns: Boolean 223 # Usage: $rv = $obj->addRHeight($n); 224 225 my $self = shift; 226 my $n = shift; 227 228 $$self[AVLRHEIGHT] += $n; 229 230 return 1; 231} 232 233sub addLHeight { 234 235 # Purpose: Adds the passed value to the left-side height 236 # Returns: Boolean 237 # Usage: $rv = $obj->addLHeight($n); 238 239 my $self = shift; 240 my $n = shift; 241 242 $$self[AVLLHEIGHT] += $n; 243 244 return 1; 245} 246 247sub decrRHeight { 248 249 # Purpose: Decrements the right-side branch height 250 # Returns: Boolean 251 # Usage: $rv = $obj->decrRHeight; 252 253 my $self = shift; 254 255 $$self[AVLRHEIGHT]--; 256 257 return 1; 258} 259 260sub decrLHeight { 261 262 # Purpose: Decrements the left-side branch height 263 # Returns: Boolean 264 # Usage: $rv = $obj->decrLHeight; 265 266 my $self = shift; 267 268 $$self[AVLLHEIGHT]--; 269 270 return 1; 271} 272 273sub balance { 274 275 # Purpose: Returns the current balance of right/left-side branch heights 276 # Returns: Integer 277 # Usage: $balance = $obj->balance; 278 279 my $self = shift; 280 281 return $$self[AVLRHEIGHT] - $$self[AVLLHEIGHT]; 282} 283 284sub count { 285 286 # Purpose: Returns the count of nodes from this node and its sub-branches 287 # Returns: Integer 288 # Usage: $count = $obj->count; 289 290 my $self = shift; 291 my $rv = 1; 292 293 $rv += $$self[AVLRIGHT]->count if defined $$self[AVLRIGHT]; 294 $rv += $$self[AVLLEFT]->count if defined $$self[AVLLEFT]; 295 296 return $rv; 297} 298 299sub height { 300 301 # Purpose: Returns the height of this node and its longest sub-branch 302 # Returns: Integer 303 # Usage: $height = $obj->height; 304 305 my $self = shift; 306 307 return 1 + ( 308 $$self[AVLRHEIGHT] > $$self[AVLLHEIGHT] 309 ? $$self[AVLRHEIGHT] 310 : $$self[AVLLHEIGHT] ); 311} 312 313sub rHeight { 314 315 # Purpose: Returns the height of the right-side sub-branch 316 # Returns: Integer 317 # Usage: $height = $obj->rHeight; 318 319 my $self = shift; 320 321 return $$self[AVLRHEIGHT]; 322} 323 324sub lHeight { 325 326 # Purpose: Returns the height of the left-side sub-branch 327 # Returns: Integer 328 # Usage: $height = $obj->lHeight; 329 330 my $self = shift; 331 332 return $$self[AVLLHEIGHT]; 333} 334 335sub updtHeights { 336 337 # Purpose: Brute force method of recalculating all sub-branch heights 338 # Returns: Boolean 339 # Usage: $rv = $obj->updtHeights; 340 341 my $self = shift; 342 343 $$self[AVLRHEIGHT] = 344 defined $$self[AVLRIGHT] 345 ? $$self[AVLRIGHT]->height 346 : 0; 347 $$self[AVLLHEIGHT] = 348 defined $$self[AVLLEFT] ? $$self[AVLLEFT]->height : 0; 349 350 return 1; 351} 352 353sub children { 354 355 # Purpose: Returns all nodes linked to from this node 356 # Returns: Array of AVLNode refs 357 # Usage: @crefs = $obj->children; 358 359 my $self = shift; 360 my @rv; 361 362 push @rv, $$self[AVLRIGHT] if defined $$self[AVLRIGHT]; 363 push @rv, $$self[AVLLEFT] if defined $$self[AVLLEFT]; 364 365 return @rv; 366} 367 3681; 369 370__END__ 371 372=head1 NAME 373 374Paranoid::Data::AVLTree::AVLNode - AVL Tree Node Object Class 375 376=head1 VERSION 377 378$Id: lib/Paranoid/Data/AVLTree/AVLNode.pm, 2.08 2020/12/31 12:10:06 acorliss Exp $ 379 380=head1 SYNOPSIS 381 382 $node = Paranoid::Data::AVLTree::AVLNode->new($key, $val); 383 $record = $node->ioRecord; 384 $key = $node->key; 385 $val = $node->val; 386 $rv = $node->setVal($val); 387 $ref = $node->right; 388 $rv = $node->setRight($node); 389 $ref = $node->left; 390 $rv = $node->setLeft($node); 391 $rv = $node->incrRHeight; 392 $rv = $node->incrLHeight; 393 $rv = $node->addRHeight($n); 394 $rv = $node->addLHeight($n); 395 $rv = $node->decrRHeight; 396 $rv = $node->decrLHeight; 397 $balance = $node->balance; 398 $count = $node->count; 399 $height = $node->height; 400 $height = $node->rHeight; 401 $height = $node->lHeight; 402 $rv = $node->updtHeights; 403 @crefs = $node->children; 404 405=head1 DESCRIPTION 406 407This class provides the core data objects that comprise an AVL-balanced tree. 408 409=head1 SUBROUTINES/METHODS 410 411=head2 new 412 413 $node = Paranoid::Data::AVLTree::AVLNode->new($key, $val); 414 415This method creates a new AVLNode object. Like hashes, the key must be 416defined, but it cannot be a zero-length string. In those cases, this method 417will return undef. 418 419=head2 ioRecord 420 421 $record = $node->ioRecord; 422 423This method creates a string representation of the node for use in spooling to 424disk. 425 426=head2 key 427 428 $key = $node->key; 429 430This method returns the key for the node. 431 432=head2 val 433 434 $val = $node->val; 435 436This method returns the associated value for the node. It can be undef. 437 438=head2 setVal 439 440 $rv = $node->setVal($val); 441 442This method sets the assocated value for the node. 443 444=head2 right 445 446 $ref = $node->right; 447 448This method retrieves a reference to the next right-side node in the branch, 449if any. 450 451=head2 setRight 452 453 $rv = $node->setRight($node); 454 455This method sets/removes the reference to the next right-side node in the branch. 456 457=head2 left 458 459 $ref = $node->left; 460 461This method retrieves a reference to the next left-side node in the branch, 462if any. 463 464=head2 setLeft 465 466 $rv = $node->setLeft($node); 467 468This method sets/removes the reference to the next left-side node in the branch. 469 470=head2 incrRHeight 471 472 $rv = $node->incrRHeight; 473 474This method increments the height counter for the ride-side sub-branch. 475 476=head2 incrLHeight 477 478 $rv = $node->incrLHeight; 479 480This method increments the height counter for the left-side sub-branch. 481 482=head2 addRHeight 483 484 $rv = $node->addRHeight($n); 485 486This method adds the passed value to the height counter for the right-side 487sub-branch. 488 489=head2 addLHeight 490 491 $rv = $node->addLHeight($n); 492 493This method adds the passed value to the height counter for the left-side 494sub-branch. 495 496=head2 decrRHeight 497 498 $rv = $node->decrRHeight; 499 500This method decrements the height counter for the right-side sub-branch. 501 502=head2 decrLHeight 503 504 $rv = $node->decrLHeight; 505 506This method decrements the height counter for the left-side sub-branch. 507 508=head2 balance 509 510 $balance = $node->balance; 511 512This returns the node balance, which is a relative indidcator of the disparity 513in heights of the right & left sub-branches. A negative number denotes a 514longer left-side branch, zero means equal sub-branch heights, and a positive 515integer denotes a longer right-side branch. 516 517=head2 count 518 519 $count = $node->count; 520 521This method returns the count of nodes, including all nodes in linked 522sub-branches. 523 524=head2 height 525 526 $height = $node->height; 527 528This method returns the longest height of the node and any attached 529sub-branches. 530 531=head2 rHeight 532 533 $height = $node->rHeight; 534 535This method returns the height of the right-side sub-branch, or zero if there 536is no linked branch. 537 538=head2 lHeight 539 540 $height = $node->lHeight; 541 542This method returns the height of the left-side sub-branch, or zero if there 543is no linked branch. 544 545=head2 updtHeights 546 547 $rv = $node->updtHeights; 548 549This method performs a brute force recalculation of all attached sub-branches. 550 551=head2 children 552 553 @crefs = $node->children; 554 555This returns references to the next nodes in any attadhed sub-branches. 556 557=head1 DEPENDENCIES 558 559=over 560 561=item o 562 563L<Carp> 564 565=item o 566 567L<Paranoid> 568 569=back 570 571=head1 BUGS AND LIMITATIONS 572 573=head1 AUTHOR 574 575Arthur Corliss (corliss@digitalmages.com) 576 577=head1 LICENSE AND COPYRIGHT 578 579This software is free software. Similar to Perl, you can redistribute it 580and/or modify it under the terms of either: 581 582 a) the GNU General Public License 583 <https://www.gnu.org/licenses/gpl-1.0.html> as published by the 584 Free Software Foundation <http://www.fsf.org/>; either version 1 585 <https://www.gnu.org/licenses/gpl-1.0.html>, or any later version 586 <https://www.gnu.org/licenses/license-list.html#GNUGPL>, or 587 b) the Artistic License 2.0 588 <https://opensource.org/licenses/Artistic-2.0>, 589 590subject to the following additional term: No trademark rights to 591"Paranoid" have been or are conveyed under any of the above licenses. 592However, "Paranoid" may be used fairly to describe this unmodified 593software, in good faith, but not as a trademark. 594 595(c) 2005 - 2020, Arthur Corliss (corliss@digitalmages.com) 596(tm) 2008 - 2020, Paranoid Inc. (www.paranoid.com) 597 598