The QueueQueue

Level 31
Joined
Jul 10, 2007
Messages
6,307
Given the complexity of what can be done and how to work with the QueueQueue structure, a tutorial is necessary.

A QueueQueue is like a multi dimensional queue. Rather than always having to add a node to the end of it, a node can be added anywhere, but nodes aren't added to the current queue but an inner queue.

If you were to have a set of nodes on a queue-
Code:
1
2
3
4
5

Each node could point to another set of nodes.

Code:
1
    6,7,8,9,10
2
    11,12,13,14,15
3
    16,17,18,19,20
4
    21,22,23,24,25
5
    26,27,28,29,30

So, the first queue (vertical) would be the nodes 1-5. Node 1 would contain 6-10, node 2 would contain 11-15, etc.
Code:
1,2,3,4,5

1: 6,7,8,9,10
2: 11,12,13,14,15
3: 16,17,18,19,20
4: 21,22,23,24,25
5: 26,27,28,29,30

Remember that any node can contain further nodes, so the data structure could get rather complex.

Code:
1,2,3,4,5

1: 6,7,8,9,10
2: 11,12,13,14,15
3: 16,17,18,19,20
4: 21,22,23,24,25
5: 26,27,28,29,30

6: 31,32,33
7: 34,35,36
8: 37,38,39,40
9: 41,42
10: 43,44,45,46

etc, etc

Example
Code:
1
    6
        31
            36
                40
                41
                42
                43
                44
                    45
                        46
            37
            38
            39
        32
        33
        34
        35
    7
        36
    8
    9
    10
2
    11
        47
            50
                51
            52
                53
                54
            55
        48
            49
    12
    13
    14
    15
3
    16,17,18,19,20
4
    21,22,23,24,25
5
    26,27,28,29,30

In reality, the first 5 nodes would be contained in a special node called a head.

Code:
6 (head)
    1
    2
    3
    4
    5

This data structure is interpreted as a list of inner nodes of an outer node being the properties of that outer node. For example

Code:
hero
    inventory
        item1
        item2
        item3
        item4
        item5
        item6
    location
        x
        y
    facing
    states
        life
        mana
    level

The properties of the hero would be inventory, location, facing, states, and level. The hero node itself has no value, it just points to other things.
Code:
hero
    inventory
    location
    facing
    states

The other properties listed are not properties of the hero, but rather properties of whatever their parent node is. For example, the properties of an inventory are the 6 items it can have.
Code:
inventory
    item1
    item2
    item3
    item4
    item5
    item6

And from here, items can have many properties of their own like charges and gold cost.

If a hero has an inventory and that inventory can have 6 items, then that hero can have 6 items.

When looping through this structure (getting all of the values in the right order), you first read the object, then its inner properties.

So for example, the hero would be read like this-
Code:
hero
inventory
item1
item2
item3
item4
item5
item6
location
x
y
facing
states
life
mana
level

Not like this
Code:
hero
inventory
location
facing
states

And keep in mind that the actual nodes directly inside of the hero are
Code:
inventory
location
facing
states

So, this means that when moving on from a node, you go right before you go down.

read hero, go right (inventory), go right (item1), go down.
Code:
hero->inventory->item1
                 item2
                 item3
                 item4
                 item5
                 item6

At item6, you can't go down anymore, so you have to go left. None of them items point back to the inventory and the inventory only points to item1, so you have to actually store row positions into an array of columns.

In the above example-
Code:
hero        inventory        item1
                             item2
                             item3
                             item4
                             item5
                             item6

So, for column 1, hero would be stored. For column 2, inventory would be stored. Column 3 would have item 6 stored at the end, but you wouldn't go beyond column 3.

To go left, if using an array, you just subtract one from the current column.

JASS:
//go right
set column[currentColumn] = node        //store the node
set currentColumn = currentColumn + 1 //go right

So going right from the hero would store the hero node and then go right.

Because a node in a QueueQueue can have anything inside of it, it can also point to other nodes. Keep in mind that other nodes point down and right, and only the node plus whatever is right of it would be wanted, so for simplicity, only heads should be pointed to.

So for example, adding hero to player.
Code:
player
    heroPointer
        hero

