Queue.h

/* This file is Copyright 2000-2008 Meyer Sound Laboratories Inc.  See the included LICENSE.txt file for details. */

#ifndef MuscleQueue_h
#define MuscleQueue_h

#include "support/MuscleSupport.h"

BEGIN_NAMESPACE(muscle);

#ifndef SMALL_QUEUE_SIZE
# define SMALL_QUEUE_SIZE 3
#endif

template <class ItemType> class Queue
{
public:
   Queue();

   explicit Queue(uint32 initialSlots);

   Queue(const Queue& copyMe);

   virtual ~Queue();

   Queue &operator=(const Queue &from);

   bool operator==(const Queue &rhs) const;

   bool operator!=(const Queue &rhs) const {return !(*this == rhs);}

   status_t CopyFrom(const Queue<ItemType> & rhs);

   status_t AddTail(const ItemType & item = ItemType());

   status_t AddTail(const Queue<ItemType> & queue, uint32 startIndex = 0, uint32 numItems = MUSCLE_NO_LIMIT);

   status_t AddTail(const ItemType * items, uint32 numItems);

   status_t AddHead(const ItemType &item = ItemType());

   status_t AddHead(const Queue<ItemType> & queue, uint32 startIndex = 0, uint32 numItems = MUSCLE_NO_LIMIT);

   status_t AddHead(const ItemType * items, uint32 numItems);

   status_t RemoveHead();

   status_t RemoveHead(ItemType & returnItem);

   status_t RemoveTail();

   status_t RemoveTail(ItemType & returnItem);

   status_t RemoveItemAt(uint32 index);

   status_t RemoveItemAt(uint32 index, ItemType & returnItem);

   status_t GetItemAt(uint32 index, ItemType & returnItem) const;

   ItemType * GetItemAt(uint32 index) const;

   status_t ReplaceItemAt(uint32 index, const ItemType & newItem = ItemType());
 
   status_t InsertItemAt(uint32 index, const ItemType & newItem = ItemType());
   
   status_t InsertItemsAt(uint32 index, const Queue<ItemType> & queue, uint32 startIndex = 0, uint32 numNewItems = MUSCLE_NO_LIMIT);

   status_t InsertItemsAt(uint32 index, const ItemType * items, uint32 numNewItems);

   void Clear(bool releaseCachedBuffers = false);

   uint32 GetNumItems() const {return _itemCount;}

   uint32 GetNumAllocatedItemSlots() const {return _queueSize;}

   bool IsEmpty() const {return (_itemCount == 0);}

   bool HasItems() const {return (_itemCount > 0);}

   const ItemType & Head() const {return *GetItemAt(0);}

   const ItemType & Tail() const {return *GetItemAt(_itemCount-1);}

   ItemType & Head() {return *GetItemAt(0);}

   ItemType & Tail() {return *GetItemAt(_itemCount-1);}

   ItemType * HeadPointer() const {return (_itemCount > 0) ? GetItemAt(0) : NULL;}

   ItemType * TailPointer() const {return (_itemCount > 0) ? GetItemAt(_itemCount-1) : NULL;}

   const ItemType & operator [](uint32 Index) const; 

   ItemType & operator [](uint32 Index);

   ItemType * GetItemPointer(uint32 index) const {return GetItemAt(index);}

   status_t EnsureSize(uint32 numSlots, bool setNumItems = false, uint32 extraReallocItems = 0);

   int32 IndexOf(const ItemType & item) const;

   void Swap(uint32 fromIndex, uint32 toIndex);

   void ReverseItemOrdering(uint32 from=0, uint32 to = MUSCLE_NO_LIMIT); 

   typedef int (*ItemCompareFunc)(const ItemType & item1, const ItemType & item2, void * cookie);

   void Sort(ItemCompareFunc compareFunc, uint32 from=0, uint32 to = MUSCLE_NO_LIMIT, void * optCookie = NULL);

   void SwapContents(Queue<ItemType> & that);

   uint32 RemoveAllInstancesOf(const ItemType & val);

   status_t RemoveFirstInstanceOf(const ItemType & val);

   status_t RemoveLastInstanceOf(const ItemType & val);

   bool StartsWith(const ItemType & prefix) const {return ((HasItems())&&(Head() == prefix));}

   bool StartsWith(const Queue<ItemType> & prefixQueue) const;

   bool EndsWith(const ItemType & suffix) const {return ((HasItems())&&(Tail() == suffix));}

   bool EndsWith(const Queue<ItemType> & suffixQueue) const;

   ItemType * GetArrayPointer(uint32 whichArray, uint32 & retLength) {return const_cast<ItemType *>(GetArrayPointerAux(whichArray, retLength));} 

   const ItemType * GetArrayPointer(uint32 whichArray, uint32 & retLength) const {return GetArrayPointerAux(whichArray, retLength);}

   void Normalize();

private:
   const ItemType * GetArrayPointerAux(uint32 whichArray, uint32 & retLength) const;
   void SwapContentsAux(Queue<ItemType> & that);

   inline uint32 NextIndex(uint32 idx) const {return (idx >= _queueSize-1) ? 0 : idx+1;}
   inline uint32 PrevIndex(uint32 idx) const {return (idx == 0) ? _queueSize-1 : idx-1;}

   // Translates a user-index into an index into the _queue array.
   inline uint32 InternalizeIndex(uint32 idx) const {return (_headIndex + idx) % _queueSize;}

   // Helper methods, used for sorting (stolen from http://www-ihm.lri.fr/~thomas/VisuTri/inplacestablesort.html)
   void Merge(ItemCompareFunc compareFunc, uint32 from, uint32 pivot, uint32 to, uint32 len1, uint32 len2, void * cookie);
   uint32 Lower(ItemCompareFunc compareFunc, uint32 from, uint32 to, const ItemType & val, void * cookie) const;
   uint32 Upper(ItemCompareFunc compareFunc, uint32 from, uint32 to, const ItemType & val, void * cookie) const;

   ItemType _smallQueue[SMALL_QUEUE_SIZE];  // small queues can be stored inline in this array
   ItemType * _queue;                       // points to _smallQueue, or to a dynamically alloc'd array
   uint32 _queueSize;  // number of slots in the _queue array
   uint32 _itemCount;  // number of valid items in the array
   uint32 _headIndex;  // index of the first filled slot (meaningless if _itemCount is zero)
   uint32 _tailIndex;  // index of the last filled slot (meaningless if _itemCount is zero)
   const uint32 _initialSize;  // as specified in ctor
};

