### 11 releases

Uses old Rust 2015

0.2.9 | May 24, 2015 |
---|---|

0.2.8 | Apr 3, 2015 |

0.2.7 | Feb 23, 2015 |

0.2.4 | Jan 9, 2015 |

0.1.0 | Nov 16, 2014 |

#**2903** in Rust patterns

**58** downloads per month

Used in **5** crates
(4 directly)

**MIT/Apache**

47KB

841 lines

Strided slices.

This library provides two types

and `Strided`

as
generalised forms of `MutStrided`

and `&``[`T`]`

respectively, where the
elements are regularly spaced in memory, but not necessarily
immediately adjacently.`&``mut` `[`T`]`

###
`lib.rs`

:

Strided slices.

This library provides two types

and `Stride`

as
generalised forms of `MutStride`

and `&``[`T`]`

respectively, where the
elements are regularly spaced in memory, but not necessarily
immediately adjacently.`&``mut` `[`T`]`

For example, given an underlying array

, the
elements `[``1``,` `2``,` `3``,` `4``,` `5``]`

are a strided slice with stride 2, and
`[``1``,` `3``,` `5``]`

has stride 3. Any slice can be regarded as a strided slice
with stride 1.`[``1``,` `4``]`

This provides functionality through which one can safely and
efficiently manipulate every

th element of a slice (even a
mutable one) as close as possible to it being a conventional
slice. This releases one from worries about stride bookkeeping,
aliasing of `n`

or any `&``mut`

code.`unsafe`

# Quick start

The work-horse functions are

and
`.``substrides``(`n`)`

, which return an iterator across a series of
`.``substrides_mut``(`n`)`

new strided slices (shared and mutable, respectively), each of
which points to every `n`

th element, and each of which starts at
the next successive offset. For example, the following has
`n`

.`n = 3`

`use` `strided``::`MutStride`;`
`let` `mut` v `=` `[``1``u8``,` `2``,` `3``,` `4``,` `5``]``;`
`let` `mut` all `=` `MutStride``::`new`(``&``mut` v`)``;`
`let` `mut` substrides `=` all`.``substrides_mut``(``3``)``;`
`let` a `=` substrides`.``next``(``)``.``unwrap``(``)``;`
`let` b `=` substrides`.``next``(``)``.``unwrap``(``)``;`
`let` c `=` substrides`.``next``(``)``.``unwrap``(``)``;`
`assert!``(`substrides`.``next``(``)``.``is_none``(``)``)``;` `//` there was exactly 3.
`assert_eq!``(`a`,` `MutStride``::`new`(``&``mut` `[``1``,` `4``]``)``)``;`
`assert_eq!``(`b`,` `MutStride``::`new`(``&``mut` `[``2``,` `5``]``)``)``;`
`assert_eq!``(`c`,` `MutStride``::`new`(``&``mut` `[``3``]``)``)``;`

The common case of

has an abbreviation `n = 2`

`substrides2`

(resp. `substrides2_mut`

), which takes the liberty of returns a
tuple rather than an iterator to make direct destructuring
work. Continuing with the values above, `left`

and `right`

point
to alternate elements, starting at index `0`

and `1`

of their
parent slice respectively.`let` `(`left`,` right`)` `=` all`.``substrides2_mut``(``)``;`
`assert_eq!``(`left`,` `MutStride``::`new`(``&``mut` `[``1``,` `3``,` `5``]``)``)``;`
`assert_eq!``(`right`,` `MutStride``::`new`(``&``mut` `[``2``,` `4``]``)``)``;`

A lot of the conventional slice functionality is available, such as indexing, iterators and slicing.

`let` `(``mut` left`,` right`)` `=` all`.``substrides2_mut``(``)``;`
`assert_eq!``(`left`[``2``]``,` `5``)``;`
`assert!``(`right`.``get``(``10``)``.``is_none``(``)``)``;` `//` out of bounds
left`[``2``]` `+=` `10``;`
`match` left`.``get_mut``(``0``)` `{`
`Some``(`val`)` `=>` `*`val `-=` `1``,`
`None` `=>` `{``}`
`}`
`assert_eq!``(`right`.``iter``(``)``.``fold``(``0``,` `|``sum``,` `a``|` `sum ``+` `*`a`)``,` `2` `+` `4``)``;`
`for` val `in` left`.``iter_mut``(``)` `{`
`*`val `/=` `2`
`}`

## Ownership and `reborrow`

`reborrow`

has a method `MutStride`

which has signature`reborrow`

`impl``<``'a`, T`>`` ``MutStride``<``'a`, T`>` `{`
`pub` `fn` `reborrow``<``'b``>``(``&``'b` `mut` `self``)`` ``->` `MutStride``<``'b`, T`>` `{` `...` `}`
`}`

That is, it allows temporarily viewing a strided slices as one
with a shorter lifetime. This method is key because many of the
methods on

take `MutStride`

by-value and so consume
ownership... which is rather unfortunate if one wants to use a
strided slice multiple times.`self`

The temporary returned by

can be used with the
consuming methods, which allows the parent slice to continuing
being used after that temporary has disappeared. For example, all
of the splitting and slicing methods on `reborrow`

consume
ownership, and so `MutStride`

is necessary there to continue using,
in this case, `reborrow`

.`left`

