simple_map - [mainnet]

This module provides a solution for unsorted maps, that is it has the properties that

Keys point to Values
Each Key must be unique
A Key can be found within O(N) time
The keys are unsorted.
Adds and removals take O(N) time

DEPRECATED: since it’s implementation is inneficient, it has been deprecated in favor of ordered_map.move.

use 0x1::error;
use 0x1::option;
use 0x1::vector;

Constants

Map key already exists

const EKEY_ALREADY_EXISTS: u64 = 1;

Map key is not found

const EKEY_NOT_FOUND: u64 = 2;

Structs

`SimpleMap`

DEPRECATED: since it’s implementation is inneficient, it has been deprecated in favor of ordered_map.move.

struct SimpleMap<Key, Value> has copy, drop, store

Fields

data: vector<simple_map::Element<Key, Value>>

`Element`

struct Element<Key, Value> has copy, drop, store

Fields

key: Key
value: Value

Functions

`length`

public fun length<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>): u64

Implementation

public fun length<Key: store, Value: store>(self: &SimpleMap<Key, Value>): u64 {
    self.data.length()
}

`new`

Create an empty SimpleMap.

public fun new<Key: store, Value: store>(): simple_map::SimpleMap<Key, Value>

Implementation

public fun new<Key: store, Value: store>(): SimpleMap<Key, Value> {
    SimpleMap {
        data: vector::empty(),
    }
}

`new_from`

Create a SimpleMap from a vector of keys and values. The keys must be unique.

public fun new_from<Key: store, Value: store>(keys: vector<Key>, values: vector<Value>): simple_map::SimpleMap<Key, Value>

Implementation

public fun new_from<Key: store, Value: store>(
    keys: vector<Key>,
    values: vector<Value>,
): SimpleMap<Key, Value> {
    let map = new();
    map.add_all(keys, values);
    map
}

`create`

Create an empty SimpleMap. This function is deprecated, use new instead.

#[deprecated]
public fun create<Key: store, Value: store>(): simple_map::SimpleMap<Key, Value>

Implementation

public fun create<Key: store, Value: store>(): SimpleMap<Key, Value> {
    new()
}

`borrow`

public fun borrow<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>, key: &Key): &Value

Implementation

public fun borrow<Key: store, Value: store>(
    self: &SimpleMap<Key, Value>,
    key: &Key,
): &Value {
    let maybe_idx = self.find(key);
    assert!(maybe_idx.is_some(), error::invalid_argument(EKEY_NOT_FOUND));
    let idx = maybe_idx.extract();
    &self.data.borrow(idx).value
}

`borrow_mut`

public fun borrow_mut<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: &Key): &mut Value

Implementation

public fun borrow_mut<Key: store, Value: store>(
    self: &mut SimpleMap<Key, Value>,
    key: &Key,
): &mut Value {
    let maybe_idx = self.find(key);
    assert!(maybe_idx.is_some(), error::invalid_argument(EKEY_NOT_FOUND));
    let idx = maybe_idx.extract();
    &mut self.data.borrow_mut(idx).value
}

`contains_key`

public fun contains_key<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>, key: &Key): bool

Implementation

public fun contains_key<Key: store, Value: store>(
    self: &SimpleMap<Key, Value>,
    key: &Key,
): bool {
    let maybe_idx = self.find(key);
    maybe_idx.is_some()
}

`destroy_empty`

public fun destroy_empty<Key: store, Value: store>(self: simple_map::SimpleMap<Key, Value>)

Implementation

public fun destroy_empty<Key: store, Value: store>(self: SimpleMap<Key, Value>) {
    let SimpleMap { data } = self;
    data.destroy_empty();
}

`add`

Add a key/value pair to the map. The key must not already exist.

public fun add<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: Key, value: Value)

Implementation

public fun add<Key: store, Value: store>(
    self: &mut SimpleMap<Key, Value>,
    key: Key,
    value: Value,
) {
    let maybe_idx = self.find(&key);
    assert!(maybe_idx.is_none(), error::invalid_argument(EKEY_ALREADY_EXISTS));

    self.data.push_back(Element { key, value });
}

`add_all`

Add multiple key/value pairs to the map. The keys must not already exist.

public fun add_all<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, keys: vector<Key>, values: vector<Value>)

Implementation

