Skip to main content

ftui_layout/
wide_prefix.rs

1//! Checked wide-domain prefix sums for virtualized content.
2//!
3//! [`WidePrefixSums`] is the dependency-light arithmetic seam for hosts whose
4//! logical content is larger than a terminal coordinate or a `u32` total.
5//! It deliberately owns no terminal, runtime, renderer, or persistence
6//! policy. Callers can use it for reader heights, virtualized blocks, or other
7//! non-terminal sequences of non-negative `u64` values.
8//!
9//! The structure is a Fenwick tree. Updates and queries are logarithmic, while
10//! all arithmetic is checked and failed updates leave the existing tree
11//! unchanged. `partition_point` returns the number of complete entries whose
12//! prefix sum fits within an offset, which avoids the ambiguous inclusive
13//! indexing of the original terminal-oriented helper.
14
15/// A checked Fenwick tree over non-negative `u64` values.
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct WidePrefixSums {
18    /// One-indexed Fenwick storage; slot zero is intentionally unused.
19    tree: Vec<u64>,
20}
21
22impl WidePrefixSums {
23    /// Create an all-zero tree with `len` entries.
24    ///
25    /// The allocation is fallible and the `len + 1` slot calculation is
26    /// checked before attempting it.
27    pub fn try_new(len: usize) -> Result<Self, WidePrefixError> {
28        let slots = len
29            .checked_add(1)
30            .ok_or(WidePrefixError::CapacityOverflow { len })?;
31        let mut tree = Vec::new();
32        tree.try_reserve_exact(slots)
33            .map_err(|_| WidePrefixError::AllocationFailed { len })?;
34        tree.resize(slots, 0);
35        Ok(Self { tree })
36    }
37
38    /// Build a tree from values in linear time.
39    ///
40    /// Fails with `SumOverflow` at the first entry whose inclusive prefix
41    /// exceeds `u64::MAX`.
42    pub fn try_from_values(values: &[u64]) -> Result<Self, WidePrefixError> {
43        // Every prefix and every tree node is a sum of entries, so a total
44        // that fits bounds them all. Checking only the nodes admitted
45        // `[u64::MAX, 0, 1]`: no node overflows, but its total does, and
46        // then `total`, `value(2)`, `set` and `remove` all failed on it.
47        let mut total = 0_u64;
48        for (index, &value) in values.iter().enumerate() {
49            total = total
50                .checked_add(value)
51                .ok_or(WidePrefixError::SumOverflow { index })?;
52        }
53        let mut result = Self::try_new(values.len())?;
54        for (index, &value) in values.iter().enumerate() {
55            result.tree[index + 1] = value;
56        }
57        for index in 1..=values.len() {
58            let Some(parent) = index.checked_add(lowbit(index)) else {
59                continue;
60            };
61            if parent <= values.len() {
62                result.tree[parent] += result.tree[index];
63            }
64        }
65        Ok(result)
66    }
67
68    /// Number of entries in the sequence.
69    #[must_use]
70    pub fn len(&self) -> usize {
71        self.tree.len() - 1
72    }
73
74    /// Whether the sequence has no entries.
75    #[must_use]
76    pub fn is_empty(&self) -> bool {
77        self.len() == 0
78    }
79
80    /// Return the value at `index`.
81    pub fn value(&self, index: usize) -> Result<u64, WidePrefixError> {
82        self.check_index(index)?;
83        let end = self.prefix_before(index + 1)?;
84        let start = self.prefix_before(index)?;
85        end.checked_sub(start)
86            .ok_or(WidePrefixError::InvariantViolation { index })
87    }
88
89    /// Return the sum of entries in `[0, end)`.
90    ///
91    /// `end == len()` is valid and returns the total.
92    pub fn prefix_before(&self, end: usize) -> Result<u64, WidePrefixError> {
93        if end > self.len() {
94            return Err(WidePrefixError::EndOutOfBounds {
95                end,
96                len: self.len(),
97            });
98        }
99        let mut index = end;
100        let mut sum = 0_u64;
101        while index != 0 {
102            sum = sum
103                .checked_add(self.tree[index])
104                .ok_or(WidePrefixError::SumOverflow { index: index - 1 })?;
105            index -= lowbit(index);
106        }
107        Ok(sum)
108    }
109
110    /// Return the inclusive prefix ending at `index`.
111    pub fn prefix_inclusive(&self, index: usize) -> Result<u64, WidePrefixError> {
112        self.check_index(index)?;
113        self.prefix_before(index + 1)
114    }
115
116    /// Return the sum of entries in `[start, end)`.
117    pub fn range(&self, start: usize, end: usize) -> Result<u64, WidePrefixError> {
118        if start > end || end > self.len() {
119            return Err(WidePrefixError::InvalidRange {
120                start,
121                end,
122                len: self.len(),
123            });
124        }
125        let before_start = self.prefix_before(start)?;
126        let before_end = self.prefix_before(end)?;
127        before_end
128            .checked_sub(before_start)
129            .ok_or(WidePrefixError::InvariantViolation { index: start })
130    }
131
132    /// Return the total sum of all entries.
133    pub fn total(&self) -> Result<u64, WidePrefixError> {
134        self.prefix_before(self.len())
135    }
136
137    /// Add a signed adjustment to one entry.
138    ///
139    /// The entry and the total are checked before any mutation, so taking
140    /// the entry below zero or the total above `u64::MAX` fails and leaves
141    /// the tree unchanged.
142    pub fn add(&mut self, index: usize, delta: i64) -> Result<(), WidePrefixError> {
143        self.check_index(index)?;
144        if delta >= 0 {
145            self.apply_unsigned_delta(index, delta as u64, true)
146        } else {
147            self.apply_unsigned_delta(index, delta.unsigned_abs(), false)
148        }
149    }
150
151    /// Set one entry to a new non-negative value.
152    pub fn set(&mut self, index: usize, value: u64) -> Result<(), WidePrefixError> {
153        let current = self.value(index)?;
154        if value >= current {
155            self.apply_unsigned_delta(index, value - current, true)
156        } else {
157            self.apply_unsigned_delta(index, current - value, false)
158        }
159    }
160
161    /// Rebuild the tree from a new sequence, preserving the old tree if the
162    /// new sequence cannot be represented or allocated.
163    pub fn rebuild(&mut self, values: &[u64]) -> Result<(), WidePrefixError> {
164        let replacement = Self::try_from_values(values)?;
165        *self = replacement;
166        Ok(())
167    }
168
169    /// Insert one entry and rebuild the bounded prefix directory.
170    ///
171    /// Structural edits are intentionally explicit and linear-time. The
172    /// replacement tree is fully validated before it becomes visible, so a
173    /// failed allocation or sum check leaves this tree unchanged.
174    pub fn insert(&mut self, index: usize, value: u64) -> Result<(), WidePrefixError> {
175        let new_len = self
176            .len()
177            .checked_add(1)
178            .ok_or(WidePrefixError::CapacityOverflow { len: self.len() })?;
179        if index > self.len() {
180            return Err(WidePrefixError::IndexOutOfBounds {
181                index,
182                len: self.len(),
183            });
184        }
185        let mut values = self.snapshot_values()?;
186        values
187            .try_reserve_exact(1)
188            .map_err(|_| WidePrefixError::AllocationFailed { len: new_len })?;
189        values.insert(index, value);
190        let replacement = Self::try_from_values(&values)?;
191        *self = replacement;
192        Ok(())
193    }
194
195    /// Remove one entry and rebuild the bounded prefix directory.
196    pub fn remove(&mut self, index: usize) -> Result<u64, WidePrefixError> {
197        self.check_index(index)?;
198        let mut values = self.snapshot_values()?;
199        let removed = values.remove(index);
200        let replacement = Self::try_from_values(&values)?;
201        *self = replacement;
202        Ok(removed)
203    }
204
205    /// Return the number of complete entries whose prefix sum is at most
206    /// `offset`.
207    ///
208    /// The result is in `0..=len()`. Zero-height entries are included, making
209    /// the result suitable for selecting a virtualized row at an exact
210    /// boundary without an inclusive/exclusive ambiguity.
211    #[must_use]
212    pub fn partition_point(&self, offset: u64) -> usize {
213        let mut position = 0_usize;
214        let mut consumed = 0_u64;
215        let mut bit = highest_power_of_two(self.len());
216        while bit != 0 {
217            let Some(next) = position.checked_add(bit) else {
218                bit >>= 1;
219                continue;
220            };
221            if next <= self.len()
222                && let Some(candidate) = consumed.checked_add(self.tree[next])
223                && candidate <= offset
224            {
225                position = next;
226                consumed = candidate;
227            }
228            bit >>= 1;
229        }
230        position
231    }
232
233    fn check_index(&self, index: usize) -> Result<(), WidePrefixError> {
234        if index >= self.len() {
235            return Err(WidePrefixError::IndexOutOfBounds {
236                index,
237                len: self.len(),
238            });
239        }
240        Ok(())
241    }
242
243    fn snapshot_values(&self) -> Result<Vec<u64>, WidePrefixError> {
244        let mut values = Vec::new();
245        values
246            .try_reserve_exact(self.len())
247            .map_err(|_| WidePrefixError::AllocationFailed { len: self.len() })?;
248        for index in 0..self.len() {
249            values.push(self.value(index)?);
250        }
251        Ok(values)
252    }
253
254    fn apply_unsigned_delta(
255        &mut self,
256        index: usize,
257        delta: u64,
258        increasing: bool,
259    ) -> Result<(), WidePrefixError> {
260        // Each node on the update path is a sum of entries that includes this
261        // one, so it lies between the entry and the total. Keeping those two
262        // in range keeps every node in range. Checking the nodes alone missed
263        // both: on `[5, 5]`, `add(1, -7)` found node 2 (holding 10) able to
264        // absorb it and left entry 1 at -2, and on `[u64::MAX, 0, 0]`,
265        // `add(2, 1)` found no node overflowing and pushed the total past
266        // `u64::MAX`.
267        if increasing {
268            self.total()?
269                .checked_add(delta)
270                .ok_or(WidePrefixError::SumOverflow { index })?;
271        } else if self.value(index)? < delta {
272            return Err(WidePrefixError::SumUnderflow { index });
273        }
274
275        let mut cursor = index + 1;
276        while cursor <= self.len() {
277            self.tree[cursor] = if increasing {
278                self.tree[cursor] + delta
279            } else {
280                self.tree[cursor] - delta
281            };
282            // A missing next index is past any representable length, so
283            // this was the last node on the path.
284            let Some(next) = cursor.checked_add(lowbit(cursor)) else {
285                break;
286            };
287            cursor = next;
288        }
289        Ok(())
290    }
291}
292
293/// Failure returned by checked wide-prefix operations.
294#[derive(Debug, Clone, Copy, PartialEq, Eq)]
295pub enum WidePrefixError {
296    /// `len + 1` cannot be represented as a `usize`.
297    CapacityOverflow { len: usize },
298    /// The allocator rejected the requested capacity.
299    AllocationFailed { len: usize },
300    /// An entry index is outside the sequence.
301    IndexOutOfBounds { index: usize, len: usize },
302    /// A half-open range or endpoint is invalid.
303    InvalidRange {
304        start: usize,
305        end: usize,
306        len: usize,
307    },
308    /// A prefix endpoint is larger than the sequence length.
309    EndOutOfBounds { end: usize, len: usize },
310    /// A checked prefix or update would exceed `u64::MAX`.
311    SumOverflow { index: usize },
312    /// A checked decrement would make a prefix negative.
313    SumUnderflow { index: usize },
314    /// Internal prefix ordering was inconsistent.
315    InvariantViolation { index: usize },
316}
317
318impl std::fmt::Display for WidePrefixError {
319    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
320        match self {
321            Self::CapacityOverflow { len } => {
322                write!(formatter, "wide-prefix length overflow: {len}")
323            }
324            Self::AllocationFailed { len } => {
325                write!(formatter, "wide-prefix allocation failed: {len}")
326            }
327            Self::IndexOutOfBounds { index, len } => {
328                write!(
329                    formatter,
330                    "wide-prefix index {index} out of bounds (len={len})"
331                )
332            }
333            Self::InvalidRange { start, end, len } => {
334                write!(
335                    formatter,
336                    "wide-prefix range [{start}, {end}) invalid (len={len})"
337                )
338            }
339            Self::EndOutOfBounds { end, len } => {
340                write!(formatter, "wide-prefix end {end} out of bounds (len={len})")
341            }
342            Self::SumOverflow { index } => write!(formatter, "wide-prefix sum overflow at {index}"),
343            Self::SumUnderflow { index } => {
344                write!(formatter, "wide-prefix sum underflow at {index}")
345            }
346            Self::InvariantViolation { index } => {
347                write!(formatter, "wide-prefix invariant violation at {index}")
348            }
349        }
350    }
351}
352
353impl std::error::Error for WidePrefixError {}
354
355#[inline]
356fn lowbit(value: usize) -> usize {
357    value.isolate_lowest_one()
358}
359
360#[inline]
361fn highest_power_of_two(value: usize) -> usize {
362    if value == 0 {
363        0
364    } else {
365        1 << (usize::BITS - 1 - value.leading_zeros())
366    }
367}
368
369#[cfg(test)]
370mod tests {
371    use super::{WidePrefixError, WidePrefixSums};
372
373    #[test]
374    fn supports_totals_above_u32() {
375        let sums = WidePrefixSums::try_from_values(&[u32::MAX as u64, 7]).unwrap();
376        assert_eq!(sums.prefix_before(1).unwrap(), u32::MAX as u64);
377        assert_eq!(sums.total().unwrap(), u64::from(u32::MAX) + 7);
378        assert_eq!(sums.range(1, 2).unwrap(), 7);
379    }
380
381    #[test]
382    fn partition_point_is_half_open_and_includes_zero_height_entries() {
383        let sums = WidePrefixSums::try_from_values(&[0, 3, 0, 4]).unwrap();
384        assert_eq!(sums.partition_point(0), 1);
385        assert_eq!(sums.partition_point(3), 3);
386        assert_eq!(sums.partition_point(6), 3);
387        assert_eq!(sums.partition_point(7), 4);
388    }
389
390    #[test]
391    fn failed_update_is_atomic() {
392        let mut sums = WidePrefixSums::try_from_values(&[u64::MAX]).unwrap();
393        assert_eq!(
394            sums.add(0, 1),
395            Err(WidePrefixError::SumOverflow { index: 0 })
396        );
397        assert_eq!(sums.value(0).unwrap(), u64::MAX);
398    }
399
400    #[test]
401    fn construction_rejects_total_overflow() {
402        assert_eq!(
403            WidePrefixSums::try_from_values(&[u64::MAX, 1]),
404            Err(WidePrefixError::SumOverflow { index: 1 })
405        );
406    }
407
408    #[test]
409    fn negative_adjustment_checks_the_entry_not_just_its_nodes() {
410        // Node 2 holds 5 + 5 and could absorb -7; entry 1 cannot.
411        let mut sums = WidePrefixSums::try_from_values(&[5, 5]).unwrap();
412        assert_eq!(
413            sums.add(1, -7),
414            Err(WidePrefixError::SumUnderflow { index: 1 })
415        );
416        assert_eq!(sums.value(1).unwrap(), 5);
417        assert_eq!(sums.total().unwrap(), 10);
418    }
419
420    #[test]
421    fn total_overflow_is_rejected_when_no_node_overflows() {
422        // No node of `[MAX, 0, 1]` exceeds `u64::MAX`; the prefix through
423        // entry 2 does.
424        assert_eq!(
425            WidePrefixSums::try_from_values(&[u64::MAX, 0, 1]),
426            Err(WidePrefixError::SumOverflow { index: 2 })
427        );
428        let mut sums = WidePrefixSums::try_from_values(&[u64::MAX, 0, 0]).unwrap();
429        assert_eq!(
430            sums.add(2, 1),
431            Err(WidePrefixError::SumOverflow { index: 2 })
432        );
433        assert_eq!(sums.value(2).unwrap(), 0);
434        assert_eq!(sums.total().unwrap(), u64::MAX);
435    }
436
437    #[test]
438    fn updates_match_a_plain_vector_model() {
439        // Near-maximal values make both the entry and the total bounds bite.
440        let mut state = 0x2545_f491_4f6c_dd1d_u64;
441        let mut next = move || {
442            state ^= state << 13;
443            state ^= state >> 7;
444            state ^= state << 17;
445            state
446        };
447        // A new value for `model[index]` is admissible when the total with it
448        // still fits in a `u64`.
449        let fits = |model: &[u64], index: usize, value: u64| {
450            model
451                .iter()
452                .enumerate()
453                .filter(|&(i, _)| i != index)
454                .try_fold(value, |sum, (_, &v)| sum.checked_add(v))
455                .is_some()
456        };
457        let mut model = vec![0_u64; 9];
458        let mut sums = WidePrefixSums::try_from_values(&model).unwrap();
459        for _ in 0..20_000 {
460            let index = (next() % 9) as usize;
461            let magnitude = next() >> (next() % 64);
462            let target = if next() % 2 == 0 {
463                let delta = (magnitude >> 1) as i64 * if next() % 2 == 0 { 1 } else { -1 };
464                let entry = if delta >= 0 {
465                    model[index].checked_add(delta.unsigned_abs())
466                } else {
467                    model[index].checked_sub(delta.unsigned_abs())
468                }
469                .filter(|&entry| fits(&model, index, entry));
470                assert_eq!(sums.add(index, delta).is_ok(), entry.is_some());
471                entry
472            } else {
473                let entry = Some(magnitude).filter(|&entry| fits(&model, index, entry));
474                assert_eq!(sums.set(index, magnitude).is_ok(), entry.is_some());
475                entry
476            };
477            if let Some(entry) = target {
478                model[index] = entry;
479            }
480            for (i, &value) in model.iter().enumerate() {
481                assert_eq!(sums.value(i), Ok(value));
482            }
483        }
484    }
485
486    #[test]
487    fn negative_adjustment_rejects_underflow() {
488        let mut sums = WidePrefixSums::try_from_values(&[2, 4]).unwrap();
489        assert_eq!(
490            sums.add(0, -3),
491            Err(WidePrefixError::SumUnderflow { index: 0 })
492        );
493        assert_eq!(sums.total().unwrap(), 6);
494    }
495
496    #[test]
497    fn constructor_and_queries_validate_boundaries() {
498        assert_eq!(
499            WidePrefixSums::try_new(usize::MAX),
500            Err(WidePrefixError::CapacityOverflow { len: usize::MAX })
501        );
502        let sums = WidePrefixSums::try_new(2).unwrap();
503        assert_eq!(
504            sums.value(2),
505            Err(WidePrefixError::IndexOutOfBounds { index: 2, len: 2 })
506        );
507        assert_eq!(
508            sums.range(2, 1),
509            Err(WidePrefixError::InvalidRange {
510                start: 2,
511                end: 1,
512                len: 2
513            })
514        );
515    }
516
517    #[test]
518    fn set_and_rebuild_preserve_checked_semantics() {
519        let mut sums = WidePrefixSums::try_from_values(&[1, 2, 3]).unwrap();
520        sums.set(1, u64::from(u32::MAX) + 1).unwrap();
521        assert_eq!(sums.value(1).unwrap(), u64::from(u32::MAX) + 1);
522        sums.rebuild(&[5, 8]).unwrap();
523        assert_eq!(sums.total().unwrap(), 13);
524        assert_eq!(sums.len(), 2);
525    }
526
527    #[test]
528    fn structural_edits_are_bounded_and_checked() {
529        let mut sums = WidePrefixSums::try_from_values(&[2, 4]).unwrap();
530        sums.insert(1, 3).unwrap();
531        assert_eq!(sums.total().unwrap(), 9);
532        assert_eq!(sums.value(1).unwrap(), 3);
533        assert_eq!(sums.remove(0).unwrap(), 2);
534        assert_eq!(sums.range(0, 2).unwrap(), 7);
535        assert_eq!(
536            sums.insert(usize::MAX, 1),
537            Err(WidePrefixError::IndexOutOfBounds {
538                index: usize::MAX,
539                len: 2
540            })
541        );
542    }
543
544    #[test]
545    fn structural_overflow_preserves_existing_tree() {
546        let mut sums = WidePrefixSums::try_from_values(&[u64::MAX]).unwrap();
547        assert_eq!(
548            sums.insert(1, 1),
549            Err(WidePrefixError::SumOverflow { index: 1 })
550        );
551        assert_eq!(sums.len(), 1);
552        assert_eq!(sums.value(0).unwrap(), u64::MAX);
553    }
554}