1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

//! Simple hashed wheel timer with bounded interval.
//!
//! Relevant:
//! http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf

use std::mem;
use std::ops::IndexMut;

/// A simple wheel timer implementation with a fixed ring size.
pub struct WheelTimer<T> {
  max_interval: usize,
  current_tick: usize,
  size: usize,

  ring: Vec<Vec<T>>
}

/// Iterator implementation allows for using the wheel timer in a for loop.
///
/// # Example
///
/// ```
/// use wheel_timer::WheelTimer;
///
/// let mut timer: WheelTimer<usize> = WheelTimer::new(20);
/// for result in timer {
///   // result is a vector of the values at that step
/// }
/// ```
impl<T> Iterator for WheelTimer<T> {
  type Item = Vec<T>;

  fn next(&mut self) -> Option<Vec<T>> {
    let size = self.size();
    return if size > 0 {
      Some(self.tick())
    } else {
      None
    };
  }
}

impl<T> WheelTimer<T> {

  /// Creates a new timer with the specified max interval.
  ///
  /// # Example
  ///
  /// ```
  /// use wheel_timer::WheelTimer;
  ///
  /// let mut timer: WheelTimer<usize> = WheelTimer::new(20);
  /// ```
  pub fn new(max_interval: usize) -> WheelTimer<T> {
    // Initialize the ring with Nil values
    let mut ring = Vec::with_capacity(max_interval);
    for _ in 0..max_interval {
      ring.push(Vec::new())
    }

    return WheelTimer{
      max_interval: max_interval,
      current_tick: 0,
      ring: ring,
      size: 0,
    }
  }

  /// Returns the number of items currently scheduled.
  ///
  /// # Example
  ///
  /// ```
  /// use wheel_timer::WheelTimer;
  ///
  /// let mut timer: WheelTimer<usize> = WheelTimer::new(20);
  /// timer.schedule(4, 1);
  /// timer.schedule(7, 1);
  /// timer.schedule(1, 1);
  /// assert_eq!(timer.size(), 3);
  /// ```
  pub fn size(&self) -> usize {
    self.size
  }

  /// Schedules a new value, available after `ticks` have passed.
  ///
  /// # Example
  ///
  /// ```
  /// use wheel_timer::WheelTimer;
  ///
  /// let mut timer: WheelTimer<usize> = WheelTimer::new(20);
  /// timer.schedule(4, 7); // schedule value 7 for 4 ticks
  /// ```
  pub fn schedule(&mut self, ticks: usize, value: T) {
    // Compute the scheduled position in the wheel
    let index = (self.current_tick + ticks) % self.max_interval;

    // Get the current node at `index` in the wheel and append the new node
    self.ring.index_mut(index).push(value);

    // Increment the size counter
    self.size = self.size + 1;
  }

  /// Tick the timer, returning the node at the current tick.
  ///
  /// # Example
  ///
  /// ```
  /// use wheel_timer::WheelTimer;
  ///
  /// let mut timer: WheelTimer<usize> = WheelTimer::new(20);
  /// timer.schedule(3, 4); // schedule value 4 for 3 ticks
  /// timer.tick();
  /// timer.tick();
  /// timer.tick();
  /// let result = timer.tick(); // vec![4]
  /// assert_eq!(result.len(), 1);
  /// ```
  pub fn tick(&mut self) -> Vec<T> {
    // Get the node at the current tick in the wheel
    let node = mem::replace(self.ring.index_mut(self.current_tick), Vec::new());

    // Increment the timer
    self.current_tick = (self.current_tick + 1) % self.max_interval;

    // Reduce the size by the length of the removed node
    self.size = self.size - node.len();

    // Return the node that was in that spot
    return node
  }
}