1 | #include "avl.h" |
---|

2 | #include "avl-private.h" |
---|

3 | |
---|

4 | // Perform a shallow copy of src, return the |
---|

5 | // new tree in ret |
---|

6 | forall(K | Comparable(K), V) |
---|

7 | int copy(tree(K, V) * src, tree(K, V) ** ret){ |
---|

8 | tree(K, V) * helper(tree(K, V) * t, int * worked){ |
---|

9 | if (empty(t)){ |
---|

10 | // given empty tree, return empty tree |
---|

11 | return NULL; |
---|

12 | } |
---|

13 | |
---|

14 | // otherwise, this is not an empty node, |
---|

15 | // create a new node |
---|

16 | tree(K, V) * newTree = create(t->key, t->value); |
---|

17 | if (empty(newTree)) { |
---|

18 | *worked = 1; |
---|

19 | return NULL; |
---|

20 | } |
---|

21 | |
---|

22 | // recursively copy the left and right branches |
---|

23 | newTree->left = helper(t->left, worked); |
---|

24 | newTree->right = helper(t->right, worked); |
---|

25 | |
---|

26 | setParent(newTree->left, newTree); |
---|

27 | setParent(newTree->right, newTree); |
---|

28 | return newTree; |
---|

29 | } |
---|

30 | |
---|

31 | int worked = 0; |
---|

32 | *ret = helper(src, &worked); |
---|

33 | return worked; |
---|

34 | } |
---|

35 | |
---|

36 | // Apply func to every value element in t, using an in order traversal |
---|

37 | forall(K | Comparable(K), V) |
---|

38 | void for_each(tree(K, V) * t, int (*func)(V)) { |
---|

39 | if (t == NULL) { |
---|

40 | return; |
---|

41 | } |
---|

42 | // recursively apply the function to the left, |
---|

43 | // apply the function to this node, |
---|

44 | // recursively apply the function to the right |
---|

45 | for_each(t->left, func); |
---|

46 | func(t->value); |
---|

47 | for_each(t->right, func); |
---|

48 | } |
---|