c2_histograms 0.2.4

use std::collections::{HashSet, HashMap};
use crate::standard::{Histogram, HistogramParams};

/// This module contains Histogram implementations that simulate memory saving
/// optimizations. Note that this is only for evaluation purposes, it does not actually
/// perform the space saving operations.

// -----------------------------------------------------------------------------------
// --- COMPACT HISTOGRAM -------------------------------------------------------------
// -----------------------------------------------------------------------------------
#[cfg(test)]
mod compact_testing {
    use crate::c2::new_compact_params;

    #[test]
    fn init_params(){
        assert!(new_compact_params(0.5, 8, 7).is_none());
        assert!(new_compact_params(1.0, 8, 7).is_none());
        assert!(new_compact_params(4.0, 0, 7).is_none());
        assert!(new_compact_params(4.0, 8, 0).is_none());

        assert!(new_compact_params(3.0, 9, 7).is_some());
    }

    #[test]
    fn ranges(){
        let cp = new_compact_params(3.0, 9, 7).unwrap();

        assert_eq!(cp.range(0), Some((1, 3)));
        assert_eq!(cp.range(1), Some((4, 9)));
        assert_eq!(cp.range(2), Some((10, 27)));
        assert_eq!(cp.range(3), Some((28, 81)));

        assert!(cp.range(10).is_none());

        let cp = new_compact_params(3.5, 9, 7).unwrap();

        assert_eq!(cp.range(0), Some((1, 3)));
        assert_eq!(cp.range(1), Some((4, 12)));
        assert_eq!(cp.range(2), Some((13, 42)));
        assert_eq!(cp.range(3), Some((43, 150)));

    }

    #[test]
    fn sub_ranges(){
        let cp = new_compact_params(3.0, 9, 7).unwrap();

        assert_eq!(cp.get_kth_sub_range(0, 0), Some((1,1)));
        assert_eq!(cp.get_kth_sub_range(0, 1), Some((2,2)));
        assert_eq!(cp.get_kth_sub_range(0, 2), Some((3,3)));

        assert!(cp.get_kth_sub_range(0, 3).is_none());

        let cp = new_compact_params(3.5, 9, 7).unwrap();

        assert_eq!(cp.get_kth_sub_range(2, 0), Some((13, 17)));
        assert_eq!(cp.get_kth_sub_range(2, 1), Some((17, 21)));
        assert_eq!(cp.get_kth_sub_range(2, 2), Some((21, 25)));
        assert_eq!(cp.get_kth_sub_range(2, 3), Some((25, 29)));
        assert_eq!(cp.get_kth_sub_range(2, 4), Some((29, 33)));
        assert_eq!(cp.get_kth_sub_range(2, 5), Some((33, 37)));
        assert_eq!(cp.get_kth_sub_range(2, 6), Some((37, 42)));
        assert!(cp.get_kth_sub_range(2, 7).is_none());

        assert_eq!(cp.get_kth_sub_range(3, 0), Some((43, 58)));
        assert_eq!(cp.get_kth_sub_range(3, 1), Some((58, 73)));
        assert_eq!(cp.get_kth_sub_range(3, 2), Some((73, 88)));
        assert_eq!(cp.get_kth_sub_range(3, 3), Some((88, 104)));
        assert_eq!(cp.get_kth_sub_range(3, 4), Some((104, 119)));
        assert_eq!(cp.get_kth_sub_range(3, 5), Some((119, 134)));
        assert_eq!(cp.get_kth_sub_range(3, 6), Some((134, 150)));
    }

    #[test]
    fn pos_leases(){
        let cp = new_compact_params(2.0, 3, 2).unwrap();
        assert_eq!(cp.possible_leases(), vec![1,2,3,4,6,8]);
        let cp = new_compact_params(3.0, 3, 2).unwrap();
        assert_eq!(cp.possible_leases(), vec![1,2,6,9,18,27]);
        let cp = new_compact_params(4.0, 4, 2).unwrap();
        assert_eq!(cp.possible_leases(), vec![2,4,10,16,40,64,160,256]);
        let cp = new_compact_params(4.0, 4, 3).unwrap();
        assert_eq!(cp.possible_leases(), vec![1,2,3,8,12,16,32,48,64,128,192,256]);
    }

