ddk-trie 1.1.2

Data structures for storage and retrival of numerical Discreet Log Contracts (DLC).
Documentation 
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

//! # Combination Iterator
//! Utility struct and functions too support iterating though all possible
//! t combinations of n elements (where t >= n).

/// Structure to use to support iteration through all possible t combinations
/// of n elements.
pub struct CombinationIterator {
    selector: Vec<usize>,
    pub(crate) nb_selected: usize,
    pub(crate) nb_elements: usize,
    is_init: bool,
}

impl CombinationIterator {
    /// Creates a new combination iterator for a collection of `nb_elements`
    /// where each combination includes `nb_selected` elements. Panics if
    /// `nb_elements < nb_selected`.
    pub fn new(nb_elements: usize, nb_selected: usize) -> CombinationIterator {
        assert!(nb_elements >= nb_selected);

        let selector = (0..nb_selected).collect();
        CombinationIterator {
            selector,
            nb_elements,
            nb_selected,
            is_init: false,
        }
    }

    /// Returns the index of the provided combination if part of the set of
    /// combinations produced by the iterator, None otherwise.
    pub fn get_index_for_combination(self, combination: &[usize]) -> Option<usize> {
        for (i, cur) in self.enumerate() {
            if combination == cur {
                return Some(i);
            }
        }

        None
    }
}

impl Iterator for CombinationIterator {
    type Item = Vec<usize>;
    fn next(&mut self) -> Option<Self::Item> {
        if !self.is_init {
            self.is_init = true;
            return Some(self.selector.clone());
        }

        let last_index = self.nb_selected - 1;
        let mut cur_index = last_index;
        while cur_index > 0
            && self.selector[cur_index] == self.nb_elements - 1 - (last_index - cur_index)
        {
            cur_index -= 1;
        }

        self.selector[cur_index] += 1;
        cur_index += 1;

        while cur_index <= last_index {
            self.selector[cur_index] = self.selector[cur_index - 1] + 1;
            cur_index += 1;
        }

        if self.selector[0] == self.nb_elements - self.nb_selected + 1 {
            return None;
        }

        Some(self.selector.clone())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn generate_combinations_test() {
        let combination_iterator = CombinationIterator::new(4, 3);
        let expected = vec![vec![0, 1, 2], vec![0, 1, 3], vec![0, 2, 3], vec![1, 2, 3]];

        for (i, cur) in combination_iterator.enumerate() {
            assert_eq!(cur, expected[i]);
        }
    }

    #[test]
    fn get_combination_index_test() {
        let combination_iterator = CombinationIterator::new(4, 3);

        assert_eq!(
            2,
            combination_iterator
                .get_index_for_combination(&[0, 2, 3])
                .expect("Could not find combination")
        );
    }
}