This crate implements the “eytzinger” (aka BFS) array layout where a binary search tree is stored by layer (instead of as a sorted array). This can have significant performance benefits (see Khuong, Paul-Virak, and Pat Morin. “Array layouts for comparison-based searching.”).
use eytzinger::SliceExt; let mut data = [0, 1, 2, 3, 4, 5, 6]; data.eytzingerize(&mut eytzinger::permutation::InplacePermutator); assert_eq!(data, [3, 1, 5, 0, 2, 4, 6]); assert_eq!(data.eytzinger_search(&5), Some(2)); assert_eq!(data.eytzinger_search_by(|x| x.cmp(&6)), Some(6));
The basic building blocks this crate is made of.
Abstractions around applying generic permutations using generic implementations.
Generates a permutation that transforms a sorted array into an eytzinger array.
Eytzinger extension methods for slices.
Binary searches this eytzinger slice with a comparator function.
Converts a sorted array to its eytzinger representation.