use alloc::vec::Vec;
use alloc::string::String;
use alloc::btree_map::BTreeMap;

use super::super::{Transaction, EventManager, Order, View, Events, get_view_id};
use super::diff_props_object;


#[inline]
pub fn diff_view(
    parent_id: &str,
    index: usize,
    prev_view_option: Option<&View>,
    next_view_option: Option<&View>,
    event_manager: &mut EventManager,
    transaction: &mut Transaction
) {
    match next_view_option {
        Some(next_view) => match prev_view_option {
            Some(prev_view) => match prev_view {
                &View::Text(ref prev_text) => match next_view {
                    &View::Text(ref next_text) => if prev_text != next_text {
                        let id = get_view_id(parent_id, prev_view.key(), index);
                        transaction.replace(&id, prev_view.into(), next_view.into());
                    },
                    &View::Data { events: ref next_events, .. } => {
                        let id = get_view_id(parent_id, prev_view.key(), index);
                        add_events(&id, next_events, event_manager, transaction);
                        transaction.replace(&id, prev_view.into(), next_view.into());
                    },
                },
                &View::Data {
                    key: ref prev_key,
                    props: ref prev_props,
                    events: ref prev_events,
                    children: ref prev_children, ..
                } => match next_view {
                    &View::Text(_) => {
                        let id = get_view_id(parent_id, prev_view.key(), index);
                        remove_events(&id, prev_events, event_manager, transaction);
                        transaction.replace(&id, prev_view.into(), next_view.into());
                    },
                    &View::Data {
                        key: ref next_key,
                        props: ref next_props,
                        events: ref next_events,
                        children: ref next_children, ..
                    } => if prev_key == next_key {
                        let children = diff_children(prev_children, next_children);
                        let id = get_view_id(parent_id, next_key.as_ref(), index);

                        for i in 0..children.children.len() {
                            diff_view(&id, i, prev_children.get(i), children.children[i], event_manager, transaction);
                        }

                        if children.removes.len() != 0 || children.inserts.len() != 0 {
                            transaction.order(&id, Order::new(
                                children.removes.iter().map(|&(k, v)| (k, v.map(|v| v.clone()))).collect(),
                                children.inserts.iter().map(|&(k, v)| (k.map(|k| k.clone()), v)).collect(),
                            ));
                        }

                        diff_events(&id, prev_events, next_events, event_manager, transaction);

                        match diff_props_object(prev_props, next_props) {
                            Some(props) => transaction.props(&id, prev_props.clone(), props),
                            None => (),
                        }
                    } else {
                        let id = get_view_id(parent_id, next_key.as_ref(), index);
                        add_events(&id, next_events, event_manager, transaction);
                        transaction.replace(&id, prev_view.into(), next_view.into());
                    },
                },
            },
            None => {
                let id = get_view_id(parent_id, next_view.key(), index);
                if let Some(next_events) = next_view.events() {
                    add_events(&id, next_events, event_manager, transaction);
                }
                transaction.insert(parent_id, &id, index, next_view.into());
            },
        },
        None => if let Some(prev_view) = prev_view_option {
            let id = get_view_id(parent_id, prev_view.key(), index);
            if let Some(prev_events) = prev_view.events() {
                remove_events(&id, prev_events, event_manager, transaction);
            }
            transaction.remove(&id, prev_view.into());
        },
    }
}


#[inline]
fn remove_events(id: &str, events: &Events, event_manager: &mut EventManager, transaction: &mut Transaction) {
    events.for_each(|(name, _)| {
        transaction.remove_event(id, name);
        event_manager.remove(id, name);
    });
}

#[inline]
fn add_events(id: &str, events: &Events, event_manager: &mut EventManager, transaction: &mut Transaction) {
    events.for_each(|(name, func)| {
        transaction.add_event(id, name);
        event_manager.add(id, name, func.clone());
    });
}

#[inline]
fn diff_events(id: &str, prev_events: &Events, next_events: &Events, event_manager: &mut EventManager, transaction: &mut Transaction) {
    prev_events.for_each(|(name, _)| {
        if !next_events.contains(name) {
            transaction.remove_event(id, name);
            event_manager.remove(id, name);
        }
    });
    next_events.for_each(|(name, func)| {
        if !prev_events.contains(name) {
            transaction.add_event(id, name);
        }
        event_manager.add(id, name, func.clone());
    });
}