    #[test]
    fn index_buckets(){
        let cp = new_compact_params(2.0, 5, 4).unwrap();
        assert_eq!(cp.bucket_index(1), Some(0));
        assert_eq!(cp.bucket_index(2), Some(0));
        assert_eq!(cp.bucket_index(3), Some(1));
        assert_eq!(cp.bucket_index(4), Some(1));
        assert_eq!(cp.bucket_index(5), Some(2));
        assert_eq!(cp.bucket_index(7), Some(2));
        assert_eq!(cp.bucket_index(8), Some(2));
        assert_eq!(cp.bucket_index(9), Some(3));
        assert_eq!(cp.bucket_index(32), Some(4));
        assert!(cp.bucket_index(33).is_none());

        let cp = new_compact_params(3.7, 5, 4).unwrap();
        assert_eq!(cp.bucket_index(1), Some(0));
        assert_eq!(cp.bucket_index(2), Some(0));
        assert_eq!(cp.bucket_index(3), Some(0));
        assert_eq!(cp.bucket_index(4), Some(1));
        assert_eq!(cp.bucket_index(5), Some(1));
        assert_eq!(cp.bucket_index(13), Some(1));
        assert_eq!(cp.bucket_index(14), Some(2));
        assert_eq!(cp.bucket_index(50), Some(2));
        assert_eq!(cp.bucket_index(51), Some(3));
    }


}

// contains the parameters for compressing and reinterpreting the histograms
// this should never be built except by cloning and the new_grid_params function below
/// `CompactParams` contains 3 critical parameters determining how a [`CompactHistogram`]
/// is stored and interpreted. See [`CompactHistogram`] for a full explanation.
///
/// # Example
/// To create your own parameters, use the constructor function
/// ```
/// # use c2_histograms::c2::{new_compact_params};
/// if let Some(cp) = new_compact_params(4.5, 12, 9) {
///     // do something...
/// } else { }
/// ```
///
/// [`CompactHistogram`]: struct.CompactHistogram.html
#[derive(Debug, Clone)]
pub struct CompactParams {
    // the logarithmic base
    base : f64,

    // the maximum RI to have a bucket
    max : f64,

    // the number of buckets
    num_buckets : usize,

    // the number of sub-ranges
    k : usize
}

impl CompactParams {

    // accessors
    pub fn max(&self) -> f64 { self.max }
    pub fn base(&self) -> f64 { self.base }
    pub fn k(&self) -> usize { self.k }
    pub fn num_buckets(&self) -> usize { self.num_buckets }

    /* for all practical purposes this is irrelevant, just confuses things (also deprecated)
    pub fn bucket_labels(&self) -> Vec<usize> {
        let nb = self.num_buckets();
        let mut output = vec![];
        output.reserve(nb+1);
        for i in 0..nb+1 {
            output.insert(i,(self.base.powi(i as i32).floor() + 0.1) as usize);
        }
        output
    }*/

    // definitely not the most efficient way to do it
    // compute all possible leases that this grid/ch can represent
    pub fn possible_leases(&self) -> Vec<usize> {
        let mut output = vec![];
        let mut counter = 0;
        output.reserve(self.num_buckets * self.k);
        for b in 0..self.num_buckets {
            for k_i in 0..self.k {
                if let Some((_min, max)) = self.get_kth_sub_range(b, k_i) {
                    output.insert(counter, max as usize);
                    counter += 1;
                }
            }
        }
        output
    }

