common_range_tools/
utils.rs

1//! The [crate::utils] module represents the static methods that drive most of the overlap and consolidation intenrals.
2//! The static methods are exposed for general use and testing.
3
4use crate::{CpCmp, GetBeginEnd, GetBeginEndOption, Mrs, builder::IncDecCpCmp};
5use std::{
6    cmp::Ordering,
7    mem,
8    ops::{
9        Bound::{Excluded, Included, Unbounded},
10        RangeBounds,
11    },
12};
13
14/// This enum is used to represent positional relationships between 2 ranges.
15///  - before a range: [RangeRelation::Before]
16///  - overlap with a range: [RangeRelation::Overlap]
17///  - after a range: [RangeRelation::Overlap]
18///
19/// The additional states, represent the initialization of the set.
20///  - empty or no data: [RangeRelation::Invalid]
21///  - last or final: [RangeRelation::Last]
22pub enum RangeRelation<T> {
23    /// Range a is before range b
24    Before(T),
25
26    /// Range a and b overlap
27    Overlap(T),
28
29    /// Range a is after range b
30    After(T),
31
32    /// Represents final set of data
33    Last(T),
34
35    /// Denotes a was not valid
36    Invalid(T),
37}
38
39impl<T> RangeRelation<T> {
40    /// Unwraps the Value.
41    pub fn unwrap(self) -> T {
42        match self {
43            RangeRelation::After(v)
44            | RangeRelation::Before(v)
45            | RangeRelation::Last(v)
46            | RangeRelation::Invalid(v)
47            | RangeRelation::Overlap(v) => return v,
48        }
49    }
50    /// Unwraps the state of [RangeRelation::Invalid] or panics!.
51    pub fn invalid(self) -> T {
52        match self {
53            RangeRelation::Invalid(data) => data,
54            _ => panic!("Not Last!"),
55        }
56    }
57
58    /// Unwraps the state of [RangeRelation::Last] or panics!
59    pub fn last(self) -> T {
60        match self {
61            RangeRelation::Last(data) => data,
62            _ => panic!("Not Last!"),
63        }
64    }
65
66    /// Unwraps the state of [RangeRelation::Before] or panics!
67    pub fn before(self) -> T {
68        match self {
69            RangeRelation::Before(data) => data,
70            _ => panic!("Not Before!"),
71        }
72    }
73
74    /// Unwraps the state of [RangeRelation::Overlap] or panics!
75    pub fn overlap(self) -> T {
76        match self {
77            RangeRelation::Overlap(data) => data,
78            _ => panic!("Not Overlap!"),
79        }
80    }
81
82    /// Unwraps the state of [RangeRelation::After] or panics!
83    pub fn after(self) -> T {
84        match self {
85            RangeRelation::After(data) => data,
86            _ => panic!("Not After!"),
87        }
88    }
89
90    /// Returns true if [RangeRelation::Last].
91    pub fn is_last(&self) -> bool {
92        match self {
93            RangeRelation::Last(_) => true,
94            _ => false,
95        }
96    }
97
98    /// Returns true if [RangeRelation::Invalid].
99    pub fn is_invalid(&self) -> bool {
100        match self {
101            RangeRelation::Invalid(_) => true,
102            _ => false,
103        }
104    }
105
106    /// Returns true if [RangeRelation::Overlap].
107    pub fn is_overlap(&self) -> bool {
108        match self {
109            RangeRelation::Overlap(_) => true,
110            _ => false,
111        }
112    }
113
114    /// Returns true if [RangeRelation::Before].
115    pub fn is_before(&self) -> bool {
116        match self {
117            RangeRelation::Before(_) => true,
118            _ => false,
119        }
120    }
121
122    /// Returns true if [RangeRelation::After].
123    pub fn is_after(&self) -> bool {
124        match self {
125            RangeRelation::After(_) => true,
126            _ => false,
127        }
128    }
129}
130/// Compares the positional relationship between a and b.
131///
132/// - [RangeRelation::Invalid] a was not a valid range.
133/// - [RangeRelation::Before] a is before b.
134/// - [RangeRelation::After] a is after b.
135/// - [RangeRelation::Overlap] a and b overlap to some degree.
136pub fn range_relation<T, R: GetBeginEnd<T>, N: GetBeginEnd<T>, C: CpCmp<T>>(
137    a: &R,
138    b: &N,
139    t: &C,
140) -> RangeRelation<()> {
141    if t.is_invalid_set(a.get_begin(), a.get_end()) {
142        return RangeRelation::Invalid(());
143    } else if t.lt(a.get_end(), b.get_begin()) {
144        return RangeRelation::Before(());
145    } else if t.lt(b.get_end(), a.get_begin()) {
146        return RangeRelation::After(());
147    }
148
149    return RangeRelation::Overlap(());
150}
151
152/// **Range to value Conversion**
153///
154/// This method takes a [std::ops::RangeBounds] and returns the calculted values for the type.
155///
156/// For conversion of start values
157///   - [std::ops::Bound::Unbounded] becomes $t::MIN
158///   - [std::ops::Bound::Included] value is not changed
159///   - [std::ops::Bound::Excluded] value is incremented
160///
161/// For conversion of end values
162///   - [std::ops::Bound::Unbounded] becomes $t::MAX
163///   - [std::ops::Bound::Included] value is not changed
164///   - [std::ops::Bound::Excluded] value is decremented
165///
166/// See [IncDecCpCmp] for more details.
167///
168/// Example of range to number conversion.
169///
170pub fn range_bounds_to_values<T, V>(
171    range: &impl RangeBounds<T>,
172    rebound: &V,
173    cmp: &impl IncDecCpCmp<T, V>,
174) -> Option<(T, T)> {
175    if let Some(begin) = cmp.rebound_start(range.start_bound(), rebound)
176        && let Some(end) = cmp.rebound_end(range.end_bound(), rebound)
177    {
178        return Some((begin, end));
179    } else {
180        return None;
181    }
182}
183
184/// Compares range a and b and returns the **Forward Consolidation Order** [std::cmp::Ordering] value.
185///
186/// The sort order is meant to represent **Forward Consolidation Order** not tradtional range sort order.
187/// **Forward Consolidation Order** is represented as earliest largest ranges first.
188///
189/// Put another way:
190/// - GetBeginEnd.get_begin() asc
191/// - GetBeginEnd.get_end() desc
192///
193/// # Panics!
194/// If the [RangeBounds] cannot be converted to a computable range!
195pub fn sort_forward<T, V, R: RangeBounds<T>, S: RangeBounds<T>, C: IncDecCpCmp<T, V>>(
196    x: &R,
197    y: &S,
198    rebound: &V,
199    t: &C,
200) -> Ordering {
201    let a: Mrs<T> = (range_bounds_to_values(x, rebound, t)).unwrap().into();
202    let b: Mrs<T> = (range_bounds_to_values(y, rebound, t)).unwrap().into();
203    if t.lt(b.get_begin(), a.get_begin()) {
204        return Ordering::Greater;
205    } else if t.lt(a.get_begin(), b.get_begin()) {
206        return Ordering::Less;
207
208    // anything below this point both begin values are the same
209    } else if t.lt(a.get_end(), b.get_end()) {
210        return Ordering::Greater;
211    } else if t.lt(b.get_end(), a.get_end()) {
212        return Ordering::Less;
213    }
214    // if we get here, begin and end are equal
215    return Ordering::Equal;
216}
217
218/// Compares range a and b and returns the **Reverse Consolidation Order** [std::cmp::Ordering] value.
219///
220/// The sort order is meant to represent **Reverse Consolidation Order** not tradtional range sort order.
221/// **Reverse Consolidation Order** is represented as latest largest ranges first.
222///
223/// Put another way:
224/// - GetBeginEnd.get_end() desc
225/// - GetBeginEnd.get_begin() asc
226///
227/// # Panics!
228/// If the [RangeBounds] cannot be converted to a computable range!
229pub fn sort_reverse<T, V, R: RangeBounds<T>, S: RangeBounds<T>, C: IncDecCpCmp<T, V>>(
230    x: &R,
231    y: &S,
232    rebound: &V,
233    t: &C,
234) -> Ordering {
235    let a: Mrs<T> = (range_bounds_to_values(x, rebound, t)).unwrap().into();
236    let b: Mrs<T> = (range_bounds_to_values(y, rebound, t)).unwrap().into();
237    if t.lt(a.get_end(), b.get_end()) {
238        return Ordering::Greater;
239    } else if t.lt(b.get_end(), a.get_end()) {
240        return Ordering::Less;
241    } else if t.lt(b.get_begin(), a.get_begin()) {
242        return Ordering::Greater;
243    } else if t.lt(a.get_begin(), b.get_begin()) {
244        return Ordering::Less;
245    }
246
247    // anything below this point both begin values are the same
248
249    // if we get here, begin and end are equal
250    return Ordering::Equal;
251}
252
253fn contains<T, R: GetBeginEnd<T>, C: CpCmp<T>>(check: &R, value: &T, t: &C) -> bool {
254    return t.contains(check.get_begin(), check.get_end(), value);
255}
256
257pub fn reduce_next<T, C: CpCmp<T>, R: GetBeginEnd<T>>(
258    begin: &T,
259    end: &T,
260    src: &[R],
261    t: &C,
262) -> (T, T) {
263    let mut target = end;
264
265    for r in src {
266        let (start, finish) = r.to_tuple_ref();
267        if !t.overlap(begin, end, start, finish) {
268            continue;
269        }
270        let mut min = finish;
271        if t.lt(begin, start) {
272            min = start;
273        }
274        if t.lt(min, target) {
275            target = min
276        }
277    }
278    return (t.cp(begin), t.cp(target));
279}
280
281pub fn next_smallest_range<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
282    begin: &T,
283    end: &T,
284    src: &[R],
285    step: &V,
286    t: &C,
287) -> (T, T) {
288    return retool_end(reduce_next(begin, end, src, t), src, step, t);
289}
290
291/// Computes the final value from a result of [crate::reduce_next].
292pub fn retool_end<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
293    res: (T, T),
294    src: &[R],
295    step: &V,
296    t: &C,
297) -> (T, T) {
298    let (begin, end) = res;
299
300    let mut shrank = None;
301    let mut driver = &end;
302    let mut exact: usize = 0;
303    let mut min_end = None;
304    for r in src {
305        let (c, d) = r.to_tuple_ref();
306
307        if t.overlap(&begin, &end, c, d) {
308            if t.lt(&begin, c)
309                && let Some(n) = t.dec(&c, step)
310                && !t.is_invalid_set(&begin, &n)
311            {
312                match &shrank {
313                    Some(cmp) => {
314                        if t.lt(&n, cmp) {
315                            shrank = Some(n);
316                        }
317                    }
318                    None => shrank = Some(n),
319                }
320                continue;
321            }
322            exact += 1;
323            driver = d;
324            match min_end {
325                Some(n) => {
326                    if t.lt(d, n) {
327                        min_end = Some(d);
328                    }
329                }
330                None => min_end = Some(d),
331            }
332        }
333    }
334    if shrank.is_some() {
335        return (begin, shrank.unwrap());
336    } else if exact == 1 {
337        return (begin, t.cp(driver));
338    } else if let Some(n) = min_end {
339        return (begin, t.cp(n));
340    }
341    return (begin, end);
342}
343
344/// Computes the final value from a result of [crate::reduce_back].
345pub fn retool_begin<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
346    res: (T, T),
347    src: &[R],
348    step: &V,
349    t: &C,
350) -> (T, T) {
351    let (begin, end) = res;
352
353    let mut shrank = None;
354    let mut driver = &begin;
355    let mut exact: usize = 0;
356    let mut max_begin = None;
357    for r in src {
358        let (c, d) = r.to_tuple_ref();
359
360        if t.overlap(&begin, &end, c, d) {
361            if t.lt(d, &end)
362                && let Some(n) = t.inc(&d, step)
363                && !t.is_invalid_set(&n, &end)
364            {
365                match &shrank {
366                    Some(cmp) => {
367                        if t.lt(cmp, &n) {
368                            shrank = Some(n);
369                        }
370                    }
371                    None => shrank = Some(n),
372                }
373                continue;
374            }
375            exact += 1;
376            driver = c;
377            match max_begin {
378                Some(n) => {
379                    if t.lt(n, c) {
380                        max_begin = Some(c);
381                    }
382                }
383                None => max_begin = Some(c),
384            }
385        }
386    }
387    if shrank.is_some() {
388        return (shrank.unwrap(), end);
389    } else if exact == 1 {
390        return (t.cp(driver), end);
391    } else if let Some(n) = max_begin {
392        return (t.cp(n), end);
393    }
394    return (begin, end);
395}
396
397/// Given the current begin and end, returns the smallest next range from src.
398pub fn previous_smallest_range<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
399    begin: &T,
400    end: &T,
401    src: &[R],
402    step: &V,
403    t: &C,
404) -> (T, T) {
405    return retool_begin(reduce_back(begin, end, src, t), src, step, t);
406}
407
408/// Given the current begin and end, returns the smallest back range from src.
409pub fn reduce_back<T, C: CpCmp<T>, R: GetBeginEnd<T>>(
410    begin: &T,
411    end: &T,
412    src: &[R],
413    t: &C,
414) -> (T, T) {
415    let mut target = begin;
416
417    for r in src {
418        let (start, finish) = r.to_tuple_ref();
419        if !t.overlap(begin, end, start, finish) {
420            continue;
421        }
422        let mut min = start;
423        if t.lt(finish, end) {
424            min = finish;
425        }
426        if t.lt(target, min) {
427            target = min;
428        }
429    }
430
431    return (t.cp(target), t.cp(end));
432}
433
434/// Returns an [Option] wrapped tuple representing the smallest begin and largest end values found in src.
435pub fn min_max<'r, T, R: GetBeginEnd<T>, C: CpCmp<T>>(
436    src: &'r [R],
437    t: &C,
438) -> Option<(&'r T, &'r T)> {
439    let mut check: Option<(&T, &T)> = None;
440
441    for span in src {
442        let (start, finish) = span.to_tuple_ref();
443        match check {
444            Some((begin, end)) => {
445                let mut a = begin;
446                let mut z = end;
447                if t.lt(end, finish) {
448                    z = finish;
449                }
450                if t.lt(start, begin) {
451                    a = start;
452                }
453                check = Some((a, z))
454            }
455            _ => check = Some((start, finish)),
456        }
457    }
458    if let Some((begin, end)) = check {
459        return Some((begin, end));
460    }
461
462    return None;
463}
464
465/// Looks for the first most range, if found returns an Option<(T,T)>.
466pub fn first_range_begin_end<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
467    src: &[R],
468    step: &V,
469    t: &C,
470) -> Option<(T, T)> {
471    if let Some((begin, end)) = min_max(src, t) {
472        return Some(next_smallest_range(begin, end, src, step, t));
473    }
474
475    return None;
476}
477
478/// Looks for the last most range, if found returns an Option<(T,T)>.
479pub fn last_range_begin_end<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
480    src: &[R],
481    step: &V,
482    t: &C,
483) -> Option<(T, T)> {
484    let check = min_max(src, t);
485    if let Some((begin, end)) = check {
486        return Some(previous_smallest_range(begin, end, src, step, t));
487    }
488
489    return None;
490}
491
492/// Searches for the next smallest range valid range of (T,T) overlaps with begin.
493/// If no range overlaps with end, it finds the next smallest range after begin.
494/// Returns None when no matches were found.
495pub fn next_range_begin_end<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
496    begin: &T,
497    src: &[R],
498    step: &V,
499    t: &C,
500) -> Option<(T, T)> {
501    let mut target: Option<&T> = None;
502    let mut alt: Option<(&T, &T)> = None;
503    for check in src {
504        let (start, finish) = check.to_tuple_ref();
505        if contains(check, begin, t) {
506            match target {
507                Some(cmp) => {
508                    if t.lt(finish, cmp) {
509                        target = Some(finish)
510                    }
511                }
512                _ => target = Some(finish),
513            }
514        } else {
515            if t.lt(begin, start) {
516                match alt {
517                    Some((cmp, _)) => {
518                        if t.lt(start, cmp) {
519                            alt = Some((start, finish))
520                        }
521                    }
522                    _ => alt = Some((start, finish)),
523                }
524            }
525        }
526    }
527    if let Some(end) = target {
528        return Some(next_smallest_range(begin, end, src, step, t));
529    } else if let Some((begin, end)) = alt {
530        return Some(next_smallest_range(begin, end, src, step, t));
531    }
532    return None;
533}
534
535/// Searches for the previous smallest range valid range of (T,T) overlaps with end.
536/// If no range overlaps with end, it finds the previous smallest range before begin.
537/// Returns None when no matches were found.
538pub fn previous_range_begin_end<T, V, C: IncDecCpCmp<T, V>, R: GetBeginEnd<T>>(
539    end: &T,
540    src: &[R],
541    step: &V,
542    t: &C,
543) -> Option<(T, T)> {
544    let mut target: Option<&T> = None;
545    let mut alt: Option<(&T, &T)> = None;
546    let mut valid = Vec::new();
547    for check in src {
548        valid.push(check);
549        let (start, finish) = check.to_tuple_ref();
550        if contains(check, end, t) {
551            match target {
552                Some(cmp) => {
553                    if t.lt(start, cmp) {
554                        target = Some(start)
555                    }
556                }
557                _ => target = Some(start),
558            }
559        } else {
560            if t.lt(finish, end) {
561                match alt {
562                    Some((x, y)) => {
563                        let mut a = x;
564                        let mut b = y;
565                        if t.lt(y, finish) {
566                            b = finish
567                        }
568                        if t.lt(start, a) {
569                            a = start
570                        }
571                        alt = Some((a, b));
572                    }
573                    _ => alt = Some((start, finish)),
574                }
575            }
576        }
577    }
578    if let Some(begin) = target {
579        return Some(previous_smallest_range(begin, end, src, step, t));
580    } else if let Some((begin, end)) = alt {
581        return Some(previous_smallest_range(begin, end, src, step, t));
582    }
583    return None;
584}
585
586/// Given 2 instances of [GetBeginEnd] it returns a range that contains both.
587pub fn grow<
588    T,
589    Q: GetBeginEnd<T>,
590    R: GetBeginEnd<T>,
591    S: GetBeginEnd<T>,
592    C: CpCmp<T>,
593    F: GetBeginEndOption<T, Q>,
594>(
595    x: &R,
596    y: &S,
597    t: &C,
598    f: &F,
599) -> Q {
600    let a;
601    if t.lt(x.get_begin(), y.get_begin()) {
602        a = t.cp(x.get_begin())
603    } else {
604        a = t.cp(y.get_begin())
605    }
606    let z;
607    if t.lt(x.get_end(), y.get_end()) {
608        z = t.cp(y.get_end());
609    } else {
610        z = t.cp(x.get_end());
611    }
612    return f.new_range((a, z));
613}
614
615/// This function is the stateless implementation of [crate::Consolidate].
616pub fn consolidate<
617    T,
618    V,
619    R: GetBeginEnd<T>,
620    S: RangeBounds<T>,
621    C: IncDecCpCmp<T, V>,
622    F: GetBeginEndOption<T, R>,
623    I: Iterator<Item = S>,
624>(
625    last: &mut Option<(R, Vec<(usize, S)>)>,
626    iter: &mut I,
627    t: &C,
628    rebound: &V,
629    f: &F,
630    mut offset: usize,
631) -> (usize, Option<RangeRelation<(R, Vec<(usize, S)>)>>) {
632    // this value will become our next offset when we are called again!
633    for range in iter {
634        let r = range_bounds_to_values(&range, rebound, t);
635        let mut ar;
636        match r {
637            Some(src) => ar = (f.new_range(src), vec![(offset, range)]),
638            None => {
639                let a;
640                match range.start_bound() {
641                    Included(s) => a = t.cp(s),
642                    Excluded(s) => a = t.cp(s),
643                    Unbounded => a = t.min(),
644                }
645                let b;
646                match range.start_bound() {
647                    Included(s) => b = t.cp(s),
648                    Excluded(s) => b = t.cp(s),
649                    Unbounded => b = t.max(),
650                }
651                match mem::replace(last, None) {
652                    Some((good, mut list)) => {
653                        let bad = f.new_range((a, b));
654                        let r = grow(&good, &bad, t, f);
655                        list.push((offset, range));
656                        ar = (r, list);
657                    }
658                    None => ar = (f.new_range((a, b)), vec![(offset, range)]),
659                }
660                offset += 1;
661                return (offset, Some(RangeRelation::Invalid(ar)));
662            }
663        }
664
665        offset += 1;
666
667        let nv = mem::replace(last, None);
668        if let Some((src, mut list)) = nv {
669            match range_relation(&src, &ar.0, t) {
670                RangeRelation::Overlap(_) => {
671                    let nr = grow(&src, &ar.0, t, f);
672                    list.append(&mut ar.1);
673                    if t.is_invalid_set(nr.get_begin(), nr.get_end()) {
674                        *last = None;
675                        return (offset, Some(RangeRelation::Invalid((nr, list))));
676                    } else {
677                        *last = Some((nr, list));
678                    }
679                }
680                RangeRelation::Before(_) => {
681                    *last = Some(ar);
682                    return (offset, Some(RangeRelation::Before((src, list))));
683                }
684                RangeRelation::After(_) => {
685                    *last = Some(ar);
686                    return (offset, Some(RangeRelation::After((src, list))));
687                }
688                RangeRelation::Invalid(_) => {
689                    *last = Some(ar);
690                    return (offset, Some(RangeRelation::Invalid((src, list))));
691                }
692                _ => {}
693            }
694        } else {
695            *last = Some(ar);
696        }
697    }
698    if last.is_some() {
699        let res = mem::replace(last, None);
700        return (offset, Some(RangeRelation::Last(res.unwrap())));
701    }
702    return (offset, None);
703}
common_range_tools/utils.rs

common_range_tools/
utils.rs
