Documentation
¶
Overview ¶
Package slice implements some useful functions for manipulating slices of str.String values, and finding "pivots" (specific str.Symbol values at specific indices for which comparison operations approximately bisect the slice).
Index ¶
- func LongestCommonPrefix[T str.Symbol](a, b []T, chop, limit int) int
- type Bitmap
- type Optional
- type Slice
- func (m Slice[T]) AllEqual() bool
- func (s Slice[T]) Count() int
- func (s Slice[T]) CountN(n int) int
- func (m Slice[T]) FindPivot(index int) (pivot T, balance int, valid bool)
- func (m Slice[T]) GetI(i, symI int) Optional[T]
- func (m Slice[T]) Items() iter.Seq2[int, str.String[T]]
- func (m Slice[T]) LongestCommonPrefix(chop int) int
- func (m Slice[T]) MaxAt(index int) T
- func (s Slice[T]) MaxLen() (l int)
- func (m Slice[T]) MinAt(index int) T
- func (m Slice[T]) Split(symI int, pivot T) (Slice[T], Slice[T])
- func (m Slice[T]) SymbolsAt(index int) iter.Seq2[int, Optional[T]]
- type Untyped
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func LongestCommonPrefix ¶
LongestCommonPrefix returns the number of contiguous str.Symbol values in a str.String that are equal, starting at the index given by chop. limit represents the highest value that can be returned; the search is canceled if it exceeds this limit.
Types ¶
type Bitmap ¶
type Bitmap []uint64
Bitmap stores the information needed to maintain an arbitrary subset of a Slice. It records which elements in the original slice to consider present in the subslice, and provides a mapping from "virtual" indices (sequentially rodered references to elements in the subslice) to "physical" indoces (the index of the actual element in the underlying slice)
type Optional ¶
Optional represents a str.Symbol at a particular index within a str.String. Since the String might be too short to contain the Symbol, Optional encodes an additional Null value, distinct from any value the Symbol may have.
type Slice ¶
Slice is a collection of str.String values, to be compiled into a codeberg.org/alice_systems/slice_id.Set.
func (Slice[T]) FindPivot ¶
FindPivot starts at the middle of the Slice, and scans outwards to find the nearest Pivot String for the given Pivot Index, returning the Pivot Symbol and the index of that String in the Slice. For the result of FindPivot to be useful, the Slice must be sorted.
A Pivot String is a str.String that satisfies the Pivot Condition, defined below.
A Pivot Index is a number that represents the position of a str.Symbol within a str.String.
The Pivot Symbol for a str.String is the str.Symbol at the given Pivot Index. If a String's length is too short to contain a Pivot Symbol, this is itself considered as a distinct value of a Pivot Symbol.
The Pivot condition is satisfied by a str.String whose Pivot Symbol is not equal to that of its neighbor to the left. Assuming a sorted Slice, an index that refers to a String that satisfies this condition divides the slice into two groups:
- The Strings at indices greater than or equal to that of the Pivot String all have a Pivot Symbol greater than or equal to that of the Pivot String,
- The strings at indices less than that of the Pivot String all have a Pivot Symbol less than that of the Pivot String.
In other words, if you call PivotIndex(6) on a Slice, PivotIndex will look for the String closest to the middle of the Slice, whose 6th Symbol is different from that of its neighbor to the left in the Slice.
func (Slice[T]) GetI ¶
Get returns an Optional str.Symbol at symI, within the str.String at the physical index i in the slice
func (Slice[T]) LongestCommonPrefix ¶
LongestCommonPrefix returns the minimum output of LongestCommonPrefix for all pairs of values in the Slice.
func (Slice[T]) MaxLen ¶
MaxLen returns the length of the longest str.String in the Slice.
Source Files