Embedded Template Library 1.0
histogram.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2021 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_HISTOGRAM_INCLUDED
32#define ETL_HISTOGRAM_INCLUDED
33
34#include "platform.h"
35#include "functional.h"
36#include "algorithm.h"
37#include "array.h"
38#include "flat_map.h"
39#include "static_assert.h"
40#include "type_traits.h"
41#include "integral_limits.h"
42
43namespace etl
44{
45 namespace private_histogram
46 {
47 //***************************************************************************
49 //***************************************************************************
50 template <typename TCount, size_t Max_Size_>
52 {
53 public:
54
55 ETL_STATIC_ASSERT(etl::is_integral<TCount>::value, "Only integral count allowed");
56
57 static ETL_CONSTANT size_t Max_Size = Max_Size_;
58
59 typedef typename etl::array<TCount, Max_Size>::const_iterator const_iterator;
60
61 //*********************************
63 //*********************************
64 const_iterator begin() const
65 {
66 return accumulator.begin();
67 }
68
69 //*********************************
71 //*********************************
72 const_iterator cbegin() const
73 {
74 return accumulator.cbegin();
75 }
76
77 //*********************************
79 //*********************************
80 const_iterator end() const
81 {
82 return accumulator.end();
83 }
84
85 //*********************************
87 //*********************************
88 const_iterator cend() const
89 {
90 return accumulator.cend();
91 }
92
93 //*********************************
95 //*********************************
96 void clear()
97 {
98 accumulator.fill(TCount(0));
99 }
100
101 //*********************************
103 //*********************************
104 ETL_CONSTEXPR size_t size() const
105 {
106 return Max_Size;
107 }
108
109 //*********************************
111 //*********************************
112 ETL_CONSTEXPR size_t max_size() const
113 {
114 return Max_Size;
115 }
116
117 //*********************************
119 //*********************************
120 size_t count() const
121 {
122 return etl::accumulate(accumulator.begin(), accumulator.end(), size_t(0));
123 }
124
125 protected:
126
128 };
129
130 template <typename TCount, size_t Max_Size_>
131 ETL_CONSTANT size_t histogram_common<TCount, Max_Size_>::Max_Size;
132 }
133
134 //***************************************************************************
136 //***************************************************************************
137 template <typename TKey, typename TCount, size_t Max_Size, int32_t Start_Index = etl::integral_limits<int32_t>::max>
139 : public etl::private_histogram::histogram_common<TCount, Max_Size>
140 , public etl::unary_function<TKey, void>
141 {
142 public:
143
144 ETL_STATIC_ASSERT(etl::is_integral<TKey>::value, "Only integral keys allowed");
145 ETL_STATIC_ASSERT(etl::is_integral<TCount>::value, "Only integral count allowed");
146
147 typedef TKey key_type;
148 typedef TCount count_type;
149 typedef TCount value_type;
150
151 //*********************************
153 //*********************************
155 {
156 this->accumulator.fill(count_type(0));
157 }
158
159 //*********************************
161 //*********************************
162 template <typename TIterator>
163 histogram(TIterator first, TIterator last)
164 {
165 this->accumulator.fill(count_type(0));
166 add(first, last);
167 }
168
169 //*********************************
171 //*********************************
172 histogram(const histogram& other)
173 {
174 this->accumulator = other.accumulator;
175 }
176
177#if ETL_USING_CPP11
178 //*********************************
180 //*********************************
181 histogram(histogram&& other)
182 {
183 this->accumulator = etl::move(other.accumulator);
184 }
185#endif
186
187 //*********************************
189 //*********************************
191 {
192 this->accumulator = rhs.accumulator;
193
194 return *this;
195 }
196
197#if ETL_USING_CPP11
198 //*********************************
200 //*********************************
202 {
203 this->accumulator = etl::move(rhs.accumulator);
204
205 return *this;
206 }
207#endif
208
209 //*********************************
211 //*********************************
212 void add(key_type key)
213 {
214 ++this->accumulator[key - Start_Index];
215 }
216
217 //*********************************
219 //*********************************
220 template <typename TIterator>
221 void add(TIterator first, TIterator last)
222 {
223 while (first != last)
224 {
225 add(*first);
226 ++first;
227 }
228 }
229
230 //*********************************
232 //*********************************
233 void operator ()(key_type key)
234 {
235 add(key);
236 }
237
238 //*********************************
240 //*********************************
241 template <typename TIterator>
242 void operator ()(TIterator first, TIterator last)
243 {
244 add(first, last);
245 }
246
247 //*********************************
249 //*********************************
250 value_type operator [](key_type key) const
251 {
252 return this->accumulator[key];
253 }
254 };
255
256 //***************************************************************************
258 //***************************************************************************
259 template<typename TKey, typename TCount, size_t Max_Size>
260 class histogram<TKey, TCount, Max_Size, etl::integral_limits<int32_t>::max>
261 : public etl::private_histogram::histogram_common<TCount, Max_Size>
262 , public etl::unary_function<TKey, void>
263 {
264 public:
265
266 ETL_STATIC_ASSERT(etl::is_integral<TKey>::value, "Only integral keys allowed");
267 ETL_STATIC_ASSERT(etl::is_integral<TCount>::value, "Only integral count allowed");
268
269 typedef TKey key_type;
270 typedef TCount count_type;
271 typedef TCount value_type;
272
273 //*********************************
275 //*********************************
276 explicit histogram(key_type start_index_)
277 : start_index(start_index_)
278 {
279 this->accumulator.fill(count_type(0));
280 }
281
282 //*********************************
284 //*********************************
285 template <typename TIterator>
286 histogram(key_type start_index_, TIterator first, TIterator last)
287 : start_index(start_index_)
288 {
289 this->accumulator.fill(count_type(0));
290 add(first, last);
291 }
292
293 //*********************************
295 //*********************************
296 histogram(const histogram& other)
297 {
298 this->accumulator = other.accumulator;
299 }
300
301#if ETL_USING_CPP11
302 //*********************************
304 //*********************************
305 histogram(histogram&& other)
306 {
307 this->accumulator = etl::move(other.accumulator);
308 }
309#endif
310
311 //*********************************
313 //*********************************
315 {
316 this->accumulator = rhs.accumulator;
317
318 return *this;
319 }
320
321#if ETL_USING_CPP11
322 //*********************************
324 //*********************************
326 {
327 this->accumulator = etl::move(rhs.accumulator);
328
329 return *this;
330 }
331#endif
332
333 //*********************************
335 //*********************************
336 void add(key_type key)
337 {
338 ++this->accumulator[key - start_index];
339 }
340
341 //*********************************
343 //*********************************
344 template <typename TIterator>
345 void add(TIterator first, TIterator last)
346 {
347 while (first != last)
348 {
349 add(*first);
350 ++first;
351 }
352 }
353
354 //*********************************
356 //*********************************
357 void operator ()(key_type key)
358 {
359 add(key);
360 }
361
362 //*********************************
364 //*********************************
365 template <typename TIterator>
366 void operator ()(TIterator first, TIterator last)
367 {
368 add(first, last);
369 }
370
371 //*********************************
373 //*********************************
374 value_type operator [](key_type key) const
375 {
376 return this->accumulator[key];
377 }
378
379 private:
380
381 key_type start_index;
382 };
383
384 //***************************************************************************
386 //***************************************************************************
387 template<typename TKey, typename TCount, size_t Max_Size_>
388 class sparse_histogram : public etl::unary_function<TKey, void>
389 {
390 private:
391
393
394 public:
395
396 ETL_STATIC_ASSERT(etl::is_integral<TCount>::value, "Only integral count allowed");
397
398 static ETL_CONSTANT size_t Max_Size = Max_Size_;
399
400 typedef TKey key_type;
401 typedef TCount count_type;
402 typedef typename accumulator_type::value_type value_type;
403 typedef typename accumulator_type::const_iterator const_iterator;
404
405 public:
406
407 //*********************************
409 //*********************************
411 {
412 }
413
414 //*********************************
416 //*********************************
417 template <typename TIterator>
418 sparse_histogram(TIterator first, TIterator last)
419 {
420 add(first, last);
421 }
422
423 //*********************************
425 //*********************************
427 {
428 this->accumulator = other.accumulator;
429 }
430
431#if ETL_USING_CPP11
432 //*********************************
434 //*********************************
436 {
437 accumulator = etl::move(other.accumulator);
438 }
439#endif
440
441 //*********************************
443 //*********************************
445 {
446 accumulator = rhs.accumulator;
447
448 return *this;
449 }
450
451#if ETL_USING_CPP11
452 //*********************************
454 //*********************************
456 {
457 accumulator = etl::move(rhs.accumulator);
458
459 return *this;
460 }
461#endif
462
463 //*********************************
465 //*********************************
466 const_iterator begin() const
467 {
468 return accumulator.begin();
469 }
470
471 //*********************************
473 //*********************************
474 const_iterator cbegin() const
475 {
476 return accumulator.cbegin();
477 }
478
479 //*********************************
481 //*********************************
482 const_iterator end() const
483 {
484 return accumulator.begin();
485 }
486
487 //*********************************
489 //*********************************
490 const_iterator cend() const
491 {
492 return accumulator.cbegin();
493 }
494
495 //*********************************
497 //*********************************
498 void add(const key_type& key)
499 {
500 ++accumulator[key];
501 }
502
503 //*********************************
505 //*********************************
506 template <typename TIterator>
507 void add(TIterator first, TIterator last)
508 {
509 while (first != last)
510 {
511 add(*first);
512 ++first;
513 }
514 }
515
516 //*********************************
518 //*********************************
519 void operator ()(const key_type& key)
520 {
521 add(key);
522 }
523
524 //*********************************
526 //*********************************
527 template <typename TIterator>
528 void operator ()(TIterator first, TIterator last)
529 {
530 add(first, last);
531 }
532
533 //*********************************
535 //*********************************
536 const value_type& operator [](const key_type& key) const
537 {
538 static const value_type unused(key_type(), count_type(0));
539
540 typename accumulator_type::const_iterator itr = accumulator.find(key);
541
542 if (itr != accumulator.end())
543 {
544 return *itr;
545 }
546 else
547 {
548 return unused;
549 }
550 }
551
552 //*********************************
554 //*********************************
555 void clear()
556 {
557 accumulator.clear();
558 }
559
560 //*********************************
562 //*********************************
563 size_t size() const
564 {
565 return accumulator.size();
566 }
567
568 //*********************************
570 //*********************************
571 ETL_CONSTEXPR size_t max_size() const
572 {
573 return Max_Size;
574 }
575
576 //*********************************
578 //*********************************
579 size_t count() const
580 {
581 count_type sum = count_type(0);
582
583 const_iterator itr = accumulator.begin();
584
585 while (itr != accumulator.end())
586 {
587 sum += (*itr).second;
588 ++itr;
589 }
590
591 return sum;
592 }
593
594 private:
595
597 };
598
599 template <typename TKey, typename TCount, size_t Max_Size_>
600 ETL_CONSTANT size_t sparse_histogram<TKey, TCount, Max_Size_>::Max_Size;
601}
602
603#endif
histogram(key_type start_index_, TIterator first, TIterator last)
Constructor.
Definition: histogram.h:286
histogram(key_type start_index_)
Constructor.
Definition: histogram.h:276
void add(TIterator first, TIterator last)
Add.
Definition: histogram.h:345
histogram(const histogram &other)
Copy constructor.
Definition: histogram.h:296
Histogram with a compile time start index.
Definition: histogram.h:141
void operator()(key_type key)
operator ()
Definition: histogram.h:233
void add(key_type key)
Add.
Definition: histogram.h:212
value_type operator[](key_type key) const
operator []
Definition: histogram.h:250
void add(TIterator first, TIterator last)
Add.
Definition: histogram.h:221
histogram(TIterator first, TIterator last)
Constructor.
Definition: histogram.h:163
histogram()
Constructor.
Definition: histogram.h:154
histogram & operator=(const histogram &rhs)
Copy assignment.
Definition: histogram.h:190
histogram(const histogram &other)
Copy constructor.
Definition: histogram.h:172
Base for histograms.
Definition: histogram.h:52
const_iterator end() const
End of the histogram.
Definition: histogram.h:80
const_iterator cend() const
End of the histogram.
Definition: histogram.h:88
const_iterator cbegin() const
Beginning of the histogram.
Definition: histogram.h:72
size_t count() const
Count of items in the histogram.
Definition: histogram.h:120
const_iterator begin() const
Beginning of the histogram.
Definition: histogram.h:64
void clear()
Clear the histogram.
Definition: histogram.h:96
ETL_CONSTEXPR size_t size() const
Size of the histogram.
Definition: histogram.h:104
ETL_CONSTEXPR size_t max_size() const
Max size of the histogram.
Definition: histogram.h:112
Histogram for sparse keys.
Definition: histogram.h:389
ETL_CONSTEXPR size_t max_size() const
Max size of the histogram.
Definition: histogram.h:571
const_iterator begin() const
Beginning of the histogram.
Definition: histogram.h:466
sparse_histogram(const sparse_histogram &other)
Copy constructor.
Definition: histogram.h:426
const_iterator end() const
End of the histogram.
Definition: histogram.h:482
void clear()
Clear the histogram.
Definition: histogram.h:555
void add(TIterator first, TIterator last)
Add.
Definition: histogram.h:507
const value_type & operator[](const key_type &key) const
operator []
Definition: histogram.h:536
const_iterator cbegin() const
Beginning of the histogram.
Definition: histogram.h:474
void operator()(const key_type &key)
operator ()
Definition: histogram.h:519
sparse_histogram & operator=(const sparse_histogram &rhs)
Copy assignment.
Definition: histogram.h:444
size_t size() const
Size of the histogram.
Definition: histogram.h:563
sparse_histogram(TIterator first, TIterator last)
Constructor.
Definition: histogram.h:418
sparse_histogram()
Constructor.
Definition: histogram.h:410
void add(const key_type &key)
Add.
Definition: histogram.h:498
const_iterator cend() const
End of the histogram.
Definition: histogram.h:490
size_t count() const
Count of items in the histogram.
Definition: histogram.h:579
ETL_CONSTEXPR14 T accumulate(TIterator first, TIterator last, T sum)
Definition: algorithm.h:1882
ETL_CONSTEXPR14 void fill(parameter_t value)
Definition: array.h:369
ETL_NODISCARD iterator begin() ETL_NOEXCEPT
Returns an iterator to the beginning of the array.
Definition: array.h:226
ETL_NODISCARD iterator end() ETL_NOEXCEPT
Returns an iterator to the end of the array.
Definition: array.h:253
ETL_NODISCARD ETL_CONSTEXPR const_iterator cbegin() const ETL_NOEXCEPT
Returns a const iterator to the beginning of the array.
Definition: array.h:244
iterator begin()
Definition: flat_map.h:128
void clear()
Clears the flat_map.
Definition: flat_map.h:685
iterator find(const_key_reference key)
Definition: flat_map.h:712
const_iterator cbegin() const
Definition: flat_map.h:164
iterator end()
Definition: flat_map.h:146
size_type size() const
Definition: flat_map.h:924
Definition: flat_map.h:1129
Definition: integral_limits.h:468
is_integral
Definition: type_traits_generator.h:1001
bitset_ext
Definition: absolute.h:38
Definition: functional.h:117