use graph::GraphLike;
use graph::ReadableVertex;
use graph::Vertex;
use graph::WritableVertex;
use information::InformationProvider;
use std::collections::VecDeque;
use std::mem;

pub struct Graph<TInformation> {
    vertices: Vec<Option<Vertex<TInformation>>>,
}

impl <TInformation> Graph<TInformation> {
    pub fn defragment(&mut self) -> Vec<usize> {
        let mut new_vertex_id_layout: Vec<_> = (0..self.vertices.len()).collect();
        let mut visited_vertex_counter = 0;
        self
            .breadth_first_search(
                |vertex_id| {
                    new_vertex_id_layout[vertex_id] = visited_vertex_counter;
                    visited_vertex_counter = visited_vertex_counter + 1;
                }
            );

        let mut new_vertices: Vec<Option<Vertex<TInformation>>> = (0..visited_vertex_counter).map(|_| None).collect();
        for old_vertex_id in self.get_vertex_ids() {
            let old_vertex_option = self.take_vertex_option(old_vertex_id);
            let old_vertex = old_vertex_option.unwrap();

            let new_input_ids: Vec<_> =
                old_vertex
                    .get_input_ids()
                    .into_iter()
                    .cloned()
                    .map(
                        |old_input_id| {
                            new_vertex_id_layout[old_input_id]
                        }
                    )
                    .collect();

            let new_output_ids: Vec<_> =
                old_vertex
                    .get_output_ids()
                    .into_iter()
                    .cloned()
                    .map(
                        |old_output_id| {
                            new_vertex_id_layout[old_output_id]
                        }
                    )
                    .collect();

            let information = old_vertex.take_information();

            let new_vertex = Vertex::new_from_input_ids_and_output_ids(information, new_input_ids, new_output_ids);
            let new_vertex_id = new_vertex_id_layout[old_vertex_id];

            new_vertices[new_vertex_id] = Some(new_vertex);
        }

        self.vertices = new_vertices;

        new_vertex_id_layout
    }

    pub fn new() -> Graph<TInformation> {
        Graph{ vertices: Vec::new() }
    }

    fn inner_get_vertex(&self, vertex_id: usize) -> &Vertex<TInformation> {
        self.vertices[vertex_id].as_ref().unwrap()
    }

    fn inner_get_vertex_mut<'a>(&'a mut self, vertex_id: usize) -> &'a mut Vertex<TInformation> {
        self.vertices[vertex_id].as_mut().unwrap()
    }

    fn take_vertex_option(&mut self, vertex_id: usize) -> Option<Vertex<TInformation>> {
        mem::replace(&mut self.vertices[vertex_id], None)
    }

    #[allow(unused_attributes)]
    #[test]
    pub fn get_vertices_test(&self) -> &Vec<Option<Vertex<TInformation>>> {
        &self.vertices
    }
}

impl <TInformation> GraphLike<TInformation> for Graph<TInformation> {
    fn add_vertex(&mut self, information: TInformation) -> usize {
        let new_vertex_id = self.vertices.len();
        let new_vertex = Vertex::new(information);
        let some_new_vertex = Some(new_vertex);
        self.vertices.push(some_new_vertex);

        new_vertex_id
    }

    fn breadth_first_search<TFn>(&self, mut func: TFn)
        where TFn: FnMut(usize) {
        let mut visit_vec: Vec<_> = (0..self.vertices.len()).map(|_| false).collect();
        let start_vertex_ids = self.get_start_vertex_ids();
        let mut vertex_id_queue: VecDeque<_> = start_vertex_ids.into_iter().collect();

        while let Some(current_vertex_id) = vertex_id_queue.pop_front() {
            func(current_vertex_id);

            visit_vec[current_vertex_id] = true;

            let current_vertex = self.get_vertex(current_vertex_id);
            for output_vertex_id in current_vertex.get_output_ids().into_iter() {
                if !visit_vec[output_vertex_id.clone()] {
                    vertex_id_queue.push_back(output_vertex_id.clone());
                }
            }
        }
    }

    fn connect_vertices(&mut self, from_vertex_id: usize, to_vertex_id: usize) {
        {
            let from_vertex = self.inner_get_vertex_mut(from_vertex_id);
            from_vertex.add_output(to_vertex_id);
        }
        {
            let to_vertex = self.inner_get_vertex_mut(to_vertex_id);
            to_vertex.add_input(from_vertex_id);
        }
    }

