odem-rs-core 0.3.0

//! This module provides utility types for ordering and interval management
//! within the simulation calendar. It includes:
//!
//! - `Cyclic`: A newtype wrapper over `Wrapping<T>` that implements cyclic
//!   (modular) ordering on unsigned integers. This ordering treats numbers as
//!   arranged in a ring so that comparisons wrap around the maximum value.
//!
//! - `Partition`: A type representing fully ordered, non-overlapping
//!   intervals of contiguous integers. Partitions are used as precedence types
//!   and support efficient hierarchical (depth-first) comparisons via a
//!   compact, single-integer representation.

use core::{
	cmp::Ordering,
	fmt,
	num::Wrapping,
	ops::{Add, AddAssign, Sub, SubAssign},
};

/* ********************************************************************* Mark */

/// A newtype wrapper for unsigned integers with cyclic (modular) ordering.
///
/// In cyclic ordering, the values are conceptually arranged in a ring. An
/// element `a` is considered less than an element `b` if the backward distance
/// (wrapping around the end) from `b` to `a` is smaller than the forward
/// distance. Although this ordering does not satisfy transitivity globally
/// (e.g., one may find `x < y < z < x` spanning the entire range), any
/// contiguous subset that covers less than half the range is totally ordered.
#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
#[cfg_attr(doc, derive(PartialOrd, Ord))]
pub struct Cyclic<T>(pub Wrapping<T>);

/// Implements the `PartialOrd` and `Ord` traits for the `Cyclic<T>` newtype
/// wrapper, enabling cyclic (modular) ordering for the underlying unsigned
/// integer type.
///
/// The cyclic ordering is achieved by subtracting the inner values (with
/// wrapping arithmetic) and converting the result to a corresponding signed
/// integer type. The sign of the result determines the order, which allows
/// values to be compared as if they were arranged on a ring.
macro_rules! impl_cyclic {
	(@impl $UID:ident -> $SID:ident) => {
		impl Cyclic<$UID> {
			/// Constructs the smallest value with cyclic ordering, relative to
			/// the value passed into this function.
			#[allow(dead_code)]
			pub const fn relative_min(self) -> Self {
				// incrementing the relative maximum by one yields the minimal
				// value
				Cyclic(Wrapping(self.relative_max().0.0.wrapping_add(1)))
			}

			/// Constructs the largest value with cyclic ordering, relative to
			/// the value passed into this function.
			#[allow(dead_code)]
			pub const fn relative_max(self) -> Self {
				// flip the first bit for the value the largest, relative to
				// the initial value
				Cyclic::new(self.0.0 ^ !(!(0 as $UID) >> 1))
			}
		}

		impl PartialOrd for Cyclic<$UID> {
			fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
				Some(self.cmp(other))
			}
		}

		impl Ord for Cyclic<$UID> {
			fn cmp(&self, other: &Self) -> Ordering {
				// Compute the difference and use its signum to determine the cyclic order.
				match (self.0.0.wrapping_sub(other.0.0) as $SID).signum() {
					0 => Ordering::Equal,
					1 => Ordering::Greater,
					_ => Ordering::Less,
				}
			}
		}
	};

	($($UID:ident -> $SID:ident),* $(,)?) => {
		$(impl_cyclic!(@impl $UID -> $SID);)*
	};
}

#[cfg(not(doc))]
impl_cyclic!(u8 -> i8, u16 -> i16, u32 -> i32, u64 -> i64, usize -> isize);

// Forwarding implementation for Cyclic<T> to Wrapping<T>
impl<T: fmt::Display> fmt::Display for Cyclic<T> {
	#[inline]
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		self.0.fmt(f)
	}
}

impl<T> Cyclic<T> {
	/// Creates a new value with cyclic ordering.
	#[allow(dead_code)]
	pub const fn new(value: T) -> Self {
		Cyclic(Wrapping(value))
	}
}

impl<T> Add for Cyclic<T>
where
	Wrapping<T>: Add<Output = Wrapping<T>>,
{
	type Output = Self;

	#[inline]
	fn add(self, other: Self) -> Self {
		Cyclic(self.0 + other.0)
	}
}

impl<T> Add<T> for Cyclic<T>
where
	Wrapping<T>: Add<Output = Wrapping<T>>,
{
	type Output = Self;

	#[inline]
	fn add(self, other: T) -> Self {
		Cyclic(self.0 + Wrapping(other))
	}
}

impl<T> AddAssign for Cyclic<T>
where
	Wrapping<T>: AddAssign,
{
	#[inline]
	fn add_assign(&mut self, other: Self) {
		self.0 += other.0;
	}
}

impl<T> AddAssign<T> for Cyclic<T>
where
	Wrapping<T>: AddAssign<T>,
{
	#[inline]
	fn add_assign(&mut self, other: T) {
		self.0 += other;
	}
}

impl<T> Sub for Cyclic<T>
where
	Wrapping<T>: Sub<Output = Wrapping<T>>,
{
	type Output = Self;

	#[inline]
	fn sub(self, other: Self) -> Self {
		Cyclic(self.0 - other.0)
	}
}

impl<T> Sub<T> for Cyclic<T>
where
	Wrapping<T>: Sub<Output = Wrapping<T>>,
{
	type Output = Self;

	#[inline]
	fn sub(self, other: T) -> Self {
		Cyclic(self.0 - Wrapping(other))
	}
}

impl<T> SubAssign for Cyclic<T>
where
	Wrapping<T>: SubAssign,
{
	#[inline]
	fn sub_assign(&mut self, other: Self) {
		self.0 -= other.0;
	}
}

impl<T> SubAssign<T> for Cyclic<T>
where
	Wrapping<T>: SubAssign<T>,
{
	#[inline]
	fn sub_assign(&mut self, other: T) {
		self.0 -= other;
	}
}

/* *************************************************************** Partitions */

/// A type representing fully ordered, non-overlapping intervals of contiguous
/// integers.
///
/// The `Partition` type is used as a precedence marker within the simulation
/// library. Intervals are ordered in a depth-first fashion: parent intervals
/// sort before their subintervals, and adjacent intervals sort in ascending
/// order. Because all generated intervals do not overlap, comparing two
/// `Partition` values is as simple as comparing their underlying integer
/// values, ensuring efficient hierarchical comparisons.
///
/// # Internal Layout
///
/// The internal representation uses a single unsigned integer by splitting its
/// bits into two fields:
///
/// - **Offset**: The higher bits (from bit `n-1` down to bit `e`) represent the
///   starting point.
/// - **Nesting**: The lower `e` bits (from bit `e-1` down to bit `0`) represent
///   the nesting level, which determines the interval’s granularity.
///
/// Here, `n` is the total number of bits in the underlying type, and `e` is
/// `ilog2(n)`. This arrangement reserves `e` bits to encode the degree of
/// nesting (or precision), allowing the interval to be expressed as a
/// power-of-two subdivision of the full range.
///
/// ## Example for `Partition<u8>`
///
/// For an 8-bit unsigned integer, `e = ilog2(8) = 3`, so:
///
/// - **Offset**: Uses the 5 most significant bits (bits 7..3).
/// - **Nesting**: Uses the 3 least significant bits (bits 2..0).
///
/// - `Partition(0u8)` represents the interval `[0, 32)` since the offset is 0
///   and no nesting has occurred (2⁵ = 32).
/// - `Partition(1u8)` represents the interval `[0, 16)`, as a nesting level of
///   1 halves the interval.
/// - `Partition(9u8)` (binary `00001001`) represents an interval starting at 1
///   with a nesting level of 1, corresponding to `[1, 16)`.
///   - Here we see that the generated partition doesn't overlap with its
///     neighboring partition `Partition(137)` (binary `10001001`) starting at
///     17 with a nesting level of 1, i.e. `[17, 32)`.
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Default)]
pub struct Partition<T>(pub T);

/// An iterator over the subintervals generated by splitting a combined
/// interval.
///
/// This iterator is returned by the [split] method on `Partition`.
///
/// [split]: Partition::split
struct Iter<T> {
	/// Contains the next partition to be returned.
	next: Partition<T>,
	/// Contains the number of partitions left in this iterator.
	size: T,
}

/// Implements methods and trait implementations for the `Partition<T>` type,
/// which represents fully ordered, non-overlapping intervals of contiguous
/// integers.
///
/// The macro generates:
///
/// - Methods for constructing a universal partition (`new`), splitting an
///   interval into subintervals (`split`), and advancing the partition at the
///   current nesting level (`advance`, `advance_by`).
/// - Computations for properties such as the available capacity for further
///   splits (`capacity`), the starting offset of the interval (`offset`), the
///   current nesting level (`nesting`), and the interval's size (`delta`).
/// - Methods to get the interval as a half-open integer range (`range`) and
///   as a normalized floating-point range in `[0, 1)` (`float_range`).
/// - Trait implementations including `From`, `Display`, `Debug`, `Binary`, and
///   iterator traits for a helper iterator (`Iter<T>`) that yield
///   subintervals.
///
/// The macro supports two modes:
///
/// - **Implementation mode**: Produces the full method implementations for a
///   given unsigned integer type.
/// - **Documentation mode**: Provides stubbed implementations using
///   `unimplemented!()` to generate documentation without revealing the full
///   logic.
macro_rules! impl_prec {
	(@impl $UID:ident $($GEN:ident)?) => {
		impl<$($GEN)*> Partition<$UID> {
			/// The number of bits used to store the nesting level.
			///
			/// This is computed as `ilog2(n)`, where `n` is the total number of
			/// bits in the underlying type.
			const EXP_BITS: u32 = $UID::BITS.ilog2();

			/// The number of bits used to store the offset (precision).
			const NUM_BITS: u32 = $UID::BITS - Self::EXP_BITS;

			/// A bitmask covering all bits used to store the nesting level.
			const EXP_MASK: $UID = !(!0 << Self::EXP_BITS);

			/// Creates a new partition representing the universal range.
			pub const fn new() -> Self {
				Self(0)
			}

			/// Creates the lowest precedence representing the last in the
			/// precedence ordering.
			///
			/// This is the opposite of the precedence returned by [`Self::new`].
			pub const fn lowest() -> Self {
				Self((!0 << Self::EXP_BITS) | (Self::NUM_BITS as $UID))
			}

			/// Splits the current interval into `n` sub-intervals.
			///
			/// Returns an iterator over the sub-intervals if there is
			/// sufficient remaining precision; otherwise, returns `None`.
			pub const fn split(self, n: $UID) -> Option<impl ExactSizeIterator<Item = Self>> {
				let bits = n.next_power_of_two().trailing_zeros();

				if bits <= self.capacity() {
					Some(Iter {
						next: Self(self.0 + bits as $UID),
						size: n
					})
				} else {
					None
				}
			}

			/// Advances to the next interval at the current nesting level.
			///
			/// **Note:** Calling this method without having split the partition
			/// into enough sub-intervals may yield unexpected results.
			const fn advance(self) -> Self {
				self.advance_by(1)
			}

			/// Advances by the specified number of intervals at the current
			/// nesting level.
			///
			/// See [advance] for caveats.
			///
			/// [advance]: Self::advance
			const fn advance_by(self, count: u32) -> Self {
				Self(
					self.0.wrapping_add(
						(count as $UID).wrapping_shl(self.0.wrapping_neg() as u32)
					)
				)
			}

			/// Returns the remaining capacity for splitting as the number of
			/// available bits.
			///
			/// This represents the number of additional subdivisions (expressed
			/// as a power of two) that can be encoded.
			pub const fn capacity(self) -> u32 {
				Self::NUM_BITS - self.nesting() as u32
			}

			/// Returns the starting point (offset) of the interval represented
			/// by this partition.
			const fn offset(self) -> $UID {
				self.0 >> Self::EXP_BITS
			}

			/// Returns the current nesting level.
			///
			/// The nesting level indicates how many times the interval has been
			/// subdivided, starting from 0.
			const fn nesting(self) -> $UID {
				self.0 & Self::EXP_MASK
			}

			/// Computes the length (delta) of the interval, taking the nesting
			/// level into account.
			const fn delta(self) -> $UID {
				(!0) as $UID >> Self::EXP_BITS >> self.nesting()
			}

			/// Returns the half-open interval `[start, end)` represented by
			/// this partition.
			pub const fn range(self) -> core::ops::Range<$UID> {
				let lo = self.offset();
				// bitwise OR instead of PLUS to ensure that `hi` ends at the
				// partition border
				let hi = lo | self.delta();
				lo..hi+1
			}

			/// Returns the interval normalized to floating-point numbers in
			/// `[0, 1)`.
			///
			/// This converts the partition's range to a float range by dividing
			/// by the maximum possible value.
			pub fn float_range(self) -> core::ops::Range<f64> {
				let max = (1 as $UID) << Self::NUM_BITS;
				let range = self.range();

				(range.start as f64) / (max as f64)
				.. (range.end as f64) / (max as f64)
			}
		}

		impl<$($GEN)*> From<$UID> for Partition<$UID> {
			fn from(value: $UID) -> Self {
				Self((value << Self::EXP_BITS) | (Self::NUM_BITS as $UID))
			}
		}

		impl<$($GEN)*> fmt::Display for Partition<$UID> {
			fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
				f.debug_tuple("Partition")
				 .field(&self.float_range())
				 .finish()
			}
		}

		impl<$($GEN)*> fmt::Debug for Partition<$UID> {
			fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
				f.debug_struct("Partition")
				 .field("irange", &self.range())
				 .field("frange", &self.float_range())
				 .field("capacity", &self.capacity())
				 .finish()
			}
		}

		impl<$($GEN)*> fmt::Binary for Partition<$UID> {
			fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
				write!(
					f, "Partition({:0num$b}_{:0exp$b})",
					self.offset(), self.nesting(),
					exp = Self::EXP_BITS as usize,
					num = Self::NUM_BITS as usize
				)
			}
		}

		impl<$($GEN)*> Iterator for Iter<$UID> {
			type Item = Partition<$UID>;

			fn next(&mut self) -> Option<Self::Item> {
				if self.size > 0 {
					let next = self.next;
					self.size -= 1;
					self.next = next.advance();
					Some(next)
				} else {
					None
				}
			}

			fn size_hint(&self) -> (usize, Option<usize>) {
				(self.len(), Some(self.len()))
			}

			fn count(self) -> usize {
				self.len()
			}
		}

		impl<$($GEN)*> ExactSizeIterator for Iter<$UID> {
			fn len(&self) -> usize {
				self.size as usize
			}
		}
	};

	(@doc $UID:ident) => {
		impl_prec!(@impl $UID $UID);
	};

	($($UID:ident),* $(,)?) => {
		$(impl_prec!(@impl $UID);)*
	};
}

#[cfg(not(doc))]
impl_prec!(u8, u16, u32, u64, u128, usize);

#[cfg(doc)]
impl_prec!(@doc T);

/// Helper structure for keys that only implement [PartialOrd], e.g. [f32] and
/// [f64], that are expected to totally order at runtime.
///
/// Non-ordered values behave like wildcards and compare as equal to every other
/// value in this ordering.
#[repr(transparent)]
pub(crate) struct ForceOrd<T>(pub T);

impl<T: PartialEq> PartialEq for ForceOrd<T> {
	fn eq(&self, other: &Self) -> bool {
		self.0.eq(&other.0)
	}
}

impl<T: PartialOrd> Eq for ForceOrd<T> {}

impl<T: PartialOrd> PartialOrd for ForceOrd<T> {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		Some(self.cmp(other))
	}
}

impl<T: PartialOrd> Ord for ForceOrd<T> {
	fn cmp(&self, other: &Self) -> Ordering {
		self.0.partial_cmp(&other.0).unwrap_or(Ordering::Equal)
	}
}

#[cfg(test)]
mod tests {
	use super::*;
	use proptest::{prop_assert, proptest};

	proptest! {
		#[test]
		#[cfg_attr(miri, ignore)]
		fn cyclic_non_transitive(value: u32) {
			let x = Cyclic::new(value);
			let y = x.relative_max();
			let z = y + 100;
			prop_assert!(x < y && y < z && z < x);
		}

		#[test]
		#[cfg_attr(miri, ignore)]
		fn cyclic_relative_min(value: u32) {
			let x = Cyclic::new(value);
			let y = x.relative_min();
			prop_assert!(x > y);
		}

		#[test]
		#[cfg_attr(miri, ignore)]
		fn cyclic_relative_max(value: u32) {
			let x = Cyclic::new(value);
			let y = x.relative_max();
			prop_assert!(x < y);
		}

		#[test]
		#[cfg_attr(miri, ignore)]
		fn cyclic_relative_max_plus_one(value: u32) {
			let x = Cyclic::new(value);
			let y = x.relative_max() + 1;
			prop_assert!(x > y);
		}

		#[test]
		#[cfg_attr(miri, ignore)]
		fn cyclic_relative_min_minus_one(value: u32) {
			let x = Cyclic::new(value);
			let y = x.relative_min() - 1;
			prop_assert!(x < y);
		}
	}

	#[test]
	fn partition_capacity() {
		assert_eq!(Partition::<u8>::new().capacity(), 8 - 3);
		assert_eq!(Partition::<u16>::new().capacity(), 16 - 4);
		assert_eq!(Partition::<u32>::new().capacity(), 32 - 5);
		assert_eq!(Partition::<u64>::new().capacity(), 64 - 6);
		assert_eq!(Partition::<u128>::new().capacity(), 128 - 7);
	}

	#[test]
	fn partition_deep_nesting() {
		let p1 = Partition::<u8>::new();

		for p2 in p1.split(4).expect("remaining capacity is 5") {
			for p3 in p2.split(4).expect("remaining capacity is 3") {
				for p4 in p3.split(2).expect("remaining capacity is 1") {
					assert_eq!(p4.capacity(), 0);
				}
			}
		}
	}

	#[test]
	fn partition_shallow_nesting() {
		let p1 = Partition::<u8>::new();

		for p2 in p1.split(32).expect("remaining capacity is 5") {
			assert_eq!(p2.capacity(), 0);
		}
	}
}