public fun add_all<Key: store, Value: store>(
    self: &mut SimpleMap<Key, Value>,
    keys: vector<Key>,
    values: vector<Value>,
) {
    keys.zip(values, |key, value| {
        self.add(key, value);
    });
}

`upsert`

Insert key/value pair or update an existing key to a new value

public fun upsert<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: Key, value: Value): (option::Option<Key>, option::Option<Value>)

Implementation

public fun upsert<Key: store, Value: store>(
    self: &mut SimpleMap<Key, Value>,
    key: Key,
    value: Value
): (std::option::Option<Key>, std::option::Option<Value>) {
    let data = &mut self.data;
    let len = data.length();
    for (i in 0..len) {
        let element = data.borrow(i);
        if (&element.key == &key) {
            data.push_back(Element { key, value });
            data.swap(i, len);
            let Element { key, value } = data.pop_back();
            return (std::option::some(key), std::option::some(value))
        };
    };
    self.data.push_back(Element { key, value });
    (std::option::none(), std::option::none())
}

`keys`

Return all keys in the map. This requires keys to be copyable.

public fun keys<Key: copy, Value>(self: &simple_map::SimpleMap<Key, Value>): vector<Key>

Implementation

public fun keys<Key: copy, Value>(self: &SimpleMap<Key, Value>): vector<Key> {
    self.data.map_ref(|e| {
        e.key
    })
}

`values`

Return all values in the map. This requires values to be copyable.

public fun values<Key, Value: copy>(self: &simple_map::SimpleMap<Key, Value>): vector<Value>

Implementation

public fun values<Key, Value: copy>(self: &SimpleMap<Key, Value>): vector<Value> {
    self.data.map_ref(|e| {
        e.value
    })
}

`to_vec_pair`

Transform the map into two vectors with the keys and values respectively Primarily used to destroy a map

public fun to_vec_pair<Key: store, Value: store>(self: simple_map::SimpleMap<Key, Value>): (vector<Key>, vector<Value>)

Implementation

public fun to_vec_pair<Key: store, Value: store>(
    self: SimpleMap<Key, Value>): (vector<Key>, vector<Value>) {
    let keys: vector<Key> = vector::empty();
    let values: vector<Value> = vector::empty();
    let SimpleMap { data } = self;
    data.for_each(|e| {
        let Element { key, value } = e;
        keys.push_back(key);
        values.push_back(value);
    });
    (keys, values)
}

`destroy`

For maps that cannot be dropped this is a utility to destroy them using lambdas to destroy the individual keys and values.

public fun destroy<Key: store, Value: store>(self: simple_map::SimpleMap<Key, Value>, dk: |Key|, dv: |Value|)

Implementation

public inline fun destroy<Key: store, Value: store>(
    self: SimpleMap<Key, Value>,
    dk: |Key|,
    dv: |Value|
) {
    let (keys, values) = self.to_vec_pair();
    keys.destroy(|_k| dk(_k));
    values.destroy(|_v| dv(_v));
}

`remove`

Remove a key/value pair from the map. The key must exist.

public fun remove<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: &Key): (Key, Value)

Implementation

public fun remove<Key: store, Value: store>(
    self: &mut SimpleMap<Key, Value>,
    key: &Key,
): (Key, Value) {
    let maybe_idx = self.find(key);
    assert!(maybe_idx.is_some(), error::invalid_argument(EKEY_NOT_FOUND));
    let placement = maybe_idx.extract();
    let Element { key, value } = self.data.swap_remove(placement);
    (key, value)
}

`find`

fun find<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>, key: &Key): option::Option<u64>

Implementation

fun find<Key: store, Value: store>(
    self: &SimpleMap<Key, Value>,
    key: &Key,
): option::Option<u64> {
    let len = self.data.length();
    for (i in 0..len) {
        let element = self.data.borrow(i);
        if (&element.key == key) {
            return option::some(i)
        };
    };
    option::none<u64>()
}

Specification

`SimpleMap`

struct SimpleMap<Key, Value> has copy, drop, store

data: vector<simple_map::Element<Key, Value>>

pragma intrinsic = map,
    map_new = create,
    map_len = length,
    map_destroy_empty = destroy_empty,
    map_has_key = contains_key,
    map_add_no_override = add,
    map_del_return_key = remove,
    map_borrow = borrow,
    map_borrow_mut = borrow_mut,
    map_spec_get = spec_get,
    map_spec_set = spec_set,
    map_spec_del = spec_remove,
    map_spec_len = spec_len,
    map_spec_has_key = spec_contains_key;

