datafrog/
treefrog.rs

1//! Join functionality.
2
3use super::Relation;
4
5/// Performs treefrog leapjoin using a list of leapers.
6pub(crate) fn leapjoin<'leap, Tuple: Ord, Val: Ord + 'leap, Result: Ord>(
7    source: &[Tuple],
8    mut leapers: impl Leapers<'leap, Tuple, Val>,
9    mut logic: impl FnMut(&Tuple, &Val) -> Result,
10) -> Relation<Result> {
11    let mut result = Vec::new(); // temp output storage.
12    let mut values = Vec::new(); // temp value storage.
13
14    for tuple in source {
15        // Determine which leaper would propose the fewest values.
16        let mut min_index = usize::max_value();
17        let mut min_count = usize::max_value();
18        leapers.for_each_count(tuple, |index, count| {
19            if min_count > count {
20                min_count = count;
21                min_index = index;
22            }
23        });
24
25        // We had best have at least one relation restricting values.
26        assert!(min_count < usize::max_value());
27
28        // If there are values to propose:
29        if min_count > 0 {
30            // Push the values that `min_index` "proposes" into `values`.
31            leapers.propose(tuple, min_index, &mut values);
32
33            // Give other leapers a chance to remove values from
34            // anti-joins or filters.
35            leapers.intersect(tuple, min_index, &mut values);
36
37            // Push remaining items into result.
38            for val in values.drain(..) {
39                result.push(logic(tuple, val));
40            }
41        }
42    }
43
44    Relation::from_vec(result)
45}
46
47/// Implemented for a tuple of leapers
48pub trait Leapers<'leap, Tuple, Val> {
49    /// Internal method:
50    fn for_each_count(&mut self, tuple: &Tuple, op: impl FnMut(usize, usize));
51
52    /// Internal method:
53    fn propose(&mut self, tuple: &Tuple, min_index: usize, values: &mut Vec<&'leap Val>);
54
55    /// Internal method:
56    fn intersect(&mut self, tuple: &Tuple, min_index: usize, values: &mut Vec<&'leap Val>);
57}
58
59macro_rules! tuple_leapers {
60    ($($Ty:ident)*) => {
61        #[allow(unused_assignments, non_snake_case)]
62        impl<'leap, Tuple, Val, $($Ty),*> Leapers<'leap, Tuple, Val> for ($($Ty,)*)
63        where
64            $($Ty: Leaper<'leap, Tuple, Val>,)*
65        {
66            fn for_each_count(&mut self, tuple: &Tuple, mut op: impl FnMut(usize, usize)) {
67                let ($($Ty,)*) = self;
68                let mut index = 0;
69                $(
70                    let count = $Ty.count(tuple);
71                    op(index, count);
72                    index += 1;
73                )*
74            }
75
76            fn propose(&mut self, tuple: &Tuple, min_index: usize, values: &mut Vec<&'leap Val>) {
77                let ($($Ty,)*) = self;
78                let mut index = 0;
79                $(
80                    if min_index == index {
81                        return $Ty.propose(tuple, values);
82                    }
83                    index += 1;
84                )*
85                    panic!("no match found for min_index={}", min_index);
86            }
87
88            fn intersect(&mut self, tuple: &Tuple, min_index: usize, values: &mut Vec<&'leap Val>) {
89                let ($($Ty,)*) = self;
90                let mut index = 0;
91                $(
92                    if min_index != index {
93                        $Ty.intersect(tuple, values);
94                    }
95                    index += 1;
96                )*
97            }
98        }
99    }
100}
101
102tuple_leapers!(A B);
103tuple_leapers!(A B C);
104tuple_leapers!(A B C D);
105tuple_leapers!(A B C D E);
106tuple_leapers!(A B C D E F);
107tuple_leapers!(A B C D E F G);
108
109/// Methods to support treefrog leapjoin.
110pub trait Leaper<'leap, Tuple, Val> {
111    /// Estimates the number of proposed values.
112    fn count(&mut self, prefix: &Tuple) -> usize;
113    /// Populates `values` with proposed values.
114    fn propose(&mut self, prefix: &Tuple, values: &mut Vec<&'leap Val>);
115    /// Restricts `values` to proposed values.
116    fn intersect(&mut self, prefix: &Tuple, values: &mut Vec<&'leap Val>);
117}
118
119pub(crate) mod filters {
120    use super::Leaper;
121    use super::Leapers;
122
123    /// A treefrog leaper that tests each of the tuples from the main
124    /// input (the "prefix"). Use like `PrefixFilter::from(|tuple|
125    /// ...)`; if the closure returns true, then the tuple is
126    /// retained, else it will be ignored. This leaper can be used in
127    /// isolation in which case it just acts like a filter on the
128    /// input (the "proposed value" will be `()` type).
129    pub struct PrefixFilter<Tuple, Func: Fn(&Tuple) -> bool> {
130        phantom: ::std::marker::PhantomData<Tuple>,
131        predicate: Func,
132    }
133
134    impl<'leap, Tuple, Func> PrefixFilter<Tuple, Func>
135    where
136        Func: Fn(&Tuple) -> bool,
137    {
138        /// Creates a new filter based on the prefix
139        pub fn from(predicate: Func) -> Self {
140            PrefixFilter {
141                phantom: ::std::marker::PhantomData,
142                predicate,
143            }
144        }
145    }
146
147    impl<'leap, Tuple, Val, Func> Leaper<'leap, Tuple, Val> for PrefixFilter<Tuple, Func>
148    where
149        Func: Fn(&Tuple) -> bool,
150    {
151        /// Estimates the number of proposed values.
152        fn count(&mut self, prefix: &Tuple) -> usize {
153            if (self.predicate)(prefix) {
154                usize::max_value()
155            } else {
156                0
157            }
158        }
159        /// Populates `values` with proposed values.
160        fn propose(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val>) {
161            panic!("PrefixFilter::propose(): variable apparently unbound");
162        }
163        /// Restricts `values` to proposed values.
164        fn intersect(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val>) {
165            // We can only be here if we returned max_value() above.
166        }
167    }
168
169    impl<'leap, Tuple, Func> Leapers<'leap, Tuple, ()> for PrefixFilter<Tuple, Func>
170    where
171        Func: Fn(&Tuple) -> bool,
172    {
173        fn for_each_count(&mut self, tuple: &Tuple, mut op: impl FnMut(usize, usize)) {
174            if <Self as Leaper<'_, Tuple, ()>>::count(self, tuple) == 0 {
175                op(0, 0)
176            } else {
177                // we will "propose" the `()` value if the predicate applies
178                op(0, 1)
179            }
180        }
181
182        fn propose(&mut self, _: &Tuple, min_index: usize, values: &mut Vec<&'leap ()>) {
183            assert_eq!(min_index, 0);
184            values.push(&());
185        }
186
187        fn intersect(&mut self, _: &Tuple, min_index: usize, values: &mut Vec<&'leap ()>) {
188            assert_eq!(min_index, 0);
189            assert_eq!(values.len(), 1);
190        }
191    }
192
193    /// A treefrog leaper based on a predicate of prefix and value.
194    /// Use like `ValueFilter::from(|tuple, value| ...)`. The closure
195    /// should return true if `value` ought to be retained. The
196    /// `value` will be a value proposed elsewhere by an `extend_with`
197    /// leaper.
198    ///
199    /// This leaper cannot be used in isolation, it must be combined
200    /// with other leapers.
201    pub struct ValueFilter<Tuple, Val, Func: Fn(&Tuple, &Val) -> bool> {
202        phantom: ::std::marker::PhantomData<(Tuple, Val)>,
203        predicate: Func,
204    }
205
206    impl<'leap, Tuple, Val, Func> ValueFilter<Tuple, Val, Func>
207    where
208        Func: Fn(&Tuple, &Val) -> bool,
209    {
210        /// Creates a new filter based on the prefix
211        pub fn from(predicate: Func) -> Self {
212            ValueFilter {
213                phantom: ::std::marker::PhantomData,
214                predicate,
215            }
216        }
217    }
218
219    impl<'leap, Tuple, Val, Func> Leaper<'leap, Tuple, Val> for ValueFilter<Tuple, Val, Func>
220    where
221        Func: Fn(&Tuple, &Val) -> bool,
222    {
223        /// Estimates the number of proposed values.
224        fn count(&mut self, _prefix: &Tuple) -> usize {
225            usize::max_value()
226        }
227        /// Populates `values` with proposed values.
228        fn propose(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val>) {
229            panic!("PrefixFilter::propose(): variable apparently unbound");
230        }
231        /// Restricts `values` to proposed values.
232        fn intersect(&mut self, prefix: &Tuple, values: &mut Vec<&'leap Val>) {
233            values.retain(|val| (self.predicate)(prefix, val));
234        }
235    }
236
237}
238
239/// Extension method for relations.
240pub trait RelationLeaper<Key: Ord, Val: Ord> {
241    /// Extend with `Val` using the elements of the relation.
242    fn extend_with<'leap, Tuple: Ord, Func: Fn(&Tuple) -> Key>(
243        &'leap self,
244        key_func: Func,
245    ) -> extend_with::ExtendWith<'leap, Key, Val, Tuple, Func>
246    where
247        Key: 'leap,
248        Val: 'leap;
249    /// Extend with `Val` using the complement of the relation.
250    fn extend_anti<'leap, Tuple: Ord, Func: Fn(&Tuple) -> Key>(
251        &'leap self,
252        key_func: Func,
253    ) -> extend_anti::ExtendAnti<'leap, Key, Val, Tuple, Func>
254    where
255        Key: 'leap,
256        Val: 'leap;
257    /// Extend with any value if tuple is present in relation.
258    fn filter_with<'leap, Tuple: Ord, Func: Fn(&Tuple) -> (Key, Val)>(
259        &'leap self,
260        key_func: Func,
261    ) -> filter_with::FilterWith<'leap, Key, Val, Tuple, Func>
262    where
263        Key: 'leap,
264        Val: 'leap;
265    /// Extend with any value if tuple is absent from relation.
266    fn filter_anti<'leap, Tuple: Ord, Func: Fn(&Tuple) -> (Key, Val)>(
267        &'leap self,
268        key_func: Func,
269    ) -> filter_anti::FilterAnti<'leap, Key, Val, Tuple, Func>
270    where
271        Key: 'leap,
272        Val: 'leap;
273}
274
275impl<Key: Ord, Val: Ord> RelationLeaper<Key, Val> for Relation<(Key, Val)> {
276    fn extend_with<'leap, Tuple: Ord, Func: Fn(&Tuple) -> Key>(
277        &'leap self,
278        key_func: Func,
279    ) -> extend_with::ExtendWith<'leap, Key, Val, Tuple, Func>
280    where
281        Key: 'leap,
282        Val: 'leap,
283    {
284        extend_with::ExtendWith::from(self, key_func)
285    }
286    fn extend_anti<'leap, Tuple: Ord, Func: Fn(&Tuple) -> Key>(
287        &'leap self,
288        key_func: Func,
289    ) -> extend_anti::ExtendAnti<'leap, Key, Val, Tuple, Func>
290    where
291        Key: 'leap,
292        Val: 'leap,
293    {
294        extend_anti::ExtendAnti::from(self, key_func)
295    }
296    fn filter_with<'leap, Tuple: Ord, Func: Fn(&Tuple) -> (Key, Val)>(
297        &'leap self,
298        key_func: Func,
299    ) -> filter_with::FilterWith<'leap, Key, Val, Tuple, Func>
300    where
301        Key: 'leap,
302        Val: 'leap,
303    {
304        filter_with::FilterWith::from(self, key_func)
305    }
306    fn filter_anti<'leap, Tuple: Ord, Func: Fn(&Tuple) -> (Key, Val)>(
307        &'leap self,
308        key_func: Func,
309    ) -> filter_anti::FilterAnti<'leap, Key, Val, Tuple, Func>
310    where
311        Key: 'leap,
312        Val: 'leap,
313    {
314        filter_anti::FilterAnti::from(self, key_func)
315    }
316}
317
318pub(crate) mod extend_with {
319    use super::{binary_search, Leaper, Leapers, Relation};
320    use crate::join::gallop;
321
322    /// Wraps a Relation<Tuple> as a leaper.
323    pub struct ExtendWith<'leap, Key, Val, Tuple, Func>
324    where
325        Key: Ord + 'leap,
326        Val: Ord + 'leap,
327        Tuple: Ord,
328        Func: Fn(&Tuple) -> Key,
329    {
330        relation: &'leap Relation<(Key, Val)>,
331        start: usize,
332        end: usize,
333        key_func: Func,
334        phantom: ::std::marker::PhantomData<Tuple>,
335    }
336
337    impl<'leap, Key, Val, Tuple, Func> ExtendWith<'leap, Key, Val, Tuple, Func>
338    where
339        Key: Ord + 'leap,
340        Val: Ord + 'leap,
341        Tuple: Ord,
342        Func: Fn(&Tuple) -> Key,
343    {
344        /// Constructs a ExtendWith from a relation and key and value function.
345        pub fn from(relation: &'leap Relation<(Key, Val)>, key_func: Func) -> Self {
346            ExtendWith {
347                relation,
348                start: 0,
349                end: 0,
350                key_func,
351                phantom: ::std::marker::PhantomData,
352            }
353        }
354    }
355
356    impl<'leap, Key, Val, Tuple, Func> Leaper<'leap, Tuple, Val>
357        for ExtendWith<'leap, Key, Val, Tuple, Func>
358    where
359        Key: Ord + 'leap,
360        Val: Ord + 'leap,
361        Tuple: Ord,
362        Func: Fn(&Tuple) -> Key,
363    {
364        fn count(&mut self, prefix: &Tuple) -> usize {
365            let key = (self.key_func)(prefix);
366            self.start = binary_search(&self.relation[..], |x| &x.0 < &key);
367            let slice1 = &self.relation[self.start..];
368            let slice2 = gallop(slice1, |x| &x.0 <= &key);
369            self.end = self.relation.len() - slice2.len();
370            slice1.len() - slice2.len()
371        }
372        fn propose(&mut self, _prefix: &Tuple, values: &mut Vec<&'leap Val>) {
373            let slice = &self.relation[self.start..self.end];
374            values.extend(slice.iter().map(|&(_, ref val)| val));
375        }
376        fn intersect(&mut self, _prefix: &Tuple, values: &mut Vec<&'leap Val>) {
377            let mut slice = &self.relation[self.start..self.end];
378            values.retain(|v| {
379                slice = gallop(slice, |kv| &kv.1 < v);
380                slice.get(0).map(|kv| &kv.1) == Some(v)
381            });
382        }
383    }
384
385    impl<'leap, Key, Val, Tuple, Func> Leapers<'leap, Tuple, Val>
386        for ExtendWith<'leap, Key, Val, Tuple, Func>
387    where
388        Key: Ord + 'leap,
389        Val: Ord + 'leap,
390        Tuple: Ord,
391        Func: Fn(&Tuple) -> Key,
392    {
393        fn for_each_count(&mut self, tuple: &Tuple, mut op: impl FnMut(usize, usize)) {
394            op(0, self.count(tuple))
395        }
396
397        fn propose(&mut self, tuple: &Tuple, min_index: usize, values: &mut Vec<&'leap Val>) {
398            assert_eq!(min_index, 0);
399            Leaper::propose(self, tuple, values);
400        }
401
402        fn intersect(&mut self, _: &Tuple, min_index: usize, _: &mut Vec<&'leap Val>) {
403            assert_eq!(min_index, 0);
404        }
405    }
406}
407
408pub(crate) mod extend_anti {
409    use super::{binary_search, Leaper, Relation};
410    use crate::join::gallop;
411
412    /// Wraps a Relation<Tuple> as a leaper.
413    pub struct ExtendAnti<'leap, Key, Val, Tuple, Func>
414    where
415        Key: Ord + 'leap,
416        Val: Ord + 'leap,
417        Tuple: Ord,
418        Func: Fn(&Tuple) -> Key,
419    {
420        relation: &'leap Relation<(Key, Val)>,
421        key_func: Func,
422        phantom: ::std::marker::PhantomData<Tuple>,
423    }
424
425    impl<'leap, Key, Val, Tuple, Func> ExtendAnti<'leap, Key, Val, Tuple, Func>
426    where
427        Key: Ord + 'leap,
428        Val: Ord + 'leap,
429        Tuple: Ord,
430        Func: Fn(&Tuple) -> Key,
431    {
432        /// Constructs a ExtendAnti from a relation and key and value function.
433        pub fn from(relation: &'leap Relation<(Key, Val)>, key_func: Func) -> Self {
434            ExtendAnti {
435                relation,
436                key_func,
437                phantom: ::std::marker::PhantomData,
438            }
439        }
440    }
441
442    impl<'leap, Key: Ord, Val: Ord + 'leap, Tuple: Ord, Func> Leaper<'leap, Tuple, Val>
443        for ExtendAnti<'leap, Key, Val, Tuple, Func>
444    where
445        Key: Ord + 'leap,
446        Val: Ord + 'leap,
447        Tuple: Ord,
448        Func: Fn(&Tuple) -> Key,
449    {
450        fn count(&mut self, _prefix: &Tuple) -> usize {
451            usize::max_value()
452        }
453        fn propose(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val>) {
454            panic!("ExtendAnti::propose(): variable apparently unbound.");
455        }
456        fn intersect(&mut self, prefix: &Tuple, values: &mut Vec<&'leap Val>) {
457            let key = (self.key_func)(prefix);
458            let start = binary_search(&self.relation[..], |x| &x.0 < &key);
459            let slice1 = &self.relation[start..];
460            let slice2 = gallop(slice1, |x| &x.0 <= &key);
461            let mut slice = &slice1[..(slice1.len() - slice2.len())];
462            if !slice.is_empty() {
463                values.retain(|v| {
464                    slice = gallop(slice, |kv| &kv.1 < v);
465                    slice.get(0).map(|kv| &kv.1) != Some(v)
466                });
467            }
468        }
469    }
470}
471
472pub(crate) mod filter_with {
473
474    use super::{Leaper, Leapers, Relation};
475
476    /// Wraps a Relation<Tuple> as a leaper.
477    pub struct FilterWith<'leap, Key, Val, Tuple, Func>
478    where
479        Key: Ord + 'leap,
480        Val: Ord + 'leap,
481        Tuple: Ord,
482        Func: Fn(&Tuple) -> (Key, Val),
483    {
484        relation: &'leap Relation<(Key, Val)>,
485        key_func: Func,
486        phantom: ::std::marker::PhantomData<Tuple>,
487    }
488
489    impl<'leap, Key, Val, Tuple, Func> FilterWith<'leap, Key, Val, Tuple, Func>
490    where
491        Key: Ord + 'leap,
492        Val: Ord + 'leap,
493        Tuple: Ord,
494        Func: Fn(&Tuple) -> (Key, Val),
495    {
496        /// Constructs a FilterWith from a relation and key and value function.
497        pub fn from(relation: &'leap Relation<(Key, Val)>, key_func: Func) -> Self {
498            FilterWith {
499                relation,
500                key_func,
501                phantom: ::std::marker::PhantomData,
502            }
503        }
504    }
505
506    impl<'leap, Key, Val, Val2, Tuple, Func> Leaper<'leap, Tuple, Val2>
507        for FilterWith<'leap, Key, Val, Tuple, Func>
508    where
509        Key: Ord + 'leap,
510        Val: Ord + 'leap,
511        Tuple: Ord,
512        Func: Fn(&Tuple) -> (Key, Val),
513    {
514        fn count(&mut self, prefix: &Tuple) -> usize {
515            let key_val = (self.key_func)(prefix);
516            if self.relation.binary_search(&key_val).is_ok() {
517                usize::max_value()
518            } else {
519                0
520            }
521        }
522        fn propose(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val2>) {
523            panic!("FilterWith::propose(): variable apparently unbound.");
524        }
525        fn intersect(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val2>) {
526            // Only here because we didn't return zero above, right?
527        }
528    }
529
530    impl<'leap, Key, Val, Tuple, Func> Leapers<'leap, Tuple, ()>
531        for FilterWith<'leap, Key, Val, Tuple, Func>
532    where
533        Key: Ord + 'leap,
534        Val: Ord + 'leap,
535        Tuple: Ord,
536        Func: Fn(&Tuple) -> (Key, Val),
537    {
538        fn for_each_count(&mut self, tuple: &Tuple, mut op: impl FnMut(usize, usize)) {
539            if <Self as Leaper<Tuple, ()>>::count(self, tuple) == 0 {
540                op(0, 0)
541            } else {
542                op(0, 1)
543            }
544        }
545
546        fn propose(&mut self, _: &Tuple, min_index: usize, values: &mut Vec<&'leap ()>) {
547            assert_eq!(min_index, 0);
548            values.push(&());
549        }
550
551        fn intersect(&mut self, _: &Tuple, min_index: usize, values: &mut Vec<&'leap ()>) {
552            assert_eq!(min_index, 0);
553            assert_eq!(values.len(), 1);
554        }
555    }
556}
557
558pub(crate) mod filter_anti {
559
560    use super::{Leaper, Leapers, Relation};
561
562    /// Wraps a Relation<Tuple> as a leaper.
563    pub struct FilterAnti<'leap, Key, Val, Tuple, Func>
564    where
565        Key: Ord + 'leap,
566        Val: Ord + 'leap,
567        Tuple: Ord,
568        Func: Fn(&Tuple) -> (Key, Val),
569    {
570        relation: &'leap Relation<(Key, Val)>,
571        key_func: Func,
572        phantom: ::std::marker::PhantomData<Tuple>,
573    }
574
575    impl<'leap, Key, Val, Tuple, Func> FilterAnti<'leap, Key, Val, Tuple, Func>
576    where
577        Key: Ord + 'leap,
578        Val: Ord + 'leap,
579        Tuple: Ord,
580        Func: Fn(&Tuple) -> (Key, Val),
581    {
582        /// Constructs a FilterAnti from a relation and key and value function.
583        pub fn from(relation: &'leap Relation<(Key, Val)>, key_func: Func) -> Self {
584            FilterAnti {
585                relation,
586                key_func,
587                phantom: ::std::marker::PhantomData,
588            }
589        }
590    }
591
592    impl<'leap, Key: Ord, Val: Ord + 'leap, Val2, Tuple: Ord, Func> Leaper<'leap, Tuple, Val2>
593        for FilterAnti<'leap, Key, Val, Tuple, Func>
594    where
595        Key: Ord + 'leap,
596        Val: Ord + 'leap,
597        Tuple: Ord,
598        Func: Fn(&Tuple) -> (Key, Val),
599    {
600        fn count(&mut self, prefix: &Tuple) -> usize {
601            let key_val = (self.key_func)(prefix);
602            if self.relation.binary_search(&key_val).is_ok() {
603                0
604            } else {
605                usize::max_value()
606            }
607        }
608        fn propose(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val2>) {
609            panic!("FilterAnti::propose(): variable apparently unbound.");
610        }
611        fn intersect(&mut self, _prefix: &Tuple, _values: &mut Vec<&'leap Val2>) {
612            // Only here because we didn't return zero above, right?
613        }
614    }
615
616    impl<'leap, Key, Val, Tuple, Func> Leapers<'leap, Tuple, ()>
617        for FilterAnti<'leap, Key, Val, Tuple, Func>
618    where
619        Key: Ord + 'leap,
620        Val: Ord + 'leap,
621        Tuple: Ord,
622        Func: Fn(&Tuple) -> (Key, Val),
623    {
624        fn for_each_count(&mut self, tuple: &Tuple, mut op: impl FnMut(usize, usize)) {
625            if <Self as Leaper<Tuple, ()>>::count(self, tuple) == 0 {
626                op(0, 0)
627            } else {
628                op(0, 1)
629            }
630        }
631
632        fn propose(&mut self, _: &Tuple, min_index: usize, values: &mut Vec<&'leap ()>) {
633            // We only get here if `tuple` is *not* a member of `self.relation`
634            assert_eq!(min_index, 0);
635            values.push(&());
636        }
637
638        fn intersect(&mut self, _: &Tuple, min_index: usize, values: &mut Vec<&'leap ()>) {
639            // We only get here if `tuple` is not a member of `self.relation`
640            assert_eq!(min_index, 0);
641            assert_eq!(values.len(), 1);
642        }
643    }
644}
645
646fn binary_search<T>(slice: &[T], mut cmp: impl FnMut(&T) -> bool) -> usize {
647    // we maintain the invariant that `lo` many elements of `slice` satisfy `cmp`.
648    // `hi` is maintained at the first element we know does not satisfy `cmp`.
649
650    let mut hi = slice.len();
651    let mut lo = 0;
652    while lo < hi {
653        let mid = lo + (hi - lo) / 2;
654        if cmp(&slice[mid]) {
655            lo = mid + 1;
656        } else {
657            hi = mid;
658        }
659    }
660    lo
661}
datafrog/treefrog.rs

datafrog/
treefrog.rs
