Skip to main content

Module 0x2::vec_set

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

Struct VecSet​

A set data structure backed by a vector. The set is guaranteed not to contain duplicate keys. All operations are O(N) in the size of the set

  • the intention of this data structure is only to provide the convenience of programming against a set API. Sets that need sorted iteration rather than insertion order iteration should be handwritten.
struct VecSet<K: copy, drop> has copy, drop, store
Fields
contents: vector<K>

Constants​

This key already exists in the map

const EKeyAlreadyExists: u64 = 0;

This key does not exist in the map

const EKeyDoesNotExist: u64 = 1;

Function empty​

Create an empty VecSet

public fun empty<K: copy, drop>(): vec_set::VecSet<K>
Implementation
public fun empty<K: copy + drop>(): VecSet<K> {
    VecSet { contents: vector[] }
}

Function singleton​

Create a singleton VecSet that only contains one element.

public fun singleton<K: copy, drop>(key: K): vec_set::VecSet<K>
Implementation
public fun singleton<K: copy + drop>(key: K): VecSet<K> {
    VecSet { contents: vector[key] }
}

Function insert​

Insert a key into self. Aborts if key is already present in self.

public fun insert<K: copy, drop>(self: &mut vec_set::VecSet<K>, key: K)
Implementation
public fun insert<K: copy + drop>(self: &mut VecSet<K>, key: K) {
    assert!(!self.contains(&key), EKeyAlreadyExists);
    self.contents.push_back(key)
}

Function remove​

Remove the entry key from self. Aborts if key is not present in self.

public fun remove<K: copy, drop>(self: &mut vec_set::VecSet<K>, key: &K)
Implementation
public fun remove<K: copy + drop>(self: &mut VecSet<K>, key: &K) {
    let idx = get_idx(self, key);
    self.contents.remove(idx);
}

Function contains​

Return true if self contains an entry for key, false otherwise

public fun contains<K: copy, drop>(self: &vec_set::VecSet<K>, key: &K): bool
Implementation
public fun contains<K: copy + drop>(self: &VecSet<K>, key: &K): bool {
    get_idx_opt(self, key).is_some()
}

Function size​

Return the number of entries in self

public fun size<K: copy, drop>(self: &vec_set::VecSet<K>): u64
Implementation
public fun size<K: copy + drop>(self: &VecSet<K>): u64 {
    self.contents.length()
}

Function is_empty​

Return true if self has 0 elements, false otherwise

public fun is_empty<K: copy, drop>(self: &vec_set::VecSet<K>): bool
Implementation
public fun is_empty<K: copy + drop>(self: &VecSet<K>): bool {
    size(self) == 0
}

Function into_keys​

Unpack self into vectors of keys. The output keys are stored in insertion order, not sorted.

public fun into_keys<K: copy, drop>(self: vec_set::VecSet<K>): vector<K>
Implementation
public fun into_keys<K: copy + drop>(self: VecSet<K>): vector<K> {
    let VecSet { contents } = self;
    contents
}

Function from_keys​

Construct a new VecSet from a vector of keys. The keys are stored in insertion order (the original keys ordering) and are not sorted.

public fun from_keys<K: copy, drop>(keys: vector<K>): vec_set::VecSet<K>
Implementation
public fun from_keys<K: copy + drop>(mut keys: vector<K>): VecSet<K> {
    keys.reverse();
    let mut set = empty();
    while (!keys.is_empty()) set.insert(keys.pop_back());
    set
}

Function keys​

Borrow the contents of the VecSet to access content by index without unpacking. The contents are stored in insertion order, not sorted.

public fun keys<K: copy, drop>(self: &vec_set::VecSet<K>): &vector<K>
Implementation
public fun keys<K: copy + drop>(self: &VecSet<K>): &vector<K> {
    &self.contents
}

Function get_idx_opt​

Find the index of key in self. Return None if key is not in self. Note that keys are stored in insertion order, not sorted.

fun get_idx_opt<K: copy, drop>(self: &vec_set::VecSet<K>, key: &K): option::Option<u64>
Implementation
fun get_idx_opt<K: copy + drop>(self: &VecSet<K>, key: &K): Option<u64> {
    let mut i = 0;
    let n = size(self);
    while (i < n) {
        if (&self.contents[i] == key) {
            return option::some(i)
        };
        i = i + 1;
    };
    option::none()
}

Function get_idx​

Find the index of key in self. Aborts if key is not in self. Note that map entries are stored in insertion order, not sorted.

fun get_idx<K: copy, drop>(self: &vec_set::VecSet<K>, key: &K): u64
Implementation
fun get_idx<K: copy + drop>(self: &VecSet<K>, key: &K): u64 {
    let idx_opt = get_idx_opt(self, key);
    assert!(idx_opt.is_some(), EKeyDoesNotExist);
    idx_opt.destroy_some()
}