# The QueueQueue

#### Nestharus

Level 31
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:

#### PurgeandFire

Level 43
That's a pretty cool structure. A bit limited in its uses, but it is still really interesting.

Anyway, I just detached the signature, so ~Approved. It makes sense to me and is a good tutorial.

EDIT: gy'd by request

Last edited:

Replies
2
Views
1K
Replies
6
Views
6K
Replies
8
Views
2K
Replies
5
Views
568
Replies
7
Views
2K