3
\$\begingroup\$

As .Net has no Deque class (Double-Ended Queue) in the Frameworks and I couldn't find an example implementation that I was happy with, I have written the following with the intent that I may post it as a canonical implementation.

First the interface definition:

/// <summary>
///     Standard interface for a Double-Ended Queue (Deque)
/// </summary>
/// <remarks>
///     The first six methods below (PushFront/Back, PopFront/Back and
///   PeekFront/Back) represent the standard deque operations found in 
///   virtually every canonical and official language implementation
///   (see: https://en.wikipedia.org/wiki/Double-ended_queue#Operations)
///   of a DEQUE class.  
///   
///     Unfortunately, there is no standard when it comes to the names of 
///   these operations, so I have chosen to use the names from the C++ Deque
///   class template (https://www.cplusplus.com/reference/deque/deque/),
///   but with standard .Net name styling .
///   
///     The Count and IsEmpty properties are logical additions to these, 
///   and reasonable to add as they have very low overhead in all 
///   implementations.
/// </remarks>
public interface IDeque<T>
{
    /// <summary> Add a new element to the front of the queue. </summary>
    /// <param name="V"> The item to add to the queue</param>
    void PushFront(T V);
    /// <summary> Add a new element to the back of the queue. </summary>
    /// <param name="V"> The item to add to the queue</param>
    void PushBack(T V);

    /// <summary> Removes and returns the element at the front of the queue. </summary>
    /// <exception cref="InvalidOperationException">Thrown if Pop is called when the Deque is empty.</exception>
    T PopFront();
    /// <summary> Removes and returns the element at the back of the queue. </summary>
    /// <exception cref="InvalidOperationException">Thrown if Pop is called when the Deque is empty.</exception>
    T PopBack();

    /// <summary> Returns the element at the front of the queue without removing it. 
    ///     If the Deque is empty, the default for the type "T" is returned. </returns>
    T PeekFront { get; }
    /// <summary> Returns the element at the front of the queue without removing it. 
    ///     If the Deque is empty, the default for the type "T" is returned. </returns>
    T PeekBack { get; }

    /// <summary> Gets the number of elements in the queue. </summary>
    int Count { get; }

    /// <summary> True if there are no elements in the queue, false otherwise. </summary>
    bool IsEmpty { get; }
}

And the class implementation:

/// <summary>
/// Fast implementation of IDeque, using a dynamically resizeable circular buffer (array)
/// </summary>
/// <inheritdoc cref="IDeque{T}"/>
/// <remarks>
///     This implements a Deque (Double-Ended Queue, see 
///   https://en.wikipedia.org/wiki/Double-ended_queue) in what I believe 
///   is the most efficient way (for a .Net managed language).  The obvious 
///   way would be using a doubly-linked list (LinkedList{T}), but these 
///   are variously attested to be slow/inefficient in .Net compared to 
///   the List and Array classes, primarily because of locality and 
///   sequential access issues.
///   
///     The recommended approach is one of several different ways of using
///   arrays:
///         1) Using a dynamic array with resizeable upper and lower bounds. Or 
///         2) Storing contents in a circular buffer, with the Deque as a 
///           windowed range into the buffer.
///           
///     Approach (1) is technically possible using the special Array class, 
///   or more complexly with one or more List objects, but neither of these
///   is as efficient as a language-native typed array and both involve 
///   boxing overhead and null-conversion issues if {T} is a value-type.
///   
///     This left approach (2), which I have never seen implemented for a 
///   Deque in a .Net managed language (C# or VB.net).  I've also never seen 
///   a good type-generic implementation for .Net, which is what prompted 
///   me to write this class.
/// </remarks>
public class Deque<T> : IDeque<T>
{
    #region Constructors
    public Deque(int InitialAllocation = 16)
    {
        size_ = InitialAllocation;
        buffer_ = new T[size_];

        front_ = 0;
        back_ = decrement(front_);

        empty_T = (new T[1])[0];    // Trick to get the default uninitialized
                                    //value for type <T>, without any boxing
                                    //or null-conversion issues.
    }
    #endregion


