Commits

Anonymous committed 442616b

get rid of bstree, come back later with better ideas

Comments (0)

Files changed (2)

types/bstree.h

-#ifndef _BSTREE_H_
-#define _BSTREE_H_
-
-#include <stdlib.h>
-#define bstree_def(Name, Type, Cmp)                        \
-typedef struct Name##_ Name;                               \
-struct Name##_ {                                           \
-    Name *left;                                            \
-    Name *right;                                           \
-    Name *parent;                                          \
-    Type  data;                                            \
-};                                                         \
-static inline int Name##_cmp(Type a, Type b)               \
-{                                                          \
-    return Cmp;                                            \
-}                                                          \
-Name *Name##_new(Type t)                                   \
-{                                                          \
-    Name *n = malloc(sizeof(Name));                        \
-    if (!n)                                                \
-        return NULL;                                       \
-    *n = (Name){ NULL, NULL, NULL, t };                    \
-    return n;                                              \
-}                                                          \
-Name *Name##_find(Name *n, Type t)                         \
-{                                                          \
-    while (n) {                                            \
-        int c = Name##_cmp(t, n->data);                    \
-        if      (c < 0) n = n->left;                       \
-        else if (c > 0) n = n->right;                      \
-        else            return n;                          \
-    }                                                      \
-    return NULL;                                           \
-}                                                          \
-void Name##_for_each(Name *n, void (*act)(Type*))          \
-{                                                          \
-    if (!n)                                                \
-        return;                                            \
-    Name##_for_each(n->left , act);                        \
-    act(&n->data);                                         \
-    Name##_for_each(n->right, act);                        \
-}                                                          \
-Name *Name##_rotate_right(Name **q)                        \
-{                                                          \
-    Name *r, *p;                                           \
-    if (!q || !*q || !(*q)->left)                          \
-        return NULL;                                       \
-    r = *q;                                                \
-    p = r->left;                                           \
-    if (r->parent) {                                       \
-        if (r->parent->left == r) r->parent->left  = p;    \
-        else                      r->parent->right = p;    \
-    }                                                      \
-    if ((r->left = p->right))                              \
-        r->left->parent = r;                               \
-    p->parent = r->parent;                                 \
-    r->parent = p;                                         \
-    p->right  = r;                                         \
-    *q = p;                                                \
-    return p;                                              \
-}                                                          \
-Name *Name##_rotate_left(Name **q)                         \
-{                                                          \
-    Name *r, *p;                                           \
-    if (!q || !*q || !(*q)->right)                         \
-        return NULL;                                       \
-    r = *q;                                                \
-    p = r->right;                                          \
-    if (r->parent) {                                       \
-        if (r->parent->left == r) r->parent->left  = p;    \
-        else                      r->parent->right = p;    \
-    }                                                      \
-    if ((r->right = p->left))                              \
-        r->right->parent = r;                              \
-    p->parent = r->parent;                                 \
-    r->parent = p;                                         \
-    p->left   = r;                                         \
-    *q = p;                                                \
-    return p;                                              \
-}                                                          \
-Name *Name##_insert(Name **q, Type t)                      \
-{                                                          \
-    Name *n, *p;                                           \
-    if (!q)                                                \
-        return NULL;                                       \
-    if (!*q)                                               \
-        return *q = Name##_new(t);                         \
-    for (n = *q; n; p = n, n = *q) {                       \
-        int c = Name##_cmp(t, n->data);                    \
-        if      (c < 0) q = &n->left;                      \
-        else if (c > 0) q = &n->right;                     \
-        else {                                             \
-            n->data = t;                                   \
-            return n;                                      \
-        }                                                  \
-    }                                                      \
-    n = *q = Name##_new(t);                                \
-    n->parent = p;                                         \
-    return n;                                              \
-}                                                          \
-void Name##_del(Name **q)                                  \
-{                                                          \
-    Name *n, *d, **p = NULL;                               \
-    if (!q || !*q)                                         \
-        return;                                            \
-    n = *q;                                                \
-    if (n->parent)                                         \
-        p = (n->parent->left == n) ? &n->parent->left      \
-                                   : &n->parent->right;    \
-    switch (!!n->left + !!n->right) {                      \
-        case 0: *q = NULL;                                 \
-                free(n);                                   \
-                break;                                     \
-        case 1: *q = n->left ? n->left : n->right;         \
-                (*q)->parent = n->parent;                  \
-                free(n);                                   \
-                break;                                     \
-        case 2: for (d = n->right; d->left; d = d->left)   \
-                    ;                                      \
-                n->data = d->data;                         \
-                Name##_del(&d);                            \
-                return;                                    \
-    }                                                      \
-    if (p)                                                 \
-        *p = *q;                                           \
-}                                                          \
-void Name##_del_sub(Name **q)                              \
-{                                                          \
-    Name *n;                                               \
-    if (!q || !*q)                                         \
-        return;                                            \
-    n  = *q;                                               \
-    Name##_del_sub(&n->left);                              \
-    Name##_del_sub(&n->right);                             \
-    if (n->parent) {                                       \
-        if (n->parent->left == n) n->parent->left  = NULL; \
-        else                      n->parent->right = NULL; \
-    }                                                      \
-    *q = NULL;                                             \
-    free(n);                                               \
-}
-#endif
 #include "list.h"
 #include "heap.h"
 #include "bstree.h"
