NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
sum_tree_inl.h
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 #pragma once
29 
30 namespace nvbio {
31 
32 // return the number of nodes corresponding to a given number of leaves
33 //
34 template <typename Iterator>
37 {
38  const uint32 log_size = nvbio::log2( size );
39  const uint32 padded_size =
40  (1u << log_size) < size ?
41  1u << (log_size+1u) :
42  1u << log_size;
43 
44  return padded_size * 2u - 1u;
45 }
46 
47 // constructor
48 //
49 template <typename Iterator>
52  m_cells( cells ),
53  m_size( size ),
54  m_padded_size(
55  (1u << nvbio::log2( size )) < size ?
56  1u << (nvbio::log2( size )+1u) :
57  1u << nvbio::log2( size ) )
58 {}
59 
60 // setup the tree structure
61 //
62 template <typename Iterator>
65 {
66  // zero out padding cells
67  for (uint32 i = m_size; i < m_padded_size; ++i)
68  m_cells[i] = zero;
69 
70  uint32 src = 0;
71 
72  for (uint32 n = m_padded_size; n >= 2; n >>= 1)
73  {
74  const uint32 dst = src + n;
75 
76  const uint32 m = n >> 1;
77  for (uint32 i = 0; i < m; ++i)
78  m_cells[ dst + i ] = (m_cells[ src + i*2 ] + m_cells[ src + i*2 + 1u ]);
79 
80  src += n;
81  }
82 }
83 
84 // increment a cell's value
85 //
86 template <typename Iterator>
89 {
90  uint32 dst = 0;
91  uint32 j = i;
92  for (uint32 m = m_padded_size; m >= 2; m >>= 1, j >>= 1)
93  {
94  m_cells[ dst + j ] += v;
95 
96  dst += m;
97  }
98 }
99 
100 // reset a cell's value
101 //
102 template <typename Iterator>
105 {
106  // sum the left & right values of each ancestor bottom-up
107  m_cells[ i ] = v;
108 
109  uint32 prev_base = 0u;
110  uint32 parent_base = m_padded_size;
111  uint32 parent = i >> 1;
112 
113  for (uint32 m = m_padded_size >> 1; parent_base + parent < nodes(); m >>= 1)
114  {
115  m_cells[ parent_base + parent ] =
116  m_cells[ prev_base + parent*2 ] +
117  m_cells[ prev_base + parent*2+1 ];
118 
119  prev_base = parent_base;
120  parent_base += m;
121  parent >>= 1;
122  }
123 }
124 
125 // sample a cell from a linear tree
126 //
127 template <typename Iterator>
129 uint32 sample(const SumTree<Iterator>& tree, const float value)
130 {
131  const uint32 padded_size = tree.padded_size();
132 
133  // compute the offset
134  uint32 node_base = padded_size*2u - 4u;
135  uint32 node_index = 0;
136 
137  float v = value;
138 
139  // choose the proper child of each internal node, from the root down to the leaves.
140  for (uint32 m = 2; m < padded_size; m *= 2)
141  {
142  // choose the proper node among the selected pair.
143  const float l = float(tree.cell( node_base + node_index ));
144  const float r = float(tree.cell( node_base + node_index + 1u ));
145  const float sum = float( l + r );
146 
147  if (sum == 0.0f)
148  node_index *= 2;
149  else
150  {
151  if (v * sum < l || r == 0.0f)
152  {
153  node_index = node_index * 2u;
154  v = nvbio::min( v * sum / l, 1.0f );
155  }
156  else
157  {
158  node_index = (node_index + 1u) * 2u;
159  v = nvbio::min( (v*sum - l) / r, 1.0f );
160  }
161  }
162 
163  node_base -= m*2;
164  }
165 
166  // level 0
167  const uint32 size = tree.size();
168  {
169  // choose the proper leaf among the selected pair.
170  const float l = node_index < size ? float(tree.cell( node_index )) : 0.0f;
171  const float r = node_index + 1u < size ? float(tree.cell( node_index + 1u )) : 0.0f;
172  const float sum = float( l + r );
173 
174  node_index = (v * sum < l || r == 0.0f) ? node_index : node_index + 1u;
175  }
176 
177  // clamp the leaf index to the tree size
178  return node_index < size ? node_index : size - 1u;
179 }
180 
181 } // namespace nvbio