☰
ps_map
container.ps_map
Functions
add mapping from kv.values.0 to kv.values.1
Adding has a cumulative average runtime in O(log size) and a worst-case
runtime of O(size)
Adding has a cumulative average runtime in O(log size) and a worst-case
runtime of O(size)
§(k container.ps_map.PK, v container.ps_map.V):Any => container.this.ps_map container.ps_map.PK container.ps_map.V
§(k container.ps_map.PK, v container.ps_map.V)
:
Any =>
container.this.ps_map container.ps_map.PK container.ps_map.Vadd mapping from k to v
create sorted array of all keys in this map
create a string containing all mappings
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 hierachy of types. So for Type values, dynamic_type is redefined
to just return Type.type.
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 hierachy of types. So for Type values, dynamic_type is redefined
to just return Type.type.
check if key k is present in the set of keys
find the value k is mapped to or nil if k is not part of this map
infix operator synonym for union of two ps_maps
get an array of all key/value pairs in this map
get a sequence of all keys in this map
get the highest key in this map
get the lowest key in this map
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.
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.
union of two ps_maps
creates a new ps_map that maps all the keys that exist either in ps_map.this
or in other to the values they are mapped to. In case a key k exists in
both ps_map.this and other, it will be mapped to ps_map.this[k] or to other[k],
but it is undefined to which of these two.
creates a new ps_map that maps all the keys that exist either in ps_map.this
or in other to the values they are mapped to. In case a key k exists in
both ps_map.this and other, it will be mapped to ps_map.this[k] or to other[k],
but it is undefined to which of these two.
get a sequence of all values in this map
Type Features
empty -- an empty partially sorted map
This feature creates an empty instance of ps_map.
This feature creates an empty instance of ps_map.
ps_map -- routine to initialize a partially sorted map from two Sequences
This feature creates a pre-initialized instance of ps_map.
This feature creates a pre-initialized instance of ps_map.
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`.
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`.
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.