BRL-CAD
bu_redblack.c
Go to the documentation of this file.
1 /* T E S T _ R B T R E E . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2012-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @file bu_redblack.c
21  * Test unit for Red - Black Tree API
22  */
23 
24 #include "common.h"
25 
26 /* system headers */
27 #include <stdlib.h>
28 #include <stdio.h>
29 
30 /* interface headers */
31 #include "bu.h"
32 #include "./rb_internals.h"
33 
34 
35 /**
36  * Generic Comparison function that internally casts
37  * parameters to integers.
38  *
39  * Comment to be deleted if considered useless.
40  */
41 static int
42 compareFunc(const void* a, const void* b)
43 {
44  if (*(int*)a > *(int*)b) return (1);
45  if (*(int*)a < *(int*)b) return (-1);
46  return (0);
47 }
48 
49 
50 /**
51  * Function to be applied to every node of the
52  * red-black tree.
53  */
54 static void
55 displayNode(void* data, int dep)
56 {
57  printf("Depth = %d Value = %s, ", dep, (char*)data);
58 }
59 
60 
61 int
62 main(int ac, char *av[])
63 {
64  struct bu_rb_tree *testTree;
65  void *searchedValue;
66  const char *sources[] = {"h", "e", "a", "l", "l", "o"};
67  int i = 0;
68  int passed = 0;
69 
70  if (ac > 1) {
71  printf("uh oh, unexpected args after %s\n", av[0]);
72  return 1;
73  }
74 
75  testTree = bu_rb_create1("TestingTree", BU_RB_COMPARE_FUNC_CAST_AS_FUNC_ARG(compareFunc));
76  for (i = 0; i < 6; i++)
77  bu_rb_insert(testTree, (void *)sources[i]);
78 
79  printf("SEARCH TEST: \n\tSEARCHING AN EXISTING VALUE:\n");
80  searchedValue = bu_rb_search(testTree, 0, (void *)"h");
81 
82  if (searchedValue == NULL) {
83  printf("\t\t\t[FAILED]\n\t\t\tShould be h \n");
84  } else {
85  printf("\t\t\t[PASSED]\n");
86  passed++;
87  }
88 
89  printf("\tSEARCHING A NONEXISTENT VALUE:\n");
90  searchedValue = bu_rb_search(testTree, 0, (void *)"not");
91 
92  if (searchedValue == 0) {
93  printf("\t\t\t[PASSED]\n");
94  passed++;
95  } else {
96  printf("\t\t\t[FAILED]\n\t\t\tShould be NULL\n");
97  }
98 
99  printf("DELETE TEST: \n\tDELETING AN EXISTENT VALUE:\n");
100  searchedValue = bu_rb_search(testTree, 0, (void *)"a");
101  bu_rb_delete(testTree, 0);
102 
103  printf("\tSEARCHING THE SAME VALUE AFTER DELETION \n");
104  searchedValue = bu_rb_search(testTree, 0, (void *)"a");
105 
106  if (searchedValue == 0) {
107  printf("\t\t\t[PASSED]\n");
108  passed++;
109  } else {
110  printf("\t\t\t[FAILED]\n\t\t\tShould be NULL\n");
111  }
112 
113  /* user tests */
114  printf("RED-BLACK TREE WALKING TESTS :\n");
115 
116  printf("\nPREORDER:\n");
117  bu_rb_walk(testTree, 0, BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(displayNode), 0);
119  searchedValue = bu_rb_search(testTree, 0, (void *)"h");
120 
121  printf("\nPREORDER AFTER SEARCH:\n");
122  bu_rb_walk(testTree, 0, BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(displayNode), 0);
124 
125  printf("\nINORDER:\n");
126  bu_rb_walk(testTree, 0, BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(displayNode), 1);
128 
129  printf("\nPOSTORDER\n");
130  bu_rb_walk(testTree, 0, BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(displayNode), 2);
132 
133  if (passed != 3)
134  return 1;
135  return 0;
136 }
137 
138 
139 /*
140  * Local Variables:
141  * mode: C
142  * tab-width: 8
143  * indent-tabs-mode: t
144  * c-file-style: "stroustrup"
145  * End:
146  * ex: shiftwidth=4 tabstop=8
147  */
int main(int ac, char *av[])
Definition: bu_redblack.c:62
Definition: rb.h:109
void * bu_rb_search(struct bu_rb_tree *tree, int order, void *data)
Definition: rb_search.c:67
struct bu_rb_tree * bu_rb_create1(const char *description, int(*compare_func)(void))
Definition: rb_create.c:102
#define BU_RB_WALK_FUNC_CAST_AS_FUNC_ARG(_func)
Definition: rb.h:558
Header file for the BRL-CAD common definitions.
COMPLEX data[64]
Definition: fftest.c:34
void bu_rb_diagnose_tree(struct bu_rb_tree *tree, int order, int trav_type)
Definition: rb_diag.c:71
#define BU_RB_COMPARE_FUNC_CAST_AS_FUNC_ARG(_func)
Definition: rb.h:254
void bu_rb_delete(struct bu_rb_tree *tree, int order)
Definition: rb_delete.c:149
int bu_rb_insert(struct bu_rb_tree *tree, void *data)
Definition: rb_insert.c:150
void bu_rb_walk(struct bu_rb_tree *tree, int order, void(*visit)(void), int trav_type)
Definition: rb_walk.c:238