Eytzinger

https://docs.rs/eytzinger/1.1.2/
Admin
This crate implements the "eytzinger" (aka BFS) array layout where a binary search tree is stored by...
Tokens:34,509
Snippets:330
Trust Score:9.1
Update:3 months ago
Show doc for...
Tokens:
Raw
### Eytzinger Transformation and Search Example

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Demonstrates how to use the `eytzingerize` method to transform a slice into the Eytzinger layout and how to perform searches using `eytzinger_search` and `eytzinger_search_by`.

```APIDOC
## Usage

```rust
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));
```
```

--------------------------------

### Step by in PermutationGenerator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator starting at the same point, but stepping by the given amount at each iteration. This allows skipping permutations.

```rust
fn step_by(self, step: usize) -> StepBy<Self>
```

--------------------------------

### impl Any for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `type_id` method to get the `TypeId` of the type.

```APIDOC
## fn type_id(&self) -> TypeId

Gets the `TypeId` of `self`.
```

--------------------------------

### PermutationGenerator::iterable

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Get an iterator for the permutation. This may be more efficient than indexing a counter.

```APIDOC
## PermutationGenerator::iterable

### Description
Get an iterator for the permutation. This may be more efficient than indexing a counter.

### Method
`iterable(&self) -> PermutationGenerator`
```

--------------------------------

### take

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator that yields the first `n` elements.

```APIDOC
## take

### Description
Creates an iterator that yields the first `n` elements, or fewer if the underlying iterator ends sooner.

### Signature
`fn take(self, n: usize) -> Take<Self>`

### Type Parameters
- `Self`: Must implement `Sized`.

### Parameters
- `n` (usize): The maximum number of elements to yield.
```

--------------------------------

### Get nth item from PermutationGenerator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Returns the nth element of the iterator. This method consumes elements up to n.

```rust
fn nth(&mut self, n: usize) -> Option<Self::Item>
```

--------------------------------

### Simple Heap Permutation

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Shows how to use `HeapPermutator` for permuting data. Requires the 'heap-permutator' feature.

```rust
fn simple_heap_permutation() {
        let permutation: &[usize] = &[4, 2, 3, 0, 1];
        let mut data = [1, 2, 3, 4, 5];
        HeapPermutator::default().permute(&mut data, &permutation);
        assert_eq!(data, [5, 3, 4, 1, 2]);
    }
```

--------------------------------

### Permutation Trait - Iterable Method

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/trait.Permutation.html

Provides a method to get an iterator over the permutation. This can be more efficient than repeated indexing.

```rust
fn iterable(&self) -> Self::Iter;
```

--------------------------------

### impl CloneToUninit for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `clone_to_uninit` method for nightly-only experimental cloning to uninitialized memory.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

Performs copy-assignment from `self` to `dest`. This is a nightly-only experimental API.
```

--------------------------------

### Get size hint for PermutationGenerator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Returns the bounds on the remaining length of the iterator. This is part of the Iterator trait implementation.

```rust
fn size_hint(&self) -> (usize, Option<usize>)
```

--------------------------------

### Using eytzinger_search_by for Searching

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/fn.eytzinger_search_by.html

Demonstrates how to use eytzinger_search_by with different target values. Ensure the comparator function is consistent with the slice's sort order.

```rust
use eytzinger::eytzinger_search_by;
let s = [3, 1, 5, 0, 2, 4, 6];
assert_eq!(eytzinger_search_by(&s, |x| x.cmp(&3)), Some(0));
assert_eq!(eytzinger_search_by(&s, |x| x.cmp(&5)), Some(2));
assert_eq!(eytzinger_search_by(&s, |x| x.cmp(&6)), Some(6));
assert_eq!(eytzinger_search_by(&s, |x| x.cmp(&7)), None);

```

--------------------------------

### Get next item from PermutationGenerator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Advances the iterator and returns the next value. This is the core method for iterating through permutations.

```rust
fn next(&mut self) -> Option<usize>
```

--------------------------------

### by_ref

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates a reference adapter for the iterator.

```APIDOC
## by_ref

### Description
Creates a “by reference” adapter for this instance of `Iterator`.

### Signature
`fn by_ref(&mut self) -> &mut Self`

### Type Parameters
- `Self`: Must implement `Sized`.
```

--------------------------------

### Simple Heap Copy Permutation

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Illustrates permutation using `HeapCopyPermutator`.

```rust
fn simple_heap_copy_permutation() {
        let permutation: &[usize] = &[4, 2, 3, 0, 1];
        let mut data = [1, 2, 3, 4, 5];
        HeapCopyPermutator::default().permute(&mut data, &permutation);
        assert_eq!(data, [5, 3, 4, 1, 2]);
    }
