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::ordered_map

This module provides an implementation for an ordered map.

Keys point to values, and each key in the map must be unique.

Currently, one implementation is provided, backed by a single sorted vector.

That means that keys can be found within O(log N) time. Adds and removals take O(N) time, but the constant factor is small, as it does only O(log N) comparisons, and does efficient mem-copy with vector operations.

Additionally, it provides a way to lookup and iterate over sorted keys, making range query take O(log N + R) time (where R is number of elements in the range).

Most methods operate with OrderedMap being self. All methods that start with iter_*, operate with IteratorPtr being self.

Uses cmp::compare for ordering, which compares primitive types natively, and uses common lexicographical sorting for complex types.

Warning: All iterator functions need to be carefully used, because they are just pointers into the structure, and modification of the map invalidates them (without compiler being able to catch it). Type is also named IteratorPtr, so that Iterator is free to use later. Better guarantees would need future Move improvements that will allow references to be part of the struct, allowing cleaner iterator APIs.

That’s why all functions returning iterators are prefixed with “internal_”, to clarify nuances needed to make sure usage is correct. A set of inline utility methods is provided instead, to provide guaranteed valid usage to iterators.

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

Struct Entry

Individual entry holding (key, value) pair

struct Entry<K, V> has copy, drop, store
Fields
key: K
value: V

Enum OrderedMap

The OrderedMap datastructure.

enum OrderedMap<K, V> has copy, drop, store
Variants
SortedVectorMap
Fields
entries: vector<ordered_map::Entry<K, V>>
List of entries, sorted by key.

Enum IteratorPtr

An iterator pointing to a valid position in an ordered map, or to the end.

TODO: Once fields can be (mutable) references, this class will be deprecated.

enum IteratorPtr has copy, drop
Variants
End
Fields
Position
Fields
index: u64
The index of the iterator pointing to.

Constants 

const EITER_OUT_OF_BOUNDS: u64 = 3;

Map key already exists

const EKEY_ALREADY_EXISTS: u64 = 1;

Map key is not found

const EKEY_NOT_FOUND: u64 = 2;

New key used in replace_key_inplace doesn’t respect the order

const ENEW_KEY_NOT_IN_ORDER: u64 = 4;

Function new

Create a new empty OrderedMap, using default (SortedVectorMap) implementation.

public fun new<K, V>(): ordered_map::OrderedMap<K, V>
Implementation 
public fun new<K, V>(): OrderedMap<K, V> {
    OrderedMap::SortedVectorMap {
        entries: vector::empty(),
    }
}

Function new_from

Create a OrderedMap from a vector of keys and values. Aborts with EKEY_ALREADY_EXISTS if duplicate keys are passed in.

public fun new_from<K, V>(keys: vector<K>, values: vector<V>): ordered_map::OrderedMap<K, V>
Implementation 
public fun new_from<K, V>(keys: vector<K>, values: vector<V>): OrderedMap<K, V> {
    let map = new();
    map.add_all(keys, values);
    map
}

Function length

Number of elements in the map.

public fun length<K, V>(self: &ordered_map::OrderedMap<K, V>): u64
Implementation 
public fun length<K, V>(self: &OrderedMap<K, V>): u64 {
    self.entries.length()
}

Function is_empty

Whether map is empty.

public fun is_empty<K, V>(self: &ordered_map::OrderedMap<K, V>): bool
Implementation 
public fun is_empty<K, V>(self: &OrderedMap<K, V>): bool {
    self.entries.is_empty()
}

Function add

Add a key/value pair to the map. Aborts with EKEY_ALREADY_EXISTS if key already exist.

public fun add<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: K, value: V)
Implementation 
public fun add<K, V>(self: &mut OrderedMap<K, V>, key: K, value: V) {
    let len = self.entries.length();
    let index = binary_search(&key, &self.entries, 0, len);

    // key must not already be inside.
    assert!(index >= len || &self.entries[index].key != &key, error::invalid_argument(EKEY_ALREADY_EXISTS));
    self.entries.insert(index, Entry { key, value });
}

Function upsert

If the key doesn’t exist in the map, inserts the key/value, and returns none. Otherwise, updates the value under the given key, and returns the old value.

public fun upsert<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: K, value: V): option::Option<V>
Implementation 
public fun upsert<K: drop, V>(self: &mut OrderedMap<K, V>, key: K, value: V): Option<V> {
    let len = self.entries.length();
    let index = binary_search(&key, &self.entries, 0, len);

    if (index < len && &self.entries[index].key == &key) {
        let Entry {
            key: _,
            value: old_value,
        } = self.entries.replace(index, Entry { key, value });
        option::some(old_value)
    } else {
        self.entries.insert(index, Entry { key, value });
        option::none()
    }
}

Function remove

Remove a key/value pair from the map. Aborts with EKEY_NOT_FOUND if key doesn’t exist.

public fun remove<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): V
Implementation 
public fun remove<K: drop, V>(self: &mut OrderedMap<K, V>, key: &K): V {
    let len = self.entries.length();
    let index = binary_search(key, &self.entries, 0, len);
    assert!(index < len, error::invalid_argument(EKEY_NOT_FOUND));
    let Entry { key: old_key, value } = self.entries.remove(index);
    assert!(key == &old_key, error::invalid_argument(EKEY_NOT_FOUND));
    value
}

