Skip to content

Instantly share code, notes, and snippets.

@makoConstruct
Created September 7, 2014 01:41
Show Gist options
  • Save makoConstruct/9fab7b5cc988a4a93415 to your computer and use it in GitHub Desktop.
Save makoConstruct/9fab7b5cc988a4a93415 to your computer and use it in GitHub Desktop.
fn rotate_right<A>(mut root: Nref<A>)-> Nref<A>{ //assumes root and leftofroot are some. I can't think of a way to take them as &ref Box<Node<A>> s, though, rightofleft might be None, and I need to be able to switch rightofleft with leftofroot.
let leftofroot = &mut root.unwrap().left;
let rightofleft = &mut root.unwrap().left.unwrap().right;
// transitions are as follows
// | root | leftofroot | rightofleft | -swap->
// | leftofroot | root | rightofleft | -swap->
// | leftofroot | rightofleft | root |
// left is now pointed by the previous owner of root[it is the new root of the tree cutting in question], left's right is now on the leftref of the old root, and the old root is the right child of the new root. That is the rotation we want.
swap(&mut root, leftofroot);
swap(leftofroot, rightofleft);
rightofleft.unwrap().update_deepness(); //the grid shows these will be some as long as the input requirements were met
root .unwrap().update_deepness();
root
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment