Go to the documentation of this file.
16 #ifndef FLEX_UTILS_TOP_N_GENERATOR_H_
17 #define FLEX_UTILS_TOP_N_GENERATOR_H_
38 inline bool operator()(
const T& lhs,
const T& rhs)
const {
return lhs < rhs; }
48 inline bool operator()(
const T& lhs,
const T& rhs)
const {
return rhs < lhs; }
53 template <
typename T,
typename CMP_T>
60 inline void push(
const T& val,
size_t idx) {
62 pq_.emplace(val, idx);
65 if (
pq_.top().val == val) {
67 }
else if (CMP_T()(
pq_.top().val, val)) {
70 pq_.emplace(
pq_.top().val, i);
73 pq_.emplace(val, idx);
76 if (
pq_.size() <
n_) {
77 pq_.emplace(val, idx);
82 pq_.emplace(val, idx);
83 auto cur = std::move(
pq_.top());
86 while (!
pq_.empty() &&
pq_.top().val == cur.val) {
98 while (!
pq_.empty()) {
99 indices.push_back(
pq_.top().idx);
108 values.resize(indices.size(),
pq_.top().val);
109 while (!
pq_.empty()) {
110 values.push_back(
pq_.top().val);
111 indices.push_back(
pq_.top().idx);
118 std::priority_queue<unit_t, std::vector<unit_t>, CMP_T>
pq_;
122 template <
typename T,
typename CMP_T>
130 std::vector<size_t>& indices) {
131 size_t size = input.size();
132 std::priority_queue<unit_t, std::vector<unit_t>, CMP_T> pq(CMP_T{});
133 for (
size_t i = 0; i < size; ++i) {
134 if (pq.size() <
n_) {
135 pq.emplace(input[i], i);
136 }
else if (CMP_T()(input[i], pq.top().val)) {
138 pq.emplace(input[i], i);
142 T top_val = pq.top().val;
144 for (
size_t i = 0; i < size; ++i) {
145 if (input[i] == top_val) {
146 indices.push_back(i);
149 while (!pq.empty() && pq.top().val == top_val) {
152 while (!pq.empty()) {
153 indices.push_back(pq.top().idx);
164 #endif // FLEX_UTILS_TOP_N_GENERATOR_H_
TopNGenerator(size_t n)
Definition: top_n_generator.h:58
std::vector< size_t > replicated_indices_
Definition: top_n_generator.h:119
Definition: top_n_generator.h:42
void generate_pairs(std::vector< T > &values, std::vector< size_t > &indices)
Definition: top_n_generator.h:104
InplaceTopNGenerator(size_t n)
Definition: top_n_generator.h:127
Definition: adj_list.h:23
bool operator()(const T &lhs, const T &rhs) const
Definition: top_n_generator.h:48
bool operator()(const T &lhs, const T &rhs) const
Definition: top_n_generator.h:38
TopNUnit(const T &val_, size_t idx_)
Definition: top_n_generator.h:26
Definition: top_n_generator.h:123
size_t n_
Definition: top_n_generator.h:159
void generate_indices(std::vector< size_t > &indices)
Definition: top_n_generator.h:95
T val
Definition: top_n_generator.h:27
size_t n_
Definition: top_n_generator.h:117
Definition: top_n_generator.h:32
bool operator()(const elem_t &lhs, const elem_t &rhs) const
Definition: top_n_generator.h:44
bool operator()(const elem_t &lhs, const elem_t &rhs) const
Definition: top_n_generator.h:34
void generate_indices(const std::vector< T > &input, std::vector< size_t > &indices)
Definition: top_n_generator.h:129
Definition: top_n_generator.h:25
Definition: top_n_generator.h:54
size_t idx
Definition: top_n_generator.h:28
void push(const T &val, size_t idx)
Definition: top_n_generator.h:60
std::priority_queue< unit_t, std::vector< unit_t >, CMP_T > pq_
Definition: top_n_generator.h:118