Crate eytzinger[−][src]
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.”).
Usage
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));
Modules
foundation | The basic building blocks this crate is made of. |
permutation | Abstractions around applying generic permutations using generic implementations. |
Structs
PermutationGenerator | Generates a permutation that transforms a sorted array into an eytzinger array. |
Traits
SliceExt | Eytzinger extension methods for slices. |
Functions
eytzinger_search_by | Binary searches this eytzinger slice with a comparator function. |
eytzingerize | Converts a sorted array to its eytzinger representation. |