source: src/tests/avltree/avl2.c @ 4b2589a

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 4b2589a was 3dcd347a, checked in by Thierry Delisle <tdelisle@…>, 8 years ago

moved some more tests to new test folder

  • Property mode set to 100644
File size: 2.3 KB
Line 
1#include "avl.h"
2#include "avl-private.h"
3
4forall(otype K | Comparable(K), otype V)
5V * find(tree(K, V) * t, K key){
6  if (empty(t)){
7    return NULL;
8  }
9
10  if (t->key == key){
11    return &t->value;
12  } else if (t->key < key){
13    return find(t->right, key);
14  } else {
15    // t->key > key
16    return find(t->left, key);
17  }
18}
19
20forall(otype K | Comparable(K), otype V)
21int empty(tree(K, V) * t){
22  return t == NULL;
23}
24
25// returns the root of the tree
26forall(otype K | Comparable(K), otype V)
27int insert(tree(K, V) ** t, K key, V value) {
28  // handles a non-empty tree
29  // problem if the following signature is used: tries to use an adapter to call helper, but shouldn't
30  // be necessary - seems to be a problem with helper's type variables not being renamed
31  // tree(K, V) * helper(tree(K, V) * t, K key, V value){
32  tree(K, V) * helper(tree(K, V) * t){
33    if (t->key == key){
34      // ran into the same key - uh-oh
35      return NULL;
36    } else if (t->key < key){
37      if (t->right == NULL){
38        t->right = create(key, value);
39        tree(K, V) * right = t->right; // FIX ME!
40        right->parent = t;             // !!!!!!!
41        return t->right;
42      } else {
43        return helper(t->right);
44      }
45    } else {
46      if (t->left == NULL){
47        t->left = create(key, value);
48        tree(K, V) * left = t->left;   // FIX ME!
49        left->parent = t;              // !!!!!!!
50        return t->left;
51      } else {
52        return helper(t->left);
53      }
54    }
55  }
56
57  if (empty(*t)){
58    // be nice and return a new tree
59    *t = create(key, value);
60    return 0;
61  }
62  tree(K, V) * newTree = helper(*t);
63  if (newTree == NULL){
64    // insert error handling code, only possibility
65    // currently is that the key already exists
66    return 99;
67  }
68  // move up the tree, updating balance factors
69  // if the balance factor is -1, 0, or 1 keep going
70  // if the balance factor is -2 or 2, call fix
71  while (newTree->parent != NULL){ // loop until newTree == NULL?
72    newTree = tryFix(newTree);
73    tree(K, V) * parent = newTree->parent;  // FIX ME!!
74    assert(parent->left == newTree ||
75         parent->right == newTree);
76    newTree = newTree->parent;
77  }
78  insert(t, key, value);
79
80  // do it one more time - this is the root
81  newTree = tryFix(newTree);
82  *t = newTree;
83  return 0;
84}
Note: See TracBrowser for help on using the repository browser.