spru_util/pile/
mod.rs

1pub mod error;
2
3use std::{marker::PhantomData, mem, ops};
4
5use derive_where::derive_where;
6use spru::common::error::AnyResult;
7use tagset::tagset;
8use telety::telety;
9
10use crate::{Strictness, cloned};
11
12#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
13pub struct Pile<T> {
14    /// front/top -> back/bottom
15    items: FakeDeVec<T>,
16}
17
18impl<T> Pile<T> {
19    /// Iterate items from top to bottom
20    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> {
21        self.into_iter()
22    }
23
24    pub fn top(&self) -> Option<&T> {
25        self.items.first()
26    }
27
28    pub fn bottom(&self) -> Option<&T> {
29        self.items.last()
30    }
31}
32
33impl<T> ops::Deref for Pile<T> {
34    type Target = [T];
35
36    fn deref(&self) -> &Self::Target {
37        &self.items
38    }
39}
40
41impl<'i, T> IntoIterator for &'i Pile<T> {
42    type Item = &'i T;
43    type IntoIter = std::slice::Iter<'i, T>;
44
45    fn into_iter(self) -> Self::IntoIter {
46        self.items.iter()
47    }
48}
49
50#[telety(crate::pile)]
51#[tagset(Create<T>)]
52#[tagset(Destroy<T>)]
53#[tagset(Update<T>)]
54#[tagset(PushTop<T>)]
55#[tagset(PushBottom<T>)]
56#[tagset(PopTop<T>)]
57#[tagset(PopBottom<T>)]
58#[tagset(PushTopMany<T>)]
59#[tagset(PushBottomMany<T>)]
60#[tagset(PopTopMany<T>)]
61#[tagset(PopBottomMany<T>)]
62#[tagset(Insert<T>)]
63#[tagset(Remove<T>)]
64#[tagset(Shuffle<T>)]
65#[tagset(Clear<T>)]
66#[tagset(reserved(..32))]
67pub struct Actions<T>;
68
69pub fn create<T>(items: impl IntoIterator<Item = T>) -> Create<T> {
70    cloned::create(Pile {
71        items: items.into_iter().collect(),
72    })
73}
74
75pub fn default<T>() -> Create<T> {
76    create([])
77}
78
79pub fn destroy<T>() -> Destroy<T> {
80    cloned::destroy()
81}
82
83pub fn update<T>(items: impl IntoIterator<Item = T>) -> Update<T> {
84    cloned::update(Pile {
85        items: items.into_iter().collect(),
86    })
87}
88
89pub fn shuffle<T, R: rand::Rng>(rng: &mut R) -> Shuffle<T> {
90    let seed = rng.random();
91    Shuffle {
92        seed,
93        undo: false,
94        _p: PhantomData,
95    }
96}
97
98pub fn push_top<T>(item: T) -> PushTop<T> {
99    PushTop { item }
100}
101
102pub fn try_pop_top<T>() -> PopTop<T> {
103    PopTop {
104        strictness: Strictness::BestEffort,
105        _p: PhantomData,
106    }
107}
108
109pub fn pop_top<T>() -> PopTop<T> {
110    PopTop {
111        strictness: Strictness::AllOrError,
112        _p: PhantomData,
113    }
114}
115
116pub fn push_bottom<T>(item: T) -> PushBottom<T> {
117    PushBottom { item }
118}
119
120pub fn try_pop_bottom<T>() -> PopBottom<T> {
121    PopBottom {
122        strictness: Strictness::BestEffort,
123        _p: PhantomData,
124    }
125}
126
127pub fn pop_bottom<T>() -> PopBottom<T> {
128    PopBottom {
129        strictness: Strictness::AllOrError,
130        _p: PhantomData,
131    }
132}
133
134pub fn pop_top_many<T>(count: usize) -> PopTopMany<T> {
135    PopTopMany {
136        strictness: Strictness::AllOrError,
137        count,
138        _p: PhantomData,
139    }
140}
141
142pub fn try_pop_top_many<T>(count: usize) -> PopTopMany<T> {
143    PopTopMany {
144        strictness: Strictness::AllOrError,
145        count,
146        _p: PhantomData,
147    }
148}
149
150pub fn pop_bottom_many<T>(count: usize) -> PopTopMany<T> {
151    PopTopMany {
152        strictness: Strictness::AllOrError,
153        count,
154        _p: PhantomData,
155    }
156}
157
158pub fn try_pop_bottom_many<T>(count: usize) -> PopBottomMany<T> {
159    PopBottomMany {
160        strictness: Strictness::AllOrError,
161        count,
162        _p: PhantomData,
163    }
164}
165
166pub fn push_bottom_many<T>(elements: Vec<T>) -> PushBottomMany<T> {
167    PushBottomMany { elements }
168}
169
170pub fn push_top_many<T>(elements: Vec<T>) -> PushTopMany<T> {
171    PushTopMany { elements }
172}
173
174pub fn remove<T>(index: usize) -> Remove<T> {
175    Remove {
176        index,
177        _p: PhantomData,
178    }
179}
180
181pub fn clear<T>() -> Clear<T> {
182    Clear { _p: PhantomData }
183}
184
185// An inefficient temporary stand-in for a single-slice deque
186#[derive(Debug, Clone, PartialEq, Eq)]
187#[derive_where(Default; )]
188#[derive(serde::Serialize, serde::Deserialize)]
189#[serde(transparent)]
190struct FakeDeVec<T>(Vec<T>);
191
192impl<T> FakeDeVec<T> {
193    fn pop_front(&mut self) -> Option<T> {
194        if self.is_empty() {
195            None
196        } else {
197            Some(self.0.remove(0))
198        }
199    }
200
201    fn pop_back(&mut self) -> Option<T> {
202        self.pop()
203    }
204
205    fn push_front(&mut self, element: T) {
206        self.insert(0, element);
207    }
208
209    fn push_back(&mut self, element: T) {
210        self.push(element);
211    }
212}
213
214impl<T> std::iter::FromIterator<T> for FakeDeVec<T> {
215    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
216        Self(Vec::from_iter(iter))
217    }
218}
219
220impl<T> ops::Deref for FakeDeVec<T> {
221    type Target = Vec<T>;
222
223    fn deref(&self) -> &Self::Target {
224        &self.0
225    }
226}
227
228impl<T> ops::DerefMut for FakeDeVec<T> {
229    fn deref_mut(&mut self) -> &mut Self::Target {
230        &mut self.0
231    }
232}
233
234#[derive(Debug, Clone, crate::FromInfallible, thiserror::Error)]
235#[error("Pile error: {0}")]
236pub enum Error {
237    Pop(#[from] error::Pop),
238    Insert(#[from] error::Insert),
239    Remove(#[from] error::Remove),
240}
241
242pub type Create<T> = cloned::Create<Pile<T>>;
243
244pub type Destroy<T> = cloned::Destroy<Pile<T>>;
245
246pub type Update<T> = cloned::Update<Pile<T>>;
247
248#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, spru::action::Update)]
249pub struct PushTop<T> {
250    item: T,
251}
252
253impl<T> spru::action::Update for PushTop<T>
254where
255    T: Clone,
256{
257    type T = Pile<T>;
258    type Undo = PopTop<T>;
259
260    #[allow(refining_impl_trait)]
261    fn update(&self, value: &mut Self::T) -> AnyResult<Self::Undo> {
262        value.items.push_front(self.item.clone());
263        Ok(pop_top())
264    }
265}
266
267#[derive(Debug, Clone, Default, serde::Serialize, serde::Deserialize, spru::action::Update)]
268pub struct PopTop<T> {
269    strictness: Strictness,
270    _p: PhantomData<fn() -> T>,
271}
272
273impl<T> spru::action::Update for PopTop<T>
274where
275    T: Clone,
276{
277    type T = Pile<T>;
278    type Undo = PushTop<T>;
279
280    #[allow(refining_impl_trait)]
281    fn update(&self, value: &mut Self::T) -> AnyResult<Option<Self::Undo>> {
282        Ok(match value.items.pop_front() {
283            Some(item) => Some(push_top(item)),
284            None => match self.strictness {
285                Strictness::BestEffort => None,
286                Strictness::AllOrError => Err(error::Pop::Empty)?,
287            },
288        })
289    }
290}
291
292#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, spru::action::Update)]
293pub struct PushBottom<T> {
294    item: T,
295}
296
297impl<T> spru::action::Update for PushBottom<T>
298where
299    T: Clone,
300{
301    type T = Pile<T>;
302    type Undo = PopBottom<T>;
303
304    #[allow(refining_impl_trait)]
305    fn update(&self, value: &mut Self::T) -> AnyResult<Self::Undo> {
306        value.items.push_back(self.item.clone());
307        Ok(pop_bottom())
308    }
309}
310
311#[derive_where(Debug, Clone, Default, Serialize, Deserialize)]
312#[derive(spru::action::Update)]
313pub struct PopBottom<T> {
314    strictness: Strictness,
315    _p: PhantomData<T>,
316}
317
318impl<T> spru::action::Update for PopBottom<T>
319where
320    T: Clone,
321{
322    type T = Pile<T>;
323    type Undo = PushBottom<T>;
324
325    #[allow(refining_impl_trait)]
326    fn update(&self, value: &mut Self::T) -> AnyResult<Option<Self::Undo>> {
327        Ok(match value.items.pop_back() {
328            Some(item) => Some(push_bottom(item)),
329            None => match self.strictness {
330                Strictness::BestEffort => None,
331                Strictness::AllOrError => Err(error::Pop::Empty)?,
332            },
333        })
334    }
335}
336
337#[derive_where(Debug, Clone, Default, Serialize, Deserialize)]
338#[derive(spru::action::Update)]
339pub struct PopTopMany<T> {
340    strictness: Strictness,
341    count: usize,
342    _p: PhantomData<T>,
343}
344
345impl<T> spru::action::Update for PopTopMany<T>
346where
347    T: Clone,
348{
349    type T = Pile<T>;
350    type Undo = PushTopMany<T>;
351
352    fn update(&self, value: &mut Self::T) -> AnyResult<impl Into<Option<Self::Undo>>> {
353        let Self {
354            strictness,
355            count,
356            _p,
357        } = *self;
358
359        let mut elements = vec![];
360
361        if strictness == Strictness::AllOrError && value.items.len() <= count {
362            Err(error::Pop::Empty.into())
363        } else {
364            for _ in 0..count {
365                if let Some(element) = value.items.pop_front() {
366                    elements.push(element);
367                }
368            }
369
370            Ok(PushTopMany { elements })
371        }
372    }
373}
374
375#[derive_where(Debug, Clone, Default, Serialize, Deserialize)]
376#[derive(spru::action::Update)]
377pub struct PopBottomMany<T> {
378    strictness: Strictness,
379    count: usize,
380    _p: PhantomData<T>,
381}
382
383impl<T> spru::action::Update for PopBottomMany<T>
384where
385    T: Clone,
386{
387    type T = Pile<T>;
388    type Undo = PushBottomMany<T>;
389
390    fn update(&self, value: &mut Self::T) -> AnyResult<impl Into<Option<Self::Undo>>> {
391        let Self {
392            strictness,
393            count,
394            _p,
395        } = *self;
396
397        let mut elements = vec![];
398
399        if strictness == Strictness::AllOrError && value.items.len() <= count {
400            Err(error::Pop::Empty.into())
401        } else {
402            for _ in 0..count {
403                if let Some(element) = value.items.pop_front() {
404                    elements.push(element);
405                }
406            }
407
408            elements.reverse();
409
410            Ok(PushBottomMany { elements })
411        }
412    }
413}
414
415#[derive_where(Default)]
416#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, spru::action::Update)]
417pub struct PushTopMany<T> {
418    elements: Vec<T>,
419}
420
421impl<T> spru::action::Update for PushTopMany<T>
422where
423    T: Clone,
424{
425    type T = Pile<T>;
426    type Undo = PopTopMany<T>;
427
428    fn update(&self, value: &mut Self::T) -> AnyResult<impl Into<Option<Self::Undo>>> {
429        let Self { ref elements } = *self;
430
431        for element in elements {
432            value.items.push_front(element.clone());
433        }
434
435        Ok(PopTopMany {
436            strictness: Strictness::AllOrError,
437            count: elements.len(),
438            _p: PhantomData,
439        })
440    }
441}
442
443impl<T> ops::Deref for PushTopMany<T> {
444    type Target = [T];
445
446    fn deref(&self) -> &Self::Target {
447        &self.elements
448    }
449}
450
451#[derive_where(Default)]
452#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, spru::action::Update)]
453pub struct PushBottomMany<T> {
454    elements: Vec<T>,
455}
456
457impl<T> spru::action::Update for PushBottomMany<T>
458where
459    T: Clone,
460{
461    type T = Pile<T>;
462    type Undo = PopBottomMany<T>;
463
464    fn update(&self, value: &mut Self::T) -> AnyResult<impl Into<Option<Self::Undo>>> {
465        let Self { ref elements } = *self;
466
467        for element in elements {
468            value.items.push_front(element.clone());
469        }
470
471        Ok(PopBottomMany {
472            strictness: Strictness::AllOrError,
473            count: elements.len(),
474            _p: PhantomData,
475        })
476    }
477}
478
479impl<T> ops::Deref for PushBottomMany<T> {
480    type Target = [T];
481
482    fn deref(&self) -> &Self::Target {
483        &self.elements
484    }
485}
486
487#[derive_where(Debug, Clone, Serialize, Deserialize)]
488#[derive(spru::action::Update)]
489pub struct Shuffle<T> {
490    seed: u64,
491    undo: bool,
492    _p: PhantomData<T>,
493}
494
495impl<T> spru::action::Update for Shuffle<T>
496where
497    T: Clone,
498{
499    type T = Pile<T>;
500    type Undo = Self;
501
502    #[allow(refining_impl_trait)]
503    fn update(&self, value: &mut Self::T) -> AnyResult<Self::Undo> {
504        use rand::{Rng, SeedableRng};
505
506        let mut rng = crate::Rng::seed_from_u64(self.seed);
507
508        // Based on the soon-to-be-replaced rand 0.85 implementation
509        fn gen_index(rng: &mut crate::Rng, ubound: usize) -> usize {
510            if ubound <= (u32::MAX as usize) {
511                rng.random_range(0..ubound as u32) as usize
512            } else {
513                rng.random_range(0..ubound)
514            }
515        }
516
517        let mut deferred = self.undo.then_some(vec![]);
518
519        for i in (1..value.items.len()).rev() {
520            let index = gen_index(&mut rng, i + 1);
521            // invariant: elements with index > i have been locked in place.
522            match &mut deferred {
523                Some(deferred) => deferred.push(index),
524                None => value.items.swap(i, index),
525            }
526        }
527
528        if let Some(deferred) = deferred {
529            for (i, index) in (1..value.items.len()).zip(deferred.into_iter().rev()) {
530                value.items.swap(i, index);
531            }
532        }
533
534        Ok(self.invert())
535    }
536}
537
538impl<T> Shuffle<T> {
539    pub fn new(seed: u64) -> Self {
540        Self {
541            seed,
542            undo: false,
543            _p: PhantomData,
544        }
545    }
546
547    fn invert(&self) -> Self {
548        Self {
549            seed: self.seed,
550            undo: !self.undo,
551            _p: PhantomData,
552        }
553    }
554}
555
556#[derive(Debug, Clone, serde::Serialize, serde::Deserialize, spru::action::Update)]
557pub struct Insert<T> {
558    index: usize,
559    element: T,
560}
561
562impl<T: Clone> spru::action::Update for Insert<T> {
563    type T = Pile<T>;
564    type Undo = Remove<T>;
565
566    #[allow(refining_impl_trait)]
567    fn update(&self, value: &mut Self::T) -> AnyResult<Self::Undo> {
568        let index = self.index;
569        if index <= value.items.len() {
570            value.items.insert(index, self.element.clone());
571            Ok(Remove {
572                index,
573                _p: PhantomData,
574            })
575        } else {
576            Err(error::Insert::Index(index, value.items.len()).into())
577        }
578    }
579}
580
581#[derive_where(Debug, Clone, Serialize, Deserialize)]
582#[derive(spru::action::Update)]
583pub struct Remove<T> {
584    index: usize,
585    _p: PhantomData<T>,
586}
587
588impl<T> spru::action::Update for Remove<T> {
589    type T = Pile<T>;
590    type Undo = Insert<T>;
591
592    #[allow(refining_impl_trait)]
593    fn update(&self, value: &mut Self::T) -> AnyResult<Self::Undo> {
594        let index = self.index;
595        if index < value.items.len() {
596            let element = value.items.remove(index);
597            Ok(Insert { index, element })
598        } else {
599            Err(error::Remove::Index(index, value.items.len()).into())
600        }
601    }
602}
603
604#[derive_where(Debug, Clone, Serialize, Deserialize)]
605#[derive(spru::action::Update)]
606pub struct Clear<T> {
607    _p: PhantomData<T>,
608}
609
610impl<T> spru::action::Update for Clear<T> {
611    type T = Pile<T>;
612    type Undo = Update<T>;
613
614    #[allow(refining_impl_trait)]
615    fn update(&self, value: &mut Self::T) -> AnyResult<Self::Undo> {
616        let items = mem::take(&mut value.items);
617        Ok(update(items.0))
618    }
619}
620
621#[cfg(test)]
622mod test {
623    use rand::rng;
624    use spru::action::{Create as _, Update as _};
625
626    use super::*;
627
628    #[test]
629    fn test_shuffle() {
630        let create = create([1, 2, 3, 4, 5, 6, 7, 8]);
631        let (mut pile, _) = create.create().unwrap();
632
633        shuffle(&mut rng()).update(&mut pile).unwrap();
634
635        let orig_order = pile.items.clone();
636
637        let undo = shuffle(&mut rng()).update(&mut pile).unwrap();
638
639        assert_ne!(pile.items, orig_order);
640
641        undo.update(&mut pile).unwrap();
642
643        assert_eq!(pile.items, orig_order);
644    }
645}
spru_util/pile/mod.rs

spru_util/pile/
mod.rs
