MythTV  master
sequence.h
Go to the documentation of this file.
1 /* ============================================================
2  * File : sequence.h
3  * Description :
4  * A set of classes providing a sequence of numbers within a
5  * specified range allowing navigation in the sequence.
6  * SequenceBase - Base for all Sequence classes.
7  * SequenceInc - An incrementing sequence.
8  * SequenceDec - A decrementing sequence.
9  * SequenceRandomBase - Base for all 'random' Sequence classes.
10  * SequenceRandom - A random sequence (can have duplicates).
11  * SequenceShuffle - A random sequence (no duplicates).
12  * SequenceWeighted - A random sequence (duplicates and weighted items).
13  *
14 
15  * This program is free software; you can redistribute it
16  * and/or modify it under the terms of the GNU General
17  * Public License as published bythe Free Software Foundation;
18  * either version 2, or (at your option)
19  * any later version.
20  *
21  * This program is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24  * GNU General Public License for more details.
25  *
26  * ============================================================ */
27 
28 #ifndef SEQUENCE_H
29 #define SEQUENCE_H
30 
31 #include <algorithm>
32 #include <iterator>
33 #include <vector>
34 #if defined _MSC_VER || defined __MINGW32__
35 # include "compat.h" // for random
36 #endif
37 
38 const size_t MAX_HISTORY_SIZE = 1024;
39 
41 {
42 public:
43  SequenceBase() = default;
44  virtual ~SequenceBase() = default;
45 
46  virtual void set(size_t _idx) = 0;
47 
48  virtual void extend(size_t items)
49  {
50  m_len += items;
51  }
52 
53  size_t next()
54  {
55  ++m_idx;
56  if (m_idx == m_len)
57  {
58  m_idx = 0;
59  }
60  return get();
61  }
62 
63  size_t prev()
64  {
65  if (m_idx == 0)
66  {
67  m_idx = m_len;
68  }
69  --m_idx;
70  return get();
71  }
72 
73 protected:
74  virtual size_t get() = 0;
75 
76  size_t m_len {0};
77  size_t m_idx {0};
78 };
79 
80 class SequenceInc : public SequenceBase
81 {
82 protected:
83  void set(size_t _idx) override // SequenceBase
84  {
85  m_idx = _idx;
86  }
87 
88  size_t get() override // SequenceBase
89  { return m_idx; }
90 };
91 
92 class SequenceDec : public SequenceBase
93 {
94 protected:
95  void set(size_t _idx) override // SequenceBase
96  {
97  m_idx = m_len - _idx - 1;
98  }
99 
100  size_t get() override // SequenceBase
101  {
102  return m_len - m_idx - 1;
103  }
104 };
105 
107 {
108 public:
109  SequenceRandomBase() = default;
110 
111  void set(size_t _idx) override // SequenceBase
112  {
113  size_t seq_idx = (m_idx + 1) % m_seq.size();
114  m_seq[seq_idx] = _idx;
115  }
116 
117  void extend(size_t items) override // SequenceBase
118  {
119  size_t extension = std::min(m_len + items, MAX_HISTORY_SIZE) - m_len;
120  SequenceBase::extend(extension);
121  vector<ssize_t>::iterator insertion_iter = m_seq.begin();
122  std::advance(insertion_iter, m_eviction_idx);
123  m_seq.insert(insertion_iter, extension, -1);
124  if (m_idx > m_eviction_idx)
125  {
126  m_idx += extension;
127  }
128  m_eviction_idx += extension;
129  if (m_eviction_idx == m_len && m_len > 0)
130  {
131  m_eviction_idx = (m_idx + 1) % m_len;
132  }
133  }
134 
135 protected:
136  size_t get() override // SequenceBase
137  {
138  if (m_idx == m_eviction_idx)
139  {
140  // The end was reached from the left.
142  ++m_eviction_idx;
143  if (m_eviction_idx == m_len)
144  {
145  m_eviction_idx = 0;
146  }
147  }
148  else if (m_len > 0 && m_idx == (m_eviction_idx + 1) % m_len)
149  {
150  // The end was reached from the right.
151  evict(m_eviction_idx + 1);
152  if (m_eviction_idx == 0)
153  {
155  }
156  --m_eviction_idx;
157  }
158 
159  size_t seq_idx = m_idx % m_seq.size();
160  if (m_seq[seq_idx] == -1)
161  {
162  m_seq[seq_idx] = create();
163  }
164  return m_seq[seq_idx];
165  }
166 
167  virtual void evict(size_t i)
168  {
169  // Evict portions of the history that are far away.
170  m_seq[i] = -1;
171  }
172 
173  virtual size_t create() = 0;
174 
175  vector<ssize_t> m_seq;
176  size_t m_eviction_idx {0};
177 };
178 
180 {
181 public:
183  {
185  }
186 
187  void extend(size_t _items) override // SequenceRandomBase
188  {
189  m_items += _items;
190  // The parent len was already extended enough, so it is not called.
191  }
192 
193 protected:
194  size_t create() override // SequenceRandomBase
195  {
196  return (size_t)(((double)random()) * m_items / RAND_MAX);
197  }
198 
199  size_t m_items {0};
200 };
201 
203 {
204 public:
205  SequenceShuffle() = default;
206 
207  void set(size_t _idx) override // SequenceRandomBase
208  {
209  size_t seq_idx = (m_idx + 1) % m_seq.size();
210  evict(seq_idx);
211  ++m_eviction_idx;
212  if (m_eviction_idx == m_len)
213  {
214  m_eviction_idx = 0;
215  }
216  if (m_map[_idx])
217  {
218  auto old_iter = std::find(m_seq.begin(), m_seq.end(), _idx);
219  if (old_iter != m_seq.end())
220  *old_iter = -1;
221  }
222  else
223  {
224  m_map[_idx] = true;
225  --m_unseen;
226  }
228  }
229 
230  void extend(size_t items) override // SequenceRandomBase
231  {
233  m_map.resize(m_len, 0);
234  m_unseen += items;
235  }
236 
237 protected:
238  size_t create() override // SequenceRandomBase
239  {
240  size_t unseen_idx = (size_t)(((double)random()) * m_unseen / RAND_MAX);
241  for (size_t i = 0; ; ++i)
242  {
243  if (!m_map[i])
244  {
245  if (!unseen_idx)
246  {
247  m_map[i] = true;
248  --m_unseen;
249  return i;
250  }
251  --unseen_idx;
252  }
253  }
254  }
255 
256  void evict(size_t i) override // SequenceRandomBase
257  {
258  ssize_t evicted = m_seq[i];
259  if (evicted != -1)
260  {
261  m_map[evicted] = false;
262  ++m_unseen;
263  }
265  }
266 
267  vector<bool> m_map;
268  size_t m_unseen {0};
269 };
270 
272 {
273 public:
274  SequenceWeighted() = default;
275 
276  void extend(size_t items) override // SequenceRandom
277  {
278  m_weights.resize(m_weights.size() + items, m_totalWeight);
279  SequenceRandom::extend(items);
280  }
281 
282  void add(double weight)
283  {
284  m_totalWeight += weight;
286  }
287 
288 protected:
289  size_t create() override // SequenceRandom
290  {
291  double slot = (((double)random()) * m_totalWeight / RAND_MAX);
292  vector<double>::iterator slot_iter = std::upper_bound(
293  m_weights.begin(), m_weights.end(), slot);
294  size_t slot_idx = std::distance(m_weights.begin(), slot_iter);
295  return slot_idx;
296  }
297 
298  vector<double> m_weights;
299  size_t m_weightCursor {0};
300  double m_totalWeight {0.0};
301 };
302 
303 #endif // ndef SEQUENCE_H
void extend(size_t items) override
Definition: sequence.h:230
virtual size_t create()=0
static pid_list_t::iterator find(const PIDInfoMap &map, pid_list_t &list, pid_list_t::iterator begin, pid_list_t::iterator end, bool find_open)
double m_totalWeight
Definition: sequence.h:300
vector< double > m_weights
Definition: sequence.h:298
SequenceShuffle()=default
vector< ssize_t > m_seq
Definition: sequence.h:175
size_t prev()
Definition: sequence.h:63
SequenceRandomBase()=default
size_t next()
Definition: sequence.h:53
void extend(size_t _items) override
Definition: sequence.h:187
void set(size_t _idx) override
Definition: sequence.h:207
size_t m_items
Definition: sequence.h:199
size_t get() override
Definition: sequence.h:136
size_t m_len
Definition: sequence.h:76
size_t create() override
Definition: sequence.h:289
void evict(size_t i) override
Definition: sequence.h:256
void set(size_t _idx) override
Definition: sequence.h:95
size_t create() override
Definition: sequence.h:238
virtual void extend(size_t items)
Definition: sequence.h:48
size_t m_idx
Definition: sequence.h:77
void set(size_t _idx) override
Definition: sequence.h:111
const size_t MAX_HISTORY_SIZE
Definition: sequence.h:38
void set(size_t _idx) override
Definition: sequence.h:83
virtual ~SequenceBase()=default
SequenceBase()=default
void add(double weight)
Definition: sequence.h:282
virtual void set(size_t _idx)=0
size_t get() override
Definition: sequence.h:88
SequenceWeighted()=default
void extend(size_t items) override
Definition: sequence.h:117
size_t get() override
Definition: sequence.h:100
size_t m_eviction_idx
Definition: sequence.h:176
virtual size_t get()=0
static long int random(void)
Definition: compat.h:149
vector< bool > m_map
Definition: sequence.h:267
size_t create() override
Definition: sequence.h:194
size_t m_unseen
Definition: sequence.h:268
void extend(size_t items) override
Definition: sequence.h:276
size_t m_weightCursor
Definition: sequence.h:299
virtual void evict(size_t i)
Definition: sequence.h:167