use rand;
use rand::{Rand, Rng};
use rayon;
use rayon::prelude::*;
use std::sync::{Arc, RwLock};
use std::sync::atomic::{AtomicUsize, Ordering};
use time;

use initial_solution;
use model::{Action, EventIndex, OrderList, State, Time, TravelTime};

pub const STARTING_TEMPERATURE: f32 = 300.0;
pub const ENDING_TEMPERATURE: f32 = 0.5;

/// The actions that can be performed while searching.
pub enum PossibleAction {
    /// Randomly schedule an unscheduled order.
    Insert,
    /// Randomly remove an order from the schedule.
    Remove,
    /// Randomly remove an order with frequency <= 1 from the schedule.
    RemoveLowFrequency,
    /// Split a segment into two, introducing a new dumping moment.
    Split,
    /// Move an order to another day, vehicle or segment.
    Push,
}

impl Rand for PossibleAction {
    fn rand<R: Rng>(rng: &mut R) -> Self {
        match rng.gen_range(0, 100) {
            0...19 => PossibleAction::Insert,
            20 => PossibleAction::Remove,
            21...29 => PossibleAction::RemoveLowFrequency,
            30...34 => PossibleAction::Split,
            35...99 => PossibleAction::Push,
            _ => unreachable!("The RNG just broke, send help!"),
        }
    }
}

pub struct Solver {
    /// The internal state of the solver.
    state: Arc<RwLock<State>>,
    max_iterations: usize,
    /// The total number of actions considered and executed.
    total_actions: AtomicUsize,
}

impl Solver {
    /// Initializes a new solver with a random starting state.
    pub fn new(
        order_list: &Arc<OrderList>,
        travel_time: &Arc<TravelTime>,
        max_iterations: usize,
    ) -> Solver {
        let state = initial_solution::create_greedy_stochastic_state(order_list, travel_time);

        #[cfg(debug)]
        state.debug_validate();

        Solver::from_state(state, max_iterations)
    }

    pub fn from_state(state: State, max_iterations: usize) -> Solver {
        Solver {
            state: Arc::new(RwLock::new(state)),
            max_iterations: max_iterations,
            total_actions: AtomicUsize::new(0),
        }
    }

    /// Runs the solver for `MAX_ITERATIONS` iterations.
    pub fn solve(&mut self) -> State {
        let starting_time = time::now();
        for iteration in 0..self.max_iterations {
            // For the temperature we interpolate between a starting and an ending temperature. See
            // quadratic additive cooling http://archive.is/5cYAl.
            let interpolation =
                ((self.max_iterations - iteration) as f32 / self.max_iterations as f32).powi(2);
            let temperature =
                ENDING_TEMPERATURE + (STARTING_TEMPERATURE - ENDING_TEMPERATURE) * interpolation;

            // Every iteration we'll try to find an acceptable improvement. This is done in parallel
            // so we'll need some dummy value to get the iteration started. This action already
            // precalculated information like the difference in score performing it would make and
            // which events should be changed, so we can pass the result directly to the
            // corrosponding methods without any checks.
            let (score_delta, actions) = self.next_action(temperature);
            let mut state = self.state.write().unwrap();
            state.execute_operator(score_delta, &actions);

            self.total_actions.fetch_add(1, Ordering::Relaxed);

            if cfg!(debug) {
                state.debug_validate();
            }

            if iteration % 10_000 == 0 {
                println!(
                    "Iteration {}/{} :: score: {}, temperature: {}, unscheduled orders: {}",
                    iteration,
                    self.max_iterations,
                    state.score(),
                    temperature,
                    state.possible_orders.len()
                );
            }
        }

        let elapsed_time = (time::now() - starting_time).num_milliseconds() as f32 / 1000.0;
        println!(
            "\nTotal elapsed time: {} seconden\nChosen actions per second: {}",
            elapsed_time,
            self.max_iterations as f32 / elapsed_time
        );
        println!(
            "Iterations per second: {}",
            (self.total_actions.load(Ordering::Acquire) as f32 / elapsed_time) as usize
        );

        (*self.state).read().unwrap().clone()
    }

