| use super::SeparatorPolicy; |
| |
| #[derive(Debug)] |
| pub struct SeparatorIterator<'a> { |
| groups: &'a [u8], |
| repeat_groups_remaining: usize, |
| current_group_index: usize, |
| current_group_size: usize, |
| len: usize, |
| } |
| |
| impl<'a> SeparatorIterator<'a> { |
| pub fn new(policy: &'a SeparatorPolicy, len: usize) -> Self { |
| let groups = &policy.groups; |
| |
| let mut sum = 0; |
| |
| for (index, &group) in groups.into_iter().enumerate() { |
| sum += group as usize; |
| |
| if len <= sum { |
| return SeparatorIterator { |
| groups, |
| repeat_groups_remaining: 0, |
| current_group_index: index, |
| current_group_size: len - (sum - group as usize), |
| len, |
| } |
| } |
| } |
| |
| let repeat_group_len = match groups.last() { |
| Some(n) => *n as usize, |
| None => |
| return SeparatorIterator { |
| groups: &[], |
| repeat_groups_remaining: 0, |
| current_group_index: 0, |
| current_group_size: 0, |
| len, |
| } |
| }; |
| |
| let len_remaining = len - sum; |
| let (repeat_groups_remaining, current_group_size) |
| = ceil_div_mod(len_remaining, repeat_group_len); |
| |
| SeparatorIterator { |
| groups, |
| repeat_groups_remaining, |
| current_group_index: groups.len() - 1, |
| current_group_size, |
| len, |
| } |
| } |
| |
| /// How many separators remain? |
| pub fn sep_len(&self) -> usize { |
| self.current_group_index + self.repeat_groups_remaining |
| } |
| } |
| |
| impl<'a> Iterator for SeparatorIterator<'a> { |
| type Item = bool; |
| |
| fn next(&mut self) -> Option<Self::Item> { |
| self.len = self.len.checked_sub(1)?; |
| |
| self.current_group_size = self.current_group_size.saturating_sub(1); |
| if self.current_group_size > 0 { |
| return Some(false); |
| } |
| |
| if let Some(repeat_groups_remaining) = self.repeat_groups_remaining.checked_sub(1) { |
| self.repeat_groups_remaining = repeat_groups_remaining; |
| } else if let Some(current_group_index) = self.current_group_index.checked_sub(1) { |
| self.current_group_index = current_group_index; |
| } else { |
| return Some(false); |
| } |
| |
| self.current_group_size = self.groups[self.current_group_index] as usize; |
| return Some(true); |
| } |
| |
| fn size_hint(&self) -> (usize, Option<usize>) { |
| (self.len(), Some(self.len())) |
| } |
| } |
| |
| impl<'a> ExactSizeIterator for SeparatorIterator<'a> { |
| fn len(&self) -> usize { |
| self.len |
| } |
| } |
| |
| fn ceil_div_mod(n: usize, m: usize) -> (usize, usize) { |
| let round_up = n + m - 1; |
| (round_up / m, round_up % m + 1) |
| } |
| |
| #[cfg(test)] |
| mod test_common { |
| use super::super::*; |
| pub use super::*; |
| |
| pub fn make_policy(groups: &[u8]) -> SeparatorPolicy { |
| let mut result = policies::COMMA_SEPARATOR; |
| result.groups = groups; |
| result |
| } |
| } |
| |
| #[cfg(test)] |
| mod grouping_test { |
| use super::test_common::*; |
| |
| fn group_string(groups: &[u8], digits: &str) -> String { |
| use std::iter::once; |
| |
| let policy = &make_policy(groups); |
| let iter = SeparatorIterator::new(policy, digits.chars().count()); |
| |
| digits.chars().zip(iter) |
| .flat_map(|(digit, comma_after)| |
| once(digit) |
| .chain(if comma_after { Some(',') } else { None })) |
| .collect() |
| } |
| |
| macro_rules! grouping_test { |
| ( $name:ident, $groups:tt, $result:tt ) => { |
| #[test] |
| fn $name() { |
| let result = $result; |
| let input = $result.chars().filter(|&c| c != ',').collect::<String>(); |
| assert_eq!(group_string(&$groups, &input), result); |
| } |
| }; |
| } |
| |
| grouping_test!(by_nothing_of_0, [], ""); |
| grouping_test!(by_nothing_of_1, [], "1"); |
| grouping_test!(by_nothing_of_2, [], "21"); |
| grouping_test!(by_nothing_of_3, [], "321"); |
| |
| grouping_test!(by_1s_of_0, [1], ""); |
| grouping_test!(by_1s_of_1, [1], "1"); |
| grouping_test!(by_1s_of_2, [1], "2,1"); |
| grouping_test!(by_1s_of_3, [1], "3,2,1"); |
| |
| grouping_test!(by_2s_of_0, [2], ""); |
| grouping_test!(by_2s_of_1, [2], "1"); |
| grouping_test!(by_2s_of_2, [2], "21"); |
| grouping_test!(by_2s_of_3, [2], "3,21"); |
| grouping_test!(by_2s_of_4, [2], "43,21"); |
| grouping_test!(by_2s_of_5, [2], "5,43,21"); |
| grouping_test!(by_2s_of_6, [2], "65,43,21"); |
| grouping_test!(by_2s_of_7, [2], "7,65,43,21"); |
| grouping_test!(by_2s_of_8, [2], "87,65,43,21"); |
| grouping_test!(by_2s_of_9, [2], "9,87,65,43,21"); |
| |
| grouping_test!(by_3s_of_1, [3], "1"); |
| grouping_test!(by_3s_of_2, [3], "21"); |
| grouping_test!(by_3s_of_3, [3], "321"); |
| grouping_test!(by_3s_of_4, [3], "4,321"); |
| grouping_test!(by_3s_of_5, [3], "54,321"); |
| grouping_test!(by_3s_of_6, [3], "654,321"); |
| grouping_test!(by_3s_of_7, [3], "7,654,321"); |
| grouping_test!(by_3s_of_8, [3], "87,654,321"); |
| grouping_test!(by_3s_of_9, [3], "987,654,321"); |
| |
| grouping_test!(by_2s3_of_1, [3, 2], "1"); |
| grouping_test!(by_2s3_of_2, [3, 2], "21"); |
| grouping_test!(by_2s3_of_3, [3, 2], "321"); |
| grouping_test!(by_2s3_of_4, [3, 2], "4,321"); |
| grouping_test!(by_2s3_of_5, [3, 2], "54,321"); |
| grouping_test!(by_2s3_of_6, [3, 2], "6,54,321"); |
| grouping_test!(by_2s3_of_7, [3, 2], "76,54,321"); |
| grouping_test!(by_2s3_of_8, [3, 2], "8,76,54,321"); |
| grouping_test!(by_2s3_of_9, [3, 2], "98,76,54,321"); |
| |
| grouping_test!(by_5s4321_of_20, [1, 2, 3, 4, 5], |
| "KJIHG,FEDCB,A987,654,32,1"); |
| grouping_test!(by_5s4321_of_16, [1, 2, 3, 4, 5], |
| "G,FEDCB,A987,654,32,1"); |
| grouping_test!(by_5s4321_of_11, [1, 2, 3, 4, 5], |
| "B,A987,654,32,1"); |
| grouping_test!(by_5s4321_of_10, [1, 2, 3, 4, 5], |
| "A987,654,32,1"); |
| grouping_test!(by_5s4321_of_9, [1, 2, 3, 4, 5], |
| "987,654,32,1"); |
| grouping_test!(by_5s4321_of_7, [1, 2, 3, 4, 5], |
| "7,654,32,1"); |
| grouping_test!(by_5s4321_of_1, [1, 2, 3, 4, 5], |
| "1"); |
| grouping_test!(by_5s4321_of_0, [1, 2, 3, 4, 5], |
| ""); |
| } |
| |
| #[cfg(test)] |
| mod sep_len_test { |
| use super::test_common::*; |
| |
| fn run_iterator(mut iter: SeparatorIterator) -> (Vec<usize>, Vec<usize>) { |
| let mut predictions = Vec::with_capacity(iter.len()); |
| let mut actuals = Vec::with_capacity(iter.len()); |
| |
| let mut prediction; |
| while let Some(actual) = { |
| prediction = iter.sep_len(); |
| iter.next() |
| } { |
| predictions.push(prediction); |
| actuals.push(if actual { 1 } else { 0 }) |
| } |
| |
| let mut acc = 0; |
| for actual in actuals.iter_mut().rev() { |
| acc += *actual; |
| *actual = acc; |
| } |
| |
| (predictions, actuals) |
| } |
| |
| macro_rules! run_down { |
| ( $name:ident, $groups:tt, $size:tt ) => { |
| #[test] |
| fn $name() { |
| let policy = &make_policy(&$groups); |
| |
| let (predictions, actuals) = |
| run_iterator(SeparatorIterator::new(policy, $size)); |
| |
| assert_eq!(predictions, actuals); |
| } |
| }; |
| } |
| |
| run_down!(by_nothing_of_10, [], 10); |
| |
| run_down!(by_3s_of_10, [3], 10); |
| |
| run_down!(by_2s_of_10, [2], 10); |
| run_down!(by_2s_of_9, [2], 9); |
| run_down!(by_2s_of_8, [2], 8); |
| run_down!(by_2s_of_7, [2], 7); |
| run_down!(by_2s_of_6, [2], 6); |
| run_down!(by_2s_of_5, [2], 5); |
| run_down!(by_2s_of_4, [2], 4); |
| run_down!(by_2s_of_3, [2], 3); |
| run_down!(by_2s_of_2, [2], 2); |
| run_down!(by_2s_of_1, [2], 1); |
| run_down!(by_2s_of_0, [2], 0); |
| |
| run_down!(by_1s23_of_10, [3, 2, 1], 10); |
| run_down!(by_1s23_of_9, [3, 2, 1], 9); |
| run_down!(by_1s23_of_8, [3, 2, 1], 8); |
| run_down!(by_1s23_of_7, [3, 2, 1], 7); |
| run_down!(by_1s23_of_6, [3, 2, 1], 6); |
| run_down!(by_1s23_of_5, [3, 2, 1], 5); |
| run_down!(by_1s23_of_4, [3, 2, 1], 4); |
| run_down!(by_1s23_of_3, [3, 2, 1], 3); |
| run_down!(by_1s23_of_2, [3, 2, 1], 2); |
| run_down!(by_1s23_of_1, [3, 2, 1], 1); |
| run_down!(by_1s23_of_0, [3, 2, 1], 0); |
| } |
