LimitedQueue

• Download source - 3.27 KB

Introduction

This article describes how I tried to derive from Queue<T>, eventually decided to wrap it instead, and discusses the various issues involved in deriving from classes that were written by others and why certain decisions should be made when we write our own classes.

The result is LimitedQueue<T> which has the functionality of the built-in Queue<T>, plus some new features. The implementation, however, leaves much to be desired because the writers of Queue<T> wrote it in such a way that deriving from it properly is just not possible. In this way, this article is part instruction, part cautionary tale, and part rant.

Background

After I read this[^] article by Marc Clifton, I began thinking about how I would do that. Marc implemented his own circular list, described in this[^] article. I chose not to do that, but rather to use a System.Collections.Generic.Queue<T> and limit the number of items I put into it. After writing that, I thought about splitting the queue part away from the averaging part for more modularity, much as Marc did, but then I got caught up in other things.

Later, Jean-marc Lai published this[^] article, describing a technique similar to Marc's, with some improvement.

So, having the idea suddenly thrust back upon me, I took it up again, this time intending to not only split the queue away from the averaging code, but also desiring to add an indexer, while still using a Queue<T> to do the bulk of the work.

The Basics

By now, you are (or should be) familiar with the trinity of object-oriented programming: encapsulation, inheritance, and polymorphism. The Queue<T> class encapsulates the concepts associated with a first-in-first-out (FIFO) data structure; it hides the details of managing the underlying data storage and provides only a few methods for accessing that data, the most important being: Enqueue (to add items), Dequeue (to remove items), and Count (to find out how many items are in the queue).

In .NET, Queue<T> is implemented using an array to store the data and the implementation allows the array to grow and shrink as the amount of stored data increases and decreases. Rather than attempt to duplicate all that functionality in my own class, I would prefer to inherit from Queue<T> and use all its built-in functionality.

In .NET and C#, classes may be sealed if the author insists that no inheritance be possible (structs and static classes are inherently sealed). Queue<T> is not sealed, so inheritance is possible.

In .NET and C#, class members may also be marked virtual, this is what enables polymorphism. The members of Queue<T> are not virtual and therefore do not provide polymorphism. I find that inheritance without polymorphism is like sugar-free candy; it may be fine for some, but it leaves a bad taste in my mouth.

The Problem

Ideally, I would have my class derive from Queue<T> and override the Enqueue method:

public LimitedQueue<T> : Queue<T> 
{
    protected int maxitems ;

    // Constructors would go here
 
    public override void // Note the override keyword
    Enqueue
    (
        T Item
    )
    {
        while ( this.Count >= this.maxitems ) // If would work just as well as while here
        {
            this.Dequeue() ;
        }
 
        base.Enqueue ( Item ) ; // Notice call to base
 
        return ;
    }
}

and that would be pretty much all that's required for a very simple queue that limits the number of items it will hold. All the hard work is performed by the Queue<T>.

But because Queue<T>.Enqueue (as well as the other members of Queue<T>) is not virtual, we can't override it. So we can try non-polymorphic inheritance. What would happen then is that, although I could assign a reference to an instance of LimitedQueue<T> to a variable of type Queue<T>, if we call the Enqueue method on that reference*, the base Enqueue method would be executed, not the Enqueue method of LimitedQueue<T>. (The included Polydemo.cs file contains a demonstration of polymorphic and non-polymorphic inheritance.)

In this case, the possibility of having the base Enqueue method called from outside the class will lead to an invalid state, so we can't use non-polymorphic inheritance.

* Unless we cast it back to LimitedQueue<T>.

Wrapping

Given that we want to use the features of Queue<T> but can't inherit from it, our only resort is to wrap it. Wrapping simply means having an instance of the class as a field in our class and giving our class an interface similar to that of the wrapped class. In this case, we'll provide methods that we would otherwise override, pass some others through, and add a couple more.

LimitedQueue<T>

So the new class will need two fields, one for the Queue<T> and one for the maximum number of items. I also chose to implement the System.Collections.Generic.IEnumerable<T> and System.IDisposable interfaces:

public class LimitedQueue<T>
:
    System.Collections.Generic.IEnumerable<T>
,
    System.IDisposable
{
    protected readonly System.Collections.Generic.Queue<T> items ;
 
    private int maxitems = int.MaxValue ;
}

Note that maxitems is private, there is a property (described later) for it that other classes (including derived classes) should use. The class will also need constructors, but I'll get to them later too.