Function remove_or_none

Remove a key/value pair from the map. Returns none if key doesn’t exist.

public fun remove_or_none<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): option::Option<V>
Implementation 
public fun remove_or_none<K: drop, V>(self: &mut OrderedMap<K, V>, key: &K): Option<V> {
    let len = self.entries.length();
    let index = binary_search(key, &self.entries, 0, len);
    if (index < len && key == &self.entries[index].key) {
        let Entry { key: _, value } = self.entries.remove(index);
        option::some(value)
    } else {
        option::none()
    }
}

Function modify_or_add

Modifies element by calling modify_f if it exists, or calling add_f to add if it doesn’t. Returns true if element already existed.

public fun modify_or_add<K: copy, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K, modify_f: |&mut V| has drop, add_f: ||V has drop): bool
Implementation 
public inline fun modify_or_add<K: copy, V>(self: &mut OrderedMap<K, V>, key: &K, modify_f: |&mut V| has drop, add_f: ||V has drop): bool {
    let exists = self.modify_if_present(key, |v| modify_f(v));
    if (!exists) {
        self.add(*key, add_f());
    };
    exists
}

Function modify_if_present

Modifies element by calling modify_f if it exists. Returns true if element already existed.

public fun modify_if_present<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K, modify_f: |&mut V| has drop): bool
Implementation 
public inline fun modify_if_present<K, V>(self: &mut OrderedMap<K, V>, key: &K, modify_f: |&mut V| has drop): bool {
    let iter = self.internal_find(key);
    if (iter.iter_is_end(self)) {
        false
    } else {
        modify_f(iter.iter_borrow_mut(self));
        true
    }
}

Function contains

Returns whether map contains a given key.

public fun contains<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): bool
Implementation 
public fun contains<K, V>(self: &OrderedMap<K, V>, key: &K): bool {
    !self.internal_find(key).iter_is_end(self)
}

Function borrow 

public fun borrow<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): &V
Implementation 
public fun borrow<K, V>(self: &OrderedMap<K, V>, key: &K): &V {
    self.internal_find(key).iter_borrow(self)
}

Function borrow_mut 

public fun borrow_mut<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): &mut V
Implementation 
public fun borrow_mut<K, V>(self: &mut OrderedMap<K, V>, key: &K): &mut V {
    self.internal_find(key).iter_borrow_mut(self)
}

Function get 

public fun get<K: copy, drop, store, V: copy, store>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<V>
Implementation 
public fun get<K: drop + copy + store, V: copy + store>(self: &OrderedMap<K, V>, key: &K): Option<V> {
    let iter = self.internal_find(key);
    if (iter.iter_is_end(self)) {
        option::none()
    } else {
        option::some(*iter.iter_borrow(self))
    }
}

Function get_and_map 

public fun get_and_map<K: copy, drop, store, V: store, R>(self: &ordered_map::OrderedMap<K, V>, key: &K, f: |&V|R has drop): option::Option<R>
Implementation 
public inline fun get_and_map<K: drop + copy + store, V: store, R>(self: &OrderedMap<K, V>, key: &K, f: |&V|R has drop): Option<R> {
    let iter = self.internal_find(key);
    if (iter.iter_is_end(self)) {
        option::none()
    } else {
        option::some(f(iter.iter_borrow(self)))
    }
}

Function replace_key_inplace

Changes the key, while keeping the same value attached to it Aborts with EKEY_NOT_FOUND if old_key doesn’t exist. Aborts with ENEW_KEY_NOT_IN_ORDER if new_key doesn’t keep the order old_key was in.

