1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

use std::hash::BuildHasher;

use crate::{Feistel, DefaultBuildHasher};

/// An object of constructing random access permutations.
pub struct Permutation<B = DefaultBuildHasher>
where
    B: BuildHasher,
{
    n: u64,
    feistel: Feistel<B>,
}

impl<B> Permutation<B>
where
    B: BuildHasher,
{
    /// Construct a new permutation over the range `0..n`.
    pub fn new(n: u64, seed: u64, bob: B) -> Permutation<B> {
        let mut keys = Vec::new();
        let mut k = seed;
        for _i in 0..5 {
            k = bob.hash_one(k);
            keys.push(k);
        }
        println!("keys = {:?}", keys);

        // Code assumes an even number of bits. Rounding up
        // increases the constant factor in [`get`] but doesn't
        // alter the big-O complexity.
        let z = 64 - n.leading_zeros() as usize;
        let bits = z + (z & 1);

        Permutation {
            n,
            feistel: Feistel::new(bob, bits, &keys),
        }
    }

    /// Get the xth element of the permutation.
    pub fn get(&self, x: u64) -> u64 {
        assert!(x < self.n);
        let mut res = self.feistel.encrypt(x);
        while res >= self.n {
            res = self.feistel.encrypt(res);
        }
        res
    }

    /// Construct an iterator over the entire permutation.
    pub fn iter(&self) -> PermutationIterator<'_, B> {
        PermutationIterator::new(self, 0, self.n)
    }

    /// Construct an iterator over the subset `begin..end` of the permutation.
    pub fn range(&self, begin: u64, end: u64) -> PermutationIterator<'_, B> {
        assert!(begin <= end);
        assert!(end <= self.n);
        PermutationIterator::new(self, begin, end)
    }
}

/// An iterator over a [`Permutation`] object.
pub struct PermutationIterator<'a, B>
where
    B: BuildHasher,
{
    source: &'a Permutation<B>,
    curr: u64,
    end: u64,
}

impl<'a, B> PermutationIterator<'a, B>
where
    B: BuildHasher,
{
    fn new(source: &'a Permutation<B>, begin: u64, end: u64) -> PermutationIterator<'a, B> {
        PermutationIterator {
            source,
            curr: begin,
            end,
        }
    }
}

impl<'a, B> Iterator for PermutationIterator<'a, B>
where
    B: BuildHasher,
{
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        if self.curr == self.end {
            None
        } else {
            let res = self.source.get(self.curr);
            self.curr += 1;
            Some(res)
        }
    }
}

#[cfg(test)]
mod tests {
    use xxhash_rust::xxh64;

    use super::*;

    #[test]
    fn test_1() {
        let n = 1000;
        let bob = xxh64::Xxh64Builder::new(19);
        let perm = Permutation::new(n, 19, bob);
        let mut xs = Vec::new();
        for i in 0..n {
            let x = perm.get(i);
            //println!("{i}\t{x}");
            xs.push(x);
        }
        let mut lt = 0;
        for i in 1..n as usize {
            if xs[i - 1] < xs[i] {
                lt += 1;
            }
        }
        assert_eq!(lt, n / 2);

        xs.sort();
        for i in 0..n {
            assert_eq!(xs[i as usize], i);
        }
    }
}