Josephus permutation

Question

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein:

We define the Josephus problem as follows. Suppose that n people form a circle and that we are given a positive integer m <= n. Beginning with a designated first person, we proceed around the circle, removing every mth person. After each person is removed, counting continues around the circle that remains. This process continues until we have removed all n people. The order in which the people are removed from the circle defines the (n, m)-Josephus permutation of the integers 1,2,...,n. For example, the (7, 3)-Josephus permutation is (3,6,2,7,5,1,4)

Suppose that m is not a constant. Describe an O(nlg(n))-time algorithm that, given integers n and m, outputs the (n, m)-Josephus permutation.

My solution was to use an augmented tree for getting the rank of any element in \$O(log(n))\$time. But instead of implementing a balance tree, I build the tree given a range from 1 to n in \$O(n)\$ time. I would prefer a review on how to make my code more idiomatic and elegant but any kind of review is welcome.

Josephus permutation (lib.rs)

extern crate itertools;
use itertools::Unfold;
mod util;
use util::*;

pub fn permutation(size: u32, m: u32) -> Box<Iterator<Item = u32>> {

    let mut tree = Tree::new(1, size);
    Box::new(Unfold::new(1, move |a| {
                 *a = (*a + m - 2) % tree.len() + 1;
                 Some(tree.pop_rank(*a))
             }).take(size as usize))
}

Tree (util.rs)

use std::cmp::Ordering;


#[derive(Debug)]
struct Node {
    data: u32,
    left: Option<Box<Node>>,
    rigth: Option<Box<Node>>,
    size: u32,
}

impl Node {
    fn new(data: u32) -> Node {
        Node {
            data: data,
            left: None,
            rigth: None,
            size: 0,
        }
    }
}
#[derive(Debug)]
pub struct Tree {
    root: Option<Box<Node>>,
}

impl Tree {
    fn get_size(node: &Option<Box<Node>>) -> u32 {
        node.as_ref().map_or(0, |x| x.size)
    }
    fn build_from_range(from: u32, to: u32) -> Option<Box<Node>> {
        if from > to {
            None
        } else {
            let mid = from + (to - from) / 2;
            let mut node = Node::new(mid);

            node.left = Tree::build_from_range(from, mid - 1);
            node.rigth = Tree::build_from_range(mid + 1, to);
            node.size = 1 + Tree::get_size(&node.left) 
                          + Tree::get_size(&node.rigth);
            Some(Box::new(node))
        }
    }

    pub fn new(from: u32, to: u32) -> Tree {
        Tree { root: Tree::build_from_range(from, to) }
    }
    fn find_rank(node: &mut Option<Box<Node>>, rank: u32) -> &mut Option<Box<Node>> {

        let r = Tree::get_size(&node.as_mut()
                                    .expect("rank out of range")
                                    .left) + 1;

        Tree::get_mut(node).size -= 1;
        let (d, r) = match rank.cmp(&r) {
            Ordering::Equal => return node,
            Ordering::Less => (&mut Tree::get_mut(node).left, rank),
            Ordering::Greater => (&mut Tree::get_mut(node).rigth, rank - r),
        };
        Tree::find_rank(d, r)
    }

    fn get_mut(node: &mut Option<Box<Node>>) -> &mut Box<Node> {
        node.as_mut().unwrap()
    }

    pub fn pop_rank(&mut self, rank: u32) -> u32 {

        let ranked = Tree::find_rank(&mut self.root, rank);
        let data = ranked.as_ref()
                         .unwrap()
                         .data;

        Tree::delete_node(ranked);
        data
    }

    fn delete_node(node: &mut Option<Box<Node>>) {

        *node = node.take()
                    .map(|mut x| {
                        if x.left.is_none() {
                            x.rigth
                        } else if x.rigth.is_none() {
                            x.left
                        } else {
                            x.data = Tree::pop_min(&mut x.rigth).unwrap();
                            Some(x)
                        }
                    })
                    .expect("Cant't delete none");
    }
    fn pop_min(node: &mut Option<Box<Node>>) -> Option<u32> {
        node.take()
            .and_then(|mut x| {
                if x.left.is_none() {
                    let data = x.data;
                    *node = x.rigth;
                    Some(data)
                } else {
                    x.size -= 1;
                    let result = Tree::pop_min(&mut x.left);
                    *node = Some(x);
                    result
                }
            })
    }
    pub fn len(&self) -> u32 {
        Tree::get_size(&self.root)
    }
}

Client and tests (main.rs)

extern crate josephus;

#[test]
fn test1() {
     let x: Vec<u32> = josephus::permutation(7,3).collect();
     assert_eq!(x, vec![3, 6, 2, 7, 5, 1, 4 ]);
}

#[test]
fn test2() {
     let x: Vec<u32> = josephus::permutation(14, 6).collect();
     assert_eq!(x, vec![6, 12, 4, 11, 5, 14, 9, 7, 3 ,8, 13, 10, 2, 1 ]);
}
fn main() {
   let x: Vec<u32> = josephus::permutation(143455,1534).collect();
   println!("{:?}", x.len());
}

Answer 1

Overall, I had trouble getting some interesting feedback to start. That just meant I had to turn on the high beams and look in some dark crannies!

