rework boon tracking

4 files changed, 230 insertions, 50 deletions

diff --git a/src/statistics/boon.rs b/src/statistics/boon.rs
index 425f4a5..8175537 100644
--- a/src/statistics/boon.rs
+++ b/src/statistics/boon.rs
@@ -1,5 +1,14 @@
+//! Module providing functions and structs to deal with boon related statistics.
 use std::cmp;
 
+use std::collections::HashMap;
+use std::fmt;
+use std::ops::Mul;
+
+use super::math::{Monoid, RecordFunc, Semigroup};
+
+use fnv::FnvHashMap;
+
 /// The type of a boon.
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 pub enum BoonType {
@@ -40,6 +49,7 @@ pub struct BoonQueue {
     capacity: u32,
     queue: Vec<u64>,
     boon_type: BoonType,
+    next_update: u64,
 }
 
 impl BoonQueue {
@@ -52,6 +62,7 @@ impl BoonQueue {
             capacity,
             queue: Vec::new(),
             boon_type,
+            next_update: 0,
         }
     }
 
@@ -75,6 +86,7 @@ impl BoonQueue {
     pub fn add_stack(&mut self, duration: u64) {
         self.queue.push(duration);
         self.fix_queue();
+        self.next_update = self.next_change();
     }
 
     /// Return the amount of current stacks.
@@ -100,6 +112,10 @@ impl BoonQueue {
         if duration == 0 {
             return;
         }
+        if duration < self.next_update {
+            self.next_update -= duration;
+            return;
+        }
         let mut remaining = duration;
         match self.boon_type {
             BoonType::Duration => {
@@ -125,6 +141,7 @@ impl BoonQueue {
                     .collect();
             }
         }
+        self.next_update = self.next_change();
     }
 
     /// Remove all stacks.
@@ -163,6 +180,112 @@ impl BoonQueue {
     }
 }
 
+/// Amount of stacks of a boon.
+// Since this is also used to represent changes in stacks, we need access to
+// negative numbers too, as stacks can drop.
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+pub struct Stacks(i32);
+
+impl Semigroup for Stacks {
+    #[inline]
+    fn combine(&self, other: &Self) -> Self {
+        Stacks(self.0 + other.0)
+    }
+}
+
+impl Monoid for Stacks {
+    #[inline]
+    fn mempty() -> Self {
+        Stacks(0)
+    }
+}
+
+// This shouldn't be negative, as total stacks are always greater than 0, thus
+// the area below the curve will always be positive.
+#[derive(Clone, Copy, Debug, PartialEq, Eq)]
+#[doc(hidden)]
+pub struct BoonArea(u64);
+
+impl Semigroup for BoonArea {
+    #[inline]
+    fn combine(&self, other: &Self) -> Self {
+        BoonArea(self.0 + other.0)
+    }
+}
+
+impl Monoid for BoonArea {
+    #[inline]
+    fn mempty() -> Self {
+        BoonArea(0)
+    }
+}
+
+impl Mul<u64> for Stacks {
+    type Output = BoonArea;
+
+    #[inline]
+    fn mul(self, rhs: u64) -> BoonArea {
+        BoonArea(self.0 as u64 * rhs)
+    }
+}
+
+/// A boon log for a specific player.
+///
+/// This logs the amount of stacks of each boon a player had at any given time.
+#[derive(Clone, Default)]
+pub struct BoonLog {
+    // Keep a separate RecordFunc for each boon.
+    inner: FnvHashMap<u16, RecordFunc<u64, (), Stacks>>,
+}
+
+impl BoonLog {
+    /// Create a new, empty boon log.
+    pub fn new() -> Self {
+        Default::default()
+    }
+
+    /// Add an event to the boon log.
+    pub fn log(&mut self, time: u64, boon_id: u16, stacks: u32) {
+        let func = self.inner.entry(boon_id).or_insert_with(Default::default);
+        let current = func.tally();
+        if current.0 == stacks as i32 {
+            return;
+        }
+        let diff = stacks as i32 - current.0;
+        func.insert(time, (), Stacks(diff));
+    }
+
+    /// Get the average amount of stacks between the two given time points.
+    ///
+    /// * `a` - Start time point.
+    /// * `b` - End time point.
+    /// * `boon_id` - ID of the boon that you want to get the average for.
+    pub fn average_stacks(&self, a: u64, b: u64, boon_id: u16) -> f32 {
+        assert!(b > a);
+        let func = if let Some(f) = self.inner.get(&boon_id) {
+            f
+        } else {
+            return 0.;
+        };
+        let area = func.integral(&a, &b);
+        area.0 as f32 / (b - a) as f32
+    }
+
+    /// Get the amount of stacks at the given time point.
+    ///
+    /// * `x` - Time point.
+    /// * `boon_id` - ID of the boon that you want to get.
+    pub fn stacks_at(&self, x: u64, boon_id: u16) -> u32 {
+        self.inner.get(&boon_id).map(|f| f.get(&x)).unwrap_or(0)
+    }
+}
+
+impl fmt::Debug for BoonLog {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "BoonLog {{ .. }}")
+    }
+}
+
 #[cfg(test)]
 mod test {
     use super::*;
diff --git a/src/statistics/math.rs b/src/statistics/math.rs
index f0b0384..b7dd6ac 100644
--- a/src/statistics/math.rs
+++ b/src/statistics/math.rs
@@ -1,5 +1,8 @@
 //! This module provides some basic mathematical structures.
 
+use std::iter;
+use std::ops::{Mul, Sub};
+
 /// A semigroup.
 ///
 /// This trait lets you combine elements by a binary operation.
@@ -138,6 +141,39 @@ where
     }
 }
 
