raw-btree 0.3.0

Generic B-Tree implementation.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

mod array;
use std::cmp::Ordering;

pub use array::Array;

/// Type identifier by a key.
///
/// This is implemented by [`Item`] and [`internal::Branch`].
pub trait Keyed {
	type Key;

	fn key(&self) -> &Self::Key;
}

/// Search in `sorted_slice` for the item with the nearest key smaller or equal to the given one.
///
/// `sorted_slice` is assumed to be sorted.
#[inline]
pub fn binary_search_min<T, Q: ?Sized>(
	cmp: impl Fn(&T, &Q) -> Ordering,
	sorted_slice: &[T],
	key: &Q,
) -> Option<(usize, bool)> {
	let i_ord = cmp(&sorted_slice[0], key);
	if sorted_slice.is_empty() || i_ord.is_gt() {
		None
	} else {
		let mut i = 0;
		let mut j = sorted_slice.len() - 1;

		let j_ord = cmp(&sorted_slice[j], key);
		if j_ord.is_le() {
			return Some((j, j_ord.is_eq()));
		}

		// invariants:
		// sorted_slice[i].key <= key
		// sorted_slice[j].key > key
		// j > i

		let mut eq = i_ord.is_eq();
		while !eq && j - i > 1 {
			let k = (i + j) / 2;

			let k_ord = cmp(&sorted_slice[k], key);
			if k_ord.is_gt() {
				j = k;
			// sorted_slice[k].key > key --> sorted_slice[j] > key
			} else {
				i = k;
				eq = k_ord.is_eq();
				// sorted_slice[k].key <= key --> sorted_slice[i] <= key
			}
		}

		Some((i, eq))
	}
}