Ordered collections and sequences

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.

extend module Stdlib;

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.)

extend module Stdlib;

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];

end module Sequence;

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;