pub type Id = usize;
pub const EPHEMERAL_ID: Id = 0;
#[derive(Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serde-1", derive(serde::Serialize, serde::Deserialize))]
pub struct IdAllocator {
next_id: Option<Id>,
freed: Vec<Id>,
}
impl IdAllocator {
#[inline]
pub fn new() -> Self {
Self::default()
}
#[inline]
pub fn set_next_id(&mut self, id: Id) {
self.next_id = Some(id);
}
#[inline]
pub fn mark_external_id(&mut self, id: Id) {
if let Some(nid) = self.next_id {
let is_less = nid <= id;
if is_less && id == Id::MAX {
self.next_id = None;
} else if is_less {
self.next_id = Some(id + 1);
}
}
}
#[inline]
pub fn has_next(&self) -> bool {
self.next_id.is_some() || !self.freed.is_empty()
}
#[inline]
pub fn freed(&self) -> &[Id] {
&self.freed
}
}
impl Default for IdAllocator {
fn default() -> Self {
Self {
next_id: Some(EPHEMERAL_ID + 1),
freed: Vec::new(),
}
}
}
impl Iterator for IdAllocator {
type Item = Id;
fn next(&mut self) -> Option<Self::Item> {
if let Some(id) = self.freed.pop() {
Some(id)
} else if let Some(id) = self.next_id {
if id == Id::MAX {
self.next_id = None;
} else {
self.next_id = Some(id + 1);
}
Some(id)
} else {
None
}
}
}
impl Extend<Id> for IdAllocator {
fn extend<I: IntoIterator<Item = Id>>(&mut self, iter: I) {
self.freed.extend(iter);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn next_should_return_next_id_if_no_freed_available_and_not_reached_limit() {
let mut id_alloc = IdAllocator::new();
assert_eq!(id_alloc.next(), Some(1));
assert_eq!(id_alloc.next(), Some(2));
assert_eq!(id_alloc.next(), Some(3));
}
#[test]
fn next_should_return_freed_id_if_available() {
let mut id_alloc = IdAllocator::new();
id_alloc.extend(vec![9, 8, 7]);
assert_eq!(id_alloc.next(), Some(7));
assert_eq!(id_alloc.next(), Some(8));
assert_eq!(id_alloc.next(), Some(9));
assert_eq!(id_alloc.next(), Some(1));
assert_eq!(id_alloc.next(), Some(2));
assert_eq!(id_alloc.next(), Some(3));
}
#[test]
fn next_should_return_none_if_no_freed_and_reached_limit() {
let mut id_alloc = IdAllocator::new();
id_alloc.set_next_id(Id::MAX);
assert_eq!(id_alloc.next(), Some(Id::MAX));
assert_eq!(id_alloc.next(), None);
}
#[test]
fn extend_should_append_ids_to_freed_list() {
let mut id_alloc = IdAllocator::new();
id_alloc.extend(vec![9, 8, 7]);
id_alloc.extend(vec![6, 5, 4]);
assert_eq!(id_alloc.freed(), &[9, 8, 7, 6, 5, 4]);
}
#[test]
fn mark_external_id_should_move_next_id_beyond_provided_id_if_less_than_id() {
let mut id_alloc = IdAllocator::new();
id_alloc.set_next_id(3);
id_alloc.mark_external_id(999);
assert_eq!(id_alloc.next(), Some(1000));
}
#[test]
fn mark_external_id_should_move_next_id_beyond_provided_id_if_equal_to_id() {
let mut id_alloc = IdAllocator::new();
id_alloc.set_next_id(999);
id_alloc.mark_external_id(999);
assert_eq!(id_alloc.next(), Some(1000));
}
#[test]
fn mark_external_id_should_not_move_next_id_if_given_id_is_less_than_it() {
let mut id_alloc = IdAllocator::new();
id_alloc.set_next_id(1000);
id_alloc.mark_external_id(1);
assert_eq!(id_alloc.next(), Some(1000));
}
#[test]
fn mark_external_id_should_not_move_next_id_if_next_id_is_already_none() {
let mut id_alloc = IdAllocator::new();
id_alloc.next_id = None;
id_alloc.mark_external_id(1);
assert_eq!(id_alloc.next(), None);
}
}