    // returns a the kth sub-range in the bth bucket
    // k_i must be less than k
    // if k is larger than the length of the bucket, the reuse interval is completely
    // determined, it is min + k_i, and k_i <= min - max
    pub fn get_kth_sub_range(&self, bucket_index :usize, k_i :usize) -> Option<(usize, usize)> {
        if k_i >= self.k { return None };

        // get the overall range of the bucket
        if let Some((r_min, r_max)) = self.range(bucket_index) {

            // compute the difference
            let range = r_max - r_min;

            // directly placed item special case
            if self.k >= range {
                if k_i > range { return None; }
                return Some((k_i + r_min, k_i + r_min));
            }

            // compute the lower and upper bounds on the sub-range and return
            let sub_range = range as f64 / self.k as f64;
            let lower = r_min + (sub_range * k_i as f64) as usize;
            let higher = r_min + (sub_range * (k_i + 1) as f64) as usize;

            return Some((lower, higher));
        }

        None
    }

    // returns the range of the ith bucket under these parameters
    // [1..base][base+1..base^2]..[base^(i)+1,base^(i+1)]
    pub(crate) fn range(&self, bucket_index : usize) -> Option<(usize, usize)> {
        // if it's not a valid bucket, return nothing
        if bucket_index >= self.num_buckets() {
            None
        } else if bucket_index == 0 {
            Some((1, self.base as usize))
        } else {
            let lower = self.base.powi(bucket_index as i32) as usize + 1;
            let higher = self.base.powi((bucket_index+1) as i32) as usize;
            Some((lower, higher))
        }
    }

    // returns the bucket index that this RI would be placed in under these params
    pub fn bucket_index(&self, ri : usize) -> Option<usize> {
        // this is frequent and always the same regardless of base
        if ri == 1 {
            Some(0)

            // if we're overflowing the compressed histogram / grid, return none
        } else if ri as f64 > self.max || ri == 0 { // ri should never be zero but it's good to check
            None
        } else {
            let bi = (ri as f64).log(self.base);

            // if the r_i is a perfect power of the base:
            if bi.fract() == 0.0 {
                if bi == 1.0 {
                    Some(0)
                } else {
                    Some(bi as usize - 1)
                }
            } else {  // otherwise:
                Some(((ri as f64 - 0.1).log(self.base).floor() + 0.1) as usize)
            }
        }
    }

}

/// ensures that the parameters are all valid and if so creates a new `CompactParams` struct
///
/// For [`CompactParams`], b must be greater than or equal to 1.0, and n, k > 0.
///
/// [`CompactParams`]: struct.CompactParams.html
pub fn new_compact_params(b: f64, n: usize, k: usize) -> Option<CompactParams> {
    if b <= 1.0 || k == 0 || n == 0 {
        None
    } else {
        let max = b.powi(n as i32);
        Some(CompactParams { base: b, max, num_buckets: n, k })
    }
}

impl HistogramParams for CompactParams {}

/// `CompactHistogram` is a fixed-size representation of a histogram. The set of possible
/// labels are partitioned into logarithmically scaled ranges, then further subdivided into
/// equally sized sub-ranges (equally sized within a given range).
/// A `CompactHistogram` stores a counter for each of the larger logarithmic ranges and which
/// of the equally sized sub-ranges contains the frequency-weighted average of the labels.
/// It is associated with [`CompactParams`].
///
/// There are 3 parameters that govern this process:
/// - n -> the number of logarithmically sized ranges to represent
/// - k -> the number of equally sized sub-ranges that each larger range is divided into
/// - b -> a floating point number that determines the size of each of the logarithmically
///         scaled buckets. The ranges are [1..b], [b+1..b^2], ..., [b^(n)+1,b^(n+1)].
///
/// Each compact histogram can be stored in n * (c + log_2(k)) + c bits, where c is the number of
/// bits dedicated to a counter. Note that this value is independent of b.
///
/// This histogram also keeps track of how many labels "overflow", i.e. are too large to fit
/// into any of the ranges. The labels themselves are lost, but the frequencies are recorded and
/// included in total.
///
/// A `CompactHistogram` must be derived from a [`StandardHistogram`] using the [`to_compact`] function.
///
/// [`CompactParams`]: struct.CompactParams.html
/// [`StandardHistogram`]: ../standard/struct.StandardHistogram.html
/// [`to_compact`]: ../standard/struct.StandardHistogram.html#method.to_compact
pub struct CompactHistogram {
    // the counters for the total # ri's in a bucket
    pub(crate) counters : Vec<usize>,

