// https://play.rust-lang.org/?gist=e29150c80d38074be5642f4bc451830e&version=stable

trait ContainerFamily<T: 'static> {
    type Container: for<'a> Container<'a, Item = T>;
    fn new() -> Self::Container;
}

trait Container<'a> {
    type Item: 'a;
    type IterMut: Iterator<Item = &'a mut Self::Item>;
    fn push(&mut self, item: Self::Item);
    fn iter_mut(&'a mut self) -> Self::IterMut;
}

#[derive(Copy, Clone)]
struct VecFamily;

impl<T: 'static> ContainerFamily<T> for VecFamily {
    type Container = Vec<T>;
    fn new() -> Self::Container {
        Vec::new()
    }
}

impl<'a, T: 'a> Container<'a> for Vec<T> {
    type Item = T;
    type IterMut = ::std::slice::IterMut<'a, T>;
    fn push(&mut self, item: Self::Item) {
        self.push(item);
    }
    fn iter_mut(&'a mut self) -> Self::IterMut {
        self.as_mut_slice().iter_mut()
    }
}

use std::collections::{linked_list, LinkedList};

#[derive(Copy, Clone)]
struct LinkedListFamily;

impl<T: 'static> ContainerFamily<T> for LinkedListFamily {
    type Container = LinkedList<T>;
    fn new() -> Self::Container {
        LinkedList::new()
    }
}

impl<'a, T: 'a> Container<'a> for LinkedList<T> {
    type Item = T;
    type IterMut = linked_list::IterMut<'a, T>;
    fn push(&mut self, item: Self::Item) {
        self.push_back(item);
    }
    fn iter_mut(&'a mut self) -> Self::IterMut {
        self.iter_mut()
    }
}

struct SomeSlab<T, CF>
where
    T: 'static,
    CF: ContainerFamily<Option<T>> + ContainerFamily<usize>,
{
    container: <CF as ContainerFamily<Option<T>>>::Container,
    slot_alloc_count: <CF as ContainerFamily<usize>>::Container,
}

impl<T: 'static> SomeSlab<T, VecFamily> {
    pub fn new() -> Self {
        SomeSlab::with_container_family(VecFamily)
    }
}

impl<T, CF> SomeSlab<T, CF>
where
    T: 'static,
    CF: ContainerFamily<Option<T>> + ContainerFamily<usize>,
{
    pub fn with_container_family(_: CF) -> Self {
        Self {
            container: <CF as ContainerFamily<Option<T>>>::new(),
            slot_alloc_count: <CF as ContainerFamily<usize>>::new(),
        }
    }

    pub fn put(&mut self, item: T) -> usize {
        let mut index = 0;
        for (element, alloc_count) in self.container
            .iter_mut()
            .zip(self.slot_alloc_count.iter_mut())
        {
            if element.is_none() {
                *element = Some(item);
                *alloc_count += 1;
                return index;
            }
            index += 1;
        }
        self.container.push(Some(item));
        self.slot_alloc_count.push(1);
        index
    }

    pub fn take(&mut self, id: usize) -> Option<T> {
        for (index, element) in self.container.iter_mut().enumerate() {
            if index == id {
                return element.take();
            }
        }
        None
    }

    pub fn print_slots(&mut self)
    where
        T: ::std::fmt::Debug,
    {
        print!("[");
        for (index, element) in self.container.iter_mut().enumerate() {
            if index != 0 {
                print!(", ");
            }
            print!("{:?}", element);
        }
        println!("]");
    }
}

fn main() {
    let mut slab = SomeSlab::new();

    let five = slab.put(5);
    let ten = slab.put(10);
    slab.put(3);

    println!("{:?}", slab.take(five));
    println!("{:?}", slab.take(ten));

    slab.put(12);
    let fifteen = slab.put(15);
    slab.put(20);

    slab.take(fifteen);

    slab.print_slots();

    // ===================================================

    let mut slab = SomeSlab::with_container_family(LinkedListFamily);

    let five = slab.put("5");
    let ten = slab.put("10");
    slab.put("3");

    println!("{:?}", slab.take(five));
    println!("{:?}", slab.take(ten));

    slab.put("12");
    let fifteen = slab.put("15");
    slab.put("20");

    slab.take(fifteen);

    slab.print_slots();
}