//! The model of our solver.
//!
//! # Important note about rounding
//!
//! To prevent rounding errors we keep track of time and score by multiplying the time in seconds by
//! 10, meaning that a minute consist of 600 time units.

use rayon::prelude::*;
use std::collections::{HashMap, HashSet};
use std::f32;
use std::fmt::{Display, Formatter};
use std::fmt;
use std::sync::Arc;

/// Time is stored in tenths of seconds.
pub type Time = i32;
/// The number of time units in a minute.
pub const TIME_PER_MINUTE: Time = 600;
/// The number of time units in a second.
pub const TIME_PER_SECOND: Time = 10;
/// The length of a day in time units.
pub const DAY_LENGTH: Time = 12 * 60 * TIME_PER_MINUTE;

/// The hauling capacity of a single truck, in liters.
pub const CAPACITY: i32 = 20_000;
/// The location of the garbage disposal on the distance matrix.
pub const DUMP_LOCATION: u32 = 287;
/// The 'order id' of a dumping operation.
pub const DUMP_ORDER_ID: u32 = 0;
/// The amount of time it takes to dump the load, in time units.
pub const DUMPING_TIME: Time = 30 * TIME_PER_MINUTE;
/// The combinations of possible days that an event can be scheduled on for each frequency. See
/// `Order::days()`.
const ORDER_DAYS: [&[&[usize]]; 5] = [
    &[&[0], &[1], &[2], &[3], &[4]],
    &[&[0, 3], &[1, 4]],
    &[&[0, 2, 4]],
    &[
        &[0, 1, 2, 3],
        &[0, 1, 2, 4],
        &[0, 1, 3, 4],
        &[0, 2, 3, 4],
        &[1, 2, 3, 4],
    ],
    &[&[0, 1, 2, 3, 4]],
];

/// `TravelTime[(a, b)]` represents the travel distance from `a` to `b` in *time units*. The input
/// data is in seconds, so it be multiplied with `TIME_PER_SECOND` first.
pub type TravelTime = HashMap<(u32, u32), Time>;
pub type OrderList = HashMap<u32, Order>;

/// `(vehicle, day, segment, event_id)` indices for events.
pub type EventIndex = (usize, usize, usize, usize);

#[derive(Clone, Debug)]
/// Represents the searchable state in which we will try to minimize our score using local search
/// algorithms. Operators come in two forms:
///
/// - `<operator>()`, this will perform the operator like you'd expect.
/// - `try_<operator>()`, this function is called during the execution of the regular operator and
///   returns the difference in score applying the operator would make and a list of instructions to
///   be performed on the event lists.
///
/// The instructions returned by the `try_<operator>()` functions can be executed using the
/// `execute_operator()` function. See `Action` for more information.
pub struct State {
    /// The total current score in time units.
    pub current_score: Time,
    /// The events are structured as follows: `state.events[truck][day][event_id]`.
    ///
    /// ## Important
    /// For efficiency reasons this list won't contain a final `Events::Dump`. All methods acting on
    /// the state should still assume this event always happens!
    pub events: [[Vec<Segment>; 5]; 2],
    /// Which orders are still able to be scheduled.
    pub possible_orders: HashSet<u32>,
    /// In which vehicle, on which day and in which segment orders are scheduled. Needed for
    /// deletion.
    pub scheduled_orders: HashMap<u32, HashSet<(usize, usize, usize)>>,

    pub orders: Arc<OrderList>,
    pub travel_time: Arc<TravelTime>,
}

#[derive(Debug, PartialEq, Eq)]
/// All the errors that can occur while trying to modify the state.
pub enum StateError {
    /// Order has already been scheduled.
    AlreadyScheduled,
    /// One of the chosen days is already fully scheduled.
    DayFull,
    /// The swap would be out of bounds.
    InfeasibleSwap,
    /// The given indices are out of bounds.
    InvalidParameter,
    /// The action would cause the truck to fill over its capacity. This contains on which
    /// `(vehicle, day)` a truck goes over capacity.
    OverCapacity(usize, usize),
    /// The order can't be removed because it hasn't been scheduled yet.
    NotScheduled,
}

