Next: Implementations
Up: Collections
Previous: Ordered collections and sequences
Index
In indexed.diesel:
Indexed collections are indexed sequences. They support the behavior
of keyed tables, where the integers from 0 to c.length-1 serve as
the keys. Indexed collections inherit:
length, is_empty
, do, pick_any
, includes, find,
copy, etc., from collections;
reverse_do
, flatten, ||, etc., from sequences;
fetch, !, do_associations
, keys_do
, etc., from tables.
module IndexedCollection;
abstract class indexed[T] isa sequence[T], table[int,T],
- type parameter is covariant:
indexed[`S >= T];
abstract class indexed_exactly[T] isa sequence_exactly[T],
table_exactly[int,T],
indexed[T];
range_do
evaluates c on all elements in
[max(start,0)..min(stop,len)) (note half-open interval!)
fun range_do(a:indexed[`T], start:int, stop:int,
c:&(int,T):void):void;
allow includes etc. on any indexed collection, even inexactly
known ones
The includes_index
and find_index
methods are simply renamings
of the standard includes_key
and find_key
methods.
fun includes_index(a:indexed[`T], i:int):bool;
allow find_index
on any indexed collection, even inexactly
known ones
fun find_index(a:indexed[`T], value:T):int where =(:T,:T):bool;
fun find_index(a:indexed[`T], value:T,
if_absent:&():`S):int|S where =(:T,:T):bool;
The copy_from
method copies a portion of an indexed collection
from a start index up to (but not including) a stop index (or
the end of the collection, if the stop index is not
specified). The has_{prefix,suffix}
functions test whether an
indexed collection starts with or ends with a particular
collection; the remove_{prefix,suffix}
functions return a new
indexed collection with the specified prefix or suffix removed,
if present, or the original indexed collection otherwise. New
collections use the factory framework to try to return a
collection of the same kind as the argument.
fun copy_from(s:`S <= indexed[`T], start:int):S
where copy_from(:S, :int, :int):S;
fun copy_from(s:indexed[`T], start:int, up_to:int):indexed[T];
fun has_prefix(s:indexed[`T <= comparable[T]],
prefix:indexed[`T]):bool;
fun has_suffix(s:indexed[`T <= comparable[T]],
suffix:indexed[`T]):bool;
fun remove_prefix(s:`S <= indexed[`T <= comparable[T]],
prefix:indexed[`T]):S
where copy_from(:S, :int, :int):S;
fun remove_suffix(s:`S <= indexed[`T <= comparable[T]],
suffix:indexed[`T]):S
where copy_from(:S, :int, :int):S;
The split function breaks up an indexed collection into
segments based on a separator element. Some segments may be
empty if the separator is at the beginning, end, or adjacent to
another separator.
fun split(s:`S <= indexed[`T],
separator:`T <= comparable[T]
):extensible_sequence[S]
where copy_from(:S, :int, :int):S;
As usual, there are immutable and mutable varieties of indexed
collections. Mutable collections support changing bindings of
indices to values through the store or set_!
methods inherited from
m_table
.
abstract class i_indexed[T] isa indexed[T], i_table[int,T],
- type param is covariant:
i_indexed[`S >= T];
abstract class i_indexed_exactly[T] isa indexed_exactly[T],
i_table_exactly[int,T],
i_indexed[T];
abstract class m_indexed[T] isa indexed_exactly[T], m_table[int,T];
fun as_m_indexed(c:collection_exactly[`T]):m_indexed[T];
There are convenient ways of assigning into the beginning and end
of a collection. They can be invoked using the assignment message
sugar, e.g., first(c) := x.
fun set_first (a:m_indexed[`T], x:T):void;
fun set_second(a:m_indexed[`T], x:T):void;
fun set_third (a:m_indexed[`T], x:T):void;
fun set_fourth(a:m_indexed[`T], x:T):void;
fun set_last (a:m_indexed[`T], x:T):void;
fun set_only(a:m_indexed[`T], x:T):void;
The swap method exchanges the indices of two collection elements.
fun swap(c:m_indexed[`T], i:int, j:int):void;
The slide_elems[_by](from,to[,amount])
methods copy elements
in the range [from..to], inclusive, up by amount positions
(where amount defaults to 1), sliding down if amount is
negative.
fun slide_elems(t:m_indexed[`T], from:int, to:int):void;
fun slide_elems_by(t:m_indexed[`T], from:int, to:int, amount:int):void;
The sort method sorts a collection in place, using either the
element type's natural comparison operation (<=) or a user-supplied
comparator function. Sorting uses the quicksort algorithm and
attempts to be a reasonably stable sort.
fun sort(c:m_indexed[`T <= ordered[T]]):void;
fun sort_by(c:m_indexed[`T], pred:&(T,T):bool):void;
fun sort_by(c:m_indexed[`T], pred:&(T,T):bool,
first_index:int, last_index:int):void;
The pos method returns the index at which the first
collection occurs in the second collection (invoking the
if_absent
closure if not found), using the Knuth-Morris-Pratt
string-matching algorithm. The has_subsequence
method returns whether
the second collection is found in the first collection, and the
count_subsequences
method returns the number of non-overlapping
occurrences of the second collection in the first. [Note that the
order of collection arguments in pos is opposite to that in the
subsequence methods!]
fun pos(s1:indexed_exactly[`T <= comparable[T]],
s2:indexed_exactly[T]):int;
fun pos(s1:indexed_exactly[`T <= comparable[T]],
s2:indexed_exactly[T],
if_fail:&():int):int;
fun has_subsequence(s1:indexed_exactly[`T <= comparable[T]],
s2:indexed_exactly[T]):bool;
fun count_subsequences(s1:indexed_exactly[`T <= comparable[T]],
s2:indexed_exactly[T]):int;
An indexed_factory
is the abstract superclass of factories for
indexed collections.
abstract class indexed_factory;
generic_factory
returns a factory to use, if the receiver
factory doesn't implement some operation
fun generic_factory(:indexed_factory):indexed_factory;
mutable_factory
returns the factory to use if a mutable
result is required
fun mutable_factory(:indexed_factory):m_indexed_factory;
create_empty
yields a zero-length indexed collection of the
right kind.
fun create_empty[T](f:indexed_factory):indexed_exactly[T];
create_filled
yields a new indexed collection of the right
kind, with the given length, all of whose elements are
filler.
fun create_filled(f:indexed_factory,
size:int, filler:`T):indexed[T];
fun create_filled[T](f:indexed_factory,
size:int, filler:T):indexed_exactly[T];
create_init
yields a new indexed collection of the right
kind, with the given length, whose i'th element is the result
of evaluating the closure on i.
fun create_init(f:indexed_factory,
size:int, cl:&(int):`T):indexed[T];
fun create_init[T](f:indexed_factory,
size:int, cl:&(int):T):indexed_exactly[T];
create_mapped
yields a new indexed collection of the right
kind, whose length is the same as the argument collection's
and whose i'th element is the result of evaluating the closure
on the i'th element of the argument collection.
fun create_mapped(f:indexed_factory,
c:collection[`T1], cl:&(T1):`T2):indexed[T2];
fun create_mapped[T2](f:indexed_factory,
c:collection[`T1], cl:&(T1):T2
):indexed_exactly[T2];
Like create_mapped
, except that the argument closure is
invoked on each key/value pair of the argument collection.
fun create_mapped_associations(f:indexed_factory,
c:table[`K,`T1], cl:&(K,T1):`T2
):indexed[T2];
fun create_mapped_associations[T2](f:indexed_factory,
c:table[`K,`T1], cl:&(K,T1):T2
):indexed_exactly[T2];
create_copy
returns a new indexed collection of the right
kind whose length and elements are the same as the argument
collection's.
fun create_copy(f:indexed_factory, c:collection[`T]):indexed[T];
fun create_copy[T](f:`F <= indexed_factory, c:collection[T]):`C
where signature create_mapped[T](:F,:collection[T],:&(T):T):C;
abstract class i_indexed_factory isa indexed_factory;
abstract class m_indexed_factory isa indexed_factory;
create_sized
yields a new indexed collection of the right
kind, with the given length, all of whose elements are
initialized with some default ``uninitialized'' value.
fun create_sized[T](f:m_indexed_factory, size:int):m_indexed[T];
factory returns the factory object for the argument collection.
fun factory(:indexed[`T]):indexed_factory;
fun map(t:indexed[`T1], cl:&(T1):`T2):indexed[T2]; - a traditional map function
fun map_associations(t:indexed[`T1], cl:&(int,T1):`T2):indexed[T2]; - a version that maps over index/value pairs
end module IndexedCollection;
Subsections
Next: Implementations
Up: Collections
Previous: Ordered collections and sequences
Index
Cecil/Vortex Project