    // the sub-range into which the average ri falls
    pub(crate) sub_range_averages : Vec<usize>, // range from 0 - k-1

    pub(crate) overflowed : usize // the number of addresses that overflowed
}

impl Histogram<CompactParams, usize, usize> for CompactHistogram {
    // this is the same as in c2, make sure to update both...
    // code copying isn't great but no better approach in this case
    fn labels(&self, params : &CompactParams) -> Option<Box<dyn Iterator<Item=usize>>>{
        let mut v = Vec::new();
        let mut count = 0;
        for i in 0..params.num_buckets {
            if let Some((_min, max)) = params.get_kth_sub_range(
                i, self.sub_range_averages[i]) {
                if !v.contains(&max) {
                    v.insert(count, max);
                    count += 1;
                }
            }
        }
        Some(Box::new(v.into_iter()))
    }

    fn frequency(&self, label : usize, params : &CompactParams) -> Option<usize> {
        if let Some(bi) = params.bucket_index(label) {
            if let Some(&s) = self.counters.get(bi) {
                Some(s)
            } else { None }
        } else { Some(0) }
    }

    fn total(&self) -> usize {
        let mut sum: usize = 0;
        for i in 0..self.counters.len() {
            sum += self.counters[i];
        }
        return sum + self.overflowed as usize;
    }
}


// -----------------------------------------------------------------------------------
// --- COMPRESSED HISTOGRAM ----------------------------------------------------------
// -----------------------------------------------------------------------------------
#[cfg(test)]
mod compress_testing {
    use crate::c2::{new_compressed_params};

    #[test]
    fn init_params(){
        assert!(new_compressed_params(2.0, 5).is_some());
        assert!(new_compressed_params(5.0, 51).is_some());
        assert!(new_compressed_params(6.8, 15).is_some());
        assert!(new_compressed_params(1.5, 34).is_some());
        assert!(new_compressed_params(1.0, 21).is_none());
        assert!(new_compressed_params(-0.5, 12).is_none());
        assert!(new_compressed_params(2.0, 0).is_none());
    }

    #[test]
    fn compression(){
        let cp = new_compressed_params(2.0, 5).unwrap();
        assert_eq!(cp.compress_count(0), Some(0));
        assert_eq!(cp.compress_count(2), Some(1));
        assert_eq!(cp.compress_count(3), Some(2));
        assert_eq!(cp.compress_count(4), Some(2));
        assert_eq!(cp.compress_count(5), Some(3));
        assert_eq!(cp.compress_count(7), Some(3));
        assert_eq!(cp.compress_count(8), Some(3));
        assert_eq!(cp.compress_count(9), Some(4));
        assert_eq!(cp.compress_count(31), Some(5));
        assert_eq!(cp.compress_count(35), Some(5));
        assert_eq!(cp.compress_count(300), Some(5));

        let cp = new_compressed_params(1.5, 15).unwrap();

        assert_eq!(cp.compress_count(0), Some(0));
        assert_eq!(cp.compress_count(1), Some(1));
        assert_eq!(cp.compress_count(2), Some(2));
        assert_eq!(cp.compress_count(3), Some(3));
        assert_eq!(cp.compress_count(4), Some(4));
        assert_eq!(cp.compress_count(5), Some(4));
        assert_eq!(cp.compress_count(6), Some(5));
        assert_eq!(cp.compress_count(7), Some(5));
        assert_eq!(cp.compress_count(8), Some(6));
        assert_eq!(cp.compress_count(9), Some(6));
        assert_eq!(cp.compress_count(10), Some(6));
        assert_eq!(cp.compress_count(11), Some(6));
        assert_eq!(cp.compress_count(12), Some(7));
        assert_eq!(cp.compress_count(13), Some(7));
        assert_eq!(cp.compress_count(300), Some(15));
        assert_eq!(cp.compress_count(500), Some(15));
        assert_eq!(cp.compress_count(5000), Some(15));
    }

