Tag Archives: c#

Priority Queue with a Twist

Posted on by
1

Recently I needed a variation of a Priority Queue in C# that supported concurrency.

My requirement for a Priority Queue

  • I would receive a lot of jobs in a random order
  • A job would contain a JobNumber indicating in which order they should be executed
  • The first JobNumber would be zero
  • All JobNumbers would be present (e.g. number 7 would not be missing)
  • Several worker threads would simultaneously be retrieving jobs from the queue, hence the need for concurrency

The Solution

For the clarity of the example, I have simplified the Job class to look like:

public class Job
{
	public int jobNumber;
}

My Concurrent Priority Queue would look like:

class ConPQueue
{
	private const int TIMEOUT = 10000; // 10 seconds
	private SortedList<int, Job> list;
	private int nextJobNumber;
	private static EventWaitHandle waitHandle = new AutoResetEvent(false);
	private Boolean completeAdding = false;

	public ConPQueue()
	{
		this.list = new SortedList<int, Job>();
		this.nextJobNumber = 0;
	}

	public Boolean add(Job job)
	{
		Boolean status = false;
		if (Monitor.TryEnter(this.list, TIMEOUT))
		{
			try
			{
				this.list.Add(job.jobNumber, job);
				// Notify the take() method that new values are present
				waitHandle.Set();
			}
			finally
			{
				Monitor.Exit(this.list);
			}
		}
		return status;
	}

	public Job take()
	{
		Job job = null;
		while (job == null)
		{
			// If next job is not present, wait until notified
			// that new jobs have been added to the list
			while (!hasKey(this.nextJobNumber))
			{
				waitHandle.WaitOne();
			}
			if (Monitor.TryEnter(this.list, TIMEOUT))
			{
				try
				{
					this.list.TryGetValue(this.nextJobNumber, out job);
					if (job != null)
					{
						// Only remove item on successfull retrieval
						this.list.Remove(this.nextJobNumber++);
					}
				}
				finally
				{
					Monitor.Exit(this.list);
				}
			}
		}
		return job;
	}

	public Boolean hasKey(int Key)
	{
		Boolean exists = false;
		if (Monitor.TryEnter(this.list, TIMEOUT))
		{
			try
			{
				exists = this.list.ContainsKey(Key);
			}
			finally
			{
				Monitor.Exit(this.list);
			}
		}
		return exists;
	}

	public void addingComplete()
	{
		completeAdding = true;
	}

	public Boolean isCompleted
	{
		get { return completeAdding && list.Count == 0; }
	}
}

To add a Job to the Queue:

queue.take();

To retrieve a Job from the Queue:

queue.add(myJob);

Hope this can inspire fellow developers :-)

Messing around with Microsoft XNA

Posted on by
Reply

The last couple of days I’ve been messing around with XNA 4.0. I have never tried it before – but a lot of things are real easy to do, but one thing baffled me – how hard is was to draw a line.

After searching a bit on the topic, I decided to make a method for drawing lines – just thought I would share it.

private void DrawLine(SpriteBatch batch, float width, Color color, Vector2 p1, Vector2 p2)
{
	Texture2D blank = new Texture2D(GraphicsDevice, 1, 1, false, SurfaceFormat.Color);
	blank.SetData(new[] { Color.White });
	float angle = (float)Math.Atan2(p2.Y - p1.Y, p2.X - p1.X);
	float length = Vector2.Distance(p1, p2);
	Vector2 scale = new Vector2(length, width);
	batch.Draw(blank, p1, null, color, angle, Vector2.Zero, scale, SpriteEffects.None, 0);
}

Can it really be true that this is the smartest way to draw a line?