1 | use super::*; |
2 | use std::sync::atomic::AtomicUsize; |
3 | |
4 | #[test] |
5 | fn same_range_first_consumers_return_correct_answer() { |
6 | let find_op = |x: &i32| x % 2 == 0; |
7 | let first_found = AtomicUsize::new(usize::max_value()); |
8 | let far_right_consumer = FindConsumer::new(&find_op, MatchPosition::Leftmost, &first_found); |
9 | |
10 | // We save a consumer that will be far to the right of the main consumer (and therefore not |
11 | // sharing an index range with that consumer) for fullness testing |
12 | let consumer = far_right_consumer.split_off_left(); |
13 | |
14 | // split until we have an indivisible range |
15 | let bits_in_usize = usize::min_value().count_zeros(); |
16 | |
17 | for _ in 0..bits_in_usize { |
18 | consumer.split_off_left(); |
19 | } |
20 | |
21 | let reducer = consumer.to_reducer(); |
22 | // the left and right folders should now have the same range, having |
23 | // exhausted the resolution of usize |
24 | let left_folder = consumer.split_off_left().into_folder(); |
25 | let right_folder = consumer.into_folder(); |
26 | |
27 | let left_folder = left_folder.consume(0).consume(1); |
28 | assert_eq!(left_folder.boundary, right_folder.boundary); |
29 | // expect not full even though a better match has been found because the |
30 | // ranges are the same |
31 | assert!(!right_folder.full()); |
32 | assert!(far_right_consumer.full()); |
33 | let right_folder = right_folder.consume(2).consume(3); |
34 | assert_eq!( |
35 | reducer.reduce(left_folder.complete(), right_folder.complete()), |
36 | Some(0) |
37 | ); |
38 | } |
39 | |
40 | #[test] |
41 | fn same_range_last_consumers_return_correct_answer() { |
42 | let find_op = |x: &i32| x % 2 == 0; |
43 | let last_found = AtomicUsize::new(0); |
44 | let consumer = FindConsumer::new(&find_op, MatchPosition::Rightmost, &last_found); |
45 | |
46 | // We save a consumer that will be far to the left of the main consumer (and therefore not |
47 | // sharing an index range with that consumer) for fullness testing |
48 | let far_left_consumer = consumer.split_off_left(); |
49 | |
50 | // split until we have an indivisible range |
51 | let bits_in_usize = usize::min_value().count_zeros(); |
52 | for _ in 0..bits_in_usize { |
53 | consumer.split_off_left(); |
54 | } |
55 | |
56 | let reducer = consumer.to_reducer(); |
57 | // due to the exact calculation in split_off_left, the very last consumer has a |
58 | // range of width 2, so we use the second-to-last consumer instead to get |
59 | // the same boundary on both folders |
60 | let consumer = consumer.split_off_left(); |
61 | let left_folder = consumer.split_off_left().into_folder(); |
62 | let right_folder = consumer.into_folder(); |
63 | let right_folder = right_folder.consume(2).consume(3); |
64 | assert_eq!(left_folder.boundary, right_folder.boundary); |
65 | // expect not full even though a better match has been found because the |
66 | // ranges are the same |
67 | assert!(!left_folder.full()); |
68 | assert!(far_left_consumer.full()); |
69 | let left_folder = left_folder.consume(0).consume(1); |
70 | assert_eq!( |
71 | reducer.reduce(left_folder.complete(), right_folder.complete()), |
72 | Some(2) |
73 | ); |
74 | } |
75 | |
76 | // These tests requires that a folder be assigned to an iterator with more than |
77 | // one element. We can't necessarily determine when that will happen for a given |
78 | // input to find_first/find_last, so we test the folder directly here instead. |
79 | #[test] |
80 | fn find_first_folder_does_not_clobber_first_found() { |
81 | let best_found = AtomicUsize::new(usize::max_value()); |
82 | let f = FindFolder { |
83 | find_op: &(|&_: &i32| -> bool { true }), |
84 | boundary: 0, |
85 | match_position: MatchPosition::Leftmost, |
86 | best_found: &best_found, |
87 | item: None, |
88 | }; |
89 | let f = f.consume(0_i32).consume(1_i32).consume(2_i32); |
90 | assert!(f.full()); |
91 | assert_eq!(f.complete(), Some(0_i32)); |
92 | } |
93 | |
94 | #[test] |
95 | fn find_last_folder_yields_last_match() { |
96 | let best_found = AtomicUsize::new(0); |
97 | let f = FindFolder { |
98 | find_op: &(|&_: &i32| -> bool { true }), |
99 | boundary: 0, |
100 | match_position: MatchPosition::Rightmost, |
101 | best_found: &best_found, |
102 | item: None, |
103 | }; |
104 | let f = f.consume(0_i32).consume(1_i32).consume(2_i32); |
105 | assert_eq!(f.complete(), Some(2_i32)); |
106 | } |
107 | |