15
\$\begingroup\$

Is the implementation clean enough & can be used in production? I tried to write clean & bug-free code. It looks good to me.

I would appreciate any improvement suggestions.

One question I have is, what are the corner cases one might need to consider while implementing a Queue like this that might be part of a 3rd party library?

I am aware of the build-in C# Queue type. In production obviously that's what I would use

using System;

internal class Queue
{
    private System.String[] _container;
    private System.Int32 _topHook = 0;
    private System.Int32 _downHook = 0;

    public Queue(System.Int32 capacity = 5)
    {
        _container = new System.String[capacity];
    }

    public bool IsEmpty() => Count == 0;

    public System.Int32 Count { get { return _topHook - _downHook; } }

    public void Enqueue(System.String item)
    {
        if(Count == _container.Length) ReSize(Count * 2);
        _container[_topHook++] = item;
    }

    public System.String Dequeue()
    {
        if(IsEmpty()) throw new Exception("No Element In Queue");
        if(Count == _container.Length / 4) ReSize(Count * 2);

        var dequeuedValue = _container[_downHook++];

        _container[_downHook - 1] = null;

        return dequeuedValue;
    }

    private void ReSize(System.Int32 capacity)
    {
        System.String[] container = new System.String[capacity];
        var j = 0;

        for(var i = 0; i < _container.Length; i++)
            if(_container[i] != null)
                container[j++] = _container[i];

        _container = container;
        _topHook = Count;//_topHook will point to the NEXT element
        _downHook = 0;
    }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ Why not make it generic? \$\endgroup\$ – Alexander May 26 '17 at 16:42
  • 11
    \$\begingroup\$ You say "it looks good to me", and it has a number of obvious bugs. You need to ask yourself why that is. The problem here is not your simple mistakes; they are natural mistakes. Your "looks good" attitude is your error. Approach the code with deep skepticism; ask yourself on every operation "how do I know this will not fail?" \$\endgroup\$ – Eric Lippert May 26 '17 at 17:54
31
\$\begingroup\$
using System;

If you're going to say using System then don't be putting lots of System.s in the file; the point of this is to eliminate those.


internal class Queue

Is the class intended to be subclassed? If not, seal it. You can always unseal it later if you need to design it for extension.

Why do you not implement IEnumerable<string> ? Surely one of the primary use cases of a collection is enumerating it.

There is nothing in here that is specific to strings; it would be just as easy to write Queue<T>.


private System.String[] _container

Using System.String, System.Int32 and so on is legal, but not idiomatic in C#. Use string, int, and so on.


public Queue(System.Int32 capacity = 5)

What led you to believe that 5 is the correct number here? The maintenance programmer in the future will want to know what the consequences are of changing it to 10 or 1 or a million. Document the things that are not obvious from the code, and avoid "magic numbers".


public bool IsEmpty() => Count == 0;

This could be a property.


    if(Count == _container.Length) ReSize(Count * 2);
    _container[_topHook++] = item;

You might consider making a private property Capacity:

private int Capacity => _container.Length;

And now your code reads better.

if(Count == Capacity) ReSize(Count * 2);

Remember, keep your code in the business domain as much as possible. The length of the container is a mechanism.

Use assertions to document your invariants. That way if you break them, you get informed in your tests:

    Debug.Assert(Count <= Capacity); // precondition of resize
    if(Count == Capacity) 
      ReSize(Count * 2);
    Debug.Assert(Count < Capacity); // postcondition of resize

Do this throughout; any invariant you can think of, document it with an assertion. Like, the count goes up when you enqueue and down when you dequeue, and so on.

Now, of course, this code is still completely wrong.

Suppose the array length is 5, top is 0, bottom is 0. We enqueue four strings, so top is 4, bottom is 0. Now we dequeue. Top is 4, bottom is 1. Now we enqueue. Follow your logic:

  • count is 4 - 1 = 3
  • 3 is not 5, so no resize
  • top increments to 5

Now we enqueue again

  • count is 5 - 1 = 4
  • 4 is not 5, so no resize
  • and we dereference container[5], which is out of bounds.

Do you see your bug here?

The problem is that the condition you are attempting to avoid -- dereferencing out of bounds -- and the condition you are checking -- count vs capacity -- have nothing to do with each other. The code should be:

