Snippet Double-Ended Queue

[quraji]

To be honest it's a little annoying seeing these arguments..
And it's just downright confusing to have all these linked-list type snippets floating around, seeing as how there's no naming convention, and some have methods others don't, and vice versa. Hell, I even have some of my own (emulating data structures in vJass is fun, isn't it?)!

Can't we have a TH.net standard library for things like this? I mean come on!

Pick a convention, find the best interface and implementation for the job and that's it. Of course that would only work practically for simple things like data structures.

I'm just tired of a million different submissions doing the same thing (maybe just a bit better/simpler/more efficient/whatever) and having different interfaces and rules.

[lJASS]endrant[/lJASS]

 

[Romek]

I think it's a good thing that there are a few systems that do similar things (TT, KT2 being a good example). It allows for users to choose what they prefer themselves.

To add:
- random
- shuffle

I was going to add "get at position", "remove at position", etc. But I think that's going a bit close to the 'linked list' area.

 

[Steel]

I think it's a good thing that there are a few systems that do similar things

Why? Something like this is a standard in the industry.

This would be like allowing 3 people to write Quick Sort. What's the purpose, the algorithm is already out there and as optimized as can be so you're really just splitting hairs with this garbage. Maybe next someone will introduce a Priority Queue! ...

For those not completely following what's going on here, a Queue uses a Linked List structure. The difference is that a Queue can only add or remove from the front or the back of the Queue whereas a Linked List can manipulate any point in the structure.

 

[quraji]

Which is why I wish we could have one linked-list module and one linked-list struct. A priority queue wouldn't be bad.

 

[Steel]

[*][ljass]call q.remove(/*value*/)[/ljass]
[*][ljass]call q.removeFirst(/*value*/)[/ljass]
[*][ljass]call q.delete(/*value*/)[/ljass]
[*][ljass]call q.deleteFirst(/*value*/)[/ljass]

• Removes the first instance of the given value from within the queue.

[*][ljass]call q.removeLast(/*value*/)[/ljass]
[*][ljass]call q.deleteLast(/*value*/)[/ljass]

• Removes the last instance of the given value from within the queue.

Given that you allow a user access to these functions, this is not a queue. A queue only offers the ability to Enqueue and Dequeue when handling data manipulation. If you provide the ability to remove specific values anywhere from your data structure, you are talking about a linked list.

 

[quraji]

Given that you allow a user access to these functions, this is not a queue. A queue only offers the ability to Enqueue and Dequeue when handling data manipulation. If you provide the ability to remove specific values anywhere from your data structure, you are talking about a linked list.

I think he probably knows that, but you can't compete in 'functionality' if you can only do those things

But yes, it would be nice if this just did it's job. A nice simple queue (untested):

struct queue
    private thistype next
    private thistype last
    private integer data // size of queue (if parent struct) or attached data (if queue node)...nice trick romek

    static method create takes nothing returns thistype
        local thistype new = thistype.allocate()
        set new.next = new
        set new.last = new
        set new.data = 0
        return new
    endmethod

    method size takes nothing returns integer
        return .data
    endmethod
    method isEmpty takes nothing returns boolean
        return (.data==0)
    endmethod
    
    method enqueue takes integer i returns nothing
        local thistype node = thistype.allocate()
        set .last.next = node
        set .last = node
        set node.last = -1 // identifies this is a node
        set node.data = i  // store data on node
        set .data = .data+1 // increment size
    endmethod
    method dequeue takes nothing returns integer
        local integer d
        if (.isEmpty()) then
            debug call BJDebugMsg("|c00505050Queue: Attempt to pop value from empty queue!|r")
            return 0
        endif
        set d = .next.data
        call .next.destroy()
        set .next = .next.next // yeah, it works ;O
        set .data = .data-1
        if (.isEmpty()) then
            set .last = this
            set .next = this
        endif
        return d
    endmethod
    method peek takes nothing returns integer
        if (.isEmpty()) then
            debug call BJDebugMsg("|c00505050Queue: Attempt to peek at empty queue!|r")
            return 0
        endif
        return .next.data
    endmethod
    
    method copy takes nothing returns thistype
        local queue new = queue.create()
        local queue q
        loop
            set q = .next
            exitwhen (q==.last)
            call new.enqueue(q.data)
        endloop
        return new
    endmethod
    
    method clear takes nothing returns nothing
        loop
            exitwhen (.dequeue==0)
        endloop
    endmethod
    
    method onDestroy takes nothing returns nothing
        if (.last!=-1) then  // make sure to depopulate the queue, if it is one
            call .clear()
        endif
    endmethod
endstruct