#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};
#[cfg(feature = "u16")]
type Num = u16;
#[cfg(feature = "u32")]
type Num = u32;
#[cfg(feature = "u64")]
type Num = u64;
#[cfg(feature = "usize")]
type Num = usize;
#[derive(Copy, Debug, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Range {
start: Num,
end: Num,
}
impl Range {
pub fn len(&self) -> Num {
self.end - self.start
}
pub fn contains(&self, value: &Num) -> bool {
value >= &self.start && value <= &self.end
}
}
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct IdPool {
free: Vec<Range>,
used: usize,
}
impl IdPool {
pub fn new() -> Self {
Self::new_ranged(1..Num::MAX)
}
pub fn new_ranged(range: std::ops::Range<Num>) -> Self {
let vec = vec![Range {
start: range.start,
end: range.end,
}];
Self { free: vec, used: 0 }
}
pub fn get_used(&self) -> usize {
self.used
}
pub fn request_id(&mut self) -> Option<Num> {
if self.free.len() == 0 {
return None;
}
let range = self.free.last_mut().unwrap();
let id = range.start;
range.start += 1;
if range.len() == 0 {
self.free.pop();
}
self.used += 1;
Some(id)
}
pub fn return_id(&mut self, id: Num) -> Result<(), Num> {
let position = self.free.binary_search_by(|range| {
if range.start.checked_sub(1) == Some(id) || range.end == id {
std::cmp::Ordering::Equal
}
else if range.contains(&id) {
std::cmp::Ordering::Equal
}
else {
id.cmp(&range.start)
}
});
match position {
Err(i) => self.free.insert(
i,
Range {
start: id,
end: id + 1,
},
),
Ok(i) => {
let range = &mut self.free[i];
if range.start.checked_sub(1) == Some(id) {
range.start = id;
}
else if range.end == id {
range.end = range.end + 1;
}
else {
return Err(id);
}
let before_range_idx = match i.checked_sub(1) {
Some(idx) => idx,
None => return Err(id),
};
if self.free[before_range_idx].start == self.free[i].end {
self.free[before_range_idx].start = self.free[i].start;
self.free.remove(i);
}
}
}
self.used -= 1;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn request() {
let mut pool = IdPool::new();
assert_eq!(Some(1), pool.request_id());
assert_eq!(Some(2), pool.request_id());
assert_eq!(Some(3), pool.request_id());
}
#[test]
fn request_return() {
let mut pool = IdPool::new_ranged(1..Num::MAX);
assert_eq!(Some(1), pool.request_id());
assert_eq!(Some(2), pool.request_id());
assert_eq!(Some(3), pool.request_id());
assert_eq!(Ok(()), pool.return_id(1));
assert_eq!(Some(1), pool.request_id());
assert_eq!(Ok(()), pool.return_id(2));
assert_eq!(Some(2), pool.request_id());
assert_eq!(Some(4), pool.request_id());
assert_eq!(Ok(()), pool.return_id(3));
assert_eq!(Ok(()), pool.return_id(4));
assert_eq!(Err(5), pool.return_id(5));
}
#[test]
fn used_count() {
let mut pool = IdPool::new_ranged(1..10);
assert_eq!(Some(1), pool.request_id());
assert_eq!(Some(2), pool.request_id());
assert_eq!(Some(3), pool.request_id());
assert_eq!(Ok(()), pool.return_id(1));
assert_eq!(2, pool.get_used());
}
}