//----------------------------------------------------------------------------
class Queue
{
public:

   typedef void(FreeObjectFunc_t) ( void* object );
   typedef bool(FindIfCheckFunc_t)( void* object, void *data );
   typedef void(ForEachFunc_t)    ( void* object, void *data );

private:

   struct QueueItem
   {
      QueueItem *prev_, *next_;
      void*      object_;
      QueueItem( QueueItem *prev = NULL, QueueItem *next = NULL, void* object = NULL )
      : prev_( prev ), next_( next ), object_( object )
      { };
   };

   QueueItem        *freeItems_;
   QueueItem        *items_;
   QueueItem        *last_;
   int               count_;
   int               capacityDelta_;
   FreeObjectFunc_t *pFreeObjectFunc_;

   static void FreeQueueItems( QueueItem* *items, FreeObjectFunc_t *pFreeObjectFunc );
   void InnerRemove( QueueItem* item );
   void AddToFree  ( QueueItem* item );
   void FreeItem   ( QueueItem* item );
   void MakeFirst  ( QueueItem* item );

public:
   //---------------------------------------------------------------------------
    Queue( FreeObjectFunc_t *pFreeObjectFunc = NULL, int startCapacity = 16, int capacityDelta = 4 );
   ~Queue();
   //---------------------------------------------------------------------------
   int   Count ();
   bool  Put   ( void* object );
   void* Front ();
   void* Get   ();
   bool  Remove( void* object );
   //---------------------------------------------------------------------------
   bool  Has    ( void* object, bool makeFirst = false );
   void* FindIf ( FindIfCheckFunc_t *pCheckFunc,   void *data, bool makeFirst = false );
   void  ForEach( ForEachFunc_t     *pForEachFunc, void *data = NULL );
   //---------------------------------------------------------------------------
};
//----------------------------------------------------------------------------


//---------------------------------------------------------------------------
Queue::Queue( FreeObjectFunc_t *pFreeObjectFunc, int startCapacity, int capacityDelta )
: freeItems_      ( NULL ),
  items_          ( NULL ),
  last_           ( NULL ),
  count_          ( 0 ),
  capacityDelta_  ( capacityDelta ),
  pFreeObjectFunc_( pFreeObjectFunc )
{
   while( startCapacity-- )
   {
      QueueItem *item;
      try{ item = new QueueItem( NULL, freeItems_, NULL ); }catch(...){ item = NULL; }
      if( ! item  )
         throw -1;
      freeItems_ = item;
   }
}

//---------------------------------------------------------------------------

   void Queue::FreeQueueItems( QueueItem* *items, FreeObjectFunc_t *pFreeObjectFunc )
   {
      while( *items )
      {
         QueueItem *item = *items; *items = item->next_;
         if( pFreeObjectFunc && item->object_ )
            (*pFreeObjectFunc)( item->object_ );
         delete item;
      }
   }

Queue::~Queue()
{
   FreeQueueItems( &items_,     pFreeObjectFunc_ );
   FreeQueueItems( &freeItems_, NULL );
}

//---------------------------------------------------------------------------
int Queue::Count()
{
   return count_;
}
//---------------------------------------------------------------------------
bool Queue::Put( void* object )
{
   QueueItem *item = freeItems_;
   if( item )
      freeItems_ = item->next_;
   else
   {
      try{ item = new QueueItem(); }catch(...){ item = NULL; }
      if( ! item )
         return false;
      if( (capacityDelta_-1) > 0 )
         for( int i = 1; i < capacityDelta_; ++i )
         {
            QueueItem *freeItem;
            try{ freeItem = new QueueItem( NULL, freeItems_, NULL ); }catch(...){ freeItem = NULL; }
            if( ! freeItem )
               break;
            freeItems_ = freeItem;
         }
   }
   *item = QueueItem( last_, NULL, object );
   if( last_ )
      last_->next_ = item;
   else
      items_ = item;
   last_ = item;

   ++count_;

   return true;
}
//---------------------------------------------------------------------------
void* Queue::Front()
{
   return (items_) ? items_->object_ : NULL ;
}


   void Queue::InnerRemove( QueueItem* item )
   {
      if( item->prev_ )
         item->prev_->next_ = item->next_;
      else
         items_ = item->next_;

      if( item->next_ )
         item->next_->prev_ = item->prev_;
      else
         last_ = item->prev_;

      item->next_ = item->prev_ = NULL;
   }

   void Queue::AddToFree( QueueItem* item )
   {
      item->next_ = freeItems_;
      freeItems_ = item;
   }

   void Queue::FreeItem( QueueItem* item )
   {
      InnerRemove( item );
      AddToFree( item );
      --count_;
   }

   void Queue::MakeFirst( QueueItem* item )
   {
      InnerRemove( item );
      item->next_ = items_;
      items_ = item;
   }



//---------------------------------------------------------------------------
void* Queue::Get()
{
   QueueItem *item = items_; if( ! item ) return NULL;
   FreeItem( item );
   return item->object_;
}
//---------------------------------------------------------------------------
bool Queue::Remove( void* object )
{
   bool res;
   QueueItem *item = items_;
   for( ; item && item->object_ != object ; item = item->next_ ) /* !!! */ ;
   if( (res = (item != NULL)) )
      FreeItem( item );
   return res;
}


//---------------------------------------------------------------------------
void* Queue::FindIf( FindIfCheckFunc_t *pCheckFunc, void *data, bool makeFirst )
{
   void* object;
   if( ! pCheckFunc )
      object = NULL;
   else
   {
      QueueItem *item = items_;
      for( ; item && !(*pCheckFunc)( item->object_, data ) ; item = item->next_ ) /* !!! */ ;
      if( ! item )
         object = NULL;
      else
      {
         object = item->object_;
         if( makeFirst && item != items_ )
            MakeFirst( item );
      }
   }
   return object;
}

//---------------------------------------------------------------------------
bool Queue::Has( void* object, bool makeFirst )
{
   QueueItem *item = items_;
   for( ; item && (item->object_ != object) ; item = item->next_ ) /* !!! */ ;
   if( ! item )
      return false;
   if( makeFirst && item != items_ )
      MakeFirst( item );
   return true;
}

//-----------------------------------------------------------------------------
void Queue::ForEach( ForEachFunc_t *pForEachFunc, void *data )
{
   if( pForEachFunc )
   {
      for( QueueItem *item = items_; item ; item = item->next_ )
         (*pForEachFunc)( item->object_, data );
   }
}