avr-oxide 0.2.2

/* delayq.rs
 *
 * Developed by Tim Walls <tim.walls@snowgoons.com>
 * Copyright (c) All Rights Reserved, Tim Walls
 */
//! Simple delay queue implementation


// Imports ===================================================================
use core::ops::{Sub, SubAssign};
use avr_oxide::alloc::vec::Vec;
use avr_oxide::alloc::boxed::Box;

// Declarations ==============================================================

/**
 * Trait implemented for types that have a minimum bound
 */
pub trait Floored {

  /// Return the minimum possible value for this type
  ///
  /// # Invariant
  /// The critical invariant for any type implementing this trait is this:
  ///   `(X) - (X) == floor()` for all `X`
  fn floor() -> Self;
}

pub trait DelayQueue<C,T>
where
  C: Sub + SubAssign + Eq + Ord + Copy + Floored
{
  fn insert_at(&mut self, position: C, item: T);

  fn decrement(&mut self, by: C);

  fn consume_next_ready(&mut self) -> Option<T>;
}

pub struct SimpleDelayQueue<C,T>
where
  C: Sub + SubAssign + Eq + Ord + Copy + Floored
{
  first: Option<Box<SimpleDelayQueueElement<C,T>>>,
  ready: Vec<T>
}

pub struct SimpleDelayQueueElement<C,T> {
  counter: C,
  contains: T,

  next: Option<Box<Self>>
}

// Code ======================================================================
impl Floored for u8 {
  fn floor() -> Self {
    0u8
  }
}
impl Floored for u16 {
  fn floor() -> Self {
    0u16
  }
}
impl Floored for u32 {
  fn floor() -> Self {
    0u32
  }
}


impl<C,T> SimpleDelayQueue<C,T>
where
  C: Sub + SubAssign + Eq + Ord + Copy + Floored
{
  /// Create a new, empty delay queue
  pub fn new() -> Self {
    SimpleDelayQueue {
      first: Option::None,
      ready: Vec::new()
    }
  }

  /// Pop all the ready elements in the queue off the front and into the
  /// ready list.
  fn move_ready(&mut self) {
    loop {
      match &self.first {
        None => break,
        Some(element) => {
          if element.counter != C::floor() {
            break;
          }
        }
      };

      let content = match self.first.take() {
        None => panic!(),
        Some(node) => {
          self.first = node.next;
          node.contains
        }
      };
      self.ready.push(content);
    }
  }
}

impl<C,T> DelayQueue<C,T> for SimpleDelayQueue<C,T>
where
  C: Sub + SubAssign + Eq + Ord + Copy + Floored
{
  fn insert_at(&mut self, mut position: C, item: T) {

    let mut insert_at = &mut self.first as *mut Option<Box<SimpleDelayQueueElement<C,T>>>;
    loop {
      unsafe {
        match &mut *insert_at  {
          None => {
            // End of the list - we'll stick our element here
            break;
          },
          Some(some_element) => {
            if position < some_element.counter {
              // I fits, so I sits
              //
              // We modify the counter of the element we'll sit in front of
              some_element.counter -= position;
              break;
            } else {
              // I don't fit, decrement the delay and move on to the next one
              position -= some_element.counter;
            }

            insert_at = &mut some_element.next as *mut Option<Box<SimpleDelayQueueElement<C,T>>>;
          }
        }
      };
    }

    // insert_at now points at the Option<> that will point at our element
    unsafe {
      let new_element = Box::new(SimpleDelayQueueElement {
        counter: position,
        contains: item,
        next: core::mem::replace(&mut *insert_at, Option::None)
      });
      (&mut *insert_at).replace(new_element);
    }
  }

  #[optimize(speed)]
  fn decrement(&mut self, mut by: C) {
    // Decrement the head element by our count.  It is possible multiple
    // elements will be released, so keep going round until either there are
    // none left, or the last one remaining still has a while to wait.
    while by > C::floor() {
      match &mut self.first {
        None => break,
        Some(element) => {
          if element.counter > by {
            element.counter -= by;
            by = C::floor(); // I've consumed all the decrement
          } else {
            // I've released (one or more) elements; subtract from the
            // remaining decrement
            by -= element.counter;
            element.counter = C::floor();
          }
        }
      }

      self.move_ready();
    }
  }

  #[optimize(speed)]
  fn consume_next_ready(&mut self) -> Option<T> {
    self.ready.pop()
  }
}


