//! Licensed under the Apache License, Version 2.0
//! http://www.apache.org/licenses/LICENSE-2.0 or the MIT license
//! http://opensource.org/licenses/MIT, at your
//! option. This file may not be copied, modified, or distributed
//! except according to those terms.
use std::fmt;
use std::marker;
use std::mem;
use std::ops::{Index, IndexMut};
/// Stride is similar to the slice iterator, but with a certain number of steps
/// (the stride) skipped per iteration.
///
/// Stride does not support zero-sized types for `A`.
///
/// Iterator element type is `&'a A`.
pub struct Stride<'a, A: 'a> {
/// base pointer -- does not change during iteration
begin: *const A,
/// current offset from begin
offset: isize,
/// offset where we end (exclusive end).
end: isize,
stride: isize,
life: marker::PhantomData<&'a A>,
}
impl<'a, A> Copy for Stride<'a, A> {}
unsafe impl<'a, A> Send for Stride<'a, A> where A: Send {}
unsafe impl<'a, A> Sync for Stride<'a, A> where A: Sync {}
/// StrideMut is like Stride, but with mutable elements.
///
/// Iterator element type is `&'a mut A`.
pub struct StrideMut<'a, A: 'a> {
begin: *mut A,
offset: isize,
end: isize,
stride: isize,
life: marker::PhantomData<&'a mut A>,
}
unsafe impl<'a, A> Send for StrideMut<'a, A> where A: Send {}
unsafe impl<'a, A> Sync for StrideMut<'a, A> where A: Sync {}
impl<'a, A> Stride<'a, A>
{
/// Create a Stride iterator from a raw pointer.
pub unsafe fn from_ptr_len(begin: *const A, nelem: usize, stride: isize) -> Stride<'a, A>
{
Stride {
begin: begin,
offset: 0,
end: stride * nelem as isize,
stride: stride,
life: marker::PhantomData,
}
}
}
impl<'a, A> StrideMut<'a, A>
{
/// Create a StrideMut iterator from a raw pointer.
pub unsafe fn from_ptr_len(begin: *mut A, nelem: usize, stride: isize) -> StrideMut<'a, A>
{
StrideMut {
begin: begin,
offset: 0,
end: stride * nelem as isize,
stride: stride,
life: marker::PhantomData,
}
}
}
fn div_rem(x: usize, d: usize) -> (usize, usize)
{
(x / d, x % d)
}
macro_rules! stride_impl {
(struct $name:ident -> $slice:ty, $getptr:ident, $ptr:ty, $elem:ty) => {
impl<'a, A> $name<'a, A>
{
/// Create Stride iterator from a slice and the element step count.
///
/// If `step` is negative, start from the back.
///
/// ## Example
///
/// ```
/// use itertools::Stride;
///
/// let xs = [0, 1, 2, 3, 4, 5];
///
/// let front = Stride::from_slice(&xs, 2);
/// assert_eq!(front[0], 0);
/// assert_eq!(front[1], 2);
///
/// let back = Stride::from_slice(&xs, -2);
/// assert_eq!(back[0], 5);
/// assert_eq!(back[1], 3);
/// ```
///
/// **Panics** if values of type `A` are zero-sized. <br>
/// **Panics** if `step` is 0.
#[inline]
pub fn from_slice(xs: $slice, step: isize) -> $name<'a, A>
{
assert!(mem::size_of::<A>() != 0);
let ustep = if step < 0 { -step } else { step } as usize;
let nelem = if ustep <= 1 {
xs.len()
} else {
let (d, r) = div_rem(xs.len(), ustep);
d + if r > 0 { 1 } else { 0 }
};
let mut begin = xs. $getptr ();
unsafe {
if step > 0 {
$name::from_ptr_len(begin, nelem, step)
} else {
if nelem != 0 {
begin = begin.offset(xs.len() as isize - 1)
}
$name::from_ptr_len(begin, nelem, step)
}
}
}
/// Create Stride iterator from an existing Stride iterator
///
/// **Panics** if `step` is 0.
#[inline]
pub fn from_stride(mut it: $name<'a, A>, mut step: isize) -> $name<'a, A>
{
assert!(step != 0);
if step < 0 {
it.swap_ends();
step = -step;
}
let len = (it.end - it.offset) / it.stride;
let newstride = it.stride * step;
let (d, r) = div_rem(len as usize, step as usize);
let len = d + if r > 0 { 1 } else { 0 };
unsafe {
$name::from_ptr_len(it.begin, len, newstride)
}
}
/// Swap the begin and end and reverse the stride,
/// in effect reversing the iterator.
#[inline]
pub fn swap_ends(&mut self) {
let len = (self.end - self.offset) / self.stride;
if len > 0 {
unsafe {
let endptr = self.begin.offset((len - 1) * self.stride);
*self = $name::from_ptr_len(endptr, len as usize, -self.stride);
}
}
}
/// Return the number of elements in the iterator.
#[inline]
pub fn len(&self) -> usize {
((self.end - self.offset) / self.stride) as usize
}
}
impl<'a, A> Iterator for $name<'a, A>
{
type Item = $elem;
#[inline]
fn next(&mut self) -> Option<$elem>
{
if self.offset == self.end {
None
} else {
unsafe {
let elt: $elem =
mem::transmute(self.begin.offset(self.offset));
self.offset += self.stride;
Some(elt)
}
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
}
impl<'a, A> DoubleEndedIterator for $name<'a, A>
{
#[inline]
fn next_back(&mut self) -> Option<$elem>
{
if self.offset == self.end {
None
} else {
unsafe {
self.end -= self.stride;
let elt = mem::transmute(self.begin.offset(self.end));
Some(elt)
}
}
}
}
impl<'a, A> ExactSizeIterator for $name<'a, A> { }
impl<'a, A> Index<usize> for $name<'a, A>
{
type Output = A;
/// Return a reference to the element at a given index.
///
/// **Panics** if the index is out of bounds.
fn index<'b>(&'b self, i: usize) -> &'b A
{
assert!(i < self.len());
unsafe {
let ptr = self.begin.offset(self.offset + self.stride * (i as isize));
mem::transmute(ptr)
}
}
}
impl<'a, A> fmt::Debug for $name<'a, A>
where A: fmt::Debug
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result
{
try!(write!(f, "["));
for i in 0..self.len() {
if i != 0 {
try!(write!(f, ", "));
}
try!(write!(f, "{:?}", (*self)[i]));
}
write!(f, "]")
}
}
}
}
stride_impl!{struct Stride -> &'a [A], as_ptr, *const A, &'a A}
stride_impl!{struct StrideMut -> &'a mut [A], as_mut_ptr, *mut A, &'a mut A}
impl<'a, A> Clone for Stride<'a, A>
{
fn clone(&self) -> Stride<'a, A>
{
*self
}
}
impl<'a, A> IndexMut<usize> for StrideMut<'a, A>
{
/// Return a mutable reference to the element at a given index.
///
/// **Panics** if the index is out of bounds.
fn index_mut<'b>(&'b mut self, i: usize) -> &'b mut A
{
assert!(i < self.len());
unsafe {
let ptr = self.begin.offset(self.offset + self.stride * (i as isize));
mem::transmute(ptr)
}
}
}