ringSeq-root/io.github.scala_tessella.ring_seq/NecklaceOps

NecklaceOps

io.github.scala_tessella.ring_seq.NecklaceOps

See theNecklaceOps companion object

trait NecklaceOps extends ComparingOps

Provides canonical-form operations for a Seq considered circular.

Attributes

Companion: object
Graph
Supertypes: trait ComparingOps

trait IteratingOps

trait SlicingOps

trait TransformingOps

trait IndexingOps

class Object

trait Matchable

class Any
Show all
Known subtypes: object RingSeq

Members list

Type members

Inherited types

For improved readability, the index of a Seq.

Attributes

Inherited from:: IndexingOps

For improved readability, the index of a circular Seq.

Attributes

Note: any value is a valid index, provided that Seq is not empty
Inherited from:: IndexingOps

Extensions

extension [A, CC <: (SeqOps)](ring: CC[A])

The lexicographically smallest representative under both rotation and reflection (bracelet canonical form).

Two circular sequences belong to the same bracelet equivalence class iff their bracelet forms are equal — useful for problems where mirror images are considered identical.

Attributes

Returns: the smaller of canonical and reflectAt().canonical, by lexicographic ordering.

The lexicographically smallest rotation of this circular sequence (necklace canonical form).

Two circular sequences are rotations of each other iff their canonical forms are equal, making this useful for hashing / deduplicating equivalent rings.

Attributes

Example

Seq(2, 0, 1).canonical // Seq(0, 1, 2)

