Implement AVL Tree for near-sdk-as

[willemneal]

An AVL tree is a balanced binary tree ¹, which swaps nodes in the tree as elements are inserted and deleted in order to maintain the minimum height of the tree. This ensures that the worst case for accessing an element is O(log n), versus O(n) for a normal binary tree.

Currently smart contracts on NEAR provide a Key-Value storage but does not provide an API for accessing/iterating over the keys. Thus this data structure can be used to create an ordered map by inserting into the tree keys as values and their key as an increasing counter of all entries.

PersistentOrderedMap provides an example of iterating over the last n elements, but to maintain order it only allows the last entry to be deleted.

Please use an equivalent implementation of AVL Map in Rust for guidance: near/near-sdk-rs#154 It is okay to literally rewrite the above Rust code in AssemblyScript.

API

class AVLTree<K,V> {

  /**
   * A string name is used as a prefix for writing keys to storage.
   */
  constructor(name: string){}

  /**
   * Number of elements in the tree.
   */
  get size(): u32;

  /**
   * Returns whether the key is present in the tree.
   */
  has(key: K): boolean;
  //alias to match rust sdk
  containsKey(key: K): boolean;

  /**
   * If key is not present in the tree, a new node is added with the value.
   * Otherwise update the node with the new value.
   */
  set(key: K, value: V): void;
  //alias to match rust sdk
  insert(key: K, value: V): void;

  /**
   * Get value with key and throw if the key is not in the tree.
   */
  get(key: K): V;

  /**
   * Get value with key and return default value if key is not in the tree.
   */
  getSome(key: K, default: V): V;

  /**
   * Delete element with key if present, otherwise do nothing.
   */
  delete(key: K): void;
  //alias to match rust sdk
  remove(key: K): void;


  /**
   * Get a range of values from a start key to an end key exclusive.
   * If end is greater than max key, include start to max inclusive.
   */
  range(start: K, end: K): V[];

  /**
   * Returns minimum key.
   * Throws if tree is empty.
   */
  min(): K;

  /**
   * Returns maximum key.
   * Throws if tree is empty.
   */
  max(): K;

  /**
   * Returns the minimum key that is strictly greater than the key.
   * Throws if empty or if key is lower than `this.min()`.
   */
  lower(key: K): K;

  /**
   * Returns the maximum key that is strictly less than the key.
   * Throws if empty or if key is higher than `this.max()`.
   */
  higher(key: K): K;

  /**
   * Returns the minimum key that is greater or equal than the key.
   * Throws if empty or if key is lower than `this.min()`.
   */
  lowerOrEqual(key: K): K;

  /**
   * Returns the maximum key that is less or equal than the key.
   * Throws if empty or if key is higher than `this.max()`.
   */
  higherOrEqual(key: K): K;
}

Implementation

Other than the API above and the requirement for the same algorithmic characteristics of a AVL tree, the implementation is open to interpretation.

Testing

There must be tests that cover each edge case. Use PersistentSet as a guide for how to write tests.

Please make sure the implementation contains all tests of AVL tree that were implemented in near/near-sdk-rs#154

[MaksymZavershynskyi]

The other major issue with PersistentOrderedMap is that it has expected O(log n) time complexity. Which means it is possible that if some contract uses it the user of the contract might accidentally encounter the worst case and pay O(n) gas, which can be quite high. For instance if we use skip list for token implementation, and lets say we have 10k accounts in this token, on average users would pay gas for 13 access to storage, but when they hit the worst case they would pay for 10k accesses to storage, which is 1000 times more gas, which does not make a good UX and might actually create issues for the contract. Once AVL tree is implemented we should remove SkipList and SkipList-based implementation.

Also, let's add lowerOrEq and greaterOrEq to the API list.

[willemneal]

I agree that this is better for consistency and to not use skip lists at all, but I just want to point out that if you do have randomness, it would require (1-p)^10000, so p = 1/e: (1-1/e)^10000 = 9.8 * 10^-1993, which while possible is insanely unlikely. The one issue with skip lists is that deleting elements can mess up the balance, so to fix this you have to reflip the height of a neighbor and I don't think you have to do it every time.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

This issue now has a funding of 300.0 DAI (300.0 USD @ $1.0/DAI) attached to it.

• If you would like to work on this issue you can 'start work' on the Gitcoin Issue Details page.
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Chat
• $134,254.42 more funded OSS Work available on the Gitcoin Issue Explorer

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work has been started.

