libcollections traits 0.1

gistfile1.rs

pub trait Collection {
    fn len(self) -> uint;
    fn is_empty(&self) -> bool; //defaulted
}

pub trait Mutable: Collection {
    fn clear(&mut self);
}

pub trait Container<T>: Collection {
    fn foreach(&self, f: |&T|);
}

pub trait MutableContainer<T>: Container<T> + Mutable {
    fn foreach_move(self, f:|T|);

    fn swap (&mut self, value: T) -> Option<T>; //only really meaningful for Sets?

    fn insert(&mut self, value: T) -> bool; // defaulted

    fn insert_all <C: MutableContainer> (&mut self, other: C); // defaulted
}

pub trait SearchableContainer <T> : Container<T> {
    fn contains(&self, value: &T) -> bool; // defaulted if T is partialeq
    fn contains_all <C: Container<T>> (&self, other: &C); // defaulted
}

pub trait MutableSearchableContainer <T> : MutableContainer<T> {
    fn pop(&mut self, value: &T) -> Option<T>; 
    fn remove(&mut self, value: &T) -> bool; // defaulted
    fn remove_all <C: Container> (&mut self, other: &C); // defaulted
    fn retain_all <C: Container> (&mut self, other: &C); // defaulted
}

pub trait SortedContainer<T>: SearchableContainer<T> {
    // constructors for comparators??
    
    fn foreach_sorted(&self, f: |&T|); // bounded range variants?

    fn min <'a> (&'a self) -> Option<&'a T> // defaulted
    fn max <'a> (&'a self) -> Option<&'a T> // defaulted

    fn lower_bound_exclusive(&self, value: &T) -> Option<T>; // defaulted for partial ord
    fn lower_bound_inclusive(&self, value: &T) -> Option<T>; // defaulted for partial ord
    fn upper_bound_exclusive(&self, value: &T) -> Option<T>; // defaulted for partial ord
    fn upper_bound_inclusive(&self, value: &T) -> Option<T>; // defaulted for partial ord
}

pub trait MutableSortedContainer: MutableSearchableContainer<T> {
    fn foreach_sorted_move(self, f:|T|); // bounded range variants?

    fn pop_min(&self) -> Option<T> // defaulted
    fn pop_max(&self) -> Option<T> // defaulted
}


pub trait Set<T>: SearchableContainer<T> {
    fn is_disjoint(&self, other: &Self) -> bool; //defaulted
    fn is_subset(&self, other: &Self) -> bool; //defaulted
    fn is_superset(&self, other: &Self) -> bool; //defaulted
}

pub trait MutableSet<T>: Set<T> + MutableSearchableContainer<T> {
}

pub trait Queue<T> : MutableContainer<T> {
    fn enqueue (&mut self, value: T);
    fn dequeue (&mut self) -> Option<T>;
    fn peek <'a> (&'a self) -> Option<&'a T>;
}

pub trait Stack<T> : MutableContainer<T> {
    fn push (&mut self, value: T);
    fn pop (&mut self) -> Option<T>;
    fn top <'a> (&'a self) -> Option<&'a T>;
}

pub trait Deque<T> : MutableContainer<T> { //default impls for Stack<T> and Queue<T>
    fn front<'a>(&'a self) -> Option<&'a T>;
    fn front_mut<'a>(&'a mut self) -> Option<&'a mut T>;
    fn back<'a>(&'a self) -> Option<&'a T>;
    fn back_mut<'a>(&'a mut self) -> Option<&'a mut T>;
    fn push_front(&mut self, elt: T);
    fn push_back(&mut self, elt: T);
    fn pop_back(&mut self) -> Option<T>;
    fn pop_front(&mut self) -> Option<T>;
}

pub trait List<T> : Container<T> {
    //indexed variants of foreaches?

    fn get <'a> (&'a self, index: uint) -> Option<&'a T>;
}

