import Map "mo:map/Map";
import { nhash } "mo:map/Map";

let map = Map.new<Nat, Nat>();

Map.set(map, nhash, 1, 1);

Map.delete(map, nhash, 1);

Map interface description

Initializing / measuring
- new
- clear
- size
- empty
- make
Inserting / updating
Getting
Deleting
- remove
- delete
Performing queue operations
Mapping / filtering / cloning
Iterating
Searching
Constructing from iterators
Converting to arrays
Rehashing
- rehash

Set interface description

Initializing / measuring
- new
- clear
- size
- empty
- make
Inserting / updating
Getting
- has
- contains
Deleting
- remove
- delete
Performing queue operations
Filtering / cloning
Iterating
Searching
Constructing from iterators
Converting to arrays
Rehashing
- rehash

Iterator interface description

Moving a pointer
Getting current item
- current
Getting iterator state
- started
- finished
Resetting
- reset

Hash Utils

Calculating hashes
Composite utils
- ihash
- i8hash
- i16hash
- i32hash
- i64hash
- nhash
- n8hash
- n16hash
- n32hash
- n64hash
- thash
- phash
- bhash
- lhash
Constructing new utils

Map Interface description

type Map<K, V> = [var ?(
  keys: [var ?K],
  values: [var ?V],
  indexes: [var Nat],
  bounds: [var Nat32],
)];

Initializing / measuring

`new`

func new<K, V>(): Map<K, V>;

Creates and returns an empty Map. Empty Map has a special optimization and takes only 12 bytes of space. The Map structure will be initialized only after the insertion of the first entry and will occupy minimum 112 bytes.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`clear`

func clear<K, V>(map: Map<K, V>): ();

Removes all entries from the Map.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`size`

func size<K, V>(map: Map<K, V>): Nat;

Returns the amount of entries in the Map.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`empty`

func empty<K, V>(map: Map<K, V>): Bool;

Returns a boolean indicating whether the Map is empty (has zero entries) or not.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`make`

func make<K, V>(hashUtils: HashUtils<K>, key: K, value: V): Map<K, V>;

Creates a new Map, initializes it with the single provided (key, value) pair and returns the Map. The minimum amount of space a non-empty Map can occupy is 112 bytes.

Requires Hash Utils to be provided as the first argument.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

Inserting / updating

`put`

func put<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ?V;

If the provided key is not present in the Map, inserts a new (key, value) pair at the back of the Map and returns null.

If the provided key is present in the Map, replaces the previous value with the provided value and returns the previous value. The position of the (key, value) pair within the Map is not changed.

Requires Hash Utils to be provided as the second argument.

If the Map is empty, on the first insert the Map structure will be initialized which will take additional 100 bytes of space. The minimum amount of space a non-empty Map can occupy is 112 bytes.

Most put calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Map being full does not necessarily mean size == capacity as on deletion holes (unused array indexes) may (if a deletion happens inside the Map) or may not (if you delete the first or the last entry) be created.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`putFront`

func putFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ?V;

If the provided key is not present in the Map, inserts a new (key, value) pair at the front of the Map and returns null.

Requires Hash Utils to be provided as the second argument.

Most putFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`set`

func set<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ();

If the provided key is not present in the Map, inserts a new (key, value) pair at the back of the Map.

If the provided key is present in the Map, replaces the previous value with the provided value. The position of the (key, value) pair within the Map is not changed.

This operation is the same as put but doesn't have a return value.

Requires Hash Utils to be provided as the second argument.

Most set calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`setFront`

func setFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ();

If the provided key is not present in the Map, inserts a new (key, value) pair at the front of the Map.

If the provided key is present in the Map, replaces the previous value with the provided value. The position of the (key, value) pair within the Map is not changed.

This operation is the same as putFront but doesn't have a return value.

Requires Hash Utils to be provided as the second argument.

Most setFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`add`

func add<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ?V;

If the provided key is not present in the Map, inserts a new (key, value) pair at the back of the Map and returns null.

If the provided key is present in the Map, does no modifications and returns the previous value.

Requires Hash Utils to be provided as the second argument.

Most add calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`addFront`

func addFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ?V;

If the provided key is not present in the Map, inserts a new (key, value) pair at the front of the Map and returns null.

If the provided key is present in the Map, does no modifications and returns the previous value.

Requires Hash Utils to be provided as the second argument.

Most addFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`replace`

func replace<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: V): ?V;

If the provided key is not present in the Map, does no modifications and returns null.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`update`

func update<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, getNewValue: (K, ?V) -> ?V): ?V;

If the provided key is not present in the Map, calls the provided getNewValue function with (key, null) parameters. If the result of getNewValue call is a value, inserts a new (key, value) pair at the back of the Map and returns the new value. If the result of getNewValue call is null, does no modifications and returns null.

If the provided key is present in the Map, calls the provided getNewValue function with (key, previous value) parameters. If the result of getNewValue call is a value, replaces the previous value with the new value and returns the new value. The position of the (key, value) pair within the Map is not changed. If the result of getNewValue call is null, does no modifications and returns the previous value (which remains current).

Requires Hash Utils to be provided as the second argument.

Most update calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`updateFront`

func updateFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, getNewValue: (K, ?V) -> ?V): ?V;

If the provided key is not present in the Map, calls the provided getNewValue function with (key, null) parameters. If the result of getNewValue call is a value, inserts a new (key, value) pair at the front of the Map and returns the new value. If the result of getNewValue call is null, does no modifications and returns null.

Requires Hash Utils to be provided as the second argument.

Most updateFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`putMove`

func putMove<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: ?V): ?V;

If the provided key is not present in the Map, checks the optional value parameter. If the provided optional value is a value, inserts a new (key, value) pair at the back of the Map and returns null. If the provided optional value is null, does no modifications and returns null.

If the provided key is present in the Map, checks the optional value parameter. If the provided optional value is a value, replaces the previous value with the provided value, moves the entry to the back of the Map (if it's not there yet) and returns the previous value. If the provided optional value is null, moves the entry to the back of the Map (if it's not there yet) and returns null.

If the entry is being moved from the front to the back, all holes before the new first entry will be eliminated and rehash will never happen. If the entry is being moved from any non-front position to the back, the hole will be created and rehash may be called (if the Map is full).

Requires Hash Utils to be provided as the second argument.

Most putMove calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted (or moved from any non-front position to the back), rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`putMoveFront`

func putMoveFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: ?V): ?V;

If the provided key is not present in the Map, checks the optional value parameter. If the provided optional value is a value, inserts a new (key, value) pair at the front of the Map and returns null. If the provided optional value is null, does no modifications and returns null.

