use std::collections::{BTreeMap};
use std::collections::btree_map;

pub struct JoinedIter<'a, K: 'a, A: 'a, B: 'a> {
    left: btree_map::Iter<'a, K, A>,
    right: btree_map::Iter<'a, K, B>,
}

impl<'a, K, A, B> Iterator for JoinedIter<'a, K, A, B>
    where K: Ord
{
    type Item = (&'a K, (&'a A, &'a B));

    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
        let mut l = self.left.next();
        let mut r = self.right.next();
        loop {
            match (l, r) {
                (None, _) => return None,
                (_, None) => return None,
                (Some((lk, lv)), Some((rk, rv))) => {
                    if lk < rk {
                        l = self.left.next();
                    } else if rk < lk {
                        r = self.right.next();
                    } else {
                        return Some((lk, (lv, rv)));
                    }
                }
            }
        }
    }
}

// An `Entity` is an abstract 64-bit quantity. Nothing outside this
// module should care what an entity is or how it works.
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Entity {
    idx: u64,
}

// But for here, I'm borrowing an idea from here:
// http://bitsquid.blogspot.com/2014/08/building-data-oriented-entity-system.html
// the tl;dr (and it's not explained super well there) is that we want
// an easy way of retiring an entity and also finding out whether an
// entity is retired. The way we do this involves splitting the entity
// into two quantities: the generation (which is just 8 bits) and the
// index (which is the rest.) The logic to do so is pretty simple, as
// below.
impl Entity {
    fn new(generation: u8, index: u64) -> Entity {
        Entity { idx: (index << 8) | generation as u64 }
    }

    fn generation(self) -> u8 {
        (self.idx & 0xf) as u8
    }

    fn index(self) -> u64 {
        self.idx >> 8
    }
}


// An `EntityMgr` is the type that knows how to create and destroy
// entities. It ain't thread-safe now---I'll think about that
// later. It has two values: one of them is the `generation` vec,
// which will get extended as new _fresh_ values are created, and the
// other is the `free_indices` list, which will get extended as new
// values are destroyed.
pub struct EntityMgr {
    generation: Vec<u8>,
    free_indices: Vec<u64>,
}

impl EntityMgr {
    // Both of these start empty, of course
    pub fn new() -> EntityMgr {
        EntityMgr {
            generation: vec![],
            free_indices: vec![],
        }
    }

    // When we create a 'new' entity, we'll either build a fresh one,
    // or we'll reuse an existing one. We'll only reuse an existing
    // one if we have enough in the queue to start doing so.
    pub fn new_entity(&mut self) -> Entity {
        const MIN_FREE_INDICES: usize = 1024;
        if self.free_indices.len() < MIN_FREE_INDICES {
            // If we don't have much in the queue, then we'll start by
            // creating a new one: its new generation value is 0, and
            // its raw index is going to be whatever the length of the
            // generation list is. As long as stuff gets added to the
            // generation list each time (which it will) and nothing
            // (or not enough) is getting freed, this will act like an
            // auto-incrementing value. We can think of our Entity's
            // index as (0, n).
            self.generation.push(0);
            Entity::new(0, (self.generation.len() - 1) as u64)
        } else {
            // However, if we've got a fair bit floating around the
            // free list, then we'll want to start reusing them. We
            // grab that index, and then _use it as an index into the
            // generation table_ to get the generation. We've already
            // incremented the generation table when we destroyed the
            // previous entity, so this will also be fresh (unless it
            // has wrapped around---in that case, the old one is
            // definitely out of circulation because of our
            // MIN_FREE_INDICES check!)
            let new_idx = self.free_indices.pop().unwrap();
            Entity::new(self.generation[new_idx as usize], new_idx)
        }
    }

    pub fn destroy(&mut self, e: Entity) {
        // When we destroy an Entity, we adds it index to the list of
        // free indices, and then increment the associated generation
        // field. This makes sure that when we check to find out
        // whether an entity is alive, we can easily do so with an
        // indexing and a comparison!
        self.generation[e.index() as usize] += 1;
        self.free_indices.push(e.index());
    }

    pub fn is_alive(&self, e: Entity) -> bool {
        // And with that, our `is_alive` check is eays.
        self.generation[e.index() as usize] == e.generation()
    }
}


#[derive(Debug)]
pub struct System<Component> {
    map: BTreeMap<Entity, Component>,
}

impl<Component> System<Component> {
    pub fn new() -> System<Component> {
        System { map: BTreeMap::new() }
    }

    pub fn add(&mut self, e: Entity, c: Component) {
        self.map.insert(e, c);
    }

    pub fn each<F>(&mut self, mut callback: F)
        where F: FnMut(&Entity, &mut Component)
    {
        for (e, c) in self.map.iter_mut() {
            callback(e, c);
        }
    }
}

#[derive(Debug)]
pub struct Position {
    x: f32,
    y: f32,
}

#[derive(Debug)]
pub struct Interact {
    interact: (),
}

#[derive(Debug)]
pub struct DebugInfo {
    name: String,
}

#[derive(Debug)]
pub struct Mesh {
    mesh: (),
}

#[derive(Debug)]
pub struct SystemState {
    positions: System<Position>,
    debug_info: System<DebugInfo>,
    meshes: System<Mesh>,
    interactions: System<Interact>,
}