source: tests/avltree/avl3.cfa @ b6f2e7ab

Last change on this file since b6f2e7ab was fd54fef, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

Converting the project to use the new syntax for otype, dtype and ttytpe.

Changed prelude (gen), libcfa and test suite to use it. Added a simple deprecation rule of the old syntax to the parser; we might wish to support both syntaxes "officially," like with an extra CLI switch, but this measure should serve as a simple reminder for our team to try the new syntax.

  • Property mode set to 100644
File size: 2.7 KB
Line 
1#include "avl.h"
2#include "avl-private.h"
3#include <stdlib.hfa>
4
5// swaps the data within two tree nodes
6forall(K | Comparable(K), V)
7void node_swap(tree(K, V) * t, tree(K, V) * t2){
8        swap( t->key,  t2->key);
9        swap( t->value, t2->value);
10}
11
12// go left as deep as possible from within the right subtree
13forall(K | Comparable(K), V)
14tree(K, V) * find_successor(tree(K, V) * t){
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);
24}
25
26// cleanup - don't want to deep delete, so set children to NULL first.
27forall(K | Comparable(K), V)
28void deleteSingleNode(tree(K, V) * t) {
29        t->left = NULL;
30        t->right = NULL;
31        delete(t);
32}
33
34// does the actual remove operation once we've found the node in question
35forall(K | Comparable(K), V)
36tree(K, V) * remove_node(tree(K, V) * t){
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;
46
47                // relink tree
48                t->left = tmp->left;
49                t->right = tmp->right;
50
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;
59
60                // relink tree
61                t->left = tmp->left;
62                t->right = tmp->right;
63
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;
72
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        }
84}
85
86// finds the node that needs to be removed
87forall(K | Comparable(K), V)
88tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){
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;
106}
107
108forall(K | Comparable(K), V)
109int remove(tree(K, V) ** t, K key){
110        int worked = 0;
111        tree(K, V) * newTree = remove_helper(*t, key, &worked);
112        *t = newTree;
113        return worked;
114}
115
116// Local Variables: //
117// tab-width: 4 //
118// End: //
Note: See TracBrowser for help on using the repository browser.