How the insertion method works, never mind the .clone()s

After a major setback, I got to work on an add method for my B-tree that would use Rust’s clone() functionality extensively to get around the problems I was having with borrowing and lifetimes.  Of course, this is not a permanent solution, but rather a way to get ideas down on the screen more immediately.

Here’s how it works:

Let’s first examine the top level–

    pub fn add(mut self, k: K, v: V) -> BTree<K, V> {
        let (a, b) = self.root.clone().add(k, v, self.upper_bound.clone()); //Each lower level returns a tuple containing a Branch
        if b {                                                                                             //and a boolean to confirm that a change was made.
            self.root = Node::new_branch(a.clone().elts, a.clone().rightmost_child);
        }
        self
    }

We first call the add method on the root, which is a Node.  If the result of this addition comes back positive (it returns “true”, which is stored in the “b” part of the tuple), we reassign the root to the Branch that results from adding.  The root is the only part of the BTree that doesn’t have to adhere to a lower bound for this reason, as we only return a Branch with one actual element (and a left and right child) every time we return from adding.

Let’s see what happens at the Node level:

    fn add(mut self, k: K, v: V, ub: uint) -> (Branch<K, V>, bool) {
        match self {
            LeafNode(leaf) => leaf.add(k, v, ub),
            BranchNode(branch) => branch.add(k, v, ub)
        }
    }

A Node is an enum, which means it could have several variations on its type.  Here, it is either a LeafNode or a BranchNode.  Each contain either a Leaf or a Branch, which holds an owned vector of elements (much like a resizeable array), and maybe (in the case of a Branch), a far-right child–a Node–which has values greater than all elements in the vector.  This part of the add method tells you which way to go next, depending on the type of Node you’re dealing with.

Let’s first check out the Branch’s add method, as it is generally the next stop when you’re working with a well-populated B-tree full of elements.

fn add(mut self, k: K, v: V, ub: uint) -> (Branch<K, V>, bool) {
        let mut new_branch = Branch::new_empty(ub.clone()); 
        let mut outcome = false;
        let mut index = -1;
        for i in range(0, self.elts.len()) {
            let order = k.cmp(&self.elts[i].key);
            match order {
                Less => {
                    let new_outcome = self.clone().elts[i].left.add(k.clone(), 
                                                                    v.clone(), 
                                                                    ub.clone());
                    new_branch = new_outcome.clone().n0();
                    outcome = new_outcome.n1();
                    index = i;
                    break;
                }
                Equal => {
                    return (new_branch, outcome);
                }
                Greater => {
                    continue;
                }
            }
        }
        if index == -1 {
            let new_outcome = self.clone().rightmost_child.add(k, v, ub);
            new_branch = new_outcome.clone().n0();
            outcome = new_outcome.n1();
        }

———-

As you might guess, this is only about half the code for the Branch’s add method.  We’ll talk about the other half later, after the call to Leaf!  We can’t add at a Branch, so we use this first part of the method to determine which part of the tree to visit next.  We could end up on a Branch or a Leaf, but in either case, we’re making a recursive call to Node::add.  Here, we look through the branches and determine whether to stop and integrate the new element (designated by k and v, a soon-to-be key-value pair) at the next level down in the tree.  If the element is larger than all of the elements in the vector, we keep track of this with the “index” variable and use this to determine if we should pursue the rightmost_child as a location for the new element.

So this might continue on for some time until we find a Leaf!  Let’s check out the full code for Leaf::add.

    fn add(mut self, k: K, v: V, ub: uint) -> (Branch<K, V>, bool) {
        let new_branch = Branch::new_empty(ub.clone());
        let to_add = LeafElt::new(k, v);
        let mut index = self.elts.clone().len();
        for i in range(0, self.elts.clone().len()) {
            let order = to_add.key.cmp(&self.elts[i].key);
            match order {
                Less => {
                    self.elts.insert(i, to_add.clone());
                    index = i;
                    break;
                }
                Equal => {
                    return (new_branch, false);
                }
                Greater => {
                    continue;
                }
            }
        }
        if index == self.elts.clone().len() {
            self.elts.insert(index, to_add.clone());
        }
        if self.elts.len() > ub {
            let midpoint = self.elts.remove(ub / 2);
            let (left_leaf, right_leaf) = self.elts.partition(|le| le.key.cmp(&midpoint.key) == Greater);
            let branch_return = Branch::new(~[BranchElt::new(midpoint.clone().key, 
                                                             midpoint.clone().value,
                                                             ~Node::new_leaf(left_leaf))],
                                            ~Node::new_leaf(right_leaf));
            return (branch_return, true);
        }
        (new_branch, false)
    }

This starts out much like the Branch’s add method where we check to see where in the Node we should go from here.  Instead of making a recursive call, though, it simply smooshes the new LeafElt into the vector of elements, which is called elts.  From there we check and see if the Leaf has exceeded the size of the upper bound.  If so, we pop out the middle element of the vector, create a new Branch with a left child and a right child comprised of either half of the vector, and we return that so the level that called the leaf can see it.

Now let’s return to the Branch.

if outcome {
            let new_elt = new_branch.clone().elts[0];
            for i in range(0, self.elts.len()) {
                let order = new_elt.key.cmp(&self.elts[i].key);
                match order {
                    Less => {
                        continue;
                    }
                    Equal => {
                        return (Branch::new_empty(ub.clone()), false);
                    }
                    Greater => {
                        self.elts.insert(i + 1, new_elt);
                        if i + 2 >= self.elts.len() {
                            self.rightmost_child = new_branch.clone().rightmost_child;
                        }
                        else {
                            self.elts[i + 2].left = new_branch.clone().rightmost_child;
                        }
                        break;
                    }
                }
            }
            if self.elts.len() > ub {
                let midpoint = self.elts.remove(ub / 2);
                let (new_left, new_right) = self.clone().elts.partition(|le| 
                                                                midpoint.key.cmp(&le.key) == Greater);
                new_branch = Branch::new(~[BranchElt::new(midpoint.clone().key,
                                                          midpoint.clone().value,
                                                          ~Node::new_branch(new_left,
                                                                           midpoint.clone().left))],
                                           ~Node::new_branch(new_right, self.clone().rightmost_child));
                return (new_branch, true);
                                         
            }
        }
        (new_branch, outcome)
    }

Here, we ask ourselves if there was any “outcome” from adding: did we actually add a new element into the tree, and do we now need to resize?  If we do need to resize, we will have returned a Branch containing a single element, as you have seen at the Leaf level.  We now search the Branch to find where in the Branch this new element would go, and perform a similar maneuver as with the Leaf: if the vector elts is too large, pop out the middle and return it.  This process continues until either we return false (and then we rocket up the tree back to the BTree level, where we return self), or until we have a new root, which we reassign to the root container in the topmost level, BTree.

Pretty simple, right?  I hope to be able to take out all the clone()s, which ensure that the code passes the borrow-checker–Rust as a language is committed to memory safety, so it doesn’t let you do anything that might be potentially silly with respect to memory.  This means that once an object is used in another application, it can’t be used again.  For example, if I were to call Node::add on self.root, that would be the last time I could use it in that function, unless I use clone(), which makes a new, deep copy of the object, or I am very tricky in ways I have not yet discovered.  There is a whole mess of commented-out code that you don’t see here that represents my efforts to perform this method without using clone and while appeasing the compiler.  Turns out, some of Rust’s handy builtins don’t work exactly the way I thought they would, which is kind of a bummer.  I decided to stop and switch gears for the moment, and above, you see the results.  Pretty nifty!

Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s