If the provided key is present in the Map, checks the optional value parameter. If the provided optional value is a value, replaces the previous value with the provided value, moves the entry to the front of the Map (if it's not there yet) and returns the previous value. If the provided optional value is null, moves the entry to the front of the Map (if it's not there yet) and returns null.

If the entry is being moved from the back to the front, all holes after the new last entry will be eliminated and rehash will never happen. If the entry is being moved from any non-back position to the front, the hole will be created and rehash may be called (if the Map is full).

Requires Hash Utils to be provided as the second argument.

Most putMoveFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted (or moved from any non-back position to the front), rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`replaceMove`

func replaceMove<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: ?V): ?V;

If the provided key is not present in the Map, does no modifications and returns null.

Requires Hash Utils to be provided as the second argument.

Most replaceMove calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be moved from any non-front position to the back, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`replaceMoveFront`

func replaceMoveFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, value: ?V): ?V;

If the provided key is not present in the Map, does no modifications and returns null.

If the provided key is present in the Map, checks the optional value parameter. If the provided optional value is a value, replaces the previous value with the provided value, moves the entry to the front of the Map (if it's not there yet) and returns the previous value. If the provided optional value is null, moves the entry to the front of the Map (if it's not there yet) and returns null.

Requires Hash Utils to be provided as the second argument.

Most replaceMoveFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be moved from any non-back position to the front, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`updateMove`

func updateMove<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, getNewValue: (K, ?V) -> ?V): ?V;

If the provided key is present in the Map, calls the provided getNewValue function with (key, previous value) parameters. If the result of getNewValue call is a value, replaces the previous value with the new value, moves the entry to the back of the Map (if it's not there yet) and returns the new value. If the result of getNewValue call is null, moves the entry to the back of the Map (if it's not there yet) and returns the previous value (which remains current).

Requires Hash Utils to be provided as the second argument.

Most updateMove calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted (or moved from any non-front position to the back), rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`updateMoveFront`

func updateMoveFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K, getNewValue: (K, ?V) -> ?V): ?V;

If the provided key is not present in the Map, calls the provided getNewValue function with (key, null) parameters. If the result of getNewValue call is a value, inserts a new (key, value) pair at the front of the Map and returns the new value. If the result of getNewValue call is null, does no modifications and returns null.

If the provided key is present in the Map, calls the provided getNewValue function with (key, previous value) parameters. If the result of getNewValue call is a value, replaces the previous value with the new value, moves the entry to the front of the Map (if it's not there yet) and returns the new value. If the result of getNewValue call is null, moves the entry to the front of the Map (if it's not there yet) and returns the previous value (which remains current).

Requires Hash Utils to be provided as the second argument.

Most updateMoveFront calls will not cause any space allocations and will be executed in O(1) time. If the Map is full, on the other hand, and a new entry is about to be inserted (or moved from any non-back position to the front), rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (either equal or double the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

Getting

`get`

func get<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K): ?V;

If the provided key is present in the Map, returns the corresponding value. Otherwise, returns null.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`has`

func has<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is present in the Map, returns true. Otherwise, returns false.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`contains`

func contains<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K): ?Bool;

If the Map is empty, returns null.

If the provided key is present in the Map, returns true. Otherwise, returns false (if the Map is not empty).

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Deleting

`remove`

func remove<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K): ?V;

If the provided key is not present in the Map, does no modifications and returns null.

If the provided key is present in the Map, removes the corresponding (key, value) pair from the Map and returns the value.

Requires Hash Utils to be provided as the second argument.

If the size of the Map after the deletion is less than 3 / 8 of capacity, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current entries (half the current capacity) times 16 bytes, all entries will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Map size.

If rehash is not called and the entry is being removed from the front or the back of the Map, all holes before the new first or after the new last entry will be eliminated.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`delete`

func delete<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: K): ();

If the provided key is not present in the Map, does no modifications.

If the provided key is present in the Map, removes the corresponding (key, value) pair from the Map.

This operation is the same as remove but doesn't have a return value.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

Performing queue operations

`peek`

func peek<K, V>(map: Map<K, V>): ?(K, V);

If the Map is not empty, returns the last (key, value) pair in the Map. Otherwise, returns null.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`peekFront`

func peekFront<K, V>(map: Map<K, V>): ?(K, V);

If the Map is not empty, returns the first (key, value) pair in the Map. Otherwise, returns null.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`pop`

func pop<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>): ?(K, V);

If the Map is empty, does no modifications and returns null.

If the Map is not empty, removes the last (key, value) pair in the Map and returns it.

Requires Hash Utils to be provided as the second argument.

If rehash is not called, all holes after the new last entry will be eliminated.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`popFront`

func popFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>): ?(K, V);

If the Map is empty, does no modifications and returns null.

If the Map is not empty, removes the first (key, value) pair in the Map and returns it.

Requires Hash Utils to be provided as the second argument.

If rehash is not called, all holes before the new first entry will be eliminated.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`cycle`

func cycle<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>): ?(K, V);

If the Map is empty, does no modifications and returns null.

If the Map is not empty, moves the last (key, value) pair in the Map to the front and returns it. All holes after the new last entry will be eliminated and rehash will never happen.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`cycleFront`

func cycleFront<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>): ?(K, V);

If the Map is empty, does no modifications and returns null.

If the Map is not empty, moves the first (key, value) pair in the Map to the back and returns it. All holes before the new first entry will be eliminated and rehash will never happen.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Mapping / filtering / cloning

`mapFilter`

func mapFilter<K, V1, V2>(map: Map<K, V1>, hashUtils: HashUtils<K>, mapEntry: (K, V1) -> ?V2): Map<K, V2>;

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided mapEntry function with (key, value) parameters. Constructs a new Map with all (key, mapEntry result) pairs for which mapEntry returned non-null result (in the same order mapEntry was called). Skips all entries for which acceptEntry returned null. Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`mapFilterDesc`

func mapFilterDesc<K, V1, V2>(map: Map<K, V1>, hashUtils: HashUtils<K>, mapEntry: (K, V1) -> ?V2): Map<K, V2>;

For every entry in the Map, from the last to the first entry (in descending order) calls the provided mapEntry function with (key, value) parameters. Constructs a new Map with all (key, mapEntry result) pairs for which mapEntry returned non-null result (in the same order mapEntry was called). Skips all entries for which acceptEntry returned null. Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`filter`

func filter<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, acceptEntry: (K, V) -> Bool): Map<K, V>;

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided acceptEntry function with (key, value) parameters. Constructs a new Map with all (key, value) pairs for which acceptEntry returned true (in the same order acceptEntry was called). Skips all entries for which acceptEntry returned false. Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`filterDesc`

