6 #include <rudiments/stdio.h> 7 #include <rudiments/private/rudimentsinlines.h> 8 #include <rudiments/private/nodeinlines.h> 10 #define AVLTREE_TEMPLATE template <class valuetype> 12 #define AVLTREE_CLASS avltree<valuetype> 14 #define AVLTREENODE_TEMPLATE template <class valuetype> 16 #define AVLTREENODE_CLASS avltreenode<valuetype> 19 RUDIMENTS_TEMPLATE_INLINE
20 AVLTREE_CLASS::avltree() {
28 RUDIMENTS_TEMPLATE_INLINE
29 AVLTREE_CLASS::~avltree() {
34 RUDIMENTS_TEMPLATE_INLINE
35 void AVLTREE_CLASS::insert(valuetype value) {
40 RUDIMENTS_TEMPLATE_INLINE
49 stdoutput.
printf(
"----------------------------------------" 50 "---------------------------------------\n");
56 top->insert(node,&top);
60 first->getLeftChild();
61 first=first->getLeftChild()) {}
65 last->getRightChild();
66 last=last->getRightChild()) {}
81 RUDIMENTS_TEMPLATE_INLINE
90 stdoutput.
printf(
"----------------------------------------" 91 "---------------------------------------\n");
114 RUDIMENTS_TEMPLATE_INLINE
115 bool AVLTREE_CLASS::remove(valuetype value) {
117 return (current)?
remove(current):
false;
121 RUDIMENTS_TEMPLATE_INLINE
122 bool AVLTREE_CLASS::removeAll(valuetype value) {
124 while (
remove(value)) {
131 RUDIMENTS_TEMPLATE_INLINE
138 RUDIMENTS_TEMPLATE_INLINE
139 uint64_t AVLTREE_CLASS::getLength()
const {
144 RUDIMENTS_TEMPLATE_INLINE
150 RUDIMENTS_TEMPLATE_INLINE
156 RUDIMENTS_TEMPLATE_INLINE
162 RUDIMENTS_TEMPLATE_INLINE
169 RUDIMENTS_TEMPLATE_INLINE
172 return (node)?node->
getNext():NULL;
176 RUDIMENTS_TEMPLATE_INLINE
182 RUDIMENTS_TEMPLATE_INLINE
188 stdoutput.
printf(
"find ");
190 stdoutput.
printf(
" from ");
194 node_print(
"(null)");
203 int32_t result=current->
compare(value);
208 stdoutput.
printf(
" - %d\n",result);
213 }
else if (result==0) {
215 }
else if (result>0) {
222 stdoutput.
printf(
" success!\n");
224 stdoutput.
printf(
" failed\n");
226 stdoutput.
printf(
"} find\n\n");
233 RUDIMENTS_TEMPLATE_INLINE
234 void AVLTREE_CLASS::clear() {
238 stdoutput.
printf(
"clearing %d nodes {\n",length);
242 AVLTREENODE_CLASS *node=top;
246 if (node->getRightChild()) {
247 node=node->getRightChild();
249 while (node->getLeftChild()) {
250 node=node->getLeftChild();
254 AVLTREENODE_CLASS *p=node->getParent();
256 if (p->getLeftChild()==node) {
257 p->setLeftChild(NULL);
259 p->setRightChild(NULL);
265 stdoutput.
printf(
" clearing %lld\n",i);
280 stdoutput.
printf(
"} cleared %d nodes\n\n",i);
291 RUDIMENTS_TEMPLATE_INLINE
292 void AVLTREE_CLASS::print()
const {
299 RUDIMENTS_TEMPLATE_INLINE
300 AVLTREENODE_CLASS::avltreenode(valuetype value) {
310 RUDIMENTS_TEMPLATE_INLINE
311 AVLTREENODE_CLASS::~avltreenode() {
315 RUDIMENTS_TEMPLATE_INLINE
316 void AVLTREENODE_CLASS::setValue(valuetype value) {
321 RUDIMENTS_TEMPLATE_INLINE
322 valuetype AVLTREENODE_CLASS::getValue()
const {
327 RUDIMENTS_TEMPLATE_INLINE
328 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getParent() {
333 RUDIMENTS_TEMPLATE_INLINE
334 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getLeftChild() {
339 RUDIMENTS_TEMPLATE_INLINE
340 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getRightChild() {
345 RUDIMENTS_TEMPLATE_INLINE
346 uint8_t AVLTREENODE_CLASS::getLeftHeight() {
351 RUDIMENTS_TEMPLATE_INLINE
352 uint8_t AVLTREENODE_CLASS::getRightHeight() {
357 RUDIMENTS_TEMPLATE_INLINE
358 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getPrevious() {
368 AVLTREENODE_CLASS *node=left;
371 while (node->right) {
380 if (parent->right==
this) {
387 AVLTREENODE_CLASS *node=parent;
392 if (node->parent->right==node) {
402 RUDIMENTS_TEMPLATE_INLINE
403 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getNext() {
413 AVLTREENODE_CLASS *node=right;
425 if (parent->left==
this) {
432 AVLTREENODE_CLASS *node=parent;
437 if (node->parent->left==node) {
447 RUDIMENTS_TEMPLATE_INLINE
448 int32_t AVLTREENODE_CLASS::compare(valuetype value)
const {
449 return node_compare(this->value,value);
453 RUDIMENTS_TEMPLATE_INLINE
455 return node_compare(this->value,peer->value);
459 RUDIMENTS_TEMPLATE_INLINE
460 void AVLTREENODE_CLASS::print()
const {
461 uint16_t indentlevel=0;
462 print(
"top",&indentlevel);
466 RUDIMENTS_TEMPLATE_INLINE
467 void AVLTREENODE_CLASS::print(
const char *name, uint16_t *indentlevel)
const {
469 for (uint16_t i=0; i<*indentlevel; i++) {
472 stdoutput.
printf(
"<%s value=\"",name);
474 stdoutput.
printf(
"\" lh=\"%d\" rh=\"%d\" bf=\"%d\"",
475 leftheight,rightheight,leftheight-rightheight);
476 if (!left && !right) {
482 left->print(
"left ",indentlevel);
485 right->print(
"right",indentlevel);
488 for (uint16_t i=0; i<*indentlevel; i++) {
491 stdoutput.
printf(
"</%s>\n",name);
496 RUDIMENTS_TEMPLATE_INLINE
497 void AVLTREENODE_CLASS::setParent(AVLTREENODE_CLASS *node) {
502 RUDIMENTS_TEMPLATE_INLINE
503 void AVLTREENODE_CLASS::setLeftChild(AVLTREENODE_CLASS *node) {
508 RUDIMENTS_TEMPLATE_INLINE
509 void AVLTREENODE_CLASS::setRightChild(AVLTREENODE_CLASS *node) {
514 RUDIMENTS_TEMPLATE_INLINE
527 if (node->
compare(location->value)<=0) {
529 if (location->left) {
530 location=location->left;
534 stdoutput.
printf(
"insert ");
535 node_print(node->value);
536 stdoutput.
printf(
" to left of ");
537 node_print(location->value);
538 stdoutput.
printf(
" {\n\n");
541 location->setLeftChild(node);
545 }
else if (node->
compare(location->value)>0) {
547 if (location->right) {
548 location=location->right;
552 stdoutput.
printf(
"insert ");
553 node_print(node->value);
554 stdoutput.
printf(
" to right of ");
555 node_print(location->value);
556 stdoutput.
printf(
" {\n\n");
559 location->setRightChild(node);
565 node->setParent(location);
568 adjustParentHeights(node);
571 node->parent->balance(treetop);
574 stdoutput.
printf(
"} insert\n\n");
579 RUDIMENTS_TEMPLATE_INLINE
583 stdoutput.
printf(
"detach ");
585 stdoutput.
printf(
" {\n\n");
588 while (top->parent) { top=top->parent; }
597 stdoutput.
printf(
"less simple case: 2 children\n\n");
609 while (successor->left) {
610 successor=successor->left;
614 stdoutput.
printf(
"swap ");
616 stdoutput.
printf(
" and ");
617 node_print(successor->value);
624 bool successorwasimmediaterightchild=(right==successor);
633 successor->parent=parent;
634 if (successor->parent) {
635 if (successor->parent->left==
this) {
636 successor->parent->left=successor;
638 successor->parent->right=successor;
646 successor->left=left;
647 if (successor->left) {
648 successor->left->parent=successor;
650 if (successorwasimmediaterightchild) {
651 successor->right=
this;
652 successor->right->parent=successor;
654 successor->right=right;
655 if (successor->right) {
656 successor->right->parent=successor;
661 if (parent->left==successor) {
670 successor->leftheight=leftheight;
671 successor->rightheight=rightheight;
687 leftheight=temp.leftheight;
688 rightheight=temp.rightheight;
692 while (top->parent) { top=top->parent; }
703 stdoutput.
printf(
"simple case: 1 or 0 children\n\n");
721 if (parent->left==
this) {
723 parent->leftheight--;
726 parent->rightheight--;
731 child->parent=parent;
741 adjustParentHeights(p);
764 while (top->parent) { top=top->parent; }
770 stdoutput.
printf(
"} detach\n\n");
775 RUDIMENTS_TEMPLATE_INLINE
779 while (node->parent) {
782 uint8_t height=((node->leftheight>node->rightheight)?
784 node->rightheight)+1;
792 if (node->parent->left==node) {
793 if (node->parent->leftheight==height) {
796 node->parent->leftheight=height;
798 if (node->parent->rightheight==height) {
801 node->parent->rightheight=height;
810 RUDIMENTS_TEMPLATE_INLINE
816 stdoutput.
printf(
"balance at ");
818 stdoutput.
printf(
" {\n\n");
821 while (top->parent) { top=top->parent; }
831 if ((node->leftheight>node->rightheight &&
832 node->leftheight-node->rightheight>1) ||
833 (node->rightheight>node->leftheight &&
834 node->rightheight-node->leftheight>1)) {
837 stdoutput.
printf(
"imbalance at ");
838 node_print(node->value);
845 if (node->rightheight>node->leftheight) {
846 if (node->right->rightheight>
847 node->right->leftheight) {
848 node=node->leftRotate(treetop);
850 node=node->rightLeftRotate(treetop);
852 }
else if (node->leftheight>node->rightheight) {
853 if (node->left->leftheight>
854 node->left->rightheight) {
855 node=node->rightRotate(treetop);
857 node=node->leftRightRotate(treetop);
863 while (top->parent) { top=top->parent; }
870 stdoutput.
printf(
"no imbalance at ");
871 node_print(node->value);
882 stdoutput.
printf(
"continuing at ");
883 node_print(node->value);
891 stdoutput.
printf(
"} balance\n\n");
896 RUDIMENTS_TEMPLATE_INLINE
913 stdoutput.
printf(
"left rotation at ");
922 uint8_t starheight=b->leftheight;
934 stdoutput.
printf(
"(new tree top)\n\n");
944 a->rightheight=starheight;
952 adjustParentHeights(a);
961 RUDIMENTS_TEMPLATE_INLINE
979 stdoutput.
printf(
"right-left rotation at ");
981 stdoutput.
printf(
" {\n\n");
982 stdoutput.
printf(
"right part\n\n");
992 uint8_t starheight=b->rightheight;
1002 c->leftheight=starheight;
1010 adjustParentHeights(c);
1012 #ifdef DEBUG_AVLTREE 1014 while (top->parent) { top=top->parent; }
1019 leftRotate(treetop);
1021 #ifdef DEBUG_AVLTREE 1022 stdoutput.
printf(
"} right-left\n\n");
1032 RUDIMENTS_TEMPLATE_INLINE
1048 #ifdef DEBUG_AVLTREE 1049 stdoutput.
printf(
"right rotation at ");
1051 stdoutput.
printf(
"\n\n");
1058 uint8_t starheight=b->rightheight;
1069 #ifdef DEBUG_AVLTREE 1070 stdoutput.
printf(
"(new tree top)\n\n");
1074 b->parent=c->parent;
1080 c->leftheight=starheight;
1088 adjustParentHeights(c);
1097 RUDIMENTS_TEMPLATE_INLINE
1114 #ifdef DEBUG_AVLTREE 1115 stdoutput.
printf(
"left-right rotation at ");
1117 stdoutput.
printf(
" {\n\n");
1118 stdoutput.
printf(
"left part\n\n");
1128 uint8_t starheight=b->leftheight;
1138 a->rightheight=starheight;
1146 adjustParentHeights(a);
1148 #ifdef DEBUG_AVLTREE 1150 while (top->parent) { top=top->parent; }
1155 rightRotate(treetop);
1157 #ifdef DEBUG_AVLTREE 1158 stdoutput.
printf(
"} left-right\n\n");
avltreenode< valuetype > * getNext()
avltreenode< valuetype > * getLeftChild()
size_t printf(const char *format,...)
valuetype getValue() const
avltreenode< valuetype > * getPrevious()
avltreenode< valuetype > * getRightChild()
int32_t compare(valuetype value) const