N-sim
Emulation and simulation of
Wireless Sensor Networks



   Home


   Project Page


   Download


   CVS



   Installation


   Configuration


   Plug-ins




 Hosted by
SourceForge.net Logo

/home/brennan/n-sim/OrbisQuartus/shared/avl.h

Go to the documentation of this file.
00001 
00014 /*
00015  * Copyright 2007. Los Alamos National Security, LLC. This material
00016  * was produced under U.S. Government contract DE-AC52-06NA25396 for
00017  * Los Alamos National Laboratory (LANL), which is operated by Los
00018  * Alamos National Security, LLC, for the Department of Energy. The
00019  * U.S. Government has rights to use, reproduce, and distribute this
00020  * software. NEITHER THE GOVERNMENT NOR LOS ALAMOS NATIONAL SECURITY,
00021  * LLC, MAKES ANY WARRANTY, EXPRESS OR IMPLIED, OR ASSUMES ANY LEGAL
00022  * LIABILITY FOR THE USE OF THIS SOFTWARE. If software is modified to
00023  * produce derivative works, such modified software should be clearly
00024  * marked, so as not to confuse it with the version available from LANL.
00025  *
00026  * Additionally, this program is free software; you can redistribute
00027  * it and/or modify it under the terms of the GNU General Public
00028  * License as published by the Free Software Foundation; version 2 of
00029  * the License. Accordingly, this program is distributed in the hope
00030  * it will be useful, but WITHOUT ANY WARRANTY; without even the
00031  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00032  * PURPOSE. See the GNU General Public License for more details.
00033  */
00034 
00035 
00036 #ifndef _AVL_H_
00037 #define _AVL_H_
00038 
00039 #include "comparable.h"
00040 
00041 
00042 template <class Key>
00043 class AVL_tree;
00044 
00045 template <class Key>
00046 class AVL_node {
00047         Comparable<Key> *element;
00048         AVL_node<Key> *left, *right;
00049         AVL_node<Key> *next, *prev;
00050         unsigned int height;
00051 
00052         friend class AVL_tree<Key>;
00053 
00054  public:
00055         inline AVL_node() { element = 0; left = right = prev = next = 0; };
00056         inline AVL_node(Comparable<Key> *e) { 
00057                 element = e;
00058                 left = right = prev = next = 0;
00059         };
00060         inline ~AVL_node() { 
00061                 if (left != 0) delete left;
00062                 if (right != 0) delete right;
00063         };
00064 
00065         inline Comparable<Key> *elt() { return element; };
00066         inline AVL_node *get_next() { return next; };
00067         inline unsigned int get_height() { return height; };
00068 };
00069 
00070 
00071 template <class Key>
00072 class AVL_tree {
00073         AVL_node<Key> *root;
00074         unsigned int tree_size;
00075 
00076         int _get_height(AVL_node<Key> *node);
00077         AVL_node<Key> *_rotate(AVL_node<Key> *node, int direction);
00078         AVL_node<Key> *_double_rotate(AVL_node<Key> *node, int direction);
00079         AVL_node<Key> *__avl_ins(Comparable<Key> *elt, Key key, 
00080                                  AVL_node<Key> *tree, AVL_node<Key> *parent,
00081                                  int direction, int *error);
00082         AVL_node<Key> *__avl_del(Comparable<Key> *elt, Key key,
00083                                  AVL_node<Key> *tree, AVL_node<Key> *parent,
00084                                  int direction, int *error);
00085         void __avl_print(AVL_node<Key> *tree, int direction, int indent);
00086 
00087  public:
00088         inline AVL_tree() { root = 0; };
00089         ~AVL_tree();
00090 
00091         unsigned int get_size();
00092         inline unsigned long get_height() { return root->height; };
00093         AVL_node<Key> *find(Comparable<Key> key);
00094         Comparable<Key> *retrieve(Comparable<Key> key);
00095         AVL_node<Key> *find_min();
00096         AVL_node<Key> *find_max();
00097         int insert_elt(Comparable<Key> *elt);
00098         int delete_elt(Comparable<Key> *elt);
00099 
00100         void print();
00101         void print_list();
00102 
00103 
00104         inline void defoliate() { if (root != 0) delete root; };
00105         void burn() { 
00106                 while (find_min() != 0) {
00107                         AVL_node<Key> *list = find_min();
00108                         Comparable<Key> *elt = list->elt();
00109                         delete_elt(elt);
00110                         if (elt != 0)
00111                                 delete elt;
00112                 }
00113         };
00114 };
00115 
00116 
00117 /****************************************************
00118  * template implementation must be in the same file *
00119  ****************************************************/
00120 
00121 enum { LEFT = 0, RIGHT = 1 };
00122 
00123 
00124 static inline int _maximum(int a, int b)
00125 {
00126         return a > b ? a : b;
00127 }
00128 
00129 template <class Key>
00130 inline int AVL_tree<Key>::_get_height(AVL_node<Key> *node)
00131 {
00132         if (node == 0)
00133                 return 0;
00134         return node->get_height();
00135 }
00136 
00137 
00138 template <class Key>
00139 AVL_tree<Key>::~AVL_tree()
00140 { 
00141         AVL_node<Key> *min;
00142         while ((min = find_min()) != 0) {
00143                 Comparable<Key> *me = min->element;
00144                 delete_elt(me);
00145                 delete me;
00146         }
00147 }
00148 
00149 
00150 template <class Key>
00151 AVL_node<Key> *AVL_tree<Key>::_rotate(AVL_node<Key> *node, int direction)
00152 {
00153         AVL_node<Key> *child;
00154         if (node == 0)
00155                 return 0;
00156 
00157         if (direction == LEFT) {
00158                 child = node->right;
00159                 node->right = child->left;
00160                 child->left = node;
00161         } else {
00162                 child = node->left;
00163                 node->left = child->right;
00164                 child->right = node;
00165         }
00166 
00167         node->height = 1 + _maximum(_get_height(node->left), 
00168                                     _get_height(node->right));
00169         child->height = 1 + _maximum(_get_height(child->left), 
00170                                      _get_height(child->right));
00171 
00172         return child;
00173 }
00174 
00175 
00176 template <class Key>
00177 AVL_node<Key> *AVL_tree<Key>::_double_rotate(AVL_node<Key> *node,
00178                                              int direction)
00179 {
00180         AVL_node<Key> *child, *parent;
00181         if (node == 0)
00182                 return 0;
00183 
00184         if (direction == LEFT) {
00185                 child = node->right;
00186                 parent = child->left;
00187                 child->left = parent->right;
00188                 parent->right = child;
00189                 node->right = parent->left;
00190                 parent->left = node;
00191         } else {
00192                 child = node->left;
00193                 parent = child->right;
00194                 child->right = parent->left;
00195                 parent->left = child;
00196                 node->left = parent->right;
00197                 parent->right = node;
00198         }
00199         parent->height = 1 + _maximum(_get_height(parent->left),
00200                                       _get_height(parent->right));
00201         node->height = 1 + _maximum(_get_height(node->left),
00202                                     _get_height(node->right));
00203         child->height = 1 + _maximum(_get_height(child->left),
00204                                      _get_height(child->right));
00205         return parent;
00206 }
00207 
00208 
00209 
00210 
00211 template <class Key>
00212 unsigned int AVL_tree<Key>::get_size()
00213 {
00214         unsigned int i = 0;
00215         AVL_node<Key> *list = find_min();
00216 
00217         if (list == 0)
00218                 return 0;
00219 
00220         for (; list != 0; list = list->next)
00221                 i++;
00222 
00223         return i;
00224 }
00225 
00226 
00227 template <class Key>
00228 AVL_node<Key> *AVL_tree<Key>::find(Comparable<Key> key)
00229 {
00230         int i = 0;
00231         AVL_node<Key> *node;
00232 
00233         node = root;
00234 
00235         while (node != 0) {
00236                 if (key == *node->element)
00237                         break;
00238                 if (key < *node->element)
00239                         node = node->left;
00240                 else if (key > *node->element)
00241                         node = node->right;
00242                 i++;
00243         }
00244         return node;
00245 }
00246 
00247 
00248 template <class Key>
00249 Comparable<Key> *AVL_tree<Key>::retrieve(Comparable<Key> key)
00250 {
00251         AVL_node<Key> *node;
00252         if ((node = find(key)) == 0)
00253                 return 0;
00254         return node->element;
00255 }
00256 
00257 
00258 template <class Key>
00259 AVL_node<Key> *AVL_tree<Key>::find_min()
00260 {
00261         AVL_node<Key> *node;
00262 
00263         node = root;
00264         if (node == 0)
00265                 return 0;
00266 
00267         while (node->left != 0)
00268                 node = node->left;
00269 
00270         return node;
00271 }
00272 
00273 
00274 template <class Key>
00275 AVL_node<Key> *AVL_tree<Key>::find_max()
00276 {
00277         AVL_node<Key> *node;
00278 
00279         node = root;
00280         if (node == 0)
00281                 return 0;
00282 
00283         while (node->right != 0)
00284                 node = node->right;
00285 
00286         return node;
00287 }
00288 
00289 
00290 
00291 template <class Key>
00292 AVL_node<Key> *AVL_tree<Key>::__avl_ins(Comparable<Key> *elt, Key key,
00293                                    AVL_node<Key> *tree, AVL_node<Key> *parent,
00294                                    int direction, int *error)
00295 {
00296         if (tree == 0) {
00297                 tree = new AVL_node<Key>(elt);
00298                 if (tree == 0) {
00299                         *error = 1;
00300                         return 0;
00301                 }
00302 
00303                 if (direction == LEFT) {
00304                         tree->next = parent;
00305                         tree->prev = parent->prev;
00306                         if (parent->prev != 0)
00307                                 parent->prev->next = tree;
00308                         parent->prev = tree;
00309                 } else if (direction == RIGHT) {
00310                         tree->next = parent->next;
00311                         tree->prev = parent;
00312                         if (parent->next != 0)
00313                                 parent->next->prev = tree;
00314                         parent->next = tree;
00315                 } else {
00316                         tree->next = tree->prev = 0;
00317                 }
00318         } else if (key < tree->element->key) {
00319                 tree->left = __avl_ins(elt, key, tree->left, tree, 
00320                                        LEFT, error);
00321 
00322                 if (_get_height(tree->left) - _get_height(tree->right) >= 2) {
00323                         if (_get_height(tree->left->left) - 
00324                             _get_height(tree->left->right) >= 1)
00325                                 tree = _rotate(tree, RIGHT);
00326                         else if (_get_height(tree->left->right) - 
00327                                  _get_height(tree->left->left) >= 1)
00328                                 tree = _double_rotate(tree, RIGHT);
00329                 }
00330         } else if (key > tree->element->key) {
00331                 tree->right = __avl_ins(elt, key, tree->right, tree, 
00332                                         RIGHT, error);
00333                 if (_get_height(tree->right) - _get_height(tree->left) >= 2) {
00334                         if (_get_height(tree->right->right) - 
00335                             _get_height(tree->right->left) >= 1)
00336                                 tree = _rotate(tree, LEFT);
00337                         else if (_get_height(tree->right->left) - 
00338                                  _get_height(tree->right->right) >= 1)
00339                                 tree = _double_rotate(tree, LEFT);
00340                 }
00341         } else if (key == tree->element->key) {
00342                 *error = 1;
00343         }
00344 
00345         tree->height = 1 + _maximum(_get_height(tree->left),
00346                                     _get_height(tree->right));
00347         return tree;
00348 }
00349 
00350 
00351 template <class Key>
00352 int AVL_tree<Key>::insert_elt(Comparable<Key> *elt)
00353 {
00354         int error = 0;
00355         if (elt == 0)
00356                 return -1;
00357 
00358         root = __avl_ins(elt, elt->key, root, 0, -1, &error);
00359         return error;
00360 }
00361 
00363 template <class Key>
00364 AVL_node<Key> *AVL_tree<Key>::__avl_del(Comparable<Key> *elt, Key key,
00365                                    AVL_node<Key> *tree, AVL_node<Key> *parent,
00366                                    int direction, int *error)
00367 {
00368         if (tree == 0) {
00369                 *error = 1;
00370                 return 0;
00371         } else if (key == tree->element->key) {
00372                 AVL_node<Key> *shifted;
00373                 if (direction == LEFT && parent != 0) {
00374                         if (tree->left == 0)
00375                                 parent->left = tree->right;
00376                         else if (tree->right == 0)
00377                                 parent->left = tree->right;
00378                 } else if (direction == RIGHT && parent !=0) {
00379                         if (tree->left == 0)
00380                                 parent->right = tree->right;
00381                         else if (tree->right == 0)
00382                                 parent->right = tree->right;
00383                 }
00384 
00385                 if (tree->left == 0)
00386                         shifted = tree->right;
00387                 else if (tree->right == 0)
00388                         shifted = tree->left;
00389                 else {
00390                         if (tree->prev != 0) {
00391                                 tree->element = tree->prev->element;
00392                                 key = tree->element->key;
00393                         } else {
00394                                 tree->element = tree->next->element;
00395                                 key = tree->element->key;
00396                         }
00397                         return __avl_del(elt, key, tree, parent,
00398                                          direction, error);
00399                 }
00400 
00401                 if (tree->next != 0)
00402                         tree->next->prev = tree->prev;
00403                 if (tree->prev != 0)
00404                         tree->prev->next = tree->next;
00405                 tree->left = tree->right = 0;
00406                 delete tree;
00407 
00408                 if (shifted != 0)
00409                         shifted->height--;
00410                 return shifted;
00411         } else if (key < tree->element->key) {
00412                 tree->left = __avl_del(elt, key, tree->left, tree, 
00413                                        LEFT, error);
00414 
00415                 if (_get_height(tree->left) - _get_height(tree->right) >= 2) {
00416                         if (_get_height(tree->left->left) - 
00417                             _get_height(tree->left->right) >= 1)
00418                                 tree = _rotate(tree, RIGHT);
00419                         else if (_get_height(tree->left->right) - 
00420                                  _get_height(tree->left->left) >= 1)
00421                                 tree = _double_rotate(tree, RIGHT);
00422                 }
00423         } else if (key > tree->element->key) {
00424                 tree->right = __avl_del(elt, key, tree->right, tree, 
00425                                         RIGHT, error);
00426 
00427                 if (_get_height(tree->right) - _get_height(tree->left) >= 2) {
00428                         if (_get_height(tree->right->right) - 
00429                             _get_height(tree->right->left) >= 1)
00430                                 tree = _rotate(tree, LEFT);
00431                         else if (_get_height(tree->right->left) - 
00432                                  _get_height(tree->right->right) >= 1)
00433                                 tree = _double_rotate(tree, LEFT);
00434                 }
00435         }
00436 
00437         tree->height = 1 + _maximum(_get_height(tree->left),
00438                                     _get_height(tree->right));
00439         return tree;
00440 }
00441 
00442 
00443 template <class Key>
00444 int AVL_tree<Key>::delete_elt(Comparable<Key> *elt)
00445 {
00446         int error = 0;
00447 
00448         root = __avl_del(elt, elt->key, root, 0, -1, &error);
00449         return error;
00450 }
00451 
00452 
00453 
00454 
00455 #include <stdio.h>
00456 
00457 template <class Key>
00458 void AVL_tree<Key>::__avl_print(AVL_node<Key> *tree,
00459                                       int direction, int indent)
00460 {
00461         int i;
00462         char format[MAX_FORMAT_STRING];
00463 
00464         if (tree != 0) {
00465                 __avl_print(tree->right, RIGHT, indent + 1);
00466 
00467                 for (i = 0; i < indent - 1; i++)
00468                         fprintf(stderr, "    ");
00469                 if (indent) {
00470                         if (direction == LEFT)
00471                                 fprintf(stderr, " \\-- ");
00472                         else 
00473                                 fprintf(stderr, " /-- ");
00474                 }
00475                 sprintf(format, "%s\n", tree->element->key_format_string);
00476                 fprintf(stderr, format, tree->element->key);
00477 
00478                 __avl_print(tree->left, LEFT, indent + 1);
00479         }
00480 }
00481 
00482 
00483 template <class Key>
00484 void AVL_tree<Key>::print()
00485 {
00486         fprintf(stderr, "AVL tree: \n");
00487         __avl_print(root, -1, 0);
00488 }
00489 
00490 
00491 template <class Key>
00492 void AVL_tree<Key>::print_list()
00493 {
00494         int i;
00495         char format[MAX_FORMAT_STRING];
00496         AVL_node<Key> *list = find_min();
00497 
00498         fprintf(stderr, "Linked list:  ");
00499         if (list == 0)
00500                 goto end;
00501 
00502         sprintf(format, "%s ", list->element->key_format_string);
00503         fprintf(stderr, format, list->element->key_value());
00504         for (i = 1, list = list->next; list != 0; list = list->next, i++) {
00505                 sprintf(format, "-> %s ", list->element->key_format_string);
00506                 fprintf(stderr, format, list->element->key);
00507         }
00508  end:
00509         fprintf(stderr, "\n\n");
00510 }
00511 
00512 
00513 #endif  // _AVL_H_


© 2007, Los Alamos National Security, LLC.