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: usize = slice.len();
651 let mut lo: usize = 0;
652 while lo < hi {
653 let mid: usize = lo + (hi - lo) / 2;
654 if cmp(&slice[mid]) {
655 lo = mid + 1;
656 } else {
657 hi = mid;
658 }
659 }
660 lo
661}
662