template <class ItemType>
Queue<ItemType>::Queue()
   : _queue(NULL), _queueSize(0), _itemCount(0), _initialSize(SMALL_QUEUE_SIZE)
{
   // empty
}

template <class ItemType>
Queue<ItemType>::Queue(uint32 initialSize)
   : _queue(NULL), _queueSize(0), _itemCount(0), _initialSize(initialSize)
{
   // empty
}

template <class ItemType>
Queue<ItemType>::Queue(const Queue& rhs)
   : _queue(NULL), _queueSize(0), _itemCount(0), _initialSize(rhs._initialSize)
{
   *this = rhs;
}

template <class ItemType>
bool
Queue<ItemType>::operator ==(const Queue& rhs) const
{
   if (this == &rhs) return true;
   if (GetNumItems() != rhs.GetNumItems()) return false;

   for (int i = GetNumItems()-1; i>=0; i--) if (((*this)[i] == rhs[i]) == false) return false;

   return true;
}

template <class ItemType>
Queue<ItemType> &
Queue<ItemType>::operator =(const Queue& rhs)
{
   if (this != &rhs)
   {
      uint32 numItems = rhs.GetNumItems();
      if (EnsureSize(numItems, true) == B_NO_ERROR) for (uint32 i=0; i<numItems; i++) (*this)[i] = rhs[i];
   }
   return *this;
}