The reason for the seemingly useless pointer (heroPointer) is because any node has a list inside of it. If hero were to be stored into player directly, then something else pointing to hero would also point to everything underneath that hero (in this case, other properties of the player).

For example-
Code:
player
    hero
    resource
        gold
        lumber

Code:
commander
    hero

In the player list, hero points both right and down. Underneath hero is the resource property. This means that when commander points to hero, it'll end up looping through the hero and all of its properties and then* everything underneath hero. Furthermore, if commander were to have properties under hero, it'd end up breaking because hero can't point downwards to 2 different things.

Code:
player
    hero
    resource
        gold
        lumber

Code:
commander
    hero
    power

This attempts to make hero point down to both resource and power. Given commander is linked afterwards, it'll break the player and make the structures look more like this.

Code:
player
    hero
    power

Code:
commander
    hero
    power

A pointer can't point to multiple things*.


In the end, looping through a QueueQueue will turn out like this.
JASS:
//remember that the rows, column, and node need to be stored
local thistype array r    //first row on column
local thistype c = 0      //column
local thistype n = this   //node
loop
    //remember to first go right, then down*
    //when down, go left
    if (n.in == 0) then
        //if there is nothing to the right, then go down
        loop
            //go left until can go down or all the way left
            exitwhen n.next != 0 or c == 0
            set c = c - 1
            set n = r[c]
        endloop
        set n = n.next
        set r[c] = n
    else
        //go right
        set c = c + 1   //go to next column
        set n = n.in
        set r[c] = n    //update next column
    endif

    //exit when the current node is null
    exitwhen n == 0

    //remember that pointers don't have values! skip them.
    if (not n.pointer) then
        //code
    endif
endloop

QueueQueue contains macros and modules to help make looping through the structure easier.


A QueueQueue is primarily useful for creating dynamic objects or frames for objects. In a save/load code for example, every little piece that can be put into that code refers to an object. Most save/load codes don't do this, rather just taking a set of maximal values. However, taking a set of maximal values is a bad practice because the overall data sets can change.

Recall that items have different maximums. If a save/load code were to have 6 positions for items and were to save the charges of those items, how on earth would it know the maximum charge for each item without just making a generic charge for all items?

With dynamic objects come dynamic codes, where the maximums for every given item are known.

Given 6 items and a biggest item charge of 300
Code:
Item type 1: 60 charges max
Item type 2: 0 charges max
Item type 4: 30 charges max
Item type 5: 45 charges max
Item type 6: 0 charges max

A static save/load code would make enough space to store 300 charges, which bloats the code up in almost all cases (notice item 2 and 6 have maxes of 0 charges).

A dynamic save/load code, which is possible with this structure, would know the maximum charges of each item and be able to read them out.

Recall that save/load codes have a static list. Your common save/load code stores the hero and resources, which turns into the 6 items, gold, lumber, etc mess. With a QueueQueue, it'd turn into literally Hero and Resources (all of the properties, some of them being dynamic, would be within the Hero and Resources).

If every single possible property was stored for a set of data, then the save/load code can pick and choose what it wants. Later, the data can be interpreted based on the objects.

For example, if there were 10 different items all with varying charges, you'd only pick the 6 items and their properties for the save/load code.

Code:
1   
2   (pick)
3   
4   (pick)
5   (pick)
6   
7   (pick)
8   
9   (pick)
10  (pick)

So notice that the QueueQueue object has 10 objects in it with different properties. A new object is generated from the base objects based on the values passed in. In this case, a 2, 4, 5, 7, 9, and 10 were passed in, so only those objects were taken out of the first and put into the second.

Code:
2
4
5
7
9
10

When reading out of the code, the 2,4,5,7,9, and 10 would be read out. Remember that QueueQueue goes right before it goes left, so it'd read the 2, then it'd read all properties inside* of that 2. This leads to dynamic save/load codes that store a static set of objects rather than a static set of data, and keep in mind that most data in a save/load code is inside of a hero, so almost all of the data for these types of save/load codes can be entirely dynamic (one hero might have pets, another might have an inventory of 4 items, and etc).
 
Last edited:
Top