[GUI Library] SerraUnitIndexing

[SerraAvenger]

A simplistic indexing library. Please use this together with an interface, don't use these functions directly.

API
SUI_GetUnitIndex( u ) -> int, Gets a unique index for every unit. If the unit previously had none, a new one will be allocated.
SUI_GetUnitByIndex( i ) -> unit, returns a unit associated with the index such that u == SUI_GetUnitByIndex( SUI_GetUnitIndex( u ) ) always holds true. Thanks to Jesus4Lyf for this idea!
SUI_GetCustomValue() -> int, returns a new, unique custom value every time it is called.


Restrictions
Only 400 units that had custom indicies may be dead at a time
Only 2048 units that have custom indicies may be in a map at any time.
The custom value with the id "IdentificationIndex" may not be used. By default, the IdentificationIndex is 1337.
If those doesn't work for you (for any possible reason), just change the values.
This work is published under the NonCommercial Sampling Plus CreativeCommons license.

Please also see...
UnitIndexing, the interface this is meant to be used with.

FAQ
Q<HELP! Everything is only "Untitled blabla"! I can't use this!
A>That is normal. You are probably in standard GUI mode. In order to see function & variable names, press Ctrl+D (raw mode). HOWEVER that is only if you want to look at the code. If you want to use this library, go to UnitIndexing and follow the steps under "how to use this?">SerraUnitIndexing. Don't use functions from this library (or any Indexer) directly. ESPECIALLY if you're coding your own library.

ChangeLog
6/18/2010 - Added UnitGetByIndex(). Fixed a little bit of stuff such that the changeable variables are visible from standard GUI. V0.3
6/11/2010 - Fixed recycling bug. V0.2

 

[SerraAvenger]

bump

 

[Steel]

All your variables and triggers load with "Untitled <type>". Each function, variable, etc. Not sure if this is on my end, something like disallowing an imported library to generate variable names. Couldn't find anything in the preferences.

Ok, I tried to power through this with everything named Untitled Variable 001, I don't think you have a good enough recycle function. It does what it's supposed to but it is slow. I can give you a more in depth analysis if you want it and this variable thing gets resolved.

 

[GetTriggerUnit-]

Does the same thing in my editor.

*Is the a way to convert to custom text, yet?

 

[SerraAvenger]

All your variables and triggers load with "Untitled <type>". Each function, variable, etc. Not sure if this is on my end, something like disallowing an imported library to generate variable names. Couldn't find anything in the preferences.

You were supposed to use this with UnitIndexing.
If you want to read this piece of code, use Ctrl+D. The Interface has GUI names, this one only has raw names = )

Ok, I tried to power through this with everything named Untitled Variable 001, I don't think you have a good enough recycle function. It does what it's supposed to but it is slow. I can give you a more in depth analysis if you want it and this variable thing gets resolved.

Indeed, a more in-depth analysis would be apreciated. Especially about the recycling and the speed : )
Again, pressing Ctrl+D makes the code readable (it's not supposed to be used directly)

>*Is the a way to convert to custom text, yet?
Depends on what you want.
Ctrl+F11 compiles the map script and shows it to you, if that's what you want = )

EDIT:
Btw, the fact that you see everything like that stems from the fact that I only code in Raw mode (Ctrl+D). Automatically generating the GUI identifiers from the script identifiers should, but does not, work.
Since, however, the UnitIndexer is the library that the end user (who is probably not galaxy-proficient) should use, I think giving everything a name is neither worth the hassle nor needed. In fact, giving it standard GUI names would only increase the likeliness of this being used directly - which does (ofc) work, but is pretty dumb.

EDIT2:
Found a critical bug where I had put 0 instead of NextFreeIndex. Recycling should not have worked hence. Fixed and uploaded fixed version.
EDIT3: Seems I didn't upload the fixed version -.-

 

[Steel]

I'll look at it after work but here is something you should think about:
Do I want the recycle or the lookup method to be faster?

Usually a speed increase to the lookup is better to look for. Since you're processing an unsorted amount of data it becomes difficult to increase speed without a reference point because you're just traversing every element. If you have 400 elements in your array and you start at 0 each time and what you're looking for is in the last position you still have to pass over each element. So every time you reference that unit you take the longest time possible, which is n (n in this case being 400). If you can do something like sorting these items by the unit's name, you can cut down on time needed to find the necessary unit. Visual Example:


array[0] = "Admiral Raynor"
array[1] = "Hydralisk"
array[2] = "Hydralisk"
array[3] = "Hydralisk"
array[4] = "Larva"
array[5] = "Larva"
array[6] = "Marine"
array[7] = "Marine"
array[8] = "Marine"
array[9] = "Marine"
array[10] = "Observer"

Even though you are ordering them by string and creating duplicates, it's a faster method. You wouldn't store them based on their name, you would still use the unique Unit datatype to identify them, Marine is just your key. Since the data is sorted you can easily implement a number of search methods to get what you need. You should be able to find the algorithmic differences between list traversal and other various lookup methods out there.


Another thing I hinted on was that each time you reference the unit you're talking about you need to look it up. Sure, in a single function you could do something like...
lv_unitNew = SerraUnitIndexingFind(<someunit>)
Then just go about using lv_unitNew. However, if you reference it multiple times, especially in quick succession outside of the same functions, you're going to get a performance hit. You might want to think about making a cache for quick referencing units. It's less practical for a dataset of only 400 though, if you get up to something like a thousand or more, it would be worth it.

This is really complex stuff, it's fun if you want to tinker around with things but this isn't anything you should bend over backwards to worry about.

 

[SerraAvenger]

Short reply:
I'm using UnitData for lookup and should have constant lookup time. No iterative search, unless the GUI unit user data does use iterative search itself.
Indexing and recycling is both constant time, too. More later, gtg = )

