AVL Tree implementation with TealScript | Algorand | Page 1

hoary olive Oct 24, 2024, 6:03 PM

#

https://github.com/VKappaKV/avlTree/blob/main/projects/avlTree/contracts/AvlTree.algo.ts

Testing out how to implement an AVL Tree in Tealscript.

current error:
throw Error(Cannot resolve type ${type.getText()} (${typeString}));

implementation problem:
AVL tree balance uses <-1 and > +1 to understand balancing rotations for the tree, since negative numbers aren't supported there needs to be a workaround to go about Right case rotations

GitHub

avlTree/projects/avlTree/contracts/AvlTree.algo.ts at main · VKappa...

Contribute to VKappaKV/avlTree development by creating an account on GitHub.

#

@rapid crow

rapid crow Oct 24, 2024, 6:04 PM

#

Hit me with that full stack trace 😎

hoary olive Oct 24, 2024, 6:10 PM

#

Error: Cannot resolve type null (null)
at Compiler.getTypeInfo (C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:714:15)
at Compiler.getTypeInfo (C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:706:36)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:650:61
at Array.forEach (<anonymous>)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:647:37
at Array.forEach (<anonymous>)
at Compiler.getTypeInfo (C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:646:34)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:2079:33
at Array.forEach (<anonymous>)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:2078:58

rapid crow Oct 24, 2024, 6:17 PM

#

looks like node is definitely null somewhere. Might take a look at some of the non-null (!)assertions in your code, e.g.,

  private getBalanceFactor(node: Node): uint64 {
    const res = this.getHeight(node.left!) - this.getHeight(node.right!);
    return node ? res : 0;
  }

hoary olive Oct 24, 2024, 6:22 PM

#

Gotcha, tomorrow I'll refactor a bit to handle those cases ty

rapid crow Oct 24, 2024, 6:24 PM

#

you bet, let us know how it goes

hoary olive Oct 24, 2024, 6:25 PM

#

Btw, I want to make a test to check performances with the AVL tree vs a standard FIFO array

How would you suggest to go about this test?
Opcode cost per txn? Just to see Big O, Big Omega and Big Theta

#

For lookup, insertion, modification and delete

rapid crow Oct 24, 2024, 6:36 PM

#

yes - focusing on op codes makes sense. You could write a test that sums up the op code budget used for transactions processed via the tree or array.

#

I think you'd want to use this: https://tealscript.netlify.app/api/variables/globals/#opcodebudget

hoary olive Oct 25, 2024, 6:03 PM

#

C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:714
throw Error(Cannot resolve type ${type.getText()} (${typeString}));
^

Error: Cannot resolve type null (null)
at Compiler.getTypeInfo (C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:714:15)
at Compiler.getTypeInfo (C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:706:36)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:650:61
at Array.forEach (<anonymous>)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:647:37
at Array.forEach (<anonymous>)
at Compiler.getTypeInfo (C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:646:34)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:2079:33
at Array.forEach (<anonymous>)
at C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules@algorandfoundation\tealscript\dist\lib\compiler.js:2078:58

still getting this error. I did some refactoring to account for uint https://github.com/VKappaKV/avlTree/blob/main/projects/avlTree/contracts/AvlTree.algo.ts

GitHub

avlTree/projects/avlTree/contracts/AvlTree.algo.ts at main · VKappa...

Contribute to VKappaKV/avlTree development by creating an account on GitHub.

#

I've also done a typescript one to compare if something was a problem but the TS one is working, while Tealscript returns me this error #1299070704603496448 message

#

https://github.com/VKappaKV/avlTree/blob/main/projects/avlTree/testing_on_TS/no_negative_avltree.ts

GitHub

avlTree/projects/avlTree/testing_on_TS/no_negative_avltree.ts at ma...

Contribute to VKappaKV/avlTree development by creating an account on GitHub.

#

btw I'm also getting this error in the tsconfig.json

No inputs were found in config file 'c:/Users/Jacopo/Algodevving/avlTree/projects/avlTree/node_modules/@algorandfoundation/tealscript/tsconfig.json'. Specified 'include' paths were '["src/**/*"]' and 'exclude' paths were '["c:/Users/Jacopo/Algodevving/avlTree/projects/avlTree/node_modules/@algorandfoundation/tealscript/dist"]'.

