[Suspected bug] CQueue container class

New comment
 

Hi everyone!

I suspect there is a bug in CQueue::Contains(T item) and CQueue::Remove(T item) methods, at least.

The queue is managed with the classic head-tail circular system, so this code should be incorrect:

//+------------------------------------------------------------------+
//| Removes all values from the CQueue<T>.                           |
//+------------------------------------------------------------------+
template<typename T>
bool CQueue::Contains(T item)
  {
   int count=m_size;
//--- try to find item in array
   while(count-->0)
     {
      //--- use default equality function
      if(::Equals(m_array[count],item))
         return(true);
     }
   return(false);
  }

Also the wrong method description at the top makes me think that there could be made some mistakes when this class was written down..


The Remove method clearly fails when running this simple code for example:

   CQueue<ulong> foo;
   foo.Enqueue(1);
   foo.Remove(1);
   foo.Enqueue(2);
   printf(foo.Contains(2));

It prints "false", when the element is clearly in the queue...


Let me know if this class has been fixed or if I should use one of mine.

Thanks!

  
//+------------------------------------------------------------------+
//| Grows or shrinks the buffer to hold capacity values.             |
//+------------------------------------------------------------------+
template<typename T>
void CQueue::SetCapacity(const int capacity)
  {
   int size=ArraySize(m_array);
//--- create a new array array for temporary storage   
   T new_array[];
   ArrayResize(new_array,capacity);
//--- check size
   if(m_size>0)
     {
      if(m_head<m_tail)
        {
         //--- shift the values to the left
         ArrayCopy(new_array,m_array,0,m_head,m_size);
        }
      else
        {
         //--- shift the values to the left
         ArrayCopy(new_array,m_array,0,m_head,size-m_head);
         //--- shift the values to the right
         ArrayCopy(new_array,m_array,size-m_head,0,m_tail);
        }
     }
//---
   ArrayCopy(m_array,new_array);
//--- set new tail and head
   m_head=0;
   m_tail=(m_size == capacity) ? 0 : m_size;
  }
I found an error also in the SetCapacity() method... since the size is increased but never reduced by calling the ArrayCopy() function, the result is that the capacity of the original array is not the same of the new array one, leading to an incorrect m_tail calculation...
 
Loris De Marchi:

Hi everyone!

I suspect there is a bug in CQueue::Contains(T item) and CQueue::Remove(T item) methods, at least.

The queue is managed with the classic head-tail circular system, so this code should be incorrect:

Also the wrong method description at the top makes me think that there could be made some mistakes when this class was written down..


The Remove method clearly fails when running this simple code for example:

It prints "false", when the element is clearly in the queue...


Let me know if this class has been fixed or if I should use one of mine.

Thanks!

You are right. Reported to Metaquotes (Russian forum).
 
Loris De Marchi #:
I found an error also in the SetCapacity() method... since the size is increased but never reduced by calling the ArrayCopy() function, the result is that the capacity of the original array is not the same of the new array one, leading to an incorrect m_tail calculation...
That one I don't get it. Can you clarify the problem ?
 
Alain Verleyen #:
That one I don't get it. Can you clarify the problem ?

Hi Alain!

Thank you for answering me.

To clarify the issue, let's start from an example.

Create a queue and add an element.

Then call TrimExcess(), that calls SetCapacity().

Suddently, due to that issue, the tail will be equal to the head.

If you add another element it will override the first one then!

I think this happens because the last line of the SetCapacity() method assumes that the two arrays have the same capacity, that is not true:

   m_tail=(m_size == capacity) ? 0 : m_size;

Have a nice day,

Loris

 
Loris De Marchi #:

Hi Alain!

Thank you for answering me.

To clarify the issue, let's start from an example.

Create a queue and add an element.

Then call TrimExcess(), that calls SetCapacity().

Suddently, due to that issue, the tail will be equal to the head.

If you add another element it will override the first one then!

I think this happens because the last line of the SetCapacity() method assumes that the two arrays have the same capacity, that is not true:

Have a nice day,

Loris

You are right.
 

Thank you Alain!

How can I know when the issue will be solved and fix released? Can we track it some way?

Have a nice weekend :)


EDIT: a Dequeue() on an empty queue leads to a size equal to -1... this is embarassing xD

New comment