`let` `(``mut` left`,` right`)` `=` all`.``substrides2_mut``(``)``;`
`assert_eq!``(`left`.``reborrow``(``)``.``slice_mut``(``1``,` `3``)``,` `MutStride``::`new`(``&``mut` `[``3``,` `5``]``)``)``;`
`assert_eq!``(`left`.``reborrow``(``)``.``slice_from_mut``(``2``)``,` `MutStride``::`new`(``&``mut` `[``5``]``)``)``;`
`assert_eq!``(`left`.``reborrow``(``)``.``slice_to_mut``(``2``)``,` `MutStride``::`new`(``&``mut` `[``1``,` `3``]``)``)``;`
`//` no reborrow:
`assert_eq!``(`right`.``split_at_mut``(``1``)``,`
`(``MutStride``::`new`(``&``mut` `[``2``]``)``,` `MutStride``::`new`(``&``mut` `[``4``]``)``)``)``;`
`//` println!("{}", right); // error: use of moved value `right`.

These contortions are necessary to ensure that

s cannot
alias, while still maintaining flexibility: leaving elements with
the maximum possible lifetime (i.e. that of the non-strided slices
which they lie in). Theoretically they are necessary with
`&``mut`

too, but the compiler inserts implicit reborrows and so
one rarely needs to do them manually.`&``mut` `[``]`

In practice, one should only need to insert

s if the
compiler complains about the use of a moved value.`reborrow`

The shared

is equivalent to `Stride`

and only handles `&``[``]`

references, making ownership transfer and `&`

unnecessary,
so all its methods act identically to those on `reborrow`

.`&``[``]`

# Example

The fast Fourier transform
(FFT) is a
signal processing algorithm that performs a discrete Fourier
transform (DFT) of length

in `n`

time. A DFT breaks a
waveform into the sum of sines and cosines, and is an important
part of many other algorithms due to certain nice properties of
the Fourier transform.`O (n log n)`

The first FFT algorithm was the Cooley-Tukey algorithm. The decimation-in-time variant works by computing the FFT of equal-length subarrays of equally spaced elements and then combining these together into the desired result. This sort of spacing is exactly the striding provided by this library, and hence this library can be used to create an FFT algorithm in a very natural way.

Below is an implementation of the radix-2 case, that is, when the
length

is a power of two. In this case, only two strided
subarrays are necessary: exactly the alternating ones provided by
`n`

. Note the use of `substrides2`

to allow `reborrow`

and
`start`

to be used for the recursive `end`

calls and then again
later in the loop.`fft`

`extern` `crate` strided`;`
`extern` `crate` num`;` `//` https://github.com/rust-lang/num
`use` `std``::`f64`;`
`use` `num``::``complex``::``{`Complex`,` Complex64`}``;`
`use` `strided``::``{`MutStride`,` Stride`}``;`
`///` Writes the forward DFT of `input` to `output`.
`fn` `fft``(``input``:` `Stride``<`Complex64`>`, `mut` `output``:` `MutStride``<`Complex64`>``)`` ``{`
`//` check it's a power of two.
`assert!``(`input`.``len``(``)` `==` output`.``len``(``)` `&&` input`.``len``(``)``.``count_ones``(``)` `==` `1``)``;`
`//` base case: the DFT of a single element is itself.
`if` input`.``len``(``)` `==` `1` `{`
output`[``0``]` `=` input`[``0``]``;`
`return`
`}`
`//` split the input into two arrays of alternating elements ("decimate in time")
`let` `(`evens`,` odds`)` `=` input`.``substrides2``(``)``;`
`//` break the output into two halves (front and back, not alternating)
`let` `(``mut` start`,` `mut` end`)` `=` output`.``split_at_mut``(`input`.``len``(``)` `/` `2``)``;`
`//` recursively perform two FFTs on alternating elements of the input, writing the
`//` results into the first and second half of the output array respectively.
`fft``(`evens`,` start`.``reborrow``(``)``)``;`
`fft``(`odds`,` end`.``reborrow``(``)``)``;`
`//` exp(-2πi/N)
`let` twiddle `=` `Complex``::`from_polar`(``&``1.``0``,` `&``(``-``2.``0` `*` `f64``::``consts``::``PI` `/` input`.``len``(``)` `as` `f64``)``)``;`
`let` `mut` factor `=` `Complex``::`new`(``1.``,` `0.``)``;`
`//` combine the subFFTs with the relations:
`//` X_k = E_k + exp(-2πki/N) * O_k
`//` X_{k+N/2} = E_k - exp(-2πki/N) * O_k
`for` `(`even`,` odd`)` `in` start`.``iter_mut``(``)``.``zip``(`end`.``iter_mut``(``)``)` `{`
`let` twiddled `=` factor `*` `*`odd`;`
`let` e `=` `*`even`;`
`*`even `=` e `+` twiddled`;`
`*`odd `=` e `-` twiddled`;`
factor `=` factor `*` twiddle`;`
`}`
`}`
`fn` `main``(``)`` ``{`
`let` a `=` `[``Complex``::`new`(``2.``,` `0.``)``,` `Complex``::`new`(``1.``,` `0.``)``,`
`Complex``::`new`(``2.``,` `0.``)``,` `Complex``::`new`(``1.``,` `0.``)``]``;`
`let` `mut` b `=` `[``Complex``::`new`(``0.``,` `0.``)``;` `4``]``;`
`fft``(``Stride``::`new`(``&`a`)``,` `MutStride``::`new`(``&``mut` b`)``)``;`
`println!``(``"`forward: `{:?}` -> `{:?}``"``,` `&`a`,` `&`b`)``;`
`}`

The above definitely has complexity

, but it has a
much larger constant factor than an optimised library like
FFTW. (Strictly speaking `O (n log n)`

`output`

does not
need to be a strided slice, since it is never split into
alternating elements.)