Index: tests/avltree/avl-private.c =================================================================== --- tests/avltree/avl-private.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl-private.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,134 @@ +#include "avl.h" +#include "avl-private.h" + +// AVL tree specific (internal) operations: +// rotateLeft, rotateRight, fix +// +// AVL tree enhanced height operation +// +// calcBalance is a simple computation of height(R) - height(L) + +// an AVL tree's height is easy to compute +// just follow path with the larger balance +forall(otype K | Comparable(K), otype V) +int height(tree(K, V) * t){ + int helper(tree(K, V) * t, int ht){ + if (empty(t)){ + return ht; + } else if (t->balance > 0){ + return helper(t->right, 1+ht); + } else { + // can traverse either branch to find the height + // of an AVL tree whose balance is 0 + return helper(t->left, 1+ht); + } + } + return helper(t, 0); +} + +forall(otype K | Comparable(K), otype V) +int calcBalance(tree(K, V) * t){ + int l = height(t->left); + int r = height(t->right); + t->balance = r-l; + return t->balance; +} + +// re-establish the link between parent and child +forall(otype K | Comparable(K), otype V) +void relinkToParent(tree(K, V) * t){ + tree(K, V) * parent = t->parent; // FIX ME!! + if (empty(t->parent)){ + return; + } else if (parent->key < t->key){ + parent->right = t; + } else { + parent->left = t; + } +} + +// rotate left from t +forall(otype K | Comparable(K), otype V) +tree(K, V) * rotateLeft(tree(K, V) * t){ + tree(K, V) * newRoot = t->right; + t->right = newRoot->left; + newRoot->left = t; + + // swap parents + newRoot->parent = t->parent; + t->parent = newRoot; + if (t->right != NULL) { + tree(K, V) * right = t->right; // FIX ME!! + right->parent = t; + } + // re-establish the link between newRoot and its parent + relinkToParent(newRoot); + return newRoot; +} + +// rotate right from t +forall(otype K | Comparable(K), otype V) +tree(K, V) * rotateRight(tree(K, V) * t){ + tree(K, V) * newRoot = t->left; + t->left = newRoot->right; + newRoot->right = t; + + // swap parents + newRoot->parent = t->parent; + t->parent = newRoot; + if (t->left != NULL){ + tree(K, V) * left = t->left; // FIX ME!! + left->parent = t; + } + // re-establish the link between newRoot and its parent + relinkToParent(newRoot); + return newRoot; +} + +// balances a node that has balance factor -2 or 2 +forall(otype K | Comparable(K), otype V) +tree(K, V) * fix(tree(K, V) * t){ + // ensure that t's balance factor is one of + // the appropriate values + assert(t->balance == 2 || t->balance == -2); + + if (t->balance == -2){ + tree(K, V) * left = t->left; // FIX ME!! + if (left->balance == 1){ + t->left = rotateLeft(t->left); + } + return rotateRight(t); + } else if (t->balance == 2){ + tree(K, V) * right = t->right; // FIX ME!! + if (right->balance == -1){ + t->right = rotateRight(t->right); + } + return rotateLeft(t); + } else { + // shouldn't ever get here + assert((int)0); + return t; + } +} + +// attempt to fix the tree, if necessary +forall(otype K | Comparable(K), otype V) +tree(K, V) * tryFix(tree(K, V) * t){ + int b = calcBalance(t); + + if (b == -2 || b == 2){ + t = fix(t); + } else { + assert(b == 0 || b == 1 || b == -1); + } + return t; +} + +// sets parent field of c to be p +forall(otype K | Comparable(K), otype V) +void setParent(tree(K, V) * c, tree(K, V) * p){ + if (! empty(c)){ + c->parent = p; + } +} + Index: tests/avltree/avl-private.h =================================================================== --- tests/avltree/avl-private.h (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl-private.h (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,15 @@ +#pragma once +#include "avl.h" + +// functions that really shouldn't be exposed, but are to reduce compilation time + +// attempt to fix the tree, if necessary +forall(otype K | Comparable(K), otype V) +tree(K, V) * tryFix(tree(K, V) * t); + +// sets parent field of c to be p +forall(otype K | Comparable(K), otype V) +void setParent(tree(K, V) * c, tree(K, V) * p); + +forall(otype K | Comparable(K), otype V) +int height(tree(K, V) * t); Index: tests/avltree/avl.h =================================================================== --- tests/avltree/avl.h (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl.h (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,101 @@ +#pragma once + +extern "C" { +#define NULL 0 +#define assert(cond) if (! (cond)) { printf("Assertion failed: (%s) at %s:%d\n", #cond, __FILE__, __LINE__); abort(); } +} + +// #include +// #include + +trait Comparable(otype T) { + int ??(T t1, T t2); + +// xxx - unbound type variable problems when trying to use new instead of create +// forall( otype T, ttype Params | { void ?{}(T *, Params); } ) T * new( Params p ); + +// To-do: properly use height or balance factor +// Right now I'm recomputing the height for each +// node multiple times. It's Theta-log(n), but still.. + +// Balanced Binary Search Tree of void pointers; almost an AVL tree - +// just needs to make use of the balance factor properly +// Operations: +// ?{}, ^?{} +// create - allocate a new tree. Just a wrapper around malloc which also calls the tree constructor. +// find - search through the tree for the given key; return the associated value +// empty - return true if the tree is empty +// insert - insert node with key and value pair. Returns 0 on success +// remove - remove node with the given key, returns 0 on success, 1 on failure +// copy - deep copy of a tree +// for_each - applies the given function to every data element in the tree +// assumes that a non-zero return value is an error, will return +// the error code from func + +// temporary: need forward decl to get around typedef problem +forall(otype K | Comparable(K), otype V) +struct tree; + +forall(otype K | Comparable(K), otype V) +struct tree { + K key; + V value; + tree(K, V) * parent; + tree(K, V) * left; + tree(K, V) * right; + int balance; +}; + +forall(otype K | Comparable(K), otype V) +void ?{}(tree(K, V) &t, K key, V value); + +forall(otype K, otype V) +void ^?{}(tree(K, V) & t); + +forall(otype K | Comparable(K), otype V) +tree(K, V) * create(K key, V value); + +forall(otype K | Comparable(K), otype V) +V * find(tree(K, V) * t, K key); + +forall(otype K | Comparable(K), otype V) +int empty(tree(K, V) * t); + +// returns the root of the tree +forall(otype K | Comparable(K), otype V) +int insert(tree(K, V) ** t, K key, V value); + +forall(otype K | Comparable(K), otype V) +int remove(tree(K, V) ** t, K key); + +forall(otype K | Comparable(K), otype V) +void copy(tree(K, V) * src, tree(K, V) ** ret); + +forall(otype K | Comparable(K), otype V) +void for_each(tree(K, V) * t, void (*func)(V)); + +// // Helper function to print trees +// forall(otype K | Comparable(K), otype V) +// void printTree(tree * t, int level){ +// if (empty(t)){ +// return; +// } + +// printTree(t->left, level+1); +// printf("key: %d, value: %s, level: %d\n", t->key, t->value, level); +// printTree(t->right, level+1); +// } + +// // inorder traversal of t +// // prints each key, followed by the value +// forall(otype K | Comparable(K), otype V) +// void printTree(tree(K, V) * t){ +// printTree(t, 0); +// } Index: tests/avltree/avl0.c =================================================================== --- tests/avltree/avl0.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl0.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,11 @@ +#include "avl.h" + +forall(otype T | Comparable(T)) +int ?==?(T t1, T t2) { + return !(t1 < t2) && !(t2 < t1); +} + +forall(otype T | Comparable(T)) +int ?>?(T t1, T t2) { + return t2 < t1; +} Index: tests/avltree/avl1.c =================================================================== --- tests/avltree/avl1.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl1.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,48 @@ +#include "avl.h" +// #include "cwrap.h" +#include + +forall(otype K | Comparable(K), otype V) +void ?{}(tree(K, V) &t, K key, V value){ + (t.key) { key }; + (t.value) { value }; + t.parent = NULL; + t.left = NULL; + t.right = NULL; + t.balance = 0; +} + +forall(otype K, otype V) +void ^?{}(tree(K, V) & t){ + delete(t.left); + delete(t.right); + ^(t.key){}; + ^(t.value){}; +} + +forall(otype K | Comparable(K), otype V) +tree(K, V) * create(K key, V value) { + // infinite loop trying to resolve ... t = malloc(); + tree(K, V) * t = malloc(sizeof(tree(K,V))); + (*t){ key, value }; + return t; +} + +// // Helper function to print trees +// forall(otype K | Comparable(K), otype V) +// void printTree(tree * t, int level){ +// if (empty(t)){ +// return; +// } + +// printTree(t->left, level+1); +// printf("key: %d, value: %s, level: %d\n", t->key, t->value, level); +// printTree(t->right, level+1); +// } + +// // inorder traversal of t +// // prints each key, followed by the value +// forall(otype K | Comparable(K), otype V) +// void printTree(tree(K, V) * t){ +// printTree(t, 0); +// } Index: tests/avltree/avl2.c =================================================================== --- tests/avltree/avl2.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl2.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,84 @@ +#include "avl.h" +#include "avl-private.h" + +forall(otype K | Comparable(K), otype V) +V * find(tree(K, V) * t, K key){ + if (empty(t)){ + return NULL; + } + + if (t->key == key){ + return &t->value; + } else if (t->key < key){ + return find(t->right, key); + } else { + // t->key > key + return find(t->left, key); + } +} + +forall(otype K | Comparable(K), otype V) +int empty(tree(K, V) * t){ + return t == NULL; +} + +// returns the root of the tree +forall(otype K | Comparable(K), otype V) +int insert(tree(K, V) ** t, K key, V value) { + // handles a non-empty tree + // problem if the following signature is used: tries to use an adapter to call helper, but shouldn't + // be necessary - seems to be a problem with helper's type variables not being renamed + // tree(K, V) * helper(tree(K, V) * t, K key, V value){ + tree(K, V) * helper(tree(K, V) * t){ + if (t->key == key){ + // ran into the same key - uh-oh + return NULL; + } else if (t->key < key){ + if (t->right == NULL){ + t->right = create(key, value); + tree(K, V) * right = t->right; // FIX ME! + right->parent = t; // !!!!!!! + return t->right; + } else { + return helper(t->right); + } + } else { + if (t->left == NULL){ + t->left = create(key, value); + tree(K, V) * left = t->left; // FIX ME! + left->parent = t; // !!!!!!! + return t->left; + } else { + return helper(t->left); + } + } + } + + if (empty(*t)){ + // be nice and return a new tree + *t = create(key, value); + return 0; + } + tree(K, V) * newTree = helper(*t); + if (newTree == NULL){ + // insert error handling code, only possibility + // currently is that the key already exists + return 99; + } + // move up the tree, updating balance factors + // if the balance factor is -1, 0, or 1 keep going + // if the balance factor is -2 or 2, call fix + while (newTree->parent != NULL){ // loop until newTree == NULL? + newTree = tryFix(newTree); + tree(K, V) * parent = newTree->parent; // FIX ME!! + assert(parent->left == newTree || + parent->right == newTree); + newTree = newTree->parent; + } + insert(t, key, value); + + // do it one more time - this is the root + newTree = tryFix(newTree); + *t = newTree; + return 0; +} Index: tests/avltree/avl3.c =================================================================== --- tests/avltree/avl3.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl3.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,118 @@ +#include "avl.h" +#include "avl-private.h" +#include + +// swaps the data within two tree nodes +forall(otype K | Comparable(K), otype V) +void node_swap(tree(K, V) * t, tree(K, V) * t2){ + swap( t->key, t2->key); + swap( t->value, t2->value); +} + +// go left as deep as possible from within the right subtree +forall(otype K | Comparable(K), otype V) +tree(K, V) * find_successor(tree(K, V) * t){ + tree(K, V) * find_successor_helper(tree(K, V) * t){ + // go left as deep as possible, return the last node + if (empty(t->left)){ + return t; + } else { + return find_successor_helper(t->left); + } + } + return find_successor_helper(t->right); +} + +// cleanup - don't want to deep delete, so set children to NULL first. +forall(otype K | Comparable(K), otype V) +void deleteSingleNode(tree(K, V) * t) { + t->left = NULL; + t->right = NULL; + delete(t); +} + +// does the actual remove operation once we've found the node in question +forall(otype K | Comparable(K), otype V) +tree(K, V) * remove_node(tree(K, V) * t){ + // is the node a leaf? + if (empty(t->left) && empty(t->right)){ + // yes, just delete this node + delete(t); + return NULL; + } else if (empty(t->left)){ + // if the left is empty, there is only one child -> move right up + node_swap(t, t->right); + tree(K, V) * tmp = t->right; + + // relink tree + t->left = tmp->left; + t->right = tmp->right; + + setParent(t->left, t); + setParent(t->right, t); + deleteSingleNode(tmp); + return t; + } else if (empty(t->right)){ + // if the right is empty, there is only one child -> move left up + node_swap(t, t->left); + tree(K, V) * tmp = t->left; + + // relink tree + t->left = tmp->left; + t->right = tmp->right; + + setParent(t->left, t); + setParent(t->right, t); + deleteSingleNode(tmp); + return t; + } else { + // swap with the successor + tree(K, V) * s = find_successor(t); + tree(K, V) * parent = s->parent; + + if (parent->left == s){ + parent->left = s->right; + } else { + assert(parent->right == s); + parent->right = s->right; + } + setParent(s->right, parent); + node_swap(t, s); + deleteSingleNode(s); + return t; + } +} + +// finds the node that needs to be removed +forall(otype K | Comparable(K), otype V) +tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){ + if (empty(t)){ + // did not work because key was not found + // set the status variable and return + *worked = 1; + } else if (t->key == key) { + t = remove_node(t); + } else if (t->key < key){ + t->right = remove_helper(t->right, key, worked); + } else { + // t->key > key + t->left = remove_helper(t->left, key, worked); + } + // try to fix after deleting + if (! empty(t)) { + t = tryFix(t); + } + return t; +} + +forall(otype K | Comparable(K), otype V) +int remove(tree(K, V) ** t, K key){ + int worked = 0; + tree(K, V) * newTree = remove_helper(*t, key, &worked); + *t = newTree; + return worked; +} + +// Local Variables: // +// tab-width: 4 // +// End: // Index: tests/avltree/avl4.c =================================================================== --- tests/avltree/avl4.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl4.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,48 @@ +#include "avl.h" +#include "avl-private.h" + +// Perform a shallow copy of src, return the +// new tree in ret +forall(otype K | Comparable(K), otype V) +int copy(tree(K, V) * src, tree(K, V) ** ret){ + tree(K, V) * helper(tree(K, V) * t, int * worked){ + if (empty(t)){ + // given empty tree, return empty tree + return NULL; + } + + // otherwise, this is not an empty node, + // create a new node + tree(K, V) * newTree = create(t->key, t->value); + if (empty(newTree)) { + *worked = 1; + return NULL; + } + + // recursively copy the left and right branches + newTree->left = helper(t->left, worked); + newTree->right = helper(t->right, worked); + + setParent(newTree->left, newTree); + setParent(newTree->right, newTree); + return newTree; + } + + int worked = 0; + *ret = helper(src, &worked); + return worked; +} + +// Apply func to every value element in t, using an in order traversal +forall(otype K | Comparable(K), otype V) +void for_each(tree(K, V) * t, int (*func)(V)) { + if (t == NULL) { + return; + } + // recursively apply the function to the left, + // apply the function to this node, + // recursively apply the function to the right + for_each(t->left, func); + func(t->value); + for_each(t->right, func); +} Index: tests/avltree/avl_test.c =================================================================== --- tests/avltree/avl_test.c (revision bf71cfdb7285490eee552b461158846f626cc52f) +++ tests/avltree/avl_test.c (revision bf71cfdb7285490eee552b461158846f626cc52f) @@ -0,0 +1,52 @@ +#include "avl.h" +#include "avl-private.h" +#include + +extern "C" { + int strcmp(const char *, const char *); +} + +int main(){ + // operations: + // find(tree(K, V) *, K) + // int empty(tree(K, V) *); + // tree(K, V) * insert(tree(K, V) *, K, V); + // int remove(tree(K, V) **, K); + + // int -> int + tree(int, int) * imap = create(-1, (int)0); + insert(&imap, 12, 13); + insert(&imap, 2, 3); + assert( height(imap) == 2 ); + + printf("%d %d %d\n", *find(imap, 2), *find(imap, 12), *find(imap, -1)); + + remove(&imap, -1); + delete(imap); + + // int -> char * + tree(int, const char *) * smap = create(-1, "baz"); + insert(&smap, 12, "bar"); + insert(&smap, 2, "foo"); + assert( height(smap) == 2 ); + + printf("%s %s %s\n", *find(smap, 2), *find(smap, 12), *find(smap, -1)); + + remove(&smap, -2); + delete(smap); + + // const char* -> const char* + int ?