[Mono-list] Donation of PriorityQueue class
Mike Anderson
mikera_mono@yahoo.co.uk
Sat, 30 Mar 2002 12:24:58 +0000
--=====================_7725528==_
Content-Type: text/plain; charset="us-ascii"; format=flowed
Hi Guys,
What is the Mono plan as it relates to the inclusion of classes that are
*not* in the .NET framework?
Only asking because I've recently been implementing a PriorityQueue
collection class for a game I have been writing and thought you might like
to include it in Mono. I think it's general enough to be useful in many
settings (the only obvious specialization is the use of "double" for
priority values) and the performance is pretty good.
Anyway, here it is if you want it......
--=====================_7725528==_
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: attachment; filename="PriorityQueue.cs"
// created on 29/03/2002 at 19:27
//
// By: Mike Anderson (mikera_mono@yahoo.co.uk)
//
// License: LGPL
using System;
using System.Collections;
using System.Diagnostics;
// Note: The PriorityQueue class uses a Binary Heap data structure
// This has the following useful properties
// - No pointer/node class overheads
// - O(log n) insertion via Enqueue
// - O(log n) removal via Dequeue
//
// Basically this is implemented in two arrays (objects and priorities)
// The highest priority item is always in position 0 in the arrays
// The item in position i has child nodes in positions (i*2+1) and (i*2+2)
namespace System.Collections {
public class PriorityQueue : IEnumerable, ICollection {
private static int INITIALCAPACITY=8;
private int capacity;
private int count=0;
public double[] priorities;
public object[] objects;
public PriorityQueue(int cap) {
capacity=cap;
priorities = new double[capacity];
objects = new object[capacity];
}
public PriorityQueue() : this(INITIALCAPACITY) {
}
public PriorityQueue(PriorityQueue pq) {
capacity=pq.count;
priorities = new double[capacity];
objects = new object[capacity];
count=capacity;
Array.Copy(pq.objects,0,objects,0,count);
Array.Copy(pq.priorities,0,priorities,0,count);
}
public int Count {
get {
return count;
}
}
public bool IsSynchronized {
get {
return false;
}
}
public object SyncRoot {
get {
return this;
}
}
// copies out all the objects in priority order, but *loses* priority values
public virtual void CopyTo(Array array, int index) {
PriorityQueue pq=new PriorityQueue(this);
for (int i=0; i<count; i++) {
array.SetValue(pq.Dequeue(),i);
}
}
public virtual void Clear() {
count=0;
}
private void Swap(int a, int b) {
object to=objects[a];
objects[a]=objects[b];
objects[b]=to;
double td=priorities[a];
priorities[a]=priorities[b];
priorities[b]=td;
}
public virtual void Enqueue(object o, double p) {
EnsureCapacity(count+1);
int i=count;
objects[i]=o;
priorities[i]=p;
count=count+1;
// swap the new object up the tree as necessary
while( (i>0) && (p>priorities[(i-1)/2]) ) {
Swap(i,(i-1)/2);
i=(i-1)/2;
}
}
public virtual object Dequeue() {
if (count==0) throw new InvalidOperationException("PriorityQueue is empty");
object result=objects[0]; // this is the highest priority element
count=count-1;
if (count==0) return result; // finished if no more elements
// copy the last element into the top position
objects[0]=objects[count];
priorities[0]=priorities[count];
// have now removed the highest priority element
// the problem is just to make sure we still have a valid heap
// so we recurse down the tree, making sure each level satisfies:
// priority[i]>priority[i*2+1] and priority[i]>priority[i*2+2]
int i=0; // the object to push back down the tree
int ni=0; // the new target location
while ((i*2+1)<count) {
if (priorities[i]<priorities[i*2+1]) {
if (((i*2+2)<count)&&(priorities[i*2+1]<priorities[i*2+2])) {
ni=i*2+2;
} else {
ni=i*2+1;
}
} else {
if (((i*2+2)<count)&&(priorities[i]<priorities[i*2+2])) {
ni=i*2+2;
} else {
return result; // we are already pointing to highest bvalue
}
}
Swap(i,ni);
i=ni;
}
return result;
}
public virtual object Peek() {
if (count==0) throw new InvalidOperationException("PriorityQueue is empty");
return objects[0];
}
public virtual double PeekPriority() {
if (count==0) throw new InvalidOperationException("PriorityQueue is empty");
return priorities[0];
}
// contains method, tests equality with Object.Equals
// also allows for null object to test
public virtual bool Contains(object o) {
if (o==null) {
for (int i=0; i<count; i++) {
if (objects[i]==null) return true;
}
return false;
}
for (int i=0; i<count; i++) {
if (o.Equals(objects[i])) return true;
}
return false;
}
// double capacity whenever it is insufficient
// this ensures we keep amortised O(1) performance while adding
// given that SetCapacity(..) is an O(n) operation
private void EnsureCapacity(int s) {
if (s<=capacity) return;
SetCapacity(s*2);
}
public virtual void SetCapacity(int newcapacity) {
if (newcapacity<count) throw new InvalidOperationException("PriorityQueue: Cannot set capacity to less than Count");
double[] newpriorities=new double[newcapacity];
object[] newobjects=new object[newcapacity];
Array.Copy(priorities,0,newpriorities,0,count);
Array.Copy(objects,0,newobjects,0,count);
objects=newobjects;
priorities=newpriorities;
capacity=newcapacity;
}
// provide enumerator directly for performance reasons
public virtual PriorityQueueEnumerator GetEnumerator() {
return new PriorityQueueEnumerator(this);
}
// make sure we satisfy the IEnumerable interface
IEnumerator IEnumerable.GetEnumerator() {
return new PriorityQueueEnumerator(this);
}
// The enumerator class takes a snapshot for enumeration
// note this is an O(n log n) operation
// as we are effectively sorting all the objects
// anyone has a better algorithm.... let me know!
public class PriorityQueueEnumerator : IEnumerator {
private object[] source;
private int count;
private int position=-1;
public PriorityQueueEnumerator(PriorityQueue pq) {
count=pq.Count;
source=new object[count];
pq.CopyTo(source,0);
}
public object Current {
get {
if (position<0) throw new InvalidOperationException("PriorityQueueEnumerator: must call MoveNext() before accessing Current");
if (position>=count) throw new InvalidOperationException("PriorityQueueEnumerator: no more elements");
return source[position];
}
}
public bool MoveNext() {
position++;
return (position<count);
}
public void Reset() {
position=-1;
}
}
}
}
public class PriorityQueueTest {
public static int Main(string[] args) {
(new PriorityQueueTest()).RunTest();
return 0;
}
public void RunTest() {
EnqueueDequeueTest();
EnumeratorTest();
}
public void EnqueueDequeueTest() {
PriorityQueue pq=new PriorityQueue();
Debug.Assert(pq.Count==0);
// add items in a random-ish order
// we'll flip the values to make sure that these
// are not getting confused with the priorities
for (int i=1; i<=10; i++) {
for (int ii=1; ii<=10; ii++) {
pq.Enqueue(10000-(10*ii-i+1),10*ii-i+1);
}
}
Debug.Assert(pq.Count==100);
Debug.Assert(pq.Peek().Equals(9900));
Debug.Assert(((int)pq.PeekPriority()).Equals(100));
Debug.Assert(pq.Count==100);
// pull items off, hopefully in the correct order!
for (int i=100; i>=1; i--) {
Debug.Assert(pq.Dequeue().Equals(10000-i));
}
Debug.Assert(pq.Count==0);
try {
pq.Dequeue();
throw new Exception("PriorityQueue: Dequeue should throw exception on empty queue");
} catch (InvalidOperationException) {
}
}
public void EnumeratorTest() {
PriorityQueue pq=new PriorityQueue();
// add items in reverse-priority order
for (int i=1; i<=100; i++) {
pq.Enqueue(i,i);
}
Debug.Assert(pq.Count==100);
// everything should be read off the enumerator in priority order
int n=100;
foreach (object o in pq) {
Debug.Assert(o.Equals(n));
n--;
}
// the orginal collection should be unchanged
Debug.Assert(pq.Count==100);
}
public void SynchronisedTest() {
// TODO
}
}
--=====================_7725528==_
Content-Type: text/plain; charset="us-ascii"; format=flowed
--=====================_7725528==_--
_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com