RandomOrderQueue.cs

using System;
using System.Collections.Generic;

namespace Jesse.LanguageClassHelper
{
    /// <summary>
    /// A queue that returns items in random order
    /// </summary>
    public class RandomOrderQueue<T>
    {
        private readonly Random _randomizer;
        private int _itemCount = 0;
        
        /// <summary>List item before first item in the linked list.</summary>
        private ListItem _listHead = new ListItem();

        private class ListItem
        {
            public T Item { get; set; }
            public ListItem Next { get; set; }
        }

        public RandomOrderQueue()
        {
            _randomizer = new Random();
        }

        public RandomOrderQueue(Random randomizer)
        {
            _randomizer = randomizer;
        }

        public void AddItems(IEnumerable<T> items)
        {
            foreach (T i in items)
                Add(i);
        }

        public void Add(T item)
        {
            // figure out where to place it
            int insertAtIndex;
            insertAtIndex = _randomizer.Next(_itemCount + 1);

            // walk the list until referencing the item before the desired insert position
            ListItem previousItem = _listHead;
            for (int i = 0; i < insertAtIndex; i++)
                previousItem = previousItem.Next;

            // insert a new item into the list
            previousItem.Next = new ListItem()
            {
                Item = item,
                Next = previousItem.Next,
            };

            // increment the item count
            _itemCount++;
        }

        public bool TryDequeue(out T item)
        {
            // make sure there is an item left in the list
            if (_listHead.Next == null)
            {
                item = default(T);
                return false;
            }

            // move the list head and change the count
            _listHead = _listHead.Next;
            _itemCount--;
            
            // return the item, and drop our reference to it in the list head 
            item = _listHead.Item;
            _listHead.Item = default(T);
            return true;
        }

        public int Count
        {
            get { return _itemCount; }
        }
    }
}