linkedhashset.rs

use std::collections::{dlist, DList, HashSet, Deque};
use std::hash::Hash;
use std::iter;
use std::default::Default;

pub struct LinkedHashSet<'a, T: 'a> where T: Hash + Eq {
    // Important: HashSet must come after DList, since destructors run in
    // reverse order.  Otherwise we'd have use after free (potentially).
    element_list: DList<T>,
    element_set: HashSet<&'a T>,
}

pub type Items<'a, T> = iter::Map<'a, &'a T, &'a T, dlist::Items<'a, T>>;

impl<'a, T> LinkedHashSet<'a, T> where T: Hash + Eq + Default {
    /// Create a new LinkedHashSet
    pub fn new() -> LinkedHashSet<'a, T> {
        let mut element_list = DList::new();
        element_list.push(Default::default());
        LinkedHashSet {
            element_list: element_list,
            element_set: HashSet::new(),
        }
    }

    /// Insert an element into the set. Returns true if the element was not already in the set.
    pub fn insert<'b>(&'b mut self, mut el: T) -> bool {
        {
            // Should always succeed since there should always be at least one element in the list.
            let new_el = self.element_list.front_mut().unwrap();
            std::mem::swap(new_el, &mut el);
            // The safety of this is dependent on us to maintain a bunch of invariants, but it is
            // safe with the current API.  If we were to allow mutation of the elements, we'd
            // probably want to use UnsafeCell<T> rather than T as the DList type.
            if !self.element_set.insert(unsafe { ::std::mem::transmute(new_el) }) {
                return false
            }
        }
        // Move the build-in-place element to to the end of the list, then add a new element to
        // the front.  The reason we build in front instead of at the back is to make it easier to
        // return the appropriate iterator (without extra checks for length etc.).  Even more ideal
        // would be to build outside the list altogether, but with the current DList API that's not
        // really possible.
        self.element_list.rotate_backward();
        self.element_list.push_front(el);
        true
    }

    pub fn iter<'a>(&'a self) -> Items<'a, T> {
        let mut iter = self.element_list.iter();
        iter.next();
        iter.map(|ptr| ptr)
    }
}

fn main() {
    let mut set = LinkedHashSet::new();
    for i in range(0,100u8) {
        set.insert(i % 30);
    }

    for el in set.iter() {
        println!("{}", el);
    }
}