#[allow(unknown_lints)]
#[allow(unit_arg)]
impl State {
    /// Creates a new state, filling the list of possible orders using the supplied orderlist.
    pub fn new(orders: Arc<OrderList>, travel_time: Arc<TravelTime>) -> State {
        let initial_score = orders
            .par_iter()
            .map(|(_, order)| order.frequency as Time * order.duration * 3)
            .sum();

        State {
            current_score: initial_score,
            events: array![array![vec![Segment::new()]; 5]; 2],
            possible_orders: orders.keys().cloned().collect(),
            scheduled_orders: HashMap::new(),
            orders: orders,
            travel_time: travel_time,
        }
    }

    /// Returns the current score in minutes.
    pub fn score(&self) -> f32 {
        self.current_score as f32 / TIME_PER_MINUTE as f32
    }

    /// Performs the actions returned by the `try_<operator>()` functions.
    ///
    /// # Panics
    ///
    /// This function does not perform any bounds checking, and will thus panic when invalid actions
    /// are passed.
    pub fn execute_operator(&mut self, score_delta: Time, actions: &[Action]) {
        self.current_score += score_delta;
        for action in actions {
            match *action {
                Action::InsertOrder {
                    vehicle,
                    day,
                    segment_id,
                    index,
                    order_id,
                    time_delta,
                    volume_delta,
                } => {
                    let mut segment = &mut self.events[vehicle][day][segment_id];
                    segment.insert(index, order_id);
                    segment.duration += time_delta;
                    segment.volume += volume_delta;

                    self.possible_orders.remove(&order_id);
                    self.scheduled_orders
                        .entry(order_id)
                        .or_insert_with(HashSet::new)
                        .insert((vehicle, day, segment_id));
                }
                Action::RemoveOrder {
                    vehicle,
                    day,
                    segment_id,
                    index,
                    order_id,
                    time_delta,
                    volume_delta,
                } => {
                    let mut segment = &mut self.events[vehicle][day][segment_id];
                    segment.remove(index);
                    segment.duration += time_delta;
                    segment.volume += volume_delta;

                    // If this was the last planned day of this order, we should completely remove it
                    if self.scheduled_orders[&order_id].len() == 1 {
                        self.scheduled_orders.remove(&order_id);
                        self.possible_orders.insert(order_id);
                    } else {
                        self.scheduled_orders.get_mut(&order_id).unwrap().remove(&(
                            vehicle,
                            day,
                            segment_id,
                        ));
                    }
                }
                Action::InsertSegment {
                    vehicle,
                    day,
                    index,
                } => {
                    self.adjust_segment_id(vehicle, day, index, 1, false);

                    self.events[vehicle][day].insert(index, Segment::new());
                }
                Action::RemoveSegment {
                    vehicle,
                    day,
                    index,
                } => {
                    // Every order (if any) that is still planned in the segment should be removed
                    // first
                    for order_id in &self.events[vehicle][day][index].orders {
                        if self.scheduled_orders[order_id].len() == 1 {
                            self.scheduled_orders.remove(order_id);
                            self.possible_orders.insert(*order_id);
                        } else {
                            self.scheduled_orders.get_mut(order_id).unwrap().remove(&(
                                vehicle,
                                day,
                                index,
                            ));
                        }
                    }

                    // The segment ID of orders happening later on the day will need to be adjusted
                    // to account for this segment dissapearing
                    self.adjust_segment_id(vehicle, day, index + 1, -1, false);

                    // We should always keep at least one segment per day. If this is the day's last
                    // segment, we'll only clear it out.
                    if self.events[vehicle][day].len() > 1 {
                        self.events[vehicle][day].remove(index);
                    } else {
                        self.events[vehicle][day][index].clear();
                    }
                }
                Action::SplitSegment {
                    vehicle,
                    day,
                    segment_id,
                    index,
                    durations: (duration_a, duration_b),
                    volumes: (volume_a, volume_b),
                } => {
                    {
                        let mut segments = &mut self.events[vehicle][day];
                        let orders_b = {
                            let mut segment_a = &mut segments[segment_id];
                            let orders_b = segment_a.orders.split_off(index);
                            segment_a.duration = duration_a;
                            segment_a.volume = volume_a;

                            orders_b
                        };

                        let mut segment_b = Segment::new();
                        segment_b.orders = orders_b;
                        segment_b.duration = duration_b;
                        segment_b.volume = volume_b;
                        segments.insert(segment_id + 1, segment_b);
                    }

                    // The orders happening in `segment_b` and everything that has changed their
                    // segment ID
                    self.adjust_segment_id(vehicle, day, segment_id + 1, 1, true);
                }

                Action::MergeSegment {
                    vehicle,
                    day,
                    segment_id,
                    duration,
                    volume,
                } => {
                    self.adjust_segment_id(vehicle, day, segment_id + 1, -1, false);

                    // Until Non Lexical Lifetimes are a thing we'll have to manually split the
                    // array to be able to mutate two elements at the same time
                    let (before_segments, after_segments) =
                        self.events[vehicle][day].split_at_mut(segment_id + 1);
                    before_segments[segment_id]
                        .orders
                        .append(&mut after_segments[0].orders);

                    before_segments[segment_id].duration = duration;
                    before_segments[segment_id].volume = volume;
                }
            }
        }
    }