    fn depth_first_search<TFn>(&self, mut func: TFn)
        where TFn: FnMut(usize) {
        let mut visit_vec: Vec<_> = (0..self.vertices.len()).map(|_| false).collect();
        let start_vertex_ids = self.get_start_vertex_ids();
        let mut vertex_id_queue: VecDeque<_> = start_vertex_ids.into_iter().collect();

        while let Some(current_vertex_id) = vertex_id_queue.pop_back() {
            func(current_vertex_id);

            visit_vec[current_vertex_id] = true;

            let current_vertex = self.get_vertex(current_vertex_id);
            for output_vertex_id in current_vertex.get_output_ids().into_iter() {
                if !visit_vec[output_vertex_id.clone()] {
                    vertex_id_queue.push_back(output_vertex_id.clone());
                }
            }
        }
    }

    fn disconnect_vertices(&mut self, from_vertex_id: usize, to_vertex_id: usize) {
        {
            let from_vertex = self.inner_get_vertex_mut(from_vertex_id);
            from_vertex.remove_output(to_vertex_id);
        }
        {
            let to_vertex = self.inner_get_vertex_mut(to_vertex_id);
            to_vertex.remove_input(from_vertex_id);
        }
    }

    fn get_end_vertex_ids(&self) -> Vec<usize> {
        let vertices_len = self.vertices.len();
        let vertices = &self.vertices;

        let end_vertex_ids =
            vertices
                .into_iter()
                .zip(0..vertices_len)
                .filter(
                    |item| {
                        let &(vertex_option, _) = item;
                        if let &Some(ref vertex) = vertex_option {
                            vertex.is_end_vertex()
                        } else {
                            false
                        }
                    }
                )
                .map(
                    |item| {
                        let (_, id) = item;
                        id
                    }
                )
                .collect();

        end_vertex_ids
    }

    fn get_start_vertex_ids(&self) -> Vec<usize> {
        let vertices_len = self.vertices.len();
        let vertices = &self.vertices;

        let start_vertex_ids =
            vertices
                .into_iter()
                .zip(0..vertices_len)
                .filter(
                    |item| {
                        let &(vertex_option, _) = item;
                        if let &Some(ref vertex) = vertex_option {
                            vertex.is_start_vertex()
                        } else {
                            false
                        }
                    }
                )
                .map(
                    |item| {
                        let (_, id) = item;
                        id
                    }
                )
                .collect();

        start_vertex_ids
    }

    fn get_vertex(&self, vertex_id: usize) -> &ReadableVertex {
        self.vertices[vertex_id].as_ref().unwrap()
    }

    fn get_vertex_ids(&self) -> Vec<usize> {
        let vertices_len = self.vertices.len();
        let vertices = &self.vertices;

        let vertex_ids =
            vertices
                .into_iter()
                .zip(0..vertices_len)
                .filter(
                    |item| {
                        let &(vertex_option, _) = item;
                        vertex_option.is_some()
                    }
                )
                .map(
                    |item| {
                        let (_, id) = item;
                        id
                    }
                )
                .collect();

        vertex_ids
    }

    fn remove_vertex(&mut self, vertex_id: usize) {
        let removed_vertex = self.take_vertex_option(vertex_id).unwrap();

        let input_vertex_ids = removed_vertex.get_input_ids().into_iter().cloned();
        for input_vertex_id in input_vertex_ids {
            self.inner_get_vertex_mut(input_vertex_id).remove_output(vertex_id);
        }

        let output_vertex_ids = removed_vertex.get_output_ids().into_iter().cloned();
        for output_vertex_id in output_vertex_ids {
            self.inner_get_vertex_mut(output_vertex_id).remove_input(vertex_id);
        }
    }
}

impl <TInformation> InformationProvider<TInformation> for Graph<TInformation> {
    fn get_all_information(&self) -> Vec<&TInformation> {
        let vertices = &self.vertices;
        vertices
            .into_iter()
            .filter(|item| item.is_some())
            .map(|item| item.as_ref().unwrap().get_information())
            .collect()
    }

    fn get_all_information_mut<'a>(&'a mut self) -> Vec<&'a mut TInformation> {
        let vertices = &mut self.vertices;
        vertices
            .into_iter()
            .filter(|item| item.is_some())
            .map(|item| item.as_mut().unwrap().get_information_mut())
            .collect()
    }

    fn get_information(&self, vertex_id: usize) -> &TInformation {
        self.inner_get_vertex(vertex_id).get_information()
    }

    fn get_information_mut<'a>(&'a mut self, vertex_id: usize) -> &'a mut TInformation {
        self.inner_get_vertex_mut(vertex_id).get_information_mut()
    }
}