public(friend) fun replace_key_inplace<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, old_key: &K, new_key: K)
Implementation 
public(friend) fun replace_key_inplace<K: drop, V>(self: &mut OrderedMap<K, V>, old_key: &K, new_key: K) {
    let len = self.entries.length();
    let index = binary_search(old_key, &self.entries, 0, len);
    assert!(index < len, error::invalid_argument(EKEY_NOT_FOUND));

    assert!(old_key == &self.entries[index].key, error::invalid_argument(EKEY_NOT_FOUND));

    // check that after we update the key, order is going to be respected
    if (index > 0) {
        assert!(cmp::compare(&self.entries[index - 1].key, &new_key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };

    if (index + 1 < len) {
        assert!(cmp::compare(&new_key, &self.entries[index + 1].key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };

    self.entries[index].key = new_key;
}

Function add_all

Add multiple key/value pairs to the map. The keys must not already exist. Aborts with EKEY_ALREADY_EXISTS if key already exist, or duplicate keys are passed in.

public fun add_all<K, V>(self: &mut ordered_map::OrderedMap<K, V>, keys: vector<K>, values: vector<V>)
Implementation 
public fun add_all<K, V>(self: &mut OrderedMap<K, V>, keys: vector<K>, values: vector<V>) {
    // TODO: Can be optimized, by sorting keys and values, and then creating map.
    keys.zip(values, |key, value| {
        self.add(key, value);
    });
}

Function upsert_all

Add multiple key/value pairs to the map, overwrites values if they exist already, or if duplicate keys are passed in.

public fun upsert_all<K: drop, V: drop>(self: &mut ordered_map::OrderedMap<K, V>, keys: vector<K>, values: vector<V>)
Implementation 
public fun upsert_all<K: drop, V: drop>(self: &mut OrderedMap<K, V>, keys: vector<K>, values: vector<V>) {
    // TODO: Can be optimized, by sorting keys and values, and then creating map.
    keys.zip(values, |key, value| {
        self.upsert(key, value);
    });
}

Function append

Takes all elements from other and adds them to self, overwritting if any key is already present in self.

public fun append<K: drop, V: drop>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>)
Implementation 
public fun append<K: drop, V: drop>(self: &mut OrderedMap<K, V>, other: OrderedMap<K, V>) {
    self.append_impl(other);
}

Function append_disjoint

Takes all elements from other and adds them to self. Aborts with EKEY_ALREADY_EXISTS if other has a key already present in self.

public fun append_disjoint<K, V>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>)
Implementation 
public fun append_disjoint<K, V>(self: &mut OrderedMap<K, V>, other: OrderedMap<K, V>) {
    let overwritten = self.append_impl(other);
    assert!(overwritten.length() == 0, error::invalid_argument(EKEY_ALREADY_EXISTS));
    overwritten.destroy_empty();
}

Function append_impl

Takes all elements from other and adds them to self, returning list of entries in self that were overwritten.

fun append_impl<K, V>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>): vector<ordered_map::Entry<K, V>>
Implementation 
fun append_impl<K, V>(self: &mut OrderedMap<K, V>, other: OrderedMap<K, V>): vector<Entry<K,V>> {
    let OrderedMap::SortedVectorMap {
        entries: other_entries,
    } = other;
    let overwritten = vector::empty();

    if (other_entries.is_empty()) {
        other_entries.destroy_empty();
        return overwritten;
    };

    if (self.entries.is_empty()) {
        self.entries.append(other_entries);
        return overwritten;
    };

    // Optimization: if all elements in `other` are larger than all elements in `self`, we can just move them over.
    if (cmp::compare(&self.entries.borrow(self.entries.length() - 1).key, &other_entries.borrow(0).key).is_lt()) {
        self.entries.append(other_entries);
        return overwritten;
    };

    // In O(n), traversing from the back, build reverse sorted result, and then reverse it back
    let reverse_result = vector::empty();
    let cur_i = self.entries.length() - 1;
    let other_i = other_entries.length() - 1;

    // after the end of the loop, other_entries is empty, and any leftover is in entries
    loop {
        let ord = cmp::compare(&self.entries[cur_i].key, &other_entries[other_i].key);
        if (ord.is_gt()) {
            reverse_result.push_back(self.entries.pop_back());
            if (cur_i == 0) {
                // make other_entries empty, and rest in entries.
                // TODO cannot use mem::swap until it is public/released
                // mem::swap(&mut self.entries, &mut other_entries);
                self.entries.append(other_entries);
                break;
            } else {
                cur_i -= 1;
            };
        } else {
            // is_lt or is_eq
            if (ord.is_eq()) {
                // we skip the entries one, and below put in the result one from other.
                overwritten.push_back(self.entries.pop_back());

                if (cur_i == 0) {
                    // make other_entries empty, and rest in entries.
                    // TODO cannot use mem::swap until it is public/released
                    // mem::swap(&mut self.entries, &mut other_entries);
                    self.entries.append(other_entries);
                    break;
                } else {
                    cur_i -= 1;
                };
            };

            reverse_result.push_back(other_entries.pop_back());
            if (other_i == 0) {
                other_entries.destroy_empty();
                break;
            } else {
                other_i -= 1;
            };
        };
    };

    self.entries.reverse_append(reverse_result);

    overwritten
}

Function trim

Splits the collection into two, such to leave self with at number of elements. Returns a newly allocated map containing the elements in the range [at, len). After the call, the original map will be left containing the elements [0, at).

public fun trim<K, V>(self: &mut ordered_map::OrderedMap<K, V>, at: u64): ordered_map::OrderedMap<K, V>
Implementation 
public fun trim<K, V>(self: &mut OrderedMap<K, V>, at: u64): OrderedMap<K, V> {
    let rest = self.entries.trim(at);

    OrderedMap::SortedVectorMap {
        entries: rest
    }
}

Function borrow_front 

public fun borrow_front<K, V>(self: &ordered_map::OrderedMap<K, V>): (&K, &V)
Implementation 
public fun borrow_front<K, V>(self: &OrderedMap<K, V>): (&K, &V) {
    let entry = self.entries.borrow(0);
    (&entry.key, &entry.value)
}

Function borrow_back 

public fun borrow_back<K, V>(self: &ordered_map::OrderedMap<K, V>): (&K, &V)
Implementation 
public fun borrow_back<K, V>(self: &OrderedMap<K, V>): (&K, &V) {
    let entry = self.entries.borrow(self.entries.length() - 1);
    (&entry.key, &entry.value)
}

Function pop_front 

public fun pop_front<K, V>(self: &mut ordered_map::OrderedMap<K, V>): (K, V)
Implementation 
public fun pop_front<K, V>(self: &mut OrderedMap<K, V>): (K, V) {
    let Entry { key, value } = self.entries.remove(0);
    (key, value)
}

Function pop_back 

public fun pop_back<K, V>(self: &mut ordered_map::OrderedMap<K, V>): (K, V)
Implementation 
public fun pop_back<K, V>(self: &mut OrderedMap<K, V>): (K, V) {
    let Entry { key, value } = self.entries.pop_back();
    (key, value)
}

Function prev_key 

public fun prev_key<K: copy, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<K>
Implementation 
public fun prev_key<K: copy, V>(self: &OrderedMap<K, V>, key: &K): Option<K> {
    let it = self.internal_lower_bound(key);
    if (it.iter_is_begin(self)) {
        option::none()
    } else {
        option::some(*it.iter_prev(self).iter_borrow_key(self))
    }
}

Function next_key 

public fun next_key<K: copy, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<K>
Implementation 
public fun next_key<K: copy, V>(self: &OrderedMap<K, V>, key: &K): Option<K> {
    let it = self.internal_lower_bound(key);
    if (it.iter_is_end(self)) {
        option::none()
    } else {
        let cur_key = it.iter_borrow_key(self);
        if (key == cur_key) {
            let it = it.iter_next(self);
            if (it.iter_is_end(self)) {
                option::none()
            } else {
                option::some(*it.iter_borrow_key(self))
            }
        } else {
            option::some(*cur_key)
        }
    }
}

Function internal_lower_bound

Warning: Marked as internal, as it is safer to utilize provided inline functions instead. For direct usage of this method, check Warning at the top of the file corresponding to iterators.

Returns an iterator pointing to the first element that is greater or equal to the provided key, or an end iterator if such element doesn’t exist.

public fun internal_lower_bound<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): ordered_map::IteratorPtr
Implementation 
public fun internal_lower_bound<K, V>(self: &OrderedMap<K, V>, key: &K): IteratorPtr {
    let entries = &self.entries;
    let len = entries.length();

    let index = binary_search(key, entries, 0, len);
    if (index == len) {
        self.internal_new_end_iter()
    } else {
        new_iter(index)
    }
}

