From 754a48b7ff6d8c58b1ee08651e60112900b60455 Mon Sep 17 00:00:00 2001 From: Sébastien Crozet Date: Tue, 25 Aug 2020 22:10:25 +0200 Subject: First public release of Rapier. --- src/data/arena.rs | 1159 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/data/graph.rs | 830 ++++++++++++++++++++++++++++++++++++++ src/data/mod.rs | 4 + 3 files changed, 1993 insertions(+) create mode 100644 src/data/arena.rs create mode 100644 src/data/graph.rs create mode 100644 src/data/mod.rs (limited to 'src/data') diff --git a/src/data/arena.rs b/src/data/arena.rs new file mode 100644 index 0000000..fcec017 --- /dev/null +++ b/src/data/arena.rs @@ -0,0 +1,1159 @@ +//! Arena adapted from the generational-arena crate. +//! +//! See https://github.com/fitzgen/generational-arena/blob/master/src/lib.rs. +//! This has been modified to have a fully deterministic deserialization (including for the order of +//! Index attribution after a deserialization of the arena. +use std::cmp; +use std::iter::{self, Extend, FromIterator, FusedIterator}; +use std::mem; +use std::ops; +use std::slice; +use std::vec; + +/// The `Arena` allows inserting and removing elements that are referred to by +/// `Index`. +/// +/// [See the module-level documentation for example usage and motivation.](./index.html) +#[derive(Clone, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Arena { + items: Vec>, + generation: u64, + free_list_head: Option, + len: usize, +} + +#[derive(Clone, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +enum Entry { + Free { next_free: Option }, + Occupied { generation: u64, value: T }, +} + +/// An index (and generation) into an `Arena`. +/// +/// To get an `Index`, insert an element into an `Arena`, and the `Index` for +/// that element will be returned. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// let idx = arena.insert(123); +/// assert_eq!(arena[idx], 123); +/// ``` +#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Index { + index: usize, + generation: u64, +} + +impl Index { + /// Create a new `Index` from its raw parts. + /// + /// The parts must have been returned from an earlier call to + /// `into_raw_parts`. + /// + /// Providing arbitrary values will lead to malformed indices and ultimately + /// panics. + pub fn from_raw_parts(a: usize, b: u64) -> Index { + Index { + index: a, + generation: b, + } + } + + /// Convert this `Index` into its raw parts. + /// + /// This niche method is useful for converting an `Index` into another + /// identifier type. Usually, you should prefer a newtype wrapper around + /// `Index` like `pub struct MyIdentifier(Index);`. However, for external + /// types whose definition you can't customize, but which you can construct + /// instances of, this method can be useful. + pub fn into_raw_parts(self) -> (usize, u64) { + (self.index, self.generation) + } +} + +const DEFAULT_CAPACITY: usize = 4; + +impl Default for Arena { + fn default() -> Arena { + Arena::new() + } +} + +impl Arena { + /// Constructs a new, empty `Arena`. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::::new(); + /// # let _ = arena; + /// ``` + pub fn new() -> Arena { + Arena::with_capacity(DEFAULT_CAPACITY) + } + + /// Constructs a new, empty `Arena` with the specified capacity. + /// + /// The `Arena` will be able to hold `n` elements without further allocation. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(10); + /// + /// // These insertions will not require further allocation. + /// for i in 0..10 { + /// assert!(arena.try_insert(i).is_ok()); + /// } + /// + /// // But now we are at capacity, and there is no more room. + /// assert!(arena.try_insert(99).is_err()); + /// ``` + pub fn with_capacity(n: usize) -> Arena { + let n = cmp::max(n, 1); + let mut arena = Arena { + items: Vec::new(), + generation: 0, + free_list_head: None, + len: 0, + }; + arena.reserve(n); + arena + } + + /// Clear all the items inside the arena, but keep its allocation. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(1); + /// arena.insert(42); + /// arena.insert(43); + /// + /// arena.clear(); + /// + /// assert_eq!(arena.capacity(), 2); + /// ``` + pub fn clear(&mut self) { + self.items.clear(); + + let end = self.items.capacity(); + self.items.extend((0..end).map(|i| { + if i == end - 1 { + Entry::Free { next_free: None } + } else { + Entry::Free { + next_free: Some(i + 1), + } + } + })); + self.free_list_head = Some(0); + self.len = 0; + } + + /// Attempts to insert `value` into the arena using existing capacity. + /// + /// This method will never allocate new capacity in the arena. + /// + /// If insertion succeeds, then the `value`'s index is returned. If + /// insertion fails, then `Err(value)` is returned to give ownership of + /// `value` back to the caller. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// + /// match arena.try_insert(42) { + /// Ok(idx) => { + /// // Insertion succeeded. + /// assert_eq!(arena[idx], 42); + /// } + /// Err(x) => { + /// // Insertion failed. + /// assert_eq!(x, 42); + /// } + /// }; + /// ``` + #[inline] + pub fn try_insert(&mut self, value: T) -> Result { + match self.try_alloc_next_index() { + None => Err(value), + Some(index) => { + self.items[index.index] = Entry::Occupied { + generation: self.generation, + value, + }; + Ok(index) + } + } + } + + /// Attempts to insert the value returned by `create` into the arena using existing capacity. + /// `create` is called with the new value's associated index, allowing values that know their own index. + /// + /// This method will never allocate new capacity in the arena. + /// + /// If insertion succeeds, then the new index is returned. If + /// insertion fails, then `Err(create)` is returned to give ownership of + /// `create` back to the caller. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::{Arena, Index}; + /// + /// let mut arena = Arena::new(); + /// + /// match arena.try_insert_with(|idx| (42, idx)) { + /// Ok(idx) => { + /// // Insertion succeeded. + /// assert_eq!(arena[idx].0, 42); + /// assert_eq!(arena[idx].1, idx); + /// } + /// Err(x) => { + /// // Insertion failed. + /// } + /// }; + /// ``` + #[inline] + pub fn try_insert_with T>(&mut self, create: F) -> Result { + match self.try_alloc_next_index() { + None => Err(create), + Some(index) => { + self.items[index.index] = Entry::Occupied { + generation: self.generation, + value: create(index), + }; + Ok(index) + } + } + } + + #[inline] + fn try_alloc_next_index(&mut self) -> Option { + match self.free_list_head { + None => None, + Some(i) => match self.items[i] { + Entry::Occupied { .. } => panic!("corrupt free list"), + Entry::Free { next_free } => { + self.free_list_head = next_free; + self.len += 1; + Some(Index { + index: i, + generation: self.generation, + }) + } + }, + } + } + + /// Insert `value` into the arena, allocating more capacity if necessary. + /// + /// The `value`'s associated index in the arena is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// + /// let idx = arena.insert(42); + /// assert_eq!(arena[idx], 42); + /// ``` + #[inline] + pub fn insert(&mut self, value: T) -> Index { + match self.try_insert(value) { + Ok(i) => i, + Err(value) => self.insert_slow_path(value), + } + } + + /// Insert the value returned by `create` into the arena, allocating more capacity if necessary. + /// `create` is called with the new value's associated index, allowing values that know their own index. + /// + /// The new value's associated index in the arena is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::{Arena, Index}; + /// + /// let mut arena = Arena::new(); + /// + /// let idx = arena.insert_with(|idx| (42, idx)); + /// assert_eq!(arena[idx].0, 42); + /// assert_eq!(arena[idx].1, idx); + /// ``` + #[inline] + pub fn insert_with(&mut self, create: impl FnOnce(Index) -> T) -> Index { + match self.try_insert_with(create) { + Ok(i) => i, + Err(create) => self.insert_with_slow_path(create), + } + } + + #[inline(never)] + fn insert_slow_path(&mut self, value: T) -> Index { + let len = self.items.len(); + self.reserve(len); + self.try_insert(value) + .map_err(|_| ()) + .expect("inserting will always succeed after reserving additional space") + } + + #[inline(never)] + fn insert_with_slow_path(&mut self, create: impl FnOnce(Index) -> T) -> Index { + let len = self.items.len(); + self.reserve(len); + self.try_insert_with(create) + .map_err(|_| ()) + .expect("inserting will always succeed after reserving additional space") + } + + /// Remove the element at index `i` from the arena. + /// + /// If the element at index `i` is still in the arena, then it is + /// returned. If it is not in the arena, then `None` is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// assert_eq!(arena.remove(idx), Some(42)); + /// assert_eq!(arena.remove(idx), None); + /// ``` + pub fn remove(&mut self, i: Index) -> Option { + if i.index >= self.items.len() { + return None; + } + + match self.items[i.index] { + Entry::Occupied { generation, .. } if i.generation == generation => { + let entry = mem::replace( + &mut self.items[i.index], + Entry::Free { + next_free: self.free_list_head, + }, + ); + self.generation += 1; + self.free_list_head = Some(i.index); + self.len -= 1; + + match entry { + Entry::Occupied { + generation: _, + value, + } => Some(value), + _ => unreachable!(), + } + } + _ => None, + } + } + + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all indices such that `predicate(index, &value)` returns `false`. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut crew = Arena::new(); + /// crew.extend(&["Jim Hawkins", "John Silver", "Alexander Smollett", "Israel Hands"]); + /// let pirates = ["John Silver", "Israel Hands"]; // too dangerous to keep them around + /// crew.retain(|_index, member| !pirates.contains(member)); + /// let mut crew_members = crew.iter().map(|(_, member)| **member); + /// assert_eq!(crew_members.next(), Some("Jim Hawkins")); + /// assert_eq!(crew_members.next(), Some("Alexander Smollett")); + /// assert!(crew_members.next().is_none()); + /// ``` + pub fn retain(&mut self, mut predicate: impl FnMut(Index, &mut T) -> bool) { + for i in 0..self.capacity() { + let remove = match &mut self.items[i] { + Entry::Occupied { generation, value } => { + let index = Index { + index: i, + generation: *generation, + }; + if predicate(index, value) { + None + } else { + Some(index) + } + } + + _ => None, + }; + if let Some(index) = remove { + self.remove(index); + } + } + } + + /// Is the element at index `i` in the arena? + /// + /// Returns `true` if the element at `i` is in the arena, `false` otherwise. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// assert!(arena.contains(idx)); + /// arena.remove(idx); + /// assert!(!arena.contains(idx)); + /// ``` + pub fn contains(&self, i: Index) -> bool { + self.get(i).is_some() + } + + /// Get a shared reference to the element at index `i` if it is in the + /// arena. + /// + /// If the element at index `i` is not in the arena, then `None` is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// assert_eq!(arena.get(idx), Some(&42)); + /// arena.remove(idx); + /// assert!(arena.get(idx).is_none()); + /// ``` + pub fn get(&self, i: Index) -> Option<&T> { + match self.items.get(i.index) { + Some(Entry::Occupied { generation, value }) if *generation == i.generation => { + Some(value) + } + _ => None, + } + } + + /// Get an exclusive reference to the element at index `i` if it is in the + /// arena. + /// + /// If the element at index `i` is not in the arena, then `None` is returned. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx = arena.insert(42); + /// + /// *arena.get_mut(idx).unwrap() += 1; + /// assert_eq!(arena.remove(idx), Some(43)); + /// assert!(arena.get_mut(idx).is_none()); + /// ``` + pub fn get_mut(&mut self, i: Index) -> Option<&mut T> { + match self.items.get_mut(i.index) { + Some(Entry::Occupied { generation, value }) if *generation == i.generation => { + Some(value) + } + _ => None, + } + } + + /// Get a pair of exclusive references to the elements at index `i1` and `i2` if it is in the + /// arena. + /// + /// If the element at index `i1` or `i2` is not in the arena, then `None` is returned for this + /// element. + /// + /// # Panics + /// + /// Panics if `i1` and `i2` are pointing to the same item of the arena. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx1 = arena.insert(0); + /// let idx2 = arena.insert(1); + /// + /// { + /// let (item1, item2) = arena.get2_mut(idx1, idx2); + /// + /// *item1.unwrap() = 3; + /// *item2.unwrap() = 4; + /// } + /// + /// assert_eq!(arena[idx1], 3); + /// assert_eq!(arena[idx2], 4); + /// ``` + pub fn get2_mut(&mut self, i1: Index, i2: Index) -> (Option<&mut T>, Option<&mut T>) { + let len = self.items.len(); + + if i1.index == i2.index { + assert!(i1.generation != i2.generation); + + if i1.generation > i2.generation { + return (self.get_mut(i1), None); + } + return (None, self.get_mut(i2)); + } + + if i1.index >= len { + return (None, self.get_mut(i2)); + } else if i2.index >= len { + return (self.get_mut(i1), None); + } + + let (raw_item1, raw_item2) = { + let (xs, ys) = self.items.split_at_mut(cmp::max(i1.index, i2.index)); + if i1.index < i2.index { + (&mut xs[i1.index], &mut ys[0]) + } else { + (&mut ys[0], &mut xs[i2.index]) + } + }; + + let item1 = match raw_item1 { + Entry::Occupied { generation, value } if *generation == i1.generation => Some(value), + _ => None, + }; + + let item2 = match raw_item2 { + Entry::Occupied { generation, value } if *generation == i2.generation => Some(value), + _ => None, + }; + + (item1, item2) + } + + /// Get the length of this arena. + /// + /// The length is the number of elements the arena holds. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// assert_eq!(arena.len(), 0); + /// + /// let idx = arena.insert(42); + /// assert_eq!(arena.len(), 1); + /// + /// let _ = arena.insert(0); + /// assert_eq!(arena.len(), 2); + /// + /// assert_eq!(arena.remove(idx), Some(42)); + /// assert_eq!(arena.len(), 1); + /// ``` + pub fn len(&self) -> usize { + self.len + } + + /// Returns true if the arena contains no elements + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// assert!(arena.is_empty()); + /// + /// let idx = arena.insert(42); + /// assert!(!arena.is_empty()); + /// + /// assert_eq!(arena.remove(idx), Some(42)); + /// assert!(arena.is_empty()); + /// ``` + pub fn is_empty(&self) -> bool { + self.len == 0 + } + + /// Get the capacity of this arena. + /// + /// The capacity is the maximum number of elements the arena can hold + /// without further allocation, including however many it currently + /// contains. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(10); + /// assert_eq!(arena.capacity(), 10); + /// + /// // `try_insert` does not allocate new capacity. + /// for i in 0..10 { + /// assert!(arena.try_insert(1).is_ok()); + /// assert_eq!(arena.capacity(), 10); + /// } + /// + /// // But `insert` will if the arena is already at capacity. + /// arena.insert(0); + /// assert!(arena.capacity() > 10); + /// ``` + pub fn capacity(&self) -> usize { + self.items.len() + } + + /// Allocate space for `additional_capacity` more elements in the arena. + /// + /// # Panics + /// + /// Panics if this causes the capacity to overflow. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::with_capacity(10); + /// arena.reserve(5); + /// assert_eq!(arena.capacity(), 15); + /// # let _: Arena = arena; + /// ``` + pub fn reserve(&mut self, additional_capacity: usize) { + let start = self.items.len(); + let end = self.items.len() + additional_capacity; + let old_head = self.free_list_head; + self.items.reserve_exact(additional_capacity); + self.items.extend((start..end).map(|i| { + if i == end - 1 { + Entry::Free { + next_free: old_head, + } + } else { + Entry::Free { + next_free: Some(i + 1), + } + } + })); + self.free_list_head = Some(start); + } + + /// Iterate over shared references to the elements in this arena. + /// + /// Yields pairs of `(Index, &T)` items. + /// + /// Order of iteration is not defined. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// for i in 0..10 { + /// arena.insert(i * i); + /// } + /// + /// for (idx, value) in arena.iter() { + /// println!("{} is at index {:?}", value, idx); + /// } + /// ``` + pub fn iter(&self) -> Iter { + Iter { + len: self.len, + inner: self.items.iter().enumerate(), + } + } + + /// Iterate over exclusive references to the elements in this arena. + /// + /// Yields pairs of `(Index, &mut T)` items. + /// + /// Order of iteration is not defined. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// for i in 0..10 { + /// arena.insert(i * i); + /// } + /// + /// for (_idx, value) in arena.iter_mut() { + /// *value += 5; + /// } + /// ``` + pub fn iter_mut(&mut self) -> IterMut { + IterMut { + len: self.len, + inner: self.items.iter_mut().enumerate(), + } + } + + /// Iterate over elements of the arena and remove them. + /// + /// Yields pairs of `(Index, T)` items. + /// + /// Order of iteration is not defined. + /// + /// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all. + /// + /// # Examples + /// + /// ```ignore + /// use rapier::data::arena::Arena; + /// + /// let mut arena = Arena::new(); + /// let idx_1 = arena.insert("hello"); + /// let idx_2 = arena.insert("world"); + /// + /// assert!(arena.get(idx_1).is_some()); + /// assert!(arena.get(idx_2).is_some()); + /// for (idx, value) in arena.drain() { + /// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world")); + /// } + /// assert!(arena.get(idx_1).is_none()); + /// assert!(arena.get(idx_2).is_none()); + /// ``` + pub fn drain(&mut self) -> Drain { + Drain { + inner: self.items.drain(..).enumerate(), + } + } + + /// Given an i of `usize` without a generation, get a shared reference + /// to the element and the matching `Index` of the entry behind `i`. + /// + /// This method is useful when you know there might be an element at the + /// position i, but don't know its generation or precise Index. + /// + /// Use cases include using indexing such as Hierarchical BitMap Indexing or + /// other kinds of bit-efficient indexing. + /// + /// You should use the `get` method instead most of the time. + pub fn get_unknown_gen(&self, i: usize) -> Option<(&T, Index)> { + match self.items.get(i) { + Some(Entry::Occupied { generation, value }) => Some(( + value, + Index { + generation: *generation, + index: i, + }, + )), + _ => None, + } + } + + /// Given an i of `usize` without a generation, get an exclusive reference + /// to the element and the matching `Index` of the entry behind `i`. + /// + /// This method is useful when you know there might be an element at the + /// position i, but don't know its generation or precise Index. + /// + /// Use cases include using indexing such as Hierarchical BitMap Indexing or + /// other kinds of bit-efficient indexing. + /// + /// You should use the `get_mut` method instead most of the time. + pub fn get_unknown_gen_mut(&mut self, i: usize) -> Option<(&mut T, Index)> { + match self.items.get_mut(i) { + Some(Entry::Occupied { generation, value }) => Some(( + value, + Index { + generation: *generation, + index: i, + }, + )), + _ => None, + } + } +} + +impl IntoIterator for Arena { + type Item = T; + type IntoIter = IntoIter; + fn into_iter(self) -> Self::IntoIter { + IntoIter { + len: self.len, + inner: self.items.into_iter(), + } + } +} + +/// An iterator over the elements in an arena. +/// +/// Yields `T` items. +/// +/// Order of iteration is not defined. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// for i in 0..10 { +/// arena.insert(i * i); +/// } +/// +/// for value in arena { +/// assert!(value < 100); +/// } +/// ``` +#[derive(Clone, Debug)] +pub struct IntoIter { + len: usize, + inner: vec::IntoIter>, +} + +impl Iterator for IntoIter { + type Item = T; + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some(Entry::Free { .. }) => continue, + Some(Entry::Occupied { value, .. }) => { + self.len -= 1; + return Some(value); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl DoubleEndedIterator for IntoIter { + fn next_back(&mut self) -> Option { + loop { + match self.inner.next_back() { + Some(Entry::Free { .. }) => continue, + Some(Entry::Occupied { value, .. }) => { + self.len -= 1; + return Some(value); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } +} + +impl ExactSizeIterator for IntoIter { + fn len(&self) -> usize { + self.len + } +} + +impl FusedIterator for IntoIter {} + +impl<'a, T> IntoIterator for &'a Arena { + type Item = (Index, &'a T); + type IntoIter = Iter<'a, T>; + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +/// An iterator over shared references to the elements in an arena. +/// +/// Yields pairs of `(Index, &T)` items. +/// +/// Order of iteration is not defined. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// for i in 0..10 { +/// arena.insert(i * i); +/// } +/// +/// for (idx, value) in &arena { +/// println!("{} is at index {:?}", value, idx); +/// } +/// ``` +#[derive(Clone, Debug)] +pub struct Iter<'a, T: 'a> { + len: usize, + inner: iter::Enumerate>>, +} + +impl<'a, T> Iterator for Iter<'a, T> { + type Item = (Index, &'a T); + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some((_, &Entry::Free { .. })) => continue, + Some(( + index, + &Entry::Occupied { + generation, + ref value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl<'a, T> DoubleEndedIterator for Iter<'a, T> { + fn next_back(&mut self) -> Option { + loop { + match self.inner.next_back() { + Some((_, &Entry::Free { .. })) => continue, + Some(( + index, + &Entry::Occupied { + generation, + ref value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } +} + +impl<'a, T> ExactSizeIterator for Iter<'a, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<'a, T> FusedIterator for Iter<'a, T> {} + +impl<'a, T> IntoIterator for &'a mut Arena { + type Item = (Index, &'a mut T); + type IntoIter = IterMut<'a, T>; + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +/// An iterator over exclusive references to elements in this arena. +/// +/// Yields pairs of `(Index, &mut T)` items. +/// +/// Order of iteration is not defined. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// for i in 0..10 { +/// arena.insert(i * i); +/// } +/// +/// for (_idx, value) in &mut arena { +/// *value += 5; +/// } +/// ``` +#[derive(Debug)] +pub struct IterMut<'a, T: 'a> { + len: usize, + inner: iter::Enumerate>>, +} + +impl<'a, T> Iterator for IterMut<'a, T> { + type Item = (Index, &'a mut T); + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some((_, &mut Entry::Free { .. })) => continue, + Some(( + index, + &mut Entry::Occupied { + generation, + ref mut value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } + + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { + fn next_back(&mut self) -> Option { + loop { + match self.inner.next_back() { + Some((_, &mut Entry::Free { .. })) => continue, + Some(( + index, + &mut Entry::Occupied { + generation, + ref mut value, + }, + )) => { + self.len -= 1; + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => { + debug_assert_eq!(self.len, 0); + return None; + } + } + } + } +} + +impl<'a, T> ExactSizeIterator for IterMut<'a, T> { + fn len(&self) -> usize { + self.len + } +} + +impl<'a, T> FusedIterator for IterMut<'a, T> {} + +/// An iterator that removes elements from the arena. +/// +/// Yields pairs of `(Index, T)` items. +/// +/// Order of iteration is not defined. +/// +/// Note: All elements are removed even if the iterator is only partially consumed or not consumed at all. +/// +/// # Examples +/// +/// ```ignore +/// use rapier::data::arena::Arena; +/// +/// let mut arena = Arena::new(); +/// let idx_1 = arena.insert("hello"); +/// let idx_2 = arena.insert("world"); +/// +/// assert!(arena.get(idx_1).is_some()); +/// assert!(arena.get(idx_2).is_some()); +/// for (idx, value) in arena.drain() { +/// assert!((idx == idx_1 && value == "hello") || (idx == idx_2 && value == "world")); +/// } +/// assert!(arena.get(idx_1).is_none()); +/// assert!(arena.get(idx_2).is_none()); +/// ``` +#[derive(Debug)] +pub struct Drain<'a, T: 'a> { + inner: iter::Enumerate>>, +} + +impl<'a, T> Iterator for Drain<'a, T> { + type Item = (Index, T); + + fn next(&mut self) -> Option { + loop { + match self.inner.next() { + Some((_, Entry::Free { .. })) => continue, + Some((index, Entry::Occupied { generation, value })) => { + let idx = Index { index, generation }; + return Some((idx, value)); + } + None => return None, + } + } + } +} + +impl Extend for Arena { + fn extend>(&mut self, iter: I) { + for t in iter { + self.insert(t); + } + } +} + +impl FromIterator for Arena { + fn from_iter>(iter: I) -> Self { + let iter = iter.into_iter(); + let (lower, upper) = iter.size_hint(); + let cap = upper.unwrap_or(lower); + let cap = cmp::max(cap, 1); + let mut arena = Arena::with_capacity(cap); + arena.extend(iter); + arena + } +} + +impl ops::Index for Arena { + type Output = T; + + fn index(&self, index: Index) -> &Self::Output { + self.get(index).expect("No element at index") + } +} + +impl ops::IndexMut for Arena { + fn index_mut(&mut self, index: Index) -> &mut Self::Output { + self.get_mut(index).expect("No element at index") + } +} diff --git a/src/data/graph.rs b/src/data/graph.rs new file mode 100644 index 0000000..ea27e03 --- /dev/null +++ b/src/data/graph.rs @@ -0,0 +1,830 @@ +// This is basically a stripped down version of petgraph's UnGraph. +// - It is not generic wrt. the index type (we always use u32). +// - It preserves associated edge iteration order after Serialization/Deserialization. +// - It is always undirected. +//! A stripped-down version of petgraph's UnGraph. + +use std::cmp::max; +use std::ops::{Index, IndexMut}; + +/// Node identifier. +#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct NodeIndex(u32); + +impl NodeIndex { + #[inline] + pub fn new(x: u32) -> Self { + NodeIndex(x) + } + + #[inline] + pub fn index(self) -> usize { + self.0 as usize + } + + #[inline] + pub fn end() -> Self { + NodeIndex(crate::INVALID_U32) + } + + fn _into_edge(self) -> EdgeIndex { + EdgeIndex(self.0) + } +} + +impl From for NodeIndex { + fn from(ix: u32) -> Self { + NodeIndex(ix) + } +} + +/// Edge identifier. +#[derive(Copy, Clone, Default, PartialEq, PartialOrd, Eq, Ord, Hash, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct EdgeIndex(u32); + +impl EdgeIndex { + #[inline] + pub fn new(x: u32) -> Self { + EdgeIndex(x) + } + + #[inline] + pub fn index(self) -> usize { + self.0 as usize + } + + /// An invalid `EdgeIndex` used to denote absence of an edge, for example + /// to end an adjacency list. + #[inline] + pub fn end() -> Self { + EdgeIndex(crate::INVALID_U32) + } + + fn _into_node(self) -> NodeIndex { + NodeIndex(self.0) + } +} + +impl From for EdgeIndex { + fn from(ix: u32) -> Self { + EdgeIndex(ix) + } +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub enum Direction { + Outgoing = 0, + Incoming = 1, +} + +impl Direction { + fn opposite(self) -> Direction { + match self { + Direction::Outgoing => Direction::Incoming, + Direction::Incoming => Direction::Outgoing, + } + } +} + +const DIRECTIONS: [Direction; 2] = [Direction::Outgoing, Direction::Incoming]; + +/// The graph's node type. +#[derive(Debug, Copy, Clone)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Node { + /// Associated node data. + pub weight: N, + /// Next edge in outgoing and incoming edge lists. + next: [EdgeIndex; 2], +} + +/// The graph's edge type. +#[derive(Debug, Copy, Clone)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Edge { + /// Associated edge data. + pub weight: E, + /// Next edge in outgoing and incoming edge lists. + next: [EdgeIndex; 2], + /// Start and End node index + node: [NodeIndex; 2], +} + +impl Edge { + /// Return the source node index. + pub fn source(&self) -> NodeIndex { + self.node[0] + } + + /// Return the target node index. + pub fn target(&self) -> NodeIndex { + self.node[1] + } +} + +#[derive(Clone, Debug)] +#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))] +pub struct Graph { + pub(crate) nodes: Vec>, + pub(crate) edges: Vec>, +} + +enum Pair { + Both(T, T), + One(T), + None, +} + +/// Get mutable references at index `a` and `b`. +fn index_twice(arr: &mut [T], a: usize, b: usize) -> Pair<&mut T> { + if max(a, b) >= arr.len() { + Pair::None + } else if a == b { + Pair::One(&mut arr[max(a, b)]) + } else { + // safe because a, b are in bounds and distinct + unsafe { + let ar = &mut *(arr.get_unchecked_mut(a) as *mut _); + let br = &mut *(arr.get_unchecked_mut(b) as *mut _); + Pair::Both(ar, br) + } + } +} + +impl Graph { + /// Create a new `Graph` with estimated capacity. + pub fn with_capacity(nodes: usize, edges: usize) -> Self { + Graph { + nodes: Vec::with_capacity(nodes), + edges: Vec::with_capacity(edges), + } + } + + /// Add a node (also called vertex) with associated data `weight` to the graph. + /// + /// Computes in **O(1)** time. + /// + /// Return the index of the new node. + /// + /// **Panics** if the Graph is at the maximum number of nodes for its index + /// type (N/A if usize). + pub fn add_node(&mut self, weight: N) -> NodeIndex { + let node = Node { + weight, + next: [EdgeIndex::end(), EdgeIndex::end()], + }; + assert!(self.nodes.len() != crate::INVALID_USIZE); + let node_idx = NodeIndex::new(self.nodes.len() as u32); + self.nodes.push(node); + node_idx + } + + /// Access the weight for node `a`. + /// + /// Also available with indexing syntax: `&graph[a]`. + pub fn node_weight(&self, a: NodeIndex) -> Option<&N> { + self.nodes.get(a.index()).map(|n| &n.weight) + } + + /// Access the weight for edge `a`. + /// + /// Also available with indexing syntax: `&graph[a]`. + pub fn edge_weight(&self, a: EdgeIndex) -> Option<&E> { + self.edges.get(a.index()).map(|e| &e.weight) + } + + /// Access the weight for edge `a` mutably. + /// + /// Also available with indexing syntax: `&mut graph[a]`. + pub fn edge_weight_mut(&mut self, a: EdgeIndex) -> Option<&mut E> { + self.edges.get_mut(a.index()).map(|e| &mut e.weight) + } + + /// Add an edge from `a` to `b` to the graph, with its associated + /// data `weight`. + /// + /// Return the index of the new edge. + /// + /// Computes in **O(1)** time. + /// + /// **Panics** if any of the nodes don't exist.
+ /// **Panics** if the Graph is at the maximum number of edges for its index + /// type (N/A if usize). + /// + /// **Note:** `Graph` allows adding parallel (“duplicate”) edges. If you want + /// to avoid this, use [`.update_edge(a, b, weight)`](#method.update_edge) instead. + pub fn add_edge(&mut self, a: NodeIndex, b: NodeIndex, weight: E) -> EdgeIndex { + assert!(self.edges.len() != crate::INVALID_USIZE); + let edge_idx = EdgeIndex::new(self.edges.len() as u32); + let mut edge = Edge { + weight, + node: [a, b], + next: [EdgeIndex::end(); 2], + }; + match index_twice(&mut self.nodes, a.index(), b.index()) { + Pair::None => panic!("Graph::add_edge: node indices out of bounds"), + Pair::One(an) => { + edge.next = an.next; + an.next[0] = edge_idx; + an.next[1] = edge_idx; + } + Pair::Both(an, bn) => { + // a and b are different indices + edge.next = [an.next[0], bn.next[1]]; + an.next[0] = edge_idx; + bn.next[1] = edge_idx; + } + } + self.edges.push(edge); + edge_idx + } + + /// Access the source and target nodes for `e`. + pub fn edge_endpoints(&self, e: EdgeIndex) -> Option<(NodeIndex, NodeIndex)> { + self.edges + .get(e.index()) + .map(|ed| (ed.source(), ed.target())) + } + + /// Remove `a` from the graph if it exists, and return its weight. + /// If it doesn't exist in the graph, return `None`. + /// + /// Apart from `a`, this invalidates the last node index in the graph + /// (that node will adopt the removed node index). Edge indices are + /// invalidated as they would be following the removal of each edge + /// with an endpoint in `a`. + /// + /// Computes in **O(e')** time, where **e'** is the number of affected + /// edges, including *n* calls to `.remove_edge()` where *n* is the number + /// of edges with an endpoint in `a`, and including the edges with an + /// endpoint in the displaced node. + pub fn remove_node(&mut self, a: NodeIndex) -> Option { + self.nodes.get(a.index())?; + for d in &DIRECTIONS { + let k = *d as usize; + + // Remove all edges from and to this node. + loop { + let next = self.nodes[a.index()].next[k]; + if next == EdgeIndex::end() { + break; + } + let ret = self.remove_edge(next); + debug_assert!(ret.is_some()); + let _ = ret; + } + } + + // Use swap_remove -- only the swapped-in node is going to change + // NodeIndex, so we only have to walk its edges and update them. + + let node = self.nodes.swap_remove(a.index()); + + // Find the edge lists of the node that had to relocate. + // It may be that no node had to relocate, then we are done already. + let swap_edges = match self.nodes.get(a.index()) { + None => return Some(node.weight), + Some(ed) => ed.next, + }; + + // The swapped element's old index + let old_index = NodeIndex::new(self.nodes.len() as u32); + let new_index = a; + + // Adjust the starts of the out edges, and ends of the in edges. + for &d in &DIRECTIONS { + let k = d as usize; + let mut edges = edges_walker_mut(&mut self.edges, swap_edges[k], d); + while let Some(curedge) = edges.next_edge() { + debug_assert!(curedge.node[k] == old_index); + curedge.node[k] = new_index; + } + } + Some(node.weight) + } + + /// For edge `e` with endpoints `edge_node`, replace links to it, + /// with links to `edge_next`. + fn change_edge_links( + &mut self, + edge_node: [NodeIndex; 2], + e: EdgeIndex, + edge_next: [EdgeIndex; 2], + ) { + for &d in &DIRECTIONS { + let k = d as usize; + let node = match self.nodes.get_mut(edge_node[k].index()) { + Some(r) => r, + None => { + debug_assert!( + false, + "Edge's endpoint dir={:?} index={:?} not found", + d, edge_node[k] + ); + return; + } + }; + let fst = node.next[k]; + if fst == e { + //println!("Updating first edge 0 for node {}, set to {}", edge_node[0], edge_next[0]); + node.next[k] = edge_next[k]; + } else { + let mut edges = edges_walker_mut(&mut self.edges, fst, d); + while let Some(curedge) = edges.next_edge() { + if curedge.next[k] == e { + curedge.next[k] = edge_next[k]; + break; // the edge can only be present once in the list. + } + } + } + } + } + + /// Remove an edge and return its edge weight, or `None` if it didn't exist. + /// + /// Apart from `e`, this invalidates the last edge index in the graph + /// (that edge will adopt the removed edge index). + /// + /// Computes in **O(e')** time, where **e'** is the size of four particular edge lists, for + /// the vertices of `e` and the vertices of another affected edge. + pub fn remove_edge(&mut self, e: EdgeIndex) -> Option { + // every edge is part of two lists, + // outgoing and incoming edges. + // Remove it from both + let (edge_node, edge_next) = match self.edges.get(e.index()) { + None => return None, + Some(x) => (x.node, x.next), + }; + // Remove the edge from its in and out lists by replacing it with + // a link to the next in the list. + self.change_edge_links(edge_node, e, edge_next); + self.remove_edge_adjust_indices(e) + } + + fn remove_edge_adjust_indices(&mut self, e: EdgeIndex) -> Option { + // swap_remove the edge -- only the removed edge + // and the edge swapped into place are affected and need updating + // indices. + let edge = self.edges.swap_remove(e.index()); + let swap = match self.edges.get(e.index()) { + // no elment needed to be swapped. + None => return Some(edge.weight), + Some(ed) => ed.node, + }; + let swapped_e = EdgeIndex::new(self.edges.len() as u32); + + // Update the edge lists by replacing links to the old index by references to the new + // edge index. + self.change_edge_links(swap, swapped_e, [e, e]); + Some(edge.weight) + } + + /// Return an iterator of all edges of `a`. + /// + /// - `Directed`: Outgoing edges from `a`. + /// - `Undirected`: All edges connected to `a`. + /// + /// Produces an empty iterator if the node doesn't exist.
+ /// Iterator element type is `EdgeReference`. + pub fn edges(&self, a: NodeIndex) -> Edges { + self.edges_directed(a, Direction::Outgoing) + } + + /// Return an iterator of all edges of `a`, in the specified direction. + /// + /// - `Directed`, `Outgoing`: All edges from `a`. + /// - `Directed`, `Incoming`: All edges to `a`. + /// - `Undirected`, `Outgoing`: All edges connected to `a`, with `a` being the source of each + /// edge. + /// - `Undirected`, `Incoming`: All edges connected to `a`, with `a` being the target of each + /// edge. + /// + /// Produces an empty iterator if the node `a` doesn't exist.
+ /// Iterator element type is `EdgeReference`. + pub fn edges_directed(&self, a: NodeIndex, dir: Direction) -> Edges { + Edges { + skip_start: a, + edges: &self.edges, + direction: dir, + next: match self.nodes.get(a.index()) { + None => [EdgeIndex::end(), EdgeIndex::end()], + Some(n) => n.next, + }, + } + } + + /* + /// Return an iterator over all the edges connecting `a` and `b`. + /// + /// - `Directed`: Outgoing edges from `a`. + /// - `Undirected`: All edges connected to `a`. + /// + /// Iterator element type is `EdgeReference`. + pub fn edges_connecting(&self, a: NodeIndex, b: NodeIndex) -> EdgesConnecting { + EdgesConnecting { + target_node: b, + edges: self.edges_directed(a, Direction::Outgoing), + ty: PhantomData, + } + } + */ + + /// Lookup an edge from `a` to `b`. + /// + /// Computes in **O(e')** time, where **e'** is the number of edges + /// connected to `a` (and `b`, if the graph edges are undirected). + pub fn find_edge(&self, a: NodeIndex, b: NodeIndex) -> Option { + self.find_edge_undirected(a, b).map(|(ix, _)| ix) + } + + /// Lookup an edge between `a` and `b`, in either direction. + /// + /// If the graph is undirected, then this is equivalent to `.find_edge()`. + /// + /// Return the edge index and its directionality, with `Outgoing` meaning + /// from `a` to `b` and `Incoming` the reverse, + /// or `None` if the edge does not exist. + pub fn find_edge_undirected( + &self, + a: NodeIndex, + b: NodeIndex, + ) -> Option<(EdgeIndex, Direction)> { + match self.nodes.get(a.index()) { + None => None, + Some(node) => self.find_edge_undirected_from_node(node, b), + } + } + + fn find_edge_undirected_from_node( + &self, + node: &Node, + b: NodeIndex, + ) -> Option<(EdgeIndex, Direction)> { + for &d in &DIRECTIONS { + let k = d as usize; + let mut edix = node.next[k]; + while let Some(edge) = self.edges.get(edix.index()) { + if edge.node[1 - k] == b { + return Some((edix, d)); + } + edix = edge.next[k]; + } + } + None + } + + /// Access the internal node array. + pub fn raw_nodes(&self) -> &[Node] { + &self.nodes + } + + /// Access the internal edge array. + pub fn raw_edges(&self) -> &[Edge] { + &self.edges + } + + /// Accessor for data structure internals: the first edge in the given direction. + pub fn first_edge(&self, a: NodeIndex, dir: Direction) -> Option { + match self.nodes.get(a.index()) { + None => None, + Some(node) => { + let edix = node.next[dir as usize]; + if edix == EdgeIndex::end() { + None + } else { + Some(edix) + } + } + } + } + + /// Accessor for data structure internals: the next edge for the given direction. + pub fn next_edge(&self, e: EdgeIndex, dir: Direction) -> Option { + match self.edges.get(e.index()) { + None => None, + Some(node) => { + let edix = node.next[dir as usize]; + if edix == EdgeIndex::end() { + None + } else { + Some(edix) + } + } + } + } +} + +/// An iterator over either the nodes without edges to them or from them. +pub struct Externals<'a, N: 'a> { + iter: std::iter::Enumerate>>, + dir: Direction, +} + +impl<'a, N: 'a> Iterator for Externals<'a, N> { + type Item = NodeIndex; + fn next(&mut self) -> Option { + let k = self.dir as usize; + loop { + match self.iter.next() { + None => return None, + Some((index, node)) => { + if node.next[k] == EdgeIndex::end() && node.next[1 - k] == EdgeIndex::end() { + return Some(NodeIndex::new(index as u32)); + } else { + continue; + } + } + } + } + } +} + +/// Iterator over the neighbors of a node. +/// +/// Iterator element type is `NodeIndex`. +/// +/// Created with [`.neighbors()`][1], [`.neighbors_directed()`][2] or +/// [`.neighbors_undirected()`][3]. +/// +/// [1]: struct.Graph.html#method.neighbors +/// [2]: struct.Graph.html#method.neighbors_directed +/// [3]: struct.Graph.html#method.neighbors_undirected +pub struct Neighbors<'a, E: 'a> { + /// starting node to skip over + skip_start: NodeIndex, + edges: &'a [Edge], + next: [EdgeIndex; 2], +} + +impl<'a, E> Iterator for Neighbors<'a, E> { + type Item = NodeIndex; + + fn next(&mut self) -> Option { + // First any outgoing edges + match self.edges.get(self.next[0].index()) { + None => {} + Some(edge) => { + self.next[0] = edge.next[0]; + return Some(edge.node[1]); + } + } + // Then incoming edges + // For an "undirected" iterator (traverse both incoming + // and outgoing edge lists), make sure we don't double + // count selfloops by skipping them in the incoming list. + while let Some(edge) = self.edges.get(self.next[1].index()) { + self.next[1] = edge.next[1]; + if edge.node[0] != self.skip_start { + return Some(edge.node[0]); + } + } + None + } +} + +struct EdgesWalkerMut<'a, E: 'a> { + edges: &'a mut [Edge], + next: EdgeIndex, + dir: Direction, +} + +fn edges_walker_mut( + edges: &mut [Edge], + next: EdgeIndex, + dir: Direction, +) -> EdgesWalkerMut { + EdgesWalkerMut { edges, next, dir } +} + +impl<'a, E> EdgesWalkerMut<'a, E> { + fn next_edge(&mut self) -> Option<&mut Edge> { + self.next().map(|t| t.1) + } + + fn next(&mut self) -> Option<(EdgeIndex, &mut Edge)> { + let this_index = self.next; + let k = self.dir as usize; + match self.edges.get_mut(self.next.index()) { + None => None, + Some(edge) => { + self.next = edge.next[k]; + Some((this_index, edge)) + } + } + } +} + +/// Iterator over the edges of from or to a node +pub struct Edges<'a, E: 'a> { + /// starting node to skip over + skip_start: NodeIndex, + edges: &'a [Edge], + + /// Next edge to visit. + next: [EdgeIndex; 2], + + /// For directed graphs: the direction to iterate in + /// For undirected graphs: the direction of edges + direction: Direction, +} + +impl<'a, E> Iterator for Edges<'a, E> { + type Item = EdgeReference<'a, E>; + + fn next(&mut self) -> Option { + // type direction | iterate over reverse + // | + // Directed Outgoing | outgoing no + // Directed Incoming | incoming no + // Undirected Outgoing | both incoming + // Undirected Incoming | both outgoing + + // For iterate_over, "both" is represented as None. + // For reverse, "no" is represented as None. + let (iterate_over, reverse) = (None, Some(self.direction.opposite())); + + if iterate_over.unwrap_or(Direction::Outgoing) == Direction::Outgoing { + let i = self.next[0].index(); + if let Some(Edge { node, weight, next }) = self.edges.get(i) { + self.next[0] = next[0]; + return Some(EdgeReference { + index: EdgeIndex(i as u32), + node: if reverse == Some(Direction::Outgoing) { + swap_pair(*node) + } else { + *node + }, + weight, + }); + } + } + + if iterate_over.unwrap_or(Direction::Incoming) == Direction::Incoming { + while let Some(Edge { node, weight, next }) = self.edges.get(self.next[1].index()) { + let edge_index = self.next[1]; + self.next[1] = next[1]; + // In any of the "both" situations, self-loops would be iterated over twice. + // Skip them here. + if iterate_over.is_none() && node[0] == self.skip_start { + continue; + } + + return Some(EdgeReference { + index: edge_index, + node: if reverse == Some(Direction::Incoming) { + swap_pair(*node) + } else { + *node + }, + weight, + }); + } + } + + None + } +} + +fn swap_pair(mut x: [T; 2]) -> [T; 2] { + x.swap(0, 1); + x +} + +impl<'a, E> Clone for Edges<'a, E> { + fn clone(&self) -> Self { + Edges { + skip_start: self.skip_start, + edges: self.edges, + next: self.next, + direction: self.direction, + } + } +} + +/// Index the `Graph` by `NodeIndex` to access node weights. +/// +/// **Panics** if the node doesn't exist. +impl Index for Graph { + type Output = N; + fn index(&self, index: NodeIndex) -> &N { + &self.nodes[index.index()].weight + } +} + +/// Index the `Graph` by `NodeIndex` to access node weights. +/// +/// **Panics** if the node doesn't exist. +impl IndexMut for Graph { + fn index_mut(&mut self, index: NodeIndex) -> &mut N { + &mut self.nodes[index.index()].weight + } +} + +/// Index the `Graph` by `EdgeIndex` to access edge weights. +/// +/// **Panics** if the edge doesn't exist. +impl Index for Graph { + type Output = E; + fn index(&self, index: EdgeIndex) -> &E { + &self.edges[index.index()].weight + } +} + +/// Index the `Graph` by `EdgeIndex` to access edge weights. +/// +/// **Panics** if the edge doesn't exist. +impl IndexMut for Graph { + fn index_mut(&mut self, index: EdgeIndex) -> &mut E { + &mut self.edges[index.index()].weight + } +} + +/// A “walker” object that can be used to step through the edge list of a node. +/// +/// Created with [`.detach()`](struct.Neighbors.html#method.detach). +/// +/// The walker does not borrow from the graph, so it lets you step through +/// neighbors or incident edges while also mutating graph weights, as +/// in the following example: +pub struct WalkNeighbors { + skip_start: NodeIndex, + next: [EdgeIndex; 2], +} + +impl Clone for WalkNeighbors { + fn clone(&self) -> Self { + WalkNeighbors { + skip_start: self.skip_start, + next: self.next, + } + } +} + +/// Reference to a `Graph` edge. +#[derive(Debug)] +pub struct EdgeReference<'a, E: 'a> { + index: EdgeIndex, + node: [NodeIndex; 2], + weight: &'a E, +} + +impl<'a, E: 'a> EdgeReference<'a, E> { + #[inline] + pub fn id(&self) -> EdgeIndex { + self.index + } + + #[inline] + pub fn weight(&self) -> &'a E { + self.weight + } +} + +impl<'a, E> Clone for EdgeReference<'a, E> { + fn clone(&self) -> Self { + *self + } +} + +impl<'a, E> Copy for EdgeReference<'a, E> {} + +impl<'a, E> PartialEq for EdgeReference<'a, E> +where + E: PartialEq, +{ + fn eq(&self, rhs: &Self) -> bool { + self.index == rhs.index && self.weight == rhs.weight + } +} + +/// Iterator over all nodes of a graph. +pub struct NodeReferences<'a, N: 'a> { + iter: std::iter::Enumerate>>, +} + +impl<'a, N> Iterator for NodeReferences<'a, N> { + type Item = (NodeIndex, &'a N); + + fn next(&mut self) -> Option { + self.iter + .next() + .map(|(i, node)| (NodeIndex::new(i as u32), &node.weight)) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +impl<'a, N> DoubleEndedIterator for NodeReferences<'a, N> { + fn next_back(&mut self) -> Option { + self.iter + .next_back() + .map(|(i, node)| (NodeIndex::new(i as u32), &node.weight)) + } +} + +impl<'a, N> ExactSizeIterator for NodeReferences<'a, N> {} diff --git a/src/data/mod.rs b/src/data/mod.rs new file mode 100644 index 0000000..7c00442 --- /dev/null +++ b/src/data/mod.rs @@ -0,0 +1,4 @@ +//! Data structures modified with guaranteed deterministic behavior after deserialization. + +pub mod arena; +pub(crate) mod graph; -- cgit