1use std::collections::{HashSet, HashMap};
2use crate::standard::{Histogram, HistogramParams};
3
4#[cfg(test)]
12mod compact_testing {
13 use crate::c2::new_compact_params;
14
15 #[test]
16 fn init_params(){
17 assert!(new_compact_params(0.5, 8, 7).is_none());
18 assert!(new_compact_params(1.0, 8, 7).is_none());
19 assert!(new_compact_params(4.0, 0, 7).is_none());
20 assert!(new_compact_params(4.0, 8, 0).is_none());
21
22 assert!(new_compact_params(3.0, 9, 7).is_some());
23 }
24
25 #[test]
26 fn ranges(){
27 let cp = new_compact_params(3.0, 9, 7).unwrap();
28
29 assert_eq!(cp.range(0), Some((1, 3)));
30 assert_eq!(cp.range(1), Some((4, 9)));
31 assert_eq!(cp.range(2), Some((10, 27)));
32 assert_eq!(cp.range(3), Some((28, 81)));
33
34 assert!(cp.range(10).is_none());
35
36 let cp = new_compact_params(3.5, 9, 7).unwrap();
37
38 assert_eq!(cp.range(0), Some((1, 3)));
39 assert_eq!(cp.range(1), Some((4, 12)));
40 assert_eq!(cp.range(2), Some((13, 42)));
41 assert_eq!(cp.range(3), Some((43, 150)));
42
43 }
44
45 #[test]
46 fn sub_ranges(){
47 let cp = new_compact_params(3.0, 9, 7).unwrap();
48
49 assert_eq!(cp.get_kth_sub_range(0, 0), Some((1,1)));
50 assert_eq!(cp.get_kth_sub_range(0, 1), Some((2,2)));
51 assert_eq!(cp.get_kth_sub_range(0, 2), Some((3,3)));
52
53 assert!(cp.get_kth_sub_range(0, 3).is_none());
54
55 let cp = new_compact_params(3.5, 9, 7).unwrap();
56
57 assert_eq!(cp.get_kth_sub_range(2, 0), Some((13, 17)));
58 assert_eq!(cp.get_kth_sub_range(2, 1), Some((17, 21)));
59 assert_eq!(cp.get_kth_sub_range(2, 2), Some((21, 25)));
60 assert_eq!(cp.get_kth_sub_range(2, 3), Some((25, 29)));
61 assert_eq!(cp.get_kth_sub_range(2, 4), Some((29, 33)));
62 assert_eq!(cp.get_kth_sub_range(2, 5), Some((33, 37)));
63 assert_eq!(cp.get_kth_sub_range(2, 6), Some((37, 42)));
64 assert!(cp.get_kth_sub_range(2, 7).is_none());
65
66 assert_eq!(cp.get_kth_sub_range(3, 0), Some((43, 58)));
67 assert_eq!(cp.get_kth_sub_range(3, 1), Some((58, 73)));
68 assert_eq!(cp.get_kth_sub_range(3, 2), Some((73, 88)));
69 assert_eq!(cp.get_kth_sub_range(3, 3), Some((88, 104)));
70 assert_eq!(cp.get_kth_sub_range(3, 4), Some((104, 119)));
71 assert_eq!(cp.get_kth_sub_range(3, 5), Some((119, 134)));
72 assert_eq!(cp.get_kth_sub_range(3, 6), Some((134, 150)));
73 }
74
75 #[test]
76 fn pos_leases(){
77 let cp = new_compact_params(2.0, 3, 2).unwrap();
78 assert_eq!(cp.possible_leases(), vec![1,2,3,4,6,8]);
79 let cp = new_compact_params(3.0, 3, 2).unwrap();
80 assert_eq!(cp.possible_leases(), vec![1,2,6,9,18,27]);
81 let cp = new_compact_params(4.0, 4, 2).unwrap();
82 assert_eq!(cp.possible_leases(), vec![2,4,10,16,40,64,160,256]);
83 let cp = new_compact_params(4.0, 4, 3).unwrap();
84 assert_eq!(cp.possible_leases(), vec![1,2,3,8,12,16,32,48,64,128,192,256]);
85 }
86
87 #[test]
88 fn index_buckets(){
89 let cp = new_compact_params(2.0, 5, 4).unwrap();
90 assert_eq!(cp.bucket_index(1), Some(0));
91 assert_eq!(cp.bucket_index(2), Some(0));
92 assert_eq!(cp.bucket_index(3), Some(1));
93 assert_eq!(cp.bucket_index(4), Some(1));
94 assert_eq!(cp.bucket_index(5), Some(2));
95 assert_eq!(cp.bucket_index(7), Some(2));
96 assert_eq!(cp.bucket_index(8), Some(2));
97 assert_eq!(cp.bucket_index(9), Some(3));
98 assert_eq!(cp.bucket_index(32), Some(4));
99 assert!(cp.bucket_index(33).is_none());
100
101 let cp = new_compact_params(3.7, 5, 4).unwrap();
102 assert_eq!(cp.bucket_index(1), Some(0));
103 assert_eq!(cp.bucket_index(2), Some(0));
104 assert_eq!(cp.bucket_index(3), Some(0));
105 assert_eq!(cp.bucket_index(4), Some(1));
106 assert_eq!(cp.bucket_index(5), Some(1));
107 assert_eq!(cp.bucket_index(13), Some(1));
108 assert_eq!(cp.bucket_index(14), Some(2));
109 assert_eq!(cp.bucket_index(50), Some(2));
110 assert_eq!(cp.bucket_index(51), Some(3));
111 }
112
113
114}
115
116#[derive(Debug, Clone)]
132pub struct CompactParams {
133 base : f64,
135
136 max : f64,
138
139 num_buckets : usize,
141
142 k : usize
144}
145
146impl CompactParams {
147
148 pub fn max(&self) -> f64 { self.max }
150 pub fn base(&self) -> f64 { self.base }
151 pub fn k(&self) -> usize { self.k }
152 pub fn num_buckets(&self) -> usize { self.num_buckets }
153
154 pub fn possible_leases(&self) -> Vec<usize> {
168 let mut output = vec![];
169 let mut counter = 0;
170 output.reserve(self.num_buckets * self.k);
171 for b in 0..self.num_buckets {
172 for k_i in 0..self.k {
173 if let Some((_min, max)) = self.get_kth_sub_range(b, k_i) {
174 output.insert(counter, max as usize);
175 counter += 1;
176 }
177 }
178 }
179 output
180 }
181
182 pub fn get_kth_sub_range(&self, bucket_index :usize, k_i :usize) -> Option<(usize, usize)> {
187 if k_i >= self.k { return None };
188
189 if let Some((r_min, r_max)) = self.range(bucket_index) {
191
192 let range = r_max - r_min;
194
195 if self.k >= range {
197 if k_i > range { return None; }
198 return Some((k_i + r_min, k_i + r_min));
199 }
200
201 let sub_range = range as f64 / self.k as f64;
203 let lower = r_min + (sub_range * k_i as f64) as usize;
204 let higher = r_min + (sub_range * (k_i + 1) as f64) as usize;
205
206 return Some((lower, higher));
207 }
208
209 None
210 }
211
212 pub(crate) fn range(&self, bucket_index : usize) -> Option<(usize, usize)> {
215 if bucket_index >= self.num_buckets() {
217 None
218 } else if bucket_index == 0 {
219 Some((1, self.base as usize))
220 } else {
221 let lower = self.base.powi(bucket_index as i32) as usize + 1;
222 let higher = self.base.powi((bucket_index+1) as i32) as usize;
223 Some((lower, higher))
224 }
225 }
226
227 pub fn bucket_index(&self, ri : usize) -> Option<usize> {
229 if ri == 1 {
231 Some(0)
232
233 } else if ri as f64 > self.max || ri == 0 { None
236 } else {
237 let bi = (ri as f64).log(self.base);
238
239 if bi.fract() == 0.0 {
241 if bi == 1.0 {
242 Some(0)
243 } else {
244 Some(bi as usize - 1)
245 }
246 } else { Some(((ri as f64 - 0.1).log(self.base).floor() + 0.1) as usize)
248 }
249 }
250 }
251
252}
253
254pub fn new_compact_params(b: f64, n: usize, k: usize) -> Option<CompactParams> {
260 if b <= 1.0 || k == 0 || n == 0 {
261 None
262 } else {
263 let max = b.powi(n as i32);
264 Some(CompactParams { base: b, max, num_buckets: n, k })
265 }
266}
267
268impl HistogramParams for CompactParams {}
269
270pub struct CompactHistogram {
296 pub(crate) counters : Vec<usize>,
298
299 pub(crate) sub_range_averages : Vec<usize>, pub(crate) overflowed : usize }
304
305impl Histogram<CompactParams, usize, usize> for CompactHistogram {
306 fn labels(&self, params : &CompactParams) -> Option<Box<dyn Iterator<Item=usize>>>{
309 let mut v = Vec::new();
310 let mut count = 0;
311 for i in 0..params.num_buckets {
312 if let Some((_min, max)) = params.get_kth_sub_range(
313 i, self.sub_range_averages[i]) {
314 if !v.contains(&max) {
315 v.insert(count, max);
316 count += 1;
317 }
318 }
319 }
320 Some(Box::new(v.into_iter()))
321 }
322
323 fn frequency(&self, label : usize, params : &CompactParams) -> Option<usize> {
324 if let Some(bi) = params.bucket_index(label) {
325 if let Some(&s) = self.counters.get(bi) {
326 Some(s)
327 } else { None }
328 } else { Some(0) }
329 }
330
331 fn total(&self) -> usize {
332 let mut sum: usize = 0;
333 for i in 0..self.counters.len() {
334 sum += self.counters[i];
335 }
336 return sum + self.overflowed as usize;
337 }
338}
339
340
341#[cfg(test)]
345mod compress_testing {
346 use crate::c2::{new_compressed_params};
347
348 #[test]
349 fn init_params(){
350 assert!(new_compressed_params(2.0, 5).is_some());
351 assert!(new_compressed_params(5.0, 51).is_some());
352 assert!(new_compressed_params(6.8, 15).is_some());
353 assert!(new_compressed_params(1.5, 34).is_some());
354 assert!(new_compressed_params(1.0, 21).is_none());
355 assert!(new_compressed_params(-0.5, 12).is_none());
356 assert!(new_compressed_params(2.0, 0).is_none());
357 }
358
359 #[test]
360 fn compression(){
361 let cp = new_compressed_params(2.0, 5).unwrap();
362 assert_eq!(cp.compress_count(0), Some(0));
363 assert_eq!(cp.compress_count(2), Some(1));
364 assert_eq!(cp.compress_count(3), Some(2));
365 assert_eq!(cp.compress_count(4), Some(2));
366 assert_eq!(cp.compress_count(5), Some(3));
367 assert_eq!(cp.compress_count(7), Some(3));
368 assert_eq!(cp.compress_count(8), Some(3));
369 assert_eq!(cp.compress_count(9), Some(4));
370 assert_eq!(cp.compress_count(31), Some(5));
371 assert_eq!(cp.compress_count(35), Some(5));
372 assert_eq!(cp.compress_count(300), Some(5));
373
374 let cp = new_compressed_params(1.5, 15).unwrap();
375
376 assert_eq!(cp.compress_count(0), Some(0));
377 assert_eq!(cp.compress_count(1), Some(1));
378 assert_eq!(cp.compress_count(2), Some(2));
379 assert_eq!(cp.compress_count(3), Some(3));
380 assert_eq!(cp.compress_count(4), Some(4));
381 assert_eq!(cp.compress_count(5), Some(4));
382 assert_eq!(cp.compress_count(6), Some(5));
383 assert_eq!(cp.compress_count(7), Some(5));
384 assert_eq!(cp.compress_count(8), Some(6));
385 assert_eq!(cp.compress_count(9), Some(6));
386 assert_eq!(cp.compress_count(10), Some(6));
387 assert_eq!(cp.compress_count(11), Some(6));
388 assert_eq!(cp.compress_count(12), Some(7));
389 assert_eq!(cp.compress_count(13), Some(7));
390 assert_eq!(cp.compress_count(300), Some(15));
391 assert_eq!(cp.compress_count(500), Some(15));
392 assert_eq!(cp.compress_count(5000), Some(15));
393 }
394
395 #[test]
396 fn decompression(){
397 let cp = new_compressed_params(2.0, 5).unwrap();
398 assert_eq!(cp.decompress_count(0), Some(0));
399 assert_eq!(cp.decompress_count(1), Some(2));
400 assert_eq!(cp.decompress_count(2), Some(4));
401 assert_eq!(cp.decompress_count(3), Some(8));
402 assert_eq!(cp.decompress_count(4), Some(16));
403 assert_eq!(cp.decompress_count(5), Some(32));
404 assert!(cp.decompress_count(6).is_none());
405
406 let cp = new_compressed_params(1.5, 15).unwrap();
407 assert_eq!(cp.decompress_count(0), Some(0));
408 assert_eq!(cp.decompress_count(1), Some(1));
409 assert_eq!(cp.decompress_count(2), Some(2));
410 assert_eq!(cp.decompress_count(3), Some(3));
411 assert_eq!(cp.decompress_count(4), Some(5));
412 assert_eq!(cp.decompress_count(5), Some(7));
413 assert_eq!(cp.decompress_count(9), Some(38));
414 assert_eq!(cp.decompress_count(10), Some(57));
415 assert_eq!(cp.decompress_count(11), Some(86));
416 assert_eq!(cp.decompress_count(12), Some(129));
417 assert_eq!(cp.decompress_count(13), Some(194));
418 assert!(cp.decompress_count(16).is_none());
419 }
420
421 #[test]
422 fn decomp_comp(){
423 let cp = new_compressed_params(2.0, 5).unwrap();
424 assert_eq!(cp.decompress_count(cp.compress_count(1).unwrap()), Some(2));
425 assert_eq!(cp.decompress_count(cp.compress_count(2).unwrap()), Some(2));
426 assert_eq!(cp.decompress_count(cp.compress_count(3).unwrap()), Some(4));
427 assert_eq!(cp.decompress_count(cp.compress_count(4).unwrap()), Some(4));
428 assert_eq!(cp.decompress_count(cp.compress_count(5).unwrap()), Some(8));
429 assert_eq!(cp.decompress_count(cp.compress_count(6).unwrap()), Some(8));
430 assert_eq!(cp.decompress_count(cp.compress_count(7).unwrap()), Some(8));
431 assert_eq!(cp.decompress_count(cp.compress_count(8).unwrap()), Some(8));
432 assert_eq!(cp.decompress_count(cp.compress_count(9).unwrap()), Some(16));
433 assert_eq!(cp.decompress_count(cp.compress_count(10).unwrap()), Some(16));
434 assert_eq!(cp.decompress_count(cp.compress_count(11).unwrap()), Some(16));
435 assert_eq!(cp.decompress_count(cp.compress_count(12).unwrap()), Some(16));
436 assert_eq!(cp.decompress_count(cp.compress_count(13).unwrap()), Some(16));
437 assert_eq!(cp.decompress_count(cp.compress_count(14).unwrap()), Some(16));
438 assert_eq!(cp.decompress_count(cp.compress_count(15).unwrap()), Some(16));
439 }
440
441}
442
443#[derive(Debug, Clone)]
444pub struct CompressedParams {
457 base : f64,
458 max_exp : usize,
459
460 table: Vec<usize>
462}
463
464impl CompressedParams {
465 pub fn base(&self) -> f64 { self.base }
466 pub fn max_exp(&self) -> usize { self.max_exp }
467}
468
469pub fn new_compressed_params(base : f64, max_exp : usize) -> Option<CompressedParams> {
476 if base <= 1.01 || max_exp == 0 {
477 None
478 } else {
479 let mut table = Vec::new();
480 table.reserve_exact(max_exp + 1);
481
482
483 table.insert(0, 0);
487
488 for i in 1..(max_exp+1) {
489 let mut expanded = base.powi(i as i32);
490
491 if expanded > usize::MAX as f64 / (base * base) {
493 for j in i..(max_exp+1) {
494 table.insert(j, expanded as usize);
495 }
496 break;
497 }
498
499 while expanded as usize <= table[i-1] {
501 expanded = expanded * base;
502 }
503
504 let expanded = expanded as usize;
505
506 table.insert(i, expanded);
507 }
508
509 Some(CompressedParams { base, max_exp, table })
510 }
511}
512
513impl HistogramParams for CompressedParams {}
514
515impl CompressedParams {
516 pub(crate) fn compress_count(&self, count : usize) -> Option<u16> {
517 if count == 0 { Some(0)
519 } else if (count as f64) < self.base {
520 Some(1)
521 } else if count > self.table[self.max_exp]{
522 Some(self.max_exp as u16)
523 } else {
524 let mut min = 0;
527 let mut max = self.max_exp+1;
528 let mut mid;
529
530 loop {
531 mid = (min + max) / 2;
532 if self.table[mid] >= count && self.table[mid - 1] < count {
533 break;
534 }
535 else if self.table[mid] > count {
536 max = mid;
537 }
538 else if self.table[mid] < count {
539 min = mid;
540 }
541 }
542
543 Some(mid as u16)
544
545 }
546 }
547
548 pub(crate) fn decompress_count(&self, compressed_count : u16) -> Option<usize> {
550 if compressed_count > self.max_exp as u16 {
551 None
552 } else {
553 Some(self.table[compressed_count as usize])
554 }
555 }
556}
557
558#[allow(dead_code)]
559pub struct CompressedHistogram {
576 pub(crate) data : HashMap<usize, u16>,
578 pub(crate) total : usize,
579 pub(crate) orig_total : usize
580}
581
582impl Histogram<CompressedParams, usize, usize> for CompressedHistogram {
583 fn labels(&self, _params: &CompressedParams) -> Option<Box<dyn Iterator<Item=usize>>> {
584 let mut out : Vec<usize> = vec![];
585 let mut counter : usize = 0;
586 for k in self.data.keys(){
587 out.insert(counter, *k);
588 counter += 1;
589 }
590 Some(Box::new(out.into_iter()))
591 }
592
593 fn frequency(&self, label: usize, params: &CompressedParams) -> Option<usize> {
594 if let Some(c) = self.data.get(&label) {
595 params.decompress_count(*c)
596 } else {
597 None
598 }
599 }
600
601 fn total(&self) -> usize {
603 if self.total > self.orig_total {
604 self.total
605 } else {
606 self.orig_total
607 }
608 }
609}
610
611
612#[derive(Debug, Clone)]
617pub struct C2Params {
634 compact_params : CompactParams,
635 compressed_params : CompressedParams
636}
637
638impl C2Params {
639 pub fn compact_ps(&self) -> &CompactParams { &self.compact_params }
641
642 pub fn compressed_ps(&self) -> &CompressedParams { &self.compressed_params }
644}
645
646impl HistogramParams for C2Params {}
647
648pub fn new_c2_params(compacts : CompactParams, compresseds : CompressedParams) -> C2Params {
656 C2Params { compact_params : compacts, compressed_params : compresseds }
657}
658
659#[allow(dead_code)]
660pub struct C2Histogram {
674 pub(crate) counters : Vec<u16>,
676
677 pub(crate) sub_range_averages : Vec<usize>,
679
680 pub(crate) orig_total : usize,
683
684 pub(crate) total : usize,
685
686 pub(crate) overflowed: usize
688
689}
690
691impl Histogram<C2Params, usize, usize> for C2Histogram {
692 fn labels(&self, params: &C2Params) -> Option<Box<dyn Iterator<Item=usize>>> {
694 let params = params.compact_ps();
695 let mut v = HashSet::new();
696 for i in 0..params.num_buckets() {
697 if let Some((_min, max)) = params.get_kth_sub_range(
698 i, self.sub_range_averages[i]) {
699 v.insert(max as usize);
700 }
701 }
702 Some(Box::new(v.into_iter()))
703 }
704
705 fn frequency(&self, label: usize, params: &C2Params) -> Option<usize> {
707 if let Some(bi) = params.compact_params.bucket_index(label) {
708 if let Some(&s) = self.counters.get(bi) {
709 params.compressed_params.decompress_count(s)
710 } else { None }
711 } else { Some(0) }
712 }
713
714 fn total(&self) -> usize {
715 self.total + self.overflowed
716 }
717}