source: src/tests/avltree/avl.h @ 627f585

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 627f585 was 627f585, checked in by Rob Schluntz <rschlunt@…>, 5 years ago

moved new and delete to stdlib

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