pub trait MutableList <T> : List<T> + MutableContainer<T> {
    //splice operation?
    fn swap_at (&mut self, index: uint, value: T) -> Option<T>; // possibly ill-advised? Unclear on how to handle padding
    fn insert_at (&mut self, index: uint, value: T) -> bool; //defaulted 
    fn pop_at (&mut self, index: uint) -> Option<T>;
    fn remove_at (&mut self, index: uint) -> bool; //defaulted
}

pub trait SearchableList<T> : List<T> + SearchableContainer<T> {
    fn index_of (&self, value: &T) -> Option<uint>;
    fn last_index_of (&self, value: &T) -> Option<uint>;
}




pub trait Map<K, V>: Collection {
    fn foreach(&self, f: |(&K, &V)|);

    fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
    fn contains_key(&self, key: &K);
}

pub trait MutableMap<K, V>: Map<K, V> + Mutable {
    fn foreach_mut(&mut self, f:|(&K, &mut V)|);
    fn foreach_move(self, f:|(K, V)|);

    fn swap(&mut self, k: K, v: V) -> Option<V>;
    fn pop(&mut self, k: &K) -> Option<V>;

    fn insert(&mut self, key: K, value: V) -> bool; //defaulted
    fn remove(&mut self, key: &K) -> bool; //defaulted

    fn insert_all <M:MutableMap> (&mut self, other: M); //defaulted
    fn remove_all <M:Map> (&mut self, other: &M); //defaulted
    fn retain_all <M:Map> (&mut self, other: &M); //defaulted

    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
}

pub trait SortedMap<K,V>: Map {
    // constructors for comparators??

    fn foreach_sorted(&self, f: |(&K, &V)|);

    fn min <'a> (&'a self) -> Option<(&'a K, &'a V)>; //defaulted
    fn max <'a> (&'a self) -> Option<(&'a K, &'a V)>; //defaulted
}

pub trait SortedMutableMap<K,V> : MutableMap {
    fn foreach_sorted_mut(&mut self, f:|(&K, &mut V)|);
    fn foreach_sorted_move(self, f:|(K, V)|);

    fn pop_min(&mut self) -> Option<(K, V)>;
    fn pop_max(&mut self) -> Option<(K, V)>;

    //ugh, and I guess mut variants (key only) too??
    fn lower_bound_exclusive(&self, value: &K) -> Option<(&K, &V)>; //defaulted
    fn lower_bound_inclusive(&self, value: &K) -> Option<(&K, &V)>; //defaulted
    fn upper_bound_exclusive(&self, value: &K) -> Option<(&K, &V)>; //defaulted
    fn upper_bound_inclusive(&self, value: &K) -> Option<(&K, &V)>; //defaulted
}




pub trait PriorityQueue<T> : Mutable { // Not *really* a Queue
    //constructor for comparator?
    
    fn enqueue (&mut self, value: T);
    fn dequeue (&mut self) -> Option<T>;
    fn peek <'a> (&'a self) -> Option<&'a T>;
}

What does

pub trait MutableContainer<T>: Container<T> + Mutable {
    fn swap (&mut self, value: T) -> Option<T>; //only really meaningful for Sets?
    // ...
}

do?

I can understand a swap() that takes two elements in some ordered structure and swaps them, and I can maybe understand one that takes an index in some indexable structure and swaps it with another element. I don't know how you can just send a value generically into some mutable collection and "swap" it with anything.

@nathantypanski: For a collection like a Set, swap will return any old value that would have been overwritten by the new one. Sets can be HashSets or TreeSets, the former having no particular structure to the user. Hence my note of "only really meaningful for Sets?". But I didn't want to say "only sets have this", in case I was forgetting some exotic (or simple) structure that would want this. Maybe like a limited capacity ringbuffer might want it. If it gets full and starts eating itself, I'd rather get back the stuff that's falling out, rather than just lose it. For most structures I would always expect this to return None, and insert to consequently always return true.

It swaps out an existing value or just inserts a new one. This name has confusing connotations.