#

@rapid crow

ripe fern Oct 25, 2024, 7:02 PM

#

hoary olive btw I'm also getting this error in the tsconfig.json No inputs were found in co...

I see this intermittently and it seems to be transient--try restarting the typescript server

hoary olive Oct 25, 2024, 7:08 PM

#

ripe fern I see this intermittently and it seems to be transient--try restarting the types...

yeah that works

#

so I guess that's not related to the compiler error

#

Does TealScript support null type?

ripe fern Oct 25, 2024, 7:22 PM

#

hoary olive Does TealScript support null type?

Everything at runtime has to be a uint or bytes

hoary olive Oct 25, 2024, 7:33 PM

#

ripe fern Everything at runtime has to be a uint or bytes

but does it abstract from the compiler for null to "" in bytes? Didn't find anything about it on the docs

ripe fern Oct 25, 2024, 7:34 PM

#

That sounds right, but I have not pushed the boundaries on this

#

But at runtime you can't play with null

hoary olive Oct 25, 2024, 7:35 PM

#

hoary olive C:\Users\Jacopo\AlgoDevving\avlTree\projects\avlTree\node_modules\@algorandfound...

here it returns this error, it would be nice to know since otherwise I have to manually rewrite the implementation for null cases

ripe fern Oct 25, 2024, 7:37 PM

#

