WARNING AS100: Not implemented: Template Literals can only be used for multi-line strings. Interpolation is not supported.
throw new Error(`key is less than mininum key in tree`);
else return root.key;
}
/**
- 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 {
let root = this.rootNode!;
while (root.left || root.right) {
if (root.key <= key && root.right) {
root = this.node(root.right)!;
} else if (root.right) {
const leftNode = this.node(root.left)!;
if (leftNode.key > key) {
root = leftNode;
} else {
break;
}
}
}
if (root.key <= key)
throw new Error(`key is greater than maximum key in tree`);
else return root.key;
}
/**
- 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 {
return this.has(key) ? key : this.lower(key);
}
// 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 {
return this.has(key) ? key : this.higher(key);
}
// alias to match rust sdk
ceilKey(key: K): K {
return this.higherOrEqual(key);
}
/**
- Removes all key-value pairs from the tree
*/
clear(): void {
while (this.size > 0) {
this._val.delete(this._tree.popBack().key);
}
this.rootId = null;
}
// useful for debugging
private toString(): string {
const a: string[] = ["\n"];
for (let i: i32 = 0; i < i32(this.size); ++i) {
const node = this._tree[i];
const key = u32(node.key).toString();
const index = node.id.toString();
const leftKey = node.left
? u32(this.node(node.left)!.key).toString()
: "null";
const rightKey = node.right
? u32(this.node(node.right)!.key).toString()
: "null";
const isRoot = node.id === this.rootId!.val ? "true" : "false";
const childrenProperties: string[] = [leftKey, rightKey, isRoot];
const nodeProperties: string[] = [
key,
",",
index,
":",
childrenProperties.join(),
];
a.push(nodeProperties.join(" "));
}
return a.join("\n");
}
/**
*/
// returns root key of the tree.
get rootKey(): K {
assert(!isNull(this.rootNode), "rootNode must be defined");
return this.rootNode!.key;
}
private set rootId(rootId: Nullable | null) {
this._rootId = rootId;
storage.set(this._elementPrefix + "root", this._rootId);
}
private get rootId(): Nullable | null {
return this._rootId;
}
// returns the root node of the tree, if it exists.
// returns null otherwise
private get rootNode(): AVLTreeNode | null {
return this.node(this.rootId);
}
// returns the height for a given node
private nodeHeight(id: Nullable | null): u32 {
return id ? this._tree[id.val].height : 0;
}
// returns the difference in heights between a node's left and right subtrees
private balance(node: AVLTreeNode): i32 {
return this.nodeHeight(node.left) - this.nodeHeight(node.right);
}
// updates the height for a given node based on the heights of its subtrees
private updateHeight(node: AVLTreeNode): void {
node.height =
1 + max(this.nodeHeight(node.left), this.nodeHeight(node.right));
this._tree[node.id] = node;
}
// returns the node for the given id (index into underlying array this._tree)
private node(id: Nullable | null): AVLTreeNode | null {
return id ? this._tree[id.val] : null;
}
// inserts a new key into the tree and
// recursively updates the height of each node in the tree,
// performing rotations as needed from bottom to top
// to maintain the AVL tree balance invariant
private insertAt(parentNode: AVLTreeNode | null, key: K): AVLTreeNode {
if (!parentNode) {
const node = new AVLTreeNode(this.size, key);
this._tree.push(node);
return node;
} else {
if (key < parentNode.key) {
parentNode.left = new Nullable(
this.insertAt(this.node(parentNode.left), key).id
);
} else if (key > parentNode.key) {
parentNode.right = new Nullable(
this.insertAt(this.node(parentNode.right), key).id
);
} else {
throw new Error(
"Key already exists, but does not have an associated value"
);
}
this.updateHeight(parentNode);
return this.enforceBalance(parentNode);
}
}
// given a node
// performs a single set left and right rotations to maintain AVL tree balance invariant
private enforceBalance(node: AVLTreeNode): AVLTreeNode {
const balance = this.balance(node);
if (balance > 1) {
// implies left child must exist, since balance = left.height - right.height
const leftChildNode = this.node(node.left)!;
if (this.balance(leftChildNode) < 0) {
node.left = new Nullable(this.rotateRight(leftChildNode).id);
}
return this.rotateLeft(node);
} else if (balance < -1) {
// implies right child must exist
const rightChildNode = this.node(node.right)!;
if (this.balance(rightChildNode) > 0) {
node.right = new Nullable(this.rotateLeft(rightChildNode).id);
}
return this.rotateRight(node);
} else {
// node is already balanced
return node;
}
}
// given a node
// performs a righthand rotation
// node child
// \ /
// child -> node
// /
// child.left child.right
private rotateRight(node: AVLTreeNode): AVLTreeNode {
const childNode = this.node(node.right)!;
node.right = childNode.left;
childNode.left = new Nullable(node.id);
this.updateHeight(node);
this.updateHeight(childNode);
return childNode;
}
// given a node
// performs a lefthand rotation
// node child
// /
// child -> node
// \ /
// child.right child.right
private rotateLeft(node: AVLTreeNode): AVLTreeNode {
const childNode = this.node(node.left)!;
node.left = childNode.right;
childNode.right = new Nullable(node.id);
this.updateHeight(node);
this.updateHeight(childNode);
return childNode;
}
// removes the given key from the tree, maintaining the AVL balance invariant
private doRemove(key: K): Nullable | null {
const nodeAndParent = this.lookupAt(this.rootNode!, key);
let node = nodeAndParent.child;
let parentNode = nodeAndParent.parent;
let successorId: Nullable | null;
if (!node.left && !node.right) {
// node to remove is a leaf node
if (parentNode.key < node.key) {
parentNode.right = null;
} else {
parentNode.left = null;
}
successorId = null;
} else if (!node.left) {
// node to remove has 1 right child
// replace node to remove with its right child
if (parentNode.key < node.key) {
parentNode.right = node.right;
} else {
parentNode.left = node.right;
}
successorId = node.right;
} else if (!node.right) {
// node to remove has 1 left child
// replace node to remove with its left child
if (parentNode.key < node.key) {
parentNode.right = node.left;
} else {
parentNode.left = node.left;
}
successorId = node.left;
} else {
// node has 2 children, search for successor
const isLeftLeaning = this.balance(node) >= 0;
const nodes = isLeftLeaning
? // node to remove is left leaning, so search left subtree
this.maxAt(this.node(node.left)!, node)
: // node to remove is right leaning, so search right subtree
this.minAt(this.node(node.right)!, node);
const successor = nodes.child;
// node to remove and parentNode can be the same node on small trees (2 levels, 2-3 nodes)
// if so, make parentNode point to node
parentNode = nodes.parent.id === node.id ? node : nodes.parent;
const successorIsLeftChild = parentNode.left
? parentNode.left!.val === successor.id
: false;
// remove successor from its parent, and link the successor's child to its grandparent
if (successorIsLeftChild) {
parentNode.left = isLeftLeaning ? successor.left : successor.right;
} else {
parentNode.right = isLeftLeaning ? successor.left : successor.right;
}
// take successor's key, and update the node to remove
node.key = successor.key;
this._tree[node.id] = node;
successorId = new Nullable(node.id);
// set node to point to successor, so it is removed from the tree
node = successor;
}
this.updateHeight(parentNode);
this.swapRemove(node);
return this.size > 0 && this.rootNode
? new Nullable(this.rebalanceAt(this.rootNode!, parentNode.key).id)
: successorId;
}
// removes the given node from the tree,
// and replaces it with the last node in the underlying array (this._tree)
private swapRemove(node: AVLTreeNode): void {
if (node.id === this.size - 1) {
// node is last element in tree, so no swapping needed
if (node.id === this.rootId!.val) {
this.rootId = null;
}
} else {
const lastNode = this._tree[this.size - 1];
const parentNode = this.lookupAt(this.rootNode!, lastNode.key).parent;
if (lastNode.id === this.rootId!.val) {
this.rootId = new Nullable(node.id);
}
// check to make sure that parentNode and lastNode do not overlap
if (parentNode.id !== lastNode.id) {
// make lastNode's parent point to new index (index of node that lastNode is replacing)
if (parentNode.left ? parentNode.left!.val === lastNode.id : false) {
parentNode.left = new Nullable(node.id);
} else {
parentNode.right = new Nullable(node.id);
}
// update the parentNode
this._tree[parentNode.id] = parentNode;
}
// update index of lastNode
lastNode.id = node.id;
this._tree[lastNode.id] = lastNode;
}
this._tree.pop();
}
// given a starting node
// returns the leftmost (min) descendant node, and its parent
private minAt(
root: AVLTreeNode,
parentNode: AVLTreeNode | null = null
): ChildParentPair {
return root.left
? this.minAt(this.node(root.left)!, root)
: new ChildParentPair(root, parentNode ? parentNode : root);
}
// given a starting node
// returns the rightmost (max) descendant node, and its parent
private maxAt(
root: AVLTreeNode,
parentNode: AVLTreeNode | null = null
): ChildParentPair {
return root.right
? this.maxAt(this.node(root.right)!, root)
: new ChildParentPair(root, parentNode ? parentNode : root);
}
// given a key and a starting node
// returns the node with the associated key, as well as its parent (if it exists)
// caution: this method assumes the key exists in the tree, and will throw otherwise
private lookupAt(
root: AVLTreeNode,
key: K,
parentNode: AVLTreeNode | null = null
): ChildParentPair {
return root.key === key
? new ChildParentPair(root, parentNode ? parentNode : root)
: key < root.key
? this.lookupAt(this.node(root.left)!, key, root)
: this.lookupAt(this.node(root.right)!, key, root);
}
// recursively updates the height of each node in the tree,
// and performs rotations as needed from bottom to top
// to maintain the AVL tree balance invariant
private rebalanceAt(root: AVLTreeNode, key: K): AVLTreeNode {
if (root.key > key) {
const leftChild = this.node(root.left);
if (leftChild) {
root.left = new Nullable(this.rebalanceAt(leftChild, key).id);
}
} else if (root.key < key) {
const rightChild = this.node(root.right);
if (rightChild) {
root.right = new Nullable(this.rebalanceAt(rightChild, key).id);
}
}
this.updateHeight(root);
return this.enforceBalance(root);
}
// recursively checks that each node in the tree is balanced by checking that
// the AVL tree invariant holds:
// any node's left and right subtrees must have a difference in height <= 1
private isBalanced(root: AVLTreeNode | null = this.rootNode): bool {
const b = root ? this.balance(root) : 0;
return b >= -1 && b <= 1 && root
? this.isBalanced(this.node(root.left)) &&
this.isBalanced(this.node(root.right))
: true;
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
in ~lib/near-sdk-core/collections/avlTree.ts(267,23)
WARNING AS100: Not implemented: Template Literals can only be used for multi-line strings. Interpolation is not supported.
throw new Error(`key is greater than maximum key in tree`);
else return root.key;
}
/**
- 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 {
return this.has(key) ? key : this.lower(key);
}
// 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 {
return this.has(key) ? key : this.higher(key);
}
// alias to match rust sdk
ceilKey(key: K): K {
return this.higherOrEqual(key);
}
/**
- Removes all key-value pairs from the tree
*/
clear(): void {
while (this.size > 0) {
this._val.delete(this._tree.popBack().key);
}
this.rootId = null;
}
// useful for debugging
private toString(): string {
const a: string[] = ["\n"];
for (let i: i32 = 0; i < i32(this.size); ++i) {
const node = this._tree[i];
const key = u32(node.key).toString();
const index = node.id.toString();
const leftKey = node.left
? u32(this.node(node.left)!.key).toString()
: "null";
const rightKey = node.right
? u32(this.node(node.right)!.key).toString()
: "null";
const isRoot = node.id === this.rootId!.val ? "true" : "false";
const childrenProperties: string[] = [leftKey, rightKey, isRoot];
const nodeProperties: string[] = [
key,
",",
index,
":",
childrenProperties.join(),
];
a.push(nodeProperties.join(" "));
}
return a.join("\n");
}
/**
*/
// returns root key of the tree.
get rootKey(): K {
assert(!isNull(this.rootNode), "rootNode must be defined");
return this.rootNode!.key;
}
private set rootId(rootId: Nullable | null) {
this._rootId = rootId;
storage.set(this._elementPrefix + "root", this._rootId);
}
private get rootId(): Nullable | null {
return this._rootId;
}
// returns the root node of the tree, if it exists.
// returns null otherwise
private get rootNode(): AVLTreeNode | null {
return this.node(this.rootId);
}
// returns the height for a given node
private nodeHeight(id: Nullable | null): u32 {
return id ? this._tree[id.val].height : 0;
}
// returns the difference in heights between a node's left and right subtrees
private balance(node: AVLTreeNode): i32 {
return this.nodeHeight(node.left) - this.nodeHeight(node.right);
}
// updates the height for a given node based on the heights of its subtrees
private updateHeight(node: AVLTreeNode): void {
node.height =
1 + max(this.nodeHeight(node.left), this.nodeHeight(node.right));
this._tree[node.id] = node;
}
// returns the node for the given id (index into underlying array this._tree)
private node(id: Nullable | null): AVLTreeNode | null {
return id ? this._tree[id.val] : null;
}
// inserts a new key into the tree and
// recursively updates the height of each node in the tree,
// performing rotations as needed from bottom to top
// to maintain the AVL tree balance invariant
private insertAt(parentNode: AVLTreeNode | null, key: K): AVLTreeNode {
if (!parentNode) {
const node = new AVLTreeNode(this.size, key);
this._tree.push(node);
return node;
} else {
if (key < parentNode.key) {
parentNode.left = new Nullable(
this.insertAt(this.node(parentNode.left), key).id
);
} else if (key > parentNode.key) {
parentNode.right = new Nullable(
this.insertAt(this.node(parentNode.right), key).id
);
} else {
throw new Error(
"Key already exists, but does not have an associated value"
);
}
this.updateHeight(parentNode);
return this.enforceBalance(parentNode);
}
}
// given a node
// performs a single set left and right rotations to maintain AVL tree balance invariant
private enforceBalance(node: AVLTreeNode): AVLTreeNode {
const balance = this.balance(node);
if (balance > 1) {
// implies left child must exist, since balance = left.height - right.height
const leftChildNode = this.node(node.left)!;
if (this.balance(leftChildNode) < 0) {
node.left = new Nullable(this.rotateRight(leftChildNode).id);
}
return this.rotateLeft(node);
} else if (balance < -1) {
// implies right child must exist
const rightChildNode = this.node(node.right)!;
if (this.balance(rightChildNode) > 0) {
node.right = new Nullable(this.rotateLeft(rightChildNode).id);
}
return this.rotateRight(node);
} else {
// node is already balanced
return node;
}
}
// given a node
// performs a righthand rotation
// node child
// \ /
// child -> node
// /
// child.left child.right
private rotateRight(node: AVLTreeNode): AVLTreeNode {
const childNode = this.node(node.right)!;
node.right = childNode.left;
childNode.left = new Nullable(node.id);
this.updateHeight(node);
this.updateHeight(childNode);
return childNode;
}
// given a node
// performs a lefthand rotation
// node child
// /
// child -> node
// \ /
// child.right child.right
private rotateLeft(node: AVLTreeNode): AVLTreeNode {
const childNode = this.node(node.left)!;
node.left = childNode.right;
childNode.right = new Nullable(node.id);
this.updateHeight(node);
this.updateHeight(childNode);
return childNode;
}
// removes the given key from the tree, maintaining the AVL balance invariant
private doRemove(key: K): Nullable | null {
const nodeAndParent = this.lookupAt(this.rootNode!, key);
let node = nodeAndParent.child;
let parentNode = nodeAndParent.parent;
let successorId: Nullable | null;
if (!node.left && !node.right) {
// node to remove is a leaf node
if (parentNode.key < node.key) {
parentNode.right = null;
} else {
parentNode.left = null;
}
successorId = null;
} else if (!node.left) {
// node to remove has 1 right child
// replace node to remove with its right child
if (parentNode.key < node.key) {
parentNode.right = node.right;
} else {
parentNode.left = node.right;
}
successorId = node.right;
} else if (!node.right) {
// node to remove has 1 left child
// replace node to remove with its left child
if (parentNode.key < node.key) {
parentNode.right = node.left;
} else {
parentNode.left = node.left;
}
successorId = node.left;
} else {
// node has 2 children, search for successor
const isLeftLeaning = this.balance(node) >= 0;
const nodes = isLeftLeaning
? // node to remove is left leaning, so search left subtree
this.maxAt(this.node(node.left)!, node)
: // node to remove is right leaning, so search right subtree
this.minAt(this.node(node.right)!, node);
const successor = nodes.child;
// node to remove and parentNode can be the same node on small trees (2 levels, 2-3 nodes)
// if so, make parentNode point to node
parentNode = nodes.parent.id === node.id ? node : nodes.parent;
const successorIsLeftChild = parentNode.left
? parentNode.left!.val === successor.id
: false;
// remove successor from its parent, and link the successor's child to its grandparent
if (successorIsLeftChild) {
parentNode.left = isLeftLeaning ? successor.left : successor.right;
} else {
parentNode.right = isLeftLeaning ? successor.left : successor.right;
}
// take successor's key, and update the node to remove
node.key = successor.key;
this._tree[node.id] = node;
successorId = new Nullable(node.id);
// set node to point to successor, so it is removed from the tree
node = successor;
}
this.updateHeight(parentNode);
this.swapRemove(node);
return this.size > 0 && this.rootNode
? new Nullable(this.rebalanceAt(this.rootNode!, parentNode.key).id)
: successorId;
}
// removes the given node from the tree,
// and replaces it with the last node in the underlying array (this._tree)
private swapRemove(node: AVLTreeNode): void {
if (node.id === this.size - 1) {
// node is last element in tree, so no swapping needed
if (node.id === this.rootId!.val) {
this.rootId = null;
}
} else {
const lastNode = this._tree[this.size - 1];
const parentNode = this.lookupAt(this.rootNode!, lastNode.key).parent;
if (lastNode.id === this.rootId!.val) {
this.rootId = new Nullable(node.id);
}
// check to make sure that parentNode and lastNode do not overlap
if (parentNode.id !== lastNode.id) {
// make lastNode's parent point to new index (index of node that lastNode is replacing)
if (parentNode.left ? parentNode.left!.val === lastNode.id : false) {
parentNode.left = new Nullable(node.id);
} else {
parentNode.right = new Nullable(node.id);
}
// update the parentNode
this._tree[parentNode.id] = parentNode;
}
// update index of lastNode
lastNode.id = node.id;
this._tree[lastNode.id] = lastNode;
}
this._tree.pop();
}
// given a starting node
// returns the leftmost (min) descendant node, and its parent
private minAt(
root: AVLTreeNode,
parentNode: AVLTreeNode | null = null
): ChildParentPair {
return root.left
? this.minAt(this.node(root.left)!, root)
: new ChildParentPair(root, parentNode ? parentNode : root);
}
// given a starting node
// returns the rightmost (max) descendant node, and its parent
private maxAt(
root: AVLTreeNode,
parentNode: AVLTreeNode | null = null
): ChildParentPair {
return root.right
? this.maxAt(this.node(root.right)!, root)
: new ChildParentPair(root, parentNode ? parentNode : root);
}
// given a key and a starting node
// returns the node with the associated key, as well as its parent (if it exists)
// caution: this method assumes the key exists in the tree, and will throw otherwise
private lookupAt(
root: AVLTreeNode,
key: K,
parentNode: AVLTreeNode | null = null
): ChildParentPair {
return root.key === key
? new ChildParentPair(root, parentNode ? parentNode : root)
: key < root.key
? this.lookupAt(this.node(root.left)!, key, root)
: this.lookupAt(this.node(root.right)!, key, root);
}
// recursively updates the height of each node in the tree,
// and performs rotations as needed from bottom to top
// to maintain the AVL tree balance invariant
private rebalanceAt(root: AVLTreeNode, key: K): AVLTreeNode {
if (root.key > key) {
const leftChild = this.node(root.left);
if (leftChild) {
root.left = new Nullable(this.rebalanceAt(leftChild, key).id);
}
} else if (root.key < key) {
const rightChild = this.node(root.right);
if (rightChild) {
root.right = new Nullable(this.rebalanceAt(rightChild, key).id);
}
}
this.updateHeight(root);
return this.enforceBalance(root);
}
// recursively checks that each node in the tree is balanced by checking that
// the AVL tree invariant holds:
// any node's left and right subtrees must have a difference in height <= 1
private isBalanced(root: AVLTreeNode | null = this.rootNode): bool {
const b = root ? this.balance(root) : 0;
return b >= -1 && b <= 1 && root
? this.isBalanced(this.node(root.left)) &&
this.isBalanced(this.node(root.right))
: true;
}
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
in ~lib/near-sdk-core/collections/avlTree.ts(294,23)
Expected behavior
A clear and concise description of what you expected to happen.
Screenshots
If applicable, add screenshots to help explain your problem.
Desktop (please complete the following information):
- OS: [e.g. iOS]
- Browser [e.g. chrome, safari]
- Version [e.g. 22]
Alternatively, please attach your package.json file here for more detailed versioning
{
"name": "near",
"version": "1.0.0",
"description": "",
"main": "index.js",
"scripts": {
"test": "echo "Error: no test specified" && exit 1"
},
"keywords": [],
"author": "",
"license": "ISC",
"dependencies": {
"dotenv": "^8.2.0",
"js-sha256": "^0.9.0",
"near-api-js": "^0.35.0",
"near-sdk-as": "^3.0.0-alpha.0"
}
}
![dependabot-preview[bot] avatar](https://avatars.githubusercontent.com/in/2141?v=4 "dependabot-preview[bot]")
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent