[Snippet] AVL Tree

[Nestharus]

This resource has moved here.

--

gone

 

[Magtheridon96]

Looks cool

I tested it in-game with multiple nodes and it seemed to work perfectly.

I wonder what I could use this for

 

[Nestharus]

I needed it for the complex item catalog I'm working on. It includes level specific gear, meaning that I had to search for level ranges (needed AVL Tree for that). Also included dynamically generated catalogs specific for hero inventories (if hero has like lowest level item of 6 and highest level item of 10, item levels 6-10 will be saved instead of like 1-15). For that item level stuff, I again needed AVL Tree =).

edit
Ah, I didn't test the delete method. Did you test it mag?

 

[Bribe]

Why not use the vJass built-in method operator "<"? Seems
like the best opportunity to use it.

Edit: I'm guessing you've chosen to ignore that one. Well basically
the thing here is: no description, expect users to google search,
the only practical wc3 example I've seen this in was in save/load
w/ snippets.

I recommend maybe promoting the description much better than
what it currently is - state what kinds of cases this would be used
for. What it is now is basically a copy + paste and language
translation of someone else's code. Perhaps state "this is useful
for save/load".

 

[Nestharus]

I'm not going to be teaching common data structures and their uses if that's what you want.


If it was my own, that'd be another story.

 

[Magtheridon96]

http://en.wikipedia.org/wiki/AVL_tree

You could link this somewhere in the first post

 

[Nestharus]

Actually, since the wikipedia page might confuse people, I will put up a link I found on it.

 

[Troll-Brain]

Actually, since the wikipedia page might confuse people, I will put up a link I found on it.

Or improve yourself the wiki page

 

[Magtheridon96]

This could actually be useful for a balancing system.
I could start out with the root.
If a hero in my map is too overpowered, I go down from the root and move left.
If a he's losing, I'll move right.

Let's say he died, killed, died, died, and killed.

I'd be going like this:

Root -> left -> right -> left -> left -> right

If I hit a dead-end, I'll just go to the root

 

[Nestharus]

uhh no, lol


Think of it like a hashtable where you can search for the closest value to a value.


In a hashtable, you can store any value but you can't do a search for the closest value. In this, you can store any value and do the search. In arrays and linked lists, the search is very costly.

 

[Magtheridon96]

Cool ^^
I already have a use for this

 

[Nestharus]

Added a searchClose method ; )


Very useful for item catalogs filtered with levels in save/load ; )

 

[Magtheridon96]

        method search takes thistype val returns thistype
            if (table.has(val)) then
                return table[val]
            endif
            return 0
        endmethod

Owned
Congrats bro, you turned an O(log n) algorithm to an O(1) ^_^

 

[Bribe]

It would be saner to just do this:

method search takes thistype val returns thistype
    return return table[val]
endmethod

The table will return 0 if the value is unlisted.

 

[Laiev]

return return?

 

[Nestharus]

I must say, I have never seen return return before...


and also, as I stated before, reading an un-initialized value initializes that value, thus slowing down the table etc. Also the initialization is very slow ; ).

 

[Bribe]

Yo dawg I heard you like return so I gave you return return so you can have a return to go with a return.

php

return $return

reply

Does the value really get initialized then? I will do a test where I use "LoadInteger(ht, 0, 0)" and then check if "HaveSavedInteger(ht, 0, 0)" returns true then.

 

[Nestharus]

All right, fixed all remaining bugs, added linked list to this so that values can be looped through in ascending or descending order, etc.

searchClose now officially 100% accurately works ; )


Also, it's like impossible to break this thing Oo. The only way to break this thing is to pass in a node that is not allocated ; D. You can pass in any node on the tree and it'll still work : P.

 

[Bribe]

The public API is quite good. This being a very advanced data structure reading the code has a huge learning curve, though I was able to decypher another area you could improve on though it's not much.

            if (not low) then
                if (v[this].lessThan(val)) then
                    set this=next
                endif
                if (v[this].greaterThan(val)) then
                    return this
                endif
            else
                if (v[this].greaterThan(val)) then
                    set this=prev
                endif
                if (v[this].lessThan(val)) then
                    return this
                endif
            endif