`length`

public fun length<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>): u64

pragma intrinsic;

`new`

public fun new<Key: store, Value: store>(): simple_map::SimpleMap<Key, Value>

pragma intrinsic;
pragma opaque;
aborts_if [abstract] false;
ensures [abstract] spec_len(result) == 0;
ensures [abstract] forall k: Key: !spec_contains_key(result, k);

`new_from`

public fun new_from<Key: store, Value: store>(keys: vector<Key>, values: vector<Value>): simple_map::SimpleMap<Key, Value>

pragma intrinsic;
pragma opaque;
aborts_if [abstract] false;
ensures [abstract] spec_len(result) == len(keys);
ensures [abstract] forall k: Key: spec_contains_key(result, k) <==> vector::spec_contains(keys, k);
ensures [abstract] forall i in 0..len(keys):
    spec_get(result, keys.borrow(i)) == values.borrow(i);

`create`

#[deprecated]
public fun create<Key: store, Value: store>(): simple_map::SimpleMap<Key, Value>

pragma intrinsic;

`borrow`

public fun borrow<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>, key: &Key): &Value

pragma intrinsic;

`borrow_mut`

public fun borrow_mut<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: &Key): &mut Value

pragma intrinsic;

`contains_key`

public fun contains_key<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>, key: &Key): bool

pragma intrinsic;

`destroy_empty`

public fun destroy_empty<Key: store, Value: store>(self: simple_map::SimpleMap<Key, Value>)

pragma intrinsic;

`add`

public fun add<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: Key, value: Value)

pragma intrinsic;

`add_all`

public fun add_all<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, keys: vector<Key>, values: vector<Value>)

pragma intrinsic;

`upsert`

public fun upsert<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: Key, value: Value): (option::Option<Key>, option::Option<Value>)

pragma intrinsic;
pragma opaque;
aborts_if [abstract] false;
ensures [abstract] !spec_contains_key(old(self), key) ==> option::is_none(result_1);
ensures [abstract] !spec_contains_key(old(self), key) ==> option::is_none(result_2);
ensures [abstract] spec_contains_key(self, key);
ensures [abstract] spec_get(self, key) == value;
ensures [abstract] spec_contains_key(old(self), key) ==> ((option::is_some(result_1)) && (option::spec_borrow(result_1) == key));
ensures [abstract] spec_contains_key(old(self), key) ==> ((option::is_some(result_2)) && (option::spec_borrow(result_2) == spec_get(old(
    self
), key)));

native fun spec_len<K, V>(t: SimpleMap<K, V>): num;

native fun spec_contains_key<K, V>(t: SimpleMap<K, V>, k: K): bool;

native fun spec_set<K, V>(t: SimpleMap<K, V>, k: K, v: V): SimpleMap<K, V>;

native fun spec_remove<K, V>(t: SimpleMap<K, V>, k: K): SimpleMap<K, V>;

native fun spec_get<K, V>(t: SimpleMap<K, V>, k: K): V;

`keys`

public fun keys<Key: copy, Value>(self: &simple_map::SimpleMap<Key, Value>): vector<Key>

pragma verify=false;

`values`

public fun values<Key, Value: copy>(self: &simple_map::SimpleMap<Key, Value>): vector<Value>

pragma verify=false;

`to_vec_pair`

public fun to_vec_pair<Key: store, Value: store>(self: simple_map::SimpleMap<Key, Value>): (vector<Key>, vector<Value>)

pragma intrinsic;
pragma opaque;
ensures [abstract]
    forall k: Key: vector::spec_contains(result_1, k) <==>
        spec_contains_key(self, k);
ensures [abstract] forall i in 0..len(result_1):
    spec_get(self, result_1.borrow(i)) == result_2.borrow(i);

`remove`

public fun remove<Key: store, Value: store>(self: &mut simple_map::SimpleMap<Key, Value>, key: &Key): (Key, Value)

pragma intrinsic;

`find`

fun find<Key: store, Value: store>(self: &simple_map::SimpleMap<Key, Value>, key: &Key): option::Option<u64>

pragma verify=false;