common_range_tools/
iter.rs

1use crate::{
2    AnyIncDecCpCmp, DefaultValues, GetBeginEnd, GetBeginEndOption, IncDecCpCmp, MrsP,
3    NumberIncDecCpCmp, RangeRelation, RiFactory, first_range_begin_end, last_range_begin_end,
4    next_range_begin_end, previous_range_begin_end, range_bounds_to_values, range_relation,
5};
6
7use std::marker::PhantomData;
8use std::mem;
9use std::ops::RangeInclusive;
10use std::ops::{Add, RangeBounds, Sub};
11
12/// Core of the consolidation code.
13pub mod consolidate;
14
15/// The core [Iterator]+[DoubleEndedIterator] for finding range intersections.
16pub struct OverlapIter<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, F: GetBeginEndOption<T, R>> {
17    src: Vec<R>,
18    step: V,
19    cmp: C,
20    next: Option<R>,
21    back: Option<R>,
22    last_next: Option<R>,
23    last_back: Option<R>,
24    factory: F,
25    _marker: PhantomData<T>,
26}
27
28impl<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, F: GetBeginEndOption<T, R>>
29    OverlapIter<T, V, C, R, F>
30{
31    /// Creates a new [OverlapIter] from the slice of R.
32    pub fn new(src: Vec<R>, step: V, cmp: C, factory: F) -> Self {
33        let next = factory.factory(first_range_begin_end(&src, &step, &cmp));
34        let back = factory.factory(last_range_begin_end(&src, &step, &cmp));
35
36        Self {
37            src,
38            step,
39            cmp,
40            next,
41            back,
42            last_next: None,
43            last_back: None,
44            factory,
45            _marker: PhantomData,
46        }
47    }
48
49    /// Tries to copy the src ref range via the internals.
50    /// Returns None if it fails.
51    pub fn copy_range<U: GetBeginEnd<T>>(&self, src: &U) -> Option<R> {
52        let a = self.cmp.cp(src.get_begin());
53        let z = self.cmp.cp(src.get_end());
54        return self.factory.factory(Some((a, z)));
55    }
56
57    /// Returns a tuple of Option refs to the internal next and last_next ranges.
58    pub fn ln(&self) -> (Option<&R>, Option<&R>) {
59        let a;
60        let b;
61        match &self.next {
62            Some(n) => a = Some(n),
63            _ => a = None,
64        }
65        match &self.last_next {
66            Some(n) => b = Some(n),
67            _ => b = None,
68        }
69
70        return (a, b);
71    }
72
73    /// Returns a tuple of Option refs to the internal back and last_back ranges.
74    pub fn lb(&self) -> (Option<&R>, Option<&R>) {
75        let a;
76        let b;
77        match &self.back {
78            Some(n) => a = Some(n),
79            _ => a = None,
80        }
81        match &self.last_back {
82            Some(n) => b = Some(n),
83            _ => b = None,
84        }
85
86        return (a, b);
87    }
88
89    /// After calling [OverlapIter::update_column], call this method in place of [OverlapIter::next] to return the properly updated next value.
90    /// Calling this method resets the curent state of [OverlapIter::next_back].
91    pub fn recompute_next(&mut self) -> Option<R> {
92        self.last_back = None;
93        self.back = self
94            .factory
95            .factory(last_range_begin_end(&self.src, &self.step, &self.cmp));
96
97        let last_next = mem::replace(&mut self.last_next, None);
98        match last_next {
99            Some(x) => self.next = self.try_next(&Some(x)),
100            _ => return None,
101        }
102
103        return self.next();
104    }
105
106    /// After calling [OverlapIter::update_column], call this method in place of [OverlapIter::next_back] to return the properly updated back value.
107    /// Calling this method resets the curent state of [OverlapIter::next].
108    pub fn recompute_back(&mut self) -> Option<R> {
109        self.last_next = None;
110        self.next = self
111            .factory
112            .factory(first_range_begin_end(&self.src, &self.step, &self.cmp));
113        let last_back = mem::replace(&mut self.last_back, None);
114        match last_back {
115            Some(x) => self.back = self.try_next_back(&Some(x)),
116            _ => return None,
117        }
118
119        return self.next_back();
120    }
121
122    /// Updates the internal column to the new [GetBeginEnd] instance.
123    /// Returns [Result::Err] if the range is invalid or if the index point does not exist.
124    ///
125    /// After calling this method the next call to  [OverlapIter::next] or [OverlapIter::next_back] will not function correctly.
126    /// First call the respective [OverlapIter::recompute_next] or [OverlapIter::recompute_back],
127    /// then proceed to call either [OverlapIter::next] or [OverlapIter::next_back] normally.
128    pub fn update_column(&mut self, idx: usize, range: R) -> Result<(), &'static str> {
129        if let Some(col) = self.src.get_mut(idx) {
130            if self.cmp.is_invalid_set(range.get_begin(), range.get_end()) {
131                return Err("Invalid Range");
132            }
133            *col = range;
134            return Ok(());
135        }
136        return Err("No such Column");
137    }
138
139    /// Genrates a new next based on the src passed in.
140    pub fn try_next(&self, src: &Option<R>) -> Option<R> {
141        let mut next = None;
142        if let Some(n) = src {
143            match &self.back {
144                Some(b) => match range_relation(n, b, &self.cmp) {
145                    RangeRelation::Overlap(_) => {
146                        if let Some(begin) = self.cmp.inc(n.get_end(), &self.step) {
147                            next = self.factory.factory(next_range_begin_end(
148                                &begin,
149                                &[
150                                    MrsP {
151                                        r: b,
152                                        _t: PhantomData,
153                                    },
154                                    MrsP {
155                                        r: n,
156                                        _t: PhantomData,
157                                    },
158                                ],
159                                &self.step,
160                                &self.cmp,
161                            ));
162                        }
163                    }
164                    RangeRelation::Before(_) => {
165                        if let Some(begin) = self.cmp.inc(n.get_end(), &self.step) {
166                            next = self.factory.factory(next_range_begin_end(
167                                &begin, &self.src, &self.step, &self.cmp,
168                            ));
169                        }
170                    }
171                    _ => return None,
172                },
173                None => (),
174            }
175        }
176        return next;
177    }
178
179    /// Genrates a new back based on the src passed in.
180    pub fn try_next_back(&self, src: &Option<R>) -> Option<R> {
181        let mut back = None;
182        if let Some(b) = src
183            && let Some(n) = &self.next
184        {
185            match range_relation(b, n, &self.cmp) {
186                RangeRelation::Overlap(_) => {
187                    if let Some(end) = self.cmp.dec(b.get_begin(), &self.step) {
188                        back = self.factory.factory(previous_range_begin_end(
189                            &end,
190                            &[
191                                MrsP {
192                                    r: n,
193                                    _t: PhantomData,
194                                },
195                                MrsP {
196                                    r: b,
197                                    _t: PhantomData,
198                                },
199                            ],
200                            &self.step,
201                            &self.cmp,
202                        ));
203                    }
204                }
205                RangeRelation::After(_) => {
206                    if let Some(end) = self.cmp.dec(b.get_begin(), &self.step) {
207                        back = self.factory.factory(previous_range_begin_end(
208                            &end, &self.src, &self.step, &self.cmp,
209                        ));
210                    }
211                }
212                _ => return None,
213            }
214        }
215        return back;
216    }
217}
218
219impl<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, F: GetBeginEndOption<T, R>> Iterator
220    for OverlapIter<T, V, C, R, F>
221{
222    type Item = R;
223
224    /// This is part of a [DoubleEndedIterator] calls to [OverlapIter::next] impact calls to [OverlapIter::next_back].
225    /// ## Big O Notation
226    /// Each call to self.next() is a time complexity of O(n*3)
227    fn next(&mut self) -> Option<Self::Item> {
228        let next = self.try_next(&self.next);
229        if let Some(next) = &self.next {
230            self.last_next = self.copy_range(next);
231        }
232        return mem::replace(&mut self.next, next);
233    }
234}
235
236impl<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, F: GetBeginEndOption<T, R>> DoubleEndedIterator
237    for OverlapIter<T, V, C, R, F>
238{
239    /// This is part of a [DoubleEndedIterator] calls to [OverlapIter::next_back] impact calls to [OverlapIter::next].
240    /// ## Big O Notation
241    /// Each call to self.next_back() is a time complexity of O(n*3)
242    fn next_back(&mut self) -> Option<Self::Item> {
243        let back = self.try_next_back(&self.back);
244        if let Some(back) = &self.back {
245            self.last_back = self.copy_range(back);
246        }
247        return mem::replace(&mut self.back, back);
248    }
249}
250
251/// This acts as a general [OverlapIter] factory.
252///
253/// *The self.add_* methods*:
254///
255/// The various add_* methods return the index of the column that was added and the generated instance of [GetBeginEnd].
256/// The index can be used to update that column during the iteration process
257/// of the returned [OverlapIter] object instance.
258/// See [OverlapIter::update_column] for more details.
259pub struct Intersector<T, V, C: IncDecCpCmp<T, V>, R, F> {
260    list: Vec<R>,
261    step: V,
262    rebound: V,
263    cmp: C,
264    factory: F,
265    _r: PhantomData<(T, R)>,
266}
267
268impl<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, B: GetBeginEndOption<T, R>>
269    Intersector<T, V, C, R, B>
270{
271    /// Constructs a new instance of [Intersector].
272    pub fn new(list: Vec<R>, step: V, rebound: V, cmp: C, factory: B) -> Self {
273        Self {
274            list,
275            step,
276            rebound,
277            cmp,
278            factory,
279            _r: PhantomData,
280        }
281    }
282}
283
284impl<T, V> Intersector<T, V, AnyIncDecCpCmp<T>, RangeInclusive<T>, RiFactory<T>>
285where
286    T: PartialOrd + Copy + Add<V, Output = T> + Sub<V, Output = T>,
287    V: Copy,
288{
289    /// Creates a new [Intersector] instance that works with any data type.
290    pub fn any(
291        step: V,
292        rebound: V,
293        min: T,
294        max: T,
295    ) -> Intersector<T, V, AnyIncDecCpCmp<T>, RangeInclusive<T>, RiFactory<T>> {
296        Self {
297            list: Vec::new(),
298            step,
299            rebound,
300            cmp: AnyIncDecCpCmp::new(min, max),
301            factory: RiFactory::new(),
302            _r: PhantomData,
303        }
304    }
305
306    pub fn any_from(
307        step: V,
308        rebound: V,
309        min: T,
310        max: T,
311        src: &[impl RangeBounds<T>],
312    ) -> OverlapIter<T, V, AnyIncDecCpCmp<T>, RangeInclusive<T>, RiFactory<T>> {
313        let mut i = Self::any(step, rebound, min, max);
314        for r in src {
315            i.add_range(r);
316        }
317        return i.into_iter();
318    }
319}
320
321impl<T> Intersector<T, T, NumberIncDecCpCmp<T>, RangeInclusive<T>, RiFactory<T>>
322where
323    T: PartialOrd + Copy + Add<T, Output = T> + Sub<T, Output = T>,
324    NumberIncDecCpCmp<T>: DefaultValues<T, T>,
325{
326    /// Returns a new instance of [Intersector] configured to work with any primitive number type using the default values.
327    pub fn num_defaults() -> Self {
328        let cmp = NumberIncDecCpCmp::defaults();
329        return Self {
330            list: Vec::new(),
331            step: cmp.default_step(),
332            rebound: cmp.default_rebound(),
333            cmp,
334            factory: RiFactory::new(),
335            _r: PhantomData,
336        };
337    }
338
339    /// Returns a new instance of [Intersector] configured to work with numbers based on the arguments passed in.
340    pub fn num(step: T, rebound: T, min: T, max: T) -> Self {
341        return Self {
342            list: Vec::new(),
343            step,
344            rebound,
345            cmp: NumberIncDecCpCmp::new(min, max),
346            factory: RiFactory::new(),
347            _r: PhantomData,
348        };
349    }
350
351    /// Returns a new instance of [Intersector] configured to work with numbers.
352    /// The nteral step and rebound values are set to sr.
353    pub fn num_sr(sr: T) -> Self {
354        return Self {
355            list: Vec::new(),
356            step: sr,
357            rebound: sr,
358            cmp: NumberIncDecCpCmp::defaults(),
359            factory: RiFactory::new(),
360            _r: PhantomData,
361        };
362    }
363
364    /// Takes any list of range of numbers and converts them to an instance of [OverlapIter].
365    pub fn num_from(
366        src: &[impl RangeBounds<T>],
367    ) -> OverlapIter<T, T, NumberIncDecCpCmp<T>, RangeInclusive<T>, RiFactory<T>> {
368        let mut i = Self::num_defaults();
369        for r in src {
370            i.add_range(r);
371        }
372        return i.into_iter();
373    }
374
375    /// Takes any list of range of numbers and converts them to an instance of [OverlapIter], with the step and rebound value set to sr.
376    pub fn num_sr_from(
377        sr: T,
378        src: &[impl RangeBounds<T>],
379    ) -> OverlapIter<T, T, NumberIncDecCpCmp<T>, RangeInclusive<T>, RiFactory<T>> {
380        let mut i = Self::num_sr(sr);
381        for r in src {
382            i.add_range(r);
383        }
384        return i.into_iter();
385    }
386}
387
388macro_rules! impl_intersector_num_core{
389    ($($t:ty),*) => {
390        $(
391            impl Intersector<$t, $t, NumberIncDecCpCmp<$t>, RangeInclusive<$t>,RiFactory<$t>>
392            where NumberIncDecCpCmp<$t>: DefaultValues<$t,$t> {}
393
394        )*
395    };
396}
397impl_intersector_num_core!(
398    i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, f32, f64
399);
400
401impl<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, F: GetBeginEndOption<T, R>>
402    Intersector<T, V, C, R, F>
403{
404    /// Tries to add an instance of [GetBeginEnd] to this instance returns None if src is invalid.
405    pub fn add_raw_range(&mut self, src: R) -> Option<(usize, &R)> {
406        if self.cmp.is_invalid_set(&src.get_begin(), &src.get_end()) {
407            return None;
408        }
409        self.list.push(src);
410        let id = self.list.len() - 1;
411        return Some((id, &self.list[id]));
412    }
413
414    /// Tries to create and add a valid internal range from the tuple of refs.
415    pub fn add_from_tuple_ref(&mut self, src: (&T, &T)) -> Option<(usize, &R)> {
416        let a = self.cmp.cp(src.0);
417        let z = self.cmp.cp(src.1);
418        return self.add_from_tuple((a, z));
419    }
420    /// Tries to add a tuple to the instance, returns None if it fails.
421    pub fn add_from_tuple(&mut self, src: (T, T)) -> Option<(usize, &R)> {
422        match self.factory.factory(Some(src)) {
423            Some(mrs) => return self.add_raw_range(mrs),
424            None => None,
425        }
426    }
427
428    /// This is really a wrapper for [crate::range_bounds_to_values].
429    pub fn rebound(&self, r: &impl RangeBounds<T>) -> Option<(T, T)> {
430        return range_bounds_to_values(r, self.get_rebound(), self.get_cmp());
431    }
432
433    /// Tries to convert a given [RangeBounds] instance to the internal range type.
434    /// Returns None if the conversion process fails or the range produced is invalid.
435    pub fn add_range(&mut self, r: &impl RangeBounds<T>) -> Option<(usize, &R)> {
436        match self.rebound(r) {
437            Some(src) => self.add_tuple(src),
438            None => None,
439        }
440    }
441
442    /// Tries to convert a tuple to the internal range type and add it.
443    /// Returns None if the conversion process fails or the resulting range is invalid.
444    pub fn add_tuple(&mut self, src: (T, T)) -> Option<(usize, &R)> {
445        return self.add_from_tuple(src);
446    }
447
448    /// Returns a mutable ref to the internal instance of [IncDecCpCmp].
449    pub fn get_cmp_mut(&mut self) -> &mut C {
450        return &mut self.cmp;
451    }
452
453    /// Returns a ref to the internal instance of [IncDecCpCmp].
454    pub fn get_cmp(&self) -> &C {
455        return &self.cmp;
456    }
457
458    /// Returns a ref to the internal rebound value.
459    pub fn get_rebound(&self) -> &V {
460        return &self.rebound;
461    }
462
463    /// Returns a ref to the internal step value.
464    pub fn get_step(&self) -> &V {
465        return &self.step;
466    }
467
468    /// Updates the internal rebound value.
469    pub fn set_rebound(&mut self, rebound: V) {
470        self.rebound = rebound;
471    }
472
473    /// Updates the internal step value.
474    pub fn set_step(&mut self, step: V) {
475        self.step = step;
476    }
477}
478
479impl<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>, F: GetBeginEndOption<T, R>> IntoIterator
480    for Intersector<T, V, C, R, F>
481{
482    type Item = R;
483
484    type IntoIter = OverlapIter<T, V, C, R, F>;
485
486    /// Converts the current instance of [Intersector] into an instance of [OverlapIter].
487    fn into_iter(self) -> Self::IntoIter {
488        return OverlapIter::new(self.list, self.step, self.cmp, self.factory);
489    }
490}
common_range_tools/iter.rs

common_range_tools/
iter.rs
