use std::mem;
use std::slice;
use std::iter::{Enumerate, FilterMap};
use std::ops::{Index, IndexMut};
use std::vec::Vec;
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub enum PoolEntry<T> {
FreeListEnd,
FreeListPtr {
next_free: usize,
},
Occupied(T)
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Pool<T> {
len: usize,
free_list: Option<usize>,
entries: Vec<PoolEntry<T>>,
}
impl<T> Pool<T> {
pub fn new() -> Self {
Pool {
len: 0,
free_list: None,
entries: Vec::new(),
}
}
pub fn with_capacity(cap: usize) -> Self {
Pool {
len: 0,
free_list: None,
entries: Vec::with_capacity(cap),
}
}
pub fn empty(&self) -> bool {
self.len == 0
}
pub fn len(&self) -> usize {
self.len
}
pub fn clear(&mut self) {
self.len = 0;
self.free_list = None;
self.entries.clear();
}
pub fn push(&mut self, item: T) -> usize {
self.len += 1;
if let Some(free_item) = self.free_list {
self.free_list = match self.entries[free_item] {
PoolEntry::FreeListEnd => None,
PoolEntry::FreeListPtr{ next_free } => Some(next_free),
_ => unreachable!(),
};
self.entries[free_item] = PoolEntry::Occupied(item);
free_item
} else {
let i = self.entries.len();
self.entries.push(PoolEntry::Occupied(item));
i
}
}
pub fn remove(&mut self, i: usize) -> T {
let new_entry = if let Some(free_item) = self.free_list {
PoolEntry::FreeListPtr{ next_free: free_item }
} else {
PoolEntry::FreeListEnd
};
self.free_list = Some(i);
if let PoolEntry::Occupied(item) = mem::replace(&mut self.entries[i], new_entry) {
self.len -= 1;
item
} else {
panic!("index {} is not occupied", i);
}
}
pub fn next_free(&self) -> Option<usize> {
if let Some(free) = self.free_list {
Some(free)
} else {
None
}
}
pub fn iter<'a>(&'a self) -> impl Iterator<Item=(usize, &'a T)> {
self.into_iter()
}
pub fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item=(usize, &'a mut T)> {
self.into_iter()
}
pub fn get<'a>(&'a self, i: usize) -> Option<&'a T> {
if let Some(PoolEntry::Occupied(ref item)) = self.entries.get(i) {
Some(&item)
} else {
None
}
}
pub fn get_mut<'a>(&'a mut self, i: usize) -> Option<&'a mut T> {
if let Some(PoolEntry::Occupied(ref mut item)) = self.entries.get_mut(i) {
Some(item)
} else {
None
}
}
}
impl<T> Index<usize> for Pool<T> {
type Output = T;
fn index(&self, i: usize) -> &T {
if let PoolEntry::Occupied(ref item) = self.entries[i] {
item
} else {
panic!("index {} is not occupied", i)
}
}
}
impl<T> IndexMut<usize> for Pool<T> {
fn index_mut(&mut self, i: usize) -> &mut T {
if let PoolEntry::Occupied(ref mut item) = self.entries[i] {
item
} else {
panic!("index {} is not occupied", i)
}
}
}
impl<T> Clone for PoolEntry<T>
where
T: Clone
{
fn clone(&self) -> Self {
use self::PoolEntry::*;
match self {
&FreeListEnd => FreeListEnd,
&FreeListPtr{ next_free } => FreeListPtr{ next_free },
&Occupied(ref item) => Occupied(item.clone()),
}
}
}
impl<T> Clone for Pool<T>
where
T: Clone
{
fn clone(&self) -> Self {
Pool {
len: self.len,
free_list: self.free_list,
entries: self.entries.clone(),
}
}
}
impl<L, T> From<L> for Pool<T>
where
L: IntoIterator<Item = T>
{
fn from(iter: L) -> Pool<T> {
let mut pool = Pool::new();
for item in iter.into_iter() {
pool.push(item);
}
pool
}
}
fn filter_pool<'a, T>((i, item): (usize, &'a PoolEntry<T>)) -> Option<(usize, &'a T)> {
if let &PoolEntry::Occupied(ref item) = item {
Some((i, item))
} else {
None
}
}
impl<'a, T> IntoIterator for &'a Pool<T> {
type Item = (usize, &'a T);
type IntoIter = FilterMap<Enumerate<slice::Iter<'a, PoolEntry<T>>>, fn((usize, &PoolEntry<T>)) -> Option<(usize, &T)>>;
fn into_iter(self) -> Self::IntoIter {
self.entries.iter().enumerate().filter_map(filter_pool)
}
}
fn filter_pool_mut<'a, T>((i, item): (usize, &'a mut PoolEntry<T>)) -> Option<(usize, &'a mut T)> {
if let &mut PoolEntry::Occupied(ref mut item) = item {
Some((i, item))
} else {
None
}
}
impl<'a, T> IntoIterator for &'a mut Pool<T> {
type Item = (usize, &'a mut T);
type IntoIter = FilterMap<Enumerate<slice::IterMut<'a, PoolEntry<T>>>, fn((usize, &mut PoolEntry<T>)) -> Option<(usize, &mut T)>>;
fn into_iter(self) -> Self::IntoIter {
self.entries.iter_mut().enumerate().filter_map(filter_pool_mut)
}
}
#[cfg(test)]
mod tests {
mod pool {
use pool::*;
#[test]
fn test_manual_code() {
let mut pool: Pool<usize> = Pool::new();
let id0 = pool.push(0);
let id1 = pool.push(1);
let id2 = pool.push(2);
let id3 = pool.push(3);
assert_eq!(id0, 0);
assert_eq!(id3, 3);
pool.remove(id1);
pool.remove(id2);
assert_eq!(pool[id0], 0);
assert_eq!(pool[id3], 3);
assert_eq!(pool.iter().map(|(_i, &u)|{u}).collect::<Vec<usize>>(), vec![0, 3]);
}
#[test]
fn test_pool() {
{
let mut pool: Pool<usize> = Pool::new();
for i in 0..8 {
pool.push(i);
}
let ids = [ 0, 1, 2, 3, 4, 5, 6, 7 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
for i in 0..4 {
pool.remove(i * 2);
}
let ids = [ 1, 3, 5, 7 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
{
let _removed = pool.remove(1);
let ids = [ 3, 5, 7 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
}
}
{
let mut pool: Pool<usize> = Pool::new();
for i in 0..16 {
pool.push(i);
}
let ids = [ 0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
for i in 0..8 {
pool.remove(i * 2);
}
let ids = [ 1, 3, 5, 7, 9, 11, 13, 15 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
{
let _removed = pool.remove(1);
let ids = [ 3, 5, 7, 9, 11, 13, 15 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
}
}
{
let mut pool: Pool<usize> = Pool::new();
for i in 0..16 {
pool.push(i);
}
let ids = [ 0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
for i in 0..8 {
pool.remove(i);
}
let ids = [ 8, 9, 10, 11, 12, 13, 14, 15 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
{
let _removed = pool.remove(8);
let ids = [ 9, 10, 11, 12, 13, 14, 15 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
}
}
{
let mut pool: Pool<usize> = Pool::new();
for i in 0..24 {
pool.push(i);
}
let ids = [ 0, 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
for i in 8..16 {
pool.remove(i);
}
let ids = [ 0, 1, 2, 3, 4, 5, 6, 7,
16, 17, 18, 19, 20, 21, 22, 23 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
{
let _removed1 = pool.remove(23);
let _removed2 = pool.remove(18);
let _removed2 = pool.remove(19);
let ids = [ 0, 1, 2, 3, 4, 5, 6, 7,
16, 17, 20, 21, 22 ];
for (i, item) in pool.iter().enumerate() {
assert_eq!(*item.1, ids[i]);
}
}
}
}
}
}