    /// Insert a dump at `EventIndex`. This will result in splitting the segment into two
    /// segments.
    pub fn insert_dump(&mut self, at: EventIndex) -> Result<(), StateError> {
        let (score_delta, actions) = self.try_insert_dump(at)?;
        Ok(self.execute_operator(score_delta, &actions))
    }

    /// Try to insert a dump at `EventIndex` by splitting the segment.
    pub fn try_insert_dump(
        &self,
        (vehicle, day, segment_id, split_index): EventIndex,
    ) -> Result<(Time, Vec<Action>), StateError> {
        let old_segment = &self.events[vehicle][day][segment_id];
        if split_index == 0 || split_index >= old_segment.len() {
            return Err(StateError::InvalidParameter);
        }

        let mut total_score_difference = -old_segment.duration;
        let (orders_a, orders_b) = old_segment.orders.split_at(split_index);
        let order_lists = [orders_a, orders_b];
        let ((duration_a, volume_a), (duration_b, volume_b)) = {
            let mut new_data = order_lists.into_iter().map(|orders| {
                // Both lists of orders will form a loop starting and ending at the dump
                let mut old_location = DUMP_LOCATION;
                let mut duration = 0;
                let mut volume = 0;
                for order_id in orders.iter() {
                    let order = &self.orders[order_id];
                    let location = order.location_id;
                    duration += self.travel_time[&(old_location, location)] + order.duration;
                    volume += order.volume;

                    old_location = location;
                }

                // Add the final dump
                duration += self.travel_time[&(old_location, DUMP_LOCATION)] + DUMPING_TIME;
                total_score_difference += duration;

                (duration, volume)
            });

            (new_data.next().unwrap(), new_data.next().unwrap())
        };

        let old_total_travel_time: Time = self.events[vehicle][day]
            .iter()
            .map(|segment| segment.duration)
            .sum();
        if old_total_travel_time + total_score_difference >= DAY_LENGTH {
            return Err(StateError::DayFull);
        }

        Ok((
            total_score_difference,
            vec![
                Action::SplitSegment {
                    vehicle: vehicle,
                    day: day,
                    segment_id: segment_id,
                    index: split_index,
                    durations: (duration_a, duration_b),
                    volumes: (volume_a, volume_b),
                },
            ],
        ))
    }

    /// Inserts an order into the schedule while preventing the order to be scheduled on
    /// incompatible days. `chosen_days` should contain `(vehicle, day, event_index)` pairs on which
    /// the order should be scheduled. If the truck would go over capacity a new dump gets inserted.
    /// Inserting at event ID = day length will cause the order to be scheduled at the end of the
    /// day.
    pub fn insert_order(
        &mut self,
        order_id: u32,
        chosen_days: &[EventIndex],
    ) -> Result<(), StateError> {
        let (score_delta, actions) = self.try_insert_order(order_id, chosen_days)?;
        Ok(self.execute_operator(score_delta, &actions))
    }

