Jump to content
  • Advertisement

Glak

Member
  • Content count

    460
  • Joined

  • Last visited

Community Reputation

315 Neutral

About Glak

  • Rank
    Member

Recent Profile Visitors

The recent visitors block is disabled and is not being shown to other users.

  1. Thank you for the replies.   Waterlimon, I agree that have a SortedDictionary of Lists is probably the most elegant way from a user of the class standpoint.  I would definitely do it this way if I were making a general-purpose priority queue class.  C# should include such a class.  However I don't want to dedicate the time to working out all of the corner cases so I'm going to go with my more hacky approach, though improved based on the feedback that I am getting here.   Krypt0n, yes I think that bitshifting makes more sense for the reasons that you stated.  I rarely use bitshifting so I was hesitant.  I just edited my code above to be a bitshifting version.  Also I included the code showing how it will be used.
  2. Thanks for the response.  I edited my code to add clarifying comments and renamed "id" to "arbitrary"   Basically the problem is that SortedDictionary is almost a priority queue, but since it requires unique keys I can't use "time" as the key (since multiple events can take place on the same tick).  My solution is to tack on a small fraction onto each time to make them into unique keys.  I don't actually care about the ordering of events with the same time, but SortedDictionary does.   Using doubles (which are nicely truncated with the converstion to int) seemed easier than working with bitshifting.  I'm pretty sure that max_int will never be approached.
  3. I was surprised to find that c# does not contain a priority queue (also known as a "heap").  The closest thing seems to be SortedDictionary, but that requires unique keys.  I decided to create the simplest possible priority queue.  (note: I have edited this a few times since originally posting)     public class PriorityQueue     {         //SortedDictionary is like a priority queue, but unfortunately it requires unique keys         SortedDictionary<int, Event> events = new SortedDictionary<int,Event>();         //this is used to generate unique keys from possibly non-unique times         int arbitrary = 0;         //schedule an event at the specified time         public void add(int time, Event e)         {             int key = (time << 16) + arbitrary;             events.Add(key, e);             ++arbitrary;         }         //returns true if there are one or more events scheduled for the current time, this will be a loop condition         public bool ready_now(int time)         {             return ((events.First().Key)>>16) == time;         }         //pulls an item out for processing, this will be in the body of the loop         public Event pop()         {             var f = events.First();             events.Remove(f.Key);             return f.Value;         }     } and here is how it will be used: while(events.ready_now(current_time)) { Event e = events.pop(); e.happen(); } What do you think?  Any subtle (or not so subtle) bugs?
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!