template <class ItemType>
status_t 
Queue<ItemType>::CopyFrom(const Queue & rhs)
{
   if (this == &rhs) return B_NO_ERROR;

   uint32 numItems = rhs.GetNumItems();
   if (EnsureSize(numItems, true) == B_NO_ERROR)
   {
      for (uint32 i=0; i<numItems; i++) (*this)[i] = rhs[i];
      return B_NO_ERROR;
   }
   return B_ERROR;
}

template <class ItemType>
ItemType &
Queue<ItemType>::operator[](uint32 i)
{
   MASSERT(i<_itemCount, "Invalid index to Queue::[]");
   return _queue[InternalizeIndex(i)];
}

template <class ItemType>
const ItemType &
Queue<ItemType>::operator[](uint32 i) const
{
   MASSERT(i<_itemCount, "Invalid index to Queue::[]");
   return _queue[InternalizeIndex(i)];
}             

template <class ItemType>
ItemType * 
Queue<ItemType>::GetItemAt(uint32 i) const
{
   return &_queue[InternalizeIndex(i)];
}

template <class ItemType>
Queue<ItemType>::~Queue()
{
   if (_queue != _smallQueue) delete [] _queue;
}

template <class ItemType>
status_t 
Queue<ItemType>::
AddTail(const ItemType &item)
{
   if (EnsureSize(_itemCount+1, false, _itemCount+1) == B_ERROR) return B_ERROR;
   if (_itemCount == 0) _headIndex = _tailIndex = 0;
                   else _tailIndex = NextIndex(_tailIndex);
   _queue[_tailIndex] = item;
   _itemCount++;
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
AddTail(const Queue<ItemType> &queue, uint32 startIndex, uint32 numNewItems)
{
   uint32 hisSize = queue.GetNumItems();
   numNewItems = muscleMin(numNewItems, (startIndex < hisSize) ? (hisSize-startIndex) : 0);
   
   uint32 mySize = GetNumItems();
   uint32 newSize = mySize+numNewItems;

   if (EnsureSize(newSize, true) != B_NO_ERROR) return B_ERROR;
   for (uint32 i=mySize; i<newSize; i++) (*this)[i] = queue[startIndex++];
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
AddTail(const ItemType * items, uint32 numItems)
{
   uint32 mySize = GetNumItems();
   uint32 newSize = mySize+numItems;
   uint32 rhs = 0;

   if (EnsureSize(newSize, true) != B_NO_ERROR) return B_ERROR;
   for (uint32 i=mySize; i<newSize; i++) (*this)[i] = items[rhs++];
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
AddHead(const ItemType &item)
{
   if (EnsureSize(_itemCount+1, false, _itemCount+1) == B_ERROR) return B_ERROR;
   if (_itemCount == 0) _headIndex = _tailIndex = 0;
                   else _headIndex = PrevIndex(_headIndex);
   _queue[_headIndex] = item;
   _itemCount++;
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
AddHead(const Queue<ItemType> &queue, uint32 startIndex, uint32 numNewItems)
{
   uint32 hisSize = queue.GetNumItems();
   numNewItems = muscleMin(numNewItems, (startIndex < hisSize) ? (hisSize-startIndex) : 0);

   if (EnsureSize(numNewItems+GetNumItems()) != B_NO_ERROR) return B_ERROR;
   for (int i=((int)startIndex+numNewItems)-1; i>=(int32)startIndex; i--) if (AddHead(queue[i]) == B_ERROR) return B_ERROR;
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
AddHead(const ItemType * items, uint32 numItems)
{
   if (EnsureSize(_itemCount+numItems) != B_NO_ERROR) return B_ERROR;
   for (int i=((int)numItems)-1; i>=0; i--) if (AddHead(items[i]) == B_ERROR) return B_ERROR;
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveHead(ItemType & returnItem)
{
   if (_itemCount == 0) return B_ERROR;
   returnItem = _queue[_headIndex];
   return RemoveHead();
}

template <class ItemType>
status_t
Queue<ItemType>::
RemoveHead()
{
   if (_itemCount == 0) return B_ERROR;
   int oldHeadIndex = _headIndex;
   _headIndex = NextIndex(_headIndex);
   _itemCount--;
   _queue[oldHeadIndex] = ItemType();  // this must be done last, as queue state must be coherent when we do this
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveTail(ItemType & returnItem)
{
   if (_itemCount == 0) return B_ERROR;
   returnItem = _queue[_tailIndex];
   return RemoveTail();
}

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveTail()
{
   if (_itemCount == 0) return B_ERROR;
   int removedItemIndex = _tailIndex;
   _tailIndex = PrevIndex(_tailIndex);
   _itemCount--;
   _queue[removedItemIndex] = ItemType();  // this must be done last, as queue state must be coherent when we do this
   return B_NO_ERROR;
}

template <class ItemType>
status_t
Queue<ItemType>::
GetItemAt(uint32 index, ItemType & returnItem) const
{
   if (index >= _itemCount) return B_ERROR;
   returnItem = _queue[InternalizeIndex(index)];
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveItemAt(uint32 index, ItemType & returnItem)
{
   if (index >= _itemCount) return B_ERROR;
   returnItem = _queue[InternalizeIndex(index)];
   return RemoveItemAt(index);
}

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveItemAt(uint32 index)
{
   if (index >= _itemCount) return B_ERROR;

   uint32 internalizedIndex = InternalizeIndex(index);
   uint32 indexToClear;

   if (index < _itemCount/2)
   {
      // item is closer to the head:  shift everything forward one, ending at the head
      while(internalizedIndex != _headIndex)
      {
         uint32 prev = PrevIndex(internalizedIndex);
         _queue[internalizedIndex] = _queue[prev];
         internalizedIndex = prev;
      }
      indexToClear = _headIndex;
      _headIndex = NextIndex(_headIndex); 
   }
   else
   {
      // item is closer to the tail:  shift everything back one, ending at the tail
      while(internalizedIndex != _tailIndex)
      {
         uint32 next = NextIndex(internalizedIndex);
         _queue[internalizedIndex] = _queue[next];
         internalizedIndex = next;
      }
      indexToClear = _tailIndex;
      _tailIndex = PrevIndex(_tailIndex); 
   }

   _itemCount--;
   _queue[indexToClear] = ItemType();  // this must be done last, as queue state must be coherent when we do this
   return B_NO_ERROR; 
}

template <class ItemType>
status_t 
Queue<ItemType>::
ReplaceItemAt(uint32 index, const ItemType & newItem)
{
   if (index >= _itemCount) return B_ERROR;
   _queue[InternalizeIndex(index)] = newItem;
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
InsertItemAt(uint32 index, const ItemType & newItem)
{
   // Simple cases
   if (index >  _itemCount) return B_ERROR;
   if (index == _itemCount) return AddTail(newItem);
   if (index == 0)          return AddHead(newItem);

   // Harder case:  inserting into the middle of the array
   if (index < _itemCount/2)
   {
      // Add a space at the front, and shift things back
      if (AddHead() != B_NO_ERROR) return B_ERROR;  // allocate an extra slot
      for (uint32 i=0; i<index; i++) ReplaceItemAt(i, *GetItemAt(i+1));
   }
   else
   {
      // Add a space at the rear, and shift things forward
      if (AddTail() != B_NO_ERROR) return B_ERROR;  // allocate an extra slot
      for (int32 i=((int32)_itemCount)-1; i>((int32)index); i--) ReplaceItemAt(i, *GetItemAt(i-1));
   }
   return ReplaceItemAt(index, newItem);
}

template <class ItemType>
status_t 
Queue<ItemType>::
InsertItemsAt(uint32 index, const Queue<ItemType> & queue, uint32 startIndex, uint32 numNewItems)
{
   uint32 hisSize = queue.GetNumItems();
   numNewItems = muscleMin(numNewItems, (startIndex < hisSize) ? (hisSize-startIndex) : 0);
   if (numNewItems == 0) return B_NO_ERROR;
   if (index > _itemCount) return B_ERROR;
   if (numNewItems == 1)
   {
      if (index == 0)          return AddHead(queue.Head());
      if (index == _itemCount) return AddTail(queue.Head());
   }

   uint32 oldSize = GetNumItems();
   uint32 newSize = oldSize+numNewItems;

   if (EnsureSize(newSize, true) != B_NO_ERROR) return B_ERROR;
   for (uint32 i=index; i<oldSize; i++)           (*this)[i+numNewItems] = (*this)[i];
   for (uint32 i=index; i<index+numNewItems; i++) (*this)[i]             = queue[startIndex++];
   return B_NO_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
InsertItemsAt(uint32 index, const ItemType * items, uint32 numNewItems)
{
   if (numNewItems == 0) return B_NO_ERROR;
   if (index > _itemCount) return B_ERROR;
   if (numNewItems == 1)
   {
      if (index == 0)          return AddHead(*items);
      if (index == _itemCount) return AddTail(*items);
   }

   uint32 oldSize = GetNumItems();
   uint32 newSize = oldSize+numNewItems;

   if (EnsureSize(newSize, true) != B_NO_ERROR) return B_ERROR;
   int32 si = 0;
   for (uint32 i=index; i<oldSize; i++)           (*this)[i+numNewItems] = (*this)[i];
   for (uint32 i=index; i<index+numNewItems; i++) (*this)[i]             = items[si++];
   return B_NO_ERROR;
}

template <class ItemType>
void 
Queue<ItemType>::
Clear(bool releaseCachedBuffers)
{
   if ((releaseCachedBuffers)&&(_queue != _smallQueue))
   {
      delete [] _queue;
      _queue = NULL;
      _queueSize = 0;
      _itemCount = 0;
   }
   else while(RemoveTail() == B_NO_ERROR) {/* empty */}
}

template <class ItemType>
status_t 
Queue<ItemType>::
EnsureSize(uint32 size, bool setNumItems, uint32 extraPreallocs)
{
   if ((_queue == NULL)||(_queueSize < size))
   {
      const uint32 sqLen = ARRAYITEMS(_smallQueue);
      uint32 temp    = size + extraPreallocs;
      uint32 newQLen = muscleMax(_initialSize, ((setNumItems)||(temp <= sqLen)) ? muscleMax(sqLen,temp) : temp);

      ItemType * newQueue = ((_queue == _smallQueue)||(newQLen > sqLen)) ? newnothrow_array(ItemType,newQLen) : _smallQueue;
      if (newQueue == NULL) {WARN_OUT_OF_MEMORY; return B_ERROR;}
      if (newQueue == _smallQueue) newQLen = sqLen;
      
      for (uint32 i=0; i<_itemCount; i++) (void) GetItemAt(i, newQueue[i]);  // we know that (_itemCount < size)
      if (setNumItems) _itemCount = size;
      _headIndex = 0;
      _tailIndex = _itemCount-1;

      if (_queue == _smallQueue) 
      {
         ItemType blank = ItemType();
         for (uint32 i=0; i<sqLen; i++) _smallQueue[i] = blank;
      }
      else delete [] _queue;

      _queue = newQueue;
      _queueSize = newQLen;
   }

   if (setNumItems) 
   {
      // Force ourselves to contain exactly the required number of items
      if (_itemCount < size)
      {
         // We can do this quickly because the "new" items are already initialized properly
         _tailIndex = (_tailIndex + (size-_itemCount)) % _queueSize;
         _itemCount = size;
      }
      else while(_itemCount > size) (void) RemoveTail();  // Gotta overwrite the "removed" items, so this is a bit slower
   }

   return B_NO_ERROR;
}

template <class ItemType>
int32 
Queue<ItemType>::
IndexOf(const ItemType & item) const
{
   if (_queue) for (int i=((int)GetNumItems())-1; i>=0; i--) if (*GetItemAt(i) == item) return i;
   return -1;
}


template <class ItemType>
void 
Queue<ItemType>::
Swap(uint32 fromIndex, uint32 toIndex) 
{
   ItemType temp = *(GetItemAt(fromIndex));
   ReplaceItemAt(fromIndex, *(GetItemAt(toIndex)));
   ReplaceItemAt(toIndex,   temp);
}

template <class ItemType>
void 
Queue<ItemType>::
Sort(ItemCompareFunc compareFunc, uint32 from, uint32 to, void * cookie) 
{ 
   uint32 size = GetNumItems();
   if (to > size) to = size;
   if (to > from)
   {
      if (to < from+12) 
      {
         // too easy, just do a bubble sort (base case)
         if (to > from+1) 
         {
            for (uint32 i=from+1; i<to; i++) 
            {
               for (uint32 j=i; j>from; j--) 
               {
                  int ret = compareFunc(*(GetItemAt(j)), *(GetItemAt(j-1)), cookie);
                  if (ret < 0) Swap(j, j-1); 
                          else break; 
               }
            } 
         } 
      }
      else
      {
         // Okay, do the real thing
         uint32 middle = (from + to)/2; 
         Sort(compareFunc, from, middle, cookie); 
         Sort(compareFunc, middle, to, cookie); 
         Merge(compareFunc, from, middle, to, middle-from, to-middle, cookie); 
      }
   }
}

template <class ItemType>
void 
Queue<ItemType>::
ReverseItemOrdering(uint32 from, uint32 to) 
{
   uint32 size = GetNumItems();
   if (size > 0)
   {
      to--;  // make it inclusive
      if (to >= size) to = size-1;
      while (from < to) Swap(from++, to--); 
   }
} 

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveFirstInstanceOf(const ItemType & val) 
{
   uint32 ni = GetNumItems();
   for (uint32 i=0; i<ni; i++) if ((*this)[i] == val) return RemoveItemAt(i);
   return B_ERROR;
}

template <class ItemType>
status_t 
Queue<ItemType>::
RemoveLastInstanceOf(const ItemType & val) 
{
   for (int32 i=((int32)GetNumItems())-1; i>=0; i--) if ((*this)[i] == val) return RemoveItemAt(i);
   return B_ERROR;
}

template <class ItemType>
uint32 
Queue<ItemType>::
RemoveAllInstancesOf(const ItemType & val) 
{
   // Efficiently collapse all non-matching slots up to the top of the list
   uint32 ret      = 0;
   uint32 writeTo  = 0;
   uint32 origSize = GetNumItems();
   for(uint32 readFrom=0; readFrom<origSize; readFrom++)
   {
      const ItemType & nextRead = (*this)[readFrom];
      if (nextRead == val) ret++;
      else 
      {
         if (readFrom > writeTo) (*this)[writeTo] = nextRead;
         writeTo++;
      }
   }

   // Now get rid of any now-surplus slots
   for (; writeTo<origSize; writeTo++) RemoveTail();

   return ret;
}

template <class ItemType>
void 
Queue<ItemType>::
Merge(ItemCompareFunc compareFunc, uint32 from, uint32 pivot, uint32 to, uint32 len1, uint32 len2, void * cookie) 
{
   if ((len1)&&(len2))
   {
      if (len1+len2 == 2) 
      { 
         if (compareFunc(*(GetItemAt(pivot)), *(GetItemAt(from)), cookie) < 0) Swap(pivot, from); 
      } 
      else
      {
         uint32 first_cut, second_cut; 
         uint32 len11, len22; 
         if (len1 > len2) 
         { 
            len11      = len1/2; 
            first_cut  = from + len11; 
            second_cut = Lower(compareFunc, pivot, to, *GetItemAt(first_cut), cookie); 
            len22      = second_cut - pivot; 
         } 
         else 
         { 
            len22      = len2/2; 
            second_cut = pivot + len22; 
            first_cut  = Upper(compareFunc, from, pivot, *GetItemAt(second_cut), cookie); 
            len11      = first_cut - from; 
         } 

         // do a rotation
         if ((pivot!=first_cut)&&(pivot!=second_cut)) 
         {
            // find the greatest common denominator of (pivot-first_cut) and (second_cut-first_cut)
            uint32 n = pivot-first_cut;
            {
               uint32 m = second_cut-first_cut;
               while(n!=0) 
               {
                  uint32 t = m % n; 
                  m=n; 
                  n=t;
               } 
               n = m;
            }

            while(n--) 
            {
               const ItemType val = *GetItemAt(first_cut+n); 
               uint32 shift = pivot - first_cut; 
               uint32 p1 = first_cut+n;
               uint32 p2 = p1+shift; 
               while (p2 != first_cut + n) 
               { 
                  ReplaceItemAt(p1, *GetItemAt(p2));
                  p1 = p2; 
                  if (second_cut - p2 > shift) p2 += shift; 
                                          else p2  = first_cut + (shift - (second_cut - p2)); 
               } 
               ReplaceItemAt(p1, val);
            }
         }

         uint32 new_mid = first_cut+len22; 
         Merge(compareFunc, from,    first_cut,  new_mid, len11,        len22,        cookie); 
         Merge(compareFunc, new_mid, second_cut, to,      len1 - len11, len2 - len22, cookie); 
      }
   }
}


template <class ItemType>
uint32 
Queue<ItemType>::
Lower(ItemCompareFunc compareFunc, uint32 from, uint32 to, const ItemType & val, void * cookie) const
{
   if (to > from)
   {
      uint32 len = to - from;
      while (len > 0) 
      {
         uint32 half = len/2; 
         uint32 mid  = from + half; 
         if (compareFunc(*(GetItemAt(mid)), val, cookie) < 0) 
         {
            from = mid+1; 
            len  = len - half - 1; 
         } 
         else len = half; 
      }
   }
   return from; 
} 

template <class ItemType>
uint32 
Queue<ItemType>::
Upper(ItemCompareFunc compareFunc, uint32 from, uint32 to, const ItemType & val, void * cookie) const 
{
   if (to > from)
   {
      uint32 len = to - from;
      while (len > 0) 
      { 
         uint32 half = len/2; 
         uint32 mid  = from + half; 
         if (compareFunc(val, *(GetItemAt(mid)), cookie) < 0) len = half; 
         else 
         {
            from = mid+1; 
            len  = len - half -1; 
         } 
      } 
   }
   return from; 
}

template <class ItemType>
const ItemType * 
Queue<ItemType> :: GetArrayPointerAux(uint32 whichArray, uint32 & retLength) const
{
   if (_itemCount > 0)
   {
      switch(whichArray)
      {
         case 0:  
            retLength = (_headIndex <= _tailIndex) ? (_tailIndex-_headIndex)+1 : (_queueSize-_headIndex);
            return &_queue[_headIndex];
         break;

         case 1:
            if (_headIndex > _tailIndex)
            {
               retLength = _tailIndex+1;
               return &_queue[0];
            }
         break;
      }
   }
   return NULL;
}

template <class ItemType>
void
Queue<ItemType>::SwapContents(Queue<ItemType> & that)
{
   bool thisSmall = (_queue == _smallQueue);
   bool thatSmall = (that._queue == that._smallQueue);

   if ((thisSmall)&&(thatSmall))
   {
      // First, move any extra items from the longer queue to the shorter one...
      uint32 commonSize = muscleMin(GetNumItems(), that.GetNumItems());
      int32 sizeDiff    = ((int32)GetNumItems())-((int32)that.GetNumItems());
      Queue<ItemType> & copyTo   = (sizeDiff > 0) ? that : *this;
      Queue<ItemType> & copyFrom = (sizeDiff > 0) ? *this : that;
      (void) copyTo.AddTail(copyFrom, commonSize);   // guaranteed not to fail
      (void) copyFrom.EnsureSize(commonSize, true);  // remove the copied items from (copyFrom)

      // Then just swap the elements that are present in both arrays
      for (uint32 i=0; i<commonSize; i++) muscleSwap((*this)[i], that[i]);
   }
   else if (thisSmall) SwapContentsAux(that);
   else if (thatSmall) that.SwapContentsAux(*this);
   else
   {
      // this case is easy, we can just swizzle the pointers around
      muscleSwap(_queue,     that._queue);
      muscleSwap(_queueSize, that._queueSize);
      muscleSwap(_headIndex, that._headIndex);
      muscleSwap(_tailIndex, that._tailIndex);
      muscleSwap(_itemCount, that._itemCount);
   }
}

template <class ItemType>
void
Queue<ItemType>::SwapContentsAux(Queue<ItemType> & largeThat)
{
   // First, copy over our (small) contents to his static buffer
   uint32 ni = GetNumItems();
   for (uint32 i=0; i<ni; i++) largeThat._smallQueue[i] = (*this)[i];

   // Now adopt his dynamic buffer
   _queue     = largeThat._queue;
   _queueSize = largeThat._queueSize;
   _headIndex = largeThat._headIndex;
   _tailIndex = largeThat._tailIndex;
   
   // And point him back at his static buffer
   if (ni > 0)
   {
      largeThat._queue     = largeThat._smallQueue;
      largeThat._queueSize = ARRAYITEMS(largeThat._smallQueue);
      largeThat._headIndex = 0;
      largeThat._tailIndex = ni-1;
   }
   else
   {
      largeThat._queue     = NULL;
      largeThat._queueSize = 0;
      // headIndex and tailIndex are undefined in this case anyway
   }
   
   muscleSwap(_itemCount, largeThat._itemCount);
}

template <class ItemType>
bool
Queue<ItemType>::StartsWith(const Queue<ItemType> & prefixQueue) const
{
   if (prefixQueue.GetNumItems() > GetNumItems()) return false;
   uint32 prefixQueueLen = prefixQueue.GetNumItems();
   for (uint32 i=0; i<prefixQueueLen; i++) if (!(prefixQueue[i] == (*this)[i])) return false;
   return true;
}

template <class ItemType>
bool
Queue<ItemType>::EndsWith(const Queue<ItemType> & suffixQueue) const
{
   if (suffixQueue.GetNumItems() > GetNumItems()) return false;
   int32 lastToCheck = GetNumItems()-suffixQueue.GetNumItems();
   for (int32 i=GetNumItems()-1; i>=lastToCheck; i--) if (!(suffixQueue[i] == (*this)[i])) return false;
   return true;
}

template <class ItemType>
void
Queue<ItemType>::Normalize()
{
   if ((_itemCount > 0)&&(_headIndex > _tailIndex))
   {
      if (_itemCount*2 <= _queueSize)
      {
         // There's enough space in the middle of the
         // array to just copy the items over, yay!  This
         // is more efficient when there are just a few
         // valid items in a large array.
         uint32 startAt = _tailIndex+1;
         for (uint32 i=0; i<_itemCount; i++) 
         {
            ItemType & from = (*this)[i];
            _queue[startAt+i] = from;
            from = ItemType();  // clear the old slot to avoid leaving extra Refs, etc
         }
         _headIndex = startAt;
         _tailIndex = startAt+_itemCount-1; 
      }
      else
      {
         // There's not enough room to do a simple copy,
         // so we'll rotate the entire array using this
         // algorithm that was written by Paul Hsieh, taken
         // from http://www.azillionmonkeys.com/qed/case8.html
         uint32 c = 0;
         for (uint32 v = 0; c<_queueSize; v++)
         {
             uint32 t  = v;
             uint32 tp = v + _headIndex;
             ItemType tmp = _queue[v];
             c++;
             while(tp != v) 
             {
                 _queue[t] = _queue[tp];
                 t = tp;
                 tp += _headIndex;
                 if (tp >= _queueSize) tp -= _queueSize;
                 c++;
             }
             _queue[t] = tmp;
         }
         _headIndex = 0;
         _tailIndex = _itemCount-1;
      }
   }
}

END_NAMESPACE(muscle);

#endif

---