fn analyze_with_infinity<T>(
values: &[T],
first_infinity: usize,
extrema: Option<(T, T)>,
) -> InputCharacteristics<T>where
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/selector.rs (line 61)
41fn analyze<T>(values: &[T]) -> InputCharacteristics<T>
42where
43 T: Signed,
44{
45 let Some(&first) = values.first() else {
46 return InputCharacteristics {
47 finite_count: 0,
48 finite_prefix_len: 0,
49 finite_entries: Vec::new(),
50 run_entries: Some(Vec::new()),
51 extrema: None,
52 is_convex: true,
53 is_concave: true,
54 is_nondecreasing: true,
55 is_nonincreasing: true,
56 run_count: 0,
57 piece_count: 0,
58 };
59 };
60 if first.is_maximum() {
61 return analyze_with_infinity(values, 0, None);
62 }
63
64 let mut minimum = first;
65 let mut maximum = first;
66 let mut is_convex = true;
67 let mut is_concave = true;
68 let mut is_nondecreasing = true;
69 let mut is_nonincreasing = true;
70 let mut run_count = 1;
71 let mut run_entries = Some(vec![(0, first)]);
72 let mut piece_count = 1;
73 let mut previous_value = first;
74 let mut previous_slope = None;
75
76 for (index, &value) in values.iter().enumerate().skip(1) {
77 if value.is_maximum() {
78 return analyze_with_infinity(values, index, Some((minimum, maximum)));
79 }
80 minimum = minimum.min(value);
81 maximum = maximum.max(value);
82 is_nondecreasing &= previous_value <= value;
83 is_nonincreasing &= previous_value >= value;
84 if previous_value != value {
85 run_count += 1;
86 if let Some(entries) = &mut run_entries {
87 if entries.len() == MAX_CACHED_RUNS {
88 run_entries = None;
89 } else {
90 entries.push((index, value));
91 }
92 }
93 }
94 let slope = value - previous_value;
95 if let Some(previous_slope) = previous_slope {
96 is_convex &= previous_slope <= slope;
97 is_concave &= previous_slope >= slope;
98 piece_count += usize::from(previous_slope != slope);
99 }
100 previous_slope = Some(slope);
101 previous_value = value;
102 }
103 InputCharacteristics {
104 finite_count: values.len(),
105 finite_prefix_len: values.len(),
106 finite_entries: Vec::new(),
107 run_entries,
108 extrema: Some((minimum, maximum)),
109 is_convex,
110 is_concave,
111 is_nondecreasing,
112 is_nonincreasing,
113 run_count,
114 piece_count,
115 }
116}