[Snippet] Queue

[Nestharus]

library Queue
	//static method create takes nothing returns thistype
	//method destroy takes nothing returns nothing

	//method enqueue takes thistype node returns nothing
	//method dequeue takes nothing returns nothing
	
	//method clear takes nothing returns nothing

	module Queue
		private static integer c = 0		//instance count
		readonly thistype next
		readonly thistype last

		static method createQueue takes nothing returns thistype
			local thistype this = thistype(0).next
			if (0 == this) then
				set this = c + 1
				set c = this
			else
				set thistype(0).next = next
			endif

			set next = 0
			set last = this

			return this
		endmethod

		method enqueueNode takes thistype node returns nothing
			set last.next = node
			set node.next = 0
			set last = node
		endmethod

		method dequeueNode takes nothing returns nothing
			set next = next.next
			if (0 == next) then
				set last = this
			endif
		endmethod

		method clearQueue takes nothing returns nothing
			if (this != last) then
				set last.next = thistype(0).next
				set thistype(0).next = next
				set next = 0
				set last = this
			endif
		endmethod

		method destroyQueue takes nothing returns nothing
			set last.next = thistype(0).next
			set thistype(0).next = this
		endmethod
	endmodule
endlibrary

 

[Dirac]

So this is basically a stack with hideous API, dynamic capacities and clean deallocation.

Instead of queue name it push and instead of dequeue name it pop

 

[Nestharus]

How is this a stack?? It's a queue...


enqueue and dequeue are the standard add/remove method names for a queue.

 

[Magtheridon96]

A queue is similar to a singly linked list.

 

[Bribe]

Another data structure that people can use. Approved.

 

[Berb]

I'm confused at how this would be implemented, but I find it odd that nobody else was puzzled by it.

I'm confused at the fact that the dequeue method doesn't return anything. It should return the value that was first queued, no?

Or is that referenced as structname.last?

Okay so the dequeue method seems to... take the struct out of the queue? How exactly do you extract the first element in a queue?

Because the implementation is so weird, I'd suggest having more documentation. The API is named as a queue but it seems to work more like a linked-list.

 

[Magtheridon96]

Because the implementation is so weird, I'd suggest having more documentation. The API is named as a queue but it seems to work more like a linked-list

Because a Queue is a linked list

 

[Berb]

You don't have to use a linked list to make a queue. A queue is just an abstract data-type that suggests first on, first off (FIFO) "storage" if you will.

It can be implemented using arrays or linked lists, but the only advantage of using a linked list is the dynamic storage capabilities.

I actually have a hard time imagining what one would use this for where a linked-list doesn't suffice, or an array for that matter.

 

[Bribe]

I'm going to be using this for my next implementation of MissileRecycler, with timestamps and a single timer instead of TimerUtils. That way I always take from the bottom and add to the top (or vice-versa, just in case you are standing on your head).

 

[Berb]

But this has no method that "takes from the bottom". The dequeue method doesn't return anything (it looks like it just removes a given struct from the queue). If you've already got all of this information though, then a linked list would suffice already.

I'm curious, what happens when the same struct is added to two separate queues? I don't understand how this library would go about having that, since each struct member only has one next member.

It seems like this tries to be a queue without the capabilities of an actual queue, implemented using a linked list that doesn't even have full linked list capabilities. I really don't see the point in it, yet after almost no discussion at all it's been approved.

enqueue and dequeue are the standard add/remove method names for a queue.

Just because you name the methods as a queue doesn't make it a queue.

Another data structure that people can use. Approved.

A queue isn't a data-structure, it's an abstract data-type. The capabilities of this library don't match that of a linked-list (as far as I can see, you cannot have the same struct in multiple linked lists) nor does it match the capabilities of a queue (there is no way to pull values off of the queue).

How is this a stack?? It's a queue...

The only similarity this has to a queue is the names you have used.

Clearly we need some help discovering what a queue is, so here's a link:
http://en.wikipedia.org/wiki/Queue_(abstract_data_type)

This is more along the lines of what it should look like:

Queue

library Queue
private struct qnode
    public integer data  = 0 // this would be a struct index
    public thistype next = 0
endstruct
struct queue
    private qnode head = 0
    private qnode tail = 0
    
    method isEmpty takes nothing returns boolean
        return head == 0
    endmethod
    
    method enqueue takes integer data returns nothing
        if (isEmpty()) then
            set head = qnode.create()
            set head.data = data
            set tail = head
        else
            set tail.next = qnode.create()
            set tail = tail.next
            set tail.data = data
        endif
    endmethod
    
    method dequeue takes nothing returns integer
        local integer data
        local qnode extract
        if not (isEmpty()) then
            set extract = head
            set data = extract.data
            set head = head.next
            call extract.destroy( )
            return data
        endif
        return 0
    endmethod
endstruct
endlibrary

 

[Nestharus]

Actually, the one I wrote allows any node to either be a node or a queue ; ), so it's a bit more dynamic in that regard. The way you wrote it is extremely standard Berb, but I tried to write it in a way that would be the most useful (meaning any node can be whatever). I really wrote it to let users do whatever they wanted to do with the lightest code possible ; ).


