//+------------------------------------------------------------------+
//|                                              PriorityQueue.mqh   |
//+------------------------------------------------------------------+

#ifndef PRIORITY_QUEUE_MQH
#define PRIORITY_QUEUE_MQH

#include "ThrottledRequest.mqh"

//--- tolerance used when comparing two priority scores for equality;
//--- avoids the fragility of a direct double == double comparison
#define PRIORITY_EPSILON 0.0000001

//+------------------------------------------------------------------+
//| CPriorityQueue                                                   |
//+------------------------------------------------------------------+
class CPriorityQueue
  {
private:
   CThrottledRequest m_items[];          // the backing array, sorted by priority desc
   int               m_count;            // number of items currently in the queue
   int               m_capacity;         // maximum items the queue will hold

   void              InsertSorted(const CThrottledRequest &req);
   bool              PriorityEquals(const double a,const double b) const;

public:
                     CPriorityQueue(void);
                    ~CPriorityQueue(void);

   void              Configure(const int capacity);
   bool              Push(const CThrottledRequest &req);
   bool              Pop(CThrottledRequest &out_req);
   bool              Peek(CThrottledRequest &out_req) const;
   bool              Cancel(const ulong request_id);
   int               Count(void) const { return(m_count); }
   int               Capacity(void) const { return(m_capacity); }
   bool              IsFull(void) const { return(m_count >= m_capacity); }
   bool              IsEmpty(void) const { return(m_count == 0); }
  };

//+------------------------------------------------------------------+
//| Constructor                                                      |
//+------------------------------------------------------------------+
CPriorityQueue::CPriorityQueue(void)
  {
   m_count    = 0;
   m_capacity = 50;
   ::ArrayResize(m_items,m_capacity);
  }

//+------------------------------------------------------------------+
//| Destructor                                                       |
//+------------------------------------------------------------------+
CPriorityQueue::~CPriorityQueue(void)
  {
   ::ArrayFree(m_items);
  }

//+------------------------------------------------------------------+
//| Configure                                                        |
//| Sets the maximum number of requests the queue will hold. Clears  |
//| any existing items. Call from OnInit() before any Push() calls.  |
//+------------------------------------------------------------------+
void CPriorityQueue::Configure(const int capacity)
  {
   m_capacity = (capacity > 0 ? capacity : 50);
   m_count    = 0;
   ::ArrayResize(m_items,m_capacity);
  }

//+------------------------------------------------------------------+
//| PriorityEquals                                                   |
//| Compares two priority scores within a small tolerance rather     |
//| than using a direct == comparison, since priority is a double    |
//| and can accumulate floating-point representation error when the  |
//| caller computes it from an expression rather than a literal.     |
//+------------------------------------------------------------------+
bool CPriorityQueue::PriorityEquals(const double a,const double b) const
  {
   return(::MathAbs(a - b) < PRIORITY_EPSILON);
  }

//+------------------------------------------------------------------+
//| InsertSorted                                                     |
//+------------------------------------------------------------------+
void CPriorityQueue::InsertSorted(const CThrottledRequest &req)
  {
//--- find insertion position: first index where the new item
//--- should appear before the existing item
   int insert_pos = m_count;

   for(int i = 0; i < m_count; i++)
     {
      bool higher_priority = (req.priority > m_items[i].priority &&
                              !PriorityEquals(req.priority,m_items[i].priority));
      bool same_priority_earlier = (PriorityEquals(req.priority,m_items[i].priority) &&
                                    req.enqueue_ms < m_items[i].enqueue_ms);

      if(higher_priority || same_priority_earlier)
        {
         insert_pos = i;
         break;
        }
     }

//--- shift items from insert_pos onwards one position to the right
   for(int i = m_count; i > insert_pos; i--)
      m_items[i] = m_items[i - 1];

   m_items[insert_pos] = req;
   m_count++;
  }

//+------------------------------------------------------------------+
//| Push                                                             |
//+------------------------------------------------------------------+
bool CPriorityQueue::Push(const CThrottledRequest &req)
  {
   if(m_count >= m_capacity)
      return(false);

   InsertSorted(req);
   return(true);
  }

//+------------------------------------------------------------------+
//| Pop                                                              |
//+------------------------------------------------------------------+
bool CPriorityQueue::Pop(CThrottledRequest &out_req)
  {
   if(m_count == 0)
      return(false);

   out_req = m_items[0];

//--- shift remaining items left by one position
   for(int i = 0; i < m_count - 1; i++)
      m_items[i] = m_items[i + 1];

   m_count--;
   return(true);
  }

//+------------------------------------------------------------------+
//| Peek                                                             |
//+------------------------------------------------------------------+
bool CPriorityQueue::Peek(CThrottledRequest &out_req) const
  {
   if(m_count == 0)
      return(false);

   out_req = m_items[0];
   return(true);
  }

//+------------------------------------------------------------------+
//| Cancel                                                           |
//+------------------------------------------------------------------+
bool CPriorityQueue::Cancel(const ulong request_id)
  {
   for(int i = 0; i < m_count; i++)
     {
      if(m_items[i].request_id == request_id)
        {
         //--- shift items after this position left by one
         for(int j = i; j < m_count - 1; j++)
            m_items[j] = m_items[j + 1];

         m_count--;
         return(true);
        }
     }

   return(false);
  }

#endif // PRIORITY_QUEUE_MQH
//+------------------------------------------------------------------+