Struct Circular 

pub struct Circular<'a, T> { /* private fields */ }

A borrowed view of a slice as a circular sequence.

Carries a (slice, offset, reflected) triple. Every operation routes through a single index-mapping function, so the algebra stays consistent however the view was constructed.

The type is Copy and trivially cheap to pass by value.

Examples

use ring_seq::AsCircular;

let ring = [10, 20, 30];
let c = ring.circular();
assert_eq!(c.len(), 3);
assert_eq!(*c.apply(4), 20); // wraps

Implementations

impl<'a, T> Circular<'a, T>

pub fn len(self) -> usize

Number of elements in the underlying ring.

pub fn is_empty(self) -> bool

Returns true if the ring has no elements.

pub fn apply(self, i: isize) -> &'a T

Returns the element at the (possibly negative, possibly out-of-bounds) circular index i.

Panics

Panics if the ring is empty.

Examples

use ring_seq::AsCircular;

let r = [10, 20, 30].circular();
assert_eq!(*r.apply(0), 10);
assert_eq!(*r.apply(3), 10);    // wraps forward
assert_eq!(*r.apply(-1), 30);   // wraps backward

pub fn iter(self) -> CircularIter<'a, T>

Returns an iterator yielding the elements of this view in order.

The iterator is ExactSizeIterator and FusedIterator.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3].circular();
let collected: Vec<_> = r.iter().copied().collect();
assert_eq!(collected, vec![1, 2, 3]);

pub fn start_at(self, i: isize) -> Circular<'a, T>

Returns a view whose position 0 is the element at circular index i.

Equivalent to rotate_left(i). All other reindexed-view methods are defined in terms of this one.

Examples

use ring_seq::AsCircular;

let r = [10, 20, 30, 40].circular();
let v: Vec<_> = r.start_at(2).iter().copied().collect();
assert_eq!(v, vec![30, 40, 10, 20]);

pub fn rotate_left(self, step: isize) -> Circular<'a, T>

Shifts the view left by step positions. Position 0 of the result is what was at position step of self.

step may be negative (delegates to rotate_right) and may exceed len (wraps).

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4].circular();
let v: Vec<_> = r.rotate_left(1).iter().copied().collect();
assert_eq!(v, vec![2, 3, 4, 1]);

pub fn rotate_right(self, step: isize) -> Circular<'a, T>

Shifts the view right by step positions. Position 0 of the result is what was at position -step of self.

step may be negative (delegates to rotate_left) and may exceed len (wraps).

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4].circular();
let v: Vec<_> = r.rotate_right(1).iter().copied().collect();
assert_eq!(v, vec![4, 1, 2, 3]);

pub fn reflect_at(self, i: isize) -> Circular<'a, T>

Reflects the view around position i.

Position 0 of the result is the element at position i; subsequent positions walk backward from there. Flips the reflected bit of the view (a second reflection at the same index recovers the original).

Examples

use ring_seq::AsCircular;

let r = ['a', 'b', 'c', 'd'].circular();
let v: Vec<_> = r.reflect_at(0).iter().copied().collect();
assert_eq!(v, vec!['a', 'd', 'c', 'b']);

pub fn slice(self, from: isize, to: isize) -> CircularIter<'a, T>

Returns an iterator over the circular range [from, to).

The range is taken in the view’s forward direction starting at the element with circular index from. Yields max(to - from, 0) elements, wrapping around the ring as many times as needed; an empty range produces an empty iterator.

Examples

use ring_seq::AsCircular;

let r = [0, 1, 2, 3, 4].circular();
let v: Vec<_> = r.slice(2, 7).copied().collect();
assert_eq!(v, vec![2, 3, 4, 0, 1]);

pub fn take_while<P>(self, pred: P, from: isize) -> impl Iterator<Item = &'a T>

where P: FnMut(&T) -> bool,

Returns an iterator yielding elements from circular index from while pred holds, stopping at the first element that fails (or after one full lap).

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4, 5].circular();
let v: Vec<_> = r.take_while(|&x| x < 4, 0).copied().collect();
assert_eq!(v, vec![1, 2, 3]);

pub fn drop_while<P>(self, pred: P, from: isize) -> impl Iterator<Item = &'a T>

where P: FnMut(&T) -> bool,

