treemap's lazy iterator needs to be optimized

[thestinger]

Going back to the old way isn't currently possible (without multiple lifetime parameters), but it's currently doing implicit copies of the pointer stack with every iteration which should be fixable.

[nikomatsakis]

Strictly speaking multiple lifetime parameters are not required to use a more traditional iterator. However, the current handling of the self region is problematic. Here is a proof of concept that I got to compile, but it doesn't work with impls because they always conflate the self region with the lifetime parameter. This is actually a known issue I plan to address, I will open a bug describing it.

The key point is that the next() function does not use the same lifetime for the &mut Iterator pointer as for its contents:

fn next<T>(iter: &mut Iterator/&a<T>) -> bool {
    iter.index += 1; // Relies on rollover
    iter.index < iter.vector.len()
}

Note: I changed the iterator protocol here to use a bool return on next() rather than returning an Option from get. This is not necessary, it was to see which style I preferred. Probably best, ultimately, would be to offer two methods or something like that.

extern mod std;

use std::treemap;

struct Iterator<T> {
    vector: &[T],
    index: uint
}

fn iter<T>(v: &v/[T]) -> Iterator/&v<T> {
    Iterator {vector: v, index: uint::max_value}
}

fn next<T>(iter: &mut Iterator/&a<T>) -> bool {
    iter.index += 1; // Relies on rollover
    iter.index < iter.vector.len()
}

fn get<T>(iter: &v/Iterator<T>) -> &v/T {
    &iter.vector[iter.index]
}

fn is_disjoint(t1: &[int], t2: &[int]) -> bool {
    let mut x = iter(t1);
    let mut y = iter(t2);

    if !next(&mut x) { return true; }
    if !next(&mut y) { return true; }

    loop {
        let advance_x = {
            let a = get(&x);
            let b = get(&y);
            if *a < *b {
                true
            } else if *b < *a {
                false
            } else {
                return false;
            }
        };

        if advance_x {
            if !next(&mut x) {
                return true;
            }
        } else if !next(&mut y) {
            return true;
        }
    }
}

fn main() {
    assert is_disjoint([1, 3, 5], [2, 4, 6]);
    assert !is_disjoint([1, 3, 5], [2, 4, 5]);
    assert is_disjoint([], []);
    assert is_disjoint([1, 2], []);
    assert is_disjoint([], [1, 2]);
}