    /// Calculate what would happen if an order were to be inserted. This returns the difference in
    /// score and for which days a dump should be added before the order.
    pub fn try_insert_order(
        &self,
        order_id: u32,
        chosen_days: &[EventIndex],
    ) -> Result<(Time, Vec<Action>), StateError> {
        if !self.possible_orders.contains(&order_id) {
            return Err(StateError::AlreadyScheduled);
        }

        let order = &self.orders[&order_id];
        let mut actions = Vec::with_capacity(chosen_days.len());
        let mut total_score_difference = 0;
        for &(vehicle, day, segment_id, event_id) in chosen_days {
            let segment = &self.events[vehicle][day][segment_id];
            let orders = &segment.orders;

            if event_id > orders.len() || segment_id > self.events[vehicle][day].len() {
                return Err(StateError::InvalidParameter);
            }

            let last_location = self.get_location_id(orders.get(event_id.wrapping_sub(1)));
            let location = order.location_id;
            let next_location = self.get_location_id(orders.get(event_id));

            // If the order would cause the truck to go over its capacity we have to schedule a new
            // dump. We only have to look at the new part (i.e. from the to be inserted event until
            // the next dump). If the truck goes over its capacity in that time we should insert a
            // dump.
            if segment.volume + order.volume > CAPACITY {
                return Err(StateError::OverCapacity(vehicle, day));
            }

            let mut time_difference = -self.travel_time[&(last_location, next_location)]
                + self.travel_time[&(last_location, location)]
                + self.travel_time[&(location, next_location)]
                + order.duration;
            // If this is the first event in the segment we should account for the newly added
            // dumping time
            if orders.is_empty() {
                time_difference += DUMPING_TIME;
            }

            // The insertion is only possible if the day can end in time
            let old_total_travel_time: Time = self.events[vehicle][day]
                .iter()
                .map(|segment| segment.duration)
                .sum();
            if old_total_travel_time + time_difference >= DAY_LENGTH {
                return Err(StateError::DayFull);
            }

            total_score_difference += time_difference - order.duration * 3;
            actions.push(Action::InsertOrder {
                vehicle: vehicle,
                day: day,
                segment_id: segment_id,
                index: event_id,
                order_id: order_id,
                time_delta: time_difference,
                volume_delta: order.volume,
            });
        }

        Ok((total_score_difference, actions))
    }

    /// Inserts an order into the schedule at the end of the day. This function should only be used
    /// as a helper for creating the initial solutions.
    pub fn insert_order_last(
        &mut self,
        order_id: u32,
        chosen_days: &[(usize, usize)],
    ) -> Result<(), StateError> {
        let chosen_days: Vec<_> = chosen_days
            .into_iter()
            .map(|&(vehicle, day)| {
                let day_length = self.events[vehicle][day].len();
                let segment_length = self.events[vehicle][day][day_length - 1].len();
                (vehicle, day, day_length - 1, segment_length)
            })
            .collect();

        self.insert_order(order_id, &chosen_days)
    }

    /// Simulates inserting an order into the schedule at the end of the day. This function should
    /// only be used as a helper for creating the initial solutions.
    pub fn try_insert_order_last(
        &self,
        order_id: u32,
        chosen_days: &[(usize, usize)],
    ) -> Result<(Time, Vec<Action>), StateError> {
        let chosen_days: Vec<_> = chosen_days
            .into_iter()
            .map(|&(vehicle, day)| {
                let day_length = self.events[vehicle][day].len();
                let segment_length = self.events[vehicle][day][day_length - 1].len();
                (vehicle, day, day_length - 1, segment_length)
            })
            .collect();

        self.try_insert_order(order_id, &chosen_days)
    }