#[inline]
fn diff_children<'a>(
    prev_children: &'a [View],
    next_children: &'a [View]
) -> Children<'a> {
    let prev_children_len = prev_children.len();
    let next_children_len = next_children.len();
    let max_children = if prev_children_len > next_children_len {prev_children_len} else {next_children_len};
    let next_indices = KeyIndices::new(next_children);

    if next_indices.free.len() != prev_children_len {
        let prev_indices = KeyIndices::new(prev_children);

        if prev_indices.free.len() != prev_children_len {
            let mut children = Children::new();

            let mut free_index = 0;
            let free_count = next_indices.free.len();
            let mut deleted_items = 0;

            for prev_item in prev_children {
                if let Some(prev_item_key) = prev_item.key() {
                    if let Some(item_index) = next_indices.keys.get(prev_item_key) {
                        children.children.push(next_children.get(*item_index));
                    } else {
                        deleted_items += 1;
                        children.children.push(None);
                    }
                } else {
                    if free_index < free_count {
                        let item_index = next_indices.free[free_index];
                        free_index += 1;
                        children.children.push(next_children.get(item_index));
                    } else {
                        deleted_items += 1;
                        children.children.push(None);
                    }
                }
            }

            let last_free_index = if free_index >= next_indices.free.len() {
                next_children_len
            } else {
                next_indices.free[free_index]
            };

            let mut j = 0;
            for new_item in next_children {
                if let Some(new_item_key) = new_item.key() {
                    if !prev_indices.keys.contains_key(new_item_key) {
                        children.children.push(Some(new_item));
                    }
                } else if j >= last_free_index {
                    children.children.push(Some(new_item));
                }
                j += 1;
            }

            let mut simulate = children.children.clone();
            let mut simulate_index = 0;

            let mut k = 0;
            while k < next_children_len {
                let wanted_item = &next_children[k];
                let mut simulate_item = simulate[simulate_index];

                while simulate_item == None && simulate.len() != 0 {
                    simulate.remove(simulate_index);
                    children.removes.push((simulate_index, None));
                    simulate_item = simulate[simulate_index];
                }

                if simulate_item == None || simulate_item.unwrap().key() != wanted_item.key() {
                    if let Some(wanted_item_key) = wanted_item.key() {
                        if simulate_item.is_some() && simulate_item.unwrap().key().is_some() {
                            let simulate_item_unwraped = simulate_item.unwrap();
                            let simulate_item_key = simulate_item_unwraped.key().unwrap();

                            if next_indices.keys[simulate_item_key] != k + 1 {
                                simulate.remove(simulate_index);
                                children.removes.push((simulate_index, Some(simulate_item_key)));
                                simulate_item = simulate[simulate_index];

                                if simulate_item.is_none() || simulate_item_key != wanted_item_key {
                                    children.inserts.push((Some(wanted_item_key), k));
                                } else {
                                    simulate_index += 1;
                                }
                            } else {
                                children.inserts.push((Some(wanted_item_key), k));
                            }
                        } else {
                            children.inserts.push((Some(wanted_item_key), k));
                        }
                        k += 1
                    } else if let Some(simulate_item) = simulate_item {
                        let simulate_item_key = simulate_item.key();

                        if simulate_item_key.is_some() {
                            simulate.remove(simulate_index);
                            children.removes.push((simulate_index, simulate_item_key));
                        }
                    }
                } else {
                    simulate_index += 1;
                    k += 1;
                }
            }

            while simulate_index < simulate.len() {
                let simulate_item = simulate[simulate_index];
                simulate.remove(simulate_index);
                children.removes.push((simulate_index, if let Some(simulate_item) = simulate_item {
                    simulate_item.key()
                } else {
                    None
                }));
            }

            if children.removes.len() == deleted_items && children.inserts.len() == 0 {
                children.clear();
                children.pad(max_children)
            } else {
                children.pad(max_children)
            }
        } else {
            Children::from(&*next_children).pad(max_children)
        }
    } else {
        Children::from(&*next_children).pad(max_children)
    }
}


struct Children<'a> {
    children: Vec<Option<&'a View>>,
    removes: Vec<(usize, Option<&'a String>)>,
    inserts: Vec<(Option<&'a String>, usize)>,
}

impl<'a> From<&'a [View]> for Children<'a> {
    #[inline(always)]
    fn from(children: &'a [View]) -> Self {
        Children {
            children: children.iter().map(|v| Some(v)).collect(),
            removes: Vec::new(),
            inserts: Vec::new(),
        }
    }
}

impl<'a> Children<'a> {
    #[inline(always)]
    fn new() -> Self {
        Children {
            children: Vec::new(),
            removes: Vec::new(),
            inserts: Vec::new(),
        }
    }
    #[inline]
    fn clear(&mut self) {
        self.removes.clear();
        self.inserts.clear();
    }
    #[inline]
    fn pad(mut self, len: usize) -> Self {
        if self.children.len() < len {
            for _ in 0..(len - self.children.len()) {
                self.children.push(None);
            }
        }
        self
    }
}


struct KeyIndices<'a> {
    keys: BTreeMap<&'a String, usize>,
    free: Vec<usize>,
}

impl<'a> KeyIndices<'a> {
    #[inline]
    fn new(children: &'a [View]) -> Self {
        let mut keys = BTreeMap::new();
        let mut free = Vec::new();

        let mut i = 0;
        for child in children {
            if let Some(key) = child.key() {
                keys.insert(key, i);
            } else {
                free.push(i);
            }
            i += 1;
        }

        KeyIndices {
            keys: keys,
            free: free,
        }
    }
}