btree.rs

//! A B-tree is a tree data structure that keeps data sorted and allows
//! searches, sequential access, insertions, deletions in logarithmic time.
//! B-trees are different from binary search trees because a b-tree node can
//! have more than two children (also known as the *degree* of a b-tree).
//!
//! Basic example:
//!
//! ~~~ rust
//! let mut s = BTree::new();
//!
//! s.insert(1, "foo");
//! s.insert(42, "bar");
//!
//! assert_eq!(s.find(1), &"foo");
//! assert_eq!(s.find(42), &"bar");
//! ~~~

#[link(name="btree", vers="0.1pre",
       uuid="136fafb0-e4e0-11e2-a28f-0800200c9a66")];

//use std::vec::VecIterator;
//use std::util::{swap, replace};
use std::util::replace;

// The number of keys is chosen to vary between d and 2d, where d is the
// minimum number of keys and d+1 is the minimum degree (branching factor) of
// the tree. In this case, d = 2 which results in degree = 5.
static BTREE_DEGREE : uint = 5;

pub struct BTree<'self, K, V> {
    priv nodes: [Option<TreeItem<'self, K, V>>, ..BTREE_DEGREE],
}

enum TreeItem<'self, K, V> {
    TreeNode { key: K, value: ~BTree<'self, K, V> },
    TreeLeaf { key: K, value: &'self V },
}

//pub struct TreeNode<K, V> {
//    key: K,
//    node: Option<BTree<K, V>>,
//    leaf: Option<TreeLeaf<K, V>>,
//}
//
//pub struct TreeLeaf<K, V> {
//    key: K,
//    value: V,
//}

impl<'self, K: Eq + Ord, V> Container for BTree<'self, K, V> {
    /// Return the number of nodes or values in the b-tree node
    #[inline]
    fn len(&self) -> uint { self.nodes.len() }

    /// Return true if the b-tree node contains no nodes or values
    #[inline]
    fn is_empty(&self) -> bool {
        match *self.nodes.head() {
            None => { true }
            _ => { false }
        }
    }
}

impl<'self, K: TotalOrd, V> Mutable for BTree<'self, K, V> {
    /// Clear the b-tree, removing all nodes.
    fn clear(&mut self) {
        for self.nodes.mut_iter().advance |node| {
            match *node {
                None => {
                    break;
                }
                _ => {
                    *node = None;
                }
            }
        }
    }
}

impl<'self, K: Eq + Ord, V> BTree<'self, K, V> {
    pub fn new() -> BTree<K, V> {
        // TODO: once https://github.com/mozilla/rust/issues/5244 is fixed,
        // use the following statement:
        //BTree { nodes: ~[None, ..BTREE_DEGREE] }
        BTree { nodes: [None, None, None, None, None] }
    }

    pub fn find<'a> (&'a self, key: K) -> Option<&'a V> {
        // TODO: implement find
        None
    }

    /// Insert a key-value pair into the b-tree.
    pub fn insert(&mut self, key: K, value: V) -> bool {
//        let mut node = &None;
//
//        if self.is_empty() {
//            self.nodes[0] = TreeLeaf { key: key, value: &None};
//            node = &self.nodes[0];
//        }
//
//        match node {
//            &TreeLeaf { key: _, value: ref mut v } => {
//                replace(v, &value);
//            }
//            _ => {
//
//            }
//        }
//
        true
    }
}

// // TODO: get leaf instead of node?
// /// Return the node found with the key. If there is no node found for the key,
// /// the node is created and inserted at the proper location in the b-tree.
// fn get_insert_node<'r, K: Eq + Ord, V>(tree: &'r mut BTree<'r, K, V>, key: K)
//     -> &'r TreeItem<'r, K, V> {
// 
//     //if tree.nodes.head().is_none() {
//     if tree.is_empty() {
//         tree.nodes[0] = None; //TreeLeaf { key: key, value: &None};
//         return &tree.nodes[0];
//     }
// 
//     //for tree.nodes.mut_iter().advance |pair| {
// 
//     //}
// 
//     &None
// }