Alice Project

The ArraySlice structure

________ Synopsis ____________________________________________________

    signature ARRAY_SLICE
    structure ArraySlice : ARRAY_SLICE

An extended version of the Standard ML Basis' ArraySlice structure.

See also: Array, VectorSlice, MONO_ARRAY_SLICE

________ Import ______________________________________________________

Imported implicitly.

________ Interface ___________________________________________________

    signature ARRAY_SLICE =
	type 'a slice
	type 'a t = 'a slice

	val full :        'a array -> 'a slice
	val slice :       'a array * int * int option -> 'a slice
	val subslice :    'a slice * int * int option -> 'a slice
	val vector :      'a slice -> 'a vector
	val toVector :    'a slice -> 'a vector
	val toList :      'a slice -> 'a list

	val length :      'a slice -> int
	val isEmpty :     'a slice -> bool
	val base :        'a slice -> 'a array * int * int
	val sub :         'a slice * int -> 'a
	val update :      'a slice * int * 'a -> unit
	val swap :        'a slice * int * int -> unit
	val getItem :     'a slice -> ('a * 'a slice) option

	val triml :       int -> 'a slice -> 'a slice
	val trimr :       int -> 'a slice -> 'a slice
	val splitAt :     'a slice * int -> 'a slice * 'a slice
	val splitl :      ('a -> bool) -> 'a slice -> 'a slice * 'a slice
	val splitr :      ('a -> bool) -> 'a slice -> 'a slice * 'a slice
	val dropl :       ('a -> bool) -> 'a slice -> 'a slice
	val dropr :       ('a -> bool) -> 'a slice -> 'a slice
	val takel :       ('a -> bool) -> 'a slice -> 'a slice
	val taker :       ('a -> bool) -> 'a slice -> 'a slice

	val rev :         'a slice -> unit
	val copy :        {src : 'a slice,  dst : 'a array, di : int} -> unit
	val copyVec :     {src : 'a VectorSlice.slice, dst : 'a array, di : int} -> unit

	val app :         ('a -> unit) -> 'a slice -> unit
	val appr :        ('a -> unit) -> 'a slice -> unit
	val modify :      ('a -> 'a) -> 'a slice -> unit
	val foldl :       ('a * 'b -> 'b) -> 'b -> 'a slice -> 'b
	val foldr :       ('a * 'b -> 'b) -> 'b -> 'a slice -> 'b
	val all :         ('a -> bool) -> 'a slice -> bool
	val exists :      ('a -> bool) -> 'a slice -> bool
	val find :        ('a -> bool) -> 'a slice -> 'a option

	val appi :        (int * 'a -> unit) -> 'a slice -> unit
	val appri :       (int * 'a -> unit) -> 'a slice -> unit
	val modifyi :     (int * 'a -> 'a) -> 'a slice -> unit
	val foldli :      (int * 'a * 'b -> 'b) -> 'b -> 'a slice -> 'b
	val foldri :      (int * 'a * 'b -> 'b) -> 'b -> 'a slice -> 'b
	val alli :        (int * 'a -> bool) -> 'a slice -> bool
	val existsi :     (int * 'a -> bool) -> 'a slice -> bool
	val findi :       (int * 'a -> bool) -> 'a slice -> (int * 'a) option

	val contains :    ''a slice -> ''a -> bool
	val notContains : ''a slice -> ''a -> bool

	val equal :       ('a * 'a -> bool) -> 'a slice * 'a slice -> bool
	val collate :     ('a * 'a -> order) -> 'a slice * 'a slice -> order

	val isSorted :    ('a * 'a -> order) -> 'a slice -> bool
	val sort :        ('a * 'a -> order) -> 'a slice -> unit

________ Description _________________________________________________

Items not described here are as in the Standard ML Basis' ArraySlice structure.

type t = slice

A local synonym for type slice.

toVector sl

Creates a vector of the elements of sl. Equivalent to vector sl.

toList sl

Creates a list of the elements of sl in order of increasing indices. Equivalent to Vector.toList (toVector sl).

rev sl

Reverses in-place the order of elements in the slice sl.

swap (sl, i, j)

Swaps the ith and jth element of slice sl. If i < 0 or |sl| <= i, or j < 0 or |sl| <= j, then the Subscript exception is raised.

triml k sl
trimr k sl

These functions remove k elements from the left (respectively, right) of the slice sl. If k is greater than the size of the slice, an empty slice is returned. Specifically, for a slice sl = slice(arr,i,j) and kj, we have:

        triml k sl = slice(arr, i+k, j-k)
        trimr k sl = slice(arr, i, j-k)

The exception Subscript is raised if k < 0. This exception is raised when triml k or trimr k is evaluated.

splitAt (sl, i)

Returns the pair of slices (sl1, sl2), where sl1 contains the first i characters of sl and sl2 contains the rest, assuming 0 ≤ isize sl. Otherwise, it raises Subscript.

splitl f sl
splitr f sl

These functions scan sl from left to right (respectively, right to left) looking for the first element that does not satisfy the predicate f. They return the pair (sl1, sl2) giving the split of the slice into the span up to that element and the rest. The slice sl1 is the left side of the split, sl2the right side.

dropl f sl
dropl f sl
takel f sl
taker f sl

These routines scan the slice sl for the first element not satisfying the predicate f. The functions dropl and takel scan left to right (i.e., increasing indices), while dropr and taker scan from the right. The drop functions drop the maximal subslice consisting of elements satisfying the predicate, while the take functions return the maximal such subslice. These can be defined in terms of the split operations:

        takel f sl = #1(splitl f sl)
        dropl f sl = #2(splitl f sl)
        taker f sl = #2(splitr f sl)
        dropr f sl = #1(splitr f sl)
appr f sl
appri f sl

Like app and appi, but apply f in right to left order (i.e., decreasing indices). The expression appr f sl is equivalent to:

        appri (f o #2) sl
alli f sl
existsi f sl

Indexed versions of the functions all and exists. The index of each element is passed to f as an additional argument. The following equivalences hold:

        all f sl    = alli (f o #2) sl
        exists f sl = existsi (f o #2) sl
contains sl a

Returns true if the element a occurs in the slice sl; otherwise false.

notContains sl a

Returns true if the element a does not occur in the slice sl; otherwise false. Equivalent to not(contains sl a).

equal eq (sl1, sl2)

Creates an equality function on slices given an equality on the element type.

isSorted f sl

Returns true iff the elements in sl are sorted with respect to the ordering function f.

sort f sl

Sorts the elements in the slice sl with respect to the ordering function f. Sorting may be unstable with respect to equal elements.

last modified 2007/Mar/30 17:10