Rotor FUBAR of the day (compliments Christoph Nahr): Queue.Clone returns invalid results...
So the method in question is Queue.Clone(). Ideally, Queue.Clone() would return an exact copy of the Queue being cloned. IMO that should mean array density and size, current head/tail pointers, and current versions. However, the Clone method does a couple of strange things. Look below at what the code does actually do. It creates a new queue of the current _size, not the currently allocated internal array length. Uhm, kay. Then it sets the private _size field, uhm kay. Then it does an array copy, which is where things get really messed up. First, it copies from array element 0 to array element size. This means that elements of the queue at a location beyond _size (perhaps nearer _array.Length), won't even get copied. So elements appear to be lost. That isn't right.
Note also that _head and _tail are never copied. So if I Enqueue a bunch of elements, then Dequeue one, then Enqueue one. The _head element gets reset to 0 in the cloned queue. So does the _tail element. Hell, the only reason a new call to Enqueue doesn't overwrite the entire collection is because of a call to SetCapacity when you Enqueue the next element. Secretly, the _tail element gets updated to the new _size of the array. SetCapacity is called because the new queue length was perfectly sized to the number of existing elements. Algorithmically having _tail set to 0 isn't a bad thing though, because logically if you have a queue and you resize it down to the number of elements in the queue, the tail wraps back around and should be pointing at the first element in the list. I can't fault the programmer her for finding a cool shortcut, I guess, just in their array copying implementation. (note a switch to CopyTo would appear to do the *right* thing).
/// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Clone"]/*' />
public virtual Object Clone() {
Queue q = new Queue(_size);
q._size = _size;
Array.Copy(_array, 0, q._array, 0, _size);
q._version = _version;
return q;
}
So what might fix this problem? Well, first, using the CopyTo method of the Queue would have done the right thing. Even better would have been to simply use the ToArray method. I've included what I think would be the appropriate code at the bottom, along with a sample program that demonstrates *losing* elements because of the way the Clone is done. Note a Clone of an unused queue would work as expected.
If I recall there was some validation behind why the Clone() method didn't really work correctly, but I can't for the life of me remember. Hopefully someone chimes in and gives us some validation for this problem. Special thanks to Christoph Narh for pointing out some of these issues on the msnews.microsoft.com newsgroups.
Here is the recoded Clone method using ToArray:
/// <include file='doc\Queue.uex' path='docs/doc[@for="Queue.Clone"]/*' />
public virtual Object Clone() {
Queue q = new Queue(); // We don't care about initial settings
q._array = this.ToArray();
q._size = q._array.Length;
q._version = _version;
return q;
}
Here is the sample program that demonstrates losing elements:
using System;
using System.Collections;
public class QueueCloneHack {
private static void Main(string[] args) {
Queue queue = new Queue(50); // Initial Capacity
/*
1 2 3 4 5 6
h t
*/
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
queue.Enqueue(5);
queue.Enqueue(6);
/*
1 2 3 4 5 6
h t
*/
queue.Dequeue();
/*
1 2 3 4 5 6 7
h t
*/
queue.Enqueue(7);
Queue queue2 = (Queue) queue.Clone();
Console.WriteLine(queue2.Count);
while(queue2.Count > 0) {
Console.WriteLine(queue2.Dequeue());
}
}
}