dive_value/
subset_cursor.rs1use super::SubsetIter;
4use crate::{ErrorKind, Result, Set, Value, ValueError};
5
6pub struct ConcreteSubsetStream {
28 source: Set,
29 inner: SubsetIter,
30 pending: bool,
31 done: bool,
32}
33
34#[derive(Default)]
35struct Position {
36 indices: Vec<usize>,
37 k: usize,
38 started: bool,
39 pending: bool,
40 done: bool,
41}
42
43#[derive(Default)]
46pub struct SubsetScratch {
47 from: Position,
48 target: Position,
49 base_len: usize,
50 ready: bool,
51}
52
53pub struct SubsetCommit<'a> {
57 stream: &'a mut ConcreteSubsetStream,
58 scratch: &'a mut SubsetScratch,
59}
60
61impl ConcreteSubsetStream {
62 pub(super) fn new(inner: SubsetIter, source: Set) -> Self {
63 Self {
64 source,
65 inner,
66 pending: false,
67 done: false,
68 }
69 }
70
71 #[must_use]
74 pub fn belongs_to(&self, source: &Set) -> bool {
75 self.source.ptr_eq(source)
76 }
77
78 #[must_use]
80 pub fn base_elements(&self) -> &[Value] {
81 &self.inner.base
82 }
83
84 #[must_use]
87 pub fn current_indices(&self) -> Option<&[usize]> {
88 (self.inner.started && !self.pending && !self.done).then_some(self.inner.idx.as_slice())
89 }
90
91 pub fn prepare_masked_next(
101 &self,
102 allowed: &[usize],
103 scratch: &mut SubsetScratch,
104 mut poll: impl FnMut() -> Result<()>,
105 ) -> Result<bool> {
106 scratch.ready = false;
107 let Some(current) = self.current_indices() else {
108 return Ok(false);
109 };
110 poll()?;
111 let mut previous = None;
112 for &index in allowed {
113 poll()?;
114 if index >= self.inner.base.len() || previous.is_some_and(|p| p >= index) {
115 return Err(ValueError::new(
116 ErrorKind::Argument,
117 "subset indices must be increasing and in range",
118 ));
119 }
120 previous = Some(index);
121 }
122 copy_indices(&mut scratch.from.indices, current, &mut poll)?;
123 scratch.from.k = self.inner.k;
124 scratch.from.started = self.inner.started;
125 scratch.from.pending = self.pending;
126 scratch.from.done = self.done;
127 scratch.base_len = self.inner.base.len();
128 scratch.target.indices.clear();
129 scratch
130 .target
131 .indices
132 .try_reserve(allowed.len())
133 .map_err(|error| reservation(&error))?;
134 let k = current.len();
135 let ranks = &mut scratch.target.indices;
136 let mut greater = false;
137 if k <= allowed.len() {
138 for (position, &index) in current.iter().enumerate() {
139 poll()?;
140 let lower = allowed.partition_point(|candidate| *candidate < index);
141 let rank = ranks.last().map_or(lower, |last| lower.max(last + 1));
142 if rank >= allowed.len() || allowed.len() - rank < k - position {
143 break;
144 }
145 ranks.push(rank);
146 if allowed[rank] > index {
147 greater = true;
148 fill_ranks(ranks, k, &mut poll)?;
149 break;
150 }
151 }
152 }
153 if !greater {
154 while let Some(last) = ranks.last().copied() {
157 poll()?;
158 let position = ranks.len() - 1;
159 if last < allowed.len() - k + position {
160 ranks[position] += 1;
161 fill_ranks(ranks, k, &mut poll)?;
162 greater = true;
163 break;
164 }
165 ranks.pop();
166 }
167 }
168 if !greater {
169 ranks.clear();
170 if k < allowed.len() {
171 for rank in 0..=k {
172 poll()?;
173 ranks.push(rank);
174 }
175 } else {
176 scratch.target.done = true;
177 scratch.target.pending = false;
178 scratch.target.started = true;
179 scratch.target.k = k;
180 scratch.ready = true;
181 return Ok(true);
182 }
183 }
184 for rank in ranks.iter_mut() {
185 poll()?;
186 *rank = allowed[*rank];
187 }
188 scratch.target.k = ranks.len();
189 scratch.target.started = true;
190 scratch.target.pending = true;
191 scratch.target.done = false;
192 scratch.ready = true;
193 Ok(true)
194 }
195}
196
197fn reservation(error: &std::collections::TryReserveError) -> ValueError {
198 ValueError::new(
199 ErrorKind::DiveLimit,
200 format!("subset index scratch: {error}"),
201 )
202}
203fn copy_indices(
204 to: &mut Vec<usize>,
205 from: &[usize],
206 poll: &mut impl FnMut() -> Result<()>,
207) -> Result<()> {
208 to.clear();
209 to.try_reserve(from.len())
210 .map_err(|error| reservation(&error))?;
211 for &index in from {
212 poll()?;
213 to.push(index);
214 }
215 Ok(())
216}
217fn fill_ranks(
218 ranks: &mut Vec<usize>,
219 length: usize,
220 poll: &mut impl FnMut() -> Result<()>,
221) -> Result<()> {
222 while ranks.len() < length {
223 poll()?;
224 let next = ranks.last().map_or(0, |last| last + 1);
225 ranks.push(next);
226 }
227 Ok(())
228}
229
230impl SubsetScratch {
231 #[must_use]
236 pub fn prepare_commit<'a>(
237 &'a mut self,
238 stream: &'a mut ConcreteSubsetStream,
239 ) -> Option<SubsetCommit<'a>> {
240 if !self.ready
241 || self.base_len != stream.inner.base.len()
242 || self.from.k != stream.inner.k
243 || self.from.started != stream.inner.started
244 || self.from.pending != stream.pending
245 || self.from.done != stream.done
246 || self.from.indices != stream.inner.idx
247 {
248 return None;
249 }
250 Some(SubsetCommit {
251 stream,
252 scratch: self,
253 })
254 }
255}
256
257impl SubsetCommit<'_> {
258 pub fn commit(self) {
261 std::mem::swap(&mut self.stream.inner.idx, &mut self.scratch.target.indices);
262 self.stream.inner.k = self.scratch.target.k;
263 self.stream.inner.started = self.scratch.target.started;
264 self.stream.pending = self.scratch.target.pending;
265 self.stream.done = self.scratch.target.done;
266 self.scratch.ready = false;
267 }
268}
269
270impl Iterator for ConcreteSubsetStream {
271 type Item = Value;
272 fn next(&mut self) -> Option<Value> {
273 if self.done {
274 return None;
275 }
276 if self.pending {
277 self.pending = false;
278 return Some(self.inner.current_value());
279 }
280 let value = self.inner.next();
281 if value.is_none() {
282 self.done = true;
283 }
284 value
285 }
286}
287
288#[cfg(test)]
289#[path = "subset_cursor_tests.rs"]
290mod tests;