-
Notifications
You must be signed in to change notification settings - Fork 107
/
Copy pathshuffle_weighted.qbk
84 lines (58 loc) · 3.4 KB
/
shuffle_weighted.qbk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
[/ File shuffle_weighted.qbk]
[section:shuffle_weighted shuffle_weighted]
[/license
Copyright (c) 2017 Alexander Zaitsev
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
]
The header file 'shuffle_weighted.hpp' contains shuffle_weighted algorithm. There is range-based version.
The algorithms rearrange the elements randomly with weights, using random number generator.
The routine `shuffle_weighted` takes a item sequence and a weight sequences.
The routines come in 2 forms; the first one takes two iterators to define the item range, one iterator to define the beginning of weight range and random generator. The second form takes range to define the item sequence, range to define weight sequence and random generator.
[heading interface]
There are two versions of algorithms:
1) takes four iterators and random generator.
2) takes two ranges and random generator.
Also there are two versions for old compilers (which doesn't support C++11 or higher standard).
Difference is only one: C++11 or higher version takes UniformRandomBitGenerator parameter as universal reference, version for old compiler takes UniformRandomBitGenerator as reference.
For C++11 or higher compilers:
``
template<typename ForwardIterator1, typename ForwardIterator2, typename UniformRandomBitGenerator>
void shuffle_weighted(ForwardIterator1 item_begin, ForwardIterator1 item_end, ForwardIterator2 weight_begin, ForwardIterator2 weight_end, UniformRandomBitGenerator&& g);
template<typename Range1, typename Range2, typename UniformRandomBitGenerator>
void shuffle_weighted(Range1& item_range, Range2& weight_range, UniformRandomBitGenerator&& g);
``
For old compilers:
``
template<typename ForwardIterator1, typename ForwardIterator2, typename UniformRandomBitGenerator>
void shuffle_weighted(ForwardIterator1 item_begin, ForwardIterator1 item_end, ForwardIterator2 weight_begin, ForwardIterator2 weight_end, UniformRandomBitGenerator& g);
template<typename Range1, typename Range2, typename UniformRandomBitGenerator>
void shuffle_weighted(Range1& item_range, Range2& weight_range, UniformRandomBitGenerator& g);
``
[heading Examples]
Given the containers:
std::vector<int> emp_vec, emp_order,
std::vector<int> one{1}, one_order{1},
std::vector<int> two{1, 2}, two_order{1, 2}, then
``
shuffle_weighted(emp_vec, emp_order)) --> no changes
shuffle_weighted(one, one_order)) --> no changes
shuffle_weighted(two, two_order)) --> weighted-random result
``
[heading Iterator Requirements]
`shuffle_weighted` works on Forawrd-compatible iterators (for item and weight sequences both).
[heading Complexity]
All of the variants of `shuffle_weighted` runs in ['O(N^2)] time.
[heading Exception Safety]
All of the variants of `shuffle_weighted` takes their parameters by iterators or reference, and do not depend upon any global state. Therefore, all the routines in this file provide the strong exception guarantee.
[heading Notes]
* Weights should be bigger than 0.
* If ItemSequence and WeightSequence sizes are different, behavior is undefined.
* `shuffle_weighted` works also on empty sequences.
* Be careful: weights can be changed inside the function.
[endsect]
[/ File shuffle_weighted.qbk
Copyright 2017 Alexander Zaitsev
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt).
]