type Node = {
  data: uint64;
  left: Node | null;
  right: Node | null;
  leftHeight: uint64;
  rightHeight: uint64;
};```

#

@winter chasm Can you do dis in TealScript?

#

I would imagine you would need to define a non-null value that can serve as null in the logic

#

This endeavor does beg the question of if this logic needs to be performed on chain or off

#

What are you trying to achieve?

hoary olive Oct 25, 2024, 7:44 PM

#

ripe fern What are you trying to achieve?

a priority queue data structure depending on a certain buffer saturation value, on chain

#

can dm you more details if you want

ripe fern Oct 25, 2024, 7:45 PM

#

Is it a secret?

winter chasm Oct 25, 2024, 7:45 PM

#

Neither null or undefined are supported in TEALScript. It also doesn't support union types in general

hoary olive Oct 25, 2024, 7:46 PM

#

hoary olive a priority queue data structure depending on a certain buffer saturation value, ...

But the core implementation should leverage a data structure that keeps performances in reasonable log n for lookups/insert/modification/delete

hoary olive Oct 25, 2024, 7:47 PM

#

ripe fern Is it a secret?

It's a new project and details aren't public pepeblink

ripe fern Oct 25, 2024, 7:47 PM

#

Could you just have a Node that represents null?

hoary olive Oct 25, 2024, 7:48 PM

#

yeah at that point maybe I can get away with using bytes and setting an empty string

#

so maybe something like Node | Bytes

#

and check "" => treat it as null

#

?

ripe fern Oct 25, 2024, 7:49 PM

#

No union types

#

Just have a Node struct that represents null?

hoary olive Oct 25, 2024, 7:53 PM

#

ripe fern No union types

oh right

hoary olive Oct 25, 2024, 7:55 PM

#

ripe fern Just have a Node struct that represents null?

mhh I'm not sure how to integrate it the way you mean it

#

gotta think about it

ripe fern Oct 25, 2024, 7:55 PM

#

Check for equivalence vs the special "null" Node struct value

#

Or

#

Do the Node structs sit in boxes?

hoary olive Oct 25, 2024, 7:56 PM

#

with typeof(NullNode)?

ripe fern Oct 25, 2024, 7:56 PM

#

You could have the absence of a box represent a null node

#

and do box existence checks

hoary olive Oct 25, 2024, 7:58 PM

#

pepethink at first I thought about using one box, because if each node is a box then the txn might run out of box references?

ripe fern Oct 25, 2024, 7:58 PM

#

True

#

You could pack box refs on to other outer txns up to a point

hoary olive Oct 25, 2024, 7:59 PM

#

mmh not the ideal to scale the structure to 100s + of nodes

ripe fern Oct 25, 2024, 7:59 PM

#

OK so that won't work, then

hoary olive Oct 25, 2024, 8:00 PM

#

ripe fern Check for equivalence vs the special "null" Node struct value

I'll try with this one

ripe fern Oct 25, 2024, 8:00 PM

#

What if you just had a property of the Node struct that was a boolean which indicated if it was a null node?

#

type Node = {
  data: uint64;
  left: Node;
  right: Node;
  leftHeight: uint64;
  rightHeight: uint64;
  isNullNode: boolean
}

hoary olive Oct 25, 2024, 8:04 PM

#

if (!node) return { data, left: null, right: null, leftHeight: 1, rightHeight: 1 };

considered this case, where when I insert a new node I have to declare his 2 leafs nulls as it's a new leaf insertion. Instead of null what should I use? It will expect a type Node

#

I can do the boolean, but wouldn't it return an error?

#

maybe something like

type Node = {
  data: uint64;
  left?: Node;
  right?: Node;
  leftHeight: uint64;
  rightHeight: uint64;
  isNullNode: boolean
}

ripe fern Oct 25, 2024, 8:07 PM

#

I need a snack and then will fiddle with this to see if I can get what I have in mind to work

hoary olive Oct 25, 2024, 8:10 PM

#

peepolove ty man

rapid crow Oct 25, 2024, 8:11 PM

#

left: Node || 0 ? catching up, disregard if this suggestion makes no sense ;p

hoary olive Oct 25, 2024, 8:12 PM

#

rapid crow `left: Node || 0` ? catching up, disregard if this suggestion makes no sense ;p

I think this would be the same as an union type since it would convert left to either a Node or uint64

ripe fern Oct 25, 2024, 8:12 PM

#

rapid crow `left: Node || 0` ? catching up, disregard if this suggestion makes no sense ;p

No unions

hoary olive Oct 25, 2024, 8:12 PM

#

what if...yes unions Okayge

ripe fern Oct 25, 2024, 8:13 PM

#

OK hold up

hoary olive Oct 25, 2024, 8:13 PM

#

@winter chasm plz

ripe fern Oct 25, 2024, 8:13 PM

#

Your Node type is infinitely deep

hoary olive Oct 25, 2024, 8:14 PM

#

ripe fern Your Node type is infinitely deep

Each Node has reference to his 2 leafs which reference 2 leafs

ripe fern Oct 25, 2024, 8:14 PM

#

This won't work because you don't have a way to terminate at 2 leaves deep

hoary olive Oct 25, 2024, 8:15 PM

#

In-order Traversal of AVL Tree:
1
2
3
4
5
7
15
17
18
20
25
27
30
35
40
45
48
50
55
60
{"data":15,"left":{"data":5,"left":{"data":3,"left":{"data":1,"left":null,"right":{"data":2,"left":null,"right":null}},"right":{"data":4,"left":null,"right":null}},"right":{"data":7,"left":null,"right":null}},"right":{"data":40,"left":{"data":25,"left":{"data":20,"left":{"data":17,"left":null,"right":{"data":18,"left":null,"right":null}},"right":null},"right":{"data":30,"left":{"data":27,"left":null,"right":null},"right":{"data":35,"left":null,"right":null}}},"right":{"data":50,"left":{"data":45,"left":null,"right":{"data":48,"left":null,"right":null}},"right":{"data":60,"left":{"data":55,"left":null,"right":null},"right":null}}}}

#

this is a print for the Typescript implementation

hoary olive Oct 25, 2024, 8:16 PM

#

ripe fern This won't work because you don't have a way to terminate at 2 leaves deep

~~it terminates at 2 leaves deep~~ nvm

rapid crow Oct 25, 2024, 8:16 PM

#

what about representing it as a terminal node? e.g., sentinel pattern

type Node = {
    ...
    isNullNode: boolean; // whatever value works
};

ripe fern Oct 25, 2024, 8:19 PM

#

I think you could figure out the byte length of a Node struct in storage and then have an array of zero bytes of the same size to use as a placeholder value in the terminal leaves

hoary olive Oct 25, 2024, 8:32 PM

#

ok so if I init the AVL tree with nothing it's a

null

and if I want to start with one it will be :

{"data":1,"left":null,"right":null}

So what you mean is that I should make it look like:

{"data":1, "left": // an empty struct with just the fields , "right": // empty struct}

#

would that pass the compiler check for Node type?

#

I'll try it on typescript first to see if it works

ripe fern Oct 25, 2024, 8:33 PM

#

Neither a null value nor a recursive type is going to work here

#

Also, you mentioned the limit on box references

hoary olive Oct 25, 2024, 8:34 PM

#

yeah...

ripe fern Oct 25, 2024, 8:34 PM

#

    maxKeys: 1,
    allowPotentialCollisions: false,
  });```