    /// Moves an order from a vehicle/day/segment to another segment. This will return an error if
    /// the order doesn't fit in the new day due to volume or time constraints. The operator doesn't
    /// checker whether the order could actually be moved to the new day (due to frequency
    /// constraints).
    pub fn push_order(&mut self, from: EventIndex, to: EventIndex) -> Result<(), StateError> {
        let (score_delta, actions) = self.try_push_order(from, to)?;
        Ok(self.execute_operator(score_delta, &actions))
    }

    /// Try to move an order from a vehicle/day/segment to another segment. See `push_order` for
    /// more implementation details.
    pub fn try_push_order(
        &self,
        (from_vehicle, from_day, from_segment_id, from_index): EventIndex,
        (to_vehicle, to_day, to_segment_id, to_index): EventIndex,
    ) -> Result<(Time, Vec<Action>), StateError> {
        let mut actions = Vec::with_capacity(2);
        let mut total_score_difference = 0;

        // Pushes to the same position should be rejected
        let same_day = from_vehicle == to_vehicle && from_day == to_day;
        let same_segment = same_day && from_segment_id == to_segment_id;
        if same_segment && (from_index == to_index || to_index == from_index + 1) {
            return Err(StateError::InvalidParameter);
        }

        let from_segment = &self.events[from_vehicle][from_day][from_segment_id];
        let to_segment = &self.events[to_vehicle][to_day][to_segment_id];
        let from_orders = &from_segment.orders;
        let to_orders = &to_segment.orders;
        let order_id = from_orders[from_index];
        let order = &self.orders[&order_id];
        let location = order.location_id;

        // We'll check whether inserting at `to` is possible before checking the removal, as the
        // removal is less likely to cause errors
        {
            let old_total_travel_time: Time = self.events[to_vehicle][to_day]
                .iter()
                .map(|segment| segment.duration)
                .sum();

            let last_location = self.get_location_id(to_orders.get(to_index.wrapping_sub(1)));
            let next_location = self.get_location_id(to_orders.get(to_index));

            let time_difference = -self.travel_time[&(last_location, next_location)]
                + self.travel_time[&(last_location, location)]
                + self.travel_time[&(location, next_location)]
                + order.duration;

            if old_total_travel_time + time_difference >= DAY_LENGTH {
                return Err(StateError::DayFull);
            }
            if to_segment.volume + order.volume > CAPACITY {
                return Err(StateError::OverCapacity(to_vehicle, to_day));
            }

            // If the push occurs within a single segment and shfits the order onto a later moment
            // the indices have to be adjusted as the removal happens first. We also have to account
            // for the rare chance that the segment we're pushing from gets removed.
            total_score_difference += time_difference;
            actions.push(Action::InsertOrder {
                vehicle: to_vehicle,
                day: to_day,
                segment_id: if same_day && to_segment_id > from_segment_id
                    && from_segment.len() == 1
                {
                    to_segment_id - 1
                } else {
                    to_segment_id
                },
                index: if same_segment && to_index > from_index {
                    to_index - 1
                } else {
                    to_index
                },
                order_id: order_id,
                time_delta: time_difference,
                volume_delta: order.volume,
            });
        }

        // Remove the entire from segment if this is the only order left there.
        if from_segment.len() == 1 {
            total_score_difference += -from_segment.duration;
            actions.insert(
                0,
                Action::RemoveSegment {
                    vehicle: from_vehicle,
                    day: from_day,
                    index: from_segment_id,
                },
            );
        } else {
            let old_total_travel_time: Time = self.events[from_vehicle][from_day]
                .iter()
                .map(|segment| segment.duration)
                .sum();

            let last_location = self.get_location_id(from_orders.get(from_index.wrapping_sub(1)));
            let next_location = self.get_location_id(from_orders.get(from_index + 1));
            let time_difference = -self.travel_time[&(last_location, location)]
                - self.travel_time[&(location, next_location)]
                - order.duration
                + self.travel_time[&(last_location, next_location)];

            if old_total_travel_time + time_difference >= DAY_LENGTH {
                return Err(StateError::DayFull);
            }

            // We'll have to make sure the removal happens first or else we might get problems when
            // moving an event within the same segment.
            total_score_difference += time_difference;
            actions.insert(
                0,
                Action::RemoveOrder {
                    vehicle: from_vehicle,
                    day: from_day,
                    segment_id: from_segment_id,
                    index: from_index,
                    order_id: order_id,
                    time_delta: time_difference,
                    volume_delta: -order.volume,
                },
            );
        }

        Ok((total_score_difference, actions))
    }