The starting index of the lexicographically smallest rotation (Booth's algorithm, O(n)).

Attributes

Returns: the index in [0, ring.size) such that ring.startAt(canonicalIndex) is the lex-smallest of all rotations. Returns 0 for empty or single-element sequences.

Inherited extensions

extension [A, CC <: (SeqOps)](ring: CC[A])

Tests whether this circular sequence contains a given sequence as a slice.

Value parameters

that: the sequence to test

Attributes

Returns

true if this circular sequence contains a slice with the same elements as ''that'', otherwise false.

Example

Seq(0, 1, 2).containsSliceO(Seq(2, 0, 1, 2, 0)) // true

Inherited from:

SlicingOps

Drops the longest prefix of elements starting at some circular index that satisfy a predicate.

Value parameters

from: IndexO
p: the predicate used to test elements

Attributes

Example

Seq(0, 1, 2, 3, 4).dropWhileO(_ < 3, 1) // Seq(3, 4, 0)

Inherited from:

SlicingOps

Finds first index after or at a start index where this circular sequence contains a given sequence as a slice.

Value parameters

from: IndexO
that: the sequence to test

Attributes

Returns

the first index >= ''from'' such that the elements of this circular sequence starting at this index match the elements of sequence ''that'', or -1 if no such subsequence exists.

Example

Seq(0, 1, 2).indexOfSliceO(Seq(2, 0, 1, 2, 0)) // 2

Inherited from:

SlicingOps

Finds last index before or at a given end index where this circular sequence contains a given sequence as a slice.

Value parameters

end: IndexO
that: the sequence to test

Attributes

Returns

the last index <= ''end'' such that the elements of this circular sequence starting at this index match the elements of sequence ''that'', or -1 if no such subsequence exists.

Example

Seq(0, 1, 2, 0, 1, 2).lastIndexOfSliceO(Seq(2, 0)) // 5

Inherited from:

SlicingOps

Computes the length of the longest segment that starts from some circular index and whose elements all satisfy some predicate.

Value parameters

from: IndexO
p: the predicate used to test elements

Attributes

Returns

the length of the longest segment of this sequence starting from circular index ''from'' such that every element of the segment satisfies the predicate ''p''

Example

Seq(0, 1, 2).segmentLengthO(_ % 2 == 0, 2) // 2

Inherited from:

SlicingOps

Selects an interval of elements.

Value parameters

from: IndexO
until: IndexO

Attributes

Returns

a sequence containing the elements greater than or equal to circular index ''from'' extending up to (but not including) circular index ''until'' of this sequence.

Note

a slice of a circular sequence can be bigger than the size of the elements in the sequence.

Example

Seq(0, 1, 2).sliceO(-1, 4) // Seq(2, 0, 1, 2, 0)

Inherited from:

SlicingOps

Splits this circular sequence into a prefix/suffix pair at the first element starting from some circular index that does not satisfy the predicate.

Value parameters

from: IndexO
p: the predicate used to test elements

Attributes

Returns

a pair (takeWhileO(p, from), dropWhileO(p, from)).

Example

Seq(0, 1, 2, 3, 4).spanO(_ < 3, 1) // (Seq(1, 2), Seq(3, 4, 0))

Inherited from:

SlicingOps

Selects the longest prefix of elements starting at some circular index that satisfy a predicate.

Value parameters

from: IndexO
p: the predicate used to test elements

Attributes

Example

Seq(0, 1, 2, 3, 4).takeWhileO(_ < 3, 1) // Seq(1, 2)

Inherited from:

SlicingOps

extension [A, CC <: (SeqOps)](ring: CC[A])

Reflects the sequence to start at some circular index.

Value parameters

i: IndexO

Attributes

Returns

a sequence consisting of all elements reversed and rotated to start at circular index ''i''.

Example

Seq(0, 1, 2).reflectAt() // Seq(0, 2, 1)

Inherited from:

TransformingOps

Rotates the sequence to the left by some steps.

Value parameters

step: the circular distance between each old and new position

Attributes

Returns

a sequence consisting of all elements rotated to the left by ''step'' places. If ''step'' is negative the rotation happens to the right.

Example

Seq(0, 1, 2).rotateLeft(1) // Seq(1, 2, 0)

Inherited from:

TransformingOps

Rotate the sequence to the right by some steps.

Value parameters

step: the circular distance between each new and old position

Attributes

Returns

a sequence consisting of all elements rotated to the right by ''step'' places. If ''step'' is negative the rotation happens to the left.

Example

Seq(0, 1, 2).rotateRight(1) // Seq(2, 0, 1)

Inherited from:

TransformingOps

Rotates the sequence to start at some circular index.

Value parameters

i: IndexO

Attributes

Returns

a sequence consisting of all elements rotated to start at circular index ''i''. It is equivalent to rotateLeft.

Example

Seq(0, 1, 2).startAt(1) // Seq(1, 2, 0)

Inherited from:

TransformingOps

extension [A, CC <: (SeqOps)](ring: CC[A])

Finds the rotation offset that aligns this circular sequence with a given sequence.

Value parameters

that: the sequence to align to

Attributes

Returns

Some(k) such that ring.startAt(k) == that, or None if no rotation matches (or sizes differ).

Example

Seq(0, 1, 2).alignTo(Seq(2, 0, 1)) // Some(2)

Inherited from:

ComparingOps

The number of positions at which corresponding elements differ (Hamming distance).

Value parameters

that: the sequence to compare against, must have the same size

Attributes

Example

Seq(1, 0, 1, 1).hammingDistance(Seq(1, 1, 0, 1)) // 2

Inherited from:

ComparingOps

Tests whether this circular sequence is a reflection of a given sequence.

Value parameters

that: the sequence to test

Attributes

Returns

true if this circular sequence is a reflection of ''that'', otherwise false.

Example

Seq(0, 1, 2).isReflectionOf(Seq(0, 2, 1)) // true

Inherited from:

ComparingOps

Tests whether this circular sequence is a reversion of a given sequence.

Value parameters

that: the sequence to test

Attributes

Returns

true if this circular sequence is a reversion of ''that'', otherwise false.

Example

Seq(0, 1, 2).isReversionOf(Seq(2, 1, 0)) // true

Inherited from:

ComparingOps

Tests whether this circular sequence is a rotation of a given sequence.

Value parameters

that: the sequence to test

Attributes

Returns

true if this circular sequence is a rotation of ''that'', otherwise false.

Example

Seq(0, 1, 2).isRotationOf(Seq(1, 2, 0)) // true

Inherited from:

ComparingOps

Tests whether this circular sequence is a rotation or a reflection of a given sequence.

Value parameters

that: the sequence to test

Attributes

Returns

true if this circular sequence is a rotation or a reflection of ''that'', otherwise false.

Example

Seq(0, 1, 2).isRotationOrReflectionOf(Seq(2, 0, 1)) // true

Inherited from:

ComparingOps

The minimum Hamming distance over all rotations of this circular sequence.

Value parameters

that: the sequence to compare against, must have the same size

Attributes

Returns

0 iff that is a rotation of this, otherwise the smallest number of positional mismatches over any rotation. Useful for "how close are these two rings, up to rotation?".

Example

Seq(1, 0, 1, 1).minRotationalHammingDistance(Seq(1, 1, 0, 1)) // 0

Inherited from:

ComparingOps

extension [A, CC <: (SeqOps)](ring: CC[A])

Partitions this circular sequence into non-overlapping fixed-size blocks.

Unlike standard grouped, the last block wraps across the seam between the last and first elements, so every block has exactly size elements. Produces ceil(n / size) blocks for a ring of size n, and no blocks for an empty ring.

Value parameters

size: the number of elements per block; must be positive

Attributes

Returns

an iterator producing sequences of size ''size''; empty when the ring is empty.

Example

Seq(0, 1, 2, 3, 4).groupedO(2) // Iterator(Seq(0, 1), Seq(2, 3), Seq(4, 0))

Inherited from:

IteratingOps

Computes all the reflections of this circular sequence

Attributes

Returns

An iterator producing the 2 sequences obtained by reflecting this circular sequence, starting from itself, or just itself if empty.

Example

Seq(0, 1, 2).reflections // Iterator(Seq(0, 1, 2), Seq(0, 2, 1))

Inherited from:

IteratingOps

Computes all the reversions of this circular sequence

Attributes

Returns

An iterator producing the 2 sequences obtained by reversing this circular sequence, starting from itself, or just itself if empty.

Example

Seq(0, 1, 2).reversions // Iterator(Seq(0, 1, 2), Seq(2, 1, 0))

Inherited from:

IteratingOps

Computes all the rotations of this circular sequence

Attributes

Returns

An iterator producing all the sequences obtained by rotating this circular sequence, starting from itself and moving one rotation step to the right, or just itself if empty.

Example

Seq(0, 1, 2).rotations // Iterator(Seq(0, 1, 2), Seq(1, 2, 0), Seq(2, 0, 1))

Inherited from:

IteratingOps

Computes all the rotations and reflections of this circular sequence

Attributes

Returns

An iterator producing all the sequences obtained by rotating and reflecting this circular sequence, starting from itself and moving one rotation step to the right, then reflecting and doing the same, or just itself if empty.

Example

Seq(0, 1, 2).rotationsAndReflections // Iterator(Seq(0, 1, 2), Seq(1, 2, 0), Seq(2, 0, 1), Seq(0, 2, 1), Seq(2, 1, 0), Seq(1, 0, 2))

Inherited from:

IteratingOps

Groups elements in fixed size blocks by passing a "sliding window" over them

Value parameters

size: the number of elements per group
step: the distance between the first elements of successive groups

Attributes

Returns

An iterator producing sequences of size ''size''.

Example

Seq(0, 1, 2).slidingO(2) // Iterator(Seq(0, 1), Seq(1, 2), Seq(2, 0))

Inherited from:

IteratingOps

Iterates over the elements paired with their original (circular) index, starting at some circular index.

Value parameters

from: IndexO

Attributes

Returns

an iterator of (element, index) pairs of length ring.size. Indices are in [0, ring.size).

Example

Seq('a', 'b', 'c').zipWithIndexO(1).toList // List(('b', 1), ('c', 2), ('a', 0))

Inherited from:

IteratingOps

extension [A, CC <: (SeqOps)](ring: CC[A])

Gets the element at some circular index.

Value parameters

i: IndexO

Attributes

Throws

java.lang.ArithmeticException

if Seq is empty

Example

Seq(0, 1, 2).applyO(3) // 0

Inherited from:

IndexingOps

Normalize a given index of a circular Seq

Value parameters

i: IndexO

Attributes

Inherited from:: IndexingOps

In this article

Generated with