Skip to content

Latest commit

 

History

History
1035 lines (556 loc) · 35.9 KB

simple_map.md

File metadata and controls

1035 lines (556 loc) · 35.9 KB
Raw

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
use 0x1::error;
use 0x1::option;
use 0x1::vector;

Struct SimpleMap

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 {
    vector::length(&self.data)
}

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();
    add_all(&mut map, 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 = find(self, key);
    assert!(option::is_some(&maybe_idx), error::invalid_argument(EKEY_NOT_FOUND));
    let idx = option::extract(&mut maybe_idx);
    &vector::borrow(&self.data, 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 = find(self, key);
    assert!(option::is_some(&maybe_idx), error::invalid_argument(EKEY_NOT_FOUND));
    let idx = option::extract(&mut maybe_idx);
    &mut vector::borrow_mut(&mut self.data, 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 = find(self, key);
    option::is_some(&maybe_idx)
}

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;
    vector::destroy_empty(data);
}

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 = find(self, &key);
    assert!(option::is_none(&maybe_idx), error::invalid_argument(EKEY_ALREADY_EXISTS));

    vector::push_back(&mut self.data, 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>,
) {
    vector::zip(keys, values, |key, value| {
        add(self, 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 = vector::length(data);
    let i = 0;
    while (i < len) {
        let element = vector::borrow(data, i);
        if (&element.key == &key) {
            vector::push_back(data, Element { key, value });
            vector::swap(data, i, len);
            let Element { key, value } = vector::pop_back(data);
            return (std::option::some(key), std::option::some(value))
        };
        i = i + 1;
    };
    vector::push_back(&mut self.data, 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> {
    vector::map_ref(&self.data, |e| {
        let e: &Element<Key, Value> = 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> {
    vector::map_ref(&self.data, |e| {
        let e: &Element<Key, Value> = 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;
    vector::for_each(data, |e| {
        let Element { key, value } = e;
        vector::push_back(&mut keys, key);
        vector::push_back(&mut values, 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) = to_vec_pair(self);
    vector::destroy(keys, |_k| dk(_k));
    vector::destroy(values, |_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 = find(self, key);
    assert!(option::is_some(&maybe_idx), error::invalid_argument(EKEY_NOT_FOUND));
    let placement = option::extract(&mut maybe_idx);
    let Element { key, value } = vector::swap_remove(&mut self.data, 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 leng = vector::length(&self.data);
    let i = 0;
    while (i < leng) {
        let element = vector::borrow(&self.data, i);
        if (&element.key == key) {
            return option::some(i)
        };
        i = i + 1;
    };
    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, vector::borrow(keys, i)) == vector::borrow(values, 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;
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, vector::borrow(result_1, i)) == vector::borrow(result_2, 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;