node topological sorting

Change-Id: I6a6a6964255d818be1bf9a8f4ec9e317befa19c5

1 files changed, 190 insertions, 0 deletions

diff --git a/crates/core/src/utilities.rs b/crates/core/src/utilities.rs
new file mode 100644
index 0000000..583ad7c
--- /dev/null
+++ b/crates/core/src/utilities.rs
@@ -0,0 +1,190 @@
+//! Utilities used throughout the library.
+
+use alloc::{alloc::Allocator, collections::TryReserveError, vec::Vec};
+
+#[cfg(feature = "core-fmt")]
+use core::fmt;
+
+#[cfg(feature = "core-error")]
+use core::error;
+
+/// Extension trait for handling OOM conditions better with a [`Vec`].
+pub trait VecMemoryExt<T> {
+    /// Appends an element to the back of the vector.
+    ///
+    /// # Errors
+    ///
+    /// This method errors if the capacity overflows or if the allocator
+    /// reports a failure.
+    fn try_push(&mut self, value: T) -> Result<(), TryReserveError>;
+}
+
+impl<T, A> VecMemoryExt<T> for Vec<T, A>
+where
+    A: Allocator,
+{
+    fn try_push(&mut self, value: T) -> Result<(), TryReserveError> {
+        self.try_reserve(1)?;
+
+        //SAFETY: we just reserved space for this element
+        unsafe { self.push_within_capacity(value).unwrap_unchecked() };
+
+        Ok(())
+    }
+}
+
+/// Extension trait for wrapping arithmetic.
+pub trait WrappingArithmeticExt {
+    /// Wrapping integer increment.
+    fn wrapping_increment(self) -> Self;
+
+    /// Mutable wrapping integer increment.
+    fn wrapping_increment_mut(&mut self);
+
+    /// Wrapping integer decrement.
+    fn wrapping_decrement(self) -> Self;
+
+    /// Mutable wrapping integer decrement.
+    fn wrapping_decrement_mut(&mut self);
+}
+
+macro_rules! wrapping_arithmetic_ext_impl {
+    ($t:ty) => {
+        impl WrappingArithmeticExt for $t {
+            fn wrapping_increment(self) -> Self {
+                self.wrapping_add(1)
+            }
+
+            fn wrapping_increment_mut(&mut self) {
+                *self = self.wrapping_add(1);
+            }
+
+            fn wrapping_decrement(self) -> Self {
+                self.wrapping_sub(1)
+            }
+
+            fn wrapping_decrement_mut(&mut self) {
+                *self = self.wrapping_sub(1);
+            }
+        }
+    };
+}
+
+wrapping_arithmetic_ext_impl!(usize);
+wrapping_arithmetic_ext_impl!(u64);
+wrapping_arithmetic_ext_impl!(u32);
+wrapping_arithmetic_ext_impl!(u16);
+wrapping_arithmetic_ext_impl!(u8);
+
+wrapping_arithmetic_ext_impl!(isize);
+wrapping_arithmetic_ext_impl!(i64);
+wrapping_arithmetic_ext_impl!(i32);
+wrapping_arithmetic_ext_impl!(i16);
+wrapping_arithmetic_ext_impl!(i8);
+
+/// Extension trait for checked arithmetic that turns the output into a
+/// [`Result`].
+pub trait CheckedArithmeticExt: Sized {
+    /// Checked integer addition.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_add(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer division.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_div(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer multiplication.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_mul(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer remainder.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_rem(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer subtraction.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_sub(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+}
+
+macro_rules! checked_arithmetic_ext_impl {
+    ($t:ty) => {
+        impl CheckedArithmeticExt for $t {
+            fn errored_add(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_add(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_div(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_div(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_mul(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_mul(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_rem(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_rem(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_sub(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_sub(rhs).ok_or(IntegerOverflowError)
+            }
+        }
+    };
+}
+
+checked_arithmetic_ext_impl!(usize);
+checked_arithmetic_ext_impl!(u64);
+checked_arithmetic_ext_impl!(u32);
+checked_arithmetic_ext_impl!(u16);
+checked_arithmetic_ext_impl!(u8);
+
+checked_arithmetic_ext_impl!(isize);
+checked_arithmetic_ext_impl!(i64);
+checked_arithmetic_ext_impl!(i32);
+checked_arithmetic_ext_impl!(i16);
+checked_arithmetic_ext_impl!(i8);
+
+/// Representation of an integer overflow error.
+#[derive(PartialEq, Eq)]
+#[cfg_attr(feature = "core-fmt", derive(Debug))]
+pub struct IntegerOverflowError;
+
+#[cfg(feature = "core-fmt")]
+impl fmt::Display for IntegerOverflowError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str("integer overflow")
+    }
+}
+
+#[cfg(feature = "core-error")]
+impl error::Error for IntegerOverflowError {}