Returns an iterator that skips elements from circular index from while pred holds, then yields the rest of the lap (one full rotation maximum).

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4, 5].circular();
let v: Vec<_> = r.drop_while(|&x| x < 4, 0).copied().collect();
assert_eq!(v, vec![4, 5]);

pub fn enumerate(self, from: isize) -> Enumerate<'a, T>

Returns an iterator yielding (element, ring_index) pairs starting at circular index from and going around once.

Unlike Iterator::enumerate, the second element of each pair is the element’s index in the underlying ring (already wrapped to [0, len)), not the iteration count.

Examples

use ring_seq::AsCircular;

let r = ['a', 'b', 'c'].circular();
let v: Vec<_> = r.enumerate(1).map(|(&c, i)| (c, i)).collect();
assert_eq!(v, vec![('b', 1), ('c', 2), ('a', 0)]);

pub fn rotations(self) -> Rotations<'a, T>

Returns an iterator yielding each rotation of this view as a fresh Circular.

For a non-empty ring of length n the iterator yields n items; for an empty ring it yields one (empty) item. The reflected bit of self is preserved by every yielded rotation.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3].circular();
let starts: Vec<i32> = r.rotations().map(|v| *v.apply(0)).collect();
assert_eq!(starts, vec![1, 2, 3]);

pub fn reflections(self) -> Reflections<'a, T>

Returns an iterator yielding the view and its reflection at position 0.

For a non-empty ring the iterator yields two items; for an empty ring it yields one. The first item is always self.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4].circular();
let count = r.reflections().count();
assert_eq!(count, 2);

pub fn reversions(self) -> Reversions<'a, T>

Returns an iterator yielding the view and its reverse.

“Reverse” here means walking the ring in the opposite direction starting from position len - 1 — equivalent to reflect_at(-1).

For a non-empty ring the iterator yields two items; for an empty ring it yields one.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3].circular();
let last: Vec<_> = r.reversions()
    .map(|v| v.iter().copied().collect::<Vec<_>>())
    .collect();
assert_eq!(last, vec![vec![1, 2, 3], vec![3, 2, 1]]);

pub fn rotations_and_reflections(self) -> RotationsAndReflections<'a, T>

Returns an iterator yielding every rotation of this view followed by every rotation of its reflection at position 0.

For a non-empty ring of length n the iterator yields 2n items; for an empty ring it yields one.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3].circular();
assert_eq!(r.rotations_and_reflections().count(), 6);

pub fn windows(self, size: usize) -> Windows<'a, T>

Returns an iterator yielding every circular window of length size (step 1) as a CircularIter.

For a non-empty ring of length n the iterator yields n windows; for an empty ring it yields no windows.

Panics

Panics if size is zero.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4].circular();
let windows: Vec<Vec<i32>> = r
    .windows(2)
    .map(|w| w.copied().collect())
    .collect();
assert_eq!(windows, vec![vec![1, 2], vec![2, 3], vec![3, 4], vec![4, 1]]);

pub fn index_from(self, i: isize) -> usize

Normalizes a circular index to [0, len).

Uses Euclidean remainder so that negative indices wrap correctly.

Panics

Panics if the ring is empty.

Examples

use ring_seq::AsCircular;

let r = [10, 20, 30].circular();
assert_eq!(r.index_from(0), 0);
assert_eq!(r.index_from(4), 1);
assert_eq!(r.index_from(-1), 2);

pub fn is_rotation_of(self, other: &[T]) -> bool

where T: PartialEq,

Returns true if other is some rotation of this view.

pub fn is_reflection_of(self, other: &[T]) -> bool

where T: PartialEq,

Returns true if other equals this view or its reflection at position 0.

pub fn is_reversion_of(self, other: &[T]) -> bool

where T: PartialEq,

Returns true if other equals this view or its reverse.

pub fn is_rotation_or_reflection_of(self, other: &[T]) -> bool

where T: PartialEq,

Returns true if other is any rotation of this view or of its reflection at position 0.

pub fn rotation_offset(self, other: &[T]) -> Option<usize>

where T: PartialEq,

Returns the starting offset at which other matches this view as a rotation, or None if no such offset exists.

pub fn hamming_distance(self, other: &[T]) -> usize

