uqa_core/memory/
deque.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! A rolling deque whose retained capacity remains charged after prefix removal.
8
9use std::collections::VecDeque;
10
11use super::{reconcile_buffer_capacity, replacement, MemoryBudget, MemoryError, MemoryReservation};
12
13#[derive(Debug)]
14pub struct BudgetedDeque<T> {
15    values: VecDeque<T>,
16    memory: MemoryReservation,
17}
18
19impl<T> BudgetedDeque<T> {
20    pub fn new(budget: &MemoryBudget) -> Self {
21        Self {
22            values: VecDeque::new(),
23            memory: budget.empty_reservation(),
24        }
25    }
26
27    pub fn len(&self) -> usize {
28        self.values.len()
29    }
30
31    pub fn is_empty(&self) -> bool {
32        self.values.is_empty()
33    }
34
35    pub fn capacity(&self) -> usize {
36        self.values.capacity()
37    }
38
39    pub fn reserve(&mut self, additional: usize) -> Result<(), MemoryError> {
40        let required = self
41            .len()
42            .checked_add(additional)
43            .ok_or(MemoryError::SizeOverflow)?;
44        if required <= self.values.capacity() {
45            return Ok(());
46        }
47        let (capacity, mut memory) =
48            replacement::<T>(self.memory.budget(), self.capacity(), required)?;
49        let mut values = VecDeque::new();
50        values.try_reserve_exact(capacity)?;
51        reconcile_buffer_capacity::<T>(&mut memory, values.capacity())?;
52        while let Some(value) = self.values.pop_front() {
53            values.push_back(value);
54        }
55        self.values = values;
56        self.memory = memory;
57        Ok(())
58    }
59
60    pub fn push_back(&mut self, value: T) -> Result<(), MemoryError> {
61        self.reserve(1)?;
62        self.values.push_back(value);
63        Ok(())
64    }
65
66    pub fn push_front(&mut self, value: T) -> Result<(), MemoryError> {
67        self.reserve(1)?;
68        self.values.push_front(value);
69        Ok(())
70    }
71
72    pub fn pop_front(&mut self) -> Option<T> {
73        self.values.pop_front()
74    }
75
76    pub fn pop_back(&mut self) -> Option<T> {
77        self.values.pop_back()
78    }
79
80    pub fn iter(&self) -> std::collections::vec_deque::Iter<'_, T> {
81        self.values.iter()
82    }
83}
84
85impl<T> std::ops::Index<usize> for BudgetedDeque<T> {
86    type Output = T;
87
88    fn index(&self, index: usize) -> &T {
89        &self.values[index]
90    }
91}
92
93impl<'a, T> IntoIterator for &'a BudgetedDeque<T> {
94    type Item = &'a T;
95    type IntoIter = std::collections::vec_deque::Iter<'a, T>;
96
97    fn into_iter(self) -> Self::IntoIter {
98        self.iter()
99    }
100}
101
102impl<T> std::ops::IndexMut<usize> for BudgetedDeque<T> {
103    fn index_mut(&mut self, index: usize) -> &mut T {
104        &mut self.values[index]
105    }
106}
uqa_core/memory/deque.rs

uqa_core/memory/
deque.rs
