Click here to Skip to main content
Click here to Skip to main content
Go to top

LimitedQueue

, 23 Dec 2008
Rate this:
Please Sign up or sign in to vote.
Wrapping a built-in type when deriving is not a suitable solution, and why

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 relevent 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 developer 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

PIEBALDconsult
Software Developer (Senior)
United States United States
BSCS 1992 Wentworth Institute of Technology
 
Originally from the Boston (MA) area. Lived in SoCal for a while. Now in the Phoenix (AZ) area.
 
OpenVMS enthusiast, ISO 8601 evangelist, photographer, opinionated SOB
 
---------------
 
"If you need help knowing what to think, let me know and I'll tell you." -- Jeffrey Snover [MSFT]
 
"Typing is no substitute for thinking." -- R.W. Hamming
 
"I find it appalling that you can become a programmer with less training than it takes to become a plumber." -- Bjarne Stroustrup
 
ZagNut’s Law: Arrogance is inversely proportional to ability.
 
"Well blow me sideways with a plastic marionette. I've just learned something new - and if I could award you a 100 for that post I would. Way to go you keyboard lovegod you." -- Pete O'Hanlon
 
"linq'ish" sounds like "inept" in German -- Andreas Gieriet
 
"Things would be different if I ran the zoo." -- Dr. Seuss
 
"Wrong is evil, and it must be defeated." – Jeff Ello
 
"A good designer must rely on experience, on precise, logical thinking, and on pedantic exactness." -- Nigel Shaw
 
“It’s always easier to do it the hard way.” -- Blackhart

“If Unix wasn’t so bad that you can’t give it away, Bill Gates would never have succeeded in selling Windows.” -- Blackhart

"Omit needless local variables." -- Strunk... had he taught programming
 

 
"We learn more from our mistakes than we do from getting it right the first time."
 
My first rule of debugging: "If you get a different error message, you're making progress."
 
My golden rule of database management: "Do not unto others' databases as you would not have done unto yours."
 
My general rule of software development: "Design should be top-down, but implementation should be bottom-up."

Comments and Discussions

 
GeneralWhy don't you override... PinmemberMcMarc8-Jan-09 2:25 
GeneralRe: Why don't you override... PinmemberPIEBALDconsult8-Jan-09 4:22 
GeneralRe: Why don't you override... PinmemberMcMarc8-Jan-09 20:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 23 Dec 2008
Article Copyright 2008 by PIEBALDconsult
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid