perty 0.0.1

#![doc = include_str!("../README.md")]

use std::{
    cell::RefCell,
    collections::VecDeque,
    rc::{Rc, Weak},
};

use rand::{
    Rng,
    distr::{Distribution, Uniform},
};
use rand_distr::Triangular;
use serde::{Deserialize, Serialize};
use thiserror::Error;

/// A struct that contains the data necessary to resolve a PERT task. Use
/// `PertTask::new` in your impl of `TryIntoTask` to construct one for
/// your own task struct definition.
#[non_exhaustive] // Used to prevent users of the library constructing it without using our constructor (`new`).
#[derive(Debug, Clone, Serialize)]
pub struct PertTask {
    /// A unique id for the task.
    pub id: String,
    /// A vec of ids that are direct dependencies for the task.
    pub deps: Vec<String>,
    /// The duration of the task.
    pub duration: f32,
    /// The earliest time the task can start.
    pub early_start_time: f32,
    /// The earliest time the task can finish.
    pub early_finish_time: f32,
    /// The latest time the task can start.
    pub late_start_time: f32,
    /// The latest time the task can finish.
    pub late_finish_time: f32,
    /// A list of PertTasks the task depends on. A private field that is constructed when `solve_pert` is run.
    #[serde(skip_serializing)]
    parents: Vec<PertTaskWeakRef>,
    /// A list of PertTasks the tasks is a dependent. A private filed that is constructed when `solve_pert` is run.
    #[serde(skip_serializing)]
    children: Vec<PertTaskWeakRef>,
}

/// Rolling our own implementation of `PartialEq` for `PertTask`.
/// We check whether two task references have the same `id`.
impl PartialEq for PertTask {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

impl PertTask {
    /// Create a new `PertTask`. This is only way a `PertTask` can be constructed.
    pub fn new(id: String, deps: Vec<String>, duration: f32) -> PertTask {
        Self {
            id,
            deps,
            duration,
            early_start_time: 0.,
            early_finish_time: f32::MIN,
            late_start_time: f32::MAX,
            late_finish_time: f32::MAX,
            parents: Vec::new(),
            children: Vec::new(),
        }
    }

    /// Reports `true` if the tasks is on the critical path.
    pub fn is_critical(&self) -> bool {
        let diff = (self.late_start_time - self.early_start_time).abs();
        diff < 0.001
    }

    /// Reports the slack time for a task.
    pub fn slack(&self) -> f32 {
        self.late_start_time - self.early_start_time
    }
}

/// A convenience type encapsulating `Rc`, `RefCell` and `PertTask`.
type PertTaskRcRef = Rc<RefCell<PertTask>>;

/// A convenience type encapsulating `Weak`, `RefCell` and `PertTask`.
type PertTaskWeakRef = Weak<RefCell<PertTask>>;

/// The primary trait that this crate and the functionality it provides is built around.
/// The user of the library should implement this for their data struct which is likely
/// to contain more task-related information than is required for a PERT analysis.
/// It requires the user to implement `try_into_pert_task` where they can provide their
/// own error type for cases where the task may not be able to be return a `PertTask`.
/// The user should extract the information they require from their struct and call `PertTask::new`
/// to construct the `PertTask`. Have a look at the impl for `Task` from this library for an
/// example.
pub trait TryIntoPertTask {
    type Error;
    /// Return a PertTask from your own task struct. Note. It does not consume the original task.
    fn try_into_pert_task(&self) -> Result<PertTask, Self::Error>;
}

/// The trait introduces the `solve_pert` functionality. The crate has implemented it
/// for any `Vec<T>` where `T` implements `TryIntoPertTask`.
pub trait Pert {
    type Error;

    /// Take the `Vec<T>` and try and return a vec of pert tasks.
    fn try_into_pert_tasks(&self) -> Result<Vec<PertTask>, PertError<Self::Error>>;