    /// Removes an order from the schedule. Orders will be removed form all the days they are
    /// scheduled on. If this causes a segment to be empty it will get removed.
    pub fn remove_order(&mut self, order_id: u32) -> Result<(), StateError> {
        let (score_delta, actions) = self.try_remove_order(order_id)?;
        Ok(self.execute_operator(score_delta, &actions))
    }

    /// Try to remove an order. An error will be returned if the order could not be removed. If this
    /// causes a segment to be empty it will get removed.
    pub fn try_remove_order(&self, order_id: u32) -> Result<(Time, Vec<Action>), StateError> {
        if !self.scheduled_orders.contains_key(&order_id) {
            return Err(StateError::NotScheduled);
        }

        let order = &self.orders[&order_id];
        let scheduled_days = &self.scheduled_orders[&order_id];
        let mut actions = Vec::with_capacity(scheduled_days.len());
        let mut total_score_difference = 0;
        for &(vehicle, day, segment_id) in scheduled_days {
            let segment = &self.events[vehicle][day][segment_id];
            // Remove the entire segment if this is the only order in that segment
            if segment.len() == 1 {
                total_score_difference += -segment.duration + order.duration * 3;
                actions.push(Action::RemoveSegment {
                    vehicle: vehicle,
                    day: day,
                    index: segment_id,
                });
                continue;
            }

            let orders = &segment.orders;
            let event_id = orders
                .iter()
                .position(|&order| order == order_id)
                .ok_or(StateError::InvalidParameter)?;

            let last_location = self.get_location_id(orders.get(event_id.wrapping_sub(1)));
            let location = order.location_id;
            let next_location = self.get_location_id(orders.get(event_id + 1));
            let time_difference = -self.travel_time[&(last_location, location)]
                - self.travel_time[&(location, next_location)]
                - order.duration
                + self.travel_time[&(last_location, next_location)];

            total_score_difference += time_difference + order.duration * 3;
            actions.push(Action::RemoveOrder {
                vehicle: vehicle,
                day: day,
                segment_id: segment_id,
                index: event_id,
                order_id: order_id,
                time_delta: time_difference,
                volume_delta: -order.volume,
            });
        }

        Ok((total_score_difference, actions))
    }

    /// Helper for finding the location id of an order, retrieved from `self.events`. If `order` is
    /// `None`, this is either the location before the first or after the last order i.e. the
    /// dumping location.
    pub fn get_location_id(&self, order_id: Option<&u32>) -> u32 {
        match order_id {
            Some(order_id) => self.orders[order_id].location_id,
            None => DUMP_LOCATION,
        }
    }

    /// Calculates what the score should have been in minutes. This is useful for debugging score
    /// fluctuations.
    pub fn debug_recalculate_score(&self) -> f32 {
        let penalty: Time = self.possible_orders
            .par_iter()
            .map(|order_id| {
                self.orders[order_id].frequency as Time * self.orders[order_id].duration * 3
            })
            .sum();

        let mut traveling_score = 0;
        for vehicle in &self.events {
            for day in vehicle {
                for segment in day {
                    if segment.is_empty() {
                        continue;
                    }

                    let orders = &segment.orders;
                    for i in 0..segment.len() + 1 {
                        let order = orders.get(i);
                        let last_location = self.get_location_id(orders.get(i.wrapping_sub(1)));
                        let location = self.get_location_id(order);

                        traveling_score += self.travel_time[&(last_location, location)];
                        if let Some(order_id) = order {
                            traveling_score += self.orders[order_id].duration;
                        }
                    }

                    // Account for the dump
                    traveling_score += DUMPING_TIME;
                }
            }
        }

        (penalty + traveling_score) as f32 / TIME_PER_MINUTE as f32
    }

