Indexed collections: vector, array, string, list, ...

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.

extend module Stdlib;

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;