    Debug.Assert(_topHook <= _container.Length);
    Debug.Assert(Count <= Capacity);
    if (_topHook == _container.Length)
      ReSize(Count * 2);
    Debug.Assert(Count < Capacity);
    Debug.Assert(_topHook < _container.Length);
    _container[_topHook++] = item;

    _container[_topHook++] = item;

I understand that C programmers like this sort of thing. I don't. A line of code should have one effect, and this one has two, and requires that you correctly reason about the ordering of effects. Write the code so that it is crystal clear:

    _container[_topHook] = item;
    _topHook += 1;
    Debug.Assert(_topHook <= _container.Length);
    Debug.Assert(Count <= Capacity);

if(IsEmpty()) throw new Exception("No Element In Queue");  

Don't use Exception as anything but a base class in production code. This could be an invalid operation exception, or make your own exception.


    if(Count == _container.Length / 4) ReSize(Count * 2);

The logic here is correct, but is nowhere documented. The logic is: we wish to maintain two properties, first, that there is never more than a ratio of three to one for wasted space to used space, and second, that there is never a sequence of enqueue-dequeue or dequeue-enqueue operations that both cause an expensive resize. Give a justification here for why and how this logic maintains those invariants.

Consider also: who cares if we are "wasting" in a 4:1 ratio in the case where we have capacity 5 and count 1 ? Resizing the array to size 2 in this case is a waste of time. Consider taking a more sophisticated approach for small queues. Abstract the decision of whether to resize, and by how much, to a helper method that encapsulates that policy.


    var dequeuedValue = _container[_downHook++];
    _container[_downHook - 1] = null;

See what your obsession with putting the ++ in place has cost you? You do work in the decrement, and then you undo that work because you did it too soon! This is hard to reason about and a bug waiting to happen given any modification to this code. If you find you are undoing work you just did, you are doing something wrong; write the code more clearly:

