• 🏆 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!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[GUI-friendly] Data Structures: Lists

[GUI-Friendly] Data Structures: Lists

System Requirements

This is a collection of systems that allows users to create lists that hold integers. The lists are iterable, which means you can loop over them and access each element. When you remove data from the lists, they automatically change their structure to remain iterateable, which means you can remove elements from them in any order you require. However, when using the provided looping triggers, you should only remove the element that you are currently looping through, otherwise the loop may break.

The main purpose of these data structures is to help in the creation of systems, allowing them to be more modular. You can use it to create MUI spells, too, but I believe there are better options, namely: GUI Spell System by Bribe.

I tried to be as thorough as possible when creating the documentation, so the description of the system ended up being farily big. These systems have been designed to work well for both GUI and JASS users.

This system is a great solution if you need to create multiple collections, instead of just one. Using this system will also spare you from using global variables for your own data structures.

Ordered Iterable Lists

Unordered Iterable Lists

Ordered Sets


Ordered Iterateable Lists v2.0.0

This system facilitates the creation of unordered lists that are iterateable. They are iterateable because you can access all of its elements in order, and it is ordered because the order is constant, working similarly to a queue. You can think of them as "groups" of integers, where each integer can be used to access whatever data you need.

Adding data to the end of a GIOL List is an O(1) operation, which means it will always happen at the same speed, regardless of the size of the List. However, removing data from a GIOL List is an O(N) operaton, which means it takes more time depending on the size of the List.

Technical details:
GIOL lists use an extremely simple algorithm: when you remove an element, the system loops through all other elements of higher index and saves them 1 index lower. Finally, the last index is removed. Because this algorithm is slow, it will generally not be your best choice to use GIOL.

Ordered Iterateable Lists:

Each list has a unique ID that is an integer generated by GMUI. You will need this ID to manipulate the lists and destroy them when you don't need them anymore.

As for the "Lists_Hashtable" hashtable, you can use the unique ID of any GIOL list as a child hashtable. The size of a list is stored in the address 0, while the data is stored in the positive addresses. Therefore, you can use negative addresses for your own purposes.
Hashtable addresses:
0: Size of List
Positive Integers: List Data

How to Import:
  1. Open World Editor. File -> Preferences -> Tick box for "Automatically create unknown variables (...)"
  2. Copy the "GUI MUI Engine" category into your map.
  3. Open the "GMUI Header" trigger and copy its contents into your map header.
  4. Copy the "GUI Iterable Ordered Lists" category into your map.
  5. Open the "GIOL Header" trigger and copy its contents into your map header.
  6. Done!

Using the System:


Add Data

Remove Data

Create List

Destroy List

List Loop

Get Size

Advanced Loop

JASS API


This function adds Data to the last position of an existing list. Please note that conditions should be checked when executing the trigger.

Variables before execution:

Lists_ListID

The ID of the list we want to add data to.

Lists_Instance

We set this to zero because we want to add data, not remove it.

Lists_Data

