vec_collections/
merge_state.rs

1#![allow(dead_code)]
2use crate::iterators::SliceIterator;
3use binary_merge::{MergeOperation, MergeState};
4use core::{fmt, fmt::Debug};
5use inplace_vec_builder::{InPlaceSmallVecBuilder, InPlaceVecBuilder};
6use smallvec::{Array, SmallVec};
7use std::marker::PhantomData;
8
9/// A typical write part for the merge state
10pub(crate) trait MergeStateMut: MergeState {
11    /// Consume n elements of a
12    fn advance_a(&mut self, n: usize, take: bool) -> bool;
13    /// Consume n elements of b
14    fn advance_b(&mut self, n: usize, take: bool) -> bool;
15}
16
17pub(crate) trait MutateInput: MergeStateMut {
18    fn source_slices_mut(&mut self) -> (&mut [Self::A], &[Self::B]);
19}
20
21pub(crate) struct InPlaceMergeState<
22    'a,
23    A: Array,
24    B: Array,
25    C: Converter<B::Item, A::Item> = NoConverter,
26> {
27    pub a: InPlaceSmallVecBuilder<'a, A>,
28    pub b: smallvec::IntoIter<B>,
29    _c: PhantomData<C>,
30}
31
32impl<'a, A: Array, B: Array, C: Converter<B::Item, A::Item>> InPlaceMergeState<'a, A, B, C> {
33    fn new(a: &'a mut SmallVec<A>, b: SmallVec<B>) -> Self {
34        Self {
35            a: a.into(),
36            b: b.into_iter(),
37            _c: PhantomData,
38        }
39    }
40}
41
42impl<'a, A: Array, B: Array, C: Converter<B::Item, A::Item>> MergeState
43    for InPlaceMergeState<'a, A, B, C>
44{
45    type A = A::Item;
46    type B = B::Item;
47    fn a_slice(&self) -> &[A::Item] {
48        self.a.source_slice()
49    }
50    fn b_slice(&self) -> &[B::Item] {
51        self.b.as_slice()
52    }
53}
54
55impl<'a, A: Array, B: Array, C: Converter<B::Item, A::Item>> MergeStateMut
56    for InPlaceMergeState<'a, A, B, C>
57{
58    fn advance_a(&mut self, n: usize, take: bool) -> bool {
59        self.a.consume(n, take);
60        true
61    }
62    fn advance_b(&mut self, n: usize, take: bool) -> bool {
63        if take {
64            self.a.extend_from_iter((&mut self.b).map(C::convert), n);
65        } else {
66            for _ in 0..n {
67                let _ = self.b.next();
68            }
69        }
70        true
71    }
72}
73
74impl<'a, A: Array, B: Array, C: Converter<B::Item, A::Item>> InPlaceMergeState<'a, A, B, C> {
75    pub fn merge<O: MergeOperation<Self>>(a: &'a mut SmallVec<A>, b: SmallVec<B>, o: O, _c: C) {
76        let mut state = Self::new(a, b);
77        o.merge(&mut state);
78    }
79}
80
81/// An in place merge state where the rhs is a reference
82pub(crate) struct InPlaceSmallVecMergeStateRef<
83    'a,
84    A: Array,
85    B,
86    C: Converter<&'a B, A::Item> = NoConverter,
87> {
88    pub(crate) a: InPlaceSmallVecBuilder<'a, A>,
89    pub(crate) b: SliceIterator<'a, B>,
90    _c: PhantomData<C>,
91}
92
93impl<'a, A: Array, B, C: Converter<&'a B, A::Item>> InPlaceSmallVecMergeStateRef<'a, A, B, C> {
94    fn new(a: &'a mut SmallVec<A>, b: &'a impl AsRef<[B]>) -> Self {
95        Self {
96            a: a.into(),
97            b: SliceIterator(b.as_ref()),
98            _c: PhantomData,
99        }
100    }
101}
102
103impl<'a, A: Array, B, C: Converter<&'a B, A::Item>> MergeState
104    for InPlaceSmallVecMergeStateRef<'a, A, B, C>
105{
106    type A = A::Item;
107    type B = B;
108    fn a_slice(&self) -> &[A::Item] {
109        self.a.source_slice()
110    }
111    fn b_slice(&self) -> &[B] {
112        self.b.as_slice()
113    }
114}
115
116impl<'a, A: Array, B, C: Converter<&'a B, A::Item>> MergeStateMut
117    for InPlaceSmallVecMergeStateRef<'a, A, B, C>
118where
119    A::Item: Clone,
120{
121    fn advance_a(&mut self, n: usize, take: bool) -> bool {
122        self.a.consume(n, take);
123        true
124    }
125    fn advance_b(&mut self, n: usize, take: bool) -> bool {
126        if take {
127            self.a.extend_from_iter((&mut self.b).map(C::convert), n);
128        } else {
129            for _ in 0..n {
130                let _ = self.b.next();
131            }
132        }
133        true
134    }
135}
136
137impl<'a, A, B, C: Converter<&'a B, A::Item>> MutateInput
138    for InPlaceSmallVecMergeStateRef<'a, A, B, C>
139where
140    A: Array,
141    A::Item: Clone,
142{
143    fn source_slices_mut(&mut self) -> (&mut [Self::A], &[Self::B]) {
144        (self.a.source_slice_mut(), self.b.as_slice())
145    }
146}
147
148impl<'a, A: Array, B: 'a, C: Converter<&'a B, A::Item>> InPlaceSmallVecMergeStateRef<'a, A, B, C> {
149    pub fn merge<O: MergeOperation<Self>>(
150        a: &'a mut SmallVec<A>,
151        b: &'a impl AsRef<[B]>,
152        o: O,
153        _: C,
154    ) {
155        let mut state = Self::new(a, b);
156        o.merge(&mut state);
157    }
158}
159
160/// An in place merge state where the rhs is a reference
161pub(crate) struct InPlaceVecMergeStateRef<'a, A, B, C: Converter<&'a B, A> = NoConverter> {
162    pub(crate) a: InPlaceVecBuilder<'a, A>,
163    pub(crate) b: SliceIterator<'a, B>,
164    _c: PhantomData<C>,
165}
166
167impl<'a, A, B, C: Converter<&'a B, A>> InPlaceVecMergeStateRef<'a, A, B, C> {
168    fn new(a: &'a mut Vec<A>, b: &'a impl AsRef<[B]>) -> Self {
169        Self {
170            a: a.into(),
171            b: SliceIterator(b.as_ref()),
172            _c: PhantomData,
173        }
174    }
175}
176
177impl<'a, A, B, C: Converter<&'a B, A>> MergeState for InPlaceVecMergeStateRef<'a, A, B, C> {
178    type A = A;
179    type B = B;
180    fn a_slice(&self) -> &[A] {
181        self.a.source_slice()
182    }
183    fn b_slice(&self) -> &[B] {
184        self.b.as_slice()
185    }
186}
187
188impl<'a, A, B, C: Converter<&'a B, A>> MergeStateMut for InPlaceVecMergeStateRef<'a, A, B, C>
189where
190    A: Clone,
191{
192    fn advance_a(&mut self, n: usize, take: bool) -> bool {
193        self.a.consume(n, take);
194        true
195    }
196    fn advance_b(&mut self, n: usize, take: bool) -> bool {
197        if take {
198            self.a.extend_from_iter((&mut self.b).map(C::convert), n);
199        } else {
200            for _ in 0..n {
201                let _ = self.b.next();
202            }
203        }
204        true
205    }
206}
207
208impl<'a, A, B, C: Converter<&'a B, A>> MutateInput for InPlaceVecMergeStateRef<'a, A, B, C>
209where
210    A: Clone,
211{
212    fn source_slices_mut(&mut self) -> (&mut [Self::A], &[Self::B]) {
213        (self.a.source_slice_mut(), self.b.as_slice())
214    }
215}
216
217impl<'a, A, B: 'a, C: Converter<&'a B, A>> InPlaceVecMergeStateRef<'a, A, B, C> {
218    pub fn merge<O: MergeOperation<Self>>(a: &'a mut Vec<A>, b: &'a impl AsRef<[B]>, o: O, _: C) {
219        let mut state = Self::new(a, b);
220        o.merge(&mut state);
221    }
222}
223
224/// A merge state where we only track if elements have been produced, and abort as soon as the first element is produced
225pub(crate) struct BoolOpMergeState<'a, A, B> {
226    a: SliceIterator<'a, A>,
227    b: SliceIterator<'a, B>,
228    r: bool,
229}
230
231impl<'a, A: Debug, B: Debug> Debug for BoolOpMergeState<'a, A, B> {
232    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
233        write!(
234            f,
235            "a: {:?}, b: {:?} r: {}",
236            self.a_slice(),
237            self.b_slice(),
238            self.r
239        )
240    }
241}
242
243impl<'a, A, B> BoolOpMergeState<'a, A, B> {
244    fn new(a: &'a [A], b: &'a [B]) -> Self {
245        Self {
246            a: SliceIterator(a),
247            b: SliceIterator(b),
248            r: false,
249        }
250    }
251}
252
253impl<'a, A, B> BoolOpMergeState<'a, A, B> {
254    pub fn merge<O: MergeOperation<Self>>(a: &'a [A], b: &'a [B], o: O) -> bool {
255        let mut state = Self::new(a, b);
256        o.merge(&mut state);
257        state.r
258    }
259}
260
261impl<'a, A, B> MergeState for BoolOpMergeState<'a, A, B> {
262    type A = A;
263    type B = B;
264    fn a_slice(&self) -> &[A] {
265        self.a.as_slice()
266    }
267    fn b_slice(&self) -> &[B] {
268        self.b.as_slice()
269    }
270}
271
272impl<'a, A, B> MergeStateMut for BoolOpMergeState<'a, A, B> {
273    fn advance_a(&mut self, n: usize, take: bool) -> bool {
274        if take {
275            self.r = true;
276            false
277        } else {
278            self.a.drop_front(n);
279            true
280        }
281    }
282    fn advance_b(&mut self, n: usize, take: bool) -> bool {
283        if take {
284            self.r = true;
285            false
286        } else {
287            self.b.drop_front(n);
288            true
289        }
290    }
291}
292
293pub trait Converter<A, B> {
294    fn convert(value: A) -> B;
295}
296
297/// A converter that does not work. Use this only if you are sure it will never be used.
298pub struct NoConverter;
299
300impl<A, B> Converter<A, B> for NoConverter {
301    fn convert(_: A) -> B {
302        panic!("conversion not possible")
303    }
304}
305
306/// The clone converter that clones the value
307pub struct CloneConverter;
308
309impl<A: Clone> Converter<&A, A> for CloneConverter {
310    fn convert(value: &A) -> A {
311        value.clone()
312    }
313}
314
315/// The identity converter that just passes through the value
316pub struct IdConverter;
317
318impl<A> Converter<A, A> for IdConverter {
319    fn convert(value: A) -> A {
320        value
321    }
322}
323
324/// A merge state where we build into a new smallvec
325pub(crate) struct SmallVecMergeState<'a, A, B, Arr: Array, C: Converter<&'a B, A> = NoConverter> {
326    pub a: SliceIterator<'a, A>,
327    pub b: SliceIterator<'a, B>,
328    pub r: SmallVec<Arr>,
329    _c: PhantomData<C>,
330}
331
332impl<'a, A: Debug, B: Debug, Arr: Array> Debug for SmallVecMergeState<'a, A, B, Arr> {
333    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
334        write!(f, "a: {:?}, b: {:?}", self.a_slice(), self.b_slice(),)
335    }
336}
337
338impl<'a, A, B, Arr: Array, C: Converter<&'a B, A>> SmallVecMergeState<'a, A, B, Arr, C> {
339    fn new(a: &'a [A], b: &'a [B], r: SmallVec<Arr>) -> Self {
340        Self {
341            a: SliceIterator(a),
342            b: SliceIterator(b),
343            r,
344            _c: PhantomData,
345        }
346    }
347
348    pub fn into_vec(self) -> SmallVec<Arr> {
349        self.r
350    }
351
352    pub fn merge<O: MergeOperation<Self>>(a: &'a [A], b: &'a [B], o: O, _c: C) -> SmallVec<Arr> {
353        let t: SmallVec<Arr> = SmallVec::new();
354        let mut state = Self::new(a, b, t);
355        o.merge(&mut state);
356        state.into_vec()
357    }
358}
359
360impl<'a, A, B, Arr: Array, C: Converter<&'a B, A>> MergeState
361    for SmallVecMergeState<'a, A, B, Arr, C>
362{
363    type A = A;
364    type B = B;
365    fn a_slice(&self) -> &[A] {
366        self.a.as_slice()
367    }
368    fn b_slice(&self) -> &[B] {
369        self.b.as_slice()
370    }
371}
372
373impl<'a, A: Clone, B, Arr: Array<Item = A>, C: Converter<&'a B, A>> MergeStateMut
374    for SmallVecMergeState<'a, A, B, Arr, C>
375{
376    fn advance_a(&mut self, n: usize, take: bool) -> bool {
377        if take {
378            self.r.reserve(n);
379            for e in self.a.take_front(n).iter() {
380                self.r.push(e.clone())
381            }
382        } else {
383            self.a.drop_front(n);
384        }
385        true
386    }
387    fn advance_b(&mut self, n: usize, take: bool) -> bool {
388        if take {
389            self.r.reserve(n);
390            for e in self.b.take_front(n).iter() {
391                self.r.push(C::convert(e))
392            }
393        } else {
394            self.b.drop_front(n);
395        }
396        true
397    }
398}
399
400/// A merge state where we build into a new vec
401pub(crate) struct VecMergeState<'a, A, B, R, AC, BC> {
402    pub a: SliceIterator<'a, A>,
403    pub b: SliceIterator<'a, B>,
404    pub r: Vec<R>,
405    _c: PhantomData<(AC, BC)>,
406}
407
408impl<'a, A: Debug, B: Debug, R, AC, BC> Debug for VecMergeState<'a, A, B, R, AC, BC> {
409    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
410        write!(f, "a: {:?}, b: {:?}", self.a_slice(), self.b_slice(),)
411    }
412}
413
414impl<'a, A, B, R, AC: Converter<&'a A, R>, BC: Converter<&'a B, R>>
415    VecMergeState<'a, A, B, R, AC, BC>
416{
417    fn new(a: &'a [A], b: &'a [B], r: Vec<R>) -> Self {
418        Self {
419            a: SliceIterator(a),
420            b: SliceIterator(b),
421            r,
422            _c: PhantomData,
423        }
424    }
425
426    fn into_vec(self) -> Vec<R> {
427        self.r
428    }
429
430    pub fn merge<O: MergeOperation<Self>>(
431        a: &'a [A],
432        b: &'a [B],
433        o: O,
434        _ac: AC,
435        _bc: BC,
436    ) -> Vec<R> {
437        let t: Vec<R> = Vec::new();
438        let mut state = Self::new(a, b, t);
439        o.merge(&mut state);
440        state.into_vec()
441    }
442}
443
444impl<'a, A, B, R, AC, BC> MergeState for VecMergeState<'a, A, B, R, AC, BC> {
445    type A = A;
446    type B = B;
447    fn a_slice(&self) -> &[A] {
448        self.a.as_slice()
449    }
450    fn b_slice(&self) -> &[B] {
451        self.b.as_slice()
452    }
453}
454
455impl<'a, A, B, R, AC: Converter<&'a A, R>, BC: Converter<&'a B, R>> MergeStateMut
456    for VecMergeState<'a, A, B, R, AC, BC>
457{
458    fn advance_a(&mut self, n: usize, take: bool) -> bool {
459        if take {
460            self.r.reserve(n);
461            for e in self.a.take_front(n).iter() {
462                self.r.push(AC::convert(e))
463            }
464        } else {
465            self.a.drop_front(n);
466        }
467        true
468    }
469    fn advance_b(&mut self, n: usize, take: bool) -> bool {
470        if take {
471            self.r.reserve(n);
472            for e in self.b.take_front(n).iter() {
473                self.r.push(BC::convert(e))
474            }
475        } else {
476            self.b.drop_front(n);
477        }
478        true
479    }
480}
vec_collections/merge_state.rs

vec_collections/
merge_state.rs
