This module features several types and functionality related to linear sequences and linear indexing.
The most useful from an ergonomics perspective is probably StridedSlice which is like a HSlice but with a stride (step). This is akin to Python's general slicing like xs[start:stop:step], or its range(start,stop,step) function.
The primary way to construct strided slices is with the @: operator, which can be applied in several ways.
Example:
import strides let greet = "hello world" # The obvious way, as a strided slice: assert greet[ 2 .. 8 @: 3 ] == "l r" # As a prefix: assumes the whole length. assert greet[ @: 2 ] == "hlowrd" assert greet[ @: -1 ] == "dlrow olleh" # As a length + step: shorthand for `0 ..< length` or `length-1 .. 0` assert greet[ 5 @: 1 ] == "hello" assert greet[ 5 @: 2 ] == "hlo" assert greet[ 5 @: -1 ] == "olleh" assert greet[greet.len @: 3] == greet[@:3]
Given a length (for example of the container being sliced) we can "resolve" a StridedSlice into a LinearSegment (a finite LinearSequence). A LinearSegment_ consists of the fields (initial, stride, count) which should all be integers.
There are two ways to resolve a slice: the Nim way (hard slices) and the Python way (soft slices).
Standard Nim behavior is for slices to go out of bounds. For example "test"[0 ..< 20] will trigger an exception. Whereas in Python "test"[0:20] will work and simply return "test".
The first behavior is met with the ^! operator which functions very similar to ^^. It merely translates BackwardsIndex and StridedIndex into integers, not doing any bounds checking.
The second way is with the operator ^? which does soft slicing. It works the same way as ^! but automatically constrains the slice so it doesn't go out of bounds.
By default, and for convenience(?), containers use ^? to mimic Python behavior when using strided slices specifically (might change?), but regular slices (HSlice) still triggers out of bounds.
Example:
import strides # ^! resolves the strided slice into a linear segment given a length. let linseg1 = (1 .. 100 @: 5) ^! 10 assert linseg1 is LinearSegment assert linseg1.len == 20 # ^? does the same but constrains the linear segment to `0 ..< length`. let linseg2 = (1 .. 100 @: 5) ^? 10 assert linseg2.len == 2 # constrained to only cover [1, 6] let text = "aAbBcCdDeEfF" # "Hard" slices trigger out of bounds: # text[ (0 .. 100 @: 2) ^! 12 ] --> exception! # But this works: assert text[ (0 .. 100 @: 2) ^? 12 ] == "abcdef"To use StridedSlice in a custom container, you would do something like the following:
Example:
import strides type MyList = object proc len*(_: MyList): int = 69 proc `[]`*(lst: MyList, idx: AnyStrided): auto = when idx isnot LinearSegment: let idx = idx ^? lst.len # or `^!` for slices that trigger out of bounds. assert idx is LinearSegment # ...
Types
AnyIndexing = SomeInteger or BackwardsIndex or HSlice or AnyStrided
- Any type that can commonly be used to index an array-like container. Source Edit
AnyStrided = StridedSlice or StridedIndex or LinearSegment
- Any type that can commonly be used to slice with a stride. Source Edit
LinearSegment[T; I] {.pure.} = object of LinearSequence[T] count*: I
-
A LinearSequence with a count: a finite linear sequence.
This is meant to abstracts a general indexing loop, and iterating over it produces the following loop:
var index = <initial> let stop = <initial> + <count> * <stride> while index != stop: yield index index.inc <stride>
See StridedSlice for a different kind of representation.
Note: segment[i] is not bound checked. Can be constrained with segment[a .. b].
Source Edit LinearSequence[T] {.pure, inheritable.} = object initial*: T stride*: T
-
Represents the linear sequence initial + stride * k for a variable k.
One could also think of it as an infinite loop with a linear index variable.
Source Edit StridedIndex = distinct int
- Represents a @:stride index. Source Edit
StridedSlice[T; U] = object a*: T b*: U s*: int
-
Strided slice. Acts like a HSlice but with a stride parameter (s).
Inspiration is Python's slices and range, though the end point is still (unfortunately) counted as inclusive in order to remain compatible with HSlice.
You would normally construct these with the @: operator and resolve them into concrete LinearSegments with the ^! operator.
Warning: The stride should never be 0.Source Edit
Procs
func `$`(a: BackwardsIndex): string {....raises: [ValueError], tags: [], forbids: [].}
- Missing from standard library? Source Edit
func `$`(ls: LinearSequence): string
- Source Edit
func `$`(seg: LinearSegment): string
- Source Edit
func `$`(si: StridedIndex): string {....raises: [ValueError], tags: [], forbids: [].}
- Source Edit
func `$`(ss: StridedSlice): string
- Source Edit
func `@:`(step: int): auto {.inline, ...raises: [], tags: [], forbids: [].}
- Prefix variant of the step operator. Equivalent to applying a stride to the entire valid length. Returns a StridedIndex. Source Edit
func `@:`[T, U](slice: HSlice[T, U]; step: int): StridedSlice[T, U] {.inline.}
-
Turns a regular slice into a strided slice.Note: For slices with negative stride (i.e. right-to-left slices) the largest number should be specified first: 100 .. 0 @: -1 represents the indices 100, 99, 98, ..., 0, but 0 .. 100 @: -1 is empty.Source Edit
func `@:`[T: SomeInteger](e: T; step: int): StridedSlice[T, int] {.inline.}
-
Constructs a strided slice with a length and a step.
The number is taken as a "total length" of a hypothetical 0 ..< L slice. Thus it is interpreted as an exclusive end point when the stride is positive, and an exclusive start point when stride is negative.
The number of elements in the strided slice is easy to calculate as simply length div step.
Example:
assert (12 @: 2) == (0 .. 11 @: 2) assert (12 @: -2) == (11 .. 0 @: -2) # Note that these differ in more than direction! One former touches only # even numbers, the latter only odd numbers.
Source Edit func `[]`(s: string; seg: AnyStrided): string
-
Overload so that StridedSlice and StridedIndex can be used with strings.
Example:
assert "nefarious"[ 2 .. 0 @: -1 ] == "fen"
Source Edit func `[]`(seg: LinearSegment; slice: HSlice): auto {.inline.}
-
Constrains a LinearSegment to its overlap with the given slice.
Example:
let seg = initLinearSegment(1, 3, 6) # [1,4,7,10,13,16] assert seg[5 .. 20].toStridedSlice == (7 .. 16 @: 3) assert seg[-10 .. 0].toStridedSlice == (1 .. -2 @: 3) assert seg[10 .. 12].toStridedSlice == (10 .. 10 @: 3)
Source Edit func `[]`[T](arr: openArray[T]; seg: AnyStrided): seq[T]
-
Overload so that StridedSlice and StridedIndex can be used with arrays and the seq data type.
Example:
assert [1,2,3,4][ @:2 ] == @[1, 3]
Source Edit func `[]`[T](ls: LinearSequence[T]; k: T): auto {.inline.}
-
Gives the kth value in this sequence.
Synonym for ls.initial + ls.stride * k.
Note: 0-indexed, so the first value is ls[0].Source Edit func `[]`[T](ls: LinearSequence[T]; slice: HSlice): LinearSegment[T, T] {.inline.}
- Source Edit
func `[]=`(s: var string; seg: AnyStrided; input: string)
-
Overload so that StridedSlice and StridedIndex can be used with strings.
Example:
var s = "nefarious" s[ 2 .. 0 @: -1 ] = "gerg" assert s == "gregarious" # note the reversed order of 'gerg' s[@:3] = "xxxx" assert s == "xrexarxoux"
Source Edit func `[]=`[T](s: var seq[T]; seg: AnyStrided; input: openArray[T])
- Overload so that StridedSlice and StridedIndex can be used with strings. Source Edit
func `^!`(idx: AnyIndexing; length: SomeInteger): auto {.inline.}
-
Resolves indexing-like types.
Given an integer or BackwardsIndex this acts like ^^, but takes the length directly (as opposed to the container).
Given a HSlice it resolves any contained BackwardsIndex to int.
Given a StridedSlice or StridedIndex it converts it to a LinearSegment.
Slices are not constrained to the given length.
Normally the only use for this operator is in overloading [] to implement indexing.
Source Edit func `^?`(idx: AnyIndexing; length: SomeInteger): auto {.inline.}
-
Resolves indexing-like types, and constrains slicing types so they cannot go out-of-bounds.
This functions much like ^!, but slices (HSlice, StridedSlice, SliceIndex, LinearSegment) will automatically be constrained so they cannot go out-of-bounds.
Normally the only use for this operator is in overloading [] to implement indexing.
Note: The ^? and ^! operators have higher precedence than .., so parenthesis is needed when using them with a literal slice.Example:
assert (^1) ^? 50 == 49 assert (0 .. 9) ^? 50 == 0 .. 9 assert (20 .. 45) ^? 30 == 20 .. 29 assert (0 .. 99 @: 20) ^? 50 == initLinearSegment(0, 20, 3) assert (@: -1) ^? 10 == initLinearSegment(9, -1, 10)
Source Edit func initLinearSegment[T, I](initial, stride: T; count: I): LinearSegment[T, I] {. inline.}
- Source Edit
func initLinearSequence[T](initial, stride: T): LinearSequence[T] {.inline.}
- Source Edit
func initLinearSequence[T](stride: T): LinearSequence[T] {.inline.}
- Source Edit
func initStridedSlice[T, U](a: T; b: U; s: int): StridedSlice[T, U] {.inline.}
- Source Edit
func last(seg: LinearSegment): auto {.inline.}
-
The last value in this sequence.
Synonym for seg[seg.len - 1].
Warning: Invalid if seg.len == 0.Source Edit func len(seg: LinearSegment): auto {.inline.}
-
Number of values in this sequence.
Synonym for seg.count.
Source Edit func maxLT[T](ls: LinearSequence[T]; bound: T): auto {.inline.}
- Finds k such that ls[k] is the largest value in the sequence less than bound. Source Edit
func maxLTE[T](ls: LinearSequence[T]; bound: T): auto {.inline.}
- Finds k such that ls[k] is the largest value in the sequence less than or equal to bound. Source Edit
func minGT[T](ls: LinearSequence[T]; bound: T): auto {.inline.}
- Finds k such that ls[k] is the least value in the sequence greater than bound. Source Edit
func minGTE[T](ls: LinearSequence[T]; bound: T): auto {.inline.}
- Finds k such that ls[k] is the least value in the sequence greater or equal to bound. Source Edit
func toLinearSegment(ss: StridedSlice): auto {.inline.}
- Converts a resolved StridedSlice to a LinearSegment. Source Edit
Iterators
iterator items(seg: LinearSegment): auto {.inline.}
- Yields seg[0], seg[1], ..., seg[seg.len - 1]. Source Edit
iterator items(ss: StridedSlice): auto {.inline.}
- Source Edit
iterator items[T](ls: LinearSequence[T]): T {.inline.}
- Infinite loop over the linear sequence ls[0], ls[1], ls[2], .... Source Edit
iterator pairs(seg: LinearSegment): auto {.inline.}
- Yields the sequence (k, seg[k]) for k in 0 ..< seg.len. Source Edit
Converters
converter toStridedSlice(seg: LinearSegment): auto
- Source Edit
converter toTuple[T, I](seg: LinearSegment[T, I]): (T, T, I)
- Source Edit
converter toTuple[T, I](ss: StridedSlice[T, I]): (T, T, I)
- Source Edit
converter toTuple[T](ls: LinearSequence[T]): (T, T)
- Source Edit