These users each claimed they can complete the work by 1 month from now.
Please review their action plans below:

1) kaiba42 has been approved to start work.

1. Create skeleton for AVLTree implementation following the given API, matching the rust-sdk implementation.
2. Implement set of tests based on rust-sdk tests. Tests should provide full coverage of public and internal methods, in addition to testing the invariants of an AVL tree. Need to also find an alternative to quickcheck for AssemblyScript for fuzz/prop testing (any suggestions would be great!). Or at least use as-pect tests similar to those mentioned above.
3. Implement AVLTree.
4. Confirm that tests are all passing, and implemented correctly.

Learn more on the Gitcoin Issue Details page.

[kaiba42]

Is there an API for iteration that should be followed? Put another way, what is the API for iterating through existing collections like persistentMap or persistentSet? Thanks!

[willemneal]

I'm about to merge a new PR that creates a new Unordered map, #85, which uses a persistent vector to hold the keys. The keys are then ordered until a key before than the last two is deleted, which causes the last key to be swapped with the index of the key being removed. The AVL tree will remove this limitation.

As for iteration, AssemblyScript is missing iteration (it's a work in progress) and so in #85, which also updates persistentSet, there are methods for ranges that return arrays of values, keys, and entries. So frontend code can get the size of the map and then perform the iteration by using these methods. An Ordered map will use this tree to provide the same API.

[kaiba42]

Got it. Does this API for an AVLTree look good to you then? It swaps range() for values(), keys(), and entries(), following your API for the new Unordered map implementation.

API

class AVLTree<K, V> {
    private _elementPrefix: string;

    /**
     * A string name is used as a prefix for writing keys to storage.
     */
    constructor(name: string) {
        this._elementPrefix = name + collections._KEY_ELEMENT_SUFFIX;
    }
  
    /**
     * @returns Number of elements in the tree.
     */
    get size(): u32 {
        // TODO implement size()
        throw new Error("TODO implement size()")
    }

    /**
     * @returns Root key of the tree.
     */
    get root(): K {
        // TODO make private
        // TODO implement root()
        throw new Error("TODO implement root()")
    }
  
    /**
     * @returns Whether the key is present in the tree.
     */
    has(key: K): boolean {
        // TODO implement has()
        throw new Error("TODO implement has()")
    }
    //alias to match rust sdk
    containsKey(key: K): boolean {
        return this.has(key);
    }
  
    /**
     * If key is not present in the tree, a new node is added with the value.
     * Otherwise update the node with the new value.
     * 
     * @param key Key of the element.
     * @param value The new value of the element. 
     */
    set(key: K, value: V): void {
        // TODO implement set()
        throw new Error("TODO implement set()")
    }
    //alias to match rust sdk
    insert(key: K, value: V): void {
        this.set(key, value);
    }
  
    /**
     * Retrieves a related value for a given key or throws error "key not found"
     * 
     * @param key Key of the element.
     * @returns Value for the given key or the default value.
     */
    get(key: K): V {
        // TODO implement get()
        throw new Error("TODO implement get()")
    }
  
    /**
     * Retrieves the related value for a given key, or uses the `defaultValue` if not key is found
     * 
     * @param key Key of the element.
     * @param defaultValue The default value if the key is not present.
     * @returns Value for the given key or the default value.
     */
    getSome(key: K, defaultValue: V): V {
        try {
            return this.get(key);
        } catch(err) { // TODO check that this is key not found error
            return defaultValue;
        }
    }
  
    /**
     * Delete element with key if present, otherwise do nothing.
     * 
     * @param key Key to remove.
     */
    delete(key: K): void {
        // TODO implement delete()
        throw new Error("TODO implement delete()")
    }
    //alias to match rust sdk
    remove(key: K): void {
        this.delete(key);
    }
  
  
    /**
     * Get a range of values from a start key to an end key exclusive.
     * If end is greater than max key, include start to max inclusive.
     * 
     * @param start Key for lower bound (inclusive).
     * @param end Key for upper bound (exclusive).
     * @returns Range of values corresponding to keys within start and end bounds.
     */
    values(start: K, end: K): V[] {
        // TODO implement range()
        throw new Error("TODO implement values()");
    }

    /**
     * Get a range of keys from a start key to an end key exclusive.
     * If end is greater than max key, include start to max inclusive.
     * 
     * @param start Key for lower bound (inclusive).
     * @param end Key for upper bound (exclusive).
     * @returns Range of keys within start and end bounds.
     */
    keys(start: K, end: K): K[] {
        // TODO implement range()
        throw new Error("TODO implement range()");
    }

    /**
     * Get a range of entries from a start key to an end key exclusive.
     * If end is greater than max key, include start to max inclusive.
     * 
     * @param start Key for lower bound (inclusive).
     * @param end Key for upper bound (exclusive).
     * @returns Range of entries corresponding to keys within start and end bounds.
     */
    entries(start: K, end: K): MapEntry<K, V>[] {
        // TODO implement range()
        throw new Error("TODO implement range()");
    }
  
    /**
     * Returns minimum key.
     * Throws if tree is empty.
     * @returns Minimum key.
     */
    min(): K {
        // TODO implement min()
        throw new Error("TODO implement min()");
    }
  
    /**
     * Returns maximum key.
     * Throws if tree is empty.
     * @returns Maximum key.
     */
    max(): K {
        // TODO implement max()
        throw new Error("TODO implement max()");
    }
  
    /**
     * Returns the maximum key that is strictly less than the key.
     * Throws if empty or if key is lower than or equal to `this.min()`.
     * @param key Key for lower bound (exclusive).
     * @returns Maximum key that is strictly less than given key.
     */
    lower(key: K): K {
        // TODO implement lower()
        throw new Error("TODO implement lower()");
    }
  
    /**
     * Returns the minimum key that is strictly greater than the key.
     * Throws if empty or if key is higher than or equal to `this.max()`.
     * @param key Key for upper bound (exclusive).
     * @returns Minimum key that is strictly greater than given key.
     */
    higher(key: K): K {
        // TODO implement higher()
        throw new Error("TODO implement higher()");
    }
  
    /**
     * Returns the maximum key that is less or equal than the key.
     * Throws if empty or if key is lower than `this.min()`.
     * @param key Key for lower bound (inclusive).
     * @returns Maximum key that is less than or equal to given key.
     */
    lowerOrEqual(key: K): K {
        // TODO implement lowerOrEqual()
        throw new Error("TODO implement lowerOrEqual()");
    }
    //alias to match rust sdk
    floorKey(key: K): K {
        return this.lowerOrEqual(key);
    }
  
    /**
     * Returns the minimum key that is greater or equal than the key.
     * Throws if empty or if key is higher than `this.max()`.
     * @param key Key for upper bound (inclusive).
     * @returns Minimum key that is greater or equal to given key.
     */
    higherOrEqual(key: K): K {
        // TODO implement higherOrEqual()
        throw new Error("TODO implement lowerOrEqual()");
    }
    //alias to match rust sdk
    ceilKey(key: K): K {
        return this.higherOrEqual(key);
    }

    /**
     * Removes all key-value pairs from the tree
     */
    clear(): void {
        // TODO implement clear()
        throw new Error("TODO implement clear()")
    }
}

[willemneal]

Sounds good, but keep an alias for range, since we want to match the Rust API.

[gitcoinbot]

@kaiba42 Hello from Gitcoin Core - are you still working on this issue? Please submit a WIP PR or comment back within the next 3 days or you will be removed from this ticket and it will be returned to an ‘Open’ status. Please let us know if you have questions!

• reminder (3 days)
• escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

@kaiba42 due to inactivity, we have escalated this issue to Gitcoin's moderation team. Let us know if you believe this has been done in error!

• reminder (3 days)
• escalation to mods (6 days)

Funders only: Snooze warnings for 1 day | 3 days | 5 days | 10 days | 100 days

[kaiba42]

^ thinking I need to add a comment to address this...

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work for 300.0 DAI (300.0 USD @ $1.0/DAI) has been submitted by:

1. @kaiba42

@nearmax please take a look at the submitted work:

• PR by @kaiba42

---

• Learn more on the Gitcoin Issue Details page
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Chat
• $174,686.08 more funded OSS Work available on the Gitcoin Issue Explorer

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

The funding of 300.0 DAI (300.0 USD @ $1.0/DAI) attached to this issue has been approved & issued to @kaiba42.

• Learn more on the Gitcoin Issue Details page
• Questions? Checkout Gitcoin Help or the Gitcoin Chat
• $167,509.33 more funded OSS Work available on the Gitcoin Issue Explorer