NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
algorithms.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 
32 #pragma once
33 
34 #include <nvbio/basic/types.h>
35 
36 namespace nvbio {
37 
48 
54 template <typename Iterator, typename Predicate>
56  Iterator begin,
57  const uint32 n,
58  const Predicate predicate)
59 {
60  // if the range has a size of zero, let's just return the intial element
61  if (n == 0)
62  return begin;
63 
64  // check whether this segment contains only 0s or only 1s
65  if (predicate( begin[0] ) == predicate( begin[n-1] ))
66  return predicate( begin[0] ) ? begin + n : begin;
67 
68  // perform a binary search over the given range
69  uint32 count = n;
70 
71  while (count > 0)
72  {
73  const uint32 count2 = count / 2;
74 
75  Iterator mid = begin + count2;
76 
77  if (predicate( *mid ) == false)
78  begin = ++mid, count -= count2 + 1;
79  else
80  count = count2;
81  }
82  return begin;
83 }
84 
90 template <typename Iterator, typename Value, typename index_type>
92  const Value x,
93  Iterator begin,
94  const index_type n)
95 {
96  // if the range has a size of zero, let's just return the intial element
97  if (n == 0)
98  return begin;
99 
100  // check whether this segment is all left or right of x
101  if (x < begin[0])
102  return begin;
103 
104  if (begin[n-1] < x)
105  return begin + n;
106 
107  // perform a binary search over the given range
108  index_type count = n;
109 
110  while (count > 0)
111  {
112  const index_type count2 = count / 2;
113 
114  Iterator mid = begin + count2;
115 
116  if (*mid < x)
117  begin = ++mid, count -= count2 + 1;
118  else
119  count = count2;
120  }
121  return begin;
122 }
123 
129 template <typename Iterator, typename Value, typename index_type>
131  const Value x,
132  Iterator begin,
133  const index_type n)
134 {
135  // if the range has a size of zero, let's just return the intial element
136  //if (n == 0)
137  // return begin;
138 
139  // check whether this segment is all left or right of x
140  //if (x < begin[0])
141  // return begin;
142 
143  //if (begin[n-1] <= x)
144  // return begin + n;
145 
146  index_type count = n;
147 
148  while (count > 0)
149  {
150  const index_type step = count / 2;
151 
152  Iterator it = begin + step;
153 
154  if (!(x < *it))
155  {
156  begin = ++it;
157  count -= step + 1;
158  }
159  else
160  count = step;
161  }
162  return begin;
163 }
164 
170 template <typename Iterator, typename Value, typename index_type>
172  const Value x,
173  Iterator begin,
174  const index_type n)
175 {
176  return uint32( lower_bound( x, begin, n ) - begin );
177 }
178 
184 template <typename Iterator, typename Value, typename index_type>
186  const Value x,
187  Iterator begin,
188  const index_type n)
189 {
190  return index_type( upper_bound( x, begin, n ) - begin );
191 }
192 
201 template <
202  typename input_iterator1,
203  typename input_iterator2,
204  typename output_iterator>
206 void merge(
207  input_iterator1 first1,
208  input_iterator1 end1,
209  input_iterator2 first2,
210  input_iterator2 end2,
211  output_iterator output)
212 {
213  while (first1 != end1 &&
214  first2 != end2)
215  {
216  if (*first2 < *first1)
217  {
218  *output = *first2;
219 
220  ++first2;
221  }
222  else
223  {
224  *output = *first1;
225 
226  ++first1;
227  }
228 
229  ++output;
230  }
231 
232  while (first1 != end1)
233  {
234  *output = *first1;
235 
236  ++first1;
237  ++output;
238  }
239 
240  while (first2 != end2)
241  {
242  *output = *first2;
243 
244  ++first2;
245  ++output;
246  }
247 }
248 
257 template <
258  typename key_iterator1,
259  typename key_iterator2,
260  typename value_iterator1,
261  typename value_iterator2,
262  typename key_iterator,
263  typename value_iterator>
266  key_iterator1 first1,
267  key_iterator1 end1,
268  key_iterator2 first2,
269  key_iterator2 end2,
270  value_iterator1 values1,
271  value_iterator2 values2,
272  key_iterator output_keys,
273  value_iterator output_values)
274 {
275  while (first1 != end1 &&
276  first2 != end2)
277  {
278  if (*first2 < *first1)
279  {
280  *output_keys = *first2;
281  *output_values = *values2;
282 
283  ++first2;
284  ++values2;
285  }
286  else
287  {
288  *output_keys = *first1;
289  *output_values = *values1;
290 
291  ++first1;
292  ++values1;
293  }
294 
295  ++output_keys;
296  ++output_values;
297  }
298 
299  while (first1 != end1)
300  {
301  *output_keys = *first1;
302  *output_values = *values1;
303 
304  ++first1;
305  ++values1;
306  ++output_keys;
307  ++output_values;
308  }
309 
310  while (first2 != end2)
311  {
312  *output_keys = *first2;
313  *output_values = *values2;
314 
315  ++first2;
316  ++values2;
317  ++output_keys;
318  ++output_values;
319  }
320 }
321 
322 } // namespace nvbio