1. Typo with rigth.
2. I'd recommend newlines between method bodies for easier reading.
3. I'd recommend using a guard clause to return early from a function. This allows the rest of the function body to have less indentation.
4. Typo with cant't.
5. No trailing space needed in a slice / vector literal.
6. Can use a type placeholder (_) for Vec<_> instead of spelling it out again.
7. The tests could check the properties of the algorithm (all values are within the range, no duplicate values, etc.). This would be a good place for quickcheck.
8. The test names are a bit anemic. I prefer tests to be descriptive about what unique property they are checking.
9. It's not needed to create a vector to compare against; vectors can be compared to static arrays and slices.
10. For easier debugging, you can rewrite your unwrap calls to expect calls with meaningful text.
11. Names like util are always worrisome; they tend to be junk drawers where things get thrown and never cleaned up. If you have a module, hopefully there's a logical grouping for that code; use that as the name.
12. Along those lines, I'm unclear what benefit the module provides in this case. I'd suggest inlining it completely.
13. I can't fully explain this one, but it's not super common to accept a &mut T and modify it in place. There are certainly cases for this and examples in the standard library, but something about these uses threw me off.

One large thing that was quite strange was the use of Tree::* to call functions. If you have functions that don't logically belong to a struct / enum, there's nothing wrong with just having them be free functions, unassociated with any type. However, there's a large group of them that all take the same Option<Box<Node>>, so I'd encourage you to promote that to a type.

1. The get_ prefix isn't very common in Rust. I'd remove it for getters and rewrite it for transformation methods (as_foo, into_foo, by_foo, etc.).
2. Rewrite the match rank.cmp(&r) body to be more uniform.
3. For whatever reason, the *self = parts still look strange to me; but I'm not seeing an obvious improvement.

util.rs

use std::cmp::Ordering;

#[derive(Debug)]
struct Node {
    data: u32,
    left: Foo,
    right: Foo,
    size: u32,
}

impl Node {
    fn new(data: u32) -> Node {
        Node {
            data: data,
            left: Foo(None),
            right: Foo(None),
            size: 0,
        }
    }
}

#[derive(Debug)]
struct Foo(Option<Box<Node>>);

impl Foo {
    fn new(from: u32, to: u32) -> Foo {
        if from > to { return Foo(None) }

        let mid = from + (to - from) / 2;
        let mut node = Node::new(mid);

        node.left = Foo::new(from, mid - 1);
        node.right = Foo::new(mid + 1, to);
        node.size = 1 + node.left.size() + node.right.size();

        Foo(Some(Box::new(node)))
    }

    fn size(&self) -> u32 {
        self.0.as_ref().map_or(0, |x| x.size)
    }

    fn find_rank(&mut self, rank: u32) -> &mut Foo {
        let r = self.0.as_mut()
            .expect("rank out of range")
            .left.size() + 1;

        self.as_mut().size -= 1;

        match rank.cmp(&r) {
            Ordering::Equal => self,
            Ordering::Less => self.as_mut().left.find_rank(rank),
            Ordering::Greater => self.as_mut().right.find_rank(rank - r),
        }
    }

    fn as_mut(&mut self) -> &mut Box<Node> {
        self.0.as_mut().unwrap()
    }

    fn delete_node(&mut self)  {
        *self = self.0.take()
            .map(|mut x| {
                if x.left.0.is_none() {
                    x.right
                } else if x.right.0.is_none() {
                    x.left
                } else {
                    x.data = x.right.pop_min().unwrap();
                    Foo(Some(x))
                }
            })
            .expect("Can't delete None");
    }

    fn pop_min(&mut self) -> Option<u32> {
        self.0.take()
            .and_then(|mut x| {
                if x.left.0.is_none() {
                    let data = x.data;
                    *self = x.right;
                    Some(data)
                } else {
                    x.size -= 1;
                    let result = x.left.pop_min();
                    *self = Foo(Some(x));
                    result
                }
            })
    }
}

#[derive(Debug)]
pub struct Tree {
    root: Foo,
}

impl Tree {
    pub fn new(from: u32, to: u32) -> Tree {
        Tree { root: Foo::new(from, to) }
    }

    pub fn pop_rank(&mut self, rank: u32) -> u32 {
        let ranked = self.root.find_rank(rank);
        let data = ranked.0.as_ref()
                         .unwrap()
                         .data;

        ranked.delete_node();
        data
    }

    pub fn len(&self) -> u32 {
        self.root.size()
    }
}

lib.rs

extern crate itertools;

use itertools::Unfold;
mod util;
use util::*;

pub fn permutation(size: u32, m: u32) -> Box<Iterator<Item = u32>> {
    let mut tree = Tree::new(1, size);
    let x = Unfold::new(1, move |a| {
        *a = (*a + m - 2) % tree.len() + 1;
        Some(tree.pop_rank(*a))
    });
    Box::new(x.take(size as usize))
}

main.rs

extern crate joe as josephus;

#[test]
fn test1() {
     let x: Vec<_> = josephus::permutation(7, 3).collect();
     assert_eq!(x, [3, 6, 2, 7, 5, 1, 4]);
}

#[test]
fn test2() {
     let x: Vec<_> = josephus::permutation(14, 6).collect();
     assert_eq!(x, [6, 12, 4, 11, 5, 14, 9, 7, 3, 8, 13, 10, 2, 1]);
}

fn main() {
   let x: Vec<_> = josephus::permutation(143455, 1534).collect();
   println!("{:?}", x.len());
}