Next: Indexed collections: vector, array,
Up: Collections
Previous: Hash tables
Index
In ordered.diesel:
The elements of an ordered collection appear in some well-defined
order, i.e., do returns the elements in the same order each time
called (specific subclasses define how that order is
determined). Since all the classes in this section inherit from
collection, they support length, is_empty
, do, pick_any
,
includes, find, copy, and other collection operations.
module OrderedCollection;
abstract class ordered_collection[T] isa collection[T],
- type param is covariant:
ordered_collection[`S >= T];
abstract class ordered_collection_exactly[T] isa collection_exactly[T],
ordered_collection[T];
One through four ordered collections can be iterated through in
parallel using do; the iteration exits when the smallest collection
is exhausted.
fun do(c1:ordered_collection[`T1], c2:ordered_collection[`T2],
c:&(T1,T2):void):void;
fun do(c1:ordered_collection[`T1], c2:ordered_collection[`T2],
c3:ordered_collection[`T3], c:&(T1,T2,T3):void):void;
fun do(c1:ordered_collection[`T1], c2:ordered_collection[`T2],
c3:ordered_collection[`T3], c4:ordered_collection[`T4],
c:&(T1,T2,T3,T4):void):void;
An ordered collection can be iterated through in reverse order,
and a sequence can be constructed from the ordered collection in
reverse order.
fun reverse(c:ordered_collection[`T]):sequence[T];
fun reverse_do(c:ordered_collection[`T], cl:&(T):void):void;
fun reverse_do(c1:ordered_collection[`T1], c2:ordered_collection[`T2],
cl:&(T1,T2):void):void;
fun reverse_do(c1:ordered_collection[`T1], c2:ordered_collection[`T2],
c3:ordered_collection[`T3], cl:&(T1,T2,T3):void):void;
fun reverse_do(c1:ordered_collection[`T1], c2:ordered_collection[`T2],
c3:ordered_collection[`T3], c4:ordered_collection[`T4],
cl:&(T1,T2,T3,T4):void):void;
Ordered collections of comparable, partially-ordered,
totally-ordered, or hashable elements are themselves comparable,
partially-ordered, totally-ordered, or hashable, respectively. Two
ordered collections are equal (=) if they have equal elements in the
same order. Lexicographic (dictionary) ordering is used to compare
two collections.
allow = etc. on any ordered collection, even inexactly known ones
extend class ordered_collection[`T <= comparable[T]]
isa comparable[ordered_collection[T]];
allow hash on any ordered collection, even inexactly known ones
extend class ordered_collection[`T <= hashable[T]]
isa hashable[ordered_collection[T]];
let hash_shift:int;
let num_hash_bits:int;
extend class ordered_collection_exactly[`T <= ordered[T]]
isa ordered_using_compare[ordered_collection_exactly[T]];
extend class ordered_collection_exactly[`T <= ordered_hashable[T]]
isa ordered_hashable[ordered_collection_exactly[T]];
fun as_ordered_collection(c:collection[`T]):ordered_collection[T];
fun view_stream(:ordered_collection[`T]):stream[T];
Elements may be extracted from ordered collections; however, these
operations may be inefficient, particularly fetch, next_to_last
,
and last. Objects of type indexed afford fast access to any
element.
fun first (a:ordered_collection[`T]):T;
fun second(a:ordered_collection[`T]):T;
fun third (a:ordered_collection[`T]):T;
fun fourth(a:ordered_collection[`T]):T;
fun next_to_last(a:ordered_collection[`T]):T;
fun last (a:ordered_collection[`T]):T;
Ordered collections of strings can be flattened into a single string,
optionally inserting a separator string element strings (only between
non-empty element strings, for flatten_ignoring_empty
). Similarly,
any ordered collection can be flattened into a string using a
user-defined closure to convert from the collection element to a
string element.
fun flatten(c:ordered_collection[string]):string;
fun flatten(c:ordered_collection[string], sep:string):string;
fun flatten_ignoring_empty(c:ordered_collection[string],
sep:string):string;
fun flatten_eval(c:collection[`T], cl:&(T):string):string;
fun flatten_eval(c:collection[`T], sep:string, cl:&(T):string):string;
fun flatten_eval_ignoring_empty(c:collection[`T], sep:string,
cl:&(T):string):string;
Similarly, ordered collections of sequences can be flattened
into a single vector
fun flat_vector(c:ordered_collection[`T <= sequence_exactly[`S]]
):vector[S];
fun elems_print_string(c:collection[`T], sep:string):string;
end module OrderedCollection;
Extensible ordered collections can have their first and last
elements removed, as well as the removing and adding behavior of
extensible collections.
module ExtensibleOrderedCollection;
abstract class extensible_ordered_collection[T]
isa extensible_collection[T], ordered_collection_exactly[T];
fun remove_first(:extensible_ordered_collection[`T],
if_empty:&():`S):T|S;
fun remove_first(c:extensible_ordered_collection[`T]):T;
fun remove_last(:extensible_ordered_collection[`T],
if_empty:&():`S):T|S;
fun remove_last(c:extensible_ordered_collection[`T]):T;
fun remove_last_N(c:extensible_ordered_collection[`T], n:int):void; - remove the last N elements
end module ExtensibleOrderedCollection;
In sequence.diesel:
A sequence is an ordered collection where the ordering of the elements is
determined externally, by the way they were put into the collection. (In
contrast, a sorted collection is an ordered collection where the order is
determined by the elements themselves and the < binary ordering predicate
over the elements.)
module Sequence;
abstract class sequence[T] isa ordered_collection[T],
- type param is covariant:
sequence[`S >= T];
abstract class sequence_exactly[T] isa ordered_collection_exactly[T],
sequence[T];
Concatenating two sequences always produces a new sequence
fun ||(s1:sequence[`T1], s2:sequence[`T2]):sequence[T1|T2];
Extensible sequences also allow elements to be added to the
front or end of the sequence.
module ExtensibleSequence;
abstract class extensible_sequence[T]
isa extensible_ordered_collection[T], sequence_exactly[T];
fun add_first(:extensible_sequence[`T], x:T):void;
fun add_last (:extensible_sequence[`T], x:T):void;
fun add_all_last(s:extensible_sequence[`T], c:collection[T]):void;
end module ExtensibleSequence;
Next: Indexed collections: vector, array,
Up: Collections
Previous: Hash tables
Index
Cecil/Vortex Project