    #[test]
    fn decompression(){
        let cp = new_compressed_params(2.0, 5).unwrap();
        assert_eq!(cp.decompress_count(0), Some(0));
        assert_eq!(cp.decompress_count(1), Some(2));
        assert_eq!(cp.decompress_count(2), Some(4));
        assert_eq!(cp.decompress_count(3), Some(8));
        assert_eq!(cp.decompress_count(4), Some(16));
        assert_eq!(cp.decompress_count(5), Some(32));
        assert!(cp.decompress_count(6).is_none());

        let cp = new_compressed_params(1.5, 15).unwrap();
        assert_eq!(cp.decompress_count(0), Some(0));
        assert_eq!(cp.decompress_count(1), Some(1));
        assert_eq!(cp.decompress_count(2), Some(2));
        assert_eq!(cp.decompress_count(3), Some(3));
        assert_eq!(cp.decompress_count(4), Some(5));
        assert_eq!(cp.decompress_count(5), Some(7));
        assert_eq!(cp.decompress_count(9), Some(38));
        assert_eq!(cp.decompress_count(10), Some(57));
        assert_eq!(cp.decompress_count(11), Some(86));
        assert_eq!(cp.decompress_count(12), Some(129));
        assert_eq!(cp.decompress_count(13), Some(194));
        assert!(cp.decompress_count(16).is_none());
    }

    #[test]
    fn decomp_comp(){
        let cp = new_compressed_params(2.0, 5).unwrap();
        assert_eq!(cp.decompress_count(cp.compress_count(1).unwrap()), Some(2));
        assert_eq!(cp.decompress_count(cp.compress_count(2).unwrap()), Some(2));
        assert_eq!(cp.decompress_count(cp.compress_count(3).unwrap()), Some(4));
        assert_eq!(cp.decompress_count(cp.compress_count(4).unwrap()), Some(4));
        assert_eq!(cp.decompress_count(cp.compress_count(5).unwrap()), Some(8));
        assert_eq!(cp.decompress_count(cp.compress_count(6).unwrap()), Some(8));
        assert_eq!(cp.decompress_count(cp.compress_count(7).unwrap()), Some(8));
        assert_eq!(cp.decompress_count(cp.compress_count(8).unwrap()), Some(8));
        assert_eq!(cp.decompress_count(cp.compress_count(9).unwrap()), Some(16));
        assert_eq!(cp.decompress_count(cp.compress_count(10).unwrap()), Some(16));
        assert_eq!(cp.decompress_count(cp.compress_count(11).unwrap()), Some(16));
        assert_eq!(cp.decompress_count(cp.compress_count(12).unwrap()), Some(16));
        assert_eq!(cp.decompress_count(cp.compress_count(13).unwrap()), Some(16));
        assert_eq!(cp.decompress_count(cp.compress_count(14).unwrap()), Some(16));
        assert_eq!(cp.decompress_count(cp.compress_count(15).unwrap()), Some(16));
    }

}

#[derive(Debug, Clone)]
/// `CompactParams` contains 2 parameters determining how a [`CompressedHistogram`]
/// is stored and interpreted. See [`CompressedHistogram`] for a full explanation.
///
/// # Example
/// To create your own parameters, use the constructor function
/// ```
/// # use c2_histograms::c2::{new_compressed_params};
/// if let Some(cp) = new_compressed_params(2.0, 15) {
///     // do something...
/// } else { }
/// ```
/// [`CompressedHistogram`]: struct.CompressedHistogram.html
pub struct CompressedParams {
    base : f64,
    max_exp : usize,

    // lookup table for faster calculation of
    table:  Vec<usize>
}

impl CompressedParams {
    pub fn base(&self) -> f64 { self.base }
    pub fn max_exp(&self) -> usize { self.max_exp }
}

