Mercurial > data_structures

view src/ost_test.c @ 12:d359966ed8de

find changesets by author, revision, files, or words in the commit message
Added trie
author Eris Caffee <discordia@eldalin.com>
date Mon, 01 Oct 2012 15:50:30 -0500
parents
children
line source
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <stdbool.h>
4
5 #include "ost.h"
6
7 void print_val(void * data)
8 {
9 printf("%d", *((int *) data));
10 }
11
12 bool le(void * a, void * b)
13 {
14 return *((int *) a) <= *((int *) b);
15 }
16
17 bool eq(void * a, void * b)
18 {
19 return *((int *) a) == *((int *) b);
20 }
21
22 #define MAX_NUMS 10
23
24 int main (int argc, char ** argv)
25 {
26 int sorted[100] = {
27 35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567,
28 304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336,
29 596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537,
30 760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276,
31 982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124,
32 1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676,
33 1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492,
34 1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383,
35 1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926,
36 1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067,
37 };
38
39 struct ost * ost = ost_new(le, eq);
40 if (NULL == ost)
41 {
42 perror("ost_new");
43 exit(EXIT_FAILURE);
44 }
45
46 for (int i = 0; i < MAX_NUMS; ++i)
47 {
48 int * ip = malloc(sizeof(int));
49 if (NULL == ip)
50 {
51 perror("malloc");
52 exit(EXIT_FAILURE);
53 }
54 *ip = rand();
55 // Be sure to set MAX_NUMS = 100 if you want to use the sorted array
56 // *ip = sorted[i];
57 int * ip2;
58 if (NULL == (ip2 = ost_insert(ost, ip)))
59 {
60 printf("ost_insert failed\n");
61 free(ip);
62 }
63 printf("inserting %d\n", *ip2);
64 }
65
66
67 // print the tree structure
68 ost_dump(ost, print_val);
69 fprintf(stderr, "black depth is %u\n", ost_black_depth(ost));
70
71 // Print the tree in value order with their ranks
72 struct ost_iterator * it;
73 struct ost_iterator * next;
74 for (next = it = ost_begin(ost); NULL != next; next = ost_next(it))
75 printf("%-16d%u\n", *((int *) ost_value(it)), ost_rank(it));
76 free(it);
77
78
79 // Get the first 5th and 10th elements
80 it = ost_select(ost, 1);
81 if (NULL == it)
82 {
83 printf("ost_select failed\n");
84 exit(EXIT_FAILURE);
85 }
86 printf("1st order statistic is %d\n", *((int *) ost_value(it)));
87 free(it);
88
89 it = ost_select(ost, 5);
90 if (NULL == it)
91 {
92 printf("ost_select failed\n");
93 exit(EXIT_FAILURE);
94 }
95 printf("5th order statistic is %d\n", *((int *) ost_value(it)));
96 free(it);
97
98 it = ost_select(ost, 10);
99 if (NULL == it)
100 {
101 printf("ost_select failed\n");
102 exit(EXIT_FAILURE);
103 }
104 printf("10th order statistic is %d\n", *((int *) ost_value(it)));
105 free(it);
106
107
108 // Free the whole tree
109 void * d;
110 it = ost_begin(ost);
111 while (d = ost_remove(it))
112 {
113 printf("removed %d\n", *((int *) d));
114 free(d);
115 }
116 free(it);
117 printf("After deletion the size is %u\n", ost_size(ost));
118 ost_dump(ost, print_val);
119
120
121
122 // This next should fail
123 it = ost_select(ost, 1);
124 if (NULL != it)
125 {
126 printf("ost_select failed\n");
127 exit(EXIT_FAILURE);
128 }
129
130 ost_delete(ost);
131 ost = NULL;
132
133 // This next should fail
134 it = ost_select(ost, 1);
135 if (NULL != it)
136 {
137 printf("ost_select failed\n");
138 exit(EXIT_FAILURE);
139 }
140
141 exit(EXIT_SUCCESS);
142 }