No funded issue found.
Check out the Issue Explorer
Be the OSS Funding you wish to see in the world.
Looking to fund some work? You can submit a new Funded Issue here .
Time left
Opened
Issue Type
Workers Auto Approve
Project Type
Time Commitment
Experience Level
Permissions
Accepted
Reserved For
Implement AVL Tree for near-sdk-as
near
AssemblyScript
An AVL tree is a balanced binary tree [1][1], 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](https://github.com/near/near-sdk-as/pull/85/files#diff-ed2627c85f93300ebbbb194eb7fb755a) 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: https://github.com/near/near-sdk-rs/pull/154 It is okay to literally rewrite the above Rust code in AssemblyScript.
## API
```ts
class AVLTree {
/**
* 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](https://github.com/near/near-sdk-as/blob/master/assembly/__tests__/runtime/persistent-set.spec.ts) as a guide for how to write tests.
Please make sure the implementation contains all tests of AVL tree that were implemented in https://github.com/near/near-sdk-rs/pull/154
[1]: https://en.wikipedia.org/wiki/AVL_tree
Setup your profile
Tell us a little about you:
Skills
No results found for [[search]] .
Type to search skills..
Bio Required
[[totalcharacter]] / 240
Are you currently looking for work?
[[ option.string ]]
Next
Setup your profile
Our tools are based on the principles of earn (💰), learn (📖), and meet (💬).
Select the ones you are interested in. You can change it later in your settings.
I'm also an organization manager looking for a great community.
Back
Next
Save
Enable your organization profile
Gitcoin products can help grow community around your brand. Create your tribe, events, and incentivize your community with bounties. Announce new and upcoming events using townsquare. Find top-quality hackers and fund them to work with you on a grant.
These are the organizations you own. If you don't see your organization here please be sure that information is public on your GitHub profile. Gitcoin will sync this information for you.
Select the products you are interested in:
Out of the box you will receive Tribes Lite for your organization. Please provide us with a contact email:
Email
Back
Save
