#![warn(missing_docs, missing_debug_implementations)]
use std::cmp::{Ord, Ordering};
use std::borrow::Borrow;
use permutation::*;
pub mod foundation {
#[inline]
pub fn get_permutation_element_by_node(n: usize, ipk: usize, li: usize) -> usize {
let zk = li * 2 + 1;
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; let x = x.saturating_sub(n + 1);
y - x - 1
}
#[inline]
pub fn index_to_node(i: usize) -> (usize, usize) {
let ipk = (i + 2).next_power_of_two().trailing_zeros() as usize;
let li = i + 1 - (1 << (ipk - 1));
(ipk, li)
}
#[inline]
pub fn get_permutation_element(n: usize, i: usize) -> usize {
let (ipk, li) = index_to_node(i);
get_permutation_element_by_node(n, ipk, li)
}
}
pub mod permutation {
use std::iter::{Cloned, Enumerate};
use std::slice::Iter;
pub trait Permutation {
type Iter: Iterator<Item=usize>;
fn iterable(&self) -> Self::Iter;
fn index(&self, i: usize) -> usize;
}
impl<'a> Permutation for &'a [usize] {
type Iter = Cloned<Iter<'a, usize>>;
#[inline]
fn iterable(&self) -> Self::Iter {
self.iter().cloned()
}
#[inline]
fn index(&self, i: usize) -> usize {
self[i]
}
}
pub trait Permutator<T, P: ?Sized + Permutation> {
fn permute(&mut self, data: &mut [T], permutation: &P);
}
#[derive(Clone, Copy, Debug, Default)]
pub struct InplacePermutator;
impl<T, P: ?Sized + Permutation> Permutator<T, P> for InplacePermutator {
#[inline]
fn permute(&mut self, data: &mut [T], permutation: &P) {
for (i, mut p) in permutation.iterable().enumerate() {
while p < i {
p = permutation.index(p);
}
if p > i {
data.swap(i, p);
}
}
}
}
#[derive(Clone, Copy, Debug, Default)]
pub struct StackCopyPermutator;
fn recursive_permute<T: Clone, P: ?Sized + Permutation>(data: &mut [T], permutation: &mut Enumerate<P::Iter>) {
if let Some((i, p)) = permutation.next() {
let item = data[p].clone();
recursive_permute::<T, P>(data, permutation);
data[i] = item;
}
}
impl<T: Clone, P: ?Sized + Permutation> Permutator<T, P> for StackCopyPermutator {
#[inline]
fn permute(&mut self, data: &mut [T], permutation: &P) {
let mut iter = permutation.iterable().enumerate();
recursive_permute::<T, P>(data, &mut iter);
}
}
#[derive(Debug, Default)]
pub struct HeapCopyPermutator<T> {
buffer: Vec<T>,
}
impl<T: Clone, P: ?Sized + Permutation> Permutator<T, P> for HeapCopyPermutator<T> {
#[inline]
fn permute(&mut self, data: &mut [T], permutation: &P) {
self.buffer.clear();
self.buffer.extend(permutation.iterable().map(|i| data[i].clone()));
for (i, t) in self.buffer.drain(..).enumerate() {
data[i] = t;
}
}
}
#[derive(Debug, Default)]
#[cfg(feature = "heap-permutator")]
pub struct HeapPermutator {
buffer: Vec<Option<nonmax::NonMaxUsize>>,
}
#[cfg(feature = "heap-permutator")]
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());
}
}
}
}
#[derive(Debug, Default)]
#[cfg(feature = "heap-permutator-sparse")]
pub struct SparseHeapPermutator {
buffer: std::collections::HashMap<usize, usize, nohash_hasher::BuildNoHashHasher<usize>>,
}
#[cfg(feature = "heap-permutator-sparse")]
impl<T, P: ?Sized + Permutation> Permutator<T, P> for SparseHeapPermutator {
#[inline]
fn permute(&mut self, data: &mut [T], permutation: &P) {
self.buffer.clear();
for mut i in 0..data.len() {
let mut j = permutation.index(i);
if j < i {
j = self.buffer.remove(&j).unwrap();
}
data.swap(i, j);
if let Some(x) = self.buffer.remove(&i) {
i = x;
}
if j != i {
self.buffer.insert(j, i);
self.buffer.insert(i, j);
}
}
}
}
}
#[derive(Clone, Debug)]
pub struct PermutationGenerator {
size: usize,
ipk: usize,
li: usize,
}
impl PermutationGenerator {
#[inline]
pub fn new(size: usize) -> PermutationGenerator {
PermutationGenerator {
size,
ipk: 1,
li: 0,
}
}
}
impl Iterator for PermutationGenerator {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
let k2 = 1 << (self.ipk - 1);
if k2 + self.li - 1 >= self.size {
return None;
}
if self.li >= k2 {
self.li = 0;
self.ipk += 1;
}
let li = self.li;
self.li += 1;
Some(foundation::get_permutation_element_by_node(self.size, self.ipk, li))
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let k2 = 1 << (self.ipk - 1);
let size = self.size - (k2 + self.li - 1);
(size, Some(size))
}
}
impl ExactSizeIterator for PermutationGenerator {}
impl Permutation for PermutationGenerator {
type Iter = PermutationGenerator;
#[inline]
fn iterable(&self) -> PermutationGenerator {
self.clone()
}
#[inline]
fn index(&self, i: usize) -> usize {
foundation::get_permutation_element(self.size, i)
}
}
#[inline]
pub fn eytzingerize<T, P: Permutator<T, PermutationGenerator>>(data: &mut [T], permutator: &mut P) {
let len = data.len();
permutator.permute(data, &PermutationGenerator::new(len))
}
pub trait SliceExt<T> {
fn eytzingerize<P: Permutator<T, PermutationGenerator>>(&mut self, permutator: &mut P);
fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize> where Q: Ord, T: Borrow<Q>;
fn eytzinger_search_by<'a, F>(&'a self, f: F) -> Option<usize> where F: FnMut(&'a T) -> Ordering, T: 'a;
fn eytzinger_search_by_key<'a, B, F, Q: ?Sized>(&'a self, b: &Q, f: F) -> Option<usize>
where B: Borrow<Q>,
F: FnMut(&'a T) -> B,
Q: Ord,
T: 'a;
}
#[inline]
pub fn eytzinger_search_by<'a, T: 'a, F>(data: &'a [T], f: F) -> Option<usize>
where F: FnMut(&'a T) -> Ordering {
eytzinger_search_by_impl(data, f)
}
#[inline]
#[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 => {
let o = o as usize;
let o = (o >> 1) & 1;
i = 2 * i + 1 + o;
}
};
}
None => return None,
}
}
}
#[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]; i = match f(v) {
Ordering::Greater | Ordering::Equal => 2 * i + 1,
Ordering::Less => 2 * i + 2,
};
}
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<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))
}
}
#[cfg(test)]
#[macro_use]
extern crate quickcheck;
#[cfg(test)]
mod tests {
use super::*;
use super::foundation::*;
#[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);
}
}
const REF_PERMUTATIONS: &[&'static [usize]] = &[
&[],
&[0],
&[1, 0],
&[1, 0, 2],
&[2, 1, 3, 0],
&[3, 1, 4, 0, 2],
&[3, 1, 5, 0, 2, 4],
&[3, 1, 5, 0, 2, 4, 6],
&[4, 2, 6, 1, 3, 5, 7, 0],
&[5, 3, 7, 1, 4, 6, 8, 0, 2],
&[6, 3, 8, 1, 5, 7, 9, 0, 2, 4],
&[7, 3, 0xb, 1, 5, 9, 0xd, 0, 2, 4, 6, 8, 0xa, 0xc, 0xe],
];
#[test]
fn reference_permutations() {
for &array in REF_PERMUTATIONS {
let permut: Vec<_> = PermutationGenerator::new(array.len()).collect();
assert_eq!(array, permut.as_slice());
}
}
#[test]
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);
}
}
const NODE_INDEXES: &[(usize, usize)] = &[
(1, 0),
(2, 0),
(2, 1),
(3, 0),
(3, 1),
(3, 2),
(3, 3),
(4, 0),
(4, 1),
(4, 2),
(4, 3),
(4, 4),
(4, 5),
(4, 6),
(4, 7),
];
#[test]
fn calc_index() {
for (i, &x) in NODE_INDEXES.iter().enumerate() {
assert_eq!(x, index_to_node(i));
}
}
#[test]
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]);
}
#[test]
#[cfg(feature = "heap-permutator")]
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]);
}
#[test]
#[cfg(feature = "heap-permutator-sparse")]
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]);
}
#[test]
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]);
}
#[test]
fn search_negative() {
let data: &[i32] = &[6, 2, 10, 0, 4, 8, 12];
for i in -10..20 {
let expected = data.iter().position(|&x| x == i);
assert_eq!(expected, data.eytzinger_search(&i));
}
}
fn test_permutation<P: Default>(junk: Vec<usize>) -> bool where for<'a> P: Permutator<usize, &'a [usize]> {
let mut perm: Vec<_> = (0..junk.len()).collect();
perm.sort_by_key(|&i| junk[i]);
let mut data: Vec<_> = (0..perm.len()).collect();
P::default().permute(data.as_mut_slice(), &perm.as_slice());
data == perm
}
quickcheck! {
fn inplace_permutation(junk: Vec<usize>) -> bool {
test_permutation::<InplacePermutator>(junk)
}
fn stack_permutation(junk: Vec<usize>) -> bool {
test_permutation::<StackCopyPermutator>(junk)
}
#[cfg(feature = "heap-permutator")]
fn heap_permutation(junk: Vec<usize>) -> bool {
test_permutation::<HeapPermutator>(junk)
}
#[cfg(feature = "heap-permutator-sparse")]
fn heap_permutation_sparse(junk: Vec<usize>) -> bool {
test_permutation::<SparseHeapPermutator>(junk)
}
fn heap_copy_permutation(junk: Vec<usize>) -> bool {
test_permutation::<HeapCopyPermutator<_>>(junk)
}
fn eytzinger_tree_invariants(length: usize) -> bool {
let perm: Vec<_> = PermutationGenerator::new(length).collect();
let mut todo = Vec::new();
todo.push((0, 0..length));
let mut checked = 0;
while let Some((i, range)) = todo.pop() {
match perm.get(i) {
Some(&v) => {
if !(range.start <= v && v < range.end) { return false; }
todo.push((2 * (i + 1) - 1, range.start..v));
todo.push((2 * (i + 1), v..range.end));
checked += 1;
}
None => continue,
}
}
checked == length
}
fn search_works(data: Vec<usize>) -> bool {
let mut data = data;
data.sort();
data.dedup();
data.eytzingerize(&mut InplacePermutator);
data.iter().enumerate().all(|(i, v)| data.eytzinger_search(v) == Some(i))
}
}
}