    /// Checks whether or not a solution is correct and feasible.
    pub fn debug_validate(&self) {
        let mut invalid_solution = false;

        if (self.score() - self.debug_recalculate_score()).abs() > f32::EPSILON {
            invalid_solution = true;
            eprintln!(
                "Calculated score ({}) does not match actual score({})",
                self.score(),
                self.debug_recalculate_score()
            );
        }

        let mut unscheduled_orders: HashSet<_> = self.orders.keys().cloned().collect();
        let mut scheduled_orders = HashMap::new();
        for (vehicle_id, vehicle) in self.events.iter().enumerate() {
            for (day_id, day) in vehicle.iter().enumerate() {
                let mut total_duration = 0;
                for (segment_id, segment) in day.iter().enumerate() {
                    if segment.is_empty() {
                        invalid_solution = true;
                        eprintln!(
                            "V{} D{} S{} :: Empty segment",
                            vehicle_id + 1,
                            day_id + 1,
                            segment_id + 1
                        );
                    }

                    let mut volume = 0;
                    for order_id in &segment.orders {
                        let order = &self.orders[order_id];
                        volume += order.volume;
                        unscheduled_orders.remove(order_id);
                        scheduled_orders
                            .entry(*order_id)
                            .or_insert_with(HashSet::new)
                            .insert((vehicle_id, day_id, segment_id));
                    }

                    if segment.volume != volume {
                        invalid_solution = true;
                        eprintln!(
                            "V{} D{} S{} :: Mismatching volumes (expected {}, actual {})",
                            vehicle_id + 1,
                            day_id + 1,
                            segment_id + 1,
                            volume,
                            segment.volume
                        );
                    }
                    if volume > CAPACITY {
                        invalid_solution = true;
                        eprintln!(
                            "V{} D{} S{} :: Segment over capacity ({})",
                            vehicle_id + 1,
                            day_id + 1,
                            segment_id + 1,
                            volume
                        );
                    }

                    total_duration += segment.duration;
                }

                if total_duration >= DAY_LENGTH {
                    invalid_solution = true;
                    eprintln!(
                        "V{} D{} :: Activity past day end ({} min / 720 min)",
                        vehicle_id + 1,
                        day_id + 1,
                        total_duration as f32 / TIME_PER_MINUTE as f32
                    );
                }
            }
        }

        if unscheduled_orders != self.possible_orders {
            invalid_solution = true;
            eprintln!(
                "Mismatching possible orders (off by {})",
                unscheduled_orders.len() - self.possible_orders.len()
            );
        }
        if scheduled_orders != self.scheduled_orders {
            invalid_solution = true;
            eprintln!("Mismatching scheduled orders",);
        }

        if invalid_solution {
            #[cfg(debug)]
            println!("{}", self);

            panic!("Invalid solution (see above)");
        }
    }

    /// Readjusts the IDs of orders happening *on* and *after* segment `from` with `offset`. This is
    /// useful when inserting or removing segments, or else removals won't work correctly. `after`
    /// indicates whether this adjustment happens before or after actually changing the event lists.
    fn adjust_segment_id(
        &mut self,
        vehicle: usize,
        day: usize,
        from: usize,
        offset: isize,
        after: bool,
    ) {
        for (segment_id, segment) in self.events[vehicle][day].iter().enumerate().skip(from) {
            for order_id in &segment.orders {
                let order_days = self.scheduled_orders.get_mut(order_id).unwrap();
                if after {
                    order_days.remove(&(vehicle, day, (segment_id as isize - offset) as usize));
                    order_days.insert((vehicle, day, segment_id));
                } else {
                    order_days.remove(&(vehicle, day, segment_id));
                    order_days.insert((vehicle, day, (segment_id as isize + offset) as usize));
                }
            }
        }
    }
}

