search

BlueRaja / High-Speed-Priority-Queue-for-C-Sharp

A C# priority queue optimized for pathfinding applications
MIT License
1.15k stars 169 forks source link

Find a way to support having the same node in multiple queues, if possible. #35

Closed dougmill closed 6 years ago

dougmill commented 7 years ago

I've been finding in my project that I need multiple priority queues for different purposes, and some of the same objects need to go in each queue. This obviously requires multiple index values, and potentially multiple priority values, but FastQueuePriorityNode only allows for one of each.

At first I handled this by making a renamed copy of FastPriorityQueue and its node class, converting the node classes to interfaces, implementing both interfaces on the queued object, and using the copy for the second queue. But now "two queues" has expanded to "arbitrarily many queues" and that won't work any more.

SimplePriorityQueue can handle this by wrapping the object in a per-queue node wrapper, but I'd rather not accept the performance cost for that.

I'm working on a solution for my project, but I'm not sure it won't have any project-specific details and I expect there are plenty of other people who would find multi-queue support useful.

BlueRaja commented 7 years ago

I'll leave this open for a while, but I don't think there's going to be a good solution. A priority queue that uses structures (which will be slower for .Contains(), but might be faster for other operations) might suit your needs better.

dougmill commented 7 years ago

Turns out for this project I can use wrapper nodes with minimal performance cost because I almost never need to find a wrapper node given the node it wraps. That cuts out the ubiquitous dictionary lookups that I think are the main performance reduction in the simple queue.