/// checks parameters for validity and if so creates a new `CompressedParams` struct
///
/// For [`CompressedParams`], the base must be greater than 1.0, and the max_exp must be
/// nonzero.
///
/// [`CompressedParams`]: struct.CompressedParams.html
pub fn new_compressed_params(base : f64, max_exp : usize) -> Option<CompressedParams> {
    if base <= 1.01 || max_exp == 0 {
        None
    } else {
        let mut table = Vec::new();
        table.reserve_exact(max_exp + 1);


        // this is ideal for compressedHistogram, but for C2, 0 -> 0
        // or else it breaks
        //table.insert(0, 1);
        table.insert(0, 0);

        for i in 1..(max_exp+1) {
            let mut expanded = base.powi(i as i32);

            // make sure we don't get too big
            if expanded > usize::MAX as f64 / (base * base) {
                for j in i..(max_exp+1) {
                    table.insert(j, expanded as usize);
                }
                break;
            }

            // continue until we get a new value
            while expanded as usize <= table[i-1] {
                expanded = expanded * base;
            }

            let expanded = expanded as usize;

            table.insert(i, expanded);
        }

        Some(CompressedParams { base, max_exp, table })
    }
}

impl HistogramParams for CompressedParams {}

impl CompressedParams {
    pub(crate) fn compress_count(&self, count : usize) -> Option<u16> {
        if count == 0 { // this should only happen in C2Histograms
            Some(0)
        } else if (count as f64) < self.base {
            Some(1)
        } else if count > self.table[self.max_exp]{
            Some(self.max_exp as u16)
        } else {
            // we need to binary search the table
            // for the index of the element which is just greater than count
            let mut min = 0;
            let mut max = self.max_exp+1;
            let mut mid;

            loop {
                mid = (min + max) / 2;
                if self.table[mid] >= count && self.table[mid - 1] < count {
                    break;
                }
                else if self.table[mid] > count {
                    max = mid;
                }
                else if self.table[mid] < count {
                    min = mid;
                }
            }

            Some(mid as u16)

        }
    }

    // IN ORDER FOR C2 TO FUNCTION PROPERLY, 0 -> 0
    pub(crate) fn decompress_count(&self, compressed_count : u16) -> Option<usize> {
        if compressed_count > self.max_exp as u16 {
            None
        } else {
            Some(self.table[compressed_count as usize])
        }
    }
}

#[allow(dead_code)]
/// Though not fixed, `CompressedHistogram` encodes histograms using less space than a `StandardHistogram`.
/// All of the frequencies for each label are approximated by a next greatest exponent.
/// `CompressedHistogram` uses a library HashMap to store the label-frequency pairs, so it is
/// unbounded in terms of space. It is associated with [`CompressedParams`]
///
/// There are 2 parameters:
/// - b -> This floating point number is the base of the approximating exponent.
/// - max_exp -> This is the number of distinct values that can potentially be stored.
///
/// A `CompressedHistogram` must be derived from a [`StandardHistogram`] using the [`to_compressed`]
/// function.
///
/// [`CompressedParams`]: struct.CompressedParams.html
/// [`StandardHistogram`]: ../standard/struct.StandardHistogram.html
/// [`to_compressed`]: ../standard/struct.StandardHistogram.html#method.to_compressed
///
pub struct CompressedHistogram {
    // maps from ris to compressed counters
    pub(crate) data : HashMap<usize, u16>,
    pub(crate) total : usize,
    pub(crate) orig_total : usize
}

impl Histogram<CompressedParams, usize, usize> for CompressedHistogram {
    fn labels(&self, _params: &CompressedParams) -> Option<Box<dyn Iterator<Item=usize>>> {
        let mut out : Vec<usize> = vec![];
        let mut counter : usize = 0;
        for k in self.data.keys(){
            out.insert(counter, *k);
            counter += 1;
        }
        Some(Box::new(out.into_iter()))
    }

    fn frequency(&self, label: usize, params: &CompressedParams) -> Option<usize> {
        if let Some(c) = self.data.get(&label) {
            params.decompress_count(*c)
        } else {
            None
        }
    }

    /// returns whichever is greater, the compressed or decompressed size
    fn total(&self) -> usize {
        if self.total > self.orig_total {
            self.total
        } else {
            self.orig_total
        }
    }
}