Furthermore, this is a linked list. It happens to be a singly linked list. A queue only needs a singly linked list. If it was a doubly linked list, it might as well be a dequeue ; P.


The benefits of a queue over a dequeue or a linked list is that it's lighter (less overhead per operation and less memory usage), but I'm sure that you already knew that.

 

[Mr.Foxy]

library Queue
	//static method create takes nothing returns thistype
	//method destroy takes nothing returns nothing

	//method enqueue takes thistype node returns nothing
	//method dequeue takes nothing returns nothing
	
	//method clear takes nothing returns nothing

	module Queue
		private static integer c = 0		//instance count
		readonly thistype next
		readonly thistype last

		static method createQueue takes nothing returns thistype
			local thistype this = thistype(0).next
			if (0 == this) then
				set this = c + 1
				set c = this
			else
				set thistype(0).next = next
			endif

			set next = 0
			set last = this

			return this
		endmethod

		method enqueueNode takes thistype node returns nothing
			set last.next = node
			set node.next = 0
			set last = node
		endmethod

		method dequeueNode takes nothing returns nothing
			set next = next.next
			if (0 == next) then
				set last = this
			endif
		endmethod

		method clearQueue takes nothing returns nothing
			if (this != last) then
				set last.next = thistype(0).next
				set thistype(0).next = next
				set next = 0
				set last = this
			endif
		endmethod

		method destroyQueue takes nothing returns nothing
			set last.next = thistype(0).next
			set thistype(0).next = this
		endmethod
	endmodule
endlibrary

What those meaning?
For what?

 

[Magtheridon96]

^That's the actual system's code
It's written in vJass and it requires you to use JassNewGenPack.
The code is for a data-structure (Problem Berb?), known as a Queue (pronouned Q or Kyew).
This data-structure (u mad bro?) allows you to insert nodes (integers) at the end and retrieve nodes (integers) from the top.

It works just like a line in a cafeteria.
When you come, you stand at the end and the first person in the line is going to go leave next.

 

[Berb]

Actually, the one I wrote allows any node to either be a node or a queue ; ), so it's a bit more dynamic in that regard. The way you wrote it is extremely standard Berb, but I tried to write it in a way that would be the most useful (meaning any node can be whatever). I really wrote it to let users do whatever they wanted to do with the lightest code possible ; ).


Furthermore, this is a linked list. It happens to be a singly linked list. A queue only needs a singly linked list. If it was a doubly linked list, it might as well be a dequeue ; P.

You haven't answered any of my questions though. I know what a linked list is, and what a dequeue is, but for a moment would you please just stop throwing around names of data-types and data structures? The point is your library is named as a queue despite not having the functionality of a queue.

A linked list is not simply an alternative to a queue, the two are used separately. An array would be an alternative to a linked list.

But please, answer my questions. I want to know how I would implement this to have a several (3 or 4) queues with some of the structs appearing in multiple queues.

From what I can see the "nodes" which you are implementing this into only reference a single next member. This doesn't allow you to contain the struct in multiple "linked list" because you've only allowed the node to appear once. Correct me if I'm wrong.

The code is for a data-structure (Problem Berb?), known as a Queue (pronouned Q or Kyew).
This data-structure (u mad bro?) allows you to insert nodes (integers) at the end and retrieve nodes (integers) from the top.

Well you don't actually "retrieve" the node, you simply dequeue it (because in order to reference the "queue" you would have to reference the first element in the "queue"). This will relieve the first struct from the linked list. So far so good.

Now, let's try to do this. Have two queues. Each queue has two elements. The first queue contains the two elements in one order, and the second queue contains them in the other order. Please, explain to me how you would go about doing that with this.

Allow me to provide a struct for the queue to be implemented into:

struct Banana
    private string name
    static method create takes string name returns thistype
        local thistype b = allocate()
        set b.name = name
        return b
    endmethod
endstruct

 

[Nestharus]

Set the value of multiple nodes to the same thing? You have direct access to the pointers >.>.

 

[Berb]

But you only have one next member to play with. I want the next member to be able to point to different things depending on which queue I am in. From what I see, each struct may only have one next member, which disallows this.

Or are you saying that we should do this:

struct QueueNode
    structtype someStruct
    implement Queue
  
    // and then define the struct that we want to carry here?
    static method create takes structtype yourStruct returns thistype
        local thistype q = allocate()
        set q.someStruct = yourStruct
        return q
    endmethod
endstruct

This would give the same result as what I had posted earlier except without providing a standard implementation of the queue. There is no reason to complicate things by requiring more implementation than necessary.

 

[Nestharus]

To your implementation, yes. The nodes I return are literally pointers. Not all queues need to do what you just did and some do, hence why I just return the pointers for you to play with : ).

 

[Berb]

The nodes I return are literally pointers. Not all queues need to do what you just did and some do, hence why I just return the pointers for you to play with : ).

Eh, I'd prefer a Queue that doesn't leave half of the work up to the user. It's supposed to make things more simple.