```

--------------------------------

### Get remaining length of PermutationGenerator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Returns the exact remaining length of the iterator. This is part of the ExactSizeIterator trait implementation.

```rust
fn len(&self) -> usize
```

--------------------------------

### Simple Heap Permutation Sparse

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Demonstrates permutation using `SparseHeapPermutator`. Requires the 'heap-permutator-sparse' feature.

```rust
fn simple_heap_permutation_sparse() {
        let permutation: &[usize] = &[4, 2, 3, 0, 1];
        let mut data = [1, 2, 3, 4, 5];
        SparseHeapPermutator::default().permute(&mut data, &permutation);
        assert_eq!(data, [5, 3, 4, 1, 2]);
    }
```

--------------------------------

### Get last item from PermutationGenerator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Consumes the iterator, returning the last element. This is useful when only the final permutation index is needed.

```rust
fn last(self) -> Option<Self::Item>
```

--------------------------------

### Simple In-place Permutation

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Demonstrates how to use `InplacePermutator` to permute data according to a given permutation slice.

```rust
fn simple_inplace_permutation() {
        let permutation: &[usize] = &[4, 2, 3, 0, 1];
        let mut data = [1, 2, 3, 4, 5];
        InplacePermutator.permute(&mut data, &permutation);
        assert_eq!(data, [5, 3, 4, 1, 2]);
    }
```

--------------------------------

### Eytzingerize and Search Slice

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/index.html

Demonstrates how to convert a sorted slice into its eytzinger representation and then perform searches on it. Requires the `SliceExt` trait.

```rust
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));
```

--------------------------------

### Get Permutation Element Function Signature

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/foundation/fn.get_permutation_element.html

This is the function signature for `get_permutation_element`. It takes two `usize` arguments, `n` for the array size and `i` for the index in the eytzinger array, and returns a `usize` representing the index in the sorted array.

```rust
pub fn get_permutation_element(n: usize, i: usize) -> usize
```

--------------------------------

### Heap Permutation Quickcheck

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Tests the `HeapPermutator` with QuickCheck. Requires the 'heap-permutator' feature.

```rust
fn heap_permutation(junk: Vec<usize>) -> bool {
            test_permutation::<HeapPermutator>(junk)
        }
```

--------------------------------

### CloneToUninit Trait Implementation (Nightly)

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.StackCopyPermutator.html

Implements the nightly-only experimental API clone_to_uninit for copying data to uninitialized memory.

```rust
unsafe fn clone_to_uninit(&self, dest: *mut u8)
```

--------------------------------

### Interpolative Search with Floating-Point Comparison

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/fn.eytzinger_interpolative_search_by.html

Illustrates interpolative search with floating-point numbers, requiring careful handling of potential `None` results from `partial_cmp`.

```rust
use eytzinger::eytzinger_interpolative_search_by;
let s = [3, 1, 5, 0, 2, 4, 6];
assert_eq!(eytzinger_interpolative_search_by(&s, |x| (*x as f32).partial_cmp(&3.5).unwrap()), (Some(0_usize), Some(5_usize)));
```

--------------------------------

### impl From<T> for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `from` method, which returns the argument unchanged.

```APIDOC
## fn from(t: T) -> T

Returns the argument unchanged.
```

--------------------------------

### Implement From Trait

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.SparseHeapPermutator.html

Allows conversion into the same type. This is a trivial blanket implementation.

```rust
fn from(t: T) -> T
```

--------------------------------

### Stack Copy Permutation Quickcheck

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Tests the `StackCopyPermutator` using QuickCheck, ensuring it correctly permutes data.

```rust
fn stack_permutation(junk: Vec<usize>) -> bool {
            test_permutation::<StackCopyPermutator>(junk)
        }
```

--------------------------------

### Heap Copy Permutation Quickcheck

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Verifies the `HeapCopyPermutator`'s functionality using QuickCheck.

```rust
fn heap_copy_permutation(junk: Vec<usize>) -> bool {
            test_permutation::<HeapCopyPermutator<_>>(junk)
        }
