Flex  0.17.9
top_n_generator.h
Go to the documentation of this file.
1 
16 #ifndef FLEX_UTILS_TOP_N_GENERATOR_H_
17 #define FLEX_UTILS_TOP_N_GENERATOR_H_
18 
19 #include <queue>
20 #include <vector>
21 
22 namespace gs {
23 
24 template <typename T>
25 struct TopNUnit {
26  TopNUnit(const T& val_, size_t idx_) : val(val_), idx(idx_) {}
27  T val;
28  size_t idx;
29 };
30 
31 template <typename T>
32 struct TopNAscCmp {
34  inline bool operator()(const elem_t& lhs, const elem_t& rhs) const {
35  return lhs.val < rhs.val;
36  }
37 
38  inline bool operator()(const T& lhs, const T& rhs) const { return lhs < rhs; }
39 };
40 
41 template <typename T>
42 struct TopNDescCmp {
44  inline bool operator()(const elem_t& lhs, const elem_t& rhs) const {
45  return rhs.val < lhs.val;
46  }
47 
48  inline bool operator()(const T& lhs, const T& rhs) const { return rhs < lhs; }
49 };
50 
51 // CMP_T lhs > rhs is desc
52 // CMP_T lhs < rhs is asc
53 template <typename T, typename CMP_T>
56 
57  public:
58  TopNGenerator(size_t n) : n_(n), pq_(CMP_T()) {}
59 
60  inline void push(const T& val, size_t idx) {
61  if (pq_.empty()) {
62  pq_.emplace(val, idx);
63  return;
64  }
65  if (pq_.top().val == val) {
66  replicated_indices_.push_back(idx);
67  } else if (CMP_T()(pq_.top().val, val)) {
68  if (pq_.size() + replicated_indices_.size() < n_) {
69  for (auto i : replicated_indices_) {
70  pq_.emplace(pq_.top().val, i);
71  }
72  replicated_indices_.clear();
73  pq_.emplace(val, idx);
74  }
75  } else {
76  if (pq_.size() < n_) {
77  pq_.emplace(val, idx);
78  } else {
79  pq_.pop();
80  replicated_indices_.clear();
81 
82  pq_.emplace(val, idx);
83  auto cur = std::move(pq_.top());
84  pq_.pop();
85 
86  while (!pq_.empty() && pq_.top().val == cur.val) {
87  replicated_indices_.push_back(pq_.top().idx);
88  pq_.pop();
89  }
90  pq_.push(cur);
91  }
92  }
93  }
94 
95  void generate_indices(std::vector<size_t>& indices) {
96  indices = std::move(replicated_indices_);
97  replicated_indices_.clear();
98  while (!pq_.empty()) {
99  indices.push_back(pq_.top().idx);
100  pq_.pop();
101  }
102  }
103 
104  void generate_pairs(std::vector<T>& values, std::vector<size_t>& indices) {
105  indices = std::move(replicated_indices_);
106  replicated_indices_.clear();
107  values.clear();
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);
112  pq_.pop();
113  }
114  }
115 
116  private:
117  size_t n_;
118  std::priority_queue<unit_t, std::vector<unit_t>, CMP_T> pq_;
119  std::vector<size_t> replicated_indices_;
120 };
121 
122 template <typename T, typename CMP_T>
125 
126  public:
127  InplaceTopNGenerator(size_t n) : n_(n) {}
128 
129  void generate_indices(const std::vector<T>& input,
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)) {
137  pq.pop();
138  pq.emplace(input[i], i);
139  }
140  }
141 
142  T top_val = pq.top().val;
143  pq.pop();
144  for (size_t i = 0; i < size; ++i) {
145  if (input[i] == top_val) {
146  indices.push_back(i);
147  }
148  }
149  while (!pq.empty() && pq.top().val == top_val) {
150  pq.pop();
151  }
152  while (!pq.empty()) {
153  indices.push_back(pq.top().idx);
154  pq.pop();
155  }
156  }
157 
158  private:
159  size_t n_;
160 };
161 
162 } // namespace gs
163 
164 #endif // FLEX_UTILS_TOP_N_GENERATOR_H_
gs::TopNGenerator::TopNGenerator
TopNGenerator(size_t n)
Definition: top_n_generator.h:58
gs::TopNGenerator::replicated_indices_
std::vector< size_t > replicated_indices_
Definition: top_n_generator.h:119
gs::TopNDescCmp
Definition: top_n_generator.h:42
gs::TopNGenerator::generate_pairs
void generate_pairs(std::vector< T > &values, std::vector< size_t > &indices)
Definition: top_n_generator.h:104
gs::InplaceTopNGenerator::InplaceTopNGenerator
InplaceTopNGenerator(size_t n)
Definition: top_n_generator.h:127
gs
Definition: adj_list.h:23
gs::TopNDescCmp::operator()
bool operator()(const T &lhs, const T &rhs) const
Definition: top_n_generator.h:48
gs::TopNAscCmp::operator()
bool operator()(const T &lhs, const T &rhs) const
Definition: top_n_generator.h:38
gs::TopNUnit::TopNUnit
TopNUnit(const T &val_, size_t idx_)
Definition: top_n_generator.h:26
gs::InplaceTopNGenerator
Definition: top_n_generator.h:123
gs::InplaceTopNGenerator::n_
size_t n_
Definition: top_n_generator.h:159
gs::TopNGenerator::generate_indices
void generate_indices(std::vector< size_t > &indices)
Definition: top_n_generator.h:95
gs::TopNUnit::val
T val
Definition: top_n_generator.h:27
gs::TopNGenerator::n_
size_t n_
Definition: top_n_generator.h:117
gs::TopNAscCmp
Definition: top_n_generator.h:32
gs::TopNDescCmp::operator()
bool operator()(const elem_t &lhs, const elem_t &rhs) const
Definition: top_n_generator.h:44
gs::TopNAscCmp::operator()
bool operator()(const elem_t &lhs, const elem_t &rhs) const
Definition: top_n_generator.h:34
gs::InplaceTopNGenerator::generate_indices
void generate_indices(const std::vector< T > &input, std::vector< size_t > &indices)
Definition: top_n_generator.h:129
gs::TopNUnit
Definition: top_n_generator.h:25
gs::TopNGenerator
Definition: top_n_generator.h:54
gs::TopNUnit::idx
size_t idx
Definition: top_n_generator.h:28
gs::TopNGenerator::push
void push(const T &val, size_t idx)
Definition: top_n_generator.h:60
gs::TopNGenerator::pq_
std::priority_queue< unit_t, std::vector< unit_t >, CMP_T > pq_
Definition: top_n_generator.h:118