fn bit_width(value: usize) -> u32Examples found in repository?
crates/competitive/src/math/min_plus_convolution/concave.rs (line 32)
29 fn new(arbitrary: &'a [T], concave: &'a [T]) -> Self {
30 let output_len = output_len(arbitrary.len(), concave.len());
31 let leaf_count = 1_usize
32 .checked_shl(bit_width(output_len))
33 .expect("min-plus convolution envelope size must fit usize");
34 ConcaveEnvelope {
35 arbitrary,
36 concave,
37 leaf_count,
38 query_root: leaf_count >> bit_width(concave.len() - 1),
39 node_curves: vec![None; leaf_count],
40 result: vec![T::maximum(); output_len],
41 }
42 }
43
44 #[inline]
45 fn value(&self, curve: usize, output: usize) -> T {
46 self.arbitrary[curve] + self.concave[output - curve]
47 }
48
49 #[inline]
50 fn query(&mut self, output: usize) {
51 let mut best = self.result[output];
52 let mut node = (output + self.leaf_count) >> 1;
53 while node >= self.query_root {
54 if let Some(curve) = self.node_curves[node] {
55 best = best.min(self.value(curve, output));
56 }
57 node >>= 1;
58 }
59 self.result[output] = best;
60 }
61
62 #[inline]
63 fn insert_from_left(&mut self, left: usize) {
64 let mut right = left + self.concave.len();
65 let block = 1_usize << (left ^ right).ilog2();
66 right &= !(block - 1);
67 let mut depth = bit_width(right - left - 1);
68 let mut node = (self.leaf_count + left) >> depth;
69 let mut pending = (!self.arbitrary[left].is_maximum()).then_some(left);
70 while depth != 0 {
71 let Some(curve) = pending else {
72 break;
73 };
74 depth -= 1;
75 let middle = ((node << 1 | 1) << depth) - self.leaf_count - 1;
76 if middle < left {
77 node = node << 1 | 1;
78 } else if self.node_curves[node]
79 .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
80 {
81 node <<= 1;
82 } else {
83 std::mem::swap(&mut self.node_curves[node], &mut pending);
84 node = node << 1 | 1;
85 }
86 }
87 if let Some(curve) = pending {
88 let output = node - self.leaf_count;
89 self.result[output] = self.result[output].min(self.value(curve, output));
90 }
91 }
92
93 #[inline]
94 fn insert_from_right(&mut self, right: usize) {
95 let curve = right - self.concave.len();
96 let block = 1_usize << (curve ^ right).ilog2();
97 let left = right & !(block - 1);
98 if left == right {
99 return;
100 }
101 let mut depth = bit_width(right - left - 1);
102 let mut node = (self.leaf_count + left) >> depth;
103 let mut pending = (!self.arbitrary[curve].is_maximum()).then_some(curve);
104 while depth != 0 {
105 let Some(curve) = pending else {
106 break;
107 };
108 depth -= 1;
109 let middle = ((node << 1 | 1) << depth) - self.leaf_count;
110 if middle >= right {
111 node <<= 1;
112 } else if self.node_curves[node]
113 .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
114 {
115 node = node << 1 | 1;
116 } else {
117 std::mem::swap(&mut self.node_curves[node], &mut pending);
118 node <<= 1;
119 }
120 }
121 if let Some(curve) = pending {
122 let output = node - self.leaf_count;
123 self.result[output] = self.result[output].min(self.value(curve, output));
124 }
125 }