Romek
Super Moderator
- Reaction score
- 964
Double-Ended Queue
By Romek
By Romek
Version 2.0
Introduction:Inspired by this thread. I thought a double-ended queue data structure may actually have a few uses; mainly for well.. Queuing. 
Click here to find out more.
Each queue instance and value in the queue uses up an instance. There is a maximum of 8191 instances. Destroy removes the queue instance and all the values.
Click here to find out more.
Wikipedia (edited a little) said:
Each queue instance and value in the queue uses up an instance. There is a maximum of 8191 instances. Destroy removes the queue instance and all the values.
Methods and Members:
- [ljass]local Queue q = queue.create()[/ljass]
- Creates a new Queue object for you to use.
- [ljass]call q.pushBack(/*value*/)[/ljass]
- [ljass]call q.push(/*value*/)[/ljass]
- Adds the given value to the back of the queue.
- [ljass]local integer i = q.popFront()[/ljass]
- [ljass]local integer i = q.pop()[/ljass]
- Returns and removes the value at the front of the queue. Returns 0 if the queue is empty.
- [ljass]call q.pushFront(/*value*/)[/ljass]
- [ljass]call q.unshift(/*value*/)[/ljass]
- Adds the given value to the front of the queue.
- [ljass]local integer i = q.popBack()[/ljass]
- [ljass]local integer i = q.shift()[/ljass]
- Returns and removes the value at the back of the queue. Returns 0 if the queue is empty.
- [ljass]local integer i = q.first()[/ljass]
- [ljass]local integer i = q.front()[/ljass]
- Returns (but doesn't remove) the value at the front of the queue. Returns 0 if the queue is empty.
- [ljass]local integer i = q.last()[/ljass]
- [ljass]local integer i = q.back()[/ljass]
- Returns (but doesn't remove) the value at the back of the queue. Returns 0 if the queue is empty.
- [ljass]local boolean b = q.contains(/*value*/)[/ljass]
- [ljass]local boolean b = q.exists(/*value*/)[/ljass]
- Returns true if the value is within the queue.
- [ljass]local integer i = q.countValue(/*value*/)[/ljass]
- Returns the number of times the given value is in the queue.
- [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.
- [ljass]call q.removeAll(/*value*/)[/ljass]
- [ljass]call q.deleteAll(/*value*/)[/ljass]
- [ljass]call q.purge(/*value*/)[/ljass]
- Removes all instances of the given value from within the queue.
- [ljass]local queue anotherQueue = q.copy()[/ljass]
- Creates a copy of the queue, including the values within it.
- [ljass]call q.combineBack(/*another queue*/)[/ljass]
- [ljass]call q.combine(/*another queue*/)[/ljass]
- Adds all values from the given queue to the back of the queue. Removes the given queue.
- [ljass]call q.combineFront(/*another queue*/)[/ljass]
- Adds all values from the given queue to the front of the queue. Removes the given queue.
- [ljass]local boolean b = q.empty()[/ljass]
- Returns true if the queue is empty, and false otherwise.
- [ljass]local integer i = q.size[/ljass]
- The amount of values in the queue.
- [ljass]call q.destroy()[/ljass]
- Destroys the queue to free up memory!
Example:
JASS:
function Example takes nothing returns nothing
local Queue q = Queue.create()
call q.push(-1) // Adds this value to the back of the queue
call q.push(50)
call q.push(100)
call q.push(27)
call BJDebugMsg(I2S(q.size)) // Displays "4"
call BJDebugMsg(I2S(q.front())) // Displays "-1" (Doesn't remove value)
call BJDebugMsg(I2S(q.size)) // Displays "4" (The value wasn't removed)
call BJDebugMsg(I2S(q.pop())) // Displays "-1" (And removes the value)
call BJDebugMsg(I2S(q.pop())) // Displays "50"
call BJDebugMsg(I2S(q.pop())) // Displays "100"
call BJDebugMsg(I2S(q.size)) // Displays "1" (we removed 3 of the 4 values)
call BJDebugMsg(I2S(q.pop())) // Displays "27"
call q.destroy() // Destroys the queue
endfunctionThe Code:
JASS:
library Queue
// _____________________________________________________
// +-----------------------------------------------------+
// || ___ Version 2.0 ||
// || / _ \ _ _ ___ _ _ ___ ||
// || | | | | | | |/ _ \ | | |/ _ \ ||
// || | |_| | |_| | __/ |_| | __/ ||
// || \__\_\\__,_|\___|\__,_|\___| ||
// || By Romek ||
// ||___________________________________________________||
// ||¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯||
// || Queue implements the queue data structure into ||
// || vJass. Visit the wikipedia article for more ||
// || information: ||
// || <a href="http://en.wikipedia.org/wiki/Double-ended_queue" target="_blank" class="link link--external" rel="noopener">http://en.wikipedia.org/wiki/Double-ended_queue</a> ||
// ||___________________________________________________||
// ||¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯||
// || See the following Thehelper.net thread for more ||
// || information regarding the functions: ||
// || <a href="http://www.thehelper.net/forums/showthread.php?t=137226" class="link link--internal">www.thehelper.net/forums/showthread.php?t=137226</a> ||
// |+---------------------------------------------------+|
// ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
struct Queue
private thistype next = 0 // first
private thistype prev = 0 // last
private integer data = 0 // size
// How many values are there?
method operator size takes nothing returns integer
return .data
endmethod
// Is the queue empty?
method empty takes nothing returns boolean
return .size == 0
endmethod
// Peek at the first value in the queue
method front takes nothing returns integer
if .empty() then
debug call BJDebugMsg("Queue: Attempt to peek at an empty queue!")
return 0
endif
return .next.data
endmethod
// Peek at the last value in the queue
method back takes nothing returns integer
if .empty() then
debug call BJDebugMsg("Queue: Attempt to peek at an empty queue!")
return 0
endif
return .prev.data
endmethod
// Return true if the selected value is in the queue.
method contains takes integer in returns boolean
local thistype node = .next
loop
if node.data == in then
return true
endif
set node = node.next
exitwhen node == 0
endloop
return false
endmethod
// Return the amount of times 'in' is in the queue.
method countValue takes integer in returns integer
local thistype node = .next
local integer count = 0
loop
if node.data == in then
set count = count + 1
endif
set node = node.next
exitwhen node == 0
endloop
return count
endmethod
// Remove the first value 'in' in the queue.
method remove takes integer in returns nothing
local thistype node = .next
loop
if node.data == in then
set node.next.prev = node.prev
set node.prev.next = node.next
set node.prev = -2
call node.destroy()
return
endif
set node = node.next
exitwhen node == 0
endloop
endmethod
// Remove the last value 'in' in the queue.
method removeLast takes integer in returns nothing
local thistype node = .prev
loop
if node.data == in then
set node.next.prev = node.prev
set node.prev.next = node.next
set node.prev = -2
call node.destroy()
return
endif
set node = node.prev
exitwhen node == 0
endloop
endmethod
// Remove all values 'in' in the queue.
method removeAll takes integer in returns nothing
local thistype node = .next
loop
if node.data == in then
set node.next.prev = node.prev
set node.prev.next = node.next
set node.prev = -2
call node.destroy()
endif
set node = node.next
exitwhen node == 0
endloop
endmethod
// Add a value to the back of the queue.
method pushBack takes integer in returns nothing
local thistype node = .allocate()
set node.data = in
if .empty() then
set .next = node
set .prev = node
else
set .prev.next = node
set node.prev = .prev
set .prev = node
endif
set .data = .data + 1
endmethod
// Add a value to the back of the queue.
method pushFront takes integer in returns nothing
local thistype node = .allocate()
set node.data = in
if .empty() then
set .next = node
set .prev = node
else
set .next.prev = node
set node.next = .next
set .next = node
endif
set .data = .data + 1
endmethod
// Get a value from the front of the queue.
method popFront takes nothing returns integer
local integer toreturn
if .empty() then
debug call BJDebugMsg("Queue: Attempt to pop a value from an empty queue")
return 0
endif
set toreturn = .next.data
set .data = .data - 1
if .empty() then
set .next.prev = -2
call .next.destroy()
else
set .next = .next.next
set .next.prev.prev = -2
call .next.prev.destroy()
set .next.prev = 0
endif
return toreturn
endmethod
// Get a value from the back of the queue.
method popBack takes nothing returns integer
local integer toreturn
if .empty() then
debug call BJDebugMsg("Queue: Attempt to pop a value from an empty queue")
return 0
endif
set toreturn = .prev.data
set .data = .data - 1
if .empty() then
set .prev.prev = -2
call .prev.destroy()
else
set .prev = .prev.prev
set .prev.next.prev = -2
call .prev.next.destroy()
set .prev.next = 0
endif
return toreturn
endmethod
// Copy the queue
method copy takes nothing returns thistype
local thistype new = .allocate()
local thistype node = .next
loop
call new.pushBack(node.data)
set node = node.next
exitwhen node == 0
endloop
return new
endmethod
// Add another queue to the back of this one
method combineBack takes thistype other returns nothing
loop
call .pushBack(other.popFront())
exitwhen other.empty()
endloop
call other.destroy()
endmethod
// Add another queue to the back of this one
method combineFront takes thistype other returns nothing
loop
call .pushFront(other.popBack())
exitwhen other.empty()
endloop
call other.destroy()
endmethod
// Destroy node/queue
method onDestroy takes nothing returns nothing
if .prev != -2 and .next.prev != -2 and .next != 0 then
set .next.prev = -1
set .prev = -2
call .next.destroy()
endif
endmethod
// Alternative method names:
method push takes integer in returns nothing
call .pushBack(in)
endmethod
method pop takes nothing returns integer
return .popFront()
endmethod
method unshift takes integer in returns nothing
call .pushFront(in)
endmethod
method shift takes nothing returns integer
return .popBack()
endmethod
method last takes nothing returns integer
return .back()
endmethod
method first takes nothing returns integer
return .front()
endmethod
method exists takes integer in returns boolean
return .contains(in)
endmethod
method delete takes integer in returns nothing
call .remove(in)
endmethod
method deleteFirst takes integer in returns nothing
call .remove(in)
endmethod
method removeFirst takes integer in returns nothing
call .remove(in)
endmethod
method deleteLast takes integer in returns nothing
call .removeLast(in)
endmethod
method deleteAll takes integer in returns nothing
call .removeAll(in)
endmethod
method purge takes integer in returns nothing
call .removeAll(in)
endmethod
method combine takes thistype other returns nothing
call .combineBack(other)
endmethod
endstruct
endlibraryA demo map for something like this is pointless.
