source: src/tests/avltree/avl.h @ 9236060

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

Merge branch 'master' into references

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