// -----------------------------------------------------------------------------------
// --- C2 HISTOGRAM ------------------------------------------------------------------
// -----------------------------------------------------------------------------------

#[derive(Debug, Clone)]
/// `C2Params` are a wrapper struct for a set of [`CompactParams`] and [`CompressedParams`].
///
/// # Example
/// To create your own parameters, use the constructor function
/// ```
/// # use c2_histograms::c2::{new_compressed_params, new_compact_params, new_c2_params};
/// if let Some(cp1) = new_compact_params(2.0, 15, 9) {
///     if let Some(cp2) = new_compressed_params(1.4, 31) {
///         let cp = new_c2_params(cp1, cp2);
///         // do something
///     } else { }
/// } else { }
/// ```
///
/// [`CompactParams`]: struct.CompactParams.html
/// [`CompressedParams`]: struct.CompressedParams.html
pub struct C2Params {
    compact_params : CompactParams,
    compressed_params : CompressedParams
}

impl C2Params {
    /// returns a reference to the underlying CompactParameters
    pub fn compact_ps(&self) -> &CompactParams { &self.compact_params }

    /// returns a reference to the underlying CompressedParameters
    pub fn compressed_ps(&self) -> &CompressedParams { &self.compressed_params }
}

impl HistogramParams for C2Params {}

/// Wraps [`CompactParams`] and [`CompressedParams`].
///
/// [`CompactParams`]: struct.CompactParams.html
/// [`CompressedParams`]: struct.CompressedParams.html
// this doesn't really need any tests
// this set of parameters really doesn't need it's own set of functions either (just accessors),
// it can piggy-back off of the other ones
pub fn new_c2_params(compacts : CompactParams, compresseds : CompressedParams) -> C2Params {
    C2Params { compact_params : compacts, compressed_params : compresseds }
}

#[allow(dead_code)]
/// `C2Histogram` is a combination of [`CompressedHistogram`] and [`CompactHistogram`], performing
/// the memory saving operations from each of them. It is associated with [`C2Params`].
///
/// Each c2 histogram can be stored in n * (c + log2(k)) + c bits, where c = log2(max_exp)
///
/// A `C2Histogram` must be derrived from a [`StandardHistogram`] using the [`to_c2`] function.
///
/// [`CompressedHistogram`]: struct.CompressedHistogram.html
/// [`CompactHistogram`]: struct.CompactHistogram.html
/// [`C2Params`]: struct.C2Params.html
/// [`StandardHistogram`]: ../standard/struct.StandardHistogram.html
/// [`to_c2`]: ../standard/struct.StandardHistogram.html#method.to_c2
///
pub struct C2Histogram {
    // compressed counters
    pub(crate) counters : Vec<u16>,

    // sub-range averages
    pub(crate) sub_range_averages : Vec<usize>,

    // the pre-compression total
    // may be useful in saving memory?
    pub(crate) orig_total : usize,

    pub(crate) total : usize,

    // the amount of labels that overflowed the compaction process
    pub(crate) overflowed: usize

}

impl Histogram<C2Params, usize, usize> for C2Histogram {
    // this is exactly the same as compact
    fn labels(&self, params: &C2Params) -> Option<Box<dyn Iterator<Item=usize>>> {
        let params = params.compact_ps();
        let mut v = HashSet::new();
        for i in 0..params.num_buckets() {
            if let Some((_min, max)) = params.get_kth_sub_range(
                i, self.sub_range_averages[i]) {
                v.insert(max as usize);
            }
        }
        Some(Box::new(v.into_iter()))
    }

    // this is pretty much a combination of the two
    fn frequency(&self, label: usize, params: &C2Params) -> Option<usize> {
        if let Some(bi) = params.compact_params.bucket_index(label) {
            if let Some(&s) = self.counters.get(bi) {
                params.compressed_params.decompress_count(s)
            } else { None }
        } else { Some(0) }
    }

    fn total(&self) -> usize {
        self.total + self.overflowed
    }
}