+#include "splaytree.h"
 
 vector_def(Stack, int) // use vector as stack
 list_def  (Listn, int) // use list node as list
 heap_def  (Max_heap, int, a < b)
-bstree_def(Btree, int, (a > b) - (a < b))
-
-void print_int(int *i) { printf("%d,", *i); }
-size_t btree_depth(Btree *r, size_t depth) {
-    if (!r)
-        return depth;
-    depth++;
-    return size_t_max(btree_depth(r->left, depth), btree_depth(r->right, depth));
-}
-size_t btree_count(Btree *r) {
-    if (!r)
-        return 0;
-    return 1 + btree_count(r->left) + btree_count(r->right);
-}
 
 #define LENGTH(x) (sizeof(x) / sizeof(*x))
 int main(void)
 {
+    setbuf(stdout, NULL);
     srand(time(NULL));
     /* Vector demo */
     Stack *s = Stack_new(4); // minimum capacity 4
     printf("\nempty size:%zu\n", v->size);
     Stack_del(v);
 
-    /* bstree demo */
-    Btree *root = NULL;
-    printf("Btree inserting: ");
-    for (i = 50; i; i--) {
-        printf("%zu,", j = rand() % 20);
-        Btree_insert(&root, j);
-    }
-    printf("\ndepth: %zu\ncount: %zu\n", btree_depth(root, 0), btree_count(root));
-    Btree_for_each(root, print_int);
-    // Up to use to not _del_sub on a separate pointer to root...
-    Btree *btn;
-    do btn = Btree_find(root, j = rand() % 20);
-    while (!btn || btn == root);
-    printf("\nfind, print subtree, delete subtree for %zu\n", j);
-    Btree_for_each(btn, print_int);
-    Btree_del_sub(&btn);
-    printf("\nbtn is%s NULL\n", btn ? " not" : "");
-    Btree_for_each(root, print_int);
-
-    printf("\nroot: %d\n", root->data);
-    printf("del root\n");
-    Btree_del(&root);
-    printf("root: %d\n", root->data);
-    Btree_for_each(root, print_int);
-    printf("\ndepth: %zu\ncount: %zu\n", btree_depth(root, 0), btree_count(root));
-    printf("rotate_right\n");
-    Btree_rotate_right(&root);
-    printf("root: %d\n", root->data);
-    Btree_for_each(root, print_int);
-    printf("\ndepth: %zu\ncount: %zu\n", btree_depth(root, 0), btree_count(root));
-    Btree_del_sub(&root);
-
     return 0;
 }