Function internal_find

Warning: Marked as internal, as it is safer to utilize provided inline functions instead. For direct usage of this method, check Warning at the top of the file corresponding to iterators.

Returns an iterator pointing to the element that equals to the provided key, or an end iterator if the key is not found.

public fun internal_find<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): ordered_map::IteratorPtr
Implementation 
public fun internal_find<K, V>(self: &OrderedMap<K, V>, key: &K): IteratorPtr {
    let internal_lower_bound = self.internal_lower_bound(key);
    if (internal_lower_bound.iter_is_end(self)) {
        internal_lower_bound
    } else if (internal_lower_bound.iter_borrow_key(self) == key) {
        internal_lower_bound
    } else {
        self.internal_new_end_iter()
    }
}

Function internal_new_begin_iter

Warning: Marked as internal, as it is safer to utilize provided inline functions instead. For direct usage of this method, check Warning at the top of the file corresponding to iterators.

Returns the begin iterator.

public fun internal_new_begin_iter<K, V>(self: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public fun internal_new_begin_iter<K, V>(self: &OrderedMap<K, V>): IteratorPtr {
    if (self.is_empty()) {
        return IteratorPtr::End;
    };

    new_iter(0)
}

Function internal_new_end_iter

Warning: Marked as internal, as it is safer to utilize provided inline functions instead. For direct usage of this method, check Warning at the top of the file corresponding to iterators.

Returns the end iterator.

public fun internal_new_end_iter<K, V>(self: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public fun internal_new_end_iter<K, V>(self: &OrderedMap<K, V>): IteratorPtr {
    IteratorPtr::End
}

Function iter_next

Returns the next iterator, or none if already at the end iterator. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_next<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public fun iter_next<K, V>(self: IteratorPtr, map: &OrderedMap<K, V>): IteratorPtr {
    assert!(!self.iter_is_end(map), error::invalid_argument(EITER_OUT_OF_BOUNDS));

    let index = self.index + 1;
    if (index < map.entries.length()) {
        new_iter(index)
    } else {
        map.internal_new_end_iter()
    }
}

Function iter_prev

Returns the previous iterator, or none if already at the begin iterator. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_prev<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr
Implementation 
public fun iter_prev<K, V>(self: IteratorPtr, map: &OrderedMap<K, V>): IteratorPtr {
    assert!(!self.iter_is_begin(map), error::invalid_argument(EITER_OUT_OF_BOUNDS));

    let index = if (self is IteratorPtr::End) {
        map.entries.length() - 1
    } else {
        self.index - 1
    };

    new_iter(index)
}

Function iter_is_begin

Returns whether the iterator is a begin iterator.

public fun iter_is_begin<K, V>(self: &ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): bool
Implementation 
public fun iter_is_begin<K, V>(self: &IteratorPtr, map: &OrderedMap<K, V>): bool {
    if (self is IteratorPtr::End) {
        map.is_empty()
    } else {
        self.index == 0
    }
}

Function iter_is_begin_from_non_empty

Returns true iff the iterator is a begin iterator from a non-empty collection. (I.e. if iterator points to a valid element) This method doesn’t require having access to map, unlike iter_is_begin.

public fun iter_is_begin_from_non_empty(self: &ordered_map::IteratorPtr): bool
Implementation 
public fun iter_is_begin_from_non_empty(self: &IteratorPtr): bool {
    if (self is IteratorPtr::End) {
        false
    } else {
        self.index == 0
    }
}

Function iter_is_end

Returns whether the iterator is an end iterator.

public fun iter_is_end<K, V>(self: &ordered_map::IteratorPtr, _map: &ordered_map::OrderedMap<K, V>): bool
Implementation 
public fun iter_is_end<K, V>(self: &IteratorPtr, _map: &OrderedMap<K, V>): bool {
    self is IteratorPtr::End
}

Function iter_borrow_key

Borrows the key given iterator points to. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_borrow_key<K, V>(self: &ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): &K
Implementation 
public fun iter_borrow_key<K, V>(self: &IteratorPtr, map: &OrderedMap<K, V>): &K {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));

    &map.entries.borrow(self.index).key
}