ForceEnqueue

The ForceEnqueue method will use Dequeue to ensure we have room for the new item:

public virtual void
ForceEnqueue
(
    T Item
)
{
    lock ( this.items )
    {
        while ( this.items.Count >= this.maxitems )
        {
            this.Dequeue() ;
        }
 
        this.items.Enqueue ( Item ) ;
 
        return ;
    }
}

Enqueue

The Enqueue method will throw an Exception if the LimitedQueue<T> is full:

public virtual void
Enqueue
(
    T Item
)
{
    lock ( this.items )
    {
        if ( this.items.Count >= this.MaxItems )
        {
            throw ( new System.InvalidOperationException ( "The LimitedQueue is full" ) ) ;
        }
 
        this.items.Enqueue ( Item ) ;
 
        return ;
    }
}

TryEnqueue

The TryEnqueue method will not throw an Exception if the LimitedQueue<T> is full:

public virtual bool
TryEnqueue
(
    T Item
)
{
    lock ( this.items )
    {
        bool result = this.items.Count < this.MaxItems ;
 
        if ( result )
        {
            this.items.Enqueue ( Item ) ;
        }
 
        return ( result ) ;
    }
}

Dequeue

The problem with ForceEnqueue is that it may Dequeue an Item, and the user may want notification of the Item that's been dequeued. So I added an OnDequeue event (described later) to the class and Dequeue calls the RaiseDequeue method to raise the event:

public virtual T
Dequeue
(
)
{
    lock ( this.items )
    {
        T result = this.items.Dequeue() ;
 
        RaiseDequeue ( result ) ;
 
        return ( result ) ;
    }
}

TryDequeue

A version of Dequeue that doesn't throw an Exception when the LimitedQueue<T> is empty.

public virtual bool
TryDequeue
(
    out T Item
)
{
    lock ( this.items )
    {
        bool result = this.items.Count > 0 ;
 
        if ( result )
        {
            Item = this.items.Dequeue() ;
 
            RaiseDequeue ( Item ) ;
        }
        else
        {
            Item = default(T) ;
        }
 
        return ( result ) ;
    }
}

Clear

To clear the Queue<T>, we can't just call the Queue<T>'s Clear method, we need to call our own Dequeue method repeatedly until the Queue<T> is empty:

public virtual void
Clear
(
)
{
    lock ( this.items )
    {
        while ( this.items.Count > 0 )
        {
            this.Dequeue() ;
        }
    }

    return ;
}

Count

Count is one of the methods that we can simply pass to the Queue<T>:

public virtual int
Count
{
    get
    {
        return ( this.items.Count ) ;
    }
}

I won't enumerate the other pass-through members here.

Maxitems

MaxItems is one of the added members; it's a property. It will Dequeue any excess items if the new value allows fewer items than are already in the Queue<T>:

public virtual int
MaxItems
{
    get
    {
        return ( this.maxitems ) ;
    }
 
    set
    {
        if ( value <= 0 )
        {
            throw ( new System.ArgumentOutOfRangeException
            (
                "MaxItems"
            ,
                "MaxItems must be greater than zero"
            ) ) ;
        }
 
        lock ( this.items )
        {
            this.maxitems = value ;
 
            while ( this.Count > this.maxitems )
            {
                this.Dequeue() ;
            }
 
            this.items.TrimExcess() ;
        }
 
        return ;
    }
}

Indexer

The indexer is the trickiest part to implement, and will likely generate the most 1-votes.
Queue<T> doesn't have an indexer.
The System.Linq namespace has an Extension Method (ElementAt) that will act as an indexer for any IEnumerable<T>, but it relies on enumerating until it reaches the desired index; this is exceedingly inefficient if called repeatedly on a large collection.

You can use the ToArray or CopyTo method to get a copy of the array that the Queue<T> contains and then use an index; which is reasonable but still inefficient if called repeatedly on a large collection.

We know that Queue<T> stores its data in an array, but it's private. We also know that we can access any object's privates by using Reflection, but it's not a very good idea; for one thing, the definition of the class may change in future versions. In this case, I'm willing to suffer the slings and arrows and 1-votes; Queue<T> is unlikely to change except (I hope, I hope) to make it more derivable (or at least to add an indexer).

To use the private _array to write an indexer, we'll also need the _head value. We'll use Reflection to get the relevant FieldInfo objects. We also need to add fields to our class to store them; they can be static and we can use a static constructor to set them:

