//! Range and iteration utilities.
//!
//! This module provides functionality for creating and iterating over ranges of values.
//! A range represents an interval of values from a start point to an end point.
//!
//! # Range Operator Forms
//!
//! There are currently two range operator forms:
//! `start..end`, representing a range from `start` (inclusive) to `end` (exclusive).
//! `start..=end`, representing a range from `start` (inclusive) to `end` (inclusive).
use core::iter::{IntoIterator, Iterator};
use core::num::traits::One;
use core::traits::Add;
/// A (half-open) range bounded inclusively below and exclusively above
/// (`start..end`).
///
/// The range `start..end` contains all values with `start <= x < end`.
/// It is empty if `start >= end`.
///
/// # Examples
///
/// The `start..end` syntax is a `Range`:
///
/// ```
/// assert!((3..5) == core::ops::Range { start: 3, end: 5 });
///
/// let mut sum = 0;
/// for i in 3..6 {
/// sum += i;
/// }
/// assert!(sum == 3 + 4 + 5);
/// ```
#[derive(Clone, Drop, PartialEq)]
pub struct Range<T> {
/// The lower bound of the range (inclusive).
pub start: T,
/// The upper bound of the range (exclusive).
pub end: T,
}
#[generate_trait]
pub impl RangeImpl<T, +Destruct<T>, +PartialOrd<@T>> of RangeTrait<T> {
/// Returns `true` if `item` is contained in the range.
///
/// # Examples
///
/// ```
/// assert!(!(3..5).contains(@2));
/// assert!( (3..5).contains(@3));
/// assert!( (3..5).contains(@4));
/// assert!(!(3..5).contains(@5));
///
/// assert!(!(3..3).contains(@3));
/// assert!(!(3..2).contains(@3));
/// ```
fn contains(self: @Range<T>, item: @T) -> bool {
@self.start <= item && item < @self.end
}
/// Returns `true` if the range contains no items.
///
/// # Examples
///
/// ```
/// assert!(!(3_u8..5_u8).is_empty());
/// assert!( (3_u8..3_u8).is_empty());
/// assert!( (3_u8..2_u8).is_empty());
/// ```
#[inline]
fn is_empty(self: @Range<T>) -> bool {
!(@self.start < @self.end)
}
}
impl RangeDebug<T, impl TDebug: crate::fmt::Debug<T>> of crate::fmt::Debug<Range<T>> {
fn fmt(self: @Range<T>, ref f: crate::fmt::Formatter) -> Result<(), crate::fmt::Error> {
self.start.fmt(ref f)?;
write!(f, "..")?;
self.end.fmt(ref f)?;
Ok(())
}
}
/// Handles the range binary operator (`..`).
/// Used by the compiler to create a `Range` from the given `start` (inclusive) and `end`
/// (exclusive) values.
pub trait RangeOp<T> {
fn range(start: T, end: T) -> Range<T>;
}
impl RangeOpImpl<T> of RangeOp<T> {
fn range(start: T, end: T) -> Range<T> {
Range { start, end }
}
}
/// Represents an iterator located at `cur`, whose end is `end` (`cur <= end`).
#[derive(Clone, Drop, PartialEq)]
pub struct RangeIterator<T> {
/// The current value of the iterator.
cur: T,
/// The upper bound of the range (exclusive).
end: T,
}
impl RangeIteratorImpl<
T, impl OneT: One<T>, +Add<T>, +Copy<T>, +Drop<T>, +PartialEq<T>,
> of Iterator<RangeIterator<T>> {
type Item = T;
fn next(ref self: RangeIterator<T>) -> Option<T> {
if self.cur != self.end {
let value = self.cur;
self.cur = value + OneT::one();
Some(value)
} else {
None
}
}
}
impl RangeIntoIterator<
T,
+One<T>,
+Add<T>,
+Copy<T>,
+Drop<T>,
+PartialEq<T>,
+PartialOrd<T>,
-SierraIntRangeSupport<T>,
> of IntoIterator<Range<T>> {
type IntoIter = RangeIterator<T>;
fn into_iter(self: Range<T>) -> Self::IntoIter {
let start = self.start;
let end = self.end;
if start < end {
Self::IntoIter { cur: start, end }
} else {
// Invalid range, return an empty range.
Self::IntoIter { cur: end, end }
}
}
}
/// Represents the range [start, end].
#[derive(Clone, Drop, PartialEq)]
pub struct RangeInclusive<T> {
/// The lower bound of the range (inclusive).
pub start: T,
/// The upper bound of the range (inclusive).
pub end: T,
}
#[derive(Clone, Drop)]
pub struct RangeInclusiveIterator<T> {
/// The current value of the iterator.
pub(crate) cur: T,
/// The upper bound of the range (inclusive).
pub(crate) end: T,
// This field is:
// - `false` upon construction
// - `false` when iteration has yielded an element and the iterator is not exhausted
// - `true` when iteration has been used to exhaust the iterator
//
// This is required to differentiate between the last element and the end of the range.
pub(crate) exhausted: bool,
}
/// Handles the range inclusive operator (`..=`).
pub trait RangeInclusiveOp<T> {
/// Handles the `..=` operator. Returns the value of the expression `start..=end`.
fn range_inclusive(start: T, end: T) -> RangeInclusive<T>;
}
impl RangeInclusiveOpImpl<T> of RangeInclusiveOp<T> {
fn range_inclusive(start: T, end: T) -> RangeInclusive<T> {
RangeInclusive { start, end }
}
}
#[generate_trait]
pub impl RangeInclusiveImpl<T, +Destruct<T>, +PartialOrd<@T>> of RangeInclusiveTrait<T> {
/// Returns `true` if `item` is contained in the range.
///
/// # Examples
///
/// ```
/// assert!(!(3..=5).contains(@2));
/// assert!( (3..=5).contains(@3));
/// assert!( (3..=5).contains(@4));
/// assert!( (3..=5).contains(@5));
/// assert!(!(3..=5).contains(@6));
///
/// assert!( (3..=3).contains(@3));
/// assert!(!(3..=2).contains(@3));
/// ```
fn contains(self: @RangeInclusive<T>, item: @T) -> bool {
@self.start <= item && item <= @self.end
}
/// Returns `true` if the range contains no items.
///
/// # Examples
///
/// ```
/// assert!(!(3_u8..=5_u8).is_empty());
/// assert!(!(3_u8..=3_u8).is_empty());
/// assert!( (3_u8..=2_u8).is_empty());
/// ```
#[inline]
fn is_empty(self: @RangeInclusive<T>) -> bool {
@self.start > @self.end
}
}
impl RangeInclusiveDebug<
T, impl TDebug: crate::fmt::Debug<T>,
> of crate::fmt::Debug<RangeInclusive<T>> {
fn fmt(
self: @RangeInclusive<T>, ref f: crate::fmt::Formatter,
) -> Result<(), crate::fmt::Error> {
self.start.fmt(ref f)?;
write!(f, "..=")?;
self.end.fmt(ref f)?;
Ok(())
}
}
impl RangeInclusiveIteratorImpl<
T, +One<T>, +Add<T>, +Copy<T>, +Drop<T>, +PartialEq<T>, +PartialOrd<T>,
> of Iterator<RangeInclusiveIterator<T>> {
type Item = T;
fn next(ref self: RangeInclusiveIterator<T>) -> Option<T> {
if self.exhausted {
return None;
}
let current = self.cur;
// If this is the last element, mark as exhausted for next iteration
if current == self.end {
self.exhausted = true;
return Some(current);
}
// We know current < self.end here, because the iterator is not exhausted
self.cur = current + One::one();
Some(current)
}
}
pub impl RangeInclusiveIntoIterator<
T, +One<T>, +Add<T>, +Copy<T>, +Drop<T>, +PartialEq<T>, +PartialOrd<T>,
> of IntoIterator<RangeInclusive<T>> {
type IntoIter = RangeInclusiveIterator<T>;
fn into_iter(self: RangeInclusive<T>) -> Self::IntoIter {
let exhausted = self.start > self.end;
Self::IntoIter { cur: self.start, end: self.end, exhausted }
}
}
// Sierra optimization.
mod internal {
use core::internal::OptionRev;
use core::iter::Iterator;
pub extern type IntRange<T>;
impl IntRangeCopy<T> of Copy<IntRange<T>>;
impl IntRangeDrop<T> of Drop<IntRange<T>>;
pub extern fn int_range_try_new<T>(
x: T, y: T,
) -> Result<IntRange<T>, IntRange<T>> implicits(core::RangeCheck) nopanic;
pub extern fn int_range_pop_front<T>(range: IntRange<T>) -> OptionRev<(IntRange<T>, T)> nopanic;
impl IntRangeIteratorImpl<T, +Copy<T>, +Drop<T>> of Iterator<IntRange<T>> {
type Item = T;
fn next(ref self: IntRange<T>) -> Option<T> {
match int_range_pop_front(self) {
OptionRev::None => None,
OptionRev::Some((new_range, value)) => {
self = new_range;
Some(value)
},
}
}
}
}
/// Marker trait to enable using the Sierra libfuncs for integer range iteration (`IntRange`).
trait SierraIntRangeSupport<T>;
impl SierraIntRangeSupportU8 of SierraIntRangeSupport<u8>;
impl SierraIntRangeSupportU16 of SierraIntRangeSupport<u16>;
impl SierraIntRangeSupportU32 of SierraIntRangeSupport<u32>;
impl SierraIntRangeSupportU64 of SierraIntRangeSupport<u64>;
impl SierraIntRangeSupportU128 of SierraIntRangeSupport<u128>;
impl SierraIntRangeSupportI8 of SierraIntRangeSupport<i8>;
impl SierraIntRangeSupportI16 of SierraIntRangeSupport<i16>;
impl SierraIntRangeSupportI32 of SierraIntRangeSupport<i32>;
impl SierraIntRangeSupportI64 of SierraIntRangeSupport<i64>;
impl SierraIntRangeSupportI128 of SierraIntRangeSupport<i128>;
impl SierraRangeIntoIterator<
T, +Copy<T>, +Drop<T>, +SierraIntRangeSupport<T>,
> of IntoIterator<Range<T>> {
type IntoIter = internal::IntRange<T>;
fn into_iter(self: Range<T>) -> Self::IntoIter {
match internal::int_range_try_new(self.start, self.end) {
Ok(range) => range,
Err(range) => range,
}
}
}