container

abstract_array -- parent of array implementation like `array` and `expanding_array`

This provides basic functionality that an array should provide based on `index[i]`
and `length` that have to be provided by children of `abstract_array`.

Buffer -- one-dimensional mutable buffer with effect

Buffer can be used to implement ranges of mutable memory that may be
visible to the outside or even may be modified by the outside. Examples
are memory mapped files, memory shared between processes, bitmaps on a
display, memory mapped I/O, etc.

To model the effects of reading or writing a buffer, an effect is given
as an argument to a buffer. This effect should implement the operations
required to implement the `index []` and `set []` features as needed by
the backend. This could be done via direct memory accesses, as for `mmap`
memory used in a native backend, or via an API such as `java.nio.ByteBuffer`
for a JVM backend.

Circular_Buffer -- a circular buffer-like structure

buffer to which elements can be enqueued and retrieved with a FIFO
logic.

it is usually backed by a fixed length array.

effect that will be installed by `expanding_array.expand` when running `filler`

expanding_array -- an array with a length and a (possible larger) capacity

An expanding array is a persistent data structure that has cumulative O(1)
performance of adding single elements at its end.

WARNING: Due to the high worst-case time for addition, this structure should
not be used in situations when adding a single element repeatedly to the same
instance of `expanding_array` is performance critical. If the resulting
`expanding_array`'s length is `l`, this will trigger the worst-case
addition time, resulting in cumulative time O(m*l) for adding an element m
times.

This constructor is for internal use only, to create instance of
`expanding_array`, use `(expanding_array T).type.empty` to create an empty
expanding array instance.

hash_map -- an immutable hash map from keys HK to values V

abstract type for 'Linked_List'

Map -- an abstract map from keys K to values V

an interface defining a mutable array

Mutable_Array2 -- two-dimensional mutable array with effect

Mutable_Hash_Map -- a mutable hash map from keys HK to values V

Uses a mutable array internally, when upper_load_factor is reached size is multiplied
by resize_factor (doubled, tripled, etc.) and elements are copied to new array of this size.
If lower_load_factor is reached size is divided by resize_factor.
Insert and retrieve operations on this map are therefore in amortized O(1).

a type for mutable singly linked lists

On call to `Mutable_Linked_List LM T data` creates a minimal list consisting
of only one single element. To create larger rings, you can either call
`append` to add single cells, or `concat` to concatenate two lists.

Mutable_Map -- an abstract mutable map from keys K to values V

mutable_tree_map -- a mutable map using an AVL tree

ordered_map -- an immutable map from ordered keys OK to values V

Lookup performance is O(log size) since it uses binary search in a
sorted array. When deterministic performance is desired, an ordered map
should be preferred over a hash map.

performance of creation of the map is in O(n log n) where n is
keys.length.

Persistent_Map -- an abstract persistent map from keys K to values V

ps_map -- a partially sorted map

ps_map is a persistent map from an ordered key PK to a value V. This map is
generally well-behaved with respect to cumulative and average performance.

The keys and values are stored in arrays consisting of sorted sub-arrays,
with sub-arrays corresponding to the 1-bits in the binary representation
of the size.

This results in cumulative memory usage in O(size log² size), worst-case
lookup time in O(log² size) and average addition time in O(1) and worst-case
addition time in O(size log² size).

WARNING: Due to the high worst-case time for addition, this structure should
not be used in situations when adding a single element repeatedly to the same
instance of ps_map is performance critical. If the resulting map's size n is a
power of 2, this will trigger the worst-case addition time resulting in
O(m*n log² n) for adding an element m times.

This constructor is for internal use only, to create instance of ps_map, use
ps_map PK V without arguments.

ps_set -- a partially sorted set based on ps_map

ps_set is a persistent set of ordered values. This set is generally
well-behaved with respect to cumulative and average performance.

WARNING: Due to the high worst-case time for addition, this structure should
not be used in situations when adding a single element repeatedly to the same
instance of ps_set is performance critical. If the resulting set's size n is a
power of 2, this will trigger the worst-case addition time resulting in
O(m*n log² n) for adding an element m times.

Set -- an abstract set of values

sorted_array -- sorted one-dimensional immutable array

This takes an unsorted array and a compare function as an arguments and
returns a sorted one.

Non-mutating heap sort is used internally. This gives guaranteed performance in
O(n log n) comparisons and assignments for an array of size n.

This is a little wasteful on allocated memory, which is also O(n log n) since
partially sorted arrays are thrown away. This might be improved to use an
in-place heap sort to bring allocated memory down to O(n).

interface definition for stacks

A stack implementation using local mutation

create a String from this instance. Unless redefined, `a.as_string` will
create `"instance[T]"` where `T` is the dynamic type of `a`

Get the dynamic type of this instance. For value instances `x`, this is
equal to `type_of x`, but for `x` with a `ref` type `x.dynamic_type` gives
the actual runtime type, while `type_of x` results in the static
compile-time type.

There is no dynamic type of a type instance since this would result in an
endless hierarchy of types. So for Type values, dynamic_type is redefined
to just return Type.type.

map_of -- routine to initialize a map from an array of key value tuples

This feature creates an instance of a map.

example: map_of [(key1, value1), (key2, value2)]

map_of -- routine to initialize a map from arrays of ordered elements
and values

This feature creates an instance of a map.

convenience prefix operator to create a string from a value.

This permits usage of `$` as a prefix operator in a similar way both
inside and outside of constant strings: $x and "$x" will produce the
same string.

set_of_ordered -- routine to initialize a set from a Sequence of ordered elements

This feature creates an instance of a Set.

string representation of this type to be used for debugging.

result has the form "Type of '<name>'", but this might change in the future

There is no dynamic type of a type instance since this would result in an
endless hierarchy of types, so dynamic_type is redefined to just return
Type.type here.

Is this type assignable to a type parameter with constraint `T`?

The result of this is a compile-time constant that can be used to specialize
code for a particular type.

is_of_integer_type(n T : numeric) => T : integer
say (is_of_integer_type 1234) # true
say (is_of_integer_type 3.14) # false

it is most useful in conjunction preconditions or `if` statements as in

pair(a,b T) is

=>

or

val(n T) is

name of this type, including type parameters, e.g. 'option (list i32)'.

convenience prefix operator to create a string from a value.

This permits usage of `$` as a prefix operator in a similar way both
inside and outside of constant strings: $x and "$x" will produce the
same string.

NYI: Redefinition allows the type feature to be distinguished from its normal counterpart, see #3913

Get a type as a value.

This is a feature with the effect equivalent to Fuzion's `expr.type` call tail.
It is recommended to use `expr.type` and not `expr.type_value`.

`type_value` is here to show how this can be implemented and to illustrate the
difference to `dynamic_type`.