Introduction to Collections: Index Array, Linked List, Stack, Queue, Dequeue

[Nestharus]

This will talk about what an indexed array, stack, queue, and dequeue are as well as introduce how they work and how to use them.

Requires knowledge of struct syntax.

Indexed Array

An indexed array is an array that uses a counter and prevents holes in data.

	integer array a
	integer acount = 0

	set acount = acount + 1
	set a[acount] = 1
	set acount = acount + 1
	set a[acount] = 2
	set acount = acount + 1
	set a[acount] = 3
	set acount = acount + 1
	set a[acount] = 4
	set acount = acount + 1
	set a[acount] = 5
	set acount = acount + 1
	set a[acount] = 6
	set acount = acount + 1
	set a[acount] = 7

	set a[3] = 0 //hole

To prevent the hole from occurring, an indexed array will overwrite the value of the removed index with the value from the last index and decrease the counter. Essentially, it will remove the last index and shove whatever value is in that last index into the target index.

	integer array a
	integer acount = 0

	set acount = acount + 1
	set a[acount] = 1
	set acount = acount + 1
	set a[acount] = 2
	set acount = acount + 1
	set a[acount] = 3
	set acount = acount + 1
	set a[acount] = 4
	set acount = acount + 1
	set a[acount] = 5
	set acount = acount + 1
	set a[acount] = 6
	set acount = acount + 1
	set a[acount] = 7

	set a[3] = a[acount] //shove 7 into a[3]
	set acount = acount - 1 //remove 7

However, because of this, the order is not maintained.

Before-

	a[1]=1
	a[2]=2
	a[3]=3
	a[4]=4
	a[5]=5
	a[6]=6
	a[7]=7 //end

After-

	a[1]=1
	a[2]=2
	a[3]=7
	a[4]=4
	a[5]=5
	a[6]=6 //end

Indexed arrays are useful as to allocate new memory a counter can be increased. However, if data order is a necessity, they shouldn't be used. Furthermore, looping through an indexed array in JASS is slower than looping through what is called a linked list as JASS math is so slow. Indexed arrays also take up minimal memory.

Indexed arrays are also only useful for single types (pretty much like an advanced array).

	struct IndexedArray extends array
		readonly static thistype size = 0
		integer value
		
		static method create takes nothing returns thistype
			set size = size + 1
			return size
		endmethod
		method destroy takes nothing returns nothing
			set value = size.value
			set size = size - 1
		endmethod
	endstruct

The Linked List

A linked list is a list containing a set of pointers that point to each other.

In an indexed array, the previous and next slots are always known.

	a[1] //previous
	a[2]
	a[3] //next

Simply incrementing the index by 1 will get the next. Decrementing the index by 1 will get the previous. Linked lists don't require that values be right next to each other, so they have to actually point to their next and possibly previous.

	//0 is treated as the head in this case
	//a head is the node that is used to store the list
	//a head can retrieve the first value on the list as well as possibly the last
	previous[0]=2021
	next[0]=1

	previous[1]=0
	next[1]=3 //next points to 3

	previous[3]=1 //previous points to 1
	next[3]=2021 //next points to 2021

	previous[2021]=3 //previous points to 3
	next[2021]=0 //next points to 0

When looping through it, rather than incrementing/decrementing by 1 like in a normal loop, the pointers are used.

	local integer current = next[0]
	loop
		exitwhen current == 0 //exitwhen back at the head
		//do some code
		set current = next[current] //go to the next value
		//above would be equivalent to
		//set current = current + 1
		//for looping through arrays
	endloop

In a doubly linked list, values can easily be removed while maintaining order.

	set next[previous[3]]=next[3]
	set previous[next[3]]=previous[3]

The above would make 1 point to 2021 and 2021 point to 1 (link them up), removing 3 from the list altogether (nothing points to it).

A list where each node on it points to its previous and its next is called a doubly linked list (two pointers). A singly linked list would look like this.

	next[1]=3
	next[3]=2021
	next[2021]=0

Singly linked lists can only be looped through forward. Furthermore, because the previous node of any given value is unknown, only the first node on the list can be removed.

For removal, this is required
set next[1]=2021 //removes 3

When looping, if the current node were to be 3, there'd be no way to know which node was before it to perform the link. How would one retrieve 1 when they were at 3?

	local integer current = 3
	local integer prev //??? don't know the value because there is no pointer
	local integer nex = next[current] //there is a pointer for this though

A static list is where the head is always equal to 0. A dynamic list is where the head can be anything. Dynamic lists may compare to the head to exit a loop or may compare to some boolean called end (comparing a boolean is faster than comparing a large number, so booleans are good for loops when using dynamic lists).

