# Collection Traits, Take 2

**URL:** <https://internals.rust-lang.org/t/collection-traits-take-2/1272>\
**Category:** Uncategorized\
**Created:** [January 11, 2015, 6:10pm UTC](https://internals.rust-lang.org/t/collection-traits-take-2/1272 "2015-01-11T18:10:11Z")\
**Posts on this page:** 1\
**Showing post:** 15

<div class="post-metadata">

**Author:** ![Gankra](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/gankra/32/6002_2.png) [@Gankra](https://internals.rust-lang.org/u/Gankra)\
**Post date:** [January 23, 2015, 12:25am UTC](https://internals.rust-lang.org/t/collection-traits-take-2/1272/15 "2015-01-23T00:25:22Z")

</div>

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

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

```

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

```

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

```

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

```

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

```

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

```

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

```

```rust
// PriorityQueue same as Stack and Queue

```

```rust
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>;
}

```

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

```

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

```

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

```

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

```

```rust
trait SortedMap: 
    Map 
{}

```

```rust
trait SortedMutableMap: 
    SortedMap, 
    MutableMap,
{}

```

```rust
// 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.

---

_[View the full topic](https://internals.rust-lang.org/t/collection-traits-take-2/1272)._