BioDynaMo  v1.03.58-27764645
algorithm.h
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------
2 //
3 // Copyright (C) 2021 CERN & University of Surrey for the benefit of the
4 // BioDynaMo collaboration. All Rights Reserved.
5 //
6 // Licensed under the Apache License, Version 2.0 (the "License");
7 // you may not use this file except in compliance with the License.
8 //
9 // See the LICENSE file distributed with this work for details.
10 // See the NOTICE file distributed with this work for additional information
11 // regarding copyright ownership.
12 //
13 // -----------------------------------------------------------------------------
14 
15 #ifndef CORE_ALGORITHM_H_
16 #define CORE_ALGORITHM_H_
17 
18 #include <cmath>
19 #include <cstdint>
20 
21 namespace bdm {
22 
23 // -----------------------------------------------------------------------------
26 template <typename T>
27 void InPlaceParallelPrefixSum(T& v, uint64_t n) {
28  if (n < 2) {
29  return;
30  }
31 
32  // upsweep
33  uint64_t logn = static_cast<uint64_t>(std::ceil(std::log2(n)));
34  for (uint64_t d = 0; d < logn; ++d) {
35  uint64_t stride = 1 << (d + 1);
36  uint64_t delta = 1 << d;
37 
38 #pragma omp parallel for
39  for (uint64_t i = delta - 1; i < n - delta; i += stride) {
40  v[i + delta] += v[i];
41  }
42  }
43 
44  // downsweep
45  for (uint64_t d = 0; d < logn - 1; ++d) {
46  uint64_t stride = 1 << (logn - d - 1);
47  uint64_t delta = 1 << (logn - d - 2);
48 
49 #pragma omp parallel for
50  for (uint64_t i = stride - 1; i < n - delta; i += stride) {
51  v[i + delta] += v[i];
52  }
53  }
54 }
55 
56 // -----------------------------------------------------------------------------
60 template <typename T>
61 void ExclusivePrefixSum(T* v, uint64_t n) {
62  auto tmp = (*v)[0];
63  (*v)[0] = 0;
64  for (uint64_t i = 1; i <= n; ++i) {
65  auto result = (*v)[i - 1] + tmp;
66  tmp = (*v)[i];
67  (*v)[i] = result;
68  }
69 }
70 
71 // -----------------------------------------------------------------------------
72 // if search_val is found in container, return right-most occurence.
73 // If not return the index of the right-most element that is smaller.
74 // If no smaller element exists, return element at index 0
75 template <typename TSearch, typename TContainer>
76 uint64_t BinarySearch(const TSearch& search_val, const TContainer& container,
77  uint64_t from, uint64_t to) {
78  if (to <= from) {
79  if (container[from] != search_val && from > 0) {
80  // if (from < container.size() && container[from] != search_val && from >
81  // 0) {
82  from--;
83  }
84  return from;
85  }
86 
87  auto m = (from + to) / 2;
88  if (container[m] == search_val) {
89  if (m + 1 <= to && container[m + 1] == search_val) {
90  return BinarySearch(search_val, container, m + 1, to);
91  }
92  return m;
93  } else if (container[m] > search_val) {
94  return BinarySearch(search_val, container, from, m);
95  } else {
96  return BinarySearch(search_val, container, m + 1, to);
97  }
98 }
99 
100 } // namespace bdm
101 
102 #endif // CORE_ALGORITHM_H_
bdm
Definition: agent.cc:39
bdm::InPlaceParallelPrefixSum
void InPlaceParallelPrefixSum(T &v, uint64_t n)
Definition: algorithm.h:27
bdm::ExclusivePrefixSum
void ExclusivePrefixSum(T *v, uint64_t n)
Definition: algorithm.h:61
bdm::BinarySearch
uint64_t BinarySearch(const TSearch &search_val, const TContainer &container, uint64_t from, uint64_t to)
Definition: algorithm.h:76