There are also circular lists

	set next[3]=5
	set next[5]=8
	set next[8]=11
	set next[11]=3 //points back to first

	//3->5->8->11->3->5->8->11->3, etc

Looping through the above would continue to loop forever.

Stack

A stack is a type of singly linked list. They are used to add and remove values from the beginning of the list. The common methods for them are push (add) and pop (remove).

FILO (first in last out)

Push

		next[0] = 5 //first node is 5
		next[3] = next[0] //next[3] is now 5
		next[0] = 3 //first node is now 3
		//3->5

		next[8]=next[0] //next[8] is now 3
		next[0]=8 //first node is now 8
		//8->3->5

		//etc, etc

Pop

		next[0]=next[next[0]] //first node is now first node's next
		//next[next[0]] is next[8], which is 3
		//this means that the first node is now 3
		//3->5

		next[0]=next[next[0]] //first node is now first node's next
		//next[next[0]] is next[3], which is 5
		//this means that the first node is now 5
		//5

		next[0]=next[next[0]] //first node is now first node's next
		//next[next[0]] is next[5], which is 0
		//this means that the first node is now 0, which is the head
		//the list is now empty
		//

Static Stack

			struct Stack extends array
				constant thistype head = 0
				readonly thistype next

				method push takes nothing returns nothing
					set next = head.next //make this node point to the first node on list
					set head = this //make head point to this
				endmethod

				static method pop takes nothing returns nothing
					set head.next = head.next.next
				endmethod
			endstruct

Structs normally use static stacks for recycling.

			struct MyStack extends array
				private static integer instanceCount = 0
				private static integer array recycle

				static method create takes nothing returns thistype
					local thistype this
					if (recycle[0] == 0) then //0 is head, so recycle[0] is the first node
						set instanceCount = instanceCount + 1
						return instanceCount
					endif
					set this = recycle[0]
					set recycle[0] = recycle[this] //remove first node by setting head to its next
					return this
				endmethod

				method destroy takes nothing returns nothing
					set recycle[this] = recycle[0] //make next point to first node on stack
					set recycle[0] = this //update first node
				endmethod
			endstruct

Dynamic Stack

There are two types of dynamic stacks. The first type is where the head is just another node (first node on list, treated as a pointer to the list).

The next type is where the head is entirely its own thing.

The first type of dynamic list is more limited by total instances as instances are cut down by the head pointer (4000 lists with 1 node each would be 8000 nodes because the head is also a node). The second type is less limited (4000 lists with 1 node each would be 4000 nodes because the head is its own thing).

First Type

			struct Stack extends array
				private static integer instanceCount = 0
				readonly thistype next //use 0 as head for recycle stack

				static method create takes nothing returns thistype
					local thistype this
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set this = instanceCount
					else
						set this = thistype(0).next
						set thistype(0).next = next
						set next = 0
					endif
					return this
				endmethod

				method push takes nothing returns thistype
					local thistype node
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set node = instanceCount
					else
						set node = thistype(0).next
						set thistype(0).next = node.next
					endif

					set node.next = next
					set next = node

					return node
				endmethod

				method pop takes nothing returns thistype
					local thistype node = next
					set next = node.next

					//recycle the node
					set node.next = thistype(0).next
					set thistype(0).next = node

					return node
				endmethod

				method destroy takes nothing returns nothing
					local thistype last = this
					loop
						exitwhen last.next == 0
						set last = last.next
					endloop
					set last.next = thistype(0).next
					set thistype(0).next = this
				endmethod
			endstruct

Second Type

				struct Stack extends array
					private static integer instanceCount = 0
					private static integer nodeCount = 0
					readonly thistype next //use 0 as head for recycle stack
					private static integer array recycle
					readonly thistype first

					static method create takes nothing returns thistype
						local thistype this
						if (recycle[0] == 0) then
							set instanceCount = instanceCount + 1
							set this = instanceCount
						else
							set this = recycle[0]
							set recycle[0] = recycle[this]
							set first = 0
						endif
						return this
					endmethod

					method push takes nothing returns thistype
						local thistype node
						if (thistype(0).next == 0) then
							set nodeCount = nodeCount + 1
							set node = nodeCount
						else
							set node = thistype(0).next
							set thistype(0).next = node.next
						endif

						set node.next = first
						set first = node

						return node
					endmethod

					method pop takes nothing returns thistype
						local thistype node = first
						set first = node.next

						//recycle the node
						set node.next = thistype(0).next
						set thistype(0).next = node

						return node
					endmethod

					method destroy takes nothing returns nothing
						local thistype last = first
						loop
							exitwhen last.next == 0
							set last = last.next
						endloop

						//recycle set of nodes
						set last.next = thistype(0).next
						set thistype(0).next = first

						//recycle head
						set recycle[this] = recycle[0]
						set recycle[0] = this
					endmethod
				endstruct

