1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

// #![warn(cast_possible_truncation)]
// #![warn(cast_possible_wrap)]
// #![warn(cast_sign_loss)]
// #![warn(filter_map)]
// #![warn(if_not_else)]
// #![warn(items_after_statements)]
// #![warn(nonminimal_bool)]
// #![warn(option_map_unwrap_or)]
// #![warn(option_map_unwrap_or_else)]
// #![warn(option_unwrap_used)]
// #![warn(shadow_reuse)]
// #![warn(shadow_same)]
// #![warn(shadow_unrelated)]
// #![warn(single_match_else)]
// #![warn(wrong_pub_self_convention)]

//! A multiset is a datastructure which resembles a classic Set, except it allows duplicate
//! elements for each key. For more information on Multisets, see:
//!
//! * [Wikipedia Entry](https://en.wikipedia.org/wiki/Multiset)
//! * [C++ Multisets](http://en.cppreference.com/w/cpp/container/multiset)
//! * [C++ Multiset Tutorial](http://www.java2s.com/Tutorial/Cpp/0380__set-multiset/Catalog0380__set-multiset.htm)
//! * _Knuth, Donald. The Art of Computer Programming Volume II, Section 4.6.3, Exercise 19_
//!
//! This crate implements a `CappedMultiset`. A `CappedMultiset` is a datastructure similar to a
//! multiset, except it can have a dynamically defined "cap" on the value of each key. When such a
//! cap is defined, any operation to retrieve the value of an element of the set, the value
//! returned will be no greater than the "cap" on the multiset. This `cap` can be changed at
//! runtime and does not affect the actual data stored in the Multiset. As a result, setting
//! `cap = 1` or any other low value is not a lossy operation.
//!
//! ```rust
//! extern crate capped_multiset;
//!
//! use capped_multiset::CappedMultiset;
//!
//! fn main() {
//!     let set = vec![1, 2, 3, 4, 5];
//!     let mut capped_set = CappedMultiset::new(set);
//!     assert_eq!(capped_set.sum(), 15);
//!     capped_set.set_cap(Some(1));
//!     assert_eq!(capped_set.sum(), 5);
//!     capped_set.set_cap(Some(2));
//!     assert_eq!(capped_set.sum(), 9);
//! }
//! ```

/// A `CappedMultiset` structure is a data structure similar to a multiset with the key distinction
/// that it supports setting a _cap_ on the values of each element. Once a cap is set, all
/// operations on the data structure that access an element will return at most the value of the
/// cap.
#[derive(Hash, Debug, Eq, PartialEq)]
pub struct CappedMultiset {
    elements: Vec<u32>,
    cap: u32,
}

impl CappedMultiset {
    /// Consumes a `Vec<u32>` and returns a `CappedMultiset` with the same values.
    /// By default, no cap is set on the elements of the multiset
    pub fn new(item: Vec<u32>) -> CappedMultiset {
        CappedMultiset {
            elements: item,
            cap: u32::max_value()
        }
    }

    /// Compute the sum of all elements of the multiset, honoring the value of the cap.
    pub fn sum(&self) -> u32 {
        let mut sum = 0;
        for elem in self.elements.iter().map(|&x| std::cmp::min(x, self.cap)) {
            sum += elem;
        }
        sum
    }

    /// Set a cap on the values of the multiset
    pub fn set_cap(&mut self, cap: Option<u32>) {
        self.cap = cap.unwrap_or(u32::max_value());
    }
}

#[cfg(test)]
mod tests {
    use CappedMultiset;
    #[test]
    fn test_sum() {
        let simple_array: Vec<u32> = vec![1,2,3,4,5];
        let mut testset = CappedMultiset::new(simple_array);
        assert_eq!(testset.sum(), 15);
        testset.set_cap(Some(3));
        assert_eq!(testset.sum(), 12);
        testset.set_cap(None);
        assert_eq!(testset.sum(), 15);
        testset.set_cap(Some(1));
        assert_eq!(testset.sum(), 5);
        testset.set_cap(Some(0));
        assert_eq!(testset.sum(), 0);
    }
}