lib/arena/src/lib.rs

   1 //! Yet another index-based arena.
   2
   3 #![warn(missing_docs)]
   4
   5 use std::{
   6     fmt,
   7     hash::{Hash, Hasher},
   8     iter::FromIterator,
   9     marker::PhantomData,
  10     ops::{Index, IndexMut},
  11 };
  12
  13 mod map;
  14 pub use map::ArenaMap;
  15
  16 /// The raw index of a value in an arena.
  17 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
  18 pub struct RawIdx(u32);
  19
  20 impl From<RawIdx> for u32 {
  21     fn from(raw: RawIdx) -> u32 {
  22         raw.0
  23     }
  24 }
  25
  26 impl From<u32> for RawIdx {
  27     fn from(idx: u32) -> RawIdx {
  28         RawIdx(idx)
  29     }
  30 }
  31
  32 impl fmt::Debug for RawIdx {
  33     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  34         self.0.fmt(f)
  35     }
  36 }
  37
  38 impl fmt::Display for RawIdx {
  39     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  40         self.0.fmt(f)
  41     }
  42 }
  43
  44 /// The index of a value allocated in an arena that holds `T`s.
  45 pub struct Idx<T> {
  46     raw: RawIdx,
  47     _ty: PhantomData<fn() -> T>,
  48 }
  49
  50 impl<T> Clone for Idx<T> {
  51     fn clone(&self) -> Self {
  52         *self
  53     }
  54 }
  55 impl<T> Copy for Idx<T> {}
  56
  57 impl<T> PartialEq for Idx<T> {
  58     fn eq(&self, other: &Idx<T>) -> bool {
  59         self.raw == other.raw
  60     }
  61 }
  62 impl<T> Eq for Idx<T> {}
  63
  64 impl<T> Hash for Idx<T> {
  65     fn hash<H: Hasher>(&self, state: &mut H) {
  66         self.raw.hash(state)
  67     }
  68 }
  69
  70 impl<T> fmt::Debug for Idx<T> {
  71     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  72         let mut type_name = std::any::type_name::<T>();
  73         if let Some(idx) = type_name.rfind(':') {
  74             type_name = &type_name[idx + 1..]
  75         }
  76         write!(f, "Idx::<{}>({})", type_name, self.raw)
  77     }
  78 }
  79
  80 impl<T> Idx<T> {
  81     /// Creates a new index from a [`RawIdx`].
  82     pub fn from_raw(raw: RawIdx) -> Self {
  83         Idx { raw, _ty: PhantomData }
  84     }
  85
  86     /// Converts this index into the underlying [`RawIdx`].
  87     pub fn into_raw(self) -> RawIdx {
  88         self.raw
  89     }
  90 }
  91
  92 /// Yet another index-based arena.
  93 #[derive(Clone, PartialEq, Eq, Hash)]
  94 pub struct Arena<T> {
  95     data: Vec<T>,
  96 }
  97
  98 impl<T: fmt::Debug> fmt::Debug for Arena<T> {
  99     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
 100         fmt.debug_struct("Arena").field("len", &self.len()).field("data", &self.data).finish()
 101     }
 102 }
 103
 104 impl<T> Arena<T> {
 105     /// Creates a new empty arena.
 106     ///
 107     /// ```
 108     /// let arena: la_arena::Arena<i32> = la_arena::Arena::new();
 109     /// assert!(arena.is_empty());
 110     /// ```
 111     pub const fn new() -> Arena<T> {
 112         Arena { data: Vec::new() }
 113     }
 114
 115     /// Empties the arena, removing all contained values.
 116     ///
 117     /// ```
 118     /// let mut arena = la_arena::Arena::new();
 119     ///
 120     /// arena.alloc(1);
 121     /// arena.alloc(2);
 122     /// arena.alloc(3);
 123     /// assert_eq!(arena.len(), 3);
 124     ///
 125     /// arena.clear();
 126     /// assert!(arena.is_empty());
 127     /// ```
 128     pub fn clear(&mut self) {
 129         self.data.clear();
 130     }
 131
 132     /// Returns the length of the arena.
 133     ///
 134     /// ```
 135     /// let mut arena = la_arena::Arena::new();
 136     /// assert_eq!(arena.len(), 0);
 137     ///
 138     /// arena.alloc("foo");
 139     /// assert_eq!(arena.len(), 1);
 140     ///
 141     /// arena.alloc("bar");
 142     /// assert_eq!(arena.len(), 2);
 143     ///
 144     /// arena.alloc("baz");
 145     /// assert_eq!(arena.len(), 3);
 146     /// ```
 147     pub fn len(&self) -> usize {
 148         self.data.len()
 149     }
 150
 151     /// Returns whether the arena contains no elements.
 152     ///
 153     /// ```
 154     /// let mut arena = la_arena::Arena::new();
 155     /// assert!(arena.is_empty());
 156     ///
 157     /// arena.alloc(0.5);
 158     /// assert!(!arena.is_empty());
 159     /// ```
 160     pub fn is_empty(&self) -> bool {
 161         self.data.is_empty()
 162     }
 163
 164     /// Allocates a new value on the arena, returning the value’s index.
 165     ///
 166     /// ```
 167     /// let mut arena = la_arena::Arena::new();
 168     /// let idx = arena.alloc(50);
 169     ///
 170     /// assert_eq!(arena[idx], 50);
 171     /// ```
 172     pub fn alloc(&mut self, value: T) -> Idx<T> {
 173         let idx = RawIdx(self.data.len() as u32);
 174         self.data.push(value);
 175         Idx::from_raw(idx)
 176     }
 177
 178     /// Returns an iterator over the arena’s elements.
 179     ///
 180     /// ```
 181     /// let mut arena = la_arena::Arena::new();
 182     /// let idx1 = arena.alloc(20);
 183     /// let idx2 = arena.alloc(40);
 184     /// let idx3 = arena.alloc(60);
 185     ///
 186     /// let mut iterator = arena.iter();
 187     /// assert_eq!(iterator.next(), Some((idx1, &20)));
 188     /// assert_eq!(iterator.next(), Some((idx2, &40)));
 189     /// assert_eq!(iterator.next(), Some((idx3, &60)));
 190     /// ```
 191     pub fn iter(
 192         &self,
 193     ) -> impl Iterator<Item = (Idx<T>, &T)> + ExactSizeIterator + DoubleEndedIterator {
 194         self.data.iter().enumerate().map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
 195     }
 196
 197     /// Returns an iterator over the arena’s mutable elements.
 198     ///
 199     /// ```
 200     /// let mut arena = la_arena::Arena::new();
 201     /// let idx1 = arena.alloc(20);
 202     ///
 203     /// assert_eq!(arena[idx1], 20);
 204     ///
 205     /// let mut iterator = arena.iter_mut();
 206     /// *iterator.next().unwrap().1 = 10;
 207     /// drop(iterator);
 208     ///
 209     /// assert_eq!(arena[idx1], 10);
 210     /// ```
 211     pub fn iter_mut(
 212         &mut self,
 213     ) -> impl Iterator<Item = (Idx<T>, &mut T)> + ExactSizeIterator + DoubleEndedIterator {
 214         self.data
 215             .iter_mut()
 216             .enumerate()
 217             .map(|(idx, value)| (Idx::from_raw(RawIdx(idx as u32)), value))
 218     }
 219
 220     /// Reallocates the arena to make it take up as little space as possible.
 221     pub fn shrink_to_fit(&mut self) {
 222         self.data.shrink_to_fit();
 223     }
 224 }
 225
 226 impl<T> Default for Arena<T> {
 227     fn default() -> Arena<T> {
 228         Arena { data: Vec::new() }
 229     }
 230 }
 231
 232 impl<T> Index<Idx<T>> for Arena<T> {
 233     type Output = T;
 234     fn index(&self, idx: Idx<T>) -> &T {
 235         let idx = idx.into_raw().0 as usize;
 236         &self.data[idx]
 237     }
 238 }
 239
 240 impl<T> IndexMut<Idx<T>> for Arena<T> {
 241     fn index_mut(&mut self, idx: Idx<T>) -> &mut T {
 242         let idx = idx.into_raw().0 as usize;
 243         &mut self.data[idx]
 244     }
 245 }
 246
 247 impl<T> FromIterator<T> for Arena<T> {
 248     fn from_iter<I>(iter: I) -> Self
 249     where
 250         I: IntoIterator<Item = T>,
 251     {
 252         Arena { data: Vec::from_iter(iter) }
 253     }
 254 }