impl Display for State {
    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
        // The output format is `Vehicle; Day; Sequence number; Order ID` with all indices except
        // for order ID starting at 1
        for (vehicle_id, vehicle) in self.events.iter().enumerate() {
            for (day_id, day) in vehicle.iter().enumerate() {
                let mut sequence_number = 1;
                for segment in day {
                    macro_rules! print_order {
                        ($order_id:expr) => {
                            writeln!(
                                f,
                                "{}; {}; {}; {}",
                                vehicle_id + 1,
                                day_id + 1,
                                sequence_number,
                                $order_id
                            )?;
                            sequence_number += 1;
                        }
                    }

                    for order_id in &segment.orders {
                        print_order!(order_id);
                    }

                    // Every segment ends with a trip to the dumping grounds
                    print_order!(DUMP_ORDER_ID);
                }
            }
        }

        Ok(())
    }
}

#[derive(Clone, Debug, Default)]
/// Part of a route, starting and ending at `DUMP_LOCATION`.
pub struct Segment {
    /// The IDs of the orders scheduled in this segment.
    pub orders: Vec<u32>,

    /// The total duration of the segment. This *includes* the dumping time.
    pub duration: Time,
    /// The total hauled volume at the end of the segment. In a valid solution this should always be
    /// less than or equal to `CAPACITY`.
    pub volume: i32,
}

impl Segment {
    pub fn new() -> Segment {
        Segment {
            orders: Vec::new(),
            duration: 0,
            volume: 0,
        }
    }

    pub fn clear(&mut self) {
        self.orders.clear();
        self.duration = 0;
        self.volume = 0;
    }

    pub fn insert(&mut self, index: usize, order_id: u32) {
        self.orders.insert(index, order_id);
    }

    pub fn is_empty(&self) -> bool {
        self.orders.is_empty()
    }

    pub fn len(&self) -> usize {
        self.orders.len()
    }

    pub fn remove(&mut self, index: usize) {
        self.orders.remove(index);
    }
}

#[derive(Debug)]
/// The action that should be performed for the operator. This is done as an optimization so we
/// don't have to calculate information twice. Items are always inserted before `index`.
pub enum Action {
    /// Inserts an order in the specified segment.
    InsertOrder {
        vehicle: usize,
        day: usize,
        segment_id: usize,
        index: usize,
        order_id: u32,
        time_delta: Time,
        volume_delta: i32,
    },
    /// Removes and order in the specified segment.
    RemoveOrder {
        vehicle: usize,
        day: usize,
        segment_id: usize,
        index: usize,
        order_id: u32,
        time_delta: Time,
        volume_delta: i32,
    },
    /// Inserts a new segment before the specified segment.
    InsertSegment {
        vehicle: usize,
        day: usize,
        index: usize,
    },
    /// Removes an entire segment. Any scheduled orders will be readded to `possible_orders`. It is
    /// important that every instance of an order gets removed at the same time.
    RemoveSegment {
        vehicle: usize,
        day: usize,
        index: usize,
    },
    /// Split a segment before `index`. This will introduce a new dump. This is practically the same
    /// as a lot of insertiosn and removals, but with lower overhead.
    SplitSegment {
        vehicle: usize,
        day: usize,
        segment_id: usize,
        index: usize,
        durations: (Time, Time),
        volumes: (i32, i32),
    },
    /// Merge the segment at `segment_id` with the one happening after it. This would be the same as
    /// removing a dump.
    MergeSegment {
        vehicle: usize,
        day: usize,
        segment_id: usize,
        duration: Time,
        volume: i32,
    },
}

#[derive(Debug)]
/// Representds a single order from `orders.txt`.
pub struct Order {
    /// The corrosponding ID of the order location in the traveling time matrix.
    pub location_id: u32,
    /// The number of time units it would take the haul the garbage.
    pub duration: Time,
    pub frequency: usize,
    /// The (already compressed) volume of the order.
    pub volume: i32,
}

impl Order {
    pub fn days(&self) -> &[&[usize]] {
        ORDER_DAYS[self.frequency - 1]
    }
}