Queue

A queue is a singly linked list that has a pointer to its first and last nodes. They are used to add values to the end of the list and remove values from the front.

FIFO (first in first out)

The pointer to the first node is just head.first or head.next, and the pointer to the last node is head.last.

Static Queue

			struct Queue extends array
				constant thistype head = 0
				readonly thistype next
				readonly static thistype last = 0

				method push takes nothing returns nothing
					set last.next = this
					set last = this
					set next = 0
				endmethod

				static method pop takes nothing returns nothing
					set head.next = head.next.next
					if (head.next = 0) then
						set last = head
					endif
				endmethod
			endstruct

Dynamic Queue

First Type

			struct Queue extends array
				private static integer instanceCount = 0
				readonly thistype next //use 0 as head for recycle stack
				readonly thistype last

				static method create takes nothing returns thistype
					local thistype this
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set this = instanceCount
					else
						set this = thistype(0).next
						set thistype(0).next = next
						set next = 0
						set last = this
					endif
					return this
				endmethod

				method push takes nothing returns thistype
					local thistype node
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set node = instanceCount
					else
						set node = thistype(0).next
						set thistype(0).next = node.next
					endif

					set last.next = node
					set last = node
					set node.next = 0

					return node
				endmethod

				method pop takes nothing returns thistype
					local thistype node = next
					set next = node.next

					if (next == 0) then
						set last = this
					endif

					//recycle the node
					set node.next = thistype(0).next
					set thistype(0).next = node

					return node
				endmethod

				method destroy takes nothing returns nothing
					set last.next = thistype(0).next
					set thistype(0).next = this
				endmethod
			endstruct

Second Type

			struct Queue extends array
				private static integer instanceCount = 0
				private static integer nodeCount = 0
				readonly thistype next //use 0 as head for recycle stack
				private static integer array recycle
				readonly thistype first
				readonly thistype last

				static method create takes nothing returns thistype
					local thistype this
					if (recycle[0] == 0) then
						set instanceCount = instanceCount + 1
						set this = instanceCount
					else
						set this = recycle[0]
						set recycle[0] = recycle[this]
						set first = 0
						set last = 0
					endif
					return this
				endmethod

				method push takes nothing returns thistype
					local thistype node
					if (thistype(0).next == 0) then
						set nodeCount = nodeCount + 1
						set node = nodeCount
					else
						set node = thistype(0).next
						set thistype(0).next = node.next
					endif
					if (last == 0) then
						set first = node
					else
						set last.next = first
					endif
					set last = node
					set next = 0

					return node
				endmethod

				method pop takes nothing returns thistype
					local thistype node = first
					set first = node.next
					if (first == 0) then
						set last = 0
					endif

					//recycle the node
					set node.next = thistype(0).next
					set thistype(0).next = node

					return node
				endmethod

				method destroy takes nothing returns nothing
					//recycle set of nodes
					if (last != 0) then
						set last.next = thistype(0).next
						set thistype(0).next = first
					endif

					//recycle head
					set recycle[this] = recycle[0]
					set recycle[0] = this
				endmethod
			endstruct

Dequeue

A dequeue is known as a double ended queue. It is a doubly linked list where each node on the list points to its previous and next nodes. They can do FIFO (first in first out) and LILO (last in last out). Furthermore, any node on it can be removed.

Static Dequeue

			struct Dequeue extends array
				constant thistype head = 0
				readonly thistype next
				readonly thistype previous

				//anywhere on the list
				method add takes thistype node returns nothing
					set node.previous = this
					set node.next = next
					set next.previous = node
					set next = node
				endmethod

				method remove takes nothing returns nothing
					set previous.next = next
					set next.previous = previous
				endmethod
			endstruct

Dynamic Dequeues

First Type

Dynamic dequeues of the first type may either terminate with the head or with a boolean value. I prefer a boolean value as it makes the loops a bit faster.

Dequeues of the first type are always circular-

				head = 5
				5.next = 6
				6.next = 7
				7.next = head

The loops look something like this

				local thistype cur = head.next
				loop
				    exitwhen cur == head
				    //code
				    set cur = cur.next
				endloop

				local thistype cur = head.next
				loop
				    exitwhen cur.end
				    //code
				    set cur = cur.next
				endloop

			struct Dequeue extends array
				private static integer instanceCount = 0
				readonly thistype next //use 0 as head for recycle stack
				readonly thistype previous
				readonly boolean end

				static method create takes nothing returns thistype
					local thistype this
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set this = instanceCount
					else
						set this = thistype(0).next
						set thistype(0).next = next
						set next = this
						set previous = this
					endif
					set end = true
					return this
				endmethod

				method add takes nothing returns thistype
					local thistype node
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set node = instanceCount
					else
						set node = thistype(0).next
						set thistype(0).next = node.next
					endif

					set node.next = next
					set node.previous = this
					set next.previous = node
					set next = node

					return node
				endmethod

				method remove takes nothing returns nothing
					set previous.next = next
					set next.previous = previous

					//recycle the node
					set next = thistype(0).next
					set thistype(0).next = this
				endmethod

				//where destroy is head
				method destroy takes nothing returns nothing
					set previous.next = thistype(0).next
					set thistype(0).next = this
					set end = false
				endmethod
			endstruct