The Data we want to add to the list.

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListID
    • Set Lists_Instance = 0
    • Set Lists_Data = YourData
    • Trigger - Run GIOL Main <gen> (checking conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: set udg_Lists_Instance = GIOL_Append(udg_Lists_ListID, udg_Lists_Data)

Variables after execution:


Lists_ListID

Same as before.

Lists_Instance

The index of the data added to the list (equal to list's size).

Lists_Data

Same as before.

If you want to know the index the variable was saved in, it will be equal to the size of the List. See "Get Size" function.

This function removes data from a certain address of a list. Please not you should check conditions when executing the trigger.

Variables before execution:


Lists_ListID

The ID of the list we want to remove data from.

Lists_Instance

The index of the data we want to remove from the list.

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListID
    • Set Lists_Instance = YourAddress
    • Trigger - Run GIOL Main <gen> (checking conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: set udg_Lists_Instance = GIOL_Remove(udg_Lists_ListID, udg_Lists_Instance)

Variables after execution:


Lists_ListID

Same as before.

Lists_Instance

Same as before.

This function allows you to create a new list, which you can add data to. Please note that you need to ignore conditions when executing the "GIOL Main" trigger.

Variables before execution:

Lists_ListID

We set this to zero because we want to create a new list.

GUI-only method:
  • Actions
    • Set Lists_ListID = 0
    • Trigger - Run GIOL Main <gen> (ignoring conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: set udg_Lists_ListID = GIOL_CreateList()
Variables after execution:

Lists_ListID

The ID of our newly created list.

This function allows you to destroy a list that you have created. Please note that you need to ignore conditions when executing the "GIOL Main" trigger.

Variables before execution:

Lists_ListID

The ID of the list we want to destroy.

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListID
    • Trigger - Run GIOL Main <gen> (ignoring conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: call GIOL_DestroyList(udg_Lists_ListID)
Variables after execution:

Lists_ListID

Same as before.

This function allows you to iterate over a list like a normal loop, allowing you to manipulate each element in the list. It also allows you to specify how many elements you want to iterate through, and the loop will stop after it reaches that number.

Variable parameters:

Lists_ID

The ID of the list you want to iterate over.

Lists_Trigger

The trigger that should be executed for each element.

Lists_LoopUntil

How many elements should the loop iterate over before it stops

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListId
    • Set Lists_Trigger = YourTrigger
    • Set Lists_LoopUntil = (negative integer for infinite or non-negative for limited)
    • Trigger - Run GIOL Loop <gen> (ignoring conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: call GIOL_ForEachCounted(udg_Lists_ListID, udg_Lists_Trigger, udg_Lists_LoopUntil)
For each element, the specified trigger will be executed. When the loop executes a trigger, the variables Lists_Data, Lists_Instance and Lists_ListID will be set to the relevant values, so they can be used to access other data.

Variable values at each execution of Lists_Trigger:

Lists_ID

The ID of the list being iterated over.

Lists_Instance

The current index of the iteration.

Lists_LoopUntil

The data stored in the index of the list.

This is the method to retrieve the size of of a List, using a Hashtable function.


Lists_ID

The ID of the list you want to know the size of

YourIntegerVariable

The variable that will hold the size of the list.

  • Set YourIntegerVariable = (Load 0 of Lists_ListID from Lists_Hashtable)

This is a guide on how to loop through a List without using the included function (see List Loop).

  • Actions
    • For each (Integer Lists_Instance) from 1 to (Load 0 of Lists_ListID from Lists_Hashtable), do (Actions)
      • Loop - Actions
        • Set Lists_Data = (Load Lists_Instance of Lists_ListID from Lists_Hashtable)
        • -------- ------------ --------
        • -------- DO STUFF HERE --------
        • -------- ------------ --------
        • -------- REMOVE DATA IF DESIRED --------
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
          • Then - Actions
            • Set Lists_Instance = (Lists_Instance - 1)
            • Custom script: call GIOL_Remove(udg_Lists_ListID, udg_Lists_Instance)
          • Else - Actions

This is the API provided for JASS users.

JASS:
//Please note that list indices are in the range of 1 to the maximum integer value

//==============================================
// System API
//==============================================

//==============
//Getters and Setters

//Gets data in specified index of a list
//Available since 2.0.0
function GIOL_Get takes integer listKey, integer index returns integer
endfunction

//Gets the size of a specified list
//Available since 2.0.0, replaced GetListSize
function GIOL_SizeOf takes integer listKey returns integer
endfunction

//Sets the value stored inside a specified index
//Available since 2.0.0
function GIOL_Set takes integer listKey, integer index, integer data returns nothing
endfunction

//Adds data to the end of a list and returns the index the data was added at (equal to size of the list)
//Available since 2.0.0, replaced GIUL_AddData
function GIOL_Append takes integer listKey, integer data returns integer
endfunction

//Removes data from a certain index of a List
//Available since 2.0.0, replaced RemoveData
function GIOL_Remove takes integer listKey, integer instance returns nothing
endfunction

//==============
//List creation and destruction

//Creates a list and returns its list key/list ID
function GIOL_CreateList takes nothing returns integer
endfunction

//Destroys the specified list
function GIOL_DestroyList takes integer listKey returns nothing
endfunction


//==============
//Looping functionality

//======
//Functions for simplified looping

//Returns the next index of a list. If the index is 0, the end of the list has been reached.
//If you are using this function to loop, you should NOT use GIOL_Remove!
//Available since 2.0.0
function GIOL_Next takes integer listKey returns integer
endfunction

//If you are iterating over a list using a GIUL_Next loop, you can use this function to remove the
//element in the index that you are currently at.
//Available since 2.0.0
endfunction

//Loop example using GIOL_Next:
loop
     set index = GIOL_Next(mylist)
     exitwhen index == 0
     //...do stuff...
endloop

//======
//Functions for code/trigger loops

//Loops over a list and executes the given trigger
//Stops after it enconters "until" number of elements
//If a negative "until" is specified, it will only stop when there are no more elements
//Sets the udg_Lists_Data, Instance and ListID variables to their correct values each time before running the trigger
function GIOL_ForEachCounted takes integer listKey, trigger trig, integer until returns nothing
endfunction

function GIOL_ForEach takes integer listKey, trigger trig returns nothing
endfunction

//Same as GIOL_Loop, but executes the given code in a ForPlayer loop, instead of a trigger
//Added in version 1.1.0
function GIOL_ForEachCodeCounted takes integer listKey, code func, integer until returns nothing
endfunction

function GIOL_ForEachCode takes integer listKey, code func returns nothing
endfunction

//==============
//System Initialization

//Initialzies GIOL if it has not been initialized
function GIOL_Initialize takes nothing returns nothing
endfunction


Updates and Version History:

v1:

1.0.0 > Initial Release
1.1.0 > Added GIOL_CodeLoop function for JASS users

v2:

2.0.0 >
Renamed many functions (to names that were shorter or made more sense).
Added new functions that make loops easier to handle (GIOL_Next and GIOL_RemoveCurrent)​


Upcoming:



Unordered Iterateable Lists v2.0.0

This system facilitates the creation of unordered lists that are iterateable. They are iterateable because you can access all of its elements in order, but it is unordered because the order is not constant, due to the algorithm used. You can think of them as "groups" of integers, where each integer can be used to access whatever data you need.

Adding data to the end of a GIUL List is an O(1) operation, which means it will always happen at the same speed, regardless of the size of the List. Removing data from a GIUL List is also an O(1) operaton.

Technical details:
GIUL lists use the common technique known as dynamic indexing. I had a hard time finding a good introduction to this concept because I wasn't sure what people actually called it, but I found two good sources here and here (indexed array).

Unordered Iterateable Lists:

Each list has a unique ID that is an integer generated by GMUI. You will need this ID to manipulate the lists and destroy them when you don't need them anymore.

As for the "GIUL_Hashtable" hashtable, you can use the unique ID of any GIUL list as a child hashtable. The size of a list is stored in the address 0, while the data is stored in the positive addresses. Therefore, you can use negative addresses for your own purposes.
Hashtable addresses:
0: Size of List
Positive Integers: List Data

How to Import:

  1. Open World Editor. File -> Preferences -> Tick box for "Automatically create unknown variables (...)"
  2. Copy the "GUI MUI Engine" category into your map.
  3. Open the "GMUI Header" trigger and copy its contents into your map header.
  4. Copy the "GUI Iterable Unordered Lists" category into your map.
  5. Open the "GIUL Header" trigger and copy its contents into your map header.
  6. Done!

Using the System:


Add Data

Remove Data

Create List

Destroy List

List Loop

Get Size

Advanced Loop

JASS API


This function adds Data to the last position of an existing list. Please note that conditions should be checked when executing the trigger.

Variables before execution:


Lists_ListID

The ID of the list we want to add data to.

Lists_Instance

We set this to zero because we want to add data, not remove it.

Lists_Data

The Data we want to add to the list.

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListID
    • Set Lists_Instance = 0
    • Set Lists_Data = YourData
    • Trigger - Run GIUL Main <gen> (checking conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: set udg_Lists_Instance = GIUL_Append(udg_Lists_ListID, udg_Lists_Data)

Variables after execution:


Lists_ListID

Same as before.

Lists_Instance

Index of the added data (equal to size of list)

Lists_Data

Same as before.

This function removes data from a certain address of a list. Please not you should check conditions when executing the trigger.

Variables before execution:


Lists_ListID

The ID of the list we want to remove data from.

Lists_Instance

The index of the data we want to remove from the list.

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListID
    • Set Lists_Instance = YourAddress
    • Trigger - Run GIUL Main <gen> (checking conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: set udg_Lists_Instance = GIUL_Remove(udg_Lists_ListID, udg_Lists_Instance)

Variables after execution:


Lists_ListID

Same as before.

Lists_Instance

Same as before.

This function allows you to create a new list, which you can add data to. Please note that you need to ignore conditions when executing the "GIUL Main" trigger.

Variables before execution:

Lists_ListID

We set this to zero because we want to create a new list.

GUI-only method:
  • Actions
    • Set Lists_ListID = 0
    • Trigger - Run GIUL Main <gen> (ignoring conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: set udg_Lists_ListID = GIUL_CreateList()

Variables after execution:


Lists_ListID

The ID of our newly created list.

This function allows you to destroy a list that you have created. Please note that you need to ignore conditions when executing the "GIUL Main" trigger.

Variables before execution:

Lists_ListID

The ID of the list we want to destroy.

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListID
    • Trigger - Run GIUL Main <gen> (ignoring conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: call GIUL_DestroyList(udg_Lists_ListID)
Variables after execution:

Lists_ListID

Same as before.

This function allows you to iterate over a list like a normal loop, allowing you to manipulate each element in the list. It also allows you to specify how many elements you want to iterate through, and the loop will stop after it reaches that number.

Variable parameters:

Lists_ID

The ID of the list you want to iterate over.

Lists_Trigger

The trigger that should be executed for each element.

Lists_LoopUntil

How many elements should the loop iterate over before it stops

GUI-only method:
  • Actions
    • Set Lists_ListID = YourListId
    • Set Lists_Trigger = YourTrigger
    • Set Lists_LoopUntil = (negative integer for infinite or non-negative for limited)
    • Trigger - Run GIUL Loop <gen> (ignoring conditions)
Custom Script method (more efficient):
  • Actions
    • Custom script: call GIUL_ForEachCounted(udg_Lists_ListID, udg_Lists_Trigger, udg_Lists_LoopUntil)
For each element, the specified trigger will be executed. When the loop executes a trigger, the variables Lists_Data, Lists_Instance and Lists_ListID will be set to the relevant values, so they can be used to access other data.

Variable values at each execution of Lists_Trigger:

Lists_ID

The ID of the list being iterated over.

Lists_Instance

The current index of the iteration.

Lists_LoopUntil

The data stored in the index of the list.

This is the method to retrieve the size of of a List, using a Hashtable function.


Lists_ID

The ID of the list you want to know the size of

YourIntegerVariable

The variable that will hold the size of the list.

  • Set YourIntegerVariable = (Load 0 of Lists_ListID from Lists_Hashtable)

This is a guide on how to loop through a List without using the included function (see List Loop).

  • Actions
    • For each (Integer Lists_Instance) from 1 to (Load 0 of Lists_ListID from Lists_Hashtable), do (Actions)
      • Loop - Actions
        • Set Lists_Data = (Load Lists_Instance of Lists_ListID from Lists_Hashtable)
        • -------- ------------ --------
        • -------- DO STUFF HERE --------
        • -------- ------------ --------
        • -------- REMOVE DATA IF DESIRED --------
        • If (All Conditions are True) then do (Then Actions) else do (Else Actions)
          • If - Conditions
          • Then - Actions
            • Set Lists_Instance = (Lists_Instance - 1)
            • Custom script: call GIUL_Remove(udg_Lists_ListID, udg_Lists_Instance)
          • Else - Actions

This is the API provided for JASS users.

JASS:
//Please note that list indices are in the range of 1 to the maximum integer value

//==============================================
// System API
//==============================================

//==============
//Getters and Setters

//Gets data in specified index of a list
//Available since 2.0.0
function GIUL_Get takes integer listKey, integer index returns integer
endfunction

//Gets the size of a specified list
//Available since 2.0.0, replaced GetListSize
function GIUL_SizeOf takes integer listKey returns integer
endfunction

//Sets the value stored inside a specified index
//Available since 2.0.0
function GIUL_Set takes integer listKey, integer index, integer data returns nothing
endfunction

//==============
//Getters and Setters

//Adds data to the end of a list and returns the index the data was added at (equal to size of the list)
//Available since 2.0.0, replaced GIUL_AddData
function GIUL_Append takes integer listKey, integer data returns integer
endfunction

//Removes data from a certain index of a List
//Available since 2.0.0, replaced RemoveData
function GIUL_Remove takes integer listKey, integer index returns nothing
endfunction

//==============
//List creation and destruction

//Creates a new list and returns its ID
function GIUL_CreateList takes nothing returns integer
endfunction

//Destroys the specified list
function GIUL_DestroyList takes integer listKey returns nothing
endfunction


//==============
//Looping functionality

//======
//Functions for simplified looping

//Returns the next index of a list. If the index is 0, the end of the list has been reached.
//If you are using this function to loop, you should NOT use GIUL_Remove!
//Available since 2.0.0
function GIUL_Next takes integer listKey returns integer
endfunction

//If you are iterating over a list using a GIUL_Next loop, you can use this function to remove the
//element in the index that you are currently at.
//Available since 2.0.0
function GIUL_RemoveCurrent takes integer listKey returns nothing
endfunction

//Loop example using GIUL_Next:
loop
    set index = GIUL_Next(mylist)
    exitwhen index == 0
    //...do stuff...
endloop

//======
//Functions for code/trigger loops

//Loops over a list and executes the given trigger
//Stops after it enconters "until" number of elements
//If a negative "until" is specified, it will only stop when there are no more elements
//Sets the udg_Lists_Data, Instance and listKey variables to their correct values each time before running the trigger
function GIUL_ForEachCounted takes integer listKey, trigger trig, integer until returns nothing
endfunction

function GIUL_ForEach takes integer listKey, trigger trig returns nothing
endfunction

//Same as GIUL_Loop, but executes the given code in a ForPlayer loop, instead of a trigger
//Added in version 1.1.0
function GIUL_ForEachCodeCounted takes integer listKey, code func, integer until returns nothing
endfunction

function GIUL_ForEachCode takes integer listKey, code func returns nothing
endfunction

//==============
//System Initialization

//Initializes GIUL if it has not yet been initialized.
function GIUL_Initialize takes nothing returns nothing
endfunction


Updates and Version History:

v1:

1.0.0 > Initial Release
1.1.0 > Added GIOL_CodeLoop function for JASS users

v2:

2.0.0 >
Renamed many functions (to names that were shorter or made more sense).
Added new functions that make loops easier to handle (GIOL_Next and GIOL_RemoveCurrent)​

Upcoming:



You can find the documentation here: Temp - Sets | HIVE


System Comparison:

Ordered Lists

Unordered Lists

Linked Lists


Pros:
+ Order is maintained
+ Directly know position of element in list
+ Size is saved

Cons:
- O(N) to remove data
- O(N) to check if element is in list

Pros:
+ O(1) to add and remove data
+ Size is saved

Cons:
- Order is not maintained
- O(N) to check if element is in list

Pros:
+ Order maintained
+ O(1) to add and remove data
+ O(1) to check if element exists in list

Cons:
- Size is not saved, you need to iterate through list or keep track of it yourself
- Can't directly know the position of an element in the list
- Can't add the same element twice to the list


Test Map:


Command

Action

kill

Kills and removes from the game your selected units.

add

Adds your selected units to a list

kill all

Kills all the units on the list created by the "add" command.

The Test Map is pretty simple, since I didn't have much time to think of and code different applications for the system. However, it allows you to see the system in action.

It has 3 unit Indexers (created with GMUI), 1 for each unit type (footman, rifleman and knight). Each unit of the same type has a unique index which is saved as its custom value, and the units are also saved in 3 different arrays, one for each unit type.

The tester can add units to different lists. The footmen are added to a GIOL list, the riflemen to a GIUL list and the Knights to a GLL list.

Releases:

Release 1:
Initial release, version 1.0.0 of all systems
Release 2:
Second release, version 1.1.0 of all systems​

Release 3:
All import triggers have been fixed and should now import all the required variables.​

Release 4:
GIUL and GIOL 2.0.0 and GLL 1.2.0 released.
Made code much more readable, without performance impacts, by taking advantage of function inlining in JassHelper. The Map Header triggers provided are optimized, so the user does not need to have JassHelper to take advantage of this.​
Contents

Guhun's Data Structures: Lists (Map)

Reviews
Dr Super Good
Comments and Suggestions: Although not really useful to anyone familiar with programming, it is potentially useful to those who are not. Specifically it is a good resource for learning about various generic data structures, how to implement them and...
Level 12
Joined
Jun 12, 2010
Messages
413
When I was mainly a GUI user I do not think I would have used this.


Way too clunky. Four lines to just add something onto a linked list? (with normal gui)

I also believe its fairly clunky to use this using normal GUI methods, which is why I left the code in the map header instead of the trigger itself, since I mostly recommend using the custom script methods. Either way, I think JASS users would get more use out of the system, I just like making stuff avaiable for GUI too.

Honestly I do not think I could have made it any better myself, I do not judge you for that. But I fear it might be wasted effort.

I'm not too certain people will start using this instead of always using their own data structures (just like people don't use the GUI Spell System in submissions for some reason o_O). Though it certainly won't be a wasted effort, as I actually needed something like this to make a buff system for my map and also create "destructable groups", since I needed to have multiple independent lists. I just thought it would be nice to make it modular and release it for people to use if they wanted to.

I just spent more time writing the documentation than I thought would be needed :wgrin:

UPDATE: (12/January/2018)

New updates to allow JASS users to execute code instead of triggers if they so desire, and a new function (GLL_ClearList) to efficiently clear a linked list, moving backwards or fowards between a start and end value.

Release 2 includes version 1.1.0 for all systems.

UPDATE: (13/January/2018)

Release 3:
All import triggers have been fixed and should now import all the required variables.
UPDATE: (10/May/2018)

Release 4:
GIUL and GIOL 2.0.0 and GLL 1.2.0 released.
Made code much more readable, without performance impacts, by taking advantage of function inlining in JassHelper. The Map Header triggers provided are optimized, so the user does not need to have JassHelper to take advantage of this.​

 
Last edited:

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,178
Comments and Suggestions:
Although not really useful to anyone familiar with programming, it is potentially useful to those who are not. Specifically it is a good resource for learning about various generic data structures, how to implement them and what they do.

The demonstration map could more clearly emphasize the different properties of each list. Such as how sets cannot have the same element added twice to them while lists can.

The usefulness of this might diminish in the future when Lua makes it to live versions of Warcraft III. Lua's table primitive type does much of this functionality already either directly or by using standard functions.​
 
Top