Ignore:
Timestamp:
Aug 25, 2017, 10:38:34 AM (8 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
800d275
Parents:
af08051 (diff), 3eab308c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/tests/avltree/avl3.c

    raf08051 r28e58fd  
    11#include "avl.h"
    22#include "avl-private.h"
    3 
    4 // from stdlib
    5 forall(otype T)
    6 void swap(T *, T *);
     3#include <stdlib>
    74
    85// swaps the data within two tree nodes
    96forall(otype K | Comparable(K), otype V)
    107void node_swap(tree(K, V) * t, tree(K, V) * t2){
    11   swap(&t->key, &t2->key);
    12   swap(&t->value, &t2->value);
     8        swap( t->key,  t2->key);
     9        swap( t->value, t2->value);
    1310}
    1411
    … …  
    1613forall(otype K | Comparable(K), otype V)
    1714tree(K, V) * find_successor(tree(K, V) * t){
    18   tree(K, V) * find_successor_helper(tree(K, V) * t){
    19     // go left as deep as possible, return the last node
    20     if (empty(t->left)){
    21       return t;
    22     } else {
    23       return find_successor_helper(t->left);
    24     }
    25   }
    26   return find_successor_helper(t->right);
     15        tree(K, V) * find_successor_helper(tree(K, V) * t){
     16                // go left as deep as possible, return the last node
     17                if (empty(t->left)){
     18                        return t;
     19                } else {
     20                        return find_successor_helper(t->left);
     21                }
     22        }
     23        return find_successor_helper(t->right);
    2724}
    2825
    … …  
    3027forall(otype K | Comparable(K), otype V)
    3128void deleteSingleNode(tree(K, V) * t) {
    32   t->left = NULL;
    33   t->right = NULL;
    34   deleteSingleNode(t);
     29        t->left = NULL;
     30        t->right = NULL;
     31        delete(t);
    3532}
    3633
    … …  
    3835forall(otype K | Comparable(K), otype V)
    3936tree(K, V) * remove_node(tree(K, V) * t){
    40   // is the node a leaf?
    41   if (empty(t->left) && empty(t->right)){
    42     // yes, just delete this node
    43     delete(t);
    44     return NULL;
    45   } else if (empty(t->left)){
    46     // if the left is empty, there is only one child -> move right up
    47     node_swap(t, t->right);
    48     tree(K, V) * tmp = t->right;
     37        // is the node a leaf?
     38        if (empty(t->left) && empty(t->right)){
     39                // yes, just delete this node
     40                delete(t);
     41                return NULL;
     42        } else if (empty(t->left)){
     43                // if the left is empty, there is only one child -> move right up
     44                node_swap(t, t->right);
     45                tree(K, V) * tmp = t->right;
    4946
    50     // relink tree
    51     t->left = tmp->left;
    52     t->right = tmp->right;
     47                // relink tree
     48                t->left = tmp->left;
     49                t->right = tmp->right;
    5350
    54     setParent(t->left, t);
    55     setParent(t->right, t);
    56     deleteSingleNode(tmp);
    57     return t;
    58   } else if (empty(t->right)){
    59     // if the right is empty, there is only one child -> move left up
    60     node_swap(t, t->left);
    61     tree(K, V) * tmp = t->left;
     51                setParent(t->left, t);
     52                setParent(t->right, t);
     53                deleteSingleNode(tmp);
     54                return t;
     55        } else if (empty(t->right)){
     56                // if the right is empty, there is only one child -> move left up
     57                node_swap(t, t->left);
     58                tree(K, V) * tmp = t->left;
    6259
    63     // relink tree
    64     t->left = tmp->left;
    65     t->right = tmp->right;
     60                // relink tree
     61                t->left = tmp->left;
     62                t->right = tmp->right;
    6663
    67     setParent(t->left, t);
    68     setParent(t->right, t);
    69     deleteSingleNode(tmp);
    70     return t;
    71   } else {
    72     // swap with the successor
    73     tree(K, V) * s = find_successor(t);
    74     tree(K, V) * parent = s->parent;
     64                setParent(t->left, t);
     65                setParent(t->right, t);
     66                deleteSingleNode(tmp);
     67                return t;
     68        } else {
     69                // swap with the successor
     70                tree(K, V) * s = find_successor(t);
     71                tree(K, V) * parent = s->parent;
    7572
    76     if (parent->left == s){
    77       parent->left = s->right;
    78     } else {
    79       assert(parent->right == s);
    80       parent->right = s->right;
    81     }
    82     setParent(s->right, parent);
    83     node_swap(t, s);
    84     deleteSingleNode(s);
    85     return t;
    86   }
     73                if (parent->left == s){
     74                        parent->left = s->right;
     75                } else {
     76                        assert(parent->right == s);
     77                        parent->right = s->right;
     78                }
     79                setParent(s->right, parent);
     80                node_swap(t, s);
     81                deleteSingleNode(s);
     82                return t;
     83        }
    8784}
    8885
    … …  
    9087forall(otype K | Comparable(K), otype V)
    9188tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){
    92   if (empty(t)){
    93     // did not work because key was not found
    94     // set the status variable and return
    95     *worked = 1;
    96   } else if (t->key == key) {
    97     t = remove_node(t);
    98   } else if (t->key < key){
    99     t->right = remove_helper(t->right, key, worked);
    100   } else {
    101     // t->key > key
    102     t->left = remove_helper(t->left, key, worked);
    103   }
    104   // try to fix after deleting
    105   if (! empty(t)) {
    106     t = tryFix(t);
    107   }
    108   return t;
     89        if (empty(t)){
     90                // did not work because key was not found
     91                // set the status variable and return
     92                *worked = 1;
     93        } else if (t->key == key) {
     94                t = remove_node(t);
     95        } else if (t->key < key){
     96                t->right = remove_helper(t->right, key, worked);
     97        } else {
     98                // t->key > key
     99                t->left = remove_helper(t->left, key, worked);
     100        }
     101        // try to fix after deleting
     102        if (! empty(t)) {
     103                t = tryFix(t);
     104        }
     105        return t;
    109106}
    110107
    111108forall(otype K | Comparable(K), otype V)
    112109int remove(tree(K, V) ** t, K key){
    113   int worked = 0;
    114   tree(K, V) * newTree = remove_helper(*t, key, &worked);
    115   *t = newTree;
    116   return worked;
     110        int worked = 0;
     111        tree(K, V) * newTree = remove_helper(*t, key, &worked);
     112        *t = newTree;
     113        return worked;
    117114}
     115
     116// Local Variables: //
     117// tab-width: 4 //
     118// End: //
Note: See TracChangeset for help on using the changeset viewer.