ROSE  0.9.9.109
Combinatorics.h
1 #ifndef ROSE_Combinatorics_H
2 #define ROSE_Combinatorics_H
3 
4 #include "LinearCongruentialGenerator.h"
5 
6 #include <algorithm>
7 #include <cassert>
8 #include <list>
9 #include <stdint.h>
10 #include <string>
11 #include <vector>
12 
13 namespace Combinatorics {
14 
16 template<typename T>
17 static T
18 factorial(T n)
19 {
20  T retval = 1;
21  while (n>1) {
22  T next = retval * n--;
23  assert(next>retval); // overflow
24  retval = next;
25  }
26  return retval;
27 }
28 
31 ROSE_UTIL_API bool flip_coin();
32 
38 template<typename T>
39 static void
40 permute(std::vector<T> &values/*in,out*/, uint64_t pn, size_t sz=(size_t)(-1))
41 {
42  if ((size_t)(-1)==sz)
43  sz = values.size();
44  assert(sz<=values.size());
45  assert(pn<factorial(sz));
46  for (size_t i=0; i<sz; ++i) {
47  uint64_t radix = sz - i;
48  uint64_t idx = pn % radix;
49  std::swap(values[i+idx], values[i]);
50  pn /= radix;
51  }
52 }
53 
58 template<typename T>
59 void
60 shuffle(std::vector<T> &vector, size_t nitems=(size_t)(-1), size_t limit=(size_t)(-1), LinearCongruentialGenerator *lcg=NULL)
61 {
62  static LinearCongruentialGenerator my_lcg;
63  if (!lcg)
64  lcg = &my_lcg;
65  nitems = std::min(nitems, vector.size());
66  limit = std::min(limit, nitems);
67 
68  for (size_t i=0; i<limit; ++i)
69  std::swap(vector[i], vector[lcg->next()%nitems]);
70 }
71 
76 ROSE_UTIL_API std::vector<uint8_t> sha1_digest(const uint8_t *data, size_t size);
77 ROSE_UTIL_API std::vector<uint8_t> sha1_digest(const std::vector<uint8_t> &data);
78 ROSE_UTIL_API std::vector<uint8_t> sha1_digest(const std::string &data);
84 ROSE_UTIL_API uint64_t fnv1a64_digest(const uint8_t *data, size_t size);
85 ROSE_UTIL_API uint64_t fnv1a64_digest(const std::vector<uint8_t> &data);
86 ROSE_UTIL_API uint64_t fnv1a64_digest(const std::string &data);
94 ROSE_UTIL_API std::string digest_to_string(const uint8_t *data, size_t size);
95 ROSE_UTIL_API std::string digest_to_string(const std::vector<uint8_t> &digest);
96 ROSE_UTIL_API std::string digest_to_string(const std::string &data);
99 } // namespace
100 #endif
Linear congruential generator.