// Tests =====================================================================
#[cfg(test)]
mod tests {
  use std::string::String;
  #[allow(unused_imports)]
  use super::*;

  #[test]
  fn delay_queue_ordered() {
    let mut queue = SimpleDelayQueue::<u16,&str>::new();

    queue.insert_at(1, "First");
    queue.insert_at(16, "Second");
    queue.insert_at(17, "Third");
    queue.insert_at(24, "Fourth");
    queue.insert_at(39, "Fifth");
    queue.insert_at(42, "Sixth");

    assert_eq!(queue.consume_next_ready(), Option::None);
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(1);
    assert_eq!(queue.consume_next_ready(), Option::Some("First"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    for _i in 0..14 {
      queue.decrement(1);
      assert_eq!(queue.consume_next_ready(), Option::None);
    }

    queue.decrement(1);
    assert_eq!(queue.consume_next_ready(), Option::Some("Second"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(1);
    assert_eq!(queue.consume_next_ready(), Option::Some("Third"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    for _i in 0..50 {
      queue.decrement(1);
    }
    // Implementation detail; unconsumed but ready entries will pile up in
    // reverse order
    assert_eq!(queue.consume_next_ready(), Option::Some("Sixth"));
    assert_eq!(queue.consume_next_ready(), Option::Some("Fifth"));
    assert_eq!(queue.consume_next_ready(), Option::Some("Fourth"));
    assert_eq!(queue.consume_next_ready(), Option::None);
  }

  #[test]
  fn delay_queue_out_of_order() {
    let mut queue = SimpleDelayQueue::<u16,&str>::new();

    queue.insert_at(24, "Fourth");
    queue.insert_at(42, "Sixth");
    queue.insert_at(17, "Third");
    queue.insert_at(1, "First");
    queue.insert_at(16, "Second");
    queue.insert_at(39, "Fifth");


    assert_eq!(queue.consume_next_ready(), Option::None);
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(1);
    assert_eq!(queue.consume_next_ready(), Option::Some("First"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    for _i in 0..14 {
      queue.decrement(1);
      assert_eq!(queue.consume_next_ready(), Option::None);
    }

    queue.decrement(1);
    assert_eq!(queue.consume_next_ready(), Option::Some("Second"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(1);
    assert_eq!(queue.consume_next_ready(), Option::Some("Third"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    for _i in 0..50 {
      queue.decrement(1);
    }
    // Implementation detail; unconsumed but ready entries will pile up in
    // reverse order
    assert_eq!(queue.consume_next_ready(), Option::Some("Sixth"));
    assert_eq!(queue.consume_next_ready(), Option::Some("Fifth"));
    assert_eq!(queue.consume_next_ready(), Option::Some("Fourth"));
    assert_eq!(queue.consume_next_ready(), Option::None);
  }

  #[test]
  fn delay_queue_large_decrement() {
    let mut queue = SimpleDelayQueue::<u16,&str>::new();

    queue.insert_at(24, "Fourth");
    queue.insert_at(42, "Sixth");
    queue.insert_at(17, "Third");
    queue.insert_at(1, "First");
    queue.insert_at(16, "Second");
    queue.insert_at(39, "Fifth");

    queue.decrement(17);
    assert_eq!(queue.consume_next_ready(), Option::Some("Third"));
    assert_eq!(queue.consume_next_ready(), Option::Some("Second"));
    assert_eq!(queue.consume_next_ready(), Option::Some("First"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(17);
    assert_eq!(queue.consume_next_ready(), Option::Some("Fourth"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(17);
    assert_eq!(queue.consume_next_ready(), Option::Some("Sixth"));
    assert_eq!(queue.consume_next_ready(), Option::Some("Fifth"));
    assert_eq!(queue.consume_next_ready(), Option::None);

    queue.decrement(17);
    assert_eq!(queue.consume_next_ready(), Option::None);
  }



}