Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Module 0x1::simple_map

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

  1. Keys point to Values
  2. Each Key must be unique
  3. A Key can be found within O(N) time
  4. The keys are unsorted.
  5. 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;

Struct 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>>

Struct Element 

struct Element<Key, Value> has copy, drop, store
Fields
key: Key
value: Value

Constants

Map key already exists

const EKEY_ALREADY_EXISTS: u64 = 1;

Map key is not found

const EKEY_NOT_FOUND: u64 = 2;

Function 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()
}

Function 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(),
    }
}

Function 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
}

Function 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()
}

Function 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
}

Function 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
}

Function 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()
}

Function 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();
}

Function 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 });
}

Function 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);
    });
}

Function 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())
}

Function 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
    })
}

Function 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
    })
}

Function 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)
}

Function 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));
}

Function 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)
}

Function 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

Struct 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;

Function length 

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

pragma intrinsic;

Function 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);

Function 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);

Function create 

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

pragma intrinsic;

Function borrow 

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

pragma intrinsic;

Function borrow_mut 

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

pragma intrinsic;

Function contains_key 

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

pragma intrinsic;

Function destroy_empty 

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

pragma intrinsic;

Function add 

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

pragma intrinsic;

Function 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;

Function 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;

Function keys 

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

pragma verify=false;

Function values 

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

pragma verify=false;

Function 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;
aborts_if [abstract] false;
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);

Function remove 

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

pragma intrinsic;

Function find 

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

pragma verify=false;