• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • ✅ HD Level Design Contest #1 POLL is now OPEN! Check out the stunning visuals of the final entries. 🔗Click here to cast your vote!

[Snippet] AVL Tree

Level 31
Joined
Jul 10, 2007
Messages
6,306
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?
 
Last edited:

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,446
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".
 
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 :p
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
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

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,446
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.

JASS:
            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
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
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).
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
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.
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
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.
 
Level 17
Joined
Apr 27, 2008
Messages
2,455
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.
 
Last edited:
Level 31
Joined
Jul 10, 2007
Messages
6,306
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 >.>.
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
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.
 
Top