SimpleMap.md

Module 0x1::SimpleMap

This module provides a solution for sorted 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

• Struct SimpleMap
• Struct Element
• Constants
• Function length
• Function create
• Function borrow
• Function borrow_mut
• Function contains_key
• Function destroy_empty
• Function add
• Function upsert
• Function remove
• Function find

use 0x1::Errors;
use 0x1::Option;
use 0x1::Vector;

Struct SimpleMap

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

Fields

data: vector<SimpleMap::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>(map: &SimpleMap::SimpleMap<Key, Value>): u64

Implementation

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

Specification

pragma intrinsic = true;

Function create

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

Implementation

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

Specification

pragma intrinsic = true;

Function borrow

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

Implementation

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

Specification

pragma intrinsic = true;

Function borrow_mut

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

Implementation

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

Specification

pragma intrinsic = true;

Function contains_key

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

Implementation

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

Specification

pragma intrinsic = true;

Function destroy_empty

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

Implementation

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

Specification

pragma intrinsic = true;

Function add

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

Implementation

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

    Vector::push_back(&mut map.data, Element { key, value });
}

Specification

pragma intrinsic = true;

Function upsert

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

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

Implementation

public fun upsert<Key: store, Value: store>(
    map: &mut SimpleMap<Key, Value>,
    key: Key,
    value: Value
): (Option::Option<Key>, Option::Option<Value>) {
    let data = &mut map.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 (Option::some(key), Option::some(value))
        };
        i = i + 1;
    };
    Vector::push_back(&mut map.data, Element { key, value });
    (Option::none(), Option::none())
}

Specification

pragma verify=false;

Function remove

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

Implementation

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

Specification

pragma intrinsic = true;

Function find

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

Implementation

fun find<Key: store, Value: store>(
    map: &SimpleMap<Key, Value>,
    key: &Key,
): Option::Option<u64> {
    let leng = Vector::length(&map.data);
    let i = 0;
    while (i < leng) {
        let element = Vector::borrow(&map.data, i);
        if (&element.key == key) {
            return Option::some(i)
        };
        i = i + 1;
    };
    Option::none<u64>()
}

Specification

pragma verify=false;