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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
/*
* Small program to test data structures used by the Julia GC integration.
*/
#include <libgap-api.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int int_cmp(int a, int b)
{
return a - b;
}
#define ELEM_TYPE int
#define COMPARE int_cmp
#include "gap/baltree.h"
void ShowTree(intTree * btree)
{
printf("Tree state: %ld nodes, %ld depth.\n", (long)intTreeCount(btree),
(long)intTreeDepth(btree));
}
void TestScapegoatTrees(void)
{
const Int N = 1024 * 1024;
intTree * btree = intTreeMake();
printf("# Testing balanced trees.\n");
for (int i = 0; i < N; i++) {
intTreeInsert(btree, i);
}
ShowTree(btree);
Int errors = 0;
for (int i = 0; i < N; i++) {
if (!intTreeFind(btree, i))
errors++;
}
printf("Missing nodes: %ld\n", (long)errors);
printf("# Removing half of all nodes.\n");
for (int i = 1; i < N; i += 2) {
intTreeRemove(btree, i);
}
ShowTree(btree);
errors = 0;
for (int i = 0; i < N; i += 2) {
if (!intTreeFind(btree, i))
errors++;
if (intTreeFind(btree, i + 1))
errors++;
}
printf("Missing/wrong nodes: %ld\n", (long)errors);
printf("# Removing all but one node.\n");
for (int i = 1; i < N; i++) {
intTreeRemove(btree, i);
}
ShowTree(btree);
intTreeClear(btree);
printf("# Creating tree from out of order insertions.\n");
for (int i = 0, j = 0; i < N; i++, j = (5 * j + 1) & (N - 1)) {
intTreeInsert(btree, j);
}
ShowTree(btree);
errors = 0;
for (int i = 0; i < N; i++) {
if (!intTreeFind(btree, i))
errors++;
}
printf("Missing nodes: %ld\n", (long)errors);
printf("# Deleting half nodes out of order.\n");
for (int i = 0, j = 0; i < N; i++, j = (j + 7) & (N - 1)) {
if (i == N / 2) {
ShowTree(btree);
printf("# Deleting other nodes out of order.\n");
}
intTreeRemove(btree, i);
}
ShowTree(btree);
intTreeDelete(btree);
printf("# Balanced tree tests finished.\n");
}
#define ELEM_TYPE int
#define COMPARE int_cmp
#include "gap/dynarray.h"
void ShowArray(intArray * arr)
{
Int sum = 0;
for (Int i = 0; i < intArrayLen(arr); i++) {
sum += arr->items[i];
}
printf("Array state: length = %ld, sum = %ld\n", (long)intArrayLen(arr),
(long)sum);
}
static void TestDynArrays(void)
{
const Int N = 50000;
printf("# Testing dynamic arrays.\n");
intArray * arr = intArrayMake(1);
for (Int i = 0; i < N; i++) {
intArrayAdd(arr, N - i);
}
ShowArray(arr);
Int errors = 0;
for (Int i = 0; i < N; i++) {
if (intArrayGet(arr, i) != N - i)
errors++;
}
printf("Wrong entries: %ld\n", (long)errors);
printf("# Sorting array.\n");
intArraySort(arr);
errors = 0;
for (Int i = 0; i < N; i++) {
if (intArrayGet(arr, i) != i + 1)
errors++;
}
printf("Wrong entries: %ld\n", (long)errors);
printf("# Splitting and duplicating array.\n");
intArraySetLen(arr, N / 2);
for (Int i = 0; i < N / 2; i++) {
intArrayAdd(arr, arr->items[i]);
}
ShowArray(arr);
printf("# Cloning array.\n");
intArray * arr2 = intArrayClone(arr);
errors = 0;
for (Int i = 0; i < N / 2; i++) {
if (intArrayGet(arr2, i) != i + 1)
errors++;
if (intArrayGet(arr2, i + N / 2) != i + 1)
errors++;
}
printf("Wrong entries: %ld\n", (long)errors);
ShowArray(arr2);
intArrayDelete(arr);
intArrayDelete(arr2);
printf("# Dynamic array tests finished.\n");
}
int main(int argc, char ** argv)
{
TestScapegoatTrees();
TestDynArrays();
return 0;
}
|
