SortedMap

Usage

use SortedMap;

or

import SortedMap;

Provides the ‘sortedMap’ type for storing sorted 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.

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

record sortedMap : writeSerializable

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 = new DefaultComparator()

The comparator used to compare keys

proc init(type keyType, type valType, param parSafe = false, comparator: record = new 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 ref 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 ref 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  where isDefaultInitializable(valType)

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 ref getBorrowed(k: keyType)  where isClass(valType)

Get a borrowed reference to the element at position k.

proc ref getReference(k: keyType) ref  where !isNonNilableClass(valType)

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 ref 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()

Iterates over the key-value pairs of this sortedMap.

Yields:

A tuple whose elements are a copy of one of the key-value pairs contained in this map.

iter values() ref

Iterates over the values of this sortedMap.

Yields:

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

proc ref 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 ref 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 ref addOrReplace(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 ref 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

operator 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.

operator 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

operator 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

operator 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.

operator 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.

operator 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.

operator 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.

operator 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.

operator 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.

operator 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.

operator 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.

operator 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.

operator 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.