Ordered hash map or tree

dan-ryan · June 16, 2022, 5:58am

Is there any support for an ordered hash map or tree or a hash array? If not, does anyone know of any libraries for such collections?

I want an array of objects that can be removed and inserted at any point in the collection. I want to be able to quickly lookup an object (I can’t use the index because the array could have been edited) and insert objects beside it in the collection.

paulyoung · June 16, 2022, 6:57am

I did a quick search and found this. It appears to provide SortedMap and SortedValueMap.

I think it was written by @quint, who might be able to say more about it.

github.com

aviate-labs/sorted.mo/blob/main/src/Map.mo

import Hash "mo:base/Hash";
import HashMap "mo:base/HashMap";
import Iter "mo:base/Iter";
import List "mo:base/List";

import O "Order";
import SList "List";

module {
    public class SortedMap<K,V>(
        capacity : Nat,
        equal    : (K, K) -> Bool,
        hash     : (K) -> Hash.Hash,
        order    : O.Order<K>,
    ) {
        let map = HashMap.HashMap<K, V>(
            capacity, equal, hash,
        );
        var keys : SList.SortedList<K> = null;

This file has been truncated. show original

dan-ryan · June 16, 2022, 7:48am

Thanks I’ll give it a try.

dan-ryan · June 16, 2022, 1:14pm

I don’t think that lib is quite it. It doesn’t seem to allow insertions at a specific index. Or am I missing something?

So a use case I want to support is a large piece of text (so it needs ordering), quick look-ups to the characters (so it needs to be a tree or a map), and the ability to insert characters at any point (editing).

justmythoughts · June 16, 2022, 2:02pm

The backend just needs to make sure the text is ordered - the frontend can parse/transform it easily (JavaScript)

So use keys lexicographically sorted keys in a sorted data structure (Red-Black Trees/BTrees/AVL Trees) and then you just need the character before and after and can find the lexicographic midpoint between the 2 character positions and store that for insertions.

Break your text into chunks to reduce the size & operations involved in insertion/deletion

Topic		Replies	Views
Should I use HashMap or RBTree? Motoko	8	570	May 11, 2023
Map v8.0.0, it's finally here Language Support Motoko	22	1912	January 6, 2024
∞ Day - Origyn Motoko Gift 2 - A Better Map Language Support Motoko	3	832	August 8, 2022
New Motoko array sorting library Motoko	18	756	August 22, 2023
Understanding HashMap Language Support Motoko , Education	1	462	January 9, 2023

Ordered hash map or tree

Related Topics