/proc/self/cwd/external/com_github_google_libprotobuf_mutator/src/weighted_reservoir_sampler.h
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2016 Google Inc. All rights reserved. |
2 | | // |
3 | | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | | // you may not use this file except in compliance with the License. |
5 | | // You may obtain a copy of the License at |
6 | | // |
7 | | // http://www.apache.org/licenses/LICENSE-2.0 |
8 | | // |
9 | | // Unless required by applicable law or agreed to in writing, software |
10 | | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | | // See the License for the specific language governing permissions and |
13 | | // limitations under the License. |
14 | | |
15 | | #ifndef SRC_WEIGHTED_RESERVOIR_SAMPLER_H_ |
16 | | #define SRC_WEIGHTED_RESERVOIR_SAMPLER_H_ |
17 | | |
18 | | #include <cassert> |
19 | | #include <random> |
20 | | |
21 | | namespace protobuf_mutator { |
22 | | |
23 | | // Algorithm pick one item from the sequence of weighted items. |
24 | | // https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao |
25 | | // |
26 | | // Example: |
27 | | // WeightedReservoirSampler<int> sampler; |
28 | | // for(int i = 0; i < size; ++i) |
29 | | // sampler.Pick(weight[i], i); |
30 | | // return sampler.GetSelected(); |
31 | | template <class T, class RandomEngine = std::default_random_engine> |
32 | | class WeightedReservoirSampler { |
33 | | public: |
34 | 0 | explicit WeightedReservoirSampler(RandomEngine* random) : random_(random) {} Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::WeightedReservoirSampler(std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul>*) Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::WeightedReservoirSampler(std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul>*) |
35 | | |
36 | 0 | void Try(uint64_t weight, const T& item) { |
37 | 0 | if (Pick(weight)) selected_ = item; |
38 | 0 | } Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Try(unsigned long, protobuf_mutator::(anonymous namespace)::MutationSampler::Result const&) Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Try(unsigned long, protobuf_mutator::ConstFieldInstance const&) |
39 | | |
40 | 0 | const T& selected() const { return selected_; } Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::selected() const Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::selected() const |
41 | | |
42 | 0 | bool IsEmpty() const { return total_weight_ == 0; } |
43 | | |
44 | | private: |
45 | 0 | bool Pick(uint64_t weight) { |
46 | 0 | if (weight == 0) return false; |
47 | 0 | total_weight_ += weight; |
48 | 0 | return weight == total_weight_ || std::uniform_int_distribution<uint64_t>( |
49 | 0 | 1, total_weight_)(*random_) <= weight; |
50 | 0 | } Unexecuted instantiation: mutator.cc:protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::(anonymous namespace)::MutationSampler::Result, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Pick(unsigned long) Unexecuted instantiation: protobuf_mutator::WeightedReservoirSampler<protobuf_mutator::ConstFieldInstance, std::__1::linear_congruential_engine<unsigned long, 48271ul, 0ul, 2147483647ul> >::Pick(unsigned long) |
51 | | |
52 | | T selected_ = {}; |
53 | | uint64_t total_weight_ = 0; |
54 | | RandomEngine* random_; |
55 | | }; |
56 | | |
57 | | } // namespace protobuf_mutator |
58 | | |
59 | | #endif // SRC_WEIGHTED_RESERVOIR_SAMPLER_H_ |