Changeset cb811ac for src/tests/avltree


Ignore:
Timestamp:
Aug 23, 2017, 9:02:41 PM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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:
7ece922
Parents:
d3e4d6c
Message:

change stdlib swap to use references, and update swap tests

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/tests/avltree/avl3.c

    rd3e4d6c rcb811ac  
    33#include <stdlib>
    44
    5 // from stdlib
    6 forall(otype T)
    7 void swap(T *, T *);
    8 
    95// swaps the data within two tree nodes
    106forall(otype K | Comparable(K), otype V)
    117void node_swap(tree(K, V) * t, tree(K, V) * t2){
    12   swap(&t->key, &t2->key);
    13   swap(&t->value, &t2->value);
     8        swap( t->key,  t2->key);
     9        swap( t->value, t2->value);
    1410}
    1511
    … …  
    1713forall(otype K | Comparable(K), otype V)
    1814tree(K, V) * find_successor(tree(K, V) * t){
    19   tree(K, V) * find_successor_helper(tree(K, V) * t){
    20     // go left as deep as possible, return the last node
    21     if (empty(t->left)){
    22       return t;
    23     } else {
    24       return find_successor_helper(t->left);
    25     }
    26   }
    27   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);
    2824}
    2925
    … …  
    3127forall(otype K | Comparable(K), otype V)
    3228void deleteSingleNode(tree(K, V) * t) {
    33   t->left = NULL;
    34   t->right = NULL;
    35   delete(t);
     29        t->left = NULL;
     30        t->right = NULL;
     31        delete(t);
    3632}
    3733
    … …  
    3935forall(otype K | Comparable(K), otype V)
    4036tree(K, V) * remove_node(tree(K, V) * t){
    41   // is the node a leaf?
    42   if (empty(t->left) && empty(t->right)){
    43     // yes, just delete this node
    44     delete(t);
    45     return NULL;
    46   } else if (empty(t->left)){
    47     // if the left is empty, there is only one child -> move right up
    48     node_swap(t, t->right);
    49     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;
    5046
    51     // relink tree
    52     t->left = tmp->left;
    53     t->right = tmp->right;
     47                // relink tree
     48                t->left = tmp->left;
     49                t->right = tmp->right;
    5450
    55     setParent(t->left, t);
    56     setParent(t->right, t);
    57     deleteSingleNode(tmp);
    58     return t;
    59   } else if (empty(t->right)){
    60     // if the right is empty, there is only one child -> move left up
    61     node_swap(t, t->left);
    62     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;
    6359
    64     // relink tree
    65     t->left = tmp->left;
    66     t->right = tmp->right;
     60                // relink tree
     61                t->left = tmp->left;
     62                t->right = tmp->right;
    6763
    68     setParent(t->left, t);
    69     setParent(t->right, t);
    70     deleteSingleNode(tmp);
    71     return t;
    72   } else {
    73     // swap with the successor
    74     tree(K, V) * s = find_successor(t);
    75     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;
    7672
    77     if (parent->left == s){
    78       parent->left = s->right;
    79     } else {
    80       assert(parent->right == s);
    81       parent->right = s->right;
    82     }
    83     setParent(s->right, parent);
    84     node_swap(t, s);
    85     deleteSingleNode(s);
    86     return t;
    87   }
     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        }
    8884}
    8985
    … …  
    9187forall(otype K | Comparable(K), otype V)
    9288tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){
    93   if (empty(t)){
    94     // did not work because key was not found
    95     // set the status variable and return
    96     *worked = 1;
    97   } else if (t->key == key) {
    98     t = remove_node(t);
    99   } else if (t->key < key){
    100     t->right = remove_helper(t->right, key, worked);
    101   } else {
    102     // t->key > key
    103     t->left = remove_helper(t->left, key, worked);
    104   }
    105   // try to fix after deleting
    106   if (! empty(t)) {
    107     t = tryFix(t);
    108   }
    109   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;
    110106}
    111107
    112108forall(otype K | Comparable(K), otype V)
    113109int remove(tree(K, V) ** t, K key){
    114   int worked = 0;
    115   tree(K, V) * newTree = remove_helper(*t, key, &worked);
    116   *t = newTree;
    117   return worked;
     110        int worked = 0;
     111        tree(K, V) * newTree = remove_helper(*t, key, &worked);
     112        *t = newTree;
     113        return worked;
    118114}
     115
     116// Local Variables: //
     117// tab-width: 4 //
     118// End: //
Note: See TracChangeset for help on using the changeset viewer.