Function iter_borrow

Borrows the value given iterator points to. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_borrow<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): &V
Implementation 
public fun iter_borrow<K, V>(self: IteratorPtr, map: &OrderedMap<K, V>): &V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));
    &map.entries.borrow(self.index).value
}

Function iter_borrow_mut

Mutably borrows the value iterator points to. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_borrow_mut<K, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>): &mut V
Implementation 
public fun iter_borrow_mut<K, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>): &mut V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));
    &mut map.entries.borrow_mut(self.index).value
}

Function iter_remove

Removes (key, value) pair iterator points to, returning the previous value. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_remove<K: drop, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>): V
Implementation 
public fun iter_remove<K: drop, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>): V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));

    let Entry { key: _, value } = map.entries.remove(self.index);
    value
}

Function iter_replace

Replaces the value iterator is pointing to, returning the previous value. Aborts with EITER_OUT_OF_BOUNDS if iterator is pointing to the end. Note: Requires that the map is not changed after the input iterator is generated.

public fun iter_replace<K: copy, drop, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>, value: V): V
Implementation 
public fun iter_replace<K: copy + drop, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>, value: V): V {
    assert!(!(self is IteratorPtr::End), error::invalid_argument(EITER_OUT_OF_BOUNDS));

    // TODO once mem::replace is public/released, update to:
    // let entry = map.entries.borrow_mut(self.index);
    // mem::replace(&mut entry.value, value)
    let key = map.entries[self.index].key;
    let Entry {
        key: _,
        value: prev_value,
    } = map.entries.replace(self.index, Entry { key, value });
    prev_value
}

Function iter_add

Add key/value pair to the map, at the iterator position (before the element at the iterator position). Aborts with ENEW_KEY_NOT_IN_ORDER is key is not larger than the key before the iterator, or smaller than the key at the iterator position.