//Should be:

            if low then
                if (v[this].greaterThan(val)) then
                    set this=prev
                endif
                if (v[this].lessThan(val)) then
                    return this
                endif
            else
                if (v[this].lessThan(val)) then
                    set this=next
                endif
                if (v[this].greaterThan(val)) then
                    return this
                endif
            endif

 

[Nestharus]

Fixed clear method for empty trees.

 

[Bribe]

See where adding safety (non-debug) can be useful?

 

[Troll-Brain]

See where adding safety (non-debug) can be useful?

He will never admit it.
Speedfreak is such a code curse.

 

[Magtheridon96]

In my maps, I usually spam debug-only safety for really crazy things like integers not getting initialized, bad parameters being passed, and the like and I use non-debug-only safety for everything else.

 

[Nestharus]

Uh, I only implement non debug safety when the thing can break with all valid arguments and valid usage. For example, clear can break when used correctly.

I don't add safety for checking against invalid arguments or invalid usage. For example, calling deallocate 2x in a row (invalid usage) or passing a deallocated node to be added to a list (invalid argument).

 

[Troll-Brain]

Uh, I only implement non debug safety when the thing can break with all valid arguments and valid usage. For example, clear can break when used correctly.

I don't add safety for checking against invalid arguments or invalid usage. For example, calling deallocate 2x in a row (invalid usage) or passing a deallocated node to be added to a list (invalid argument).

But sometimes such cases happen (plz don't tell me you never do these mistakes, i won't believe you), and it would work fine if there was a safety check, however sometimes it still won't work.

 

[Nestharus]

Yea, I make those mistakes when I do a completely library rewrite with no testing, but I fix all of the mistakes rather than keep them in there, hence why they are debug only. Bad code is bad code, don't keep your stuff broken just because you are too lazy to fix it.


What I do with debug safety now is completely crash the thread and display an error message that way you can figure out exactly where the bug occurred rather than have everything keep running. I do it by setting some var to 1/0. I now make it so that maps are completely unplayable if there are mistakes in the code, whether the debug safety is on or not. If debug safety is on, the system will crash. If debug safety is off, the system will still crash but w/o warning. In fact, Timer Tools completely disables itself if it encounters any bugs.

 

[Troll-Brain]

Bad code is not always catched.

Well, end of story for me, i knew what you will said anyway, you will never change your mind, so it's pointless to argue more about it.

EDIT :

I would rather have a map with an uncatched bad code, but still working because of the extra check safety "overhead", rather than a bugged map without this extra "overhead", all the times.
Not to mention than in case of a public resource, you're (potentially) not the only one user.

 

[Nestharus]

Fixed bug with clear command ; )

Forgot to flush the table, lolz.

 

[Nestharus]

Removed all information in the description that was not pertinent to this resource. If you don't know what an AVL Tree is then google it.


This updated description is in open defiance to Bribe's need for me to explain what things like linked lists, trees, and so on are in the docs. If it's a public data structure, you can google the information on wikipedia yourself. If it's a structure that is completely custom, like my crazy tree thing that sorts units, then that should require a description as you can't google it ; ).


Notice that I have absolutely no description on Binary Heap as it is a standard Binary Heap implementation. I'm never going to add a description either >.>.

 

[Bribe]

Another problem with not adding descriptions for "googlible" resources is that certain keywords might be unintuitive (ie. some people use "push/pop", others "add/remove" or "queue/dequeue" so the API at the least should clarify in case you suspect some people might be confused).

 

[Nestharus]

Every method that is possibly vague does have a description on it : ).

Also
push/pop is used for stacks
enqueue/dequeue is used for queues

when all 4 are used, that's a dequeue

add/remove is generally used for doubly linked lists (at least in the wc3 community).

insert/delete are generally used for tables, but I use them in my Binary Heap thing for some reason, lol.

 

[Bribe]

Fair enough in my opinion.