SortedMap¶

Usage

use SortedMap;

or

import SortedMap;

This module contains the implementation of the sortedMap type which is a container that stores key-value associations.

sortedMaps are not parallel safe by default, but can be made parallel safe by setting the param formal parSafe to true in any sortedMap constructor. When constructed from another sortedMap, the new sortedMap will inherit the parallel safety mode of its originating sortedMap.

SortedSet supports searching for a certain key, insertion and deletion in O(logN).

record sortedMap¶

type keyType¶: Type of sortedMap keys.

type valType¶: Type of sortedMap values.

param parSafe = false¶: If true, this sortedMap will perform parallel safe operations.

var comparator: record = defaultComparator¶: The comparator used to compare keys

proc init(type keyType, type valType, param parSafe = false, comparator: record = defaultComparator)¶

Initializes an empty sortedMap containing keys and values of given types.

Arguments

keyType – The type of the keys of this sortedMap.
valType – The type of the values of this sortedMap.
parSafe : bool – If true, this sortedMap will use parallel safe operations.
comparator – The comparator used to compare keys.

proc init=(const ref other: sortedMap(?kt, ?vt))¶

Initialize this sortedMap with a copy of each of the elements contained in the sortedMap other. This sortedMap will inherit the parSafe value of the sortedMap other.

Arguments: other – An sortedMap to initialize this sortedMap with.

proc clear()¶: Clears the contents of this sortedMap.

Warning

Clearing the contents of this sortedMap will invalidate all existing references to the elements contained in this sortedMap.

proc size¶: The current number of keys contained in this sortedMap.

proc isEmpty(): bool¶

Returns true if this sortedMap contains zero keys.

Returns: true if this sortedMap is empty.
Return type: bool

proc contains(const k: keyType): bool¶

Returns true if the given key is a member of this sortedMap, and false otherwise.

Arguments: k : keyType – The key to test for membership.
Returns: Whether or not the given key is a member of this sortedMap.
Return type: bool

proc update(other: sortedMap(keyType, valType, ?p))¶

Updates this sortedMap with the contents of the other, overwriting the values for already-existing keys.

Arguments: other – The other sortedMap

proc ref this(k: keyType) ref

Get the value mapped to the given key, or add the mapping if key does not exist.

Arguments: k : keyType – The key to access
Returns: Reference to the value mapped to the given key.

proc getBorrowed(k: keyType)¶: Get a borrowed reference to the element at position k.

proc getReference(k: keyType) ref¶: Get a reference to the element at position k. This method is not available for non-nilable types.

proc getValue(k: keyType)¶: Get a copy of the element stored at position k. This method is only available when a sortedMap’s valType is a non-nilable class.

proc getAndRemove(k: keyType)¶: Remove the element at position k from the sortedMap and return its value

iter these() const ref¶

Iterates over the keys of this sortedMap. This is a shortcut for keys.

Yields: A reference to one of the keys contained in this sortedMap.

iter keys() const ref¶

Iterates over the keys of this sortedMap.

Yields: A reference to one of the keys contained in this sortedMap.

iter items() const ref¶

Iterates over the key-value pairs of this sortedMap.

Yields: A tuple of references to one of the key-value pairs contained in this sortedMap.

iter values() ref¶

Iterates over the values of this sortedMap.

Yields: A reference to one of the values contained in this sortedMap.

proc writeThis(ch: channel) throws¶

Writes the contents of this sortedMap to a channel. The format looks like:

{k1: v1, k2: v2, .... , kn: vn}

Arguments: ch – A channel to write to.

proc add(in k: keyType, in v: valType): bool¶

Adds a key-value pair to the sortedMap. Method returns false if the key already exists in the sortedMap.

Arguments

k : keyType – The key to add to the sortedMap
v : valueType – The value that maps to k

Returns

true if k was not in the sortedMap and added with value v. false otherwise.

Return type

bool

proc set(k: keyType, in v: valType): bool¶

Sets the value associated with a key. Method returns false if the key does not exist in the sortedMap.

Arguments

k : keyType – The key whose value needs to change
v : valueType – The desired value to the key k

Returns

true if k was in the sortedMap and its value is updated with v. false otherwise.

Return type

bool

proc addOrSet(in k: keyType, in v: valType)¶: If the sortedMap doesn’t contain a value at position k add one and set it to v. If the sortedMap already contains a value at position k, update it to the value v.

proc remove(k: keyType): bool¶

Removes a key-value pair from the sortedMap, with the given key.

Arguments: k – The key to remove from the sortedMap
Returns: false if k was not in the sortedMap. true if it was and removed.
Return type: bool

proc toArray(): [] (keyType, valType)¶

Returns a new 0-based array containing a copy of key-value pairs as tuples.

Returns: A new DefaultRectangular array.
Return type: [] (keyType, valType)

proc keysToArray(): [] keyType¶

Returns a new 0-based array containing a copy of keys. Array is sorted using the comparator.

Returns: A new DefaultRectangular array.
Return type: [] keyType

proc valuesToArray(): [] valType¶

Returns a new 0-based array containing a copy of values. Array is not guaranteed to be in any particular order.

Returns: A new DefaultRectangular array.
Return type: [] valType

proc type sortedMap.=(ref lhs: sortedMap(?kt, ?vt, ?ps), const ref rhs: sortedMap(kt, vt, ps))¶

Replace the content of this sortedMap with the other’s.

Warning

This will invalidate any references to elements previously contained in lhs.

Arguments

lhs – The sortedMap to assign to.
rhs – The sortedMap to assign from.

proc type sortedMap.==(const ref a: sortedMap(?kt, ?vt, ?ps), const ref b: sortedMap(kt, vt, ps)): bool¶

Returns true if the contents of two sortedMaps are the same.

Arguments

a – A sortedMap to compare.
b – A sortedMap to compare.

Returns

true if the contents of two sortedMaps are equal.

Return type

bool

proc type sortedMap.!=(const ref a: sortedMap(?kt, ?vt, ?ps), const ref b: sortedMap(kt, vt, ps)): bool¶

Returns true if the contents of two sortedMaps are not the same.

Arguments

a – A sortedMap to compare.
b – A sortedMap to compare.

Returns

true if the contents of two sortedMaps are not equal.

Return type

bool

proc type sortedMap.+(a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe))¶: Returns a new sortedMap containing the keys and values in either a or b.

proc type sortedMap.+=(ref a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe))¶: Sets the left-hand side sortedMap to contain the keys and values in either a or b.

proc type sortedMap.|(a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe)): Returns a new sortedMap containing the keys and values in either a or b.

proc type sortedMap.|=(ref a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe)): Sets the left-hand side map to contain the keys and values in either a or b.

proc type sortedMap.&(a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe)): Returns a new sortedMap containing the keys that are in both a and b.

proc type sortedMap.&=(ref a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe)): Sets the left-hand side sortedMap to contain the keys that are in both a and b.

Warning

This will invalidate any references to elements previously contained in lhs.

proc type sortedMap.-(a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe))¶: Returns a new sortedMap containing the keys that are only in a, but not b.

proc type sortedMap.-=(ref a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe))¶: Sets the left-hand side sortedMap to contain the keys that are in the left-hand sortedMap, but not the right-hand sortedMap.

proc type sortedMap.^(a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe)): Returns a new sortedMap containing the keys that are in either a or b, but not both.

proc type sortedMap.^=(ref a: sortedMap(?keyType, ?valueType, ?parSafe), b: sortedMap(keyType, valueType, parSafe)): Sets the left-hand side sortedMap to contain the keys that are in either the left-hand sortedMap or the right-hand sortedMap, but not both.