Crate eytzinger 

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_interpolative_search_by

Binary searches this eytzinger slice with a comparator function.

eytzinger_search_by

Binary searches this eytzinger slice with a comparator function.

eytzingerize

Converts a sorted array to its eytzinger representation.