Before we finalize everything forever, I figured we should quickly reflect on what we want to collection traits to look like. So here’s a quick sketch of the minimal API I think we should provide. Some notable points:
- Everything is associated types; nothing should plausibly be a collection of more than one type at once.
- Very little inherits from anything else. This might be unergonomic (wrangling that foo is a Stack and Seq with the same Elem type). Not sure if we should mandate that e.g. all Deques are Sequences. We currently explicitly don’t provide indexing into DLists. Although I don’t really agree with that, I “get” why. Also it probably makes sense to mandate that Sequences and Maps have appropriate Index impls?
- I use a notion of an “inherent” impl which is an idea that has been kicking around for some time. Basically, RingBuf would inherently expose the Deque interface even if the trait is unavailable, but not Stack or Queue. In this way we nudge you to picking a particular “view” of the collection and sticking with it. Deques are only Deques unless you explicitly ask for the other interfaces.
- These traits have no support for “immutable” collections. They assume collections can be mutated. I wasn’t sure what the best way to handle immutable collections would be without including an Immutable and Mutable version of every single trait. Perhaps an associated Item (
IsMutable=true?) and some where clauses could handle this well? - There traits can’t really be expressed correctly because of iterator types and something something HKT.
- Mandating basic iter/iter_mut/into_iter support is going to be tricky because of weird cases like
Bitvwhich you can’t get references into. Just having the Iterable traits on the side might be the right call here? - Stack plays a bit funky with Vec because it would have
lastandpeekdue to its slice-ness. Although maybe all Seq’s should havefirstandlast?
trait Stack {
type Elem;
fn push(&mut self, elem: Elem);
fn pop(&mut self) -> Option<Elem>;
fn peek(&self) -> Option<&Elem>;
}
trait Queue {
type Elem;
fn enqueue(&mut self, elem: Elem);
fn dequeue(&mut self) -> Option<Elem>;
fn peek(&self) -> Option<&Elem>;
}
trait Deque {
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 Seq {
type Elem;
fn insert(&mut self, index: usize, elem: Elem);
fn remove(&mut self, index: usize) -> elem: Elem;
fn get(&self, index: usize) -> Option<&Elem>;
fn get_mut(&mut self, index: usize) -> Option<&mut Elem>;
}
trait Map {
type Key;
type Val;
fn insert(&mut self, key: Key, val: Val) -> Option<Val>;
fn remove<Q>(&mut self, key: &Q) -> Option<Val>
where Key: Borrow<Q>;
fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut Val>
where Key: Borrow<Q>;
fn get<Q>(&self, key: &Q) -> Option<&Val>
where Key: Borrow<Q>;
fn contains_key<Q>(&self, key: &Q) -> bool
where Key: Borrow<Q> {
self.get(key).is_some()
}
}
trait SortedMap: Map {
type Range;
type RangeMut;
fn range<Q, R>(&self, Bound<Q>, Bound<R>) -> Range
where Key: Borrow<Q> + Borrow<R>;
fn range_mut<Q, R>(&mut self, Bound<Q>, Bound<R>) -> RangeMut
where Key: Borrow<Q> + Borrow<R>;
}
trait Set {
type Elem;
type Union;
type Intersection;
type Difference;
type SymmetricDifference;
fn insert(&mut self, elem: Elem) -> bool;
fn remove<Q>(&mut self, elem: &Q) -> bool
where Key: Borrow<Q>;
fn contains<Q>(&mut self, elem: &Q) -> bool
where Key: Borrow<Q>;
// all the set-theoretic ops
}
trait SortedSet: Set {
type Range;
type RangeMut;
fn range<Q, R>(&self, Bound<Q>, Bound<R>) -> Range
where Elem: Borrow<Q> + Borrow<R>;
fn range_mut<Q, R>(&mut self, Bound<Q>, Bound<R>) -> RangeMut
where Elem: Borrow<Q> + Borrow<R>;
}
trait PriorityQueue {
type Elem;
fn push(&mut self, elem: Elem);
fn pop(&mut self) -> Option<Elem>;
fn peek(&self) -> Option<&Elem>;
}
inherent impl Stack for Vec;
inherent impl Seq for Vec;
inherent impl Deque for RingBuf;
impl Stack for RingBuf;
impl Queue for RingBuf;
inherent impl Seq for RingBuf;
inherent impl Deque for DList;
impl Stack for DList;
impl Queue for DList;
inherent impl Seq for DList;
inherent impl Stack for Bitv;
inherent impl Seq for Bitv;
inherent impl Map for HashMap;
inherent impl Map for BTreeMap;
inherent impl SortedMap for BTreeMap;
inherent impl Map for VecMap;
inherent impl SortedMap for VecMap;
inherent impl Set for HashSet;
inherent impl Set for BTreeSet;
inherent impl SortedSet for BTreeSet;
inherent impl Set for BitvSet;
inherent impl SortedSet for BitvSet;
inherent impl PriorityQueue for BinaryHeap;