    /// Finds a new action to perform.
    fn next_action(&self, temperature: f32) -> (Time, Vec<Action>) {
        let state = self.state.read().unwrap();

        // It's becomes more efficient to convert to vectors first than it is to use `.nth()` when
        // sampling from hashsets as the temperature lowers.
        let possible_orders: Vec<_> = state.possible_orders.iter().collect();
        let scheduled_orders: Vec<_> = state.scheduled_orders.keys().collect();

        rayon::iter::repeat(())
            .filter_map(|_| {
                self.total_actions.fetch_add(1, Ordering::Relaxed);

                let mut rng = rand::weak_rng();
                let next_action: PossibleAction = rng.gen();
                match next_action {
                    PossibleAction::Insert => {
                        if state.possible_orders.is_empty() {
                            return None;
                        }

                        let order_id = rng.choose(&possible_orders)?;
                        let possible_days = state
                            .orders
                            .get(order_id)
                            .map(|order| order.days())
                            .unwrap();
                        let order_days = rng.choose(possible_days).unwrap();

                        // For every day we randomly choose the vehicle and a place in the event
                        // list the order should be inserted in
                        let chosen_days: Vec<EventIndex> = order_days
                            .iter()
                            .map(|&day| {
                                let vehicle = rng.gen_range(0, 2);
                                let segment_id = rng.gen_range(0, state.events[vehicle][day].len());
                                let segment_length = state.events[vehicle][day][segment_id].len();
                                let event_id = rng.gen_range(0, segment_length + 1);

                                (vehicle, day, segment_id, event_id)
                            })
                            .collect();

                        state.try_insert_order(**order_id, &chosen_days).ok()
                    }

                    PossibleAction::Remove => {
                        if state.scheduled_orders.is_empty() {
                            return None;
                        }

                        let order_id = rng.choose(&scheduled_orders)?;

                        state.try_remove_order(**order_id).ok()
                    }

                    PossibleAction::RemoveLowFrequency => {
                        if state.scheduled_orders.is_empty() {
                            return None;
                        }

                        // It's possible that there are no low frequency orders scheduled.
                        let order_id = (0..100)
                            .filter_map(|_| rng.choose(&scheduled_orders))
                            .find(|order_id| state.orders[order_id].frequency == 1)?;

                        state.try_remove_order(**order_id).ok()
                    }

                    PossibleAction::Split => {
                        let vehicle = rng.gen_range(0, 2);
                        let day = rng.gen_range(0, 5);
                        let segment_count = state.events[vehicle][day].len();
                        if segment_count == 0 {
                            return None;
                        }
                        let segment_id = rng.gen_range(0, segment_count);
                        let segment = &state.events[vehicle][day][segment_id];
                        if segment.len() < 2 {
                            return None;
                        }
                        let split_at = rng.gen_range(1, segment.len());

                        state
                            .try_insert_dump((vehicle, day, segment_id, split_at))
                            .ok()
                    }

                    PossibleAction::Push => {
                        let from_vehicle = rng.gen_range(0, 2);
                        let from_day = rng.gen_range(0, 5);
                        let segment_count = state.events[from_vehicle][from_day].len();
                        if segment_count == 0 {
                            return None;
                        }
                        let from_segment_id = rng.gen_range(0, segment_count);
                        let from_segment = &state.events[from_vehicle][from_day][from_segment_id];
                        if from_segment.is_empty() {
                            return None;
                        }

                        let from_index = rng.gen_range(0, from_segment.len());
                        let order = &state.orders[&from_segment.orders[from_index]];

                        // Pushing between different days is only possible when the order can be
                        // scheduled on any day
                        let to_vehicle = rng.gen_range(0, 2);
                        let to_day = if order.frequency == 1 {
                            rng.gen_range(0, 5)
                        } else {
                            from_day
                        };
                        let segment_count = state.events[to_vehicle][to_day].len();
                        if segment_count == 0 {
                            return None;
                        }
                        let to_segment_id = rng.gen_range(0, segment_count);
                        let to_index = rng.gen_range(
                            0,
                            state.events[to_vehicle][to_day][to_segment_id].len() + 1,
                        );

                        let from_data = (from_vehicle, from_day, from_segment_id, from_index);
                        let to_data = (to_vehicle, to_day, to_segment_id, to_index);
                        state.try_push_order(from_data, to_data).ok()
                    }
                }
            })
            .find_any(|&(score_delta, _)| {
                acceptance_chance(score_delta, temperature) > rand::random()
            })
            .unwrap()
    }
}

/// Calculates the acceptance chance used when minimizing a problem using simulated annealing.
pub fn acceptance_chance(score_delta: Time, temperature: f32) -> f32 {
    if score_delta < 0 {
        return 1.0;
    }

    (-score_delta as f32 / temperature).exp()
}