hoary olive Oct 25, 2024, 8:34 PM

#

ripe fern ``` root = GlobalStateMap<uint64, Node>({ maxKeys: 1, allowPotentialCol...

that was just to set it up, I can change it

ripe fern Oct 25, 2024, 8:34 PM

#

Does this thing cap out at 64 Nodes?

hoary olive Oct 25, 2024, 8:35 PM

#

isn't the limit for 1 box 32K?

ripe fern Oct 25, 2024, 8:35 PM

#

You are using a GlobalStateMap

#

global storage is capped at 64 k/v pairs

hoary olive Oct 25, 2024, 8:36 PM

#

oh right, will fix it

ripe fern Oct 25, 2024, 8:36 PM

#

And max 128 box refs for an atomic group of 16 app calls

#

So you want to pack Nodes into a big box?

hoary olive Oct 25, 2024, 8:37 PM

#

ripe fern So you want to pack Nodes into a big box?

yep

#

I'm not sure if I should find another data structure to use. But AVL tree made the most sense

ripe fern Oct 25, 2024, 8:38 PM

#

How will you get them out of a big box?

#

Read up to 4kb and then index into an array of Nodes?

hoary olive Oct 25, 2024, 8:40 PM

#

why should the contract do that? the operation it purely needs the AVL for is to understand the address linked to a certain node in the Tree

#

The lookup shouldn't read more than log n. Actually this is an interesting thing to look into, there might be a max node limit that would require another box to represent a subtree

#

But considered the limit on recursive types I might need to look into different types of solutions. Bit of a bummer

ripe fern Oct 25, 2024, 8:42 PM

#

I suspect you are going to find this to be highly constrained by box read/write mechanics

#

If you get max 4kb out of a box, that could be many Nodes, and now you need to find the node you need, so you probably have to iterate over them

#

You'll burn up opcode in a loop trying to find the node you want to modify

hoary olive Oct 25, 2024, 8:44 PM

#

yeah but it's not an array where you have to iterate over 4kb...

ripe fern Oct 25, 2024, 8:44 PM

#

4kb/Node struct byte length

#

If you want a box to be the storage array, you will need to locate whatever Node you want to read or write

#

TypeScript abstracts all this away normally 😉

hoary olive Oct 25, 2024, 8:56 PM

#

Made some calculation, 100 Nodes would result in 7 depths for worst case of lookup. Which for 100 nodes that are represented in 3453 bytes a worst case of approximated 242 bytes. It could then be split in more subtrees in each Box

ripe fern Oct 25, 2024, 8:57 PM

#

Now I think you can start to work out how to work with the box data, which will be extracted as one blob and you'll have to parse it to find any particular Node for read/write ops

hoary olive Oct 25, 2024, 9:00 PM

#

mmh yeah but either way it's not implementable with recursive types so it's probably better if I use another data structure to represent the priority queue

ripe fern Oct 25, 2024, 9:04 PM

#

What if the Node struct was like

type Node = {
  data: uint64;
  leftID: uint64;
  rightID: uint64;
  leftHeight: uint64;
  rightHeight: uint64;

}```

hoary olive Oct 25, 2024, 9:12 PM

#

ripe fern What if the Node struct was like ```ts type Node = { data: uint64; leftID:...

So I use an array of uint64s, calculate the byte for each struct and by knowing the ID I can know the position in the array to skip in the parsed box data?

#

so the ID would most likely be just the position in the array and the connection is changed with rotations etc.

#

pepethink am I right?

#

Btw will think it through. But currently I'm also just thinking if I can shift to another type, either a bitmap or a Merkle tree, but just thoughts

ripe fern Oct 25, 2024, 9:24 PM

#

hoary olive so the ID would most likely be just the position in the array and the connection...

Yeah, this is what I was roughly thinking

winter chasm Oct 26, 2024, 9:55 AM

#

You can create a nullNode like this: const nullNode: Node = castBytes<Node>(bzero(len<Node>()));. You'd probably want to save this in global state or a scratch var each call to use in equality checks.

#AVL Tree implementation with TealScript