    /// Solve the PERT problem
    fn solve_pert(&self, max_iter: usize) -> Result<Vec<PertTask>, PertError<Self::Error>>;
}

/// The different types of error that could be returned when solving the PERT problem.
#[derive(Debug)]
pub enum PertError<T> {
    /// Can return a vec of task errors when iterating through the slice of tasks and
    /// running `try_into_pert_task`.
    TaskErrors(Vec<T>),
    /// The check the tasks ids referenced by other tasks exist has concluded some were
    /// missing.
    MissingTasks(Vec<String>),
    /// No starting task(s) were found in the vec.
    NoStartingTasks,
    /// The solver has taken too many iterations to complete. There may be cyclic dependencies.
    MaxIterReached(usize),
}

/// Implementing the `Pert` trait for `Vec<T>`. Therefore, users can simply import the trait
/// and get the functionality.
impl<T> Pert for Vec<T>
where
    T: TryIntoPertTask + PartialEq,
{
    type Error = T::Error;

    /// Default implementation iterates over the tasks that implement `PertTask` and calls
    /// `try_into_pert_task`. It collects all try_into errors which could be fed back to
    /// the user to make the amendments to their tasks. Otherwise it returns a vec of `PertTask`.
    fn try_into_pert_tasks(&self) -> Result<Vec<PertTask>, PertError<T::Error>> {
        let mut tasks: Vec<PertTask> = Vec::new();
        let mut errs: Vec<Self::Error> = Vec::new();
        for t in self.iter() {
            match t.try_into_pert_task() {
                Ok(t) => tasks.push(t),
                Err(e) => errs.push(e),
            }
        }
        match errs.is_empty() {
            true => Ok(tasks),
            false => Err(PertError::TaskErrors(errs)),
        }
    }

    /// Solve the pert problem for the `Vec<T>`.
    fn solve_pert(&self, max_iter: usize) -> Result<Vec<PertTask>, PertError<T::Error>> {
        // Wrap in a bunch of Rc refs so we can build up the pert graph.
        let mut tasks: Vec<PertTaskRcRef> = self
            .try_into_pert_tasks()?
            .into_iter()
            .map(|t| Rc::new(RefCell::new(t)))
            .collect();
        build_parent_edges::<T>(&mut tasks)?;
        build_child_edges(&mut tasks);
        solve_early_times::<T>(&mut tasks, max_iter)?;
        solve_late_times::<T>(&mut tasks, max_iter)?;
        // Return it back to a vec of tasks for the consumer.
        let owned: Vec<PertTask> = tasks
            .into_iter()
            .map(|t| {
                let t = Rc::try_unwrap(t).expect("Should only have one strong rc");
                let mut t = t.into_inner();
                t.parents.clear();
                t.children.clear();
                t
            })
            .collect();
        Ok(owned)
    }
}

/// Builds the parent associations in a PERT graph.
fn build_parent_edges<T: TryIntoPertTask>(
    tasks: &mut [PertTaskRcRef],
) -> Result<(), PertError<T::Error>> {
    let mut missing: Vec<String> = Vec::new();
    for a in tasks.iter() {
        let mut a = a.borrow_mut();
        let deps = a.deps.to_owned();
        for d in deps {
            let mut flag = false;
            for b in tasks.iter() {
                if b.borrow().id == d {
                    a.parents.push(Rc::downgrade(b));
                    flag = true;
                    break;
                }
            }
            if !flag {
                missing.push(d);
            }
        }
    }
    if !missing.is_empty() {
        return Err(PertError::MissingTasks(missing));
    }
    Ok(())
}

/// Builds the child associations in a PERT graph.
fn build_child_edges(tasks: &mut [PertTaskRcRef]) {
    // TODO: no checks for whether it has been built already.
    for a in tasks.iter() {
        for b in tasks.iter() {
            if a != b {
                let weak_a = Rc::downgrade(a);
                let is_in = b.borrow().parents.iter().any(|p| Weak::ptr_eq(p, &weak_a));
                if is_in {
                    a.borrow_mut().children.push(Rc::downgrade(b));
                }
            }
        }
    }
}

/// Solves the early times for the PERT grpah.
fn solve_early_times<T: TryIntoPertTask>(
    tasks: &mut [PertTaskRcRef],
    max_iter: usize,
) -> Result<(), PertError<T::Error>> {
    let mut processing: VecDeque<PertTaskRcRef> = VecDeque::new();

    // Find the start tasks. Typically one.
    for t in tasks.iter() {
        if t.borrow().parents.is_empty() {
            processing.push_back(t.clone());
        }
    }

    if processing.is_empty() {
        return Err(PertError::NoStartingTasks);
    }

    // Early times
    let mut n: usize = 0;
    while let Some(task) = processing.pop_front() {
        n += 1;
        if n > max_iter {
            return Err(PertError::MaxIterReached(max_iter));
        }

        let mut parent = task.borrow_mut();
        let early_finish_time = parent.early_start_time + parent.duration;
        parent.early_finish_time = early_finish_time;

        for child in parent.children.iter() {
            let child = child.upgrade().unwrap();
            if parent.early_finish_time > child.borrow().early_start_time {
                child.borrow_mut().early_start_time = parent.early_finish_time;
                processing.push_back(child);
            }
        }
    }

    Ok(())
}

/// Solves the late times in a PERT graph.
fn solve_late_times<T: TryIntoPertTask>(
    tasks: &mut [PertTaskRcRef],
    max_iter: usize,
) -> Result<(), PertError<T::Error>> {
    let mut processing: VecDeque<PertTaskRcRef> = VecDeque::new();

    // Find the latest early finish time.
    let mut latest: f32 = 0.;
    for t in tasks.iter() {
        let t = t.borrow();
        let time = t.early_finish_time;
        if time > latest {
            latest = time;
        }
    }

    // Find the activities with no children (could add a check early on for this.)
    for task in tasks.iter() {
        if task.borrow().children.is_empty() {
            task.borrow_mut().late_finish_time = latest;
            processing.push_back(task.clone());
        }
    }

    let mut n: usize = 0;
    while let Some(child) = processing.pop_front() {
        n += 1;
        if n > max_iter {
            return Err(PertError::MaxIterReached(max_iter));
        }
        let mut child = child.borrow_mut();
        let delta = child.late_finish_time - child.duration;
        child.late_start_time = delta;
        for parent in child.parents.iter() {
            let parent = parent.upgrade().unwrap();
            let mut p = parent.borrow_mut();
            if p.late_finish_time > child.late_start_time {
                p.late_finish_time = child.late_start_time;
                processing.push_back(parent.clone())
            }
        }
    }

    Ok(())
}

/// A minimal task descriptor that can implement `TryIntoPertTask`.
#[derive(Debug, Serialize, Deserialize)]
pub struct Task {
    pub id: String,
    pub deps: Vec<String>,
    pub duration: Duration,
}

impl PartialEq for Task {
    fn eq(&self, other: &Self) -> bool {
        self.id == other.id
    }
}

/// An enum detailing the distributions accepted by `Task` which are then called
/// to generate a single value for the task for a PERT run.
#[derive(Debug, Serialize, Deserialize)]
#[non_exhaustive]
#[serde(tag = "type")]
pub enum Duration {
    /// Used for a constant value duration.
    Constant(f32),
    /// Computes the expected time, $e$, for the task to complete.
    /// Calculated from the following:
    /// $$e = \frac{o+4m+p}{6}$$
    /// where: $o$ is the Optimistic Time, $m$ is the Most Likely Time,
    /// and $p$ is the Pessimistic Time.
    Pert {
        optimistic: f32,
        most_likely: f32,
        pessimistic: f32,
    },
    /// Sample a tasks duration from a uniform distribution
    Uniform { min: f32, max: f32 },
    /// Sample a tasks duration from a triangular distribution.
    Triangular { min: f32, max: f32, mode: f32 },
}

#[non_exhaustive]
#[derive(Debug, Error)]
pub enum DurationError {
    #[error("There is something wrong with the bounds you have submitted. Received: {0:?}")]
    ParameterMisMatch(Vec<f32>),
}

impl Duration {
    fn sample(&self) -> Result<f32, DurationError> {
        match self {
            Self::Constant(c) => Ok(*c),
            Self::Pert {
                optimistic,
                most_likely,
                pessimistic,
            } => {
                if 0. > *optimistic || 0. > *most_likely || 0. > *pessimistic {
                    return Err(DurationError::ParameterMisMatch(vec![
                        *optimistic,
                        *most_likely,
                        *pessimistic,
                    ]));
                }
                if optimistic > most_likely || most_likely > pessimistic {
                    return Err(DurationError::ParameterMisMatch(vec![
                        *optimistic,
                        *most_likely,
                        *pessimistic,
                    ]));
                }
                Ok((optimistic + 4. * most_likely + pessimistic) / 6.)
            }
            Self::Uniform { min, max } => {
                let mut rng = rand::rng();
                match Uniform::new(min, max) {
                    Ok(u) => Ok(rng.sample(u)),
                    Err(_) => Err(DurationError::ParameterMisMatch(vec![*min, *max])),
                }
            }
            Self::Triangular { min, max, mode } => {
                let mut rng = rand::rng();
                match Triangular::new(*min, *max, *mode) {
                    Ok(u) => Ok(u.sample(&mut rng)),
                    Err(_) => Err(DurationError::ParameterMisMatch(vec![*min, *max])),
                }
            }
        }
    }
}

impl Task {
    /// Create a new task.
    pub fn new(id: String, deps: Vec<String>, duration: Duration) -> Task {
        Self { id, deps, duration }
    }
}

impl TryIntoPertTask for Task {
    type Error = DurationError;
    fn try_into_pert_task(&self) -> Result<PertTask, Self::Error> {
        let d = self.duration.sample()?;
        let node = PertTask::new(self.id.clone(), self.deps.clone(), d);
        Ok(node)
    }
}

/// A trait the provides some common post processing analysis following a PERT solution.
pub trait PostProcess {
    /// Return the duration of the project.
    fn project_duration(&self) -> f32;
    /// Return a vec of references to the tasks on the critical path.
    fn critical_tasks(&self) -> Vec<&PertTask>;
}

impl PostProcess for Vec<PertTask> {
    /// Return project duration from a PERT run.
    fn project_duration(&self) -> f32 {
        let mut max: f32 = 0.;
        for t in self.iter() {
            let t = t.early_finish_time;
            if t > max {
                max = t
            }
        }
        max
    }

    /// Return the critical tasks.
    fn critical_tasks(&self) -> Vec<&PertTask> {
        self.iter().filter(|t| t.is_critical()).collect()
    }
}

/// A trait the provides post processing analyses over multiple PERT runs where one
/// has sampled their tasks distributions many times.
pub trait MontePostProcess {
    /// Returns the mean project duration across all the runs.
    fn mean_project_duration(&self) -> f32;
    /// Returns the median project duration.
    fn median_project_duration(&self) -> f32;
    /// Computes the ratio of how often the tasks exist on the critical path. Monte-Carlo
    /// simulations help identify the tasks that are always on the critical path and those
    /// that may be based on how the various task durations play out.
    fn task_criticality(&self) -> Vec<(String, f32)>;
}

impl MontePostProcess for Vec<Vec<PertTask>> {
    /// Find the mean project duration
    fn mean_project_duration(&self) -> f32 {
        let mut sum = 0.;
        for run in self.iter() {
            sum += run.project_duration();
        }
        sum / self.len() as f32
    }

    /// Find the median project duration
    fn median_project_duration(&self) -> f32 {
        let mut durations: Vec<f32> = self.iter().map(|t| t.project_duration()).collect();
        durations.sort_by(|a, b| a.partial_cmp(b).unwrap());
        let len = durations.len();
        if len % 2 == 1 {
            durations[len / 2]
        } else {
            let mid1 = durations[len / 2 - 1];
            let mid2 = durations[len / 2];
            (mid1 + mid2) / 2.0
        }
    }

    /// Report the ratio of how often the task lies on the critical path across
    /// all the PERT runs.
    fn task_criticality(&self) -> Vec<(String, f32)> {
        let mut tc: Vec<(String, f32)> = Vec::new();
        for t in self[0].iter() {
            tc.push((t.id.clone(), 0.0));
        }
        for run in self.iter() {
            for (a, b) in tc.iter_mut().zip(run) {
                if b.is_critical() {
                    a.1 += 1.0;
                }
            }
        }
        let n = self.len() as f32;
        for t in tc.iter_mut() {
            t.1 /= n;
        }
        tc
    }
}