EDIT:



>Another thing I hinted on was that each time you reference the unit you're talking about you need to look it up. Sure, in a single function you could do something like...
lv_unitNew = SerraUnitIndexingFind(<someunit>)
Then just go about using lv_unitNew. However, if you reference it multiple times, especially in quick succession outside of the same functions, you're going to get a performance hit. You might want to think about making a cache for quick referencing units. It's less practical for a dataset of only 400 though, if you get up to something like a thousand or more, it would be worth it.

The thing is just: If I could cache it easily, this wouldn't be needed = )
Please also note that the data set could get any size; Just the amount of indicies that are about to be recycled should never get bigger than 400.

>Usually a speed increase to the lookup is better to look for.
That's absolutely true.
Right now the lookup reads as (if the unit has an index)

func UnitGetIndex( u unit) int {
 return (int) UnitCustomValueGet( u, 1337 ) // UnitCustomValueGet returns a float :(
}

As you can see, the speed of this function only depends on the UnitCustomValueGet (? not sure if that's the right term) function from Ntve.
AMOF, I'm only having another int comparision (which will fail for an indexed unit).

Allocating a new/reusing an old index is constant time: a couple of variable lookups, an array lookup in the worst case and two variable sets.

Recycling an old index (that is, freeing the index such that it can be used again) has about the same cost as allocating/reusing an index.

So the only thing that really determines speed in my code is the UnitCustomValueGet function.

I could try tinkering with the value index (1337) and see if that makes the code go faster or something. I don't believe it though.

 

[Jesus4Lyf]

Is this the same?

 

[SerraAvenger]

Is this the same?

Haven't seen it yet, but not exactly. I've just looked at yours and there's couple of (small) differences.
Same:
You're using the same algorithms for allocation/deallocation of indicies.
You're auto-deallocating
Different:
Code behaviour/Possibilities
You're auto-allocating - which makes yours a tiny tad faster in a lot of situations, but probably also generates lots of garbage. The main problem would be for maps with lots of units, where auto-allocation can easily overflow standard array sizes.
You're just using 0 as the custom index, which can be dangerous
You have the possibility to retrieve the unit by Index. I think I should also implement this for my library, though.
You don't have a AllocateCustomValue function (not that it's needed or anything interesting, I thought I'd just point this out)
Documentation/Usability:
You haven't linked to my interface. Especially as there's two systems now, using an interface is crucial.
You should post a small description of what it does, too.
Since you're not linking to my interface, I think I also have to mention that you're a) not using labels, which makes your functions basically unusable in GUI, b) you're using JASS naming conventions, which sucks (UnitGetIndex?), c) you're not usable for a base system that other systems require because you don't show a library id.
EDIT: d), for the same reasoin as c), your library can't even be used in my interface!

As you can probably see, the main difference is that my library is much better documented and easier to use and links to the interface; While your library can easily cause unnecessary array overflows and is a tad faster.
I'll add your IndexGetUnit function tho', since I like it a lot = ) Good idea there! It aids GUIlers a lot ; ) (pun intended)
EDIT: PS: just using "UnitIndexer" as a name for a whole Library is a little tad megalomaniac, isn't it? It kinda suggests that this is the one and only Unit Indexer = ) I know that my Interface is named UnitIndexing, but it is only a shallow interface everyone should be using anyway.