public fun iter_add<K, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>, key: K, value: V)
Implementation 
public fun iter_add<K, V>(self: IteratorPtr, map: &mut OrderedMap<K, V>, key: K, value: V) {
    let len = map.entries.length();
    let insert_index = if (self is IteratorPtr::End) {
        len
    } else {
        self.index
    };

    if (insert_index > 0) {
        assert!(cmp::compare(&map.entries[insert_index - 1].key, &key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };

    if (insert_index < len) {
        assert!(cmp::compare(&key, &map.entries[insert_index].key).is_lt(), error::invalid_argument(ENEW_KEY_NOT_IN_ORDER))
    };

    map.entries.insert(insert_index, Entry { key, value });
}

Function destroy_empty

Destroys empty map. Aborts if self is not empty.

public fun destroy_empty<K, V>(self: ordered_map::OrderedMap<K, V>)
Implementation 
public fun destroy_empty<K, V>(self: OrderedMap<K, V>) {
    let OrderedMap::SortedVectorMap { entries } = self;
    // assert!(entries.is_empty(), E_NOT_EMPTY);
    entries.destroy_empty();
}

Function keys

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

public fun keys<K: copy, V>(self: &ordered_map::OrderedMap<K, V>): vector<K>
Implementation 
public fun keys<K: copy, V>(self: &OrderedMap<K, V>): vector<K> {
    self.entries.map_ref(|e| {
        let e: &Entry<K, V> = e;
        e.key
    })
}

Function values

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

public fun values<K, V: copy>(self: &ordered_map::OrderedMap<K, V>): vector<V>
Implementation 
public fun values<K, V: copy>(self: &OrderedMap<K, V>): vector<V> {
    self.entries.map_ref(|e| {
        let e: &Entry<K, V> = 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<K, V>(self: ordered_map::OrderedMap<K, V>): (vector<K>, vector<V>)
Implementation 
public fun to_vec_pair<K, V>(self: OrderedMap<K, V>): (vector<K>, vector<V>) {
    let keys: vector<K> = vector::empty();
    let values: vector<V> = vector::empty();
    let OrderedMap::SortedVectorMap { entries } = self;
    entries.for_each(|e| {
        let Entry { 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<K, V>(self: ordered_map::OrderedMap<K, V>, dk: |K|, dv: |V|)
Implementation 
public inline fun destroy<K, V>(
    self: OrderedMap<K, V>,
    dk: |K|,
    dv: |V|
) {
    let (keys, values) = self.to_vec_pair();
    keys.destroy(|_k| dk(_k));
    values.destroy(|_v| dv(_v));
}

Function for_each

Apply the function to each key-value pair in the map, consuming it.

public fun for_each<K, V>(self: ordered_map::OrderedMap<K, V>, f: |K, V|)
Implementation 
public inline fun for_each<K, V>(
    self: OrderedMap<K, V>,
    f: |K, V|
) {
    let (keys, values) = self.to_vec_pair();
    keys.zip(values, |k, v| f(k, v));
}

Function for_each_ref

Apply the function to a reference of each key-value pair in the map.

public fun for_each_ref<K, V>(self: &ordered_map::OrderedMap<K, V>, f: |&K, &V|)
Implementation 
public inline fun for_each_ref<K, V>(self: &OrderedMap<K, V>, f: |&K, &V|) {
    let iter = self.internal_new_begin_iter();
    while (!iter.iter_is_end(self)) {
        f(iter.iter_borrow_key(self), iter.iter_borrow(self));
        iter = iter.iter_next(self);
    }

    // TODO: once move supports private functions update to:
    // vector::for_each_ref(
    //     &self.entries,
    //     |entry| {
    //         f(&entry.key, &entry.value)
    //     }
    // );
}

Function for_each_mut

Apply the function to a mutable reference of each key-value pair in the map.

public fun for_each_mut<K: copy, drop, V>(self: &mut ordered_map::OrderedMap<K, V>, f: |&K, &mut V|)
Implementation 
public inline fun for_each_mut<K: copy + drop, V>(self: &mut OrderedMap<K, V>, f: |&K, &mut V|) {
    let iter = self.internal_new_begin_iter();
    while (!iter.iter_is_end(self)) {
        let key = *iter.iter_borrow_key(self);
        f(&key, iter.iter_borrow_mut(self));
        iter = iter.iter_next(self);
    }

    // TODO: once move supports private functions udpate to:
    // vector::for_each_mut(
    //     &mut self.entries,
    //     |entry| {
    //         f(&mut entry.key, &mut entry.value)
    //     }
    // );
}

Function new_iter 

fun new_iter(index: u64): ordered_map::IteratorPtr
Implementation 
inline fun new_iter(index: u64): IteratorPtr {
    IteratorPtr::Position {
        index: index,
    }
}

fun binary_search<K, V>(key: &K, entries: &vector<ordered_map::Entry<K, V>>, start: u64, end: u64): u64
Implementation 
fun binary_search<K, V>(key: &K, entries: &vector<Entry<K, V>>, start: u64, end: u64): u64 {
    let l = start;
    let r = end;
    while (l != r) {
        let mid = l + ((r - l) >> 1);
        let comparison = cmp::compare(&entries.borrow(mid).key, key);
        if (comparison.is_lt()) {
            l = mid + 1;
        } else {
            r = mid;
        };
    };
    l
}

Specification 

pragma verify = true;

Enum OrderedMap 

enum OrderedMap<K, V> has copy, drop, store
SortedVectorMap
Fields
entries: vector<ordered_map::Entry<K, V>>
List of entries, sorted by key. 
pragma intrinsic = map,
    map_new = new,
    map_len = length,
    map_destroy_empty = destroy_empty,
    map_has_key = contains,
    map_add_no_override = add,
    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,
    map_is_empty = is_empty;


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


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


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


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


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

Function new 

public fun new<K, V>(): ordered_map::OrderedMap<K, V>

pragma intrinsic;

Function new_from 

public fun new_from<K, V>(keys: vector<K>, values: vector<V>): ordered_map::OrderedMap<K, V>

pragma opaque;
pragma verify = false;
aborts_if [abstract] exists i in 0..len(keys), j in 0..len(keys) where i != j : keys[i] == keys[j];
aborts_if [abstract] len(keys) != len(values);
ensures [abstract] forall k: K {spec_contains_key(result, k)} : vector::spec_contains(keys,k) <==> spec_contains_key(result, k);
ensures [abstract] forall i in 0..len(keys) : spec_get(result, keys[i]) == values[i];
ensures [abstract] spec_len(result) == len(keys);

Function length 

public fun length<K, V>(self: &ordered_map::OrderedMap<K, V>): u64

pragma intrinsic;

Function is_empty 

public fun is_empty<K, V>(self: &ordered_map::OrderedMap<K, V>): bool

pragma intrinsic;

Function add 

public fun add<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: K, value: V)

pragma intrinsic;

Function upsert 

public fun upsert<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: K, value: V): option::Option<V>

pragma opaque;
pragma verify = false;
ensures [abstract] !spec_contains_key(old(self), key) ==> option::is_none(result);
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)) && (option::borrow(result) == spec_get(old(
    self), key)));
ensures [abstract] !spec_contains_key(old(self), key) ==> spec_len(old(self)) + 1 == spec_len(self);
ensures [abstract] spec_contains_key(old(self), key) ==> spec_len(old(self)) == spec_len(self);
ensures [abstract] forall k: K: spec_contains_key(old(self), k) && k != key ==> spec_get(old(self), k) == spec_get(self, k);
ensures [abstract] forall k: K: spec_contains_key(old(self), k) ==> spec_contains_key(self, k);

Function remove 

public fun remove<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): V

pragma opaque;
pragma verify = false;
aborts_if [abstract] !spec_contains_key(self, key);
ensures [abstract] !spec_contains_key(self, key);
ensures [abstract] spec_get(old(self), key) == result;
ensures [abstract] spec_len(old(self)) == spec_len(self) + 1;
ensures [abstract] forall k: K where k != key: spec_contains_key(self, k) ==> spec_get(self, k) == spec_get(old(self), k);
ensures [abstract] forall k: K where k != key: spec_contains_key(old(self), k) == spec_contains_key(self, k);

Function remove_or_none 

public fun remove_or_none<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): option::Option<V>

pragma opaque;
pragma verify = false;
aborts_if [abstract] false;
ensures [abstract] spec_contains_key(old(self), key) ==> result == option::spec_some(spec_get(old(self), key));
ensures [abstract] !spec_contains_key(old(self), key) ==> result == option::spec_none();
ensures [abstract] !spec_contains_key(self, key);
ensures [abstract] option::spec_is_none(result) ==> self == old(self);
ensures [abstract] option::spec_is_some(result) ==> spec_len(old(self)) == spec_len(self) + 1;
ensures [abstract] forall k: K where k != key: spec_contains_key(self, k) ==> spec_get(self, k) == spec_get(old(self), k);
ensures [abstract] forall k: K where k != key: spec_contains_key(old(self), k) == spec_contains_key(self, k);

Function contains 

public fun contains<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): bool

pragma intrinsic;

Function borrow 

public fun borrow<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): &V

