salrucc 0.13.0

use std::cmp::Eq;
use std::cmp::Ord;
use std::cmp::Reverse;
use std::hash::Hash;

use priority_queue::PriorityQueue;

/// Implements the "twin queues" - the access queue and expiry queue so that updates can be done as a unit
pub struct CacheQueues<K: Clone + Hash + Eq, AT: Ord> {
	access: PriorityQueue<K, u64>,
	expiry: PriorityQueue<K, Reverse<AT>>,
	lowest_access: u64,
}

pub enum ExpiryOption<AT> {
	Ignore,
	Never,
	Expires(AT),
}

impl<K: Clone + Hash + Eq, AT: Ord> CacheQueues<K, AT> {
	pub fn new() -> CacheQueues<K, AT> {
		CacheQueues {
			access: PriorityQueue::new(),
			expiry: PriorityQueue::new(),
			lowest_access: u64::MAX,
		}
	}

	#[cfg(test)]
	pub fn is_empty(&self) -> bool {
		self.access.is_empty() && self.expiry.is_empty()
	}

	pub fn exists(&self, key: &K) -> bool {
		self.access.get(key).is_some()
	}

	pub fn push(&mut self, key: K, absolute_expiry: ExpiryOption<AT>) {
		// If we have an expiry, we need to add to that queue
		match absolute_expiry {
			ExpiryOption::Ignore => {}
			ExpiryOption::Never => {
				self.expiry.remove(&key);
			}
			ExpiryOption::Expires(absolute_expiry_value) => {
				self.expiry
					.push(key.clone(), Reverse(absolute_expiry_value));
			}
		}

		// Add this to the access queue
		self.access.push(key, self.lowest_access);

		// And decrement the access counter
		self.lowest_access = self.lowest_access - 1;
	}

	/// Pop the least recently used item, giving the caller an opportunity to lock
	pub fn pop_least_recently_used<PK>(
		&mut self,
		try_post_process_callback: impl Fn(&K) -> Option<PK>,
	) -> Option<PK> {
		// Peek in the access queue
		let (key, _) = self.access.peek()?;

		// Attempt to post process the item with try_post_process_callback; if this fails return
		// leaving the queue unchanged
		let result = try_post_process_callback(&key)?;

		// Now pop it for real (and remove from the expiry queue as well)
		let (key, _) = self
			.access
			.pop()
			.expect("This pop() should never fail in practice");
		self.expiry.remove(&key);

		// And we're done!
		Some(result)
	}

	/// Pop an expired item off of the queue
	pub fn pop_expired<PK>(
		&mut self,
		current_time: &AT,
		try_post_process_callback: impl Fn(&K) -> Option<PK>,
	) -> Option<PK> {
		// Get the expiry of the top of the queue, or bail if it is empty
		let (key, expiry) = self.expiry.peek()?;
		let expiry = &expiry.0;

		// Bail if this has not yet expired
		if expiry > current_time {
			return None;
		}

		// Attempt to post process the item with try_post_process_callback; if this fails return
		// leaving the queue unchanged
		let result = try_post_process_callback(&key)?;

		// The top has indeed expired and we have a lock - now pop it for real (and remove from
		// the access queue as well)
		let (key, _) = self
			.expiry
			.pop()
			.expect("This pop() should never fail in practice");
		self.access.remove(&key);

		// And we're done!
		Some(result)
	}
}

#[cfg(test)]
mod tests {
	use super::CacheQueues;
	use super::ExpiryOption::Expires;
	use super::ExpiryOption::Ignore;
	use super::ExpiryOption::Never;

	#[test]
	fn general() {
		let mut queues = CacheQueues::new();
		queues.push(101, Never);
		queues.push(102, Expires(15));
		queues.push(103, Expires(16));
		queues.push(104, Expires(17));
		queues.push(105, Never);
		queues.push(102, Ignore);
		queues.push(104, Ignore);

		let cb = |x: &i32| Some(*x);
		assert_eq!(queues.pop_least_recently_used(cb), Some(101));
		assert_eq!(queues.pop_least_recently_used(cb), Some(103));
		assert_eq!(queues.pop_expired(&12, cb), None);
		assert_eq!(queues.pop_expired(&14, cb), None);
		assert_eq!(queues.pop_expired(&15, cb), Some(102));
		assert_eq!(queues.pop_expired(&16, cb), None);
		assert_eq!(queues.pop_least_recently_used(cb), Some(105));
		assert_eq!(queues.pop_least_recently_used(cb), Some(104));
		assert_eq!(queues.pop_least_recently_used(cb), None);
	}
}