Modifying v0.1.0
Swap<T>
pub func Swap<T>(left: *var T, right: *var T)
Exchanges the values at two locations. Both are borrowed mutably and both are written. Passing the same location twice is legal and leaves it alone. Cannot fail. Runs in constant time and allocates nothing. Both pointers must be non-null and writable.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
left | *var T | one of the two elements |
right | *var T | the other |
Reverse<T>
pub func Reverse<T>(items: var T[..])
Reverses the order of items in place.
items is borrowed mutably and rewritten. An empty slice and a single element are already reversed, so neither
is a special case.
Cannot fail. Runs in time proportional to the length, making half as many exchanges, and allocates nothing.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
Rotate<T>
pub func Rotate<T>(items: var T[..], middle: uint) -> bool
Rotates items left so that the element at middle becomes the first.
items is borrowed mutably and rewritten. A middle of zero or of the whole length leaves the order alone;
anything past the length is refused, since there is no such element to bring to the front.
Done as three reversals — the front, the back, then the whole — which needs no scratch storage and touches
every element at most twice.
Reports false only for a middle past the length.
Runs in time proportional to the length and allocates nothing.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
middle | uint | the index that becomes the new first element |
Returns: whether middle was a usable index
Fill<T>
pub func Fill<T>(items: var T[..], value: T)
Writes value into every position of items.
items is borrowed mutably and rewritten; value is read by value and copied into each position. An empty slice
writes nothing.
Cannot fail. Runs in time proportional to the length and allocates nothing.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
value | T | the value to write to every element |
CopyTo<T>
pub func CopyTo<T>(
destination: var T[..],
source: T[..]
) -> bool
Copies source into destination, front to back.
destination is borrowed mutably and written; source is borrowed and read. Reports false when the two lengths
differ, having written nothing: a partial copy is worse than a refused one, since the caller cannot tell how far
it got.
The two must not overlap, unless destination begins at or before source. Use MoveTo where they might.
Runs in time proportional to the length and allocates nothing.
Overlapping the wrong way silently copies elements that were already overwritten.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
destination | var T[..] | where the results go |
source | T[..] | where the elements come from |
Returns: whether destination was long enough
MoveTo<T>
pub func MoveTo<T>(
destination: var T[..],
source: T[..]
) -> bool
Copies source into destination, correctly however the two overlap.
destination is borrowed mutably and written; source is borrowed and read. Reports false when the two lengths
differ, having written nothing.
Copies back to front when destination starts after source, and front to back otherwise, which is what makes
shifting a run of elements along its own storage safe in either direction.
Runs in time proportional to the length and allocates nothing.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
destination | var T[..] | where the results go |
source | T[..] | where the elements come from |
Returns: whether destination was long enough
Unique<T>
pub func Unique<T>(items: var T[..]) -> uint
Collapses each run of adjacent equal elements in items to one, and reports how many are left.
items is borrowed mutably and rewritten. Only adjacent duplicates go: on a sorted slice that removes every
duplicate, and on an unsorted one it removes only the runs, which is the useful behaviour rather than a
compromise — it makes this the second half of sort-then-unique without paying for a second sort.
Relative order among the survivors is preserved, nothing is resized, and what lies past the reported length is
unspecified.
Requires == on the element type.
Cannot fail. Runs in time proportional to the length and allocates nothing.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
Returns: how many elements are left after collapsing each run of equal neighbours to one
RemoveValue<T>
pub func RemoveValue<T>(items: var T[..], value: T) -> uint
Removes every element of items equal to value, and reports how many are left.
items is borrowed mutably and rewritten; value is read by value. Survivors are compacted toward the front in
their original order, nothing is resized, and what lies past the reported length is unspecified.
Requires == on the element type.
Cannot fail. Runs in time proportional to the length and allocates nothing.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
value | T | the value to remove every occurrence of |
Returns: how many elements are left
RemoveWhere<T>
pub func RemoveWhere<T>(
items: var T[..],
predicate: func(T) -> bool
) -> uint
Removes every element of items that predicate accepts, and reports how many are left.
items is borrowed mutably and rewritten; predicate is called once per element. Survivors are compacted toward
the front in their original order, nothing is resized, and what lies past the reported length is unspecified.
Cannot fail. Runs in time proportional to the length and allocates nothing beyond whatever predicate does.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
predicate | func(T) -> bool | the test each element is put to |
Returns: how many elements are left
Partition<T>
pub func Partition<T>(
items: var T[..],
predicate: func(T) -> bool
) -> uint
Moves every element predicate accepts to the front of items, and reports how many there were.
items is borrowed mutably and rewritten; predicate is called once per element. Everything before the reported
index satisfies the predicate and everything from it on does not.
Order within each group is not preserved: this exchanges elements from both ends inward, which is what keeps it
to one pass and no scratch storage. A caller that needs the original order within each group needs a stable
partition, which needs somewhere to put things.
Cannot fail. Runs in time proportional to the length and allocates nothing beyond whatever predicate does.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | var T[..] | the sequence to work on |
predicate | func(T) -> bool | the test each element is put to |
Returns: the index of the first element that fails predicate
PartitionPoint<T>
pub func PartitionPoint<T>(
items: T[..],
predicate: func(T) -> bool
) -> uint
Where the accepted elements of an already-partitioned items end.
items is borrowed and read; predicate is called about as many times as the logarithm of the length. Requires
that every element the predicate accepts comes before every element it rejects — which is what Partition
leaves behind, and what a sorted slice is with respect to any threshold predicate.
A slice that is not partitioned this way does not fail; it answers, and the answer is meaningless.
Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever
predicate does.
Type parameters
| Name | Description |
|---|---|
T | the element type |
Parameters
| Name | Type | Description |
|---|---|---|
items | T[..] | the sequence to work on |
predicate | func(T) -> bool | the test each element is put to |
Returns: the index of the first element that fails predicate, assuming the sequence is partitioned