source: tests/avltree/avl.h @ 46aa60e

Last change on this file since 46aa60e was dd3576b, checked in by Peter A. Buhr <pabuhr@…>, 21 months ago

update from old to new trait syntax using forall

  • Property mode set to 100644
File size: 2.8 KB
RevLine 
[6b0b624]1#pragma once
[6e3ae00]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
[dd3576b]11forall(T)
12trait Comparable {
[6e3ae00]13  int ?<?(T, T);
14};
15
[fd54fef]16forall(T | Comparable(T))
[6e3ae00]17int ?==?(T t1, T t2);
18
[fd54fef]19forall(T | Comparable(T))
[6e3ae00]20int ?>?(T t1, T t2);
21
[627f585]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
[6e3ae00]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
[fd54fef]44forall(K | Comparable(K), V)
[6e3ae00]45struct tree;
46
[fd54fef]47forall(K | Comparable(K), V)
[6e3ae00]48struct 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
[fd54fef]57forall(K | Comparable(K), V)
[2afec66]58void ?{}(tree(K, V) &t, K key, V value);
[6e3ae00]59
[fd54fef]60forall(K | Comparable(K), V)
[2afec66]61void ^?{}(tree(K, V) & t);
[6e3ae00]62
[fd54fef]63forall(K | Comparable(K), V)
[6e3ae00]64tree(K, V) * create(K key, V value);
65
[fd54fef]66forall(K | Comparable(K), V)
[6e3ae00]67V * find(tree(K, V) * t, K key);
68
[fd54fef]69forall(K | Comparable(K), V)
[6e3ae00]70int empty(tree(K, V) * t);
71
72// returns the root of the tree
[fd54fef]73forall(K | Comparable(K), V)
[6e3ae00]74int insert(tree(K, V) ** t, K key, V value);
75
[fd54fef]76forall(K | Comparable(K), V)
[6e3ae00]77int remove(tree(K, V) ** t, K key);
78
[fd54fef]79forall(K | Comparable(K), V)
[6e3ae00]80void copy(tree(K, V) * src, tree(K, V) ** ret);
81
[fd54fef]82forall(K | Comparable(K), V)
[6e3ae00]83void 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// }
Note: See TracBrowser for help on using the repository browser.