func filterDesc<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, acceptEntry: (K, V) -> Bool): Map<K, V>;

For every entry in the Map, from the last to the first entry (in descending order) calls the provided acceptEntry function with (key, value) parameters. Constructs a new Map with all (key, value) pairs for which acceptEntry returned true (in the same order acceptEntry was called). Skips all entries for which acceptEntry returned false. Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`map`

func map<K, V1, V2>(map: Map<K, V1>, hashUtils: HashUtils<K>, mapEntry: (K, V1) -> V2): Map<K, V2>;

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided mapEntry function with (key, value) parameters. Constructs a new Map with all (key, mapEntry result) pairs (in the same order mapEntry was called). Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`mapDesc`

func mapDesc<K, V1, V2>(map: Map<K, V1>, hashUtils: HashUtils<K>, mapEntry: (K, V1) -> V2): Map<K, V2>;

For every entry in the Map, from the last to the first entry (in descending order) calls the provided mapEntry function with (key, value) parameters. Constructs a new Map with all (key, mapEntry result) pairs (in the same order mapEntry was called). Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`clone`

func clone<K, V>(map: Map<K, V>): Map<K, V>;

Iterates through the Map from the first to the last entry (in ascending order) and copies each entry into the new Map (in the order of iteration). Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`cloneDesc`

func cloneDesc<K, V>(map: Map<K, V>): Map<K, V>;

Iterates through the Map from the last to the first entry (in descending order) and copies each entry into the new Map (in the order of iteration). Returns the new Map.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Iterating

`keys`

func keys<K, V>(map: Map<K, V>): Iter<K>;

Creates an iterator object over the keys of the Map which starts at the first key and ends at the last key. The iterator can be used to iterate over all keys of the Map with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`keysDesc`

func keysDesc<K, V>(map: Map<K, V>): Iter<K>;

Creates an iterator object over the keys of the Map which starts at the last key and ends at the first key. The iterator can be used to iterate over all keys of the Map with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`vals`

func vals<K, V>(map: Map<K, V>): Iter<V>;

Creates an iterator object over the values of the Map which starts at the first value and ends at the last value. The iterator can be used to iterate over all values of the Map with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`valsDesc`

func valsDesc<K, V>(map: Map<K, V>): Iter<V>;

Creates an iterator object over the values of the Map which starts at the last value and ends at the first value. The iterator can be used to iterate over all values of the Map with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`entries`

func entries<K, V>(map: Map<K, V>): Iter<(K, V)>;

Creates an iterator object over the (key, value) pairs of the Map which starts at the first entry and ends at the last entry. The iterator can be used to iterate over all (key, value) pairs of the Map with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`entriesDesc`

func entriesDesc<K, V>(map: Map<K, V>): Iter<(K, V)>;

Creates an iterator object over the (key, value) pairs of the Map which starts at the last entry and ends at the first entry. The iterator can be used to iterate over all (key, value) pairs of the Map with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`keysFrom`

func keysFrom<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: ?K): Iter<K>;

If the optional key parameter is present, performs a search for it in the Map. Creates an iterator object over the keys of the Map which starts at the key after the found key (if the optional key parameter is present and found) or the first key (if the optional key parameter is either not present or not found) and ends at the last key. The iterator can be used to iterate over all keys of the Map after the specified key with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current key will indeed be the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the key right after it. This behavior can bit changed and the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the first key and not to the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`keysFromDesc`

func keysFromDesc<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: ?K): Iter<K>;

If the optional key parameter is present, performs a search for it in the Map. Creates an iterator object over the keys of the Map which starts at the key before the found key (if the optional key parameter is present and found) or the last key (if the optional key parameter is either not present or not found) and ends at the first key. The iterator can be used to iterate over all keys of the Map before the specified key with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current key will indeed be the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the key right before it. This behavior can bit changed and the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the last key and not to the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`valsFrom`

func valsFrom<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: ?K): Iter<V>;

If the optional key parameter is present, performs a search for it in the Map. Creates an iterator object over the values of the Map which starts at the value after the value associated with the found key (if the optional key parameter is present and found) or the first value (if the optional key parameter is either not present or not found) and ends at the last value. The iterator can be used to iterate over all values of the Map after the value associated with the specified key with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current value will indeed be the value associated with the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the value right after it. This behavior can bit changed and the value associated with the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the first value and not to the value associated with the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`valsFromDesc`

func valsFromDesc<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: ?K): Iter<V>;

If the optional key parameter is present, performs a search for it in the Map. Creates an iterator object over the values of the Map which starts at the value before the value associated with the found key (if the optional key parameter is present and found) or the last value (if the optional key parameter is either not present or not found) and ends at the first value. The iterator can be used to iterate over all values of the Map before the value associated with the specified key with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current value will indeed be the value associated with the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the value right before it. This behavior can bit changed and the value associated with the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the last value and not to the value associated with the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`entriesFrom`

func entriesFrom<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: ?K): Iter<(K, V)>;

If the optional key parameter is present, performs a search for it in the Map. Creates an iterator object over the (key, value) pairs of the Map which starts at the entry after the entry with the found key (if the optional key parameter is present and found) or the first entry (if the optional key parameter is either not present or not found) and ends at the last entry. The iterator can be used to iterate over all (key, value) pairs of the Map after the entry with the specified key with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current entry will indeed be the entry with the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the entry right after it. This behavior can bit changed and the entry with the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the first entry and not to the entry with the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`entriesFromDesc`

func entriesFromDesc<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>, key: ?K): Iter<(K, V)>;

If the optional key parameter is present, performs a search for it in the Map. Creates an iterator object over the (key, value) pairs of the Map which starts at the entry before the entry with the found key (if the optional key parameter is present and found) or the last entry (if the optional key parameter is either not present or not found) and ends at the first entry. The iterator can be used to iterate over all (key, value) pairs of the Map before the entry with the specified key with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current entry will indeed be the entry with the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the entry right before it. This behavior can bit changed and the entry with the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Map iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the last entry and not to the entry with the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Searching

`find`

func find<K, V>(map: Map<K, V>, acceptEntry: (K, V) -> Bool): ?(K, V);

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided acceptEntry function with (key, value) parameters until the acceptEntry function returns true. If true is returned, returns the current (key, value) pair immediately. If acceptEntry didn't return true for any entry, returns null.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`findDesc`

func findDesc<K, V>(map: Map<K, V>, acceptEntry: (K, V) -> Bool): ?(K, V);

For every entry in the Map, from the last to the first entry (in descending order) calls the provided acceptEntry function with (key, value) parameters until the acceptEntry function returns true. If true is returned, returns the current (key, value) pair immediately. If acceptEntry didn't return true for any entry, returns null.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`some`