+impl<X, T, D, A> RecordFunc<X, T, D>
+where
+    X: Ord + Sub<X, Output = X> + Copy,
+    D: Monoid + Mul<X, Output = A>,
+    A: Monoid,
+{
+    #[inline]
+    pub fn integral(&self, a: &X, b: &X) -> A {
+        self.integral_only(a, b, |_| true)
+    }
+
+    pub fn integral_only<F: FnMut(&T) -> bool>(&self, a: &X, b: &X, mut predicate: F) -> A {
+        let points = self
+            .data
+            .iter()
+            .skip_while(|record| record.x < *a)
+            .take_while(|record| record.x <= *b)
+            .filter(|record| predicate(&record.tag))
+            .map(|record| record.x)
+            .chain(iter::once(*b))
+            .collect::<Vec<_>>();
+        let mut area = A::mempty();
+        let mut last = *a;
+        for point in points {
+            let diff = point - last;
+            let value = self.get_only(&last, &mut predicate);
+            area = area.combine(&(value * diff));
+            last = point;
+        }
+        area
+    }
+}
+
 impl<X: Ord, T, D: Monoid> Default for RecordFunc<X, T, D> {
     fn default() -> Self {
         Self::new()
diff --git a/src/statistics/mod.rs b/src/statistics/mod.rs
index 5f2f288..0254135 100644
--- a/src/statistics/mod.rs
+++ b/src/statistics/mod.rs
@@ -9,6 +9,7 @@ pub mod gamedata;
 pub mod math;
 pub mod trackers;
 
+use self::boon::BoonLog;
 use self::damage::DamageLog;
 use self::trackers::{RunnableTracker, Tracker};
 
@@ -53,7 +54,7 @@ pub struct AgentStats {
     ///
     /// For duration-based boons, the average amount of stacks is the same as
     /// the uptime.
-    pub boon_averages: HashMap<u16, f64>,
+    pub boon_log: BoonLog,
     /// Time when the agent has entered combat (millseconds since log start).
     pub enter_combat: u64,
     /// Time when the agent has left combat (millseconds since log start).
@@ -87,6 +88,7 @@ pub fn calculate(log: &Log) -> StatResult<Statistics> {
     let mut damage_tracker = trackers::DamageTracker::new(log);
     let mut log_start_tracker = trackers::LogStartTracker::new();
     let mut combat_time_tracker = trackers::CombatTimeTracker::new();
+    let mut boon_tracker = trackers::BoonTracker::new();
 
     run_trackers(
         log,
@@ -94,6 +96,7 @@ pub fn calculate(log: &Log) -> StatResult<Statistics> {
             &mut damage_tracker,
             &mut log_start_tracker,
             &mut combat_time_tracker,
+            &mut boon_tracker,
         ],
     )?;
 
@@ -104,14 +107,27 @@ pub fn calculate(log: &Log) -> StatResult<Statistics> {
         let agent = agent_stats
             .entry(*agent_addr)
             .or_insert_with(Default::default);
+        // XXX: This used to be enter_time - log_start_time, as it makes more
+        // sense to have the time relative to the log start instead of the
+        // Windows boot time. However, this also means that we need to modify
+        // all event times before we do any tracking, as many trackers rely on
+        // event.time to track information related to time.
         if enter_time != 0 {
-            agent.enter_combat = enter_time - log_start_time;
+            agent.enter_combat = enter_time;
         }
         if exit_time != 0 {
-            agent.exit_combat = exit_time - log_start_time;
+            agent.exit_combat = exit_time;
         }
     }
 
+    let boon_logs = try_tracker!(boon_tracker.finalize());
+    for (agent_addr, boon_log) in boon_logs {
+        let agent = agent_stats
+            .entry(agent_addr)
+            .or_insert_with(Default::default);
+        agent.boon_log = boon_log;
+    }
+
     let damage_log = try_tracker!(damage_tracker.finalize());
 
     Ok(Statistics {
diff --git a/src/statistics/trackers.rs b/src/statistics/trackers.rs
index 11e51f2..5eda86c 100644
--- a/src/statistics/trackers.rs
+++ b/src/statistics/trackers.rs
@@ -20,10 +20,12 @@ use std::collections::HashMap;
 use std::error::Error;
 
 use super::super::{Event, EventKind, Log};
-use super::boon::BoonQueue;
+use super::boon::{BoonLog, BoonQueue};
 use super::damage::{DamageLog, DamageType};
 use super::gamedata::{self, Mechanic, Trigger};
 
+use fnv::FnvHashMap;
+
 /// A tracker.
 ///
 /// A tracker should be responsible for tracking a single statistic. Each
@@ -224,22 +226,18 @@ impl Tracker for CombatTimeTracker {
 /// This tracker only tracks the boons that are known to evtclib, that is the
 /// boons defined in `evtclib::statistics::gamedata::BOONS`.
 pub struct BoonTracker {
-    agent_addr: u64,
-    boon_areas: HashMap<u16, u64>,
-    boon_queues: HashMap<u16, BoonQueue>,
+    boon_logs: FnvHashMap<u64, BoonLog>,
+    boon_queues: FnvHashMap<u64, FnvHashMap<u16, BoonQueue>>,
     last_time: u64,
-    next_update: u64,
 }
 
 impl BoonTracker {
     /// Creates a new boon tracker for the given agent.
-    pub fn new(agent_addr: u64) -> BoonTracker {
+    pub fn new() -> BoonTracker {
         BoonTracker {
-            agent_addr,
-            boon_areas: Default::default(),
+            boon_logs: Default::default(),
             boon_queues: Default::default(),
             last_time: 0,
-            next_update: 0,
         }
     }
 
@@ -247,46 +245,50 @@ impl BoonTracker {
     ///
     /// * `delta_t` - Amount of milliseconds to update.
     fn update_queues(&mut self, delta_t: u64) {
+        if delta_t == 0 {
+            return;
+        }
+
         self.boon_queues
             .values_mut()
+            .flat_map(|m| m.values_mut())
             .for_each(|queue| queue.simulate(delta_t));
 
         // Throw away empty boon queues or to improve performance
+        self.boon_queues
+            .values_mut()
+            .for_each(|m| m.retain(|_, q| !q.is_empty()));
         self.boon_queues.retain(|_, q| !q.is_empty());
     }
 
-    /// Update the internal tracking areas.
-    ///
-    /// Does not update the boon queues.
-    ///
-    /// * `delta_t` - Amount of milliseconds that passed.
-    fn update_areas(&mut self, delta_t: u64) {
-        for (buff_id, queue) in &self.boon_queues {
-            let current_stacks = queue.current_stacks();
-            let area = self.boon_areas.entry(*buff_id).or_insert(0);
-            *area += current_stacks as u64 * delta_t;
+    fn update_logs(&mut self, time: u64) {
+        if time == self.last_time {
+            return;
+        }
+        for (agent, boons) in &self.boon_queues {
+            let agent_log = self
+                .boon_logs
+                .entry(*agent)
+                .or_insert_with(Default::default);
+            for (boon_id, queue) in boons {
+                agent_log.log(time, *boon_id, queue.current_stacks());
+            }
         }
-    }
-
-    fn update_next_update(&mut self) {
-        let next_update = self
-            .boon_queues
-            .values()
-            .map(BoonQueue::next_update)
-            .filter(|v| *v != 0)
-            .min()
-            .unwrap_or(0);
-        self.next_update = next_update;
     }
 
     /// Get the boon queue for the given buff_id.
     ///
     /// If the queue does not yet exist, create it.
     ///
+    /// * `agent_addr` - The address of the agent.
     /// * `buff_id` - The buff (or condition) id.
-    fn get_queue(&mut self, buff_id: u16) -> Option<&mut BoonQueue> {
+    fn get_queue(&mut self, agent_addr: u64, buff_id: u16) -> Option<&mut BoonQueue> {
         use std::collections::hash_map::Entry;
-        let entry = self.boon_queues.entry(buff_id);
+        let entry = self
+            .boon_queues
+            .entry(agent_addr)
+            .or_insert_with(Default::default)
+            .entry(buff_id);
         match entry {
             // Queue already exists
             Entry::Occupied(e) => Some(e.into_mut()),
@@ -304,45 +306,48 @@ impl BoonTracker {
 }
 
 impl Tracker for BoonTracker {
-    type Stat = HashMap<u16, u64>;
+    type Stat = HashMap<u64, BoonLog>;
     type Error = !;
 
     fn feed(&mut self, event: &Event) -> Result<(), Self::Error> {
-
         let delta_t = event.time - self.last_time;
-        if self.next_update != 0 && delta_t > self.next_update {
-            self.update_queues(delta_t);
-            self.update_areas(delta_t);
-            self.update_next_update();
-            self.last_time = event.time;
-        }
+        self.update_queues(delta_t);
 
         match event.kind {
             EventKind::BuffApplication {
-                buff_id, duration, ..
+                destination_agent_addr,
+                buff_id,
+                duration,
+                ..
             } => {
-                if let Some(queue) = self.get_queue(buff_id) {
+                if let Some(queue) = self.get_queue(destination_agent_addr, buff_id) {
                     queue.add_stack(duration as u64);
                 }
-                self.update_next_update();
             }
 
             // XXX: Properly handle SINGLE and MANUAL removal types
-            EventKind::BuffRemove { buff_id, .. } => {
-                if let Some(queue) = self.get_queue(buff_id) {
+            EventKind::BuffRemove {
+                destination_agent_addr,
+                buff_id,
+                ..
+            } => {
+                if let Some(queue) = self.get_queue(destination_agent_addr, buff_id) {
                     queue.clear();
                 }
-                self.update_next_update();
             }
 
             _ => (),
         }
+        self.update_logs(event.time);
+        self.last_time = event.time;
 
         Ok(())
     }
 
     fn finalize(self) -> Result<Self::Stat, Self::Error> {
-        Ok(self.boon_areas)
+        // Convert from FnvHashMap to HashMap in order to not leak
+        // implementation details.
+        Ok(self.boon_logs.into_iter().collect())
     }
 }