[6e3ae00] | 1 | #ifndef AVL_TREE_H
|
---|
| 2 | #define AVL_TREE_H
|
---|
| 3 |
|
---|
| 4 | extern "C" {
|
---|
| 5 | #define NULL 0
|
---|
| 6 | #define assert(cond) if (! (cond)) { printf("Assertion failed: (%s) at %s:%d\n", #cond, __FILE__, __LINE__); abort(); }
|
---|
| 7 | }
|
---|
| 8 |
|
---|
| 9 | // #include <types.h>
|
---|
| 10 | // #include <lib.h>
|
---|
| 11 |
|
---|
| 12 | trait Comparable(otype T) {
|
---|
| 13 | int ?<?(T, T);
|
---|
| 14 | };
|
---|
| 15 |
|
---|
| 16 | forall(otype T | Comparable(T))
|
---|
| 17 | int ?==?(T t1, T t2);
|
---|
| 18 |
|
---|
| 19 | forall(otype T | Comparable(T))
|
---|
| 20 | int ?>?(T t1, T t2);
|
---|
| 21 |
|
---|
| 22 | forall(dtype T | { void ^?{}(T *); })
|
---|
| 23 | void delete(T * x);
|
---|
| 24 |
|
---|
| 25 | // To-do: properly use height or balance factor
|
---|
| 26 | // Right now I'm recomputing the height for each
|
---|
| 27 | // node multiple times. It's Theta-log(n), but still..
|
---|
| 28 |
|
---|
| 29 | // Balanced Binary Search Tree of void pointers; almost an AVL tree -
|
---|
| 30 | // just needs to make use of the balance factor properly
|
---|
| 31 | // Operations:
|
---|
| 32 | // ?{}, ^?{}
|
---|
| 33 | // create - allocate a new tree. Just a wrapper around malloc which also calls the tree constructor.
|
---|
| 34 | // find - search through the tree for the given key; return the associated value
|
---|
| 35 | // empty - return true if the tree is empty
|
---|
| 36 | // insert - insert node with key and value pair. Returns 0 on success
|
---|
| 37 | // remove - remove node with the given key, returns 0 on success, 1 on failure
|
---|
| 38 | // copy - deep copy of a tree
|
---|
| 39 | // for_each - applies the given function to every data element in the tree
|
---|
| 40 | // assumes that a non-zero return value is an error, will return
|
---|
| 41 | // the error code from func
|
---|
| 42 |
|
---|
| 43 | // temporary: need forward decl to get around typedef problem
|
---|
| 44 | forall(otype K | Comparable(K), otype V)
|
---|
| 45 | struct tree;
|
---|
| 46 |
|
---|
| 47 | forall(otype K | Comparable(K), otype V)
|
---|
| 48 | struct tree {
|
---|
| 49 | K key;
|
---|
| 50 | V value;
|
---|
| 51 | tree(K, V) * parent;
|
---|
| 52 | tree(K, V) * left;
|
---|
| 53 | tree(K, V) * right;
|
---|
| 54 | int balance;
|
---|
| 55 | };
|
---|
| 56 |
|
---|
| 57 | forall(otype K | Comparable(K), otype V)
|
---|
| 58 | void ?{}(tree(K, V) *t, K key, V value);
|
---|
| 59 |
|
---|
| 60 | forall(otype K | Comparable(K), otype V)
|
---|
| 61 | void ^?{}(tree(K, V) * t);
|
---|
| 62 |
|
---|
| 63 | forall(otype K | Comparable(K), otype V)
|
---|
| 64 | tree(K, V) * create(K key, V value);
|
---|
| 65 |
|
---|
| 66 | forall(otype K | Comparable(K), otype V)
|
---|
| 67 | V * find(tree(K, V) * t, K key);
|
---|
| 68 |
|
---|
| 69 | forall(otype K | Comparable(K), otype V)
|
---|
| 70 | int empty(tree(K, V) * t);
|
---|
| 71 |
|
---|
| 72 | // returns the root of the tree
|
---|
| 73 | forall(otype K | Comparable(K), otype V)
|
---|
| 74 | int insert(tree(K, V) ** t, K key, V value);
|
---|
| 75 |
|
---|
| 76 | forall(otype K | Comparable(K), otype V)
|
---|
| 77 | int remove(tree(K, V) ** t, K key);
|
---|
| 78 |
|
---|
| 79 | forall(otype K | Comparable(K), otype V)
|
---|
| 80 | void copy(tree(K, V) * src, tree(K, V) ** ret);
|
---|
| 81 |
|
---|
| 82 | forall(otype K | Comparable(K), otype V)
|
---|
| 83 | void for_each(tree(K, V) * t, void (*func)(V));
|
---|
| 84 |
|
---|
| 85 | // // Helper function to print trees
|
---|
| 86 | // forall(otype K | Comparable(K), otype V)
|
---|
| 87 | // void printTree(tree * t, int level){
|
---|
| 88 | // if (empty(t)){
|
---|
| 89 | // return;
|
---|
| 90 | // }
|
---|
| 91 |
|
---|
| 92 | // printTree(t->left, level+1);
|
---|
| 93 | // printf("key: %d, value: %s, level: %d\n", t->key, t->value, level);
|
---|
| 94 | // printTree(t->right, level+1);
|
---|
| 95 | // }
|
---|
| 96 |
|
---|
| 97 | // // inorder traversal of t
|
---|
| 98 | // // prints each key, followed by the value
|
---|
| 99 | // forall(otype K | Comparable(K), otype V)
|
---|
| 100 | // void printTree(tree(K, V) * t){
|
---|
| 101 | // printTree(t, 0);
|
---|
| 102 | // }
|
---|
| 103 |
|
---|
| 104 |
|
---|
| 105 | #endif
|
---|