next up previous index
Next: Indexed collections: vector, array, Up: Collections Previous: Hash tables   Index

Ordered collections and sequences

In ordered.cecil:

abstract object ordered_collection[T] isa collection[T];
  extend type ordered_collection[`T] subtypes ordered_collection[`S >= T];
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.

method do(c1@:ordered_collection[`T1], c2@:ordered_collection[`T2],
          c:&(T1,T2):void):void;
method do(c1@:ordered_collection[`T1], c2@:ordered_collection[`T2],
          c3@:ordered_collection[`T3], c:&(T1,T2,T3):void):void;
method do(c1@:ordered_collection[`T1], c2@:ordered_collection[`T2],
          c3@:ordered_collection[`T3], c4@:ordered_collection[`T4],
          c:&(T1,T2,T3,T4):void):void;
One through four ordered collections can be iterated through in parallel using do; the iteration exits when the smallest collection is exhausted.

signature reverse_do(ordered_collection[`T], cl:&(T):void):void;
method reverse(s@:ordered_collection[`T]):sequence[T];
An ordered collection can be iterated through in reverse order, and a sequence can be constructed from the ordered collection in reverse order.

extend ordered_collection[`T <= comparable[T]]
                isa comparable[ordered_collection[T]];
method =(c1@:ordered_collection[`T <= comparable[T]],
         c2@:ordered_collection[T]):bool;
extend ordered_collection[`T <= ordered[T]]
                isa ordered_using_compare[ordered_collection[T]];
method compare(c1@:ordered_collection[`T <= ordered[T]],
               c2@:ordered_collection[`T <= ordered[T]],
               if_less:&():`S, if_equal:&():`S, if_greater:&():`S
               ):S;
extend ordered_collection[`T <= hashable[T]]
                isa hashable[ordered_collection[T]];
extend ordered_collection[`T <= ordered_hashable[T]]
                isa ordered_hashable[ordered_collection[T]];
let hash_shift:int;
let num_hash_bits:int;
method hash(c@:ordered_collection[`T <= hashable[T]], range:int):int;
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.

method as_ordered_collection(c@:ordered_collection[`T]):ordered_collection[T];
method as_vstring(c@:ordered_collection[char]):vstring;
method as_m_vstring(c@:ordered_collection[char]):m_vstring;
signature view_stream(ordered_collection[`T]):stream[T];
signature copy(ordered_collection[`T]):ordered_collection[T];
Ordered collections of characters can be converted to vstring or m_vstring representations, and any ordered collection can be viewed as a stream. (In the future, we plan to build a more general mechanism for converting collections to different representations.)

method fetch(a@:ordered_collection[`T], i:int):T;
method !(a@:ordered_collection[`T], i:int):T;
method first (a@:ordered_collection[`T]):T;
method second(a@:ordered_collection[`T]):T;
method third (a@:ordered_collection[`T]):T;
method fourth(a@:ordered_collection[`T]):T;
method next_to_last(a@:ordered_collection[`T]):T;
method last  (a@:ordered_collection[`T]):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.

method flatten(c@:ordered_collection[string]):string;
method flatten(c@:ordered_collection[string], sep:string):string;
method flatten_ignoring_empty(c@:ordered_collection[string],
                              sep:string):string;
method flatten_eval(c@:collection[`T], cl:&(T):string):string;
method flatten_eval(c@:collection[`T], sep:string, cl:&(T):string):string;
method flatten_eval_ignoring_empty(c@:collection[`T], sep:string,
                                   cl:&(T):string):string;
method elems_print_string(c@:collection[`T], sep:string):string;
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. In sequence.cecil:

abstract object sequence[T] isa ordered_collection[T];
extend type sequence[`T] subtypes sequence[`S >= T];
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.)

method ||(s1@:sequence[`T], s2@:sequence[`T]):sequence[T];
signature copy(sequence[`T]):sequence[T];
Concatenating two sequences always produces a new sequence


next up previous index
Next: Indexed collections: vector, array, Up: Collections Previous: Hash tables   Index

Cecil/Vortex Project