I've got a lot of problems with my current implementation, but I figure my current main problem(that could be the source of the others) is that my priority queue loses nodes in either the Add or Remove proc. So my problem is probably some minor linking issue but it's not making itself apparent to me :P. So I'd really appreciate if someone with a familiarity of priority queues would scan through my source code to see if I made any blatant mistakes.
[Edit:] Actually the problem is probably with the removal of an item that isn't the head. Before I started the pathfinding implementation I tested the data structure with random data several times. All the data was in the structure and in the correct order. Then I used clear which properly deleted all the nodes and in the correct order. I never actually tested the removal of a random item within the structure which my pathfinding algorithm does when it finds a better way to get to a tile in the open list. I should have tested this more extensivly before trying to use it :P.
[Edit2:] Come to think of it this isn't really a priority queue since I'm removing items that aren't the head so it probably should be titled a sorted linked list as it isn't really a queue. But that's an irrellevent semantics issue I thought I'd point out.
datum
proc
CalculateValue()
return 0
PriorityQueue
var
PriorityQueueNode/head
proc
Add(newitem)
var/PriorityQueueNode/PQN = new(newitem)
var/PriorityQueueNode/prev
var/PriorityQueueNode/iter
if(!head)
head = PQN
return PQN
if(head.value > PQN.value)
PQN.nextNode = head
head = PQN
return PQN
prev = head
iter = head.nextNode
while(iter && iter.value < PQN.value)
prev = iter
iter = iter.nextNode
PQN.nextNode = iter
prev.nextNode = PQN
return PQN
Remove(item)
var/PriorityQueueNode/iter = head
var/PriorityQueueNode/prev = null
var/datum/olditem
if(head.item == item)
head = head.nextNode
olditem = iter.item
del iter
return olditem
while(iter && iter.item != item)
prev = iter
iter = iter.nextNode
if(iter)
prev.nextNode = iter.nextNode
olditem = iter.item
del iter
return olditem
return null
Clear()
while(head)
Remove(head.item)
PriorityQueueNode
var
item
value
PriorityQueueNode/nextNode
New(datum/p_item)
item = p_item
value = p_item.CalculateValue()
Note: Also if I missed some obvious optimizations please point out those too since the speed of this is vital to the overal speed of my pathfinding.