☰
psMap
psMap
§psMap(PK type :ordered psMap.PK, V type, data fuzion.sys.internal_array (tuple psMap.PK psMap.V), size i32, fill i32) => psMap psMap.PK psMap.V:Map psMap.PK, psMap.V
§psMap(PK
type
:ordered psMap.PK, V type
, data fuzion.sys.internal_array (tuple psMap.PK psMap.V), size i32, fill i32) =>
psMap psMap.PK psMap.V:
Map psMap.PK, psMap.Vadd mapping from k to v
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)
create sorted array of all keys in this map
find the value k is mapped to or nil if k is not part of this map
infix operator synonym for union of two psMaps
get an array of all key/value pairs in this map
get the highest key in this map
get the lowest key in this map
union of two psMaps
creates a new psMap that maps all the keys that exist either in psMap.this
or in other to the values they are mapped to. In case a key k exists in
both psMap.this and other, it will be mapped to psMap.this[k] or to other[k],
but it is undefined to which of these two.
creates a new psMap that maps all the keys that exist either in psMap.this
or in other to the values they are mapped to. In case a key k exists in
both psMap.this and other, it will be mapped to psMap.this[k] or to other[k],
but it is undefined to which of these two.
psMap 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 psMap is performance critical. If the resulting map's size n is a
power of 2, this will trigger the worst-case addition time resutling in
O(m*n log² n) for adding an element m times.
This constructor is for internal use only, to create instance of psMap, use
psMap PK V without arguments.