protected static readonly System.Reflection.FieldInfo arrayinfo ;
protected static readonly System.Reflection.FieldInfo headinfo  ;
 
static LimitedQueue
(
)
{
    arrayinfo = typeof(System.Collections.Generic.Queue<T>).GetField
    (
        "_array"

    ,
         System.Reflection.BindingFlags.Instance
         |
         System.Reflection.BindingFlags.NonPublic
    ) ;
 
    headinfo = typeof(System.Collections.Generic.Queue<T>).GetField
    (
        "_head"
    ,
         System.Reflection.BindingFlags.Instance
         |
         System.Reflection.BindingFlags.NonPublic
    ) ;
 
    return ;
}

Once we have references to the FieldInfo objects, we can use their GetValue methods whenever we want to access an index; the indexer, then, looks like this:

public virtual T
this
[
    int Index
]
{
    get
    {
        lock ( this.items )
        {
            if ( ( Index < 0 ) || ( Index >= this.Count ) )
            {
                throw ( new System.ArgumentOutOfRangeException
                (
                    "Index"
                ,
                    "That index is out of range"
                ) ) ;
            }
 
            T[] array = (T[]) arrayinfo.GetValue ( this ) ;
            int head  = (int) headinfo.GetValue  ( this ) ;
 
            return ( array [ ( head + Index ) % array.Length ] ) ;
        }
    }
}

In this way, we access the underlying array without having to copy it or iterate over it.

OnDequeue

The OnDequeue event is just a very basic event:

public delegate void DequeueDelegate ( T Item ) ;
 
public event DequeueDelegate OnDequeue ;
 
protected virtual void
RaiseDequeue
(
    T Item
)
{
    lock ( this.items )
    {
        if ( this.OnDequeue != null )
        {
            OnDequeue ( Item ) ;
        }
    }
 
    return ;
}

Most code that uses this class should attach a handler to this event, but doing so isn't required; the developer may decide whether or not notification of dequeues, particularly automatic ones, are required.

Constructors

That brings us to the constructors; I'll document only one of them here. This one allows the user to specify the maximum number of items, attach an event handler, and pre-populate the Queue<T> with items:

public LimitedQueue
(
    int                                       MaxItems
,
    DequeueDelegate                           DequeueHandler
,
    System.Collections.Generic.IEnumerable<T> Collection
)
{
    this.items = new System.Collections.Generic.Queue<T> ( Collection ) ;

    if ( DequeueHandler != null )
    {
        this.OnDequeue += DequeueHandler ;
    }

    this.MaxItems = MaxItems ;

    return ;
}

Note that all the members of the Collection are added to the Queue<T> and the event handler is attached before MaxItems is set.

In Conclusion

Sealing classes is rather rude; if the class is worthwhile, someone will likely want to extend it. If you really don't want anyone to derive from your class, mark it sealed or consider whether or not it should be static or a struct. Bear in mind that if someone derives from your class improperly, it's their problem, not yours; don't seal your class simply because you fear someone misusing it.

The only real benefit of sealing classes or having non-virtual methods is that the compiler can make certain optimizations, but my opinion is that any such performance gains are outweighed by allowing others to easily derive from your class.

Framework and library classes should always allow polymorphic inheritance. Even if you don't expect anyone to derive from your class, but there's no reason to keep them from doing so:

• Mark the methods and properties virtual
• Mark fields protected rather than private or provide protected properties that derived classes may use
• Also consider marking the class partial, so other developers who have access to your source code may add to it without changing your files

A derived class may still utilize non-polymorphic inheritance by declaring a method using the new keyword rather than the override keyword.

More on Interfaces

When it comes to defining Interfaces, a good guideline is for an Interface to be very specific and contain very few members.

An example of a bad interface is IList<T>; it bears the description:

"Represents a collection of objects that can be individually accessed by index."

That's all well and good, but it contains members other than the indexer. Queue<T> can't implement IList<T> because IList<T> specifies Add, Remove, and RemoveAt; the standard programming concept of a queue uses the terms Enqueue and Dequeue, and certainly doesn't allow RemoveAt. Microsoft should have defined an IIndexable interface that contains only the indexer; IList<T> and Queue<T> could then both use that interface.

History

• 2008-12-14 First submitted
• 2008-12-20 Renamed Enqueue to ForceEnqueue; added Enqueue, TryEnqueue, and TryDequeue