Josephus permutation - follow up

Follow up of this question

Changes:

• The pop_min function now panics if the tree is empty.

• Moved the size attribute to the Tree struct.

• Applied most of the suggestions given by the answers.

• Added some other functions.

• Refactored some functions.

• Moved everything to the same file.

```
extern crate itertools;
use itertools::Unfold;
use std::cmp::Ordering;

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

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

#[derive(Debug)]
struct Tree {
size: u32,
root: Option>,
}

impl Tree {
fn new(from: u32, to: u32) -> Tree {
if from > to {
return Tree { root: None, size: 0, };
}
let mid = from + (to - from) / 2;
let node = Node {
data: mid,
left: Tree::new(from, mid - 1),
right: Tree::new(mid + 1, to),
};

Tree {
size: 1 + node.left.size + node.right.size,
root: Some(Box::new(node)),
}
}

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

self.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 {
self.root.as_mut().unwrap()
}

fn as_ref(&self) -> &Box {
self.root.as_ref().unwrap()
}

fn empty(&self) -> bool {
self.root.is_none()
}

fn delete_node(&mut self) {
*self = self.root
.take

This mostly looks OK, but I really don't like

*self = self.root
            .take()
            .map(|mut x| {
                if x.left.empty() {
                    x.right
                } else if x.right.empty() {
                    x.left
                } else {
                    x.data = x.right.pop_min();
                    Tree {
                        root: Some(x),
                        size: self.size,
                    }
                }
            })
            .expect("Can't delete None");

You can shift up the expect to get

let mut node = self.root.take().expect("Can't delete None");
*self =
    if node.left.empty() {
        node.right
    } else if node.right.empty() {
        node.left
    } else {
        node.data = node.right.pop_min();
        Tree {
            root: Some(node),
            size: self.size,
        }
    };

which is already much nicer. Then deal with the error and naming:

fn delete_root_node(&mut self) {
    let mut root = self.root.take().expect("Empty tree has no root");
    *self =
        if root.left.empty() {
            root.right
        } else if root.right.empty() {
            root.left
        } else {
            root.data = root.right.pop_min();
            Tree {
                root: Some(root),
                size: self.size,
            }
        };
}

Then I'd flatten it back out

fn delete_root_node(&mut self) {
    let mut root = self.root.take().expect("Empty tree has no root");

    if root.left.empty() {
        *self = root.right
    } else if root.right.empty() {
        *self = root.left
    } else {
        root.data = root.right.pop_min();
        self.root = Some(root);
    };
}

Rust's tools are great, but they shouldn't be abused. In this case, a simple imperative style reads much nicer than the semi-functional transformations, so should be preferred.

More rightward drift can be dealt with in find_rank:

fn find_rank(&mut self, rank: u32) -> &mut Tree {
    let right_offset = self.as_mut().left.size + 1;

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

Now, find_rank is doing something really horrible:

self.size -= 1;

This breaks the Tree's invariants. Much better would be to call this pop_rank and move pop_rank inside of it. You can make this a bit nicer by having pop_root return a u32 and just depending on that, though.

Then we have a nice chain of functions

fn pop_rank(&mut self, rank: u32) -> u32 {
    let left_size = self.as_mut().left.size;
    self.size -= 1;

    match rank.cmp(&(1 + left_size)) {
        Ordering::Equal   => {
            self.size += 1;
            self.pop_root()
        },
        Ordering::Less    => self.as_mut().left.pop_rank(rank),
        Ordering::Greater => self.as_mut().right.pop_rank(rank - 1 - left_size),
    }
}

fn pop_root(&mut self) -> u32 {
    let mut root = self.root.take().expect("Empty tree has no root");
    let data = root.data;

    if root.left.empty() {
        *self = root.right
    } else if root.right.empty() {
        *self = root.left
    } else {
        root.data = root.right.pop_min();
        self.root = Some(root);
        self.size -= 1;
    };

    data
}

fn pop_min(&mut self) -> u32 {
    if self.as_ref().left.empty() {
        let data = self.as_ref().data;
        *self = self.root.take().unwrap().right;
        data
    } else {
        self.size -= 1;
        self.as_mut().left.pop_min()
    }
}

The restoring of self.size in pop_rank before calling pop_root might slightly increase computational burden but it means that each function only relies on the data structure's basic invariants to work properly.

Note that pop_min doesn't actually need to panic! as that's captured by self.as_ref's auto-panic.

as_ref and as_mut are misleading names since they actually give handles to root; better would be get_root and get_root_mut. I'd also swap pop_min for pop_first for clarity.

I'd also change m to step in permutation.

I've been transfixed by this problem for a while now, so I'm going to introduce my thoughts about it. Very little of what follows has anything to do with your implementation, but hopefully someone at least finds it a little interesting.

It's worth noting that Box-heavy structures tend to be slow. A much more efficient tree structure to work with could be a Vec> like so:

tree[0]               13
tree[1]        8               5
tree[2]    4       4       4       1
tree[3]  2   2   2   2   2   2   1
tree[4] 1 1 1 1 1 1 1 1 1 1 1 1 1

tree[0..3] are used to guide you to an index in the bottom. "Using" the fifth value would result in the tree modified like so

```
tree[0] 12
tree[1] 7 5
tree[2]

StackExchange Code Review Q#122701, answer score: 3