### 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 ``` -------------------------------- ### 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` ### 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 ``` -------------------------------- ### 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) ``` -------------------------------- ### 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 ``` -------------------------------- ### 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 ``` -------------------------------- ### 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) -> bool { test_permutation::(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 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) -> bool { test_permutation::(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) -> bool { test_permutation::>(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 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 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 = >::Error The type returned in the event of a conversion error. ## fn try_into(self) -> Result>::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) -> bool { test_permutation::(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) -> bool { test_permutation::(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 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(self, f: F) -> (B, B)` ### Type Parameters - `Self`: Must implement `Sized`. - `B`: The type of the collections, must implement `Default + Extend`. - `F`: A closure `FnMut(&Self::Item) -> bool`. ``` -------------------------------- ### impl TryFrom 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>::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>(&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) -> 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(self, f: F) -> MapWindows` ### 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 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: 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, Option) where B: Borrow, 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, Option)` 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 ### Description Folds every element into an accumulator by applying an operation, returning the final result. ### Signature `fn fold(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>::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> #### 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 ### Description Tests if any element of the iterator matches a predicate. ### Signature `fn any(&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 SliceExt for [T] { #[inline] fn eytzingerize>(&mut self, permutator: &mut P) { eytzingerize(self, permutator) } #[inline] fn eytzinger_search(&self, x: &Q) -> Option where Q: Ord, T: Borrow, { self.eytzinger_search_by(|e| e.borrow().cmp(x)) } #[inline] fn eytzinger_search_by<'a, F>(&'a self, f: F) -> Option 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 where B: Borrow, 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, Option) where F: FnMut(&'a T) -> Ordering, T: 'a, { eytzinger_interpolative_search_by(self, f) } #[inline] fn eytzinger_interpolative_search(&self, x: &Q) -> (Option, Option) where Q: Ord, T: Borrow, { 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, Option) where B: Borrow, F: FnMut(&'a T) -> B, Q: Ord, T: 'a, { self.eytzinger_interpolative_search_by(|k| f(k).borrow().cmp(b)) } } ``` -------------------------------- ### impl Into 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`. ```APIDOC ## fn into(self) -> U Calls `U::from(self)`. That is, this conversion is whatever the implementation of `From 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(slice: &[T], mut compare: F) -> Option where F: FnMut(&T) -> std::cmp::Ordering` ### `eytzinger_search_by` Binary searches this eytzinger slice with a comparator function. ##### Signature `fn eytzinger_search_by(slice: &[T], mut compare: F) -> Option where F: FnMut(&T) -> std::cmp::Ordering` ### `eytzingerize` Converts a sorted array to its eytzinger representation. ##### Signature `fn eytzingerize(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` ### 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>(&mut self, permutator: &mut P)` Rearranges the slice elements according to the Eytzinger layout. - `eytzinger_search(&self, x: &Q) -> Option` Performs an Eytzinger search for an element `x` in the slice. `Q` must implement `Ord` and `T` must implement `Borrow`. - `eytzinger_search_by<'a, F>(&'a self, f: F) -> Option` 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` Performs an Eytzinger search based on a key extracted by function `f`. `B` must implement `Borrow`, `Q` must implement `Ord`, and `T` must implement `Borrow`. - `eytzinger_interpolative_search_by<'a, F>(&'a self, f: F) -> (Option, Option)` Performs an Eytzinger interpolative search using a custom comparison function `f`. Returns a tuple of optional indices representing the found range. - `eytzinger_interpolative_search(&self, x: &Q) -> (Option, Option)` Performs an Eytzinger interpolative search for an element `x` in the slice. `Q` must implement `Ord` and `T` must implement `Borrow`. 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, Option)` Performs an Eytzinger interpolative search based on a key extracted by function `f`. `B` must implement `Borrow`, `Q` must implement `Ord`, and `T` must implement `Borrow`. 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` ### 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` ### Constraints `where T: Copy + 'a, Self: Sized + Iterator` ``` -------------------------------- ### 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

### Description Searches for an element in an iterator, returning its index. ### Signature `fn position

(&mut self, predicate: P) -> Option` ### 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(self, f: F) -> Inspect` ### 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 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` ### 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(&self, x: &Q) -> Option where Q: Ord, T: Borrow; ``` -------------------------------- ### 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` ### Constraints `where T: Clone + 'a, Self: Sized + Iterator` ``` -------------------------------- ### 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 where B: Borrow, 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 Permutator 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

### Description Searches for an element of an iterator that satisfies a predicate. ### Signature `fn find

(&mut self, predicate: P) -> Option` ### 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 ### Description Converts an iterator of pairs into a pair of containers. ### Signature `fn unzip(self) -> (FromA, FromB)` ### Constraints `where FromA: Default + Extend, FromB: Default + Extend, Self: Sized + Iterator` ``` -------------------------------- ### 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> ``` -------------------------------- ### 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 = >::Error fn try_into(self) -> Result>::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 ### Description Applies function to the elements of iterator and returns the first non-none result. ### Signature `fn find_map(&mut self, f: F) -> Option` ### Constraints `where Self: Sized, F: FnMut(Self::Item) -> Option` ``` -------------------------------- ### 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(&self, f: F) -> Option 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(self, predicate: P) -> MapWhile` ### Type Parameters - `Self`: Must implement `Sized`. - `B`: The type of the mapped elements. - `P`: A closure `FnMut(Self::Item) -> Option`. ```