Sorted vector uniquification

gistfile1.rs

import core::cmp::{Eq,Ord};

mod exhibitA {
    fn unique<T: copy Eq>(&v: ~[mut T]) {
        let mut i_dst = 0, i_src = 1;
        let ln = v.len();
        if ln < 1 { return; }
        while i_src < ln {
            if !v[i_src].eq(v[i_dst]) {
                i_dst += 1;
                if (i_src != i_dst) {
                    v[i_dst] = v[i_src];
                }
            }
            i_src += 1;
        }
        i_dst += 1;
        vec::truncate(v, i_dst);
    }

    fn unique_noncopy<T: Eq>(&v: ~[mut T]) {
        let mut i_dst = 0, i_src = 1;
        let ln = v.len();
        if ln < 1 { return; }
        while i_src < ln {
            if !v[i_src].eq(v[i_dst]) {
                i_dst += 1;
                if (i_src != i_dst) {
                    v[i_dst] <-> v[i_src];
                }
            }
            i_src += 1;
        }
        i_dst += 1;
        vec::truncate(v, i_dst);
    }
}

mod exhibitB {
    import vec::*;

    fn unique<T: Eq>(&v: ~[mut T]) {
        if v.len() < 1 { return; }
        let mut i_dst = 0, i_src = 1;
        unsafe {
            do as_mut_buf(v) |p, ln| {
                // i_dst < i_src <= ln
                while i_src < ln {
                    // i_dst < i_src < ln
                    if *ptr::mut_offset(p, i_src) ==
                        *ptr::mut_offset(p, i_dst) {
                        let _dropped <- *ptr::mut_offset(p, i_src);
                    } else {
                        i_dst += 1;
                        // i_dst <= i_src < ln
                        if i_src != i_dst {
                            *ptr::mut_offset(p, i_dst) <- 
                                *ptr::mut_offset(p, i_src);
                        }
                    }
                    i_src += 1;
                }
            }
            // i_dst < i_src == ln
            unsafe::set_len(v, i_dst + 1);
        }
    }
}

#[cfg(test)]
use std;

#[test]
fn test_unique() {
    fn case(-a: ~[uint], -b: ~[uint]) {
        let mut v = vec::to_mut(a);
        exhibitB::unique(v);
        assert(v == vec::to_mut(b));
    }
    case(~[], ~[]);
    case(~[1], ~[1]);
    case(~[1,1], ~[1]);
    case(~[1,2,3], ~[1,2,3]);
    case(~[1,1,2,3], ~[1,2,3]);
    case(~[1,2,2,3], ~[1,2,3]);
    case(~[1,2,3,3], ~[1,2,3]);
    case(~[1,1,2,2,2,3,3], ~[1,2,3]);
}

#[test]
fn test_unique_unique() {
    impl ~int : Eq {
        pure fn eq(&&other: ~int) -> bool { *self == *other }
    }

    let mut v0 = ~[mut ~1, ~1, ~2, ~3];
    exhibitB::unique(v0);
    let mut v1 = ~[mut ~1, ~2, ~2, ~3];
    exhibitB::unique(v1);
    let mut v2 = ~[mut ~1, ~2, ~3, ~3];
    exhibitB::unique(v2);
}

#[test]
fn test_unique_shared() {
    impl @int : Eq {
        pure fn eq(&&other: @int) -> bool { *self == *other }
    }

    let mut v0 = ~[mut @1, @1, @2, @3];
    exhibitB::unique(v0);
    let mut v1 = ~[mut @1, @2, @2, @3];
    exhibitB::unique(v1);
    let mut v2 = ~[mut @1, @2, @3, @3];
    exhibitB::unique(v2);
}