agl / critbit
watch download tarball
public
Forks0Right
Watchers9Right
Description: Critbit trees in C
Homepage:
Clone URL: git://github.com/agl/critbit.git
critbit / critbit-test.cc
100644 94 lines (70 sloc) 1.952 kb
raw blame history 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <string>
#include <set>
 
#include "critbit.h"
 
using namespace std;
 
static void
test_contains() {
  critbit0_tree tree = {0};
 
  static const char *elems[] = {"a", "aa", "b", "bb", "ab", "ba", "aba", "bab", NULL};
 
  for (unsigned i = 0; elems[i]; ++i) critbit0_insert(&tree, elems[i]);
 
  for (unsigned i = 0; elems[i]; ++i) {
    if (!critbit0_contains(&tree, elems[i])) abort();
  }
 
  critbit0_clear(&tree);
}
 
static void
test_delete() {
  critbit0_tree tree = {0};
 
  static const char *elems[] = {"a", "aa", "b", "bb", "ab", "ba", "aba", "bab", NULL};
 
  for (unsigned i = 1; elems[i]; ++i) {
    critbit0_clear(&tree);
 
    for (unsigned j = 0; j < i; ++j) critbit0_insert(&tree, elems[j]);
    for (unsigned j = 0; j < i; ++j) {
      if (!critbit0_contains(&tree, elems[j])) abort();
    }
    for (unsigned j = 0; j < i; ++j) {
      if (1 != critbit0_delete(&tree, elems[j])) abort();
    }
    for (unsigned j = 0; j < i; ++j) {
      if (critbit0_contains(&tree, elems[j])) abort();
    }
  }
 
  critbit0_clear(&tree);
}
 
static int
allprefixed_cb(const char *elem, void *arg) {
  set<string> *a = (set<string> *) arg;
  a->insert(elem);
 
  return 1;
}
 
static void
test_allprefixed() {
  critbit0_tree tree = {0};
 
  static const char *elems[] = {"a", "aa", "aaz", "abz", "bba", "bbc", "bbd", NULL};
 
  for (unsigned i = 0; elems[i]; ++i) critbit0_insert(&tree, elems[i]);
 
  set<string> a;
 
  critbit0_allprefixed(&tree, "a", allprefixed_cb, &a);
  if (a.size() != 4 ||
      a.find("a") == a.end() ||
      a.find("aa") == a.end() ||
      a.find("aaz") == a.end() ||
      a.find("abz") == a.end()) {
    abort();
  }
  a.clear();
 
  critbit0_allprefixed(&tree, "aa", allprefixed_cb, &a);
  if (a.size() != 2 ||
      a.find("aa") == a.end() ||
      a.find("aaz") == a.end()) {
    abort();
  }
  a.clear();
 
  critbit0_clear(&tree);
}
 
int
main() {
  test_contains();
  test_delete();
  test_allprefixed();
 
  return 0;
}