func some<K, V>(map: Map<K, V>, acceptEntry: (K, V) -> Bool): Bool;

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided acceptEntry function with (key, value) parameters until the acceptEntry function returns true. If true is returned, returns true immediately. If acceptEntry didn't return true for any entry, returns false.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`someDesc`

func someDesc<K, V>(map: Map<K, V>, acceptEntry: (K, V) -> Bool): Bool;

For every entry in the Map, from the last to the first entry (in descending order) calls the provided acceptEntry function with (key, value) parameters until the acceptEntry function returns true. If true is returned, returns true immediately. If acceptEntry didn't return true for any entry, returns false.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`every`

func every<K, V>(map: Map<K, V>, acceptEntry: (K, V) -> Bool): Bool;

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided acceptEntry function with (key, value) parameters until the acceptEntry function returns false. If false is returned, returns false immediately. If acceptEntry didn't return false for any entry, returns true.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`everyDesc`

func everyDesc<K, V>(map: Map<K, V>, acceptEntry: (K, V) -> Bool): Bool;

For every entry in the Map, from the last to the first entry (in descending order) calls the provided acceptEntry function with (key, value) parameters until the acceptEntry function returns false. If false is returned, returns false immediately. If acceptEntry didn't return false for any entry, returns true.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`forEach`

func forEach<K, V>(map: Map<K, V>, mapEntry: (K, V) -> ()): ();

For every entry in the Map, from the first to the last entry (in ascending order) calls the provided mapEntry function with (key, value) parameters.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`forEachDesc`

func forEachDesc<K, V>(map: Map<K, V>, mapEntry: (K, V) -> ()): ();

For every entry in the Map, from the last to the first entry (in descending order) calls the provided mapEntry function with (key, value) parameters.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

Constructing from iterators

`fromIter`

func fromIter<K, V>(iter: IterNext<(K, V)>, hashUtils: HashUtils<K>): Map<K, V>;

