Empirical
vector_utils.h
Go to the documentation of this file.
1 
11 #ifndef EMP_VECTOR_UTILS_H
12 #define EMP_VECTOR_UTILS_H
13 
14 #include "../base/vector.h"
15 
16 namespace emp {
17 
19  template <typename T>
20  int FindValue(const emp::vector<T> vec, const T & val, size_t start_pos=0) {
21  for (size_t i = start_pos; i < vec.size(); i++) {
22  if (vec[i] == val) return (int) i;
23  }
24  return -1;
25  }
26 
28  template <typename T>
29  bool Has(const emp::vector<T> vec, const T & val) {
30  return FindValue(vec, val) >= 0;
31  }
32 
34  template <typename T>
35  void Print(const emp::vector<T> & v, std::ostream & os=std::cout, const std::string & spacer=" ") {
36  for (size_t id = 0; id < v.size(); id++) {
37  if (id) os << spacer; // Put a space before second element and beyond.
38  os << v[id];
39  }
40  }
41 
45  template <typename T>
46  size_t FindIndex(const T & v,
47  const std::function<bool(typename T::value_type, typename T::value_type)> & fun) {
48  emp_assert(v.size() > 0);
49  using v_type = typename T::value_type;
50  v_type best_val = v[0];
51  size_t best_index = 0;
52  for (size_t i = 1; i < v.size(); i++) {
53  if (fun(v[i], best_val)) {
54  best_val = v[i];
55  best_index = i;
56  }
57  }
58  return best_index;
59  }
60 
62  template <typename T>
63  size_t FindMinIndex(const T & v) {
64  using v_type = typename T::value_type;
65  return FindIndex(v, [](v_type a, v_type b){ return a < b; });
66  }
67 
69  template <typename T>
70  size_t FindMaxIndex(const T & v) {
71  using v_type = typename T::value_type;
72  return FindIndex(v, [](v_type a, v_type b){ return a > b; });
73  }
74 
75 
77  template <typename T>
78  T Sum(const emp::vector<T> & v) {
79  T sum = 0;
80  for (auto x : v) sum += x;
81  return sum;
82  }
83 
85  template <typename T>
86  T Product(const emp::vector<T> & v) {
87  T product = 1;
88  for (auto x : v) product *= x;
89  return product;
90  }
91 
93  template <typename T, typename... Ts>
94  void Sort(emp::vector<T> & v, Ts... args) {
95  std::sort(v.begin(), v.end(), std::forward<Ts>(args)...);
96  }
97 
100  template <typename T>
101  emp::vector<T> Slice(emp::vector<T> vec, int start, int stop) {
102  emp_assert(start < stop, start, stop);
103  emp_assert(start < (int)vec.size(), start, vec.size());
104  emp_assert(stop <= (int)vec.size(), stop, vec.size());
105 
106  emp::vector<T> new_vec;
107  for (int i = start; i < stop; i++){
108  new_vec.push_back(vec[i]);
109  }
110  return new_vec;
111  }
112 
114  constexpr size_t tree_left(size_t id) { return id*2+1; }
115  constexpr size_t tree_right(size_t id) { return id*2+2; }
116  constexpr size_t tree_parent(size_t id) { return (id-1)/2; }
117 
118  // == Heap manipulation ==
119 
121  template <typename T>
122  bool Heapify(emp::vector<T> & v, size_t id) {
123  const size_t id_left = tree_left(id);
124  if (id_left >= v.size()) return false; // Nothing left to heapify.
125 
126  const T val = v[id];
127  const T val_left = v[id_left];
128 
129  const size_t id_right = tree_right(id);
130  if (id_right < v.size()) {
131  const T val_right = v[id_right];
132  if (val_right > val_left && val_right > val) {
133  v[id] = val_right;
134  v[id_right] = val;
135  Heapify(v, id_right);
136  return true;
137  }
138  }
139 
140  if (val_left > val) {
141  v[id] = val_left;
142  v[id_left] = val;
143  Heapify(v, id_left);
144  return true;
145  }
146 
147  return false; // No changes need to be made.
148  }
149 
151  template <typename T>
153  size_t id = v.size();
154  while (id-- > 0) emp::Heapify(v, id);
155  }
156 
158  template <typename T>
160  emp_assert(v.size(), "Cannot extract from an empty heap!");
161  T out = v[0];
162  if (v.size() > 1) {
163  const size_t last_pos = v.size() - 1;
164  v[0] = v[last_pos];
165  v.resize(last_pos);
166  Heapify(v,0);
167  }
168  else v.resize(0);
169  return out;
170  }
171 
173  template <typename T>
174  void HeapInsert(emp::vector<T> & v, T val) {
175  size_t pos = v.size();
176  v.push_back(val);
177  while (pos > 0) {
178  pos = tree_parent(pos);
179  if (!Heapify(v,pos)) break;
180  }
181  }
182 
183 }
184 
185 #endif
void Sort(emp::vector< T > &v, Ts...args)
A quick shortcut for sorting a vector.
Definition: vector_utils.h:94
iterator end() noexcept
Definition: vector.h:155
void HeapInsert(emp::vector< T > &v, T val)
Insert a new element into a heap.
Definition: vector_utils.h:174
bool Heapify(emp::vector< T > &v, size_t id)
Heapify an individual node in a vector.
Definition: vector_utils.h:122
void push_back(PB_Ts &&...args)
Definition: vector.h:189
size_t FindMaxIndex(const T &v)
Find the index with the maximal value (picks first in cases of a tie).
Definition: vector_utils.h:70
size_t size() const
Definition: vector.h:151
T Product(const emp::vector< T > &v)
Multiply all of the contents of a vector.
Definition: vector_utils.h:86
constexpr size_t tree_left(size_t id)
Tree manipulation in vectors.
Definition: vector_utils.h:114
emp::vector< T > Slice(emp::vector< T > vec, int start, int stop)
Definition: vector_utils.h:101
T HeapExtract(emp::vector< T > &v)
Extraxt maximum element from a heap.
Definition: vector_utils.h:159
bool Has(const MAP_T &in_map, const KEY_T &key)
Take any map type, and run find to determine if a key is present.
Definition: map_utils.h:21
void resize(size_t new_size)
Definition: vector.h:161
iterator begin() noexcept
Definition: vector.h:153
constexpr size_t tree_right(size_t id)
Definition: vector_utils.h:115
int FindValue(const emp::vector< T > vec, const T &val, size_t start_pos=0)
Return the first position of a value in a vector (or -1 if none exists)
Definition: vector_utils.h:20
If we are in emscripten, make sure to include the header.
Definition: array.h:37
size_t FindIndex(const T &v, const std::function< bool(typename T::value_type, typename T::value_type)> &fun)
Definition: vector_utils.h:46
#define emp_assert(...)
Definition: assert.h:199
typename internal::ip_sort< T >::result sort
Definition: IntPack.h:193
size_t FindMinIndex(const T &v)
Find the index with the minimal value (picks first in cases of a tie).
Definition: vector_utils.h:63
constexpr size_t tree_parent(size_t id)
Definition: vector_utils.h:116
void Print(const emp::vector< T > &v, std::ostream &os=std::cout, const std::string &spacer=" ")
Print the contects of a vector.
Definition: vector_utils.h:35
std::enable_if<!emp::is_ptr_type< typename C::value_type >::value &&std::is_scalar< typename C::value_type >::value, typename C::value_type >::type Sum(C &elements)
Definition: stats.h:33