Second Type

			struct Dequeue extends array
				private static integer instanceCount = 0
				private static integer array recycle
				readonly thistype next //use 0 as head for recycle stack
				readonly thistype previous
				readonly thistype first
				readonly thistype last

				static method create takes nothing returns thistype
					local thistype this
					if (thistype(0).next == 0) then
						set instanceCount = instanceCount + 1
						set this = instanceCount
					else
						set this = recycle[0]
						set recycle[0] = recycle[node]
						set first = 0
						set last = 0
					endif
					return this
				endmethod

				//-where add before
				//where add after
				//0 add to end
				method add takes thistype where returns thistype
					local thistype node
					if (thistype(0).next == 0) then
						set nodeCount = nodeCount + 1
						set node = nodeCount
					else
						set node = thistype(0).next
						set thistype(0).next = node.next
					endif

					if (first == 0) then
						set first = node
						set last = node
						set node.next = 0
						set node.previous = 0
					else
						if (where == 0) then
							set where = last
						endif
					
						if (where > 0) then
							if (where == last) then
								set node.next = 0
								set last = node
							else
								set node.next = where.next
								set where.next.previous = node
							endif
							set where.next = node
							set node.previous = where
						else
							set where = -where
							if (where == first) then
								set node.previous = 0
								set first = node
							else
								set node.previous = where.previous
								set where.previous.next = node
							endif
							set where.previous = node
							set node.next = where
						endif
					endif

					return node
				endmethod

				method remove takes thistype node returns nothing
					if (previous == 0) then
						set first = next
					else
						set previous.next = next
					endif
					if (next == 0) then
						set last = previous
					else
						next.previous = previous
					endif

					//recycle the node
					set next = thistype(0).next
					set thistype(0).next = this
				endmethod

				//takes list
				method destroy takes nothing returns nothing
					//recycle set of nodes
					if (last != 0) then
						set last.next = thistype(0).next
						set thistype(0).next = first
					endif

					//recycle head
					set recycle[this] = recycle[0]
					set recycle[0] = this
					set first = 0
					set last = 0
				endmethod
			endstruct

 

[PurgeandFire]

Nice job, I looked over it and can't see anything wrong with it. ~Approved.

 

[Bribe]

A linked list is a type of stack, not the other way around as you have it.

Otherwise seems like a myriad of different implementations, a flavor for everyone, so to speak. Only "constant thistype head = 0" won't compile, it needs to be "static constant thistype head = 0".

 

[Nestharus]

A linked list is a type of stack, not the other way around as you have it.

Actually, there are two implementations of a stack. One implementation is using a linked list and another is using an array. Really, they don't have much to do with each other than the idea that one way a stack is implemented is via a linked list. I simply state that a stack is a type of linked list as in vJASS, virtually every stack is implemented via a linked list.

Otherwise seems like a myriad of different implementations, a flavor for everyone, so to speak. Only "constant thistype head = 0" won't compile, it needs to be "static constant thistype head = 0".

Eh, as long as one gets the concept. I wrote out all of the code in the post ;P.



I told you to look at this because of your naming convention in your DequeueStruct. That would be a static dequeue and your module would be a static dequeue as well. There are also more operations than just adding and removing, as outlined in the ranged operations tutorial.

edit
On a final note, you can't have constant struct types.

neither static constant thistype HI = 5 or constant Hello HI = 5 would work =). This is because vjass assumes that all objects are created via the create method, and Vexorian, being a wc3c kind of person, enforces that rule. It was hard enough to get him to open destroy ;P.

 

[Bribe]

Naming conventions are a bit rough I'm afraid. I've never been happy with the DequeueStruct name (mostly due to my distaste of the word queue) and would prefer calling it something else entirely. StaticDequeueStruct and StaticDequeueModule would make my skin crawl, there has to be a shorter name to describe the process.

 

[Nestharus]

Naming conventions are a bit rough I'm afraid. I've never been happy with the DequeueStruct name (mostly due to my distaste of the word queue) and would prefer calling it something else entirely. StaticDequeueStruct and StaticDequeueModule would make my skin crawl, there has to be a shorter name to describe the process.

Those are the names, lol...

 

[PurgeandFire]

gy by request