Creates a new empty Map. For every (key, value) pair in the iterator, inserts the (key, value) pair at the back of the Map if the key is not present in the Map. If the key is present in the Map, replaces the previous value with the value and moves the entry to the back of the Map (if it's not there yet). Returns the new Map.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`fromIterDesc`

func fromIterDesc<K, V>(iter: IterNext<(K, V)>, hashUtils: HashUtils<K>): Map<K, V>;

Creates a new empty Map. For every (key, value) pair in the iterator, inserts the (key, value) pair at the front of the Map if the key is not present in the Map. If the key is present in the Map, replaces the previous value with the value and moves the entry to the front of the Map (if it's not there yet). Returns the new Map.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`fromIterMap`

func fromIterMap<K, V, T>(iter: IterNext<T>, hashUtils: HashUtils<K>, mapItem: (T) -> ?(K, V)): Map<K, V>;

Creates a new empty Map. For every item in the iterator, calls the provided mapItem function. For every item mapItem returned a (key, value) pair for, inserts the (key, value) pair at the back of the Map if the key is not present in the Map. If the key is present in the Map, replaces the previous value with the value and moves the entry to the back of the Map (if it's not there yet). Skips all items mapItem returned null for. Returns the new Map.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`fromIterMapDesc`

func fromIterMapDesc<K, V, T>(iter: IterNext<T>, hashUtils: HashUtils<K>, mapItem: (T) -> ?(K, V)): Map<K, V>;

Creates a new empty Map. For every item in the iterator, calls the provided mapItem function. For every item mapItem returned a (key, value) pair for, inserts the (key, value) pair at the front of the Map if the key is not present in the Map. If the key is present in the Map, replaces the previous value with the value and moves the entry to the front of the Map (if it's not there yet). Skips all items mapItem returned null for. Returns the new Map.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Converting to arrays

`toArray`

func toArray<K, V>(map: Map<K, V>): [(K, V)];

Constructs a new array with all (key, value) pairs present in the Map, from the first to the last entry (in ascending order). Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`toArrayDesc`

func toArrayDesc<K, V>(map: Map<K, V>): [(K, V)];

Constructs a new array with all (key, value) pairs present in the Map, from the last to the first entry (in descending order). Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`toArrayMap`

func toArrayMap<K, V, T>(map: Map<K, V>, mapEntry: (K, V) -> ?T): [T];

For every entry in the Map, from the first to the last entry (in ascending order), calls the provided mapEntry function with (key, value) parameters. Constructs a new array with all non-null mapEntry result items (in the same order mapEntry was called). Skips all null mapEntry result items. Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`toArrayMapDesc`

func toArrayMapDesc<K, V, T>(map: Map<K, V>, mapEntry: (K, V) -> ?T): [T];

For every entry in the Map, from the last to the first entry (in descending order), calls the provided mapEntry function with (key, value) parameters. Constructs a new array with all non-null mapEntry result items (in the same order mapEntry was called). Skips all null mapEntry result items. Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Rehashing

`rehash`

func rehash<K, V>(map: Map<K, V>, hashUtils: HashUtils<K>): ();

If the Map is empty, returns immediately. Otherwise, allocates additional space, equal to the power of 2 that can hold 8/7 of all current entries (either half, equal or double the current capacity) times 16 bytes. Moves all entries to the new allocated space, while eliminating the holes (unused array indexes). Recalculates the hash table (mapping from a hash to the first entry in a bucket). Recalculates bucket chains (entries that have equal hash % Map size result in a collision and end up in the same bucket). To perform those recalculation, hashes for all keys must also be recalculated.

Requires Hash Utils to be provided as the second argument.

This method is usually called under the hood on inserts (when the Map is full) and deletes (when the Map size is less than 3 / 8 of capacity). It is not necessary to call this method manually under normal conditions.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Set interface description

type Set<K> = [var ?(
  keys: [var ?K],
  indexes: [var Nat],
  bounds: [var Nat32],
)];

Initializing / measuring

`new`

func new<K>(): Set<K>;

Creates and returns an empty Set. Empty Set has a special optimization and takes only 12 bytes of space. The Set structure will be initialized only after the insertion of the first key and will occupy minimum 92 bytes.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`clear`

func clear<K>(set: Set<K>): ();

Removes all keys from the Set.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`size`

func size<K>(set: Set<K>): Nat;

Returns the amount of keys in the Set.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`empty`

func empty<K>(set: Set<K>): Bool;

Returns a boolean indicating whether the Set is empty (has zero keys) or not.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`make`

func make<K>(hashUtils: HashUtils<K>, key: K): Set<K>;

Creates a new Set, initializes it with the single provided key and returns the Set. The minimum amount of space a non-empty Set can occupy is 92 bytes.

Requires Hash Utils to be provided as the first argument.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

Inserting / updating

`put`

func put<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is not present in the Set, inserts it as the last key of the Set and returns false.

If the provided key is present in the Set, does no modifications and returns true.

Requires Hash Utils to be provided as the second argument.

If the Set is empty, on the first insert the Set structure will be initialized which will take additional 80 bytes of space. The minimum amount of space a non-empty Set can occupy is 92 bytes.

Most put calls will not cause any space allocations and will be executed in O(1) time. If the Set is full, on the other hand, and a new key is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (either equal or double the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

Set being full does not necessarily mean size == capacity as on deletion holes (unused array indexes) may (if a deletion happens inside the Set) or may not (if you delete the first or the last key) be created.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`putFront`

func putFront<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is not present in the Set, inserts it as the first key of the Set and returns false.

If the provided key is present in the Set, does no modifications and returns true.

Requires Hash Utils to be provided as the second argument.

Most putFront calls will not cause any space allocations and will be executed in O(1) time. If the Set is full, on the other hand, and a new key is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (either equal or double the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`add`

func add<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): ();

If the provided key is not present in the Set, inserts it as the last key of the Set.

If the provided key is present in the Set, does no modifications.

This operation is the same as put but doesn't have a return value.

Requires Hash Utils to be provided as the second argument.

Most add calls will not cause any space allocations and will be executed in O(1) time. If the Set is full, on the other hand, and a new key is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (either equal or double the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`addFront`

func addFront<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): ();

If the provided key is not present in the Set, inserts it as the first key of the Set.

If the provided key is present in the Set, does no modifications.

This operation is the same as putFront but doesn't have a return value.

Requires Hash Utils to be provided as the second argument.

Most addFront calls will not cause any space allocations and will be executed in O(1) time. If the Set is full, on the other hand, and a new key is about to be inserted, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (either equal or double the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`putMove`

func putMove<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is not present in the Set, inserts it as the last key of the Set and returns false.

If the provided key is present in the Set, moves the key to the back of the Set (if it's not there yet) and returns true.

If the key is being moved from the front to the back, all holes before the new first key will be eliminated and rehash will never happen. If the key is being moved from any non-front position to the back, the hole will be created and rehash may be called (if the Set is full).

Requires Hash Utils to be provided as the second argument.

Most putMove calls will not cause any space allocations and will be executed in O(1) time. If the Set is full, on the other hand, and a new key is about to be inserted (or moved from any non-front position to the back), rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (either equal or double the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`putMoveFront`

func putMoveFront<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is not present in the Set, inserts it as the first key of the Set and returns false.

If the provided key is present in the Set, moves the key to the front of the Set (if it's not there yet) and returns true.

If the key is being moved from the back to the front, all holes after the new last key will be eliminated and rehash will never happen. If the key is being moved from any non-back position to the front, the hole will be created and rehash may be called (if the Set is full).

Requires Hash Utils to be provided as the second argument.

Most putMoveFront calls will not cause any space allocations and will be executed in O(1) time. If the Set is full, on the other hand, and a new key is about to be inserted (or moved from any non-back position to the front), rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (either equal or double the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

Getting

`has`

func has<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is present in the Set, returns true. Otherwise, returns false.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`contains`

func contains<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): ?Bool;

If the Set is empty, returns null.

If the provided key is present in the Set, returns true. Otherwise, returns false (if the Set is not empty).

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Deleting

`remove`

func remove<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): Bool;

If the provided key is not present in the Set, does no modifications and returns false.

If the provided key is present in the Set, removes it from the Set and returns true.

Requires Hash Utils to be provided as the second argument.

If the size of the Set after the deletion is less than 3 / 8 of capacity, rehash will happen, meaning additional space will be allocated, equal to the power of 2 that can hold 8/7 of all current keys (half the current capacity) times 12 bytes, all keys will be moved to the new allocated space, holes will be eliminated and the operation time will be proportional to the Set size.

If rehash is not called and the key is being removed from the front or the back of the Set, all holes before the new first or after the new last key will be eliminated.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`delete`

func delete<K>(set: Set<K>, hashUtils: HashUtils<K>, key: K): ();

If the provided key is not present in the Set, does no modifications.

If the provided key is present in the Set, removes it from the Set.

This operation is the same as remove but doesn't have a return value.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

Performing queue operations

`peek`

func peek<K>(set: Set<K>): ?K;

If the Set is not empty, returns the last key in the Set. Otherwise, returns null.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`peekFront`

func peekFront<K>(set: Set<K>): ?K;

If the Set is not empty, returns the first key in the Set. Otherwise, returns null.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`pop`

func pop<K>(set: Set<K>, hashUtils: HashUtils<K>): ?K;

If the Set is empty, does no modifications and returns null.

If the Set is not empty, removes the last key in the Set and returns it.

Requires Hash Utils to be provided as the second argument.

If rehash is not called, all holes after the new last key will be eliminated.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`popFront`

func popFront<K>(set: Set<K>, hashUtils: HashUtils<K>): ?K;

If the Set is empty, does no modifications and returns null.

If the Set is not empty, removes the first key in the Set and returns it.

Requires Hash Utils to be provided as the second argument.

If rehash is not called, all holes before the new first key will be eliminated.

Complexity
Runtime average	O(1)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`cycle`

func cycle<K>(set: Set<K>, hashUtils: HashUtils<K>): ?K;

If the Set is empty, does no modifications and returns null.

If the Set is not empty, moves the last key in the Set to the front and returns it. All holes after the new last key will be eliminated and rehash will never happen.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`cycleFront`

func cycleFront<K>(set: Set<K>, hashUtils: HashUtils<K>): ?K;

If the Set is empty, does no modifications and returns null.

If the Set is not empty, moves the first key in the Set to the back and returns it. All holes before the new first key will be eliminated and rehash will never happen.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Filtering / cloning

`filter`

func filter<K>(set: Set<K>, hashUtils: HashUtils<K>, acceptKey: (K) -> Bool): Set<K>;

For every key in the Set, from the first to the last key (in ascending order) calls the provided acceptKey function. Constructs a new Set with all keys for which acceptKey returned true (in the same order acceptKey was called). Skips all keys for which acceptKey returned false. Returns the new Set.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`filterDesc`

func filterDesc<K>(set: Set<K>, hashUtils: HashUtils<K>, acceptKey: (K) -> Bool): Set<K>;

For every key in the Set, from the last to the first key (in descending order) calls the provided acceptKey function. Constructs a new Set with all keys for which acceptKey returned true (in the same order acceptKey was called). Skips all keys for which acceptKey returned false. Returns the new Set.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`clone`

func clone<K>(set: Set<K>): Set<K>;

Iterates through the Set from the first to the last key (in ascending order) and copies each key into the new Set (in the order of iteration). Returns the new Set.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`cloneDesc`

func cloneDesc<K>(set: Set<K>): Set<K>;

Iterates through the Set from the last to the first key (in descending order) and copies each key into the new Set (in the order of iteration). Returns the new Set.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Iterating

`keys`

func keys<K>(set: Set<K>): Iter<K>;

Creates an iterator object over the keys of the Set which starts at the first key and ends at the last key. The iterator can be used to iterate over all keys of the Set with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

All Set iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`keysDesc`

func keysDesc<K>(set: Set<K>): Iter<K>;

Creates an iterator object over the keys of the Set which starts at the last key and ends at the first key. The iterator can be used to iterate over all keys of the Set with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`keysFrom`

func keysFrom<K>(set: Set<K>, hashUtils: HashUtils<K>, key: ?K): Iter<K>;

If the optional key parameter is present, performs a search for it in the Set. Creates an iterator object over the keys of the Set which starts at the key after the found key (if the optional key parameter is present and found) or the first key (if the optional key parameter is either not present or not found) and ends at the last key. The iterator can be used to iterate over all keys of the Set after the specified key with for in loop in ascending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Requires Hash Utils to be provided as the second argument.

All Set iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the first key and not to the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`keysFromDesc`

func keysFromDesc<K>(set: Set<K>, hashUtils: HashUtils<K>, key: ?K): Iter<K>;

If the optional key parameter is present, performs a search for it in the Set. Creates an iterator object over the keys of the Set which starts at the key before the found key (if the optional key parameter is present and found) or the last key (if the optional key parameter is either not present or not found) and ends at the first key. The iterator can be used to iterate over all keys of the Set before the specified key with for in loop in descending order. Or you can call any method on the iterator object directly. The interface of an iterator object is described in the section Iterator interface description.

Note that after the iterator creation, the current key will indeed be the found key (if it is found). But it will be omitted by for in loop so the iteration begins from the key right before it. This behavior can bit changed and the found key can be included in the iteration by calling movePrev after the iterator creation.

Requires Hash Utils to be provided as the second argument.

All Set iterators are reusable, meaning after returning null once (at the end of iteration), iterators end up in their initial state (initial state in this case corresponds to the last key and not to the found key) and a new iteration cycle can be started without creating a new iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Searching

`find`

func find<K>(set: Set<K>, acceptKey: (K) -> Bool): ?K;

For every key in the Set, from the first to the last key (in ascending order) calls the provided acceptKey function until the acceptKey function returns true. If true is returned, returns the current key immediately. If acceptKey didn't return true for any key, returns null.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`findDesc`

func findDesc<K>(set: Set<K>, acceptKey: (K) -> Bool): ?K;

For every key in the Set, from the last to the first key (in descending order) calls the provided acceptKey function until the acceptKey function returns true. If true is returned, returns the current key immediately. If acceptKey didn't return true for any key, returns null.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`some`

func some<K>(set: Set<K>, acceptKey: (K) -> Bool): Bool;

For every key in the Set, from the first to the last key (in ascending order) calls the provided acceptKey function until the acceptKey function returns true. If true is returned, returns true immediately. If acceptKey didn't return true for any key, returns false.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`someDesc`

func someDesc<K>(set: Set<K>, acceptKey: (K) -> Bool): Bool;

For every key in the Set, from the last to the first key (in descending order) calls the provided acceptKey function until the acceptKey function returns true. If true is returned, returns true immediately. If acceptKey didn't return true for any key, returns false.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`every`

func every<K>(set: Set<K>, acceptKey: (K) -> Bool): Bool;

For every key in the Set, from the first to the last key (in ascending order) calls the provided acceptKey function until the acceptKey function returns false. If false is returned, returns false immediately. If acceptKey didn't return false for any key, returns true.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`everyDesc`

func everyDesc<K>(set: Set<K>, acceptKey: (K) -> Bool): Bool;

For every key in the Set, from the last to the first key (in descending order) calls the provided acceptKey function until the acceptKey function returns false. If false is returned, returns false immediately. If acceptKey didn't return false for any key, returns true.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`forEach`

func forEach<K>(set: Set<K>, mapKey: (K) -> ()): ();

For every key in the Set, from the first to the last key (in ascending order) calls the provided mapKey function.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`forEachDesc`

func forEachDesc<K>(set: Set<K>, mapKey: (K) -> ()): ();

For every key in the Set, from the last to the first key (in descending order) calls the provided mapKey function.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

Constructing from iterators

`fromIter`

func fromIter<K>(iter: IterNext<K>, hashUtils: HashUtils<K>): Set<K>;

Creates a new empty Set. For every key in the iterator, inserts the key at the back of the Set if the key is not present in the Set. If the key is present in the Set, moves the key to the back of the Set (if it's not there yet). Returns the new Set.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`fromIterDesc`

func fromIterDesc<K>(iter: IterNext<K>, hashUtils: HashUtils<K>): Set<K>;

Creates a new empty Set. For every key in the iterator, inserts the key at the front of the Set if the key is not present in the Set. If the key is present in the Set, moves the key to the front of the Set (if it's not there yet). Returns the new Set.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`fromIterMap`

func fromIterMap<K, T>(iter: IterNext<T>, hashUtils: HashUtils<K>, mapItem: (T) -> ?K): Set<K>;

Creates a new empty Set. For every item in the iterator, calls the provided mapItem function. For every item mapItem returned a key for, inserts the key at the back of the Set if the key is not present in the Set. If the key is present in the Set, moves the key to the back of the Set (if it's not there yet). Skips all items mapItem returned null for. Returns the new Set.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`fromIterMapDesc`

func fromIterMapDesc<K, T>(iter: IterNext<T>, hashUtils: HashUtils<K>, mapItem: (T) -> ?K): Set<K>;

Creates a new empty Set. For every item in the iterator, calls the provided mapItem function. For every item mapItem returned a key for, inserts the key at the front of the Set if the key is not present in the Set. If the key is present in the Set, moves the key to the front of the Set (if it's not there yet). Skips all items mapItem returned null for. Returns the new Set.

Requires Hash Utils to be provided as the second argument.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Converting to arrays

`toArray`

func toArray<K>(set: Set<K>): [K];

Constructs a new array with all keys present in the Set, from the first to the last key (in ascending order). Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`toArrayDesc`

func toArrayDesc<K>(set: Set<K>): [K];

Constructs a new array with all keys present in the Set, from the last to the first key (in descending order). Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`toArrayMap`

func toArrayMap<K, T>(set: Set<K>, mapKey: (K) -> ?T): [T];

For every key in the Set, from the first to the last key (in ascending order), calls the provided mapKey function. Constructs a new array with all non-null mapKey result items (in the same order mapKey was called). Skips all null mapKey result items. Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

`toArrayMapDesc`

func toArrayMapDesc<K, T>(set: Set<K>, mapKey: (K) -> ?T): [T];

For every key in the Set, from the last to the first key (in descending order), calls the provided mapKey function. Constructs a new array with all non-null mapKey result items (in the same order mapKey was called). Skips all null mapKey result items. Returns the array.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Rehashing

`rehash`

func rehash<K>(set: Set<K>, hashUtils: HashUtils<K>): ();

If the Set is empty, returns immediately. Otherwise, allocates additional space, equal to the power of 2 that can hold 8/7 of all current keys (either half, equal or double the current capacity) times 12 bytes. Moves all keys to the new allocated space, while eliminating the holes (unused array indexes). Recalculates the hash table (mapping from a hash to the first key in a bucket). Recalculates bucket chains (keys that have equal hash % Set size result in a collision and end up in the same bucket). To perform those recalculation, hashes for all keys must also be recalculated.

Requires Hash Utils to be provided as the second argument.

This method is usually called under the hood on inserts (when the Set is full) and deletes (when the Set size is less than 3 / 8 of capacity). It is not necessary to call this method manually under normal conditions.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(n)
Space max	O(n)

Iterator interface description

type Iter<T> = {
  prev: () -> ?T;
  next: () -> ?T;
  peekPrev: () -> ?T;
  peekNext: () -> ?T;
  movePrev: () -> Iter<T>;
  moveNext: () -> Iter<T>;
  current: () -> ?T;
  started: () -> Bool;
  finished: () -> Bool;
  reset: () -> Iter<T>;
};

Moving a pointer

`prev`

func prev(): ?K;

func prev(): ?V;

func prev(): ?(K, V);

Sets the started flag to true. If the Map/Set is empty, returns null. Otherwise, moves the iterator pointer to the previous key/value/entry for ascending iterators and to the next key/value/entry for descending iterators and saves the pointer position in the iterator object. If the current entry before the pointer move was the first entry for ascending iterators or the last entry for descending iterators, the iterator ends up in its initial position and in the finished state, the new iteration cycle can be started and the method returns null. Otherwise returns the key/value/entry which becomes current after a pointer move.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`next`

func next(): ?K;

func next(): ?V;

func next(): ?(K, V);

Sets the started flag to true. If the Map/Set is empty, returns null. Otherwise, moves the iterator pointer to the next key/value/entry for ascending iterators and to the previous key/value/entry for descending iterators and saves the pointer position in the iterator object. If the current entry before the pointer move was the last entry for ascending iterators or the first entry for descending iterators, the iterator ends up in its initial position and in the finished state, the new iteration cycle can be started and the method returns null. Otherwise returns the key/value/entry which becomes current after a pointer move.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`peekPrev`

func peekPrev(): ?K;

func peekPrev(): ?V;

func peekPrev(): ?(K, V);

If the Map/Set is empty, returns null. Otherwise, moves the iterator pointer to the previous key/value/entry for ascending iterators and to the next key/value/entry for descending iterators but doesn't save the pointer position in the iterator object. If the current entry before the pointer move was the first entry for ascending iterators or the last entry for descending iterators, returns null. Otherwise returns the key/value/entry which becomes current after a pointer move.

This operation is the same as prev but doesn't save the pointer position, meaning the return value will be the same but the iterator object state won't change after the operation. It also doesn't change the started flag.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`peekNext`

func peekNext(): ?K;

func peekNext(): ?V;

func peekNext(): ?(K, V);

If the Map/Set is empty, returns null. Otherwise, moves the iterator pointer to the next key/value/entry for ascending iterators and to the previous key/value/entry for descending iterators but doesn't save the pointer position in the iterator object. If the current entry before the pointer move was the last entry for ascending iterators or the first entry for descending iterators, returns null. Otherwise returns the key/value/entry which becomes current after a pointer move.

This operation is the same as next but doesn't save the pointer position, meaning the return value will be the same but the iterator object state won't change after the operation. It also doesn't change the started flag.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`movePrev`

func movePrev(): Iter<K>;

func movePrev(): Iter<V>;

func movePrev(): Iter<(K, V)>;

Sets the started flag to true. If the Map/Set is empty, returns the iterator object. Otherwise, moves the iterator pointer to the previous key/value/entry for ascending iterators and to the next key/value/entry for descending iterators and saves the pointer position in the iterator object. If the current entry before the pointer move was the first entry for ascending iterators or the last entry for descending iterators, the iterator ends up in its initial position and in the finished state and the new iteration cycle can be started. Returns the iterator object.

This operation is the same as prev but always returns the iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

`moveNext`

func moveNext(): Iter<K>;

func moveNext(): Iter<V>;

func moveNext(): Iter<(K, V)>;

Sets the started flag to true. If the Map/Set is empty, returns the iterator object. Otherwise, moves the iterator pointer to the next key/value/entry for ascending iterators and to the previous key/value/entry for descending iterators and saves the pointer position in the iterator object. If the current entry before the pointer move was the last entry for ascending iterators or the first entry for descending iterators, the iterator ends up in its initial position and in the finished state and the new iteration cycle can be started. Returns the iterator object.

This operation is the same as next but always returns the iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(n) unlikely under normal conditions
Space average	O(1)
Space max	O(1)

Getting current item

`current`

func current(): ?K;

func current(): ?V;

func current(): ?(K, V);

If the Map/Set is empty or the iterator is in its initial position, returns null, otherwise returns the current key/value/entry.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

Getting iterator state

`started`

func started(): Bool;

Returns true if any prev/next/movePrev/moveNext method was called after the iterator object was created or reset with the reset method. Otherwise, returns false.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`finished`

func finished(): Bool;

Returns true if the iterator was started (meaning any prev/next/movePrev/moveNext method was called after the iterator object was created or reset with the reset method) and is currently in its initial position. Otherwise, returns false.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

Resetting

`reset`

func reset(): Iter<K>;

func reset(): Iter<V>;

func reset(): Iter<(K, V)>;

Resets the started flag to false. Resets the iterator to its initial position. Returns the iterator object.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

Hash Utils

type HashUtils<K> = (
  getHash: (K) -> Nat32,
  areEqual: (K, K) -> Bool,
);

Calculating hashes

`hashInt`

func hashInt(key: Int): Nat32;

Truncates the key to a 64 bit unsigned integer. Calculates the hash using a 64 bit variant of the Multiply-Xorshift hashing technique. Truncates the hash to a 32 bit unsigned integer. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of ihash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashInt8`

func hashInt8(key: Int8): Nat32;

Converts the key to a 32 bit unsigned integer. Calculates the hash using a 32 bit variant of the Multiply-Xorshift hashing technique. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of i8hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashInt16`

func hashInt16(key: Int16): Nat32;

This function is exposed separately, although most of the time you will be using it as a part of i16hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashInt32`

func hashInt32(key: Int32): Nat32;

This function is exposed separately, although most of the time you will be using it as a part of i32hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashInt64`

func hashInt64(key: Int64): Nat32;

Converts the key to a 64 bit unsigned integer. Calculates the hash using a 64 bit variant of the Multiply-Xorshift hashing technique. Truncates the hash to a 32 bit unsigned integer. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of i64hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashNat`

func hashNat(key: Nat): Nat32;

This function is exposed separately, although most of the time you will be using it as a part of nhash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashNat8`

func hashNat8(key: Nat8): Nat32;

This function is exposed separately, although most of the time you will be using it as a part of n8hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashNat16`

func hashNat16(key: Nat16): Nat32;

This function is exposed separately, although most of the time you will be using it as a part of n16hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashNat32`

func hashNat32(key: Nat32): Nat32;

Calculates the hash using a 32 bit variant of the Multiply-Xorshift hashing technique. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of n32hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashNat64`

func hashNat64(key: Nat64): Nat32;

Calculates the hash using a 64 bit variant of the Multiply-Xorshift hashing technique. Truncates the hash to a 32 bit unsigned integer. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of n64hash.

Prospecting for Hash Functions

New best known functions

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashText`

func hashText(key: Text): Nat32;

Converts the key to a UTF-8 encoded blob. Calculates the hash using the internal hash function for blob, which is based on the CRC32 algorithm. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of thash.

NOTE: Currently, this is the only hash function in the library that can (occasionally) allocate additional temporary space. Allocation happens at the text to blob conversion step (when the internal text representation consists of multiple substrings). This will be a subject to change when we have optimized for in text iteration that does not create an iterator object under the hood.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(n)

`hashPrincipal`

func hashPrincipal(key: Principal): Nat32;

Converts the key to blob. Calculates the hash using the internal hash function for blob, which is based on the CRC32 algorithm. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of phash.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`hashBlob`

func hashBlob(key: Blob): Nat32;

Calculates the hash using the internal hash function for blob, which is based on the CRC32 algorithm. Drops 2 most significant bits of the hash to prevent it going to the heap. Returns the hash.

This function is exposed separately, although most of the time you will be using it as a part of bhash.

Complexity
Runtime average	O(n)
Runtime max	O(n)
Space average	O(1)
Space max	O(1)

`hashBool`

func hashBool(key: Bool): Nat32;

Returns numeric alternatives for true and false values.

This function is exposed separately, although most of the time you will be using it as a part of lhash.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

Composite utils

`ihash`

let ihash: HashUtils<Int> = (hashInt, areEqual);

Composite utils for Int keys that allow calculating hashes using hashInt function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`i8hash`

let i8hash: HashUtils<Int8> = (hashInt8, areEqual);

Composite utils for Int8 keys that allow calculating hashes using hashInt8 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`i16hash`

let i16hash: HashUtils<Int16> = (hashInt16, areEqual);

Composite utils for Int16 keys that allow calculating hashes using hashInt16 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`i32hash`

let i32hash: HashUtils<Int32> = (hashInt32, areEqual);

Composite utils for Int32 keys that allow calculating hashes using hashInt32 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`i64hash`

let i64hash: HashUtils<Int64> = (hashInt64, areEqual);

Composite utils for Int64 keys that allow calculating hashes using hashInt64 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`nhash`

let nhash: HashUtils<Nat> = (hashNat, areEqual);

Composite utils for Nat keys that allow calculating hashes using hashNat function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`n8hash`

let n8hash: HashUtils<Nat8> = (hashNat8, areEqual);

Composite utils for Nat8 keys that allow calculating hashes using hashNat8 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`n16hash`

let n16hash: HashUtils<Nat16> = (hashNat16, areEqual);

Composite utils for Nat16 keys that allow calculating hashes using hashNat16 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`n32hash`

let n32hash: HashUtils<Nat32> = (hashNat32, areEqual);

Composite utils for Nat32 keys that allow calculating hashes using hashNat32 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`n64hash`

let n64hash: HashUtils<Nat64> = (hashNat64, areEqual);

Composite utils for Nat64 keys that allow calculating hashes using hashNat64 function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`thash`

let thash: HashUtils<Text> = (hashText, areEqual);

Composite utils for Text keys that allow calculating hashes using hashText function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`phash`

let phash: HashUtils<Principal> = (hashPrincipal, areEqual);

Composite utils for Principal keys that allow calculating hashes using hashPrincipal function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`bhash`

let bhash: HashUtils<Blob> = (hashBlob, areEqual);

Composite utils for Blob keys that allow calculating hashes using hashBlob function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

`lhash`

let lhash: HashUtils<Bool> = (hashBool, areEqual);

Composite utils for Bool keys that allow calculating hashes using hashBool function and checking equality.

A lot of Map/Set methods require Hash Utils to be provided with each call.

Constructing new utils

`combineHash`

func combineHash<K1, K2>(hashUtils1: HashUtils<K1>, hashUtils2: HashUtils<K2>): HashUtils<(K1, K2)>;

Constructs new Hash Utils capable of handling composite keys (tuples of 2 components). Takes 2 Hash Utils as an input which will handle the first and the second component of a composite key separately. The combined Hash Utils will handle the merging of both hashes and ensuring that equality function returns true only when both components are equal. Returns the new Hash Utils.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`useHash`

func useHash<K>(hashUtils: HashUtils<K>, hash: Nat32): HashUtils<K>;

Constructs new Hash Utils with its hashing component being a function that returns a constant hash provided as a second argument and its equality component equal to the provided Hash Utils. Returns the new Hash Utils.

WARNING: Incorrect usage of this function can result in a corrupted Map/Set state.

Complexity
Runtime average	O(1)
Runtime max	O(1)
Space average	O(1)
Space max	O(1)

`calcHash`

func calcHash<K>(hashUtils: HashUtils<K>, key: K): HashUtils<K>;

Constructs new Hash Utils with its hashing component being a function that returns a constant hash calculated from the provided key and its equality component equal to the provided Hash Utils. Returns the new Hash Utils.

WARNING: Incorrect usage of this function can result in a corrupted Map/Set state.

Complexity
Runtime average	depends on arguments
Runtime max	depends on arguments
Space average	depends on arguments
Space max	depends on arguments

ZhenyaUsenko / motoko-hash-map

readme

Table of contents