NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sum_tree_test.cpp
Go to the documentation of this file.
1 /*
2  * nvbio
3  * Copyright (c) 2011-2014, NVIDIA CORPORATION. All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  * * Redistributions of source code must retain the above copyright
8  * notice, this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of the NVIDIA CORPORATION nor the
13  * names of its contributors may be used to endorse or promote products
14  * derived from this software without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL NVIDIA CORPORATION BE LIABLE FOR ANY
20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  */
27 
28 // sum_tree_test.cpp
29 //
30 
31 #include <nvbio/basic/sum_tree.h>
32 #include <nvbio/basic/console.h>
33 #include <stdio.h>
34 #include <stdlib.h>
35 #include <vector>
36 
37 namespace nvbio {
38 
39 int sum_tree_test()
40 {
41  printf("sum tree... started\n");
42  // 128 leaves
43  {
44  const uint32 n_leaves = 128;
45 
46  std::vector<int32> vec( SumTree<uint32*>::node_count( n_leaves ) );
47 
48  SumTree<int32*> sum_tree( n_leaves, &vec[0] );
49 
50  // test 1
51  for (uint32 i = 0; i < n_leaves; ++i)
52  vec[i] = i;
53  {
54  sum_tree.setup();
55 
56  uint32 c0 = sample( sum_tree, 0.0f );
57  uint32 c1 = sample( sum_tree, 0.5f );
58  uint32 c2 = sample( sum_tree, 1.0f );
59 
60  if (c0 != 1 || c1 != 90 || c2 != 127)
61  {
62  log_error( stderr, "error in test(1):\n c(0.0) = %u (!= 1)\n c(0.5) = %u (!= 90) c(1.0) = %u (!= 127)\n", c0, c1, c2 );
63  exit(1);
64  }
65  }
66 
67  // test 2
68  for (uint32 i = 0; i < n_leaves; ++i)
69  vec[i] = i < n_leaves/2 ? 0 : 1;
70  {
71  sum_tree.setup();
72 
73  uint32 c0 = sample( sum_tree, 0.0f );
74  uint32 c1 = sample( sum_tree, 0.5f );
75  uint32 c2 = sample( sum_tree, 1.0f );
76 
77  if (c0 != 64 || c1 != 96 || c2 != 127)
78  {
79  log_error( stderr, "error in test(2):\n c(0.0) = %u (!= 64)\n c(0.5) = %u (!= 90) c(1.0) = %u (!= 127)\n", c0, c1, c2 );
80  return 1;
81  }
82  }
83 
84  // test 3
85  for (uint32 i = 0; i < n_leaves; ++i)
86  vec[i] = i < n_leaves/2 ? 1 : 0;
87  {
88  sum_tree.setup();
89 
90  uint32 c0 = sample( sum_tree, 0.0f );
91  uint32 c1 = sample( sum_tree, 0.5f );
92  uint32 c2 = sample( sum_tree, 1.0f );
93 
94  if (c0 != 0 || c1 != 32 || c2 != 63)
95  {
96  log_error( stderr, "error in test(3):\n c(0.0) = %u (!= 0)\n c(0.5) = %u (!= 32) c(1.0) = %u (!= 63)\n", c0, c1, c2 );
97  exit(1);
98  }
99  }
100  }
101  // 80 leaves
102  {
103  const uint32 n_leaves = 80;
104 
105  std::vector<int32> vec( SumTree<uint32*>::node_count( n_leaves ) );
106 
107  SumTree<int32*> sum_tree( n_leaves, &vec[0] );
108 
109  if (sum_tree.padded_size() != 128)
110  {
111  log_error( stderr, "error: wrong padded size: %u != 128\n", sum_tree.padded_size() );
112  exit(1);
113  }
114 
115  // test 4
116  for (uint32 i = 0; i < n_leaves; ++i)
117  vec[i] = i < n_leaves/2 ? 0 : 1;
118  {
119  sum_tree.setup();
120 
121  uint32 c0 = sample( sum_tree, 0.0f );
122  uint32 c1 = sample( sum_tree, 0.5f );
123  uint32 c2 = sample( sum_tree, 1.0f );
124 
125  if (c0 != 40 || c1 != 60 || c2 != 79)
126  {
127  log_error( stderr, "error in test(3):\n c(0.0) = %u (!= 40)\n c(0.5) = %u (!= 60) c(1.0) = %u (!= 79)\n", c0, c1, c2 );
128  exit(1);
129  }
130  }
131 
132  // test 5
133  for (uint32 i = 0; i < n_leaves; ++i)
134  vec[i] = i < n_leaves/2 ? 1 : 0;
135  {
136  sum_tree.setup();
137 
138  uint32 c0 = sample( sum_tree, 0.0f );
139  uint32 c1 = sample( sum_tree, 0.5f );
140  uint32 c2 = sample( sum_tree, 1.0f );
141 
142  if (c0 != 0 || c1 != 20 || c2 != 39)
143  {
144  log_error( stderr, "error in test(5):\n c(0.0) = %u (!= 0)\n c(0.5) = %u (!= 20) c(1.0) = %u (!= 39)\n", c0, c1, c2 );
145  exit(1);
146  }
147  }
148 
149  // remove the last leaf
150  sum_tree.add( 39, -1 );
151 
152  // test 6
153  uint32 c = sample( sum_tree, 1.0f );
154  if (c != 38)
155  {
156  log_error( stderr, "error in test(6):\n c(1.0) = %u (!= 38)\n", c );
157  exit(1);
158  }
159 
160  // remove one more leaf
161  sum_tree.add( 38, -1 );
162 
163  c = sample( sum_tree, 1.0f );
164  if (c != 37)
165  {
166  log_error( stderr, "error in test(7):\n c(1.0) = %u (!= 37)\n", c );
167  exit(1);
168  }
169 
170  // add it back
171  sum_tree.add( 38, 1 );
172 
173  // and remove it using set
174  sum_tree.set( 38, 0 );
175 
176  c = sample( sum_tree, 1.0f );
177  if (c != 37)
178  {
179  log_error( stderr, "error in test(8):\n c(1.0) = %u (!= 37)\n", c );
180  exit(1);
181  }
182 
183  // remove the first ten leaves
184  for (uint32 i = 0; i < 10; ++i)
185  {
186  sum_tree.set( i, 0 );
187 
188  c = sample( sum_tree, 0.0f );
189  if (c != i+1)
190  {
191  log_error( stderr, "error in test(9):\n c(0.0) = %u (!= %u)\n", c, i );
192  exit(1);
193  }
194  }
195  }
196  printf("sum tree... done\n");
197 
198  return 0;
199 }
200 
201 }
Generated on Wed Feb 25 2015 08:32:52 for NVBIO by   doxygen 1.8.4