gistfile1.txt

///////////////////////////////////////////////////////////////////////////
// The iterator trait

trait MutIterator<T> {
    fn has_next(&self) -> bool;
    fn next<'a>(&'a mut self) -> &'a mut T;
}

///////////////////////////////////////////////////////////////////////////
// Implementation for vectors (easy)

struct MutSliceIterator<'self, T> {
    v: &'self mut [T],
    pos: uint,
}

impl<'self, T> MutIterator<T> for MutSliceIterator<'self, T> {
    fn has_next(&self) -> bool {
        self.pos == self.v.len()
    }

    fn next<'a>(&'a mut self) -> &'a mut T {
        if self.pos == self.v.len() {
            fail!("next() called when has_next() is false");
        }
        let p = self.pos;
        self.pos += 1;
        &mut self.v[p]
    }
}

//////////////////////////////////////////////
// Implementation for a binary tree (pre-order, trickier)

struct BinaryTree<T> {
    value: T,
    left: Option<~BinaryTree<T>>,
    right: Option<~BinaryTree<T>>,
}

impl<T> BinaryTree<T> {
    fn iterator<'a>(&'a mut self) -> BinaryTreePreorderMutIterator<'a, T> {
        BinaryTreePreorderMutIterator {
            stack: ~[self]
        }
    }
}

struct BinaryTreePreorderMutIterator<'self,T> {
    stack: ~[&'self mut BinaryTree<T>],
}

impl<'self,T> MutIterator<T> for BinaryTreePreorderMutIterator<'self,T> {
    fn has_next(&self) -> bool {
        !self.stack.is_empty()
    }

    fn next<'a>(&'a mut self) -> &'a mut T {
        if !self.has_next() {
            fail!("next() called when has_next() is false");
        }

        let cur = self.stack.pop();

        match cur.right {
            None => {}
            Some(~ref mut r) => {
                self.stack.push(r);
            }
        }

        match cur.left {
            None => {}
            Some(~ref mut l) => {
                self.stack.push(l);
            }
        }

        &mut cur.value
    }
}

#[cfg(test)]
fn check_iter<V:Eq>(mut iter: BinaryTreePreorderMutIterator<V>,
                    values: &[V]) {
    let mut counter = 0_u;
    while iter.has_next() {
        let next = iter.next();
        if *next != values[counter] {
            fail!(fmt!("Index %u yielded %? not %?",
                       counter, *next, values[counter]));
        }
        counter += 1_u;
    }
    assert_eq!(counter, values.len());
}

#[test]
pub fn preorder1() {
    let mut the_tree = BinaryTree {
        value: "r",
        left: Some(~BinaryTree {
            value: "r.l",
            left: None,
            right: Some(~BinaryTree {
                value: "r.l.r",
                left: None,
                right: None
            }),
        }),
        right: Some(~BinaryTree {
            value: "r.r",
            left: Some(~BinaryTree {
                value: "r.r.l",
                left: None,
                right: None,
            }),
            right: Some(~BinaryTree {
                value: "r.r.r",
                left: None,
                right: None
            }),
        }),
    };

    check_iter(the_tree.iterator(),
               ["r", "r.l", "r.l.r", "r.r", "r.r.l", "r.r.r"]);
}

fn main() {}