```

--------------------------------

### Eytzinger Search (Branchless)

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

This branchless implementation is optimized for performance by avoiding conditional jumps, making it suitable for modern CPUs with efficient branch prediction.

```rust
#[inline]
#[cfg(feature = "branchless")]
fn eytzinger_search_by_impl<'a, T: 'a, F>(data: &'a [T], mut f: F) -> Option<usize>
where
    F: FnMut(&'a T) -> Ordering,
{
    let mut i = 0;
    while i < data.len() {
        let v = &data[i]; // this range check is optimized out :D
        i = match f(v) {
            Ordering::Greater | Ordering::Equal => 2 * i + 1,
            Ordering::Less => 2 * i + 2,
        };
    }

    // magic from the paper to fix up the (incomplete) final tree layer
    // (only difference is that we recheck f() because this is exact search)
    let p = i + 1;
    let j = p >> (1 + (!p).trailing_zeros());
    if j != 0 && (f(&data[j - 1]) == Ordering::Equal) {
        Some(j - 1)
    } else {
        None
    }
}
```

--------------------------------

### impl TryInto<U> for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `try_into` method for fallible conversions.

```APIDOC
## type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.

## fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
```

--------------------------------

### In-place Permutation Quickcheck

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Uses QuickCheck to test the `InplacePermutator` by verifying that applying a generated permutation to a sequence results in the correct permuted sequence.

```rust
fn inplace_permutation(junk: Vec<usize>) -> bool {
            test_permutation::<InplacePermutator>(junk)
        }
```

--------------------------------

### Heap Permutation Sparse Quickcheck

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Tests the `SparseHeapPermutator` using QuickCheck. Requires the 'heap-permutator-sparse' feature.

```rust
fn heap_permutation_sparse(junk: Vec<usize>) -> bool {
            test_permutation::<SparseHeapPermutator>(junk)
        }
```

--------------------------------

### Sequence for Understanding get_permutation_element_by_node

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/foundation/fn.get_permutation_element_by_node.html

This sequence is provided as a hint for understanding the underlying logic of the `get_permutation_element_by_node` function. It relates to the mapping between sorted and eytzinger arrays.

```plaintext
a_n = (2n - 2^floor(log2(2n)) + 1) / 2^floor(log2(2n))
(1/2, 1/4, 3/4, 1/8, 3/8, 5/8, 7/8, 1/16, 3/16, 5/16, 7/16, 9/16, 11/16, 13/16, 15/16, ...)
```

--------------------------------

### Integer Arithmetic Derivation for get_permutation_element_by_node

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/foundation/fn.get_permutation_element_by_node.html

This shows the derivation of the formula using integer arithmetic, specifically how `k` and `zk` are represented.

```plaintext
Because this is integer math: `k = zk * 2^-ipk` And because we only care about certain values of zk: `zk = li * 2 + 1`
```

--------------------------------

### Eytzinger Search (Branching)

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

This implementation uses conditional branching to navigate the Eytzinger data structure. It's suitable when branch prediction might not be optimal or for simpler logic.

```rust
#[cfg(not(feature = "branchless"))]
fn eytzinger_search_by_impl<'a, T: 'a, F>(data: &'a [T], mut f: F) -> Option<usize>
where
    F: FnMut(&'a T) -> Ordering,
{
    let mut i = 0;
    loop {
        match data.get(i) {
            Some(ref v) => {
                match f(v) {
                    Ordering::Equal => return Some(i),
                    o => {
                        // I was hoping the optimizer could handle this but it can't
                        // So here goes the evil hack: Ordering is -1/0/1
                        // So we use this dirty trick to map this to +2/X/+1
                        let o = o as usize;
                        let o = (o >> 1) & 1;
                        i = 2 * i + 1 + o;
                    }
                };
            }
            None => return None,
        }
    }
}
```

--------------------------------

### partition

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Consumes an iterator and partitions its elements into two collections based on a predicate.

```APIDOC
## partition

### Description
Consumes an iterator, creating two collections from it.

### Signature
`fn partition<B, F>(self, f: F) -> (B, B)`

### Type Parameters
- `Self`: Must implement `Sized`.
- `B`: The type of the collections, must implement `Default + Extend<Self::Item>`.
- `F`: A closure `FnMut(&Self::Item) -> bool`.
```

--------------------------------

### impl TryFrom<U> for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `try_from` method for fallible conversions.

```APIDOC
## type Error = Infallible

The type returned in the event of a conversion error.

## fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
```

--------------------------------

### SliceExt Eytzingerize Method

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Extension method for slices to convert them into Eytzinger representation in-place. Requires the slice to be sorted beforehand.

```rust
fn eytzingerize<P: Permutator<T, PermutationGenerator>>(&mut self, permutator: &mut P) {
    permutator.permute(self, &PermutationGenerator::new(self.len()))
}
```

--------------------------------

### Search Works Test

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Tests the `eytzinger_search` functionality by sorting and deduplicating a vector and then performing searches.

```rust
fn search_works(data: Vec<usize>) -> bool {
            let mut data = data;
            data.sort();
            data.dedup();
```

--------------------------------

### Debug Implementation

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.InplacePermutator.html

Allows InplacePermutator to be formatted for debugging.

```APIDOC
### impl Debug for InplacePermutator

#### fn fmt(&self, f: &mut Formatter<'_>) -> Result
Formats the value using the given formatter.
```

--------------------------------

### impl Debug for StackCopyPermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.StackCopyPermutator.html

Provides formatting for debugging StackCopyPermutator instances.

```APIDOC
## impl Debug for StackCopyPermutator

### fn fmt(&self, f: &mut Formatter<'_>) -> Result
Formats the value using the given formatter.
```

--------------------------------

### map_windows

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Calls a function for each contiguous window of size N over the iterator.

```APIDOC
## map_windows

### Description
Calls the given function `f` for each contiguous window of size `N` over `self` and returns an iterator over the outputs of `f`. Like `slice::windows()`, the windows during mapping overlap as well.

### Signature
`fn map_windows<F, R, const N: usize>(self, f: F) -> MapWindows<Self, F, N>`

### Type Parameters
- `Self`: Must implement `Sized`.
- `F`: A closure `FnMut(&[Self::Item; N]) -> R`.
- `R`: The return type of the closure.
- `N`: The size of the window (compile-time constant).

### Note
This is a nightly-only experimental API.
```

--------------------------------

### impl Borrow<T> for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `borrow` method for immutable borrowing.

```APIDOC
## fn borrow(&self) -> &T

Immutably borrows from an owned value.
```

--------------------------------

### eytzinger_interpolative_search_by_key

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/trait.SliceExt.html

Performs an interpolative binary search on an Eytzinger slice using a key extraction function. Assumes the slice is sorted by the key. Returns a tuple of two Option<usize>: the index of the highest value less than or equal to the target key, and the index of the lowest value greater than the target key.

```APIDOC
## fn eytzinger_interpolative_search_by_key<'a, B, F, Q>(
 &'a self,
 b: &Q,
 f: F,
) -> (Option<usize>, Option<usize>)
where
 B: Borrow<Q>,
 F: FnMut(&'a T) -> B,
 Q: Ord + ?Sized,
 T: 'a,

### Description
Binary searches this sorted slice with a key extraction function for interpolation. Assumes that the slice is eytzinger-sorted by the key, for instance with `slice::sort_by_key` combined with `eytzinger::eytzingerize` using the same key extraction function. The first return value is the index of the highest value that’s less than or equal to the target value. The second return value is the index of the lowest value that’s greater than to the target value.

### Parameters
- **b** (*&Q*) - The target value to search for.
- **f** (*F*) - A closure that extracts the key from each element.

### Returns
- A tuple `(Option<usize>, Option<usize>)` representing the lower and upper bounds of the search result based on the extracted key.

### Examples
```rust
use eytzinger::SliceExt;
let s = [(3, 'd'), (1, 'b'), (5, 'f'), (0, 'a'), (2, 'c'), (4, 'e'), (6, 'g')];
assert_eq!(s.eytzinger_interpolative_search_by_key(&'d', |&(_, b)| b), (Some(0), Some(5)));
assert_eq!(s.eytzinger_interpolative_search_by_key(&'f', |&(_, b)| b), (Some(2), Some(6)));
assert_eq!(s.eytzinger_interpolative_search_by_key(&'g', |&(_, b)| b), (Some(6), None));
assert_eq!(s.eytzinger_interpolative_search_by_key(&'x', |&(_, b)| b), (Some(6), None));
```
```

--------------------------------

### fold

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Folds every element into an accumulator by applying an operation.

```APIDOC
## fold<B, F>

### Description
Folds every element into an accumulator by applying an operation, returning the final result.

### Signature
`fn fold<B, F>(self, init: B, f: F) -> B`

### Constraints
`where Self: Sized, F: FnMut(B, Self::Item) -> B`
```

--------------------------------

### Implement TryFrom Trait

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.SparseHeapPermutator.html

Provides a fallible conversion mechanism from one type to another. This is a standard blanket implementation.

```rust
type Error = Infallible
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
```

--------------------------------

### Permutation Trait Implementations

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/trait.Permutation.html

Shows how the Permutation trait is implemented for specific types.

```APIDOC
## Implementations on Foreign Types
### impl<'a> Permutation for &'a [usize]
#### type Iter = Cloned<Iter<'a, usize>>
#### fn iterable(&self) -> Self::Iter
#### fn index(&self, i: usize) -> usize
```

```APIDOC
### impl Permutation for PermutationGenerator
#### type Iter = PermutationGenerator
```

--------------------------------

### any

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Tests if any element of the iterator matches a predicate.

```APIDOC
## any<F>

### Description
Tests if any element of the iterator matches a predicate.

### Signature
`fn any<F>(&mut self, f: F) -> bool`

### Constraints
`where Self: Sized, F: FnMut(Self::Item) -> bool`
```

--------------------------------

### Slice Extension for Eytzinger Search

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Provides convenient methods for performing Eytzinger searches directly on slices. Includes exact, by key, and interpolative search variants.

```rust
impl<T> SliceExt<T> for [T] {
    #[inline]
    fn eytzingerize<P: Permutator<T, PermutationGenerator>>(&mut self, permutator: &mut P) {
        eytzingerize(self, permutator)
    }

    #[inline]
    fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize>
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        self.eytzinger_search_by(|e| e.borrow().cmp(x))
    }

    #[inline]
    fn eytzinger_search_by<'a, F>(&'a self, f: F) -> Option<usize>
    where
        F: FnMut(&'a T) -> Ordering,
        T: 'a,
    {
        eytzinger_search_by(self, f)
    }

    #[inline]
    fn eytzinger_search_by_key<'a, B, F, Q: ?Sized>(&'a self, b: &Q, mut f: F) -> Option<usize>
    where
        B: Borrow<Q>,
        F: FnMut(&'a T) -> B,
        Q: Ord,
        T: 'a,
    {
        self.eytzinger_search_by(|k| f(k).borrow().cmp(b))
    }

    #[inline]
    fn eytzinger_interpolative_search_by<'a, F>(&'a self, f: F) -> (Option<usize>, Option<usize>)
    where
        F: FnMut(&'a T) -> Ordering,
        T: 'a,
    {
        eytzinger_interpolative_search_by(self, f)
    }

    #[inline]
    fn eytzinger_interpolative_search<Q: ?Sized>(&self, x: &Q) -> (Option<usize>, Option<usize>)
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        self.eytzinger_interpolative_search_by(|e| e.borrow().cmp(x))
    }

    #[inline]
    fn eytzinger_interpolative_search_by_key<'a, B, F, Q: ?Sized>(&'a self, b: &Q, mut f: F) -> (Option<usize>, Option<usize>)
    where
        B: Borrow<Q>,
        F: FnMut(&'a T) -> B,
        Q: Ord,
        T: 'a,
    {
        self.eytzinger_interpolative_search_by(|k| f(k).borrow().cmp(b))
    }
}
```

--------------------------------

### impl Into<U> for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `into` method for converting a type into another type that implements `From<T>`.

```APIDOC
## fn into(self) -> U

Calls `U::from(self)`. That is, this conversion is whatever the implementation of `From<T> for U` chooses to do.
```

--------------------------------

### Function Signature for get_permutation_element_by_node

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/foundation/fn.get_permutation_element_by_node.html

This is the function signature for `get_permutation_element_by_node`. It takes the array size (n), tree layer index (ipk), and element index (li) as unsigned integers and returns the computed index as an unsigned integer.

```rust
pub fn get_permutation_element_by_node(n: usize, ipk: usize, li: usize) -> usize
```

--------------------------------

### PermutationGenerator::index

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Index into this permutation.

```APIDOC
## PermutationGenerator::index

### Description
Index into this permutation.

### Method
`index(&self, i: usize) -> usize`
```

--------------------------------

### CloneFrom Implementation for InplacePermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.InplacePermutator.html

Provides a clone_from method for the InplacePermutator struct.

```rust
fn clone_from(&mut self, source: &Self)
```

--------------------------------

### Global Functions

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/index.html

Provides standalone functions for eytzinger-related operations, including searching within an eytzinger slice using a comparator.

```APIDOC
## Functions

### `eytzinger_interpolative_search_by`

Binary searches this eytzinger slice with a comparator function.

##### Signature
`fn eytzinger_interpolative_search_by<T, F>(slice: &[T], mut compare: F) -> Option<usize> where F: FnMut(&T) -> std::cmp::Ordering`

### `eytzinger_search_by`

Binary searches this eytzinger slice with a comparator function.

##### Signature
`fn eytzinger_search_by<T, F>(slice: &[T], mut compare: F) -> Option<usize> where F: FnMut(&T) -> std::cmp::Ordering`

### `eytzingerize`

Converts a sorted array to its eytzinger representation.

##### Signature
`fn eytzingerize<T, P: PermutationGenerator>(slice: &mut [T], permutator: &mut P)`
```

--------------------------------

### Eytzinger Binary Search with Key Extraction

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/trait.SliceExt.html

Performs a binary search on an Eytzinger-represented slice using a key extraction function. Assumes the slice is sorted by the key.

```rust
use eytzinger::SliceExt;
let s = [(3, 'd'), (1, 'b'), (5, 'f'), (0, 'a'), (2, 'c'), (4, 'e'), (6, 'g')];
assert_eq!(s.eytzinger_search_by_key(&'f', |&(_, b)| b), Some(2));
assert_eq!(s.eytzinger_search_by_key(&'g', |&(_, b)| b), Some(6));
assert_eq!(s.eytzinger_search_by_key(&'x', |&(_, b)| b), None);
```

--------------------------------

### enumerate

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator that yields the current iteration count along with the next value.

```APIDOC
## enumerate

### Description
Creates an iterator which gives the current iteration count as well as the next value.

### Signature
`fn enumerate(self) -> Enumerate<Self>`

### Type Parameters
- `Self`: Must implement `Sized`.
```

--------------------------------

### SliceExt Methods

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/trait.SliceExt.html

This section details the methods available on slices when the SliceExt trait is in scope.

```APIDOC
## SliceExt

Eytzinger extension methods for slices.

### Methods

- `eytzingerize<P: Permutator<T, PermutationGenerator>>(&mut self, permutator: &mut P)`
  Rearranges the slice elements according to the Eytzinger layout.

- `eytzinger_search<Q>(&self, x: &Q) -> Option<usize>`
  Performs an Eytzinger search for an element `x` in the slice.
  `Q` must implement `Ord` and `T` must implement `Borrow<Q>`.

- `eytzinger_search_by<'a, F>(&'a self, f: F) -> Option<usize>`
  Performs an Eytzinger search using a custom comparison function `f`.
  The function `f` takes a reference to an element and returns an `Ordering`.

- `eytzinger_search_by_key<'a, B, F, Q>(&'a self, b: &Q, f: F) -> Option<usize>`
  Performs an Eytzinger search based on a key extracted by function `f`.
  `B` must implement `Borrow<Q>`, `Q` must implement `Ord`, and `T` must implement `Borrow<Q>`.

- `eytzinger_interpolative_search_by<'a, F>(&'a self, f: F) -> (Option<usize>, Option<usize>)`
  Performs an Eytzinger interpolative search using a custom comparison function `f`.
  Returns a tuple of optional indices representing the found range.

- `eytzinger_interpolative_search<Q>(&self, x: &Q) -> (Option<usize>, Option<usize>)`
  Performs an Eytzinger interpolative search for an element `x` in the slice.
  `Q` must implement `Ord` and `T` must implement `Borrow<Q>`.
  Returns a tuple of optional indices representing the found range.

- `eytzinger_interpolative_search_by_key<'a, B, F, Q>(&'a self, b: &Q, f: F) -> (Option<usize>, Option<usize>)`
  Performs an Eytzinger interpolative search based on a key extracted by function `f`.
  `B` must implement `Borrow<Q>`, `Q` must implement `Ord`, and `T` must implement `Borrow<Q>`.
  Returns a tuple of optional indices representing the found range.
```

--------------------------------

### min

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Returns the minimum element of the iterator.

```APIDOC
## min

### Description
Returns the minimum element of an iterator.

### Signature
`fn min(self) -> Option<Self::Item>`

### Constraints
`where Self: Sized, Self::Item: Ord`
```

--------------------------------

### copied

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator that copies all of its elements.

```APIDOC
## copied<'a, T>

### Description
Creates an iterator which copies all of its elements.

### Signature
`fn copied<'a, T>(self) -> Copied<Self>`

### Constraints
`where T: Copy + 'a, Self: Sized + Iterator<Item = &'a T>`
```

--------------------------------

### Eytzinger Permutation Element Calculation

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Tests for the `get_permutation_element_by_node` function, verifying its output against known values for different inputs.

```rust
#[test]
fn magic() {
    for (i, &v) in [0, 1, 1, 2, 3, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7, 8]
        .iter()
        .enumerate()
    {
        assert_eq!(get_permutation_element_by_node(i + 1, 1, 0), v);
    }
    for (i, &v) in [0, 0, 1, 1, 1, 1, 2, 3, 3].iter().enumerate() {
        assert_eq!(get_permutation_element_by_node(i + 2, 2, 0), v);
    }
    for (i, &v) in [2, 3, 4, 5, 5, 6, 7, 8].iter().enumerate() {
        assert_eq!(get_permutation_element_by_node(i + 3, 2, 1), v);
    }
    for (i, &v) in [0, 0, 0, 0, 1, 1, 1].iter().enumerate() {
        assert_eq!(get_permutation_element_by_node(i + 4, 3, 0), v);
    }
}
```

--------------------------------

### Interpolative Search with Integer Comparison

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/fn.eytzinger_interpolative_search_by.html

Demonstrates interpolative search using integer comparison. The function returns the indices surrounding the target value.

```rust
use eytzinger::eytzinger_interpolative_search_by;
let s = [3, 1, 5, 0, 2, 4, 6];
assert_eq!(eytzinger_interpolative_search_by(&s, |x| x.cmp(&3)),  (Some(0_usize), Some(5_usize)));
assert_eq!(eytzinger_interpolative_search_by(&s, |x| x.cmp(&5)),  (Some(2_usize), Some(6_usize)));
assert_eq!(eytzinger_interpolative_search_by(&s, |x| x.cmp(&6)),  (Some(6_usize), None));
assert_eq!(eytzinger_interpolative_search_by(&s, |x| x.cmp(&7)),  (Some(6_usize), None));
assert_eq!(eytzinger_interpolative_search_by(&s, |x| x.cmp(&0)),  (Some(3_usize), Some(1_usize)));
assert_eq!(eytzinger_interpolative_search_by(&s, |x| x.cmp(&-1)), (None, Some(3_usize)));
```

--------------------------------

### Clone Implementation

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.InplacePermutator.html

Allows cloning of InplacePermutator instances.

```APIDOC
### impl Clone for InplacePermutator

#### fn clone(&self) -> InplacePermutator
Returns a duplicate of the value.

#### fn clone_from(&mut self, source: &Self)
Performs copy-assignment from `source`.
```

--------------------------------

### position

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Searches for an element and returns its index.

```APIDOC
## position<P>

### Description
Searches for an element in an iterator, returning its index.

### Signature
`fn position<P>(&mut self, predicate: P) -> Option<usize>`

### Constraints
`where Self: Sized, P: FnMut(Self::Item) -> bool`
```

--------------------------------

### impl Clone for StackCopyPermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.StackCopyPermutator.html

Provides methods for cloning StackCopyPermutator instances.

```APIDOC
## impl Clone for StackCopyPermutator

### fn clone(&self) -> StackCopyPermutator
Returns a duplicate of the value.
```

```APIDOC
### fn clone_from(&mut self, source: &Self)
Performs copy-assignment from `source`.
```

--------------------------------

### inspect

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Performs an action for each element of an iterator without consuming it.

```APIDOC
## inspect

### Description
Does something with each element of an iterator, passing the value on.

### Signature
`fn inspect<F>(self, f: F) -> Inspect<Self, F>`

### Type Parameters
- `Self`: Must implement `Sized`.
- `F`: A closure `FnMut(&Self::Item)`.
```

--------------------------------

### Implement Debug for SparseHeapPermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.SparseHeapPermutator.html

Allows SparseHeapPermutator instances to be formatted for debugging purposes. This is crucial for inspecting the state of the permutator during development.

```rust
fn fmt(&self, f: &mut Formatter<'_>) -> Result
```

--------------------------------

### Copy Implementation

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.InplacePermutator.html

Indicates that InplacePermutator is a Copy type.

```APIDOC
### impl Copy for InplacePermutator
```

--------------------------------

### impl BorrowMut<T> for T

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Provides the `borrow_mut` method for mutable borrowing.

```APIDOC
## fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value.
```

--------------------------------

### skip

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator that skips the first `n` elements.

```APIDOC
## skip

### Description
Creates an iterator that skips the first `n` elements.

### Signature
`fn skip(self, n: usize) -> Skip<Self>`

### Type Parameters
- `Self`: Must implement `Sized`.

### Parameters
- `n` (usize): The number of elements to skip.
```

--------------------------------

### Implement Into Trait

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.SparseHeapPermutator.html

Enables conversion into another type that implements `From`. This is a standard blanket implementation.

```rust
fn into(self) -> U
```

--------------------------------

### SliceExt Eytzinger Search Method

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Performs a binary search on an Eytzinger-represented slice. Returns Some(index) if found, None otherwise. Assumes the slice is already in Eytzinger format.

```rust
fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize>
    where
        Q: Ord,
        T: Borrow<Q>;
```

--------------------------------

### Compute Sorted Array Index from Eytzinger Node

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Calculates the index in a sorted array given the array size, tree layer index (ipk), and element index within the layer (li). This is the core permutation logic.

```rust
pub fn get_permutation_element_by_node(n: usize, ipk: usize, li: usize) -> usize {
    let zk = li * 2 + 1;
    // k = zk * 2^-ipk

    let last_power_of_two = (n + 2).next_power_of_two() / 2;

    let y = (last_power_of_two >> (ipk - 1)) * zk;
    let kp = y >> 1;
    let x = kp + last_power_of_two; // (1+k) * last_power_of_two
    let x = x.saturating_sub(n + 1);

    //println!("n={} x={} y={} z={} kp={} lpot={}", n, x,y,z, kp, last_power_of_two);
    y - x - 1
}
```

--------------------------------

### cloned

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator that clones all of its elements.

```APIDOC
## cloned<'a, T>

### Description
Creates an iterator which `clone`s all of its elements.

### Signature
`fn cloned<'a, T>(self) -> Cloned<Self>`

### Constraints
`where T: Clone + 'a, Self: Sized + Iterator<Item = &'a T>`
```

--------------------------------

### Debug Implementation for HeapPermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.HeapPermutator.html

Implementation of the `Debug` trait for `HeapPermutator` for formatted output.

```APIDOC
## impl Debug for HeapPermutator

### fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.
```

--------------------------------

### New PermutationGenerator instance

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates a new PermutationGenerator for a sorted array of a specified size. This is the constructor for the generator.

```rust
pub fn new(size: usize) -> PermutationGenerator
```

--------------------------------

### eytzinger_search_by_key

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/trait.SliceExt.html

Performs a binary search on an Eytzinger-represented slice using a key extraction function.

```APIDOC
## fn eytzinger_search_by_key<'a, B, F, Q>(&'a self, b: &Q, f: F) -> Option<usize>
where B: Borrow<Q>, F: FnMut(&'a T) -> B, Q: Ord + ?Sized, T: 'a

### Description
Binary searches this sorted slice with a key extraction function. Assumes that the slice is eytzinger-sorted by the key. If a matching value is found then `Some` is returned, containing the index of the matching element; if no match is found then `None` is returned.

### Parameters
- `b`: The key to search for.
- `f`: A closure that extracts a key from an element.

### Returns
- `Some(usize)`: The index of the found element.
- `None`: If the element is not found.
```

--------------------------------

### Heap Permutator Implementation (with heap-permutator feature)

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Implements a linear-time heap-based permutator using a reusable buffer. This version is enabled by the 'heap-permutator' feature flag.

```rust
impl<T, P: ?Sized + Permutation> Permutator<T, P> for HeapPermutator {
    #[inline]
    fn permute(&mut self, data: &mut [T], permutation: &P) {
        use std::convert::TryInto;
        self.buffer.clear();
        self.buffer.resize(data.len(), None);
        for mut i in 0..data.len() {
            let mut j = permutation.index(i);
            if j < i {
                j = self.buffer[j].take().unwrap().get();
            }
            data.swap(i, j);
            if let Some(x) = self.buffer[i].take() {
                i = x.get();
            }

            if j != i {
                self.buffer[j] = Some(i.try_into().unwrap());
                self.buffer[i] = Some(j.try_into().unwrap());
            }
        }
    }
}
```

--------------------------------

### find

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Searches for an element that satisfies a predicate.

```APIDOC
## find<P>

### Description
Searches for an element of an iterator that satisfies a predicate.

### Signature
`fn find<P>(&mut self, predicate: P) -> Option<Self::Item>`

### Constraints
`where Self: Sized, P: FnMut(&Self::Item) -> bool`
```

--------------------------------

### Default Implementation for HeapPermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.HeapPermutator.html

Provides a default value for HeapPermutator.

```APIDOC
## impl Default for HeapPermutator

### fn default() -> HeapPermutator

Returns the “default value” for a type.
```

--------------------------------

### unzip

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Converts an iterator of pairs into a pair of containers.

```APIDOC
## unzip<A, B, FromA, FromB>

### Description
Converts an iterator of pairs into a pair of containers.

### Signature
`fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB)`

### Constraints
`where FromA: Default + Extend<A>, FromB: Default + Extend<B>, Self: Sized + Iterator<Item = (A, B)>`
```

--------------------------------

### Advance PermutationGenerator by n elements

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Advances the iterator by n elements. This is a nightly-only experimental API.

```rust
fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>>
```

--------------------------------

### impl Default for StackCopyPermutator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.StackCopyPermutator.html

Provides a default value for StackCopyPermutator.

```APIDOC
## impl Default for StackCopyPermutator

### fn default() -> StackCopyPermutator
Returns the “default value” for a type.
```

--------------------------------

### Implement TryInto Trait

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.SparseHeapPermutator.html

Provides a fallible conversion mechanism into another type that implements `TryFrom`. This is a standard blanket implementation.

```rust
type Error = <U as TryFrom<T>>::Error
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
```

--------------------------------

### Calculate Index Test

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Verifies that `index_to_node` correctly maps linear indices to their corresponding Eytzinger tree node coordinates.

```rust
fn calc_index() {
        for (i, &x) in NODE_INDEXES.iter().enumerate() {
            assert_eq!(x, index_to_node(i));
        }
    }
```

--------------------------------

### Eytzinger Simple Permutation Test

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Tests the `eytzingerize` function by applying it to a payload and comparing the result with a reference permutation.

```rust
fn eytzingerize_simple() {
        let mut permutator = InplacePermutator;
        for &array in REF_PERMUTATIONS {
            let mut payload: Vec<_> = (0..array.len()).collect();
            eytzingerize(payload.as_mut_slice(), &mut permutator);
            assert_eq!(payload, array);
        }
    }
```

--------------------------------

### find_map

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Applies a function and returns the first non-none result.

```APIDOC
## find_map<B, F>

### Description
Applies function to the elements of iterator and returns the first non-none result.

### Signature
`fn find_map<B, F>(&mut self, f: F) -> Option<B>`

### Constraints
`where Self: Sized, F: FnMut(Self::Item) -> Option<B>`
```

--------------------------------

### Implement Any Trait

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/permutation/struct.SparseHeapPermutator.html

Provides the `type_id` method, allowing for runtime type identification. This is a common blanket implementation for types that are 'static.

```rust
fn type_id(&self) -> TypeId
```

--------------------------------

### SliceExt Eytzinger Search with Comparator

Source: https://docs.rs/eytzinger/1.1.2/src/eytzinger/lib.rs.html

Performs a binary search using a custom comparator function on an Eytzinger-represented slice. The comparator must maintain the Eytzinger order.

```rust
fn eytzinger_search_by<F>(&self, f: F) -> Option<usize>
    where
        F: FnMut(&T) -> std::cmp::Ordering;
```

--------------------------------

### Eytzinger Binary Search with Comparator

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/trait.SliceExt.html

Performs a binary search on an Eytzinger-represented slice using a custom comparator function. Returns Some(index) if found, None otherwise.

```rust
use eytzinger::SliceExt;
let s = [3, 1, 5, 0, 2, 4, 6];
assert_eq!(s.eytzinger_search_by(|x| x.cmp(&5)), Some(2));
assert_eq!(s.eytzinger_search_by(|x| x.cmp(&6)), Some(6));
assert_eq!(s.eytzinger_search_by(|x| x.cmp(&7)), None);
```

--------------------------------

### map_while

Source: https://docs.rs/eytzinger/1.1.2/eytzinger/struct.PermutationGenerator.html

Creates an iterator that maps elements while a predicate returns Some.

```APIDOC
## map_while

### Description
Creates an iterator that both yields elements based on a predicate and maps.

### Signature
`fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>`

### Type Parameters
- `Self`: Must implement `Sized`.
- `B`: The type of the mapped elements.
- `P`: A closure `FnMut(Self::Item) -> Option<B>`.
```
Tokens:
Raw