Collection Traits, Take 2

15

Based on my fever-dreams of hyper-overloaded indexing, here’s a different structuring of the traits (now with mutable variants):

trait Collection {
  fn len(&self) -> usize;
  fn is_empty(&self) -> bool { ... }
}

trait Get<Index> {
    type Output;
    fn get(&self, i: Index) -> Output;
}

trait GetMut<Index> {
    type Output;
    fn get(&self, i: Index) -> Output;
}

trait Insert<Index, Val> {
    type Output;
    fn insert(&self, i: Index, v: Val) -> Output;
}

trait Remove<Index> {
    type Output;
    fn remove(&self, i: Index, v: Val) -> Output;
}

trait Stack: 
    Collection 
{
    type Elem;
    fn push(&mut self, elem: Elem);
    fn pop(&mut self) -> Option<Elem>;
    fn peek(&self) -> Option<&Elem>;
}

trait Queue: 
    Collection 
{
    type Elem;
    fn push(&mut self, elem: Elem);
    fn pop(&mut self) -> Option<Elem>;
    fn peek(&self) -> Option<&Elem>;
}

// PriorityQueue same as Stack and Queue

trait Deque:
    Collection 
{
    type Elem;
    fn push_back(&mut self, elem: Elem);
    fn push_front(&mut self, elem: Elem);
    fn pop_back(&mut self) -> Option<Elem>;
    fn pop_front(&mut self) -> Option<Elem>;
    fn front(&self) -> Option<&Elem>;
    fn back(&self) -> Option<&Elem>;
}

trait Sequence: 
    Collection
    Get<usize, Option<&Elem>>.
    Index<usize, Elem>, 
{
    type Elem;
}

trait MutableSequence: 
    Sequence, 
    GetMut<usize, Option<&mut Elem>>,
    IndexMut<usize, Val>
    Insert<usize, Elem, ()>,
    Remove<usize, Option<Elem>>, 
    IndexMut<usize, Elem>,
{}

trait Map:
    Collection
    Get<&Key, Option<&Val>>, 
    Index<&Key, Val>,
{
    type Key;
    type Val;
    
    fn contains_key(&self, &Key) { ... }
}

trait MutableMap:
    Map,
    GetMut<&Key, Option<&mut Val>>,
    IndexMut<&Key, Val>>,
    Insert<Key, Val, Option<Val>>,
    Remove<&Key, Option<Val>>,
{}

trait SortedMap: 
    Map 
{}

trait SortedMutableMap: 
    SortedMap, 
    MutableMap,
{}

// Set mirrors Map structure accordingly

Notes:

  • I’m hand-waving HKT and self-lifetime stuff here, assuming it’s solved when we get to this point.
  • I’m handwaving that you can refer to associated type positionally in generics for convenience
  • Stack, Queue, and Deque have no Mutable variant because I don’t think that’s useful.
  • Better composition! \o/
  • Insert is a bit awkward because the semantics of Sequence insertion and Map insertion are different (sequence shifts, Map replaces). Still, I want a trait so that you can overload it to insert e.g. an IntoIterator at an index for sequences. Maybe there should be two traits. Or maybe maps shouldn’t use the trait (I don’t think they can use overloaded insert quite as much?)
  • I have, perhaps dubiously, given Stack and Queue identical method names. This may be a problem if you have a concrete Deque in scope and both Stack and Queue imported. Otherwise I think it’s a nice consistency bonus.
  • I’m not sure what to guarantee iteration-wise in these traits. In particular Bitv and BitvSet can’t return anything by-reference (modulo the static TRUE: bool = true trick). It’s possible for e.g. a Trie to have similar behaviour for its keys. Especially if we go forward with a Integer-like-key trait.