    var dequeuedValue = _container[_downHook];
    _container[_downHook] = null;
    _downHook -= 1;

"Resize" is a word; it's not "re size". So the method should be Resize, not ReSize.


As noted in the other answer the resize logic is wrong. The correct logic is to copy all the elements from downhook to tophook-1 in the original array into 0 to count-1 in the new array.

Never just fix a bug. Ask yourself "how could I have better reasoned about this code so as to avoid the bug?" and "how could I have changed the design of the code so as to avoid the bug?" For example:

Resizing a queue should not be affected in any way by the contents of the queue, and so if you are making a comparison against an element of the queue during a resize, you know immediately that you've done something wrong.

Also, resizing a queue should take as many operations as there are elements in the queue, but you do as many operations as there are in the array. So again, you could have known from first principles that the code was probably wrong.

Finally, this bug would have been never written in the first place had you made a generic Queue<T>, since there is no "null" T to use as a marker. Solving the more general problem is sometimes easier than solving a specific problem, because it forces you to not try to take advantages of specifics, like the nullability of strings.

Develop the ability to reason about these sorts of invariants, and you will find that you will write code that is more likely correct and better performing.

Also, there are already helper methods on Array to help you copy elements from one array to another, and added bonus, they are possibly faster than the code you're writing. Use them.


There's another bug in Resize. Suppose your user says that they expect the capacity to be 1000. Fine; we allocate a thousand items for the array. Then they do 250 enqueues and a dequeue. What happens? The capacity is reset to 500!

The user said that they had an expectation of how much storage they'd need, in order to cut down on the number of resizes on the way there. But you possibly give them a resize on the way to 1000 items.

Keep track of the user's capacity preference, and use that as the minimum array capacity; don't shrink to less than that. They said they're cool with using that much memory, so honour that request.


There is no logic in here that will help with debugging or testing. For example, it would be nice to see something like an implementation of ToString that dumps out a comma-separated list.


EXERCISE: Resizes are expensive; they are an O(n) operation, and so should be done as little as possible. Consider a queue where you enqueue a thousand items, then for the rest of the program you do enqueue-dequeue-enqueue-dequeue-enqueue-dequeue a few million times. How many resizes are there?

Plainly there could be zero resizes because the queue never grows in size beyond 1001 items in this scenario. And yet there are a great many resizes! What can you do to eliminate resizes in this scenario?

\$\endgroup\$
14
\$\begingroup\$

Bug?

The queue destroys itself during a resize because

public void Enqueue(System.String item)
{
    if(Count == _container.Length) ReSize(Count * 2);
    _container[_topHook++] = item;
}

this allows me to enqueue a null string but it gets lost here

for(var i = 0; i < _container.Length; i++)
    if(_container[i] != null)
        container[j++] = _container[i];

where the copy loop won't copy it. So if I had queued ["foo", null, "bar"] a resize would result in ["foo", "bar"].

You either should prevent enquing null or don't change the content.

\$\endgroup\$
  • 1
    \$\begingroup\$ @Pollob I think I don't deserve to the accepted answer (yet?) ;-) There are few more issues that I didn't mention so don't hesitate to accept another answer that will list them all later. \$\endgroup\$ – t3chb0t May 26 '17 at 15:19
  • \$\begingroup\$ I appreciate that. I totally missed the bug (it's pretty evident!) \$\endgroup\$ – Pollob May 26 '17 at 16:04
6
\$\begingroup\$

Some of this has already been said, but there should still be something new here:

Bugs

  • Resizing your queue fails when the capacity is set to 0. You should make sure that Resize always makes (or leaves) enough room for the required number of items.
  • null items are removed after a resize. There is no need to check for null values: you just need to copy everything between the head and the tail, and nothing outside of that.

Problem

  • Your queue cannot be iterated because it does not implement IEnumerable (or IEnumerable<string>). This means you can't use it with foreach, or with Linq methods, or any other code that works with enumerable collections. That significantly limits the use of this queue.

Improvements

  • Your queue constructor does not guard against negative capacities. It 'accidentally' throws an OverflowException with a rather unhelpful 'Arithmetic operation resulted in an overflow.' error message. An ArgumentOutOfRangeException would be more appropriate here.
  • topHook and downHook are rather odd names. Front and rear, or head and tail, appear to be most commonly used. Using familiar terms will make your code easier to read and understand for other programmers.
  • Personally I'm not a fan of putting an if body on the same line. It makes control flow more difficult to see.
  • Why not make your class generic? That allows you to use it for any type. There's nothing string-specific here as far as I can see.
  • Try documenting your public methods, and explaining the rationale behind non-obvious decisions (such as the chosen default capacity, or the growth and shrink behavior). What edge cases should a caller take into account? When a method fails, does it return a specific value or does it throw? If it throws, what kind of exceptions? It may also be useful to describe the characteristics of your queue (useful when someone has to decide between different collection types).
  • As for exceptions, use meaningful exception types rather than Exception. That allows calling code to distinguish between different kinds of problems, and it allows you to provide more detailed error information if necessary. Exception messages are useful for programmers, but terrible for automated exception handling ('stringly typed data').
  • Use meaningful names instead of 'magic values'. For example, growthFactor instead of 2 and shrinkThreshold instead of 4.
\$\endgroup\$
  • \$\begingroup\$ I note that the only situation in which ReSize is called with a zero argument is when the capacity is set to zero in the constructor and the first enqueue happens. It would be smart to make the constructor reject zero as a legal capacity, not just negative numbers. \$\endgroup\$ – Eric Lippert May 26 '17 at 18:21
  • \$\begingroup\$ That would be the easiest way to prevent the problem, yeah. As long as it's documented - just in case a future maintainer introduces another 0-capacity situation. \$\endgroup\$ – Pieter Witvoet May 26 '17 at 18:34
  • 1
    \$\begingroup\$ Oh, absolutely. This code is wrong in a bunch of places and brittle everywhere else. \$\endgroup\$ – Eric Lippert May 26 '17 at 18:36
1
\$\begingroup\$

Unit tests would be a straight forward way to verify the correctness of your code. Given the bugs others have pointed out, I'm assuming you haven't written any? You should (in general), and especially for this kind of code!

\$\endgroup\$

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.