pragma intrinsic;

Function borrow_mut 

public fun borrow_mut<K, V>(self: &mut ordered_map::OrderedMap<K, V>, key: &K): &mut V

pragma intrinsic;

Function get 

public fun get<K: copy, drop, store, V: copy, store>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<V>

pragma opaque;
pragma verify = false;

Function replace_key_inplace 

public(friend) fun replace_key_inplace<K: drop, V>(self: &mut ordered_map::OrderedMap<K, V>, old_key: &K, new_key: K)

pragma opaque;
pragma verify = false;

Function add_all 

public fun add_all<K, V>(self: &mut ordered_map::OrderedMap<K, V>, keys: vector<K>, values: vector<V>)

pragma opaque;
pragma verify = false;

Function upsert_all 

public fun upsert_all<K: drop, V: drop>(self: &mut ordered_map::OrderedMap<K, V>, keys: vector<K>, values: vector<V>)

pragma opaque;
pragma verify = false;

Function append 

public fun append<K: drop, V: drop>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>)

pragma opaque;
pragma verify = false;

Function append_disjoint 

public fun append_disjoint<K, V>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>)

pragma opaque;
pragma verify = false;

Function append_impl 

fun append_impl<K, V>(self: &mut ordered_map::OrderedMap<K, V>, other: ordered_map::OrderedMap<K, V>): vector<ordered_map::Entry<K, V>>

pragma opaque;
pragma verify = false;

Function trim 

public fun trim<K, V>(self: &mut ordered_map::OrderedMap<K, V>, at: u64): ordered_map::OrderedMap<K, V>

pragma opaque;
pragma verify = false;

Function borrow_front 

public fun borrow_front<K, V>(self: &ordered_map::OrderedMap<K, V>): (&K, &V)

pragma opaque;
pragma verify = false;
ensures [abstract] spec_contains_key(self, result_1);
ensures [abstract] spec_get(self, result_1) == result_2;
ensures [abstract] forall k: K where k != result_1: spec_contains_key(self, k) ==>
std::cmp::compare(result_1, k) == std::cmp::Ordering::Less;

Function borrow_back 

public fun borrow_back<K, V>(self: &ordered_map::OrderedMap<K, V>): (&K, &V)

pragma opaque;
pragma verify = false;
ensures [abstract] spec_contains_key(self, result_1);
ensures [abstract] spec_get(self, result_1) == result_2;
ensures [abstract] forall k: K where k != result_1: spec_contains_key(self, k) ==>
std::cmp::compare(result_1, k) == std::cmp::Ordering::Greater;

Function pop_front 

public fun pop_front<K, V>(self: &mut ordered_map::OrderedMap<K, V>): (K, V)

pragma opaque;
pragma verify = false;

Function pop_back 

public fun pop_back<K, V>(self: &mut ordered_map::OrderedMap<K, V>): (K, V)

pragma opaque;
pragma verify = false;

Function prev_key 

public fun prev_key<K: copy, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<K>

pragma opaque;
pragma verify = false;
ensures [abstract] result == std::option::spec_none() <==>
(forall k: K {spec_contains_key(self, k)} where spec_contains_key(self, k)
&& k != key: std::cmp::compare(key, k) == std::cmp::Ordering::Less);
ensures [abstract] result.is_some() <==>
    spec_contains_key(self, option::borrow(result)) &&
    (std::cmp::compare(option::borrow(result), key) == std::cmp::Ordering::Less)
    && (forall k: K {spec_contains_key(self, k), std::cmp::compare(option::borrow(result), k), std::cmp::compare(key, k)} where k != option::borrow(result): ((spec_contains_key(self, k) &&
    std::cmp::compare(k, key) == std::cmp::Ordering::Less)) ==>
    std::cmp::compare(option::borrow(result), k) == std::cmp::Ordering::Greater);

Function next_key 

public fun next_key<K: copy, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): option::Option<K>

pragma opaque;
pragma verify = false;
ensures [abstract] result == std::option::spec_none() <==>
(forall k: K {spec_contains_key(self, k)} where spec_contains_key(self, k) && k != key:
std::cmp::compare(key, k) == std::cmp::Ordering::Greater);
ensures [abstract] result.is_some() <==>
    spec_contains_key(self, option::borrow(result)) &&
    (std::cmp::compare(option::borrow(result), key) == std::cmp::Ordering::Greater)
    && (forall k: K {spec_contains_key(self, k)} where k != option::borrow(result): ((spec_contains_key(self, k) &&
    std::cmp::compare(k, key) == std::cmp::Ordering::Greater)) ==>
    std::cmp::compare(option::borrow(result), k) == std::cmp::Ordering::Less);

Function internal_lower_bound 

public fun internal_lower_bound<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): ordered_map::IteratorPtr

pragma opaque;
pragma verify = false;

Function internal_find 

public fun internal_find<K, V>(self: &ordered_map::OrderedMap<K, V>, key: &K): ordered_map::IteratorPtr

pragma opaque;
pragma verify = false;

Function internal_new_begin_iter 

public fun internal_new_begin_iter<K, V>(self: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr

pragma opaque;
pragma verify = false;

Function internal_new_end_iter 

public fun internal_new_end_iter<K, V>(self: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr

pragma opaque;
pragma verify = false;

Function iter_next 

public fun iter_next<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr

pragma opaque;
pragma verify = false;

Function iter_prev 

public fun iter_prev<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): ordered_map::IteratorPtr

pragma opaque;
pragma verify = false;

Function iter_is_begin 

public fun iter_is_begin<K, V>(self: &ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): bool

pragma opaque;
pragma verify = false;

Function iter_is_begin_from_non_empty 

public fun iter_is_begin_from_non_empty(self: &ordered_map::IteratorPtr): bool

pragma opaque;
pragma verify = false;

Function iter_is_end 

public fun iter_is_end<K, V>(self: &ordered_map::IteratorPtr, _map: &ordered_map::OrderedMap<K, V>): bool

pragma opaque;
pragma verify = false;

Function iter_borrow_key 

public fun iter_borrow_key<K, V>(self: &ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): &K

pragma opaque;
pragma verify = false;

Function iter_borrow 

public fun iter_borrow<K, V>(self: ordered_map::IteratorPtr, map: &ordered_map::OrderedMap<K, V>): &V

pragma opaque;
pragma verify = false;

Function iter_borrow_mut 

public fun iter_borrow_mut<K, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>): &mut V

pragma opaque;
pragma verify = false;

Function iter_remove 

public fun iter_remove<K: drop, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>): V

pragma opaque;
pragma verify = false;

Function iter_replace 

public fun iter_replace<K: copy, drop, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>, value: V): V

pragma opaque;
pragma verify = false;

Function iter_add 

public fun iter_add<K, V>(self: ordered_map::IteratorPtr, map: &mut ordered_map::OrderedMap<K, V>, key: K, value: V)

pragma opaque;
pragma verify = false;

Function destroy_empty 

public fun destroy_empty<K, V>(self: ordered_map::OrderedMap<K, V>)

pragma intrinsic;

Function keys 

public fun keys<K: copy, V>(self: &ordered_map::OrderedMap<K, V>): vector<K>

pragma verify = false;
pragma opaque;
ensures [abstract] forall k: K: vector::spec_contains(result, k) <==> spec_contains_key(self, k);

Function values 

public fun values<K, V: copy>(self: &ordered_map::OrderedMap<K, V>): vector<V>

pragma opaque;
pragma verify = false;

Function to_vec_pair 

public fun to_vec_pair<K, V>(self: ordered_map::OrderedMap<K, V>): (vector<K>, vector<V>)

pragma verify = false;
pragma opaque;

Function binary_search 

fun binary_search<K, V>(key: &K, entries: &vector<ordered_map::Entry<K, V>>, start: u64, end: u64): u64

pragma opaque;
pragma verify = false;