where T: PartialEq,

Counts positions where this view and other differ.

Panics

Panics if the lengths differ.

pub fn min_rotational_hamming_distance(self, other: &[T]) -> usize

where T: PartialEq,

Minimum Hamming distance over all rotations of this view against other.

Panics

Panics if the lengths differ.

Examples found in repository

examples/bench_min_rotational_hamming.rs (line 37)

fn bench_case(label: &str, n: usize, iters: u64, a: &[u32], b: &[u32]) {
    // warm-up
    for _ in 0..(iters / 10).max(1) {
        black_box(a.circular().min_rotational_hamming_distance(black_box(b)));
    }
    let start = Instant::now();
    let mut acc: usize = 0;
    for _ in 0..iters {
        acc = acc.wrapping_add(black_box(
            a.circular().min_rotational_hamming_distance(black_box(b)),
        ));
    }
    let elapsed = start.elapsed();
    let ns_per_op = elapsed.as_nanos() as f64 / iters as f64;
    println!(
        "{:<10} n={:<5} iters={:<10} total={:>10.3?} ns/op={:>12.0} (acc={})",
        label, n, iters, elapsed, ns_per_op, acc
    );
}

pub fn contains_slice(self, needle: &[T]) -> bool

where T: PartialEq,

Returns true if needle appears as a contiguous (possibly wrapping) substring of this view.

An empty needle is always contained.

pub fn index_of_slice(self, needle: &[T], from: isize) -> Option<usize>

where T: PartialEq,

Returns the starting circular index at which needle appears, or None if it does not. Searches forward from from.

pub fn rotational_symmetry(self) -> usize

where T: PartialEq,

Returns the rotational symmetry order: n / smallest_period, where the smallest period is the smallest divisor d of n such that apply(i) == apply(i + d) for all i. Empty and single-element rings have rotational symmetry 1.

pub fn symmetry(self) -> usize

where T: PartialEq,

Returns an iterator over the shifts at which this view equals its own reverse rotated by that shift — i.e., the count of reflectional symmetry axes (without allocating the indices themselves).

Use symmetry_indices (alloc-gated) if you need the actual indices.

pub fn chunks(self, size: usize) -> Windows<'a, T>

Returns an iterator yielding ceil(len / size) non-overlapping circular chunks of length size as CircularIters.

When size does not divide len, the final chunk wraps across the seam so every chunk has exactly size elements. An empty ring yields no chunks.

Panics

Panics if size is zero.

Examples

use ring_seq::AsCircular;

let r = [1, 2, 3, 4, 5].circular();
let chunks: Vec<Vec<i32>> = r
    .chunks(2)
    .map(|c| c.copied().collect())
    .collect();
// ceil(5/2) = 3 chunks; the last one wraps
assert_eq!(chunks, vec![vec![1, 2], vec![3, 4], vec![5, 1]]);

impl<'a, T> Circular<'a, T>

pub fn to_vec(self) -> Vec<T>

where T: Clone,

Materializes this view as a Vec<T>. Requires T: Clone.

pub fn canonical_index(self) -> usize

where T: Ord,

Returns the starting offset of the lexicographically smallest rotation of this view (Booth’s O(n) algorithm).

Single-element and empty views return 0.

pub fn canonical(self) -> Vec<T>

where T: Clone + Ord,

Returns the canonical (lexicographically smallest) rotation of this view as a Vec<T>. Requires T: Clone + Ord.

pub fn bracelet(self) -> Vec<T>

where T: Clone + Ord,

Returns the bracelet form: the lexicographically smallest among canonical() and reflect_at(0).canonical(). Requires T: Clone + Ord.

pub fn symmetry_indices(self) -> Vec<usize>

where T: PartialEq,

Returns the shifts k in [0, n) for which this view equals its own reverse rotated by k. Each shift corresponds to one axis of reflectional symmetry.

pub fn reflectional_symmetry_axes(self) -> Vec<(AxisLocation, AxisLocation)>

where T: PartialEq,

Returns the axes of reflectional symmetry as (AxisLocation, AxisLocation) pairs (each axis hits the ring in two locations).

Trait Implementations

impl<T> Clone for Circular<'_, T>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Circular<'_, T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Copy for Circular<'_, T>