    #region IDeque Properties
    public T PeekFront { get { return buffer_[front_]; } }
    public T PeekBack { get { return buffer_[back_]; } }

    public int Count { get; protected set; }
    public bool IsEmpty => (Count == 0);
    #endregion


    #region IDeque Methods
    public T PopBack()
    {
        if (IsEmpty)
            throw new InvalidOperationException("Cannot Pop from empty Deque!");

        T val = buffer_[back_];         // save the value
        buffer_[back_] = empty_T;       // erase the cell
        back_ = decrement(back_);       // move the array window
        Count--;                        // adjust the count

        return val;
    }

    public T PopFront()
    {
        if (IsEmpty)
            throw new InvalidOperationException("Cannot Pop from empty Deque!");

        T val = buffer_[front_];        // save the value
        buffer_[front_] = empty_T;      // erase the cell
        front_ = increment(front_);     // move the array window
        Count--;                        // adjust the count

        return val;
    }

    public void PushBack(T V)
    {
        if (IsFull)  expandBuffer();
        back_ = increment(back_);
        buffer_[back_] = V;
        Count++;
    }

    public void PushFront(T V)
    {
        if (IsFull) expandBuffer();
        front_ = decrement(front_);
        buffer_[front_] = V;
        Count++;
    }
    #endregion


    #region Local Properties and Fields
    protected T[] buffer_;  // holds the array window
    protected int size_;    // allocation size of buffer
    protected int back_;    // back is the tail or LEADING end
    protected int front_;   // front is the head or TRAILING end
    protected T empty_T;    // what should be in an uninitialized cell

    protected int RemainingAllocation => size_ - Count;

    /// <summary> True if there are no empty cells left in the buffer, false otherwise. </summary>
    protected bool IsFull => (RemainingAllocation <= 0);
    //protected bool IsFull => ((front_ == back_ + 1) || (front_ == 0 && back_ == size_ - 1));
    #endregion

    #region Buffer Methods (local)
    /// <summary> returns the next cell's index in the circular buffer. </summary>
    protected int increment(int index) => index == size_ - 1 ? 0 : index+1;

    /// <summary> returns the preceding cell's index in the circular buffer. </summary>
    protected int decrement(int index) => index == 0 ? size_ - 1 : index-1;

    /// <summary>
    ///     Double the size of the current buffer, without losing any contents
    /// </summary>
    /// <remarks>
    ///     Makes a new buffer twice a large as the current one.  Then copies
    ///   the contents of the old buffer to the new one, then makes the new
    ///   buffer the current ("buffer_").
    /// </remarks>
    void expandBuffer()
    {
        // allocate the new buffer
        int newSize = size_ * 2;
        T[] newBuf = new T[newSize];

        // copy the data over
        if (!IsEmpty)
        {
            //  if the pointers are in-order, then all contents can
            // be copied to the same indexes in the new buffer
            if (front_ <= back_)
            {
                for (int i = front_; i <= back_; i++)
                {
                    newBuf[i] = buffer_[i];
                }
            }

            //  The contents are wrapped-around the circular buffer so
            // reposition the back (wrapped-around) contents to after
            // the front contents.
            else 
            {
                //  The front cells can be copied to the same indexes in the
                // new buffer.
                for (int i = front_; i < size_; i++)
                {
                    newBuf[i] = buffer_[i];
                }
                //  The back cells are wrapped-around, so reposition them to
                // follow immediately after the front cells.
                for (int i = 0; i <= back_; i++)
                {
                    newBuf[i + size_] = buffer_[i];
                }
            }

        }

        // reposition the back_ pointer so it's not wrapped-around
        if (back_ < front_) back_ += size_;

        // save the new buffer 
        buffer_ = newBuf;
        size_ = newSize;
    }
    #endregion
}

I would appreciate any feedback or reviews on how to improve this code, with an eye towards my possibly posting in StackOverflow as a canonical solution.

\$\endgroup\$
0
5
\$\begingroup\$

First of all congratulation. It seems like a neat solution (I haven't played with it, I've just read it)

  • The public API is using consistent naming
  • The public methods are well documented
  • The public methods implementation are short and concise

Now let's talk about the improvement areas

Naming

  • In C# we normally use camel Casing for parameter names. But if you prefer Pascal Casing it is really up to you but please be consistent:
public Deque(int InitialAllocation = 16)
protected int increment(int index)
  • In C# we normally use Pascal Casing for method names. Yet again, please try be consistent in naming:
public T PopBack()
protected int decrement(int index)
  • In C# we normally use camel Casing for non-public member names. Please try be consistent:
protected T empty_T;   
protected int RemainingAllocation => size_ - Count;
  • Quite frankly I don't understand how do you determine when to use an underscore as suffix and when don't
protected int front_;
protected T empty_T; 

So in general:

  • Use Pascal Casing for all class members except the private fields
  • Use camel Casing for local variables and method parameters, as well as private fields
    • Some people prefer to prefix private fields with an underscore _

Expand Buffer

  • I would recommend to consider to use ArrayPool to rent and return arrays for a specify size rather than manually allocate them when needed
  • newBuf: As I can see this is the only place in your code where you have used abbreviation. I assume it was just a typo and you wanted to write newBuffer

Abusing the #region

  • If you really want to separate things from each other then I would recommend to use partial classes
  • A typical separation is that you have a file where there are only the public members and you have another one where you have all non-public ones
    • Deque.cs
    • Deque.nonpublic.cs or Deque.impl.cs

UPDATE #1: Reflect to OP's questions

Are you saying that the protected members would be styled the same as the public members? My habit has been to use PascalCase for all public members and camelCase for all local and protected members.

If you look at the MSDN documentation regarding C# Coding conventions then you can find the following paragraph:

any of the guidance pertaining to elements marked public is also applicable when working with protected and protected internal elements, all of which are intended to be visible to external callers

As always it is just a guidance and you can freely take a different path. But if you want to make this code open source for example then most of the developers will be familiar with the above naming convention.

If you don't want to make it publicly available then you should follow your organization standards. There might be a group of static code analyzer rules that dictates the naming, indentation and other code formatting policies.

I think that we have a philosophical difference on the use of Regions vs Partial classes, but I am happy to remove the #reqion markers for public posting as I know that many (most?) programmers dislike them.

Even though most of the time partial classes are used for generated code there are other uses cases as well. We have used them heavily during unit testing. With that the helper methods for initializations, assertions were separated from the test cases.

We have also found regions can be really villainous / scurvy. When you collapse the regions you do not realize how big is your class. By separating your class into multiple files it can help you later on to do proper separation, whereas region has different intent.

But yet again it is up to you how to separate your code.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Thanks for the comments, I appreciate them and I do have a question. Are you saying that the protected members would be styled the same as the public members? My habit has been to use PascalCase for all public members and camelCase for all local and protected members. I will look into ArrayPool. I think that we have a philosophical difference on the use of Regions vs Partial classes, but I am happy to remove the #reqion markers for public posting as I know that many (most?) programmers dislike them. Other than that, I take all of your points and will correct them. Thanks again. \$\endgroup\$ Dec 17 '21 at 14:02
  • 1
    \$\begingroup\$ @RBarryYoung I've reflected to your questions / concerns in my post, please check them. \$\endgroup\$ Dec 17 '21 at 15:54
  • \$\begingroup\$ Thanks for the update, I was not aware of that treatment of protected members in the style guide. \$\endgroup\$ Dec 17 '21 at 16:38
  • 1
    \$\begingroup\$ @RBarryYoung If you think about it then it does make sense, since from inheritance perspective they are part of your API. If you make your class sealed then all protected members should become private and you are suggested to use camel casing there. \$\endgroup\$ Dec 17 '21 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.