"Fossies" - the Fresh Open Source Software Archive

Member "muscle/util/Queue.h" (8 Jun 2019, 74122 Bytes) of package /linux/privat/muscle7.30.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "Queue.h" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 7.20_vs_7.21.

    1 /* This file is Copyright 2000-2013 Meyer Sound Laboratories Inc.  See the included LICENSE.txt file for details. */
    2 
    3 #ifndef MuscleQueue_h
    4 #define MuscleQueue_h
    5 
    6 #ifndef MUSCLE_AVOID_CPLUSPLUS11
    7 # include <initializer_list>
    8 #endif
    9 
   10 #include "support/MuscleSupport.h"
   11 
   12 namespace muscle {
   13 
   14 #ifndef SMALL_QUEUE_SIZE
   15 /** Specifies the number of items that should be held "inline" inside a Queue object.  Any Queue will be able to hold up to this many items without having to do a separate heap allocation.  Defaults to 3 if not specified otherwise by the compiler (e.g. via -DSMALL_QUEUE_SIZE=5) */
   16 # define SMALL_QUEUE_SIZE 3
   17 #endif
   18 
   19 #ifndef DOXYGEN_SHOULD_IGNORE_THIS
   20 # ifndef MUSCLE_AVOID_CPLUSPLUS11
   21 // Enable move semantics (when possible) for C++11
   22 #  define QQ_UniversalSinkItemRef template<typename ItemParam>
   23 #  define QQ_SinkItemParam  ItemParam &&
   24 #  define QQ_PlunderItem(item) std::move(item)
   25 #  define QQ_ForwardItem(item) std::forward<ItemParam>(item)
   26 # else
   27 // For earlier versions of C++, use the traditional copy/ref semantics
   28 #  define QQ_UniversalSinkItemRef
   29 #  define QQ_SinkItemParam const ItemType &
   30 #  define QQ_PlunderItem(item) (item)
   31 #  define QQ_ForwardItem(item) (item)
   32 # endif
   33 #endif
   34 
   35 /** This class implements a templated double-ended-queue data structure.
   36  *  Adding or removing items from the head or tail of a Queue is (on average)
   37  *  an O(1) operation.  A Queue can also serve as a reasonably efficient resizable-array 
   38  *  class (aka Vector) if that is all you need.
   39  */
   40 template <class ItemType> class Queue MUSCLE_FINAL_CLASS
   41 {
   42 public:
   43    /** Default constructor.  */
   44    Queue();
   45 
   46    /** @copydoc DoxyTemplate::DoxyTemplate(const DoxyTemplate &) */
   47    Queue(const Queue& rhs);
   48 
   49    /** Destructor. */
   50    virtual ~Queue();
   51 
   52    /** @copydoc DoxyTemplate::operator=(const DoxyTemplate &) */
   53    Queue & operator=(const Queue & rhs);
   54 
   55 #ifndef MUSCLE_AVOID_CPLUSPLUS11
   56    /** Initializer-list Constructor (C++11 only)
   57      * @param list the initializer-list of items to add to this Queue
   58      */
   59    Queue(const std::initializer_list<ItemType> & list) 
   60       : _queue(NULL)
   61       , _queueSize(0)
   62       , _itemCount(0) 
   63    {
   64       (void) AddTailMulti(list);
   65    }
   66 
   67    /** @copydoc DoxyTemplate::DoxyTemplate(DoxyTemplate &&) */
   68    Queue(Queue && rhs) 
   69       : _queue(NULL)
   70       , _queueSize(0)
   71       , _itemCount(0) 
   72    {
   73       if (rhs._queue == rhs._smallQueue) *this = rhs; else SwapContents(rhs);
   74    }
   75 
   76    /** @copydoc DoxyTemplate::operator=(DoxyTemplate &&) */
   77    Queue & operator =(Queue && rhs) {if (rhs._queue == rhs._smallQueue) *this = rhs; else SwapContents(rhs); return *this;}
   78 #endif
   79 
   80    /** @copydoc DoxyTemplate::operator==(const DoxyTemplate &) const */
   81    bool operator==(const Queue & rhs) const;
   82 
   83    /** @copydoc DoxyTemplate::operator!=(const DoxyTemplate &) const */
   84    bool operator!=(const Queue & rhs) const {return !(*this == rhs);}
   85 
   86    /** @copydoc DoxyTemplate::operator<(const DoxyTemplate &) const */
   87    bool operator<(const Queue & rhs) const {return (lexicographicalCompare(rhs) < 0);}
   88 
   89    /** @copydoc DoxyTemplate::operator<=(const DoxyTemplate &) const */
   90    bool operator<=(const Queue & rhs) const {return (lexicographicalCompare(rhs) <= 0);}
   91 
   92    /** @copydoc DoxyTemplate::operator>(const DoxyTemplate &) const */
   93    bool operator>(const Queue & rhs) const {return (lexicographicalCompare(rhs) > 0);}
   94 
   95    /** @copydoc DoxyTemplate::operator>=(const DoxyTemplate &) const */
   96    bool operator>=(const Queue & rhs) const {return (lexicographicalCompare(rhs) >= 0);}
   97 
   98    /** Similar to the assignment operator, except this method returns a status code.
   99      * @param rhs This Queue's contents will become a copy of (rhs)'s items.
  100      * @returns B_NO_ERROR on success, or B_ERROR on failure (out of memory?).
  101      */
  102    status_t CopyFrom(const Queue<ItemType> & rhs);
  103 
  104    /** Appends (item) to the end of the queue.  Queue size grows by one.
  105     *  @param item The item to append. 
  106     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  107     */
  108    QQ_UniversalSinkItemRef status_t AddTail(QQ_SinkItemParam item) {return (AddTailAndGet(QQ_ForwardItem(item)) != NULL) ? B_NO_ERROR : B_ERROR;}
  109 
  110    /** As above, except that a default-initialized item is appended.
  111     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  112     */
  113    status_t AddTail() {return AddTail(GetDefaultItem());}
  114 
  115    /** Appends some or all items in (queue) to the end of our queue.  Queue size
  116     *  grows by at most (queue.GetNumItems()).
  117     *  For example:
  118     *    Queue<int> a;  // contains 1, 2, 3, 4
  119     *    Queue<int> b;  // contains 5, 6, 7, 8
  120     *    a.AddTail(b);  // a now contains 1, 2, 3, 4, 5, 6, 7, 8
  121     *  @param queue The queue to append to our queue.
  122     *  @param startIndex Index in (queue) to start adding at.  Default to zero.
  123     *  @param numItems Number of items to add.  If this number is too large, it will be capped appropriately.  Default is to add all items.
  124     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  125     */
  126    status_t AddTailMulti(const Queue<ItemType> & queue, uint32 startIndex = 0, uint32 numItems = MUSCLE_NO_LIMIT);
  127 
  128    /** Adds the given array of items to the tail of the Queue.  Equivalent
  129     *  to adding them to the tail of the Queue one at a time, but somewhat
  130     *  more efficient.  On success, the queue size grows by (numItems).
  131     *  @param items Pointer to an array of items to add to the Queue.
  132     *  @param numItems Number of items in the array
  133     *  @return B_NO_ERROR on success, or B_ERROR on failure (out of memory)
  134     */
  135    status_t AddTailMulti(const ItemType * items, uint32 numItems);
  136 
  137 #ifndef MUSCLE_AVOID_CPLUSPLUS11
  138    /** Available in C++11 only:  Appends the items specified in the initializer
  139     *  list to this Queue.
  140     *  @param list The C++11 initializer list of items (e.g. {1,2,3,4,5} to add.
  141     *  @returns B_NO_ERROR on success, or B_ERROR on failure (out of memory?)
  142     */
  143    status_t AddTailMulti(const std::initializer_list<ItemType> & list)
  144    {
  145       if (EnsureCanAdd((uint32) list.size()) != B_NO_ERROR) return B_ERROR;
  146       for (auto i : list) (void) AddTail(i);  // can't fail, because we allocated the necessary space on the previous line
  147       return B_NO_ERROR;
  148    }
  149 #endif
  150 
  151    /** Appends (item) to the end of the queue.  Queue size grows by one.
  152     *  @param item The item to append. 
  153     *  @return A pointer to the appended item on success, or a NULL pointer on failure.
  154     */
  155    QQ_UniversalSinkItemRef ItemType * AddTailAndGet(QQ_SinkItemParam item);
  156 
  157    /** As above, except that an item is appended.
  158     *  @return A pointer to the appended item on success, or a NULL pointer on failure.
  159     *  @note that for POD ItemTypes, the appended item will be in an unitialized state.
  160     */
  161    ItemType * AddTailAndGet();
  162 
  163    /** Prepends (item) to the head of the queue.  Queue size grows by one.
  164     *  @param item The item to prepend. 
  165     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  166     */
  167    QQ_UniversalSinkItemRef status_t AddHead(QQ_SinkItemParam item) {return (AddHeadAndGet(QQ_ForwardItem(item)) != NULL) ? B_NO_ERROR : B_ERROR;}
  168 
  169    /** As above, except that a default-initialized item is prepended.
  170     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  171     */
  172    status_t AddHead() {return AddHead(GetDefaultItem());}
  173 
  174    /** Concatenates (queue) to the head of our queue.
  175     *  Our queue size grows by at most (queue.GetNumItems()).
  176     *  For example:
  177     *    Queue<int> a;  // contains 1, 2, 3, 4
  178     *    Queue<int> b;  // contains 5, 6, 7, 8
  179     *    a.AddHead(b);  // a now contains 5, 6, 7, 8, 1, 2, 3, 4
  180     *  @param queue The queue to prepend to our queue.
  181     *  @param startIndex Index in (queue) to start adding at.  Default to zero.
  182     *  @param numItems Number of items to add.  If this number is too large, it will be capped appropriately.  Default is to add all items.
  183     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  184     */
  185    status_t AddHeadMulti(const Queue<ItemType> & queue, uint32 startIndex = 0, uint32 numItems = MUSCLE_NO_LIMIT);
  186 
  187    /** Concatenates the given array of items to the head of the Queue.
  188     *  The semantics are the same as for AddHeadMulti(const Queue<ItemType> &).
  189     *  @param items Pointer to an array of items to add to the Queue.
  190     *  @param numItems Number of items in the array
  191     *  @return B_NO_ERROR on success, or B_ERROR on failure (out of memory)
  192     */
  193    status_t AddHeadMulti(const ItemType * items, uint32 numItems);
  194 
  195    /** Prepends (item) to the beginning of the queue.  Queue size grows by one.
  196     *  @param item The item to prepend. 
  197     *  @return A pointer to the prepend item on success, or a NULL pointer on failure.
  198     */
  199    QQ_UniversalSinkItemRef ItemType * AddHeadAndGet(QQ_SinkItemParam item);
  200 
  201    /** As above, except that an item is prepended.
  202     *  @return A pointer to the prepended item on success, or a NULL pointer on failure.
  203     *  @note that for POD ItemTypes, the prepended item will be in an unitialized state.
  204     */
  205    ItemType * AddHeadAndGet();
  206 
  207    /** Removes the item at the head of the queue.
  208     *  @return B_NO_ERROR on success, B_ERROR if the queue was empty.
  209     */
  210    status_t RemoveHead();
  211 
  212    /** Removes the item at the head of the queue and returns it.
  213      * If the Queue was empty, a default item is returned.
  214      */
  215    ItemType RemoveHeadWithDefault();
  216 
  217    /** Removes up to (numItems) items from the head of the queue.
  218      * @param numItems The desired number of items to remove
  219      * @returns the actual number of items removed (may be less than (numItems) if the Queue was too short) 
  220      */
  221    uint32 RemoveHeadMulti(uint32 numItems);
  222 
  223    /** Removes the item at the head of the queue and places it into (returnItem).
  224     *  @param returnItem On success, the removed item is copied into this object.
  225     *  @return B_NO_ERROR on success, B_ERROR if the queue was empty
  226     */
  227    status_t RemoveHead(ItemType & returnItem);
  228 
  229    /** Removes the item at the tail of the queue.
  230     *  @return B_NO_ERROR on success, B_ERROR if the queue was empty.
  231     */
  232    status_t RemoveTail();
  233 
  234    /** Removes the item at the tail of the queue and places it into (returnItem).
  235     *  @param returnItem On success, the removed item is copied into this object.
  236     *  @return B_NO_ERROR on success, B_ERROR if the queue was empty
  237     */
  238    status_t RemoveTail(ItemType & returnItem);
  239 
  240    /** Removes the item at the tail of the queue and returns it.
  241      * If the Queue was empty, a default item is returned.
  242      */
  243    ItemType RemoveTailWithDefault();
  244 
  245    /** Removes up to (numItems) items from the tail of the queue.
  246      * @param numItems The desired number of items to remove
  247      * @returns the actual number of items removed (may be less than (numItems) if the Queue was too short) 
  248      */
  249    uint32 RemoveTailMulti(uint32 numItems);
  250 
  251    /** Removes the item at the (index)'th position in the queue.
  252     *  @param index Which item to remove--can range from zero 
  253     *               (head of the queue) to GetNumItems()-1 (tail of the queue).
  254     *  @return B_NO_ERROR on success, B_ERROR on failure (i.e. bad index)
  255     *  Note that this method is somewhat inefficient for indices that
  256     *  aren't at the head or tail of the queue (i.e. O(n) time)
  257     */
  258    status_t RemoveItemAt(uint32 index);
  259 
  260    /** Removes the item at the (index)'th position in the queue, and copies it into (returnItem).
  261     *  @param index Which item to remove--can range from zero 
  262     *               (head of the queue) to (GetNumItems()-1) (tail of the queue).
  263     *  @param returnItem On success, the removed item is copied into this object.
  264     *  @return B_NO_ERROR on success, B_ERROR on failure (i.e. bad index)
  265     */
  266    status_t RemoveItemAt(uint32 index, ItemType & returnItem);
  267 
  268    /** Removes the nth item in the Queue and returns it.
  269     *  If there was no nth item in the Queue, a default item is returned.
  270     *  @param index Index of the item to remove and return.
  271     */
  272    ItemType RemoveItemAtWithDefault(uint32 index);
  273 
  274    /** Copies the (index)'th item into (returnItem).
  275     *  @param index Which item to get--can range from zero 
  276     *               (head of the queue) to (GetNumItems()-1) (tail of the queue).
  277     *  @param returnItem On success, the retrieved item is copied into this object.
  278     *  @return B_NO_ERROR on success, B_ERROR on failure (e.g. bad index)
  279     */
  280    status_t GetItemAt(uint32 index, ItemType & returnItem) const;
  281 
  282    /** Returns a pointer to an item in the array (i.e. no copying of the item is done).  
  283     *  Included for efficiency; be careful with this: modifying the queue can invalidate 
  284     *  the returned pointer!  
  285     *  @param index Index of the item to return a pointer to.
  286     *  @return a pointer to the internally held item, or NULL if (index) was invalid.
  287     */
  288    ItemType * GetItemAt(uint32 index) const {return (index<_itemCount)?GetItemAtUnchecked(index):NULL;}
  289 
  290    /** The same as GetItemAt(), except this version doesn't check to make sure
  291     *  (index) is valid.
  292     *  @param index Index of the item to return a pointer to.  Must be a valid index!
  293     *  @return a pointer to the internally held item.  The returned value is undefined
  294     *          if the index isn't valid, so be careful!
  295     */
  296    ItemType * GetItemAtUnchecked(uint32 index) const {return &_queue[InternalizeIndex(index)];}
  297 
  298    /** Returns a reference to the (index)'th item in the Queue, if such an item exists,
  299      * or a reference to a default item if it doesn't.  Unlike the [] operator,
  300      * it is okay to call this method with any value of (index).
  301      * @param index Which item to return.
  302      */
  303    const ItemType & GetWithDefault(uint32 index) const {return (index<_itemCount)?(*this)[index]:GetDefaultItem();}
  304 
  305    /** Returns a copy of the (index)'th item in the Queue, if such an item exists,
  306      * or the supplied default item if it doesn't.  Unlike the [] operator,
  307      * it is okay to call this method with any value of (index).
  308      * @param index Which item to return.
  309      * @param defItem An item to return if (index) isn't a valid value.
  310      * @note that this method returns by-value rather than by-reference, because
  311      *       returning (defItem) by-reference makes it too easy to call this method
  312      *       in a way that would cause it to return a dangling-reference-to-a-temporary-object.
  313      */
  314    ItemType GetWithDefault(uint32 index, const ItemType & defItem) const {return (index<_itemCount)?(*this)[index]:defItem;}
  315 
  316    /** Replaces the (index)'th item in the queue with (newItem).
  317     *  @param index Which item to replace--can range from zero 
  318     *               (head of the queue) to (GetNumItems()-1) (tail of the queue).
  319     *  @param newItem The item to place into the queue at the (index)'th position.
  320     *  @return B_NO_ERROR on success, B_ERROR on failure (e.g. bad index)
  321     */
  322    QQ_UniversalSinkItemRef status_t ReplaceItemAt(uint32 index, QQ_SinkItemParam newItem);
  323  
  324    /** As above, except the specified item is replaced with a default-initialized item.
  325     *  @param index Which item to replace--can range from zero 
  326     *               (head of the queue) to (GetNumItems()-1) (tail of the queue).
  327     *  @return B_NO_ERROR on success, B_ERROR on failure (e.g. bad index)
  328     */
  329    status_t ReplaceItemAt(uint32 index) {return ReplaceItemAt(index, GetDefaultItem());}
  330 
  331    /** Inserts (item) into the (nth) slot in the array.  InsertItemAt(0)
  332     *  is the same as AddHead(item), InsertItemAt(GetNumItems()) is the same
  333     *  as AddTail(item).  Other positions will involve an O(n) shifting of contents.
  334     *  @param index The position at which to insert the new item.
  335     *  @param newItem The item to insert into the queue.
  336     *  @return B_NO_ERROR on success, B_ERROR on failure (i.e. bad index).
  337     */
  338    QQ_UniversalSinkItemRef status_t InsertItemAt(uint32 index, QQ_SinkItemParam newItem);
  339    
  340    /** As above, except that a default-initialized item is inserted.
  341     *  @param index The position at which to insert the new item.
  342     *  @return B_NO_ERROR on success, B_ERROR on failure (i.e. bad index).
  343     */
  344    status_t InsertItemAt(uint32 index) {return InsertItemAt(index, GetDefaultItem());}
  345 
  346    /** Inserts some or all of the items in (queue) at the specified position in our queue.  
  347     *  Queue size grows by at most (queue.GetNumItems()).
  348     *  For example:
  349     *    Queue<int> a;   // contains 1, 2, 3, 4
  350     *    Queue<int> b;   // contains 5, 6, 7, 8
  351     *    a.InsertItemsAt(2, b); // a now contains 1, 2, 5, 6, 7, 8, 3, 4
  352     *  @param index The index into this Queue that items from (queue) should be inserted at.
  353     *  @param queue The queue whose items are to be inserted into this queue.
  354     *  @param startIndex Index in (queue) to start reading items from.  Defaults to zero.
  355     *  @param numNewItems Number of items to insert.  If this number is too large, it will be capped appropriately.  Default is to add all items.
  356     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  357     */
  358    status_t InsertItemsAt(uint32 index, const Queue<ItemType> & queue, uint32 startIndex = 0, uint32 numNewItems = MUSCLE_NO_LIMIT);
  359 
  360    /** Inserts the items pointed at by (items) at the specified position in our queue.  
  361     *  Queue size grows (numNewItems).
  362     *  For example:
  363     *    Queue<int> a;       // contains 1, 2, 3, 4
  364     *    const int b[] = {5, 6, 7};
  365     *    a.InsertItemsAt(2, b, ARRAYITEMS(b));  // a now contains 1, 2, 5, 6, 7, 3, 4
  366     *  @param index The index into this Queue that items from (queue) should be inserted at.
  367     *  @param items Pointer to the items to insert into this queue.
  368     *  @param numNewItems Number of items to insert.
  369     *  @return B_NO_ERROR on success, B_ERROR on failure (out of memory)
  370     */
  371    status_t InsertItemsAt(uint32 index, const ItemType * items, uint32 numNewItems);
  372 
  373    /** Removes all items from the queue. 
  374     *  @param releaseCachedBuffers If true, we will immediately free any buffers that we may be holding.  Otherwise
  375     *                              we will keep them around so that they can be re-used in the future.
  376     */
  377    void Clear(bool releaseCachedBuffers = false);
  378 
  379    /** This version of Clear() merely sets our held item-count to zero; it doesn't actually modify the
  380      * state of any items in the Queue.  This is very efficient, but be careful when using it with non-POD
  381      * types; for example, if you have a Queue<MessageRef> and you call FastClear() on it, the Messages
  382      * referenced by the MessageRef objects will not get recycled during the Clear() call because the
  383      * MessageRefs still exist in the Queue's internal array, even though they aren't readily accessible  
  384      * anymore.  Only call this method if you know what you are doing!
  385      */
  386    void FastClear() {_itemCount = _headIndex = _tailIndex = 0;}
  387 
  388    /** Returns the number of items in the queue.  (This number does not include pre-allocated space) */
  389    uint32 GetNumItems() const {return _itemCount;}
  390 
  391    /** Returns the total number of item-slots we have allocated space for.  Note that this is NOT
  392     *  the same as the value returned by GetNumItems() -- it is generally larger, since we often 
  393     *  pre-allocate additional slots in advance, in order to cut down on the number of re-allocations 
  394     *  we need to peform.
  395     */
  396    uint32 GetNumAllocatedItemSlots() const {return _queueSize;}
  397 
  398    /** Returns the number of "extra" (i.e. currently unoccupied) array slots we currently have allocated.  
  399      * Attempting to add more than (this many) additional items to this Queue will cause a memory reallocation.
  400      */
  401    uint32 GetNumUnusedItemSlots() const {return _queueSize-_itemCount;}
  402 
  403    /** Returns the number of bytes of memory taken up by this Queue's data */
  404    uint32 GetTotalDataSize() const {return sizeof(*this)+(GetNumAllocatedItemSlots()*sizeof(ItemType));}
  405 
  406    /** Convenience method:  Returns true iff there are no items in the queue. */
  407    bool IsEmpty() const {return (_itemCount == 0);}
  408 
  409    /** Convenience method:  Returns true iff there is at least one item in the queue. */
  410    bool HasItems() const {return (_itemCount > 0);}
  411 
  412    /** Returns a read-only reference the head item in the queue.  You must not call this when the queue is empty! */
  413    const ItemType & Head() const {return *GetItemAtUnchecked(0);}
  414 
  415    /** Returns a read-only reference the tail item in the queue.  You must not call this when the queue is empty! */
  416    const ItemType & Tail() const {return *GetItemAtUnchecked(_itemCount-1);}
  417 
  418    /** Returns a read-only reference the head item in the queue, or a default item if the Queue is empty. */
  419    const ItemType & HeadWithDefault() const {return HasItems() ? Head() : GetDefaultItem();}
  420 
  421    /** Returns a read-only reference the head item in the queue, or to the supplied default item if the Queue is empty.
  422      * @param defaultItem An item to return if the Queue is empty.
  423      * @note that this method returns by-value rather than by-reference, because
  424      *       returning (defItem) by-reference makes it too easy to call this method
  425      *       in a way that would cause it to return a dangling-reference-to-a-temporary-object.
  426      */
  427    ItemType HeadWithDefault(const ItemType & defaultItem) const {return HasItems() ? Head() : defaultItem;}
  428 
  429    /** Returns a read-only reference the tail item in the queue, or a default item if the Queue is empty. */
  430    const ItemType & TailWithDefault() const {return HasItems() ? Tail() : GetDefaultItem();}
  431 
  432    /** Returns a read-only reference the tail item in the queue, or to the supplied default item if the Queue is empty.
  433      * @param defaultItem An item to return if the Queue is empty.
  434      * @note that this method returns by-value rather than by-reference, because
  435      *       returning (defItem) by-reference makes it too easy to call this method
  436      *       in a way that would cause it to return a dangling-reference-to-a-temporary-object.
  437      */
  438    ItemType TailWithDefault(const ItemType & defaultItem) const {return HasItems() ? Tail() : defaultItem;}
  439 
  440    /** Returns a writable reference the head item in the queue.  You must not call this when the queue is empty! */
  441    ItemType & Head() {return *GetItemAtUnchecked(0);}
  442 
  443    /** Returns a writable reference the tail item in the queue.  You must not call this when the queue is empty! */
  444    ItemType & Tail() {return *GetItemAtUnchecked(_itemCount-1);}
  445 
  446    /** Returns a pointer to the first item in the queue, or NULL if the queue is empty */
  447    ItemType * HeadPointer() const {return GetItemAt(0);}
  448 
  449    /** Returns a pointer to the last item in the queue, or NULL if the queue is empty */
  450    ItemType * TailPointer() const {return GetItemAt(_itemCount-1);}
  451 
  452    /** Convenient read-only array-style operator (be sure to only use valid indices!)
  453      * @param index the index of the item to get (between 0 and (GetNumItems()-1), inclusive)
  454      */
  455    const ItemType & operator [](uint32 index) const; 
  456 
  457    /** Convenient read-write array-style operator (be sure to only use valid indices!)
  458      * @param index the index of the item to get (between 0 and (GetNumItems()-1), inclusive)
  459      */
  460    ItemType & operator [](uint32 index);
  461 
  462    /** Makes sure there is enough space allocated for at least (numSlots) items.  
  463     *  You only need to call this if you wish to minimize the number of data re-allocations done,
  464     *  or wish to add or remove a large number of default items at once (by specifying setNumItems=true).
  465     *  @param numSlots the minimum amount of items to pre-allocate space for in the Queue.
  466     *  @param setNumItems If true, the length of the Queue will be altered by adding or removing
  467     *                     items to (from) the tail of the Queue until the Queue is the specified size.
  468     *                     If false (the default), more slots may be pre-allocated, but the 
  469     *                     number of items officially in the Queue remains the same as before.
  470     *  @param extraReallocItems If we have to do an array reallocation, this many extra slots will be
  471     *                           added to the newly allocated array, above and beyond what is strictly
  472     *                           necessary.  That way the likelihood of another reallocation being necessary
  473     *                           in the near future is reduced.  Default value is zero, indicating that
  474     *                           no extra slots will be allocated.  This argument is ignored if (setNumItems) is true.
  475     *  @param allowShrink If set to true, the array will be reallocated even if the new array size is smaller than the 
  476     *                     existing size.  Defaults to false (i.e. only reallocate if the desired size is greater than
  477     *                     the existing size).
  478     *  @returns B_NO_ERROR on success, or B_ERROR on failure (out of memory)
  479     */
  480    status_t EnsureSize(uint32 numSlots, bool setNumItems = false, uint32 extraReallocItems = 0, bool allowShrink = false) {return EnsureSizeAux(numSlots, setNumItems, extraReallocItems, NULL, allowShrink);}
  481 
  482    /** Convenience wrapper around EnsureSize():  This method ensures that this Queue has enough 
  483      * extra space allocated to fit another (numExtraSlots) items without having to do a reallocation.
  484      * If it doesn't, it will do a reallocation so that it does have at least that much extra space.
  485      * @param numExtraSlots How many extra items we want to ensure room for.  Defaults to 1.
  486      * @returns B_NO_ERROR if the extra space now exists, or B_ERROR on failure (out of memory?)
  487      */
  488    status_t EnsureCanAdd(uint32 numExtraSlots = 1) {return EnsureSize(GetNumItems()+numExtraSlots);}
  489 
  490    /** Convenience wrapper around EnsureSize():  This method shrinks the Queue so that its size is
  491      * equal to the size of the data it contains, plus (numExtraSlots).
  492      * @param numExtraSlots the number of extra empty slots the Queue should contains after the shrink.
  493      *                      Defaults to zero.
  494      * @returns B_NO_ERROR on success, or B_ERROR on failure.
  495      */
  496    status_t ShrinkToFit(uint32 numExtraSlots = 0) {return EnsureSize(GetNumItems()+numExtraSlots, false, 0, true);}
  497 
  498    /** Convenience method -- works the same as IndexOf() but returns a boolean instead of an int32 index.
  499     *  @param item The item to look for.
  500     *  @param startAt The first index in the list to look at.  Defaults to zero.
  501     *  @param endAtPlusOne One more than the final index to look at.  If this value is greater than
  502     *               the number of items in the list, it will be clamped internally to be equal 
  503     *               to the number of items in the list.  Defaults to MUSCLE_NO_LIMIT.
  504     *  @return True if the item was found in the specified range, or false otherwise. 
  505     */
  506    bool Contains(const ItemType & item, uint32 startAt = 0, uint32 endAtPlusOne = MUSCLE_NO_LIMIT) const {return (IndexOf(item, startAt, endAtPlusOne) >= 0);}
  507 
  508    /** Returns the first index of the given (item), or -1 if (item) is not found in the list.  O(n) search time.
  509     *  @param item The item to look for.
  510     *  @param startAt The first index in the list to look at.  Defaults to zero.
  511     *  @param endAtPlusOne One more than the final index to look at.  If this value is greater than
  512     *               the number of items in the list, it will be clamped internally to be equal 
  513     *               to the number of items in the list.  Defaults to MUSCLE_NO_LIMIT.
  514     *  @return The index of the first item found, or -1 if no such item was found in the specified range.
  515     */
  516    int32 IndexOf(const ItemType & item, uint32 startAt = 0, uint32 endAtPlusOne = MUSCLE_NO_LIMIT) const;
  517 
  518    /** Returns the last index of the given (item), or -1 if (item) is not found in the list.  O(n) search time.  
  519     *  This method is different from IndexOf() in that this method searches backwards in the list.
  520     *  @param item The item to look for.
  521     *  @param startAt The initial index in the list to look at.  If this value is greater than or equal to
  522     *                 the size of the list, it will be clamped down to (numItems-1).   Defaults to MUSCLE_NO_LIMIT.
  523     *  @param endAt The final index in the list to look at.  Defaults to zero, which means
  524     *               to search back to the beginning of the list, if necessary.
  525     *  @return The index of the first item found in the reverse search, or -1 if no such item was found in the specified range.
  526     */
  527    int32 LastIndexOf(const ItemType & item, uint32 startAt = MUSCLE_NO_LIMIT, uint32 endAt = 0) const;
  528 
  529    /**
  530     *  Swaps the values of the two items at the given indices.  This operation
  531     *  will involve three copies of the held items.
  532     *  @param fromIndex First index to swap.
  533     *  @param toIndex   Second index to swap.
  534     */
  535    void Swap(uint32 fromIndex, uint32 toIndex);
  536 
  537    /**
  538     *  Reverses the ordering of the items in the given subrange.
  539     *  (e.g. if the items were A,B,C,D,E, this would change them to E,D,C,B,A)
  540     *  @param from Index of the start of the subrange.  Defaults to zero.
  541     *  @param to Index of the next item after the end of the subrange.  If greater than
  542     *         the number of items currently in the queue, this value will be clipped
  543     *         to be equal to that number.  Defaults to the largest possible uint32.
  544     */
  545    void ReverseItemOrdering(uint32 from=0, uint32 to = MUSCLE_NO_LIMIT); 
  546 
  547    /**
  548     *  Does an in-place, stable sort on a subrange of the contents of this Queue.  (The sort algorithm is a smart, in-place merge sort)
  549     *  @param compareFunctor the item-comparison functor to use when sorting the items in the Queue.
  550     *  @param from Index of the start of the subrange.  Defaults to zero.
  551     *  @param to Index of the next item after the end of the subrange.  
  552     *         If greater than the number of items currently in the queue, 
  553     *         the subrange will extend to the last item.  Defaults to the largest possible uint32.
  554     *  @param optCookie A user-defined value that will be passed to the comparison functor.
  555     */
  556    template <class CompareFunctorType> void Sort(const CompareFunctorType & compareFunctor, uint32 from=0, uint32 to = MUSCLE_NO_LIMIT, void * optCookie = NULL);
  557 
  558    /**
  559     *  Same as above, except that the default item-comparison functor for our ItemType is implicitly used.
  560     *  @param from Index of the start of the subrange.  Defaults to zero.
  561     *  @param to Index of the next item after the end of the subrange.  
  562     *         If greater than the number of items currently in the queue, 
  563     *         the subrange will extend to the last item.  Defaults to the largest possible uint32.
  564     *  @param optCookie A user-defined value that will be passed to the comparison functor.
  565     */ 
  566    void Sort(uint32 from=0, uint32 to = MUSCLE_NO_LIMIT, void * optCookie = NULL) {Sort(CompareFunctor<ItemType>(), from, to, optCookie);}
  567 
  568    /** 
  569     * Inserts the specified item at the position necessary to keep the Queue in sorted order.
  570     * Note that this method assumes the Queue is already in sorted order before the insertion.
  571     * @param item The item to insert into the Queue.
  572     * @param optCookie optional value to pass to the comparison functor.  Defaults to NULL.
  573     * @returns The index at which the item was inserted on success, or -1 on failure (out of memory)?
  574     */
  575    QQ_UniversalSinkItemRef int32 InsertItemAtSortedPosition(QQ_SinkItemParam item, void * optCookie = NULL) {return InsertItemAtSortedPosition(CompareFunctor<ItemType>(), item, optCookie);}
  576 
  577    /** 
  578     * Inserts the specified item at the position necessary to keep the Queue in sorted order.
  579     * Note that this method assumes the Queue is already in sorted order before the insertion.
  580     * @param compareFunctor a functor object whose Compare() method is called to do item comparisons.
  581     * @param item The item to insert into the Queue.
  582     * @param optCookie optional value to pass to the comparison functor.  Defaults to NULL.
  583     * @returns The index at which the item was inserted on success, or -1 on failure (out of memory)?
  584     */
  585    QQ_UniversalSinkItemRef int32 InsertItemAtSortedPosition(const CompareFunctor<ItemType> & compareFunctor, QQ_SinkItemParam item, void * optCookie = NULL);
  586 
  587    /**
  588     *  Swaps our contents with the contents of (that), in an efficient manner.
  589     *  @param that The queue whose contents are to be swapped with our own.
  590     */
  591    void SwapContents(Queue<ItemType> & that);
  592 
  593    /**
  594     *  Goes through the array and removes every item that is equal to (val).
  595     *  @param val the item to look for and remove
  596     *  @return The number of instances of (val) that were found and removed during this operation.
  597     */
  598    uint32 RemoveAllInstancesOf(const ItemType & val);
  599 
  600    /**
  601     *  Goes through the array and removes all duplicate items.
  602     *  @param assumeAlreadySorted If set to true, the algorithm will assume the array is
  603     *                             already sorted by value.  Otherwise it will sort the array
  604     *                             (so that duplicates are next to each other) before doing the
  605     *                             duplicate-removal step.  Defaults to false.
  606     *  @return The number of duplicate items that were found and removed during this operation.
  607     */
  608    uint32 RemoveDuplicateItems(bool assumeAlreadySorted = false);
  609 
  610    /**
  611     *  Goes through the array and removes the first item that is equal to (val).
  612     *  @param val the item to look for and remove
  613     *  @return B_NO_ERROR if a matching item was found and removed, or B_ERROR if it wasn't found.
  614     */
  615    status_t RemoveFirstInstanceOf(const ItemType & val);
  616 
  617    /**
  618     *  Goes through the array and removes the last item that is equal to (val).
  619     *  @param val the item to look for and remove
  620     *  @return B_NO_ERROR if a matching item was found and removed, or B_ERROR if it wasn't found.
  621     */
  622    status_t RemoveLastInstanceOf(const ItemType & val);
  623 
  624    /** Returns true iff the first item in our queue is equal to (prefix). 
  625      * @param prefix the item to check for at the head of this Queue
  626      */
  627    bool StartsWith(const ItemType & prefix) const {return ((HasItems())&&(Head() == prefix));}
  628 
  629    /** Returns true iff the (prefixQueue) is a prefix of this queue. 
  630      * @param prefixQueue the items to check for at the head of this Queue
  631      */
  632    bool StartsWith(const Queue<ItemType> & prefixQueue) const;
  633 
  634    /** Returns true iff the last item in our queue is equal to (suffix).
  635      * @param suffix the item to check for at the tail of this Queue
  636      */
  637    bool EndsWith(const ItemType & suffix) const {return ((HasItems())&&(Tail() == suffix));}
  638 
  639    /** Returns true iff the (suffixQueue) is a suffix of this queue. 
  640      * @param suffixQueue the list of items to check for at the tail of this Queue
  641      */
  642    bool EndsWith(const Queue<ItemType> & suffixQueue) const;
  643 
  644    /**
  645     *  Returns a pointer to the nth internally-held contiguous-Item-sub-array, to allow efficient
  646     *  array-style access to groups of items in this Queue.  In the current implementation 
  647     *  there may be as many as two such sub-arrays present, depending on the internal state of the Queue.
  648     *  @param whichArray Index of the internal array to return a pointer to.  Typically zero or one.
  649     *  @param retLength The number of items in the returned sub-array will be written here.
  650     *  @return Pointer to the first item in the sub-array on success, or NULL on failure.
  651     *          Note that this array is only guaranteed valid as long as no items are
  652     *          added or removed from the Queue.
  653     */ 
  654    ItemType * GetArrayPointer(uint32 whichArray, uint32 & retLength) {return const_cast<ItemType *>(GetArrayPointerAux(whichArray, retLength));} 
  655 
  656    /** Read-only version of the above
  657     *  @param whichArray Index of the internal array to return a pointer to.  Typically zero or one.
  658     *  @param retLength The number of items in the returned sub-array will be written here.
  659     *  @return Pointer to the first item in the sub-array on success, or NULL on failure.
  660     *          Note that this array is only guaranteed valid as long as no items are
  661     *          added or removed from the Queue.
  662     */
  663    const ItemType * GetArrayPointer(uint32 whichArray, uint32 & retLength) const {return GetArrayPointerAux(whichArray, retLength);}
  664 
  665    /** Normalizes the layout of the items held in this Queue so that they are guaranteed to be contiguous 
  666      * in memory.  This is useful if you want to pass pointers to items in this array in to functions
  667      * that expect C arrays.  Note that prepending items to this Queue may de-normalize it again.
  668      * Note also that this method is O(N) if the array needs normalizing.  
  669      * (It's a no-op if the Queue is already normalized, of course)
  670      */ 
  671    void Normalize();
  672 
  673    /** Returns true iff this Queue is currently normalized -- that is, if its contents are arranged
  674      * in the normal C-array ordering.  Returns false otherwise.  Call Normalize() if you want to
  675      * make sure that the data is normalized.
  676      */
  677    bool IsNormalized() const {return ((_itemCount == 0)||(_headIndex <= _tailIndex));}
  678 
  679    /** Returns true iff (val) is physically located in this container's internal items array.
  680      * @param val Reference to an item.
  681      */
  682    bool IsItemLocatedInThisContainer(const ItemType & val) const {return ((HasItems())&&((uintptr)((&val)-_queue) < (uintptr)GetNumItems()));}
  683 
  684    /** Returns a read-only reference to a default-constructed item of this Queue's type.  This item will be valid as long as this Queue is valid. */
  685    const ItemType & GetDefaultItem() const {return GetDefaultObjectForType<ItemType>();}
  686 
  687    /** Returns a pointer to our internally held array of items.  Note that this array's items are not guaranteed
  688      * to be stored in order -- in particular, the items may be "wrapped around" the end of the array, with the
  689      * first items in the sequence appearing near the end of the array.  Only use this function if you know exactly
  690      * what you are doing!
  691      */
  692    ItemType * GetRawArrayPointer() {return _queue;}
  693 
  694    /** As above, but provides read-only access */
  695    const ItemType * GetRawArrayPointer() const {return _queue;}
  696 
  697    /** Causes this Queue to drop any data it is currently holding and use the specified array as its data-buffer instead.
  698      * @param numItemsInArray The number of items pointed to by (array).
  699      * @param array Pointer to an array full of data.  This Queue will take ownership of the array, and will call
  700      *              delete[] on it at some point (either as part of a resize, or as part of the Queue destructor)
  701      *              unless you call ReleaseDataArray() beforehand.
  702      * @param validItemCount how many of the items in (array) should be considered currently-valid.  If larger than (numItemsInArray)
  703      *                      this value will be treated as if it was equal to (numItemsInArray).  (Useful if you have e.g. an
  704      *                      array of 800 items but want the final 300 of them to be used as "room to grow" only).
  705      *                      Defaults to MUSCLE_NO_LIMIT.
  706      * @note Don't call this method unless you know what you are doing!
  707      */
  708    void AdoptRawDataArray(uint32 numItemsInArray, ItemType * array, uint32 validItemCount = MUSCLE_NO_LIMIT);
  709 
  710    /** Relinquishes ownership of our internally-held data array, and returns it to the caller.
  711      * Note that the caller becomes the owner of the returned data-array and should call delete[] on it
  712      * when he is done using it, otherwise there will be a memory leak.  This method has the side effect
  713      * of clearing this Queue.
  714      * @param optRetArrayLen if non-NULL, the number of items in the returned array will be written into the
  715      *                       uint32 this pointer points to.  You can also get this value by calling GetNumAllocatedItemSlots()
  716      *                       before calling ReleaseRawDataArray() (but not afterwards!).  Defaults to NULL.
  717      * @returns a pointer to an array of items for the caller to own, or NULL on failure.  Call delete[] on the returned value to avoid a memory leak.
  718      * @note Don't call this method unless you know what you are doing!
  719      */
  720    ItemType * ReleaseRawDataArray(uint32 * optRetArrayLen = NULL);
  721 
  722 private:
  723    /** Returns true iff we need to set our ItemType objects to their default-constructed state when we're done using them */
  724    inline bool IsPerItemClearNecessary() const
  725    {
  726 #ifndef MUSCLE_AVOID_CPLUSPLUS11
  727       return !std::is_trivial<ItemType>::value;
  728 #else
  729       return true;
  730 #endif
  731    }
  732 
  733    // Like strcmp() except for vectors instead of strings
  734    int lexicographicalCompare(const Queue & rhs) const
  735    {
  736       const uint32 commonRange = muscleMin(GetNumItems(), rhs.GetNumItems());
  737       for (uint32 i=0; i<commonRange; i++)
  738       {
  739          const ItemType & leftItem  = (*this)[i];
  740          const ItemType & rightItem = rhs[i];
  741          if (leftItem < rightItem) return -1;
  742          if (rightItem < leftItem) return +1;
  743       }
  744 
  745       if (GetNumItems() < rhs.GetNumItems()) return -1;
  746       if (GetNumItems() > rhs.GetNumItems()) return +1;
  747       return 0; 
  748    }
  749 
  750    status_t EnsureSizeAux(uint32 numSlots, ItemType ** optRetOldArray) {return EnsureSizeAux(numSlots, false, 0, optRetOldArray, false);}
  751    status_t EnsureSizeAux(uint32 numSlots, bool setNumItems, uint32 extraReallocItems, ItemType ** optRetOldArray, bool allowShrink);
  752    const ItemType * GetArrayPointerAux(uint32 whichArray, uint32 & retLength) const;
  753    void SwapContentsAux(Queue<ItemType> & that);
  754 
  755    inline uint32 NextIndex(uint32 idx) const {return (idx >= _queueSize-1) ? 0 : idx+1;}
  756    inline uint32 PrevIndex(uint32 idx) const {return (idx == 0) ? _queueSize-1 : idx-1;}
  757 
  758    // Translates a user-index into an index into the _queue array.
  759    inline uint32 InternalizeIndex(uint32 idx) const 
  760    {
  761       assert(idx < _queueSize);  // just to reassure ClangSA
  762       return (_headIndex + idx) % _queueSize;
  763    }
  764 
  765    // Helper methods, used for sorting (stolen from http://www-ihm.lri.fr/~thomas/VisuTri/inplacestablesort.html)
  766    template<class CompareFunctorType> void   Merge(const CompareFunctorType & compareFunctor, uint32 from, uint32 pivot, uint32 to, uint32 len1, uint32 len2, void * optCookie);
  767    template<class CompareFunctorType> uint32 Lower(const CompareFunctorType & compareFunctor, uint32 from, uint32 to, const ItemType & val, void * optCookie) const;
  768    template<class CompareFunctorType> uint32 Upper(const CompareFunctorType & compareFunctor, uint32 from, uint32 to, const ItemType & val, void * optCookie) const;
  769 
  770    ItemType * _queue; // points to _smallQueue, or to a dynamically alloc'd array
  771    uint32 _queueSize; // number of slots in the _queue array
  772    uint32 _itemCount; // number of valid items in the array
  773    uint32 _headIndex; // index of the first filled slot (meaningless if _itemCount is zero)
  774    uint32 _tailIndex; // index of the last filled slot (meaningless if _itemCount is zero)
  775 
  776    enum {ACTUAL_SMALL_QUEUE_SIZE = ((sizeof(ItemType)*SMALL_QUEUE_SIZE) < sizeof(void*)) ? (sizeof(void*)/sizeof(ItemType)) : SMALL_QUEUE_SIZE};
  777    ItemType _smallQueue[ACTUAL_SMALL_QUEUE_SIZE];  // small queues can be stored inline in this array
  778 };
  779 
  780 template <class ItemType>
  781 Queue<ItemType>::Queue()
  782    : _queue(NULL)
  783    , _queueSize(0)
  784    , _itemCount(0)
  785    , _headIndex(0)
  786    , _tailIndex(0)
  787 {
  788    // empty
  789 }
  790 
  791 template <class ItemType>
  792 Queue<ItemType>::Queue(const Queue& rhs)
  793    : _queue(NULL)
  794    , _queueSize(0)
  795    , _itemCount(0)
  796    , _headIndex(0)
  797    , _tailIndex(0)
  798 {
  799    *this = rhs;
  800 }
  801 
  802 template <class ItemType>
  803 bool
  804 Queue<ItemType>::operator ==(const Queue& rhs) const
  805 {
  806    if (this == &rhs) return true;
  807    if (GetNumItems() != rhs.GetNumItems()) return false;
  808    for (int32 i = GetNumItems()-1; i>=0; i--) if (((*this)[i] == rhs[i]) == false) return false;
  809    return true;
  810 }
  811 
  812 template <class ItemType>
  813 Queue<ItemType> &
  814 Queue<ItemType>::operator =(const Queue& rhs)
  815 {
  816    if (this != &rhs)
  817    {
  818       const uint32 hisNumItems = rhs.GetNumItems();
  819            if (hisNumItems == 0) Clear(true);  // FogBugz #10274
  820       else if (EnsureSize(hisNumItems, true) == B_NO_ERROR) for (uint32 i=0; i<hisNumItems; i++) (*this)[i] = rhs[i];
  821    }
  822    return *this;
  823 }
  824 
  825 template <class ItemType>
  826 status_t 
  827 Queue<ItemType>::CopyFrom(const Queue & rhs)
  828 {
  829    if (this == &rhs) return B_NO_ERROR;
  830 
  831    const uint32 numItems = rhs.GetNumItems();
  832    if (EnsureSize(numItems, true) == B_NO_ERROR)
  833    {
  834       for (uint32 i=0; i<numItems; i++) (*this)[i] = rhs[i];
  835       return B_NO_ERROR;
  836    }
  837    return B_ERROR;
  838 }
  839 
  840 template <class ItemType>
  841 ItemType &
  842 Queue<ItemType>::operator[](uint32 i)
  843 {
  844    MASSERT(i<_itemCount, "Invalid index to Queue::[]");
  845    return _queue[InternalizeIndex(i)];
  846 }
  847 
  848 template <class ItemType>
  849 const ItemType &
  850 Queue<ItemType>::operator[](uint32 i) const
  851 {
  852    MASSERT(i<_itemCount, "Invalid index to Queue::[]");
  853    return *GetItemAtUnchecked(i);
  854 }             
  855 
  856 template <class ItemType>
  857 Queue<ItemType>::~Queue()
  858 {
  859    if (_queue != _smallQueue) delete [] _queue;
  860 }
  861 
  862 template <class ItemType>
  863 QQ_UniversalSinkItemRef 
  864 ItemType * 
  865 Queue<ItemType>::
  866 AddTailAndGet(QQ_SinkItemParam item)
  867 {
  868    ItemType * oldArray;
  869    if (EnsureSizeAux(_itemCount+1, false, _itemCount+1, &oldArray, false) != B_NO_ERROR) return NULL;
  870 
  871    if (_itemCount == 0) _headIndex = _tailIndex = 0;
  872                    else _tailIndex = NextIndex(_tailIndex);
  873    _itemCount++;
  874    ItemType * ret = &_queue[_tailIndex]; 
  875    *ret = item;
  876    delete [] oldArray;  // must do this AFTER the last reference to (item), in case (item) was part of (oldArray)
  877    return ret;
  878 }
  879 
  880 template <class ItemType>
  881 ItemType * 
  882 Queue<ItemType>::
  883 AddTailAndGet()
  884 {
  885    if (EnsureSize(_itemCount+1, false, _itemCount+1) != B_NO_ERROR) return NULL;
  886    if (_itemCount == 0) _headIndex = _tailIndex = 0;
  887                    else _tailIndex = NextIndex(_tailIndex);
  888    _itemCount++;
  889    return &_queue[_tailIndex]; 
  890 }
  891 
  892 template <class ItemType>
  893 status_t 
  894 Queue<ItemType>::
  895 AddTailMulti(const Queue<ItemType> & queue, uint32 startIndex, uint32 numNewItems)
  896 {
  897    const uint32 hisSize = queue.GetNumItems();
  898    numNewItems = muscleMin(numNewItems, (startIndex < hisSize) ? (hisSize-startIndex) : 0);
  899    
  900    const uint32 mySize  = GetNumItems();
  901    const uint32 newSize = mySize+numNewItems;
  902    if (EnsureSize(newSize, true) != B_NO_ERROR) return B_ERROR;
  903    for (uint32 i=mySize; i<newSize; i++) (*this)[i] = queue[startIndex+(i-mySize)];
  904 
  905    return B_NO_ERROR;
  906 }
  907 
  908 template <class ItemType>
  909 status_t 
  910 Queue<ItemType>::
  911 AddTailMulti(const ItemType * items, uint32 numItems)
  912 {
  913    const uint32 mySize  = GetNumItems();
  914    const uint32 newSize = mySize+numItems;
  915    uint32 rhs = 0;
  916 
  917    ItemType * oldArray;
  918    if (EnsureSizeAux(newSize, true, 0, &oldArray, false) != B_NO_ERROR) return B_ERROR;
  919    for (uint32 i=mySize; i<newSize; i++) (*this)[i] = items[rhs++];
  920    delete [] oldArray;  // must be done after all references to (items)
  921    return B_NO_ERROR;
  922 }
  923 
  924 template <class ItemType>
  925 QQ_UniversalSinkItemRef
  926 ItemType *
  927 Queue<ItemType>::
  928 AddHeadAndGet(QQ_SinkItemParam item)
  929 {
  930    ItemType * oldArray;
  931    if (EnsureSizeAux(_itemCount+1, false, _itemCount+1, &oldArray, false) != B_NO_ERROR) return NULL;
  932    if (_itemCount == 0) _headIndex = _tailIndex = 0;
  933                    else _headIndex = PrevIndex(_headIndex);
  934    _itemCount++;
  935    ItemType * ret = &_queue[_headIndex];
  936    *ret = QQ_ForwardItem(item);
  937    delete [] oldArray;  // must be done after all references to (item)!
  938    return ret;
  939 }
  940 
  941 template <class ItemType>
  942 ItemType *
  943 Queue<ItemType>::
  944 AddHeadAndGet()
  945 {
  946    if (EnsureSize(_itemCount+1, false, _itemCount+1) != B_NO_ERROR) return NULL;
  947    if (_itemCount == 0) _headIndex = _tailIndex = 0;
  948                    else _headIndex = PrevIndex(_headIndex);
  949    _itemCount++;
  950    return &_queue[_headIndex];
  951 }
  952 
  953 template <class ItemType>
  954 status_t 
  955 Queue<ItemType>::
  956 AddHeadMulti(const Queue<ItemType> & queue, uint32 startIndex, uint32 numNewItems)
  957 {
  958    const uint32 hisSize = queue.GetNumItems();
  959    numNewItems = muscleMin(numNewItems, (startIndex < hisSize) ? (hisSize-startIndex) : 0);
  960 
  961    if (EnsureSize(numNewItems+GetNumItems()) != B_NO_ERROR) return B_ERROR;
  962    for (int32 i=((int)startIndex+numNewItems)-1; i>=(int32)startIndex; i--) (void) AddHead(queue[i]);  // guaranteed not to fail
  963    return B_NO_ERROR;
  964 }
  965 
  966 template <class ItemType>
  967 status_t 
  968 Queue<ItemType>::
  969 AddHeadMulti(const ItemType * items, uint32 numItems)
  970 {
  971    ItemType * oldArray;
  972    if (EnsureSizeAux(_itemCount+numItems, &oldArray) != B_NO_ERROR) return B_ERROR;
  973    for (int32 i=((int32)numItems)-1; i>=0; i--) (void) AddHead(items[i]);  // guaranteed not to fail
  974    delete [] oldArray;  // must be done last!
  975    return B_NO_ERROR;
  976 }
  977 
  978 template <class ItemType>
  979 status_t 
  980 Queue<ItemType>::
  981 RemoveHead(ItemType & returnItem)
  982 {
  983    if (_itemCount == 0) return B_ERROR;
  984    returnItem = _queue[_headIndex];
  985    return RemoveHead();
  986 }
  987 
  988 template <class ItemType>
  989 uint32 
  990 Queue<ItemType>::RemoveHeadMulti(uint32 numItems)
  991 {
  992    numItems = muscleMin(numItems, _itemCount);
  993    if (numItems == _itemCount) Clear();
  994                           else for (uint32 i=0; i<numItems; i++) (void) RemoveHead();
  995    return numItems;
  996 }
  997 
  998 template <class ItemType>
  999 uint32 
 1000 Queue<ItemType>::RemoveTailMulti(uint32 numItems)
 1001 {
 1002    numItems = muscleMin(numItems, _itemCount);
 1003    if (numItems == _itemCount) Clear();
 1004                           else for (uint32 i=0; i<numItems; i++) (void) RemoveTail();
 1005    return numItems;
 1006 }
 1007 
 1008 template <class ItemType>
 1009 status_t
 1010 Queue<ItemType>::
 1011 RemoveHead()
 1012 {
 1013    if (_itemCount == 0) return B_ERROR;
 1014    const uint32 oldHeadIndex = _headIndex;
 1015    _headIndex = NextIndex(_headIndex);
 1016    _itemCount--;
 1017    if (IsPerItemClearNecessary()) _queue[oldHeadIndex] = GetDefaultItem();  // this must be done last, as queue state must be coherent when we do this
 1018    return B_NO_ERROR;
 1019 }
 1020 
 1021 template <class ItemType>
 1022 ItemType 
 1023 Queue<ItemType>::
 1024 RemoveHeadWithDefault() 
 1025 {
 1026    if (IsEmpty()) return GetDefaultItem(); 
 1027    else
 1028    {
 1029       ItemType ret = Head(); 
 1030       (void) RemoveHead(); 
 1031       return ret;
 1032    }
 1033 }
 1034 
 1035 template <class ItemType>
 1036 status_t 
 1037 Queue<ItemType>::
 1038 RemoveTail(ItemType & returnItem)
 1039 {
 1040    if (_itemCount == 0) return B_ERROR;
 1041    returnItem = _queue[_tailIndex];
 1042    return RemoveTail();
 1043 }
 1044 
 1045 template <class ItemType>
 1046 status_t 
 1047 Queue<ItemType>::
 1048 RemoveTail()
 1049 {
 1050    if (_itemCount == 0) return B_ERROR;
 1051    const uint32 removedItemIndex = _tailIndex;
 1052    _tailIndex = PrevIndex(_tailIndex);
 1053    _itemCount--;
 1054    if (IsPerItemClearNecessary()) _queue[removedItemIndex] = GetDefaultItem();  // this must be done last, as queue state must be coherent when we do this
 1055    return B_NO_ERROR;
 1056 }
 1057 
 1058 template <class ItemType>
 1059 ItemType 
 1060 Queue<ItemType>::
 1061 RemoveTailWithDefault() 
 1062 {
 1063    if (IsEmpty()) return GetDefaultItem(); 
 1064    else
 1065    {
 1066       ItemType ret = Tail(); 
 1067       (void) RemoveTail(); 
 1068       return ret;
 1069    }
 1070 }
 1071 
 1072 template <class ItemType>
 1073 status_t
 1074 Queue<ItemType>::
 1075 GetItemAt(uint32 index, ItemType & returnItem) const
 1076 {
 1077    const ItemType * p = GetItemAt(index);
 1078    if (p)
 1079    {
 1080       returnItem = *p;
 1081       return B_NO_ERROR;
 1082    }
 1083    else return B_ERROR;
 1084 }
 1085 
 1086 template <class ItemType>
 1087 status_t 
 1088 Queue<ItemType>::
 1089 RemoveItemAt(uint32 index, ItemType & returnItem)
 1090 {
 1091    if (index >= _itemCount) return B_ERROR;
 1092    returnItem = _queue[InternalizeIndex(index)];
 1093    return RemoveItemAt(index);
 1094 }
 1095 
 1096 template <class ItemType>
 1097 status_t 
 1098 Queue<ItemType>::
 1099 RemoveItemAt(uint32 index)
 1100 {
 1101    if (index >= _itemCount) return B_ERROR;
 1102 
 1103    uint32 internalizedIndex = InternalizeIndex(index);
 1104    uint32 indexToClear;
 1105 
 1106    if (index < _itemCount/2)
 1107    {
 1108       // item is closer to the head:  shift everything forward one, ending at the head
 1109       while(internalizedIndex != _headIndex)
 1110       {
 1111          const uint32 prev = PrevIndex(internalizedIndex);
 1112          _queue[internalizedIndex] = _queue[prev];
 1113          internalizedIndex = prev;
 1114       }
 1115       indexToClear = _headIndex;
 1116       _headIndex = NextIndex(_headIndex); 
 1117    }
 1118    else
 1119    {
 1120       // item is closer to the tail:  shift everything back one, ending at the tail
 1121       while(internalizedIndex != _tailIndex)
 1122       {
 1123          const uint32 next = NextIndex(internalizedIndex);
 1124          _queue[internalizedIndex] = _queue[next];
 1125          internalizedIndex = next;
 1126       }
 1127       indexToClear = _tailIndex;
 1128       _tailIndex = PrevIndex(_tailIndex); 
 1129    }
 1130 
 1131    _itemCount--;
 1132    if (IsPerItemClearNecessary()) _queue[indexToClear] = GetDefaultItem();  // this must be done last, as queue state must be coherent when we do this
 1133    return B_NO_ERROR; 
 1134 }
 1135 
 1136 template <class ItemType>
 1137 ItemType 
 1138 Queue<ItemType>::
 1139 RemoveItemAtWithDefault(uint32 index) 
 1140 {
 1141    if (index >= GetNumItems()) return GetDefaultItem();
 1142    else
 1143    {
 1144       const ItemType ret = (*this)[index];
 1145       (void) RemoveItemAt(index); 
 1146       return ret;
 1147    }
 1148 }
 1149 
 1150 template <class ItemType>
 1151 QQ_UniversalSinkItemRef
 1152 status_t 
 1153 Queue<ItemType>::
 1154 ReplaceItemAt(uint32 index, QQ_SinkItemParam newItem)
 1155 {
 1156    if (index >= _itemCount) return B_ERROR;
 1157    _queue[InternalizeIndex(index)] = QQ_ForwardItem(newItem);
 1158    return B_NO_ERROR;
 1159 }
 1160 
 1161 template <class ItemType>
 1162 QQ_UniversalSinkItemRef
 1163 status_t 
 1164 Queue<ItemType>::
 1165 InsertItemAt(uint32 index, QQ_SinkItemParam newItem)
 1166 {
 1167    if ((GetNumUnusedItemSlots() < 1)&&(IsItemLocatedInThisContainer(newItem)))
 1168    {
 1169       ItemType temp = QQ_ForwardItem(newItem); // avoid dangling pointer issue by copying the item to a temporary location
 1170       return InsertItemAt(index, temp);
 1171    }
 1172 
 1173    // Simple cases
 1174    if (index >  _itemCount) return B_ERROR;
 1175    if (index == _itemCount) return AddTail(QQ_ForwardItem(newItem));
 1176    if (index == 0)          return AddHead(QQ_ForwardItem(newItem));
 1177 
 1178    // Harder case:  inserting into the middle of the array
 1179    if (index < _itemCount/2)
 1180    {
 1181       // Add a space at the front, and shift things back
 1182       if (AddHead() != B_NO_ERROR) return B_ERROR;  // allocate an extra slot
 1183       for (uint32 i=0; i<index; i++) ReplaceItemAt(i, QQ_ForwardItem(*GetItemAtUnchecked(i+1)));
 1184    }
 1185    else
 1186    {
 1187       // Add a space at the rear, and shift things forward
 1188       if (AddTail() != B_NO_ERROR) return B_ERROR;  // allocate an extra slot
 1189       for (int32 i=((int32)_itemCount)-1; i>((int32)index); i--) ReplaceItemAt(i, QQ_ForwardItem(*GetItemAtUnchecked(i-1)));
 1190    }
 1191    return ReplaceItemAt(index, QQ_ForwardItem(newItem));
 1192 }
 1193 
 1194 template <class ItemType>
 1195 status_t 
 1196 Queue<ItemType>::
 1197 InsertItemsAt(uint32 index, const Queue<ItemType> & queue, uint32 startIndex, uint32 numNewItems)
 1198 {
 1199    const uint32 hisSize = queue.GetNumItems();
 1200    numNewItems = muscleMin(numNewItems, (startIndex < hisSize) ? (hisSize-startIndex) : 0);
 1201    if (numNewItems == 0) return B_NO_ERROR;
 1202    if (index > _itemCount) return B_ERROR;
 1203    if (numNewItems == 1)
 1204    {
 1205       if (index == 0)          return AddHead(queue.Head());
 1206       if (index == _itemCount) return AddTail(queue.Head());
 1207    }
 1208 
 1209    const uint32 oldSize = GetNumItems();
 1210    const uint32 newSize = oldSize+numNewItems;
 1211 
 1212    if (EnsureSize(newSize, true) != B_NO_ERROR) return B_ERROR;
 1213    for (uint32 i=index; i<oldSize; i++)           (*this)[i+numNewItems] = (*this)[i];
 1214    for (uint32 i=index; i<index+numNewItems; i++) (*this)[i]             = queue[startIndex++];
 1215    return B_NO_ERROR;
 1216 }
 1217 
 1218 template <class ItemType>
 1219 status_t 
 1220 Queue<ItemType>::
 1221 InsertItemsAt(uint32 index, const ItemType * items, uint32 numNewItems)
 1222 {
 1223    if (numNewItems == 0) return B_NO_ERROR;
 1224    if (index > _itemCount) return B_ERROR;
 1225    if (numNewItems == 1)
 1226    {
 1227       if (index == 0)          return AddHead(*items);
 1228       if (index == _itemCount) return AddTail(*items);
 1229    }
 1230 
 1231    const uint32 oldSize = GetNumItems();
 1232    const uint32 newSize = oldSize+numNewItems;
 1233 
 1234    ItemType * oldItems;
 1235    if (EnsureSizeAux(newSize, true, &oldItems, NULL, false) != B_NO_ERROR) return B_ERROR;
 1236    int32 si = 0;
 1237    for (uint32 i=index; i<oldSize; i++)           (*this)[i+numNewItems] = (*this)[i];
 1238    for (uint32 i=index; i<index+numNewItems; i++) (*this)[i]             = items[si++];
 1239    delete [] oldItems;
 1240    return B_NO_ERROR;
 1241 }
 1242 
 1243 template <class ItemType>
 1244 void 
 1245 Queue<ItemType>::
 1246 Clear(bool releaseCachedBuffers)
 1247 {
 1248    if ((releaseCachedBuffers)&&(_queue != _smallQueue))
 1249    {
 1250       delete [] _queue;
 1251       _queue = NULL;
 1252       _queueSize = 0;
 1253       _itemCount = 0;
 1254    }
 1255    else if (HasItems())
 1256    {
 1257       if (IsPerItemClearNecessary())
 1258       {
 1259          const ItemType & defaultItem = GetDefaultItem();
 1260          for (uint32 i=0; i<2; i++)
 1261          {
 1262             uint32 arrayLen = 0;  // set to zero just to shut the compiler up
 1263             ItemType * p = GetArrayPointer(i, arrayLen);
 1264             if (p) {for (uint32 j=0; j<arrayLen; j++) p[j] = defaultItem;}
 1265          }
 1266       }
 1267       FastClear();
 1268    }
 1269 }
 1270 
 1271 template <class ItemType>
 1272 status_t 
 1273 Queue<ItemType>::
 1274 EnsureSizeAux(uint32 size, bool setNumItems, uint32 extraPreallocs, ItemType ** retOldArray, bool allowShrink)
 1275 {
 1276    if (retOldArray) *retOldArray = NULL;  // default value, will be set non-NULL iff the old array needs deleting later
 1277 
 1278    if ((_queue == NULL)||(allowShrink ? (_queueSize != (size+extraPreallocs)) : (_queueSize < size)))
 1279    {
 1280       const uint32 sqLen = ARRAYITEMS(_smallQueue);
 1281       const uint32 temp  = size + extraPreallocs;
 1282       uint32 newQLen = muscleMax((uint32)ARRAYITEMS(_smallQueue), ((setNumItems)||(temp <= sqLen)) ? muscleMax(sqLen,temp) : temp);
 1283 
 1284       ItemType * newQueue = ((_queue == _smallQueue)||(newQLen > sqLen)) ? newnothrow_array(ItemType,newQLen) : _smallQueue;
 1285 
 1286       if (newQueue == NULL) {WARN_OUT_OF_MEMORY; return B_ERROR;}
 1287       if (newQueue == _smallQueue) newQLen = sqLen;
 1288       
 1289       // The (_queueSize > 0) check below isn't strictly necessary, but it makes clang++ feel better
 1290       if (_queueSize > 0) for (uint32 i=0; i<_itemCount; i++) newQueue[i] = QQ_PlunderItem(*GetItemAtUnchecked(i));  // we know that (_itemCount < size)
 1291 
 1292       if (setNumItems) _itemCount = size;
 1293       _headIndex = 0;
 1294       _tailIndex = _itemCount-1;
 1295 
 1296       if (_queue == _smallQueue) 
 1297       {
 1298          if (IsPerItemClearNecessary()) 
 1299          {
 1300             const ItemType & defaultItem = GetDefaultItem();
 1301             for (uint32 i=0; i<sqLen; i++) _smallQueue[i] = defaultItem;
 1302          }
 1303       }
 1304       else if (retOldArray) *retOldArray = _queue;
 1305       else delete [] _queue;
 1306 
 1307       _queue = newQueue;
 1308       _queueSize = newQLen;
 1309    }
 1310 
 1311    if (setNumItems) 
 1312    {
 1313       // Force ourselves to contain exactly the required number of items
 1314       if (size > _itemCount)
 1315       {
 1316          // We can do this quickly because the "new" items are already initialized properly
 1317          _tailIndex = PrevIndex((_headIndex+size)%_queueSize);
 1318          _itemCount = size;
 1319       }
 1320       else (void) RemoveTailMulti(_itemCount-size);
 1321    }
 1322 
 1323    return B_NO_ERROR;
 1324 }
 1325 
 1326 template <class ItemType>
 1327 int32 
 1328 Queue<ItemType>::
 1329 IndexOf(const ItemType & item, uint32 startAt, uint32 endAtPlusOne) const
 1330 {
 1331    if (startAt >= GetNumItems()) return -1;
 1332 
 1333    endAtPlusOne = muscleMin(endAtPlusOne, GetNumItems());
 1334    for (uint32 i=startAt; i<endAtPlusOne; i++) if (*GetItemAtUnchecked(i) == item) return i;
 1335    return -1;
 1336 }
 1337 
 1338 template <class ItemType>
 1339 int32 
 1340 Queue<ItemType>::
 1341 LastIndexOf(const ItemType & item, uint32 startAt, uint32 endAt) const
 1342 {
 1343    if (endAt >= GetNumItems()) return -1;
 1344 
 1345    startAt = muscleMin(startAt, GetNumItems()-1);
 1346    for (int32 i=(int32)startAt; i>=((int32)endAt); i--) if (*GetItemAtUnchecked(i) == item) return i;
 1347    return -1;
 1348 }
 1349 
 1350 template <class ItemType>
 1351 void 
 1352 Queue<ItemType>::
 1353 Swap(uint32 fromIndex, uint32 toIndex) 
 1354 {
 1355    muscleSwap((*this)[fromIndex], (*this)[toIndex]);
 1356 }
 1357 
 1358 template <class ItemType>
 1359 QQ_UniversalSinkItemRef
 1360 int32 
 1361 Queue<ItemType>::
 1362 InsertItemAtSortedPosition(const CompareFunctor<ItemType> & compareFunctor, QQ_SinkItemParam item, void * optCookie)
 1363 {
 1364    int32 insertAfter = GetNumItems();
 1365    if ((insertAfter > 0)&&(compareFunctor.Compare(item, Head(), optCookie) >= 0)) 
 1366       while(--insertAfter >= 0) 
 1367          if (compareFunctor.Compare(item, (*this)[insertAfter], optCookie) >= 0) 
 1368             return (InsertItemAt(insertAfter+1, QQ_ForwardItem(item)) == B_NO_ERROR) ? (insertAfter+1) : -1;
 1369    return (AddHead(QQ_ForwardItem(item)) == B_NO_ERROR) ? 0 : -1;
 1370 }
 1371 
 1372 template <class ItemType>
 1373 template <class CompareFunctorType>
 1374 void 
 1375 Queue<ItemType>::
 1376 Sort(const CompareFunctorType & compareFunctor, uint32 from, uint32 to, void * optCookie) 
 1377 {
 1378    const uint32 size = GetNumItems();
 1379    if (to > size) to = size;
 1380    if (to > from)
 1381    {
 1382       if (to < from+12) 
 1383       {
 1384          // too easy, just do a bubble sort (base case)
 1385          if (to > from+1) 
 1386          {
 1387             for (uint32 i=from+1; i<to; i++) 
 1388             {
 1389                for (uint32 j=i; j>from; j--) 
 1390                {
 1391                   const int ret = compareFunctor.Compare(*(GetItemAtUnchecked(j)), *(GetItemAtUnchecked(j-1)), optCookie);
 1392                   if (ret < 0) Swap(j, j-1); 
 1393                           else break; 
 1394                }
 1395             } 
 1396          } 
 1397       }
 1398       else
 1399       {
 1400          // Okay, do the real thing
 1401          const uint32 middle = (from + to)/2; 
 1402          Sort(compareFunctor, from, middle, optCookie); 
 1403          Sort(compareFunctor, middle, to, optCookie); 
 1404          Merge(compareFunctor, from, middle, to, middle-from, to-middle, optCookie); 
 1405       }
 1406    }
 1407 }
 1408 
 1409 template <class ItemType>
 1410 void 
 1411 Queue<ItemType>::
 1412 ReverseItemOrdering(uint32 from, uint32 to) 
 1413 {
 1414    const uint32 size = GetNumItems();
 1415    if (size > 0)
 1416    {
 1417       to--;  // make it inclusive
 1418       if (to >= size) to = size-1;
 1419       while (from < to) Swap(from++, to--); 
 1420    }
 1421 } 
 1422 
 1423 template <class ItemType>
 1424 status_t 
 1425 Queue<ItemType>::
 1426 RemoveFirstInstanceOf(const ItemType & val) 
 1427 {
 1428    const uint32 ni = GetNumItems();
 1429    for (uint32 i=0; i<ni; i++) if ((*this)[i] == val) return RemoveItemAt(i);
 1430    return B_ERROR;
 1431 }
 1432 
 1433 template <class ItemType>
 1434 status_t 
 1435 Queue<ItemType>::
 1436 RemoveLastInstanceOf(const ItemType & val) 
 1437 {
 1438    for (int32 i=((int32)GetNumItems())-1; i>=0; i--) if ((*this)[i] == val) return RemoveItemAt(i);
 1439    return B_ERROR;
 1440 }
 1441 
 1442 template <class ItemType>
 1443 uint32 
 1444 Queue<ItemType>::
 1445 RemoveAllInstancesOf(const ItemType & val) 
 1446 {
 1447    if (IsItemLocatedInThisContainer(val))
 1448    {
 1449       // avoid having the item erased while we are still using it
 1450       ItemType temp = val;
 1451       return RemoveAllInstancesOf(temp);
 1452    }
 1453 
 1454    // Efficiently collapse all non-matching slots up to the top of the list
 1455    const uint32 origSize = GetNumItems();
 1456    uint32 ret     = 0;
 1457    uint32 writeTo = 0;
 1458    for(uint32 readFrom=0; readFrom<origSize; readFrom++)
 1459    {
 1460       const ItemType & nextRead = (*this)[readFrom];
 1461       if (nextRead == val) ret++;
 1462       else 
 1463       {
 1464          if (readFrom > writeTo) (*this)[writeTo] = nextRead;
 1465          writeTo++;
 1466       }
 1467    }
 1468 
 1469    // Now get rid of any now-surplus slots
 1470    for (; writeTo<origSize; writeTo++) RemoveTail();
 1471 
 1472    return ret;
 1473 }
 1474 
 1475 template <class ItemType>
 1476 uint32 
 1477 Queue<ItemType>::
 1478 RemoveDuplicateItems(bool assumeAlreadySorted)
 1479 {
 1480    if (IsEmpty()) return 0;  // nothing to do!
 1481    if (assumeAlreadySorted == false) Sort();
 1482 
 1483    uint32 numWrittenItems  = 1;  // we'll always keep the first item
 1484    const uint32 totalItems = GetNumItems();
 1485    for (uint32 i=0; i<totalItems; i++)
 1486    {
 1487       const ItemType & nextItem = (*this)[i];
 1488       const ItemType & wItem    = (*this)[numWrittenItems-1];
 1489       if (nextItem != wItem) (*this)[numWrittenItems++] = nextItem;
 1490    } 
 1491 
 1492    const uint32 ret = GetNumItems()-numWrittenItems;
 1493    (void) EnsureSize(numWrittenItems, true);  // guaranteed to succeed
 1494    return ret;
 1495 }
 1496 
 1497 template <class ItemType>
 1498 template <class CompareFunctorType>
 1499 void 
 1500 Queue<ItemType>::
 1501 Merge(const CompareFunctorType & compareFunctor, uint32 from, uint32 pivot, uint32 to, uint32 len1, uint32 len2, void * optCookie) 
 1502 {
 1503    if ((len1)&&(len2))
 1504    {
 1505       if (len1+len2 == 2) 
 1506       { 
 1507          if (compareFunctor.Compare(*(GetItemAtUnchecked(pivot)), *(GetItemAtUnchecked(from)), optCookie) < 0) Swap(pivot, from); 
 1508       } 
 1509       else
 1510       {
 1511          uint32 first_cut, second_cut; 
 1512          uint32 len11, len22; 
 1513          if (len1 > len2) 
 1514          { 
 1515             len11      = len1/2; 
 1516             first_cut  = from + len11; 
 1517             second_cut = Lower(compareFunctor, pivot, to, *GetItemAtUnchecked(first_cut), optCookie); 
 1518             len22      = second_cut - pivot; 
 1519          } 
 1520          else 
 1521          { 
 1522             len22      = len2/2; 
 1523             second_cut = pivot + len22; 
 1524             first_cut  = Upper(compareFunctor, from, pivot, *GetItemAtUnchecked(second_cut), optCookie); 
 1525             len11      = first_cut - from; 
 1526          } 
 1527 
 1528          // do a rotation
 1529          if ((pivot!=first_cut)&&(pivot!=second_cut)) 
 1530          {
 1531             // find the greatest common denominator of (pivot-first_cut) and (second_cut-first_cut)
 1532             uint32 n = pivot-first_cut;
 1533             {
 1534                uint32 m = second_cut-first_cut;
 1535                while(n!=0) 
 1536                {
 1537                   uint32 t = m % n; 
 1538                   m=n; 
 1539                   n=t;
 1540                } 
 1541                n = m;
 1542             }
 1543 
 1544             while(n--) 
 1545             {
 1546                ItemType val = QQ_PlunderItem(*GetItemAtUnchecked(first_cut+n)); 
 1547                const uint32 shift = pivot - first_cut;
 1548                uint32 p1 = first_cut+n;
 1549                uint32 p2 = p1+shift; 
 1550                while (p2 != first_cut + n) 
 1551                { 
 1552                   ReplaceItemAt(p1, QQ_PlunderItem(*GetItemAtUnchecked(p2)));
 1553                   p1 = p2; 
 1554                   if (second_cut - p2 > shift) p2 += shift; 
 1555                                           else p2  = first_cut + (shift - (second_cut - p2)); 
 1556                } 
 1557                ReplaceItemAt(p1, QQ_PlunderItem(val));
 1558             }
 1559          }
 1560 
 1561          const uint32 new_mid = first_cut+len22; 
 1562          Merge(compareFunctor, from,    first_cut,  new_mid, len11,        len22,        optCookie); 
 1563          Merge(compareFunctor, new_mid, second_cut, to,      len1 - len11, len2 - len22, optCookie); 
 1564       }
 1565    }
 1566 }
 1567 
 1568 
 1569 template <class ItemType>
 1570 template <class CompareFunctorType>
 1571 uint32 
 1572 Queue<ItemType>::
 1573 Lower(const CompareFunctorType & compareFunctor, uint32 from, uint32 to, const ItemType & val, void * optCookie) const
 1574 {
 1575    if (to > from)
 1576    {
 1577       uint32 len = to - from;
 1578       while(len > 0) 
 1579       {
 1580          const uint32 half = len/2; 
 1581          const uint32 mid  = from + half; 
 1582          if (compareFunctor.Compare(*(GetItemAtUnchecked(mid)), val, optCookie) < 0) 
 1583          {
 1584             from = mid+1; 
 1585             len  = len - half - 1; 
 1586          } 
 1587          else len = half; 
 1588       }
 1589    }
 1590    return from; 
 1591 } 
 1592 
 1593 template <class ItemType>
 1594 template <class CompareFunctorType>
 1595 uint32 
 1596 Queue<ItemType>::
 1597 Upper(const CompareFunctorType & compareFunctor, uint32 from, uint32 to, const ItemType & val, void * optCookie) const 
 1598 {
 1599    if (to > from)
 1600    {
 1601       uint32 len = to - from;
 1602       while(len > 0) 
 1603       { 
 1604          const uint32 half = len/2; 
 1605          const uint32 mid  = from + half; 
 1606          if (compareFunctor.Compare(val, *(GetItemAtUnchecked(mid)), optCookie) < 0) len = half; 
 1607          else 
 1608          {
 1609             from = mid+1; 
 1610             len  = len - half -1; 
 1611          } 
 1612       } 
 1613    }
 1614    return from; 
 1615 }
 1616 
 1617 template <class ItemType>
 1618 const ItemType * 
 1619 Queue<ItemType> :: GetArrayPointerAux(uint32 whichArray, uint32 & retLength) const
 1620 {
 1621    if (_itemCount > 0)
 1622    {
 1623       switch(whichArray)
 1624       {
 1625          case 0:  
 1626             retLength = (_headIndex <= _tailIndex) ? (_tailIndex-_headIndex)+1 : (_queueSize-_headIndex);
 1627             return &_queue[_headIndex];
 1628          break;
 1629 
 1630          case 1:
 1631             if (_headIndex > _tailIndex)
 1632             {
 1633                retLength = _tailIndex+1;
 1634                return &_queue[0];
 1635             }
 1636          break;
 1637       }
 1638    }
 1639 
 1640    retLength = 0;
 1641    return NULL;
 1642 }
 1643 
 1644 template <class ItemType>
 1645 void
 1646 Queue<ItemType>::SwapContents(Queue<ItemType> & that)
 1647 {
 1648    if (&that == this) return;  // no point trying to swap with myself
 1649 
 1650    const bool thisSmall = (this->_queue == this->_smallQueue);
 1651    const bool thatSmall = (that._queue  == that._smallQueue);
 1652 
 1653    if ((thisSmall)&&(thatSmall))
 1654    {
 1655       // First, move any extra items from the longer queue to the shorter one...
 1656       const uint32 commonSize    = muscleMin(GetNumItems(), that.GetNumItems());
 1657       const int32 sizeDiff       = ((int32)GetNumItems())-((int32)that.GetNumItems());
 1658       Queue<ItemType> & copyTo   = (sizeDiff > 0) ? that : *this;
 1659       Queue<ItemType> & copyFrom = (sizeDiff > 0) ? *this : that;
 1660       (void) copyTo.AddTailMulti(copyFrom, commonSize); // guaranteed not to fail
 1661       (void) copyFrom.EnsureSize(commonSize, true);     // remove the copied items from (copyFrom)
 1662 
 1663       // Then just swap the elements that are present in both arrays
 1664       for (uint32 i=0; i<commonSize; i++) muscleSwap((*this)[i], that[i]);
 1665    }
 1666    else if (thisSmall) SwapContentsAux(that);
 1667    else if (thatSmall) that.SwapContentsAux(*this);
 1668    else
 1669    {
 1670       // this case is easy, we can just swizzle the pointers around
 1671       muscleSwap(_queue,     that._queue);
 1672       muscleSwap(_queueSize, that._queueSize);
 1673       muscleSwap(_headIndex, that._headIndex);
 1674       muscleSwap(_tailIndex, that._tailIndex);
 1675       muscleSwap(_itemCount, that._itemCount);
 1676    }
 1677 }
 1678 
 1679 template <class ItemType>
 1680 void
 1681 Queue<ItemType>::SwapContentsAux(Queue<ItemType> & largeThat)
 1682 {
 1683    // First, copy over our (small) contents to his small-buffer
 1684    const uint32 ni = GetNumItems();
 1685    for (uint32 i=0; i<ni; i++) largeThat._smallQueue[i] = QQ_PlunderItem((*this)[i]);
 1686 
 1687    // Now adopt his dynamic buffer
 1688    _queue     = largeThat._queue;
 1689    _queueSize = largeThat._queueSize;
 1690    if (_queueSize > 0)
 1691    {
 1692       _headIndex = largeThat._headIndex;
 1693       _tailIndex = largeThat._tailIndex;
 1694    }
 1695    else _headIndex = _tailIndex = 0;  // avoid static-analyzer warning in this case
 1696    
 1697    // And point him back at his small-buffer
 1698    if (ni > 0)
 1699    {
 1700       largeThat._queue     = largeThat._smallQueue;
 1701       largeThat._queueSize = ARRAYITEMS(largeThat._smallQueue);
 1702       largeThat._headIndex = 0;
 1703       largeThat._tailIndex = ni-1;
 1704    }
 1705    else
 1706    {
 1707       largeThat._queue     = NULL;
 1708       largeThat._queueSize = 0;
 1709       // headIndex and tailIndex are undefined in this case anyway
 1710    }
 1711    
 1712    muscleSwap(_itemCount, largeThat._itemCount);
 1713 }
 1714 
 1715 template <class ItemType>
 1716 bool
 1717 Queue<ItemType>::StartsWith(const Queue<ItemType> & prefixQueue) const
 1718 {
 1719    if (prefixQueue.GetNumItems() > GetNumItems()) return false;
 1720    const uint32 prefixQueueLen = prefixQueue.GetNumItems();
 1721    for (uint32 i=0; i<prefixQueueLen; i++) if (!(prefixQueue[i] == (*this)[i])) return false;
 1722    return true;
 1723 }
 1724 
 1725 template <class ItemType>
 1726 bool
 1727 Queue<ItemType>::EndsWith(const Queue<ItemType> & suffixQueue) const
 1728 {
 1729    if (suffixQueue.GetNumItems() > GetNumItems()) return false;
 1730    int32 lastToCheck = GetNumItems()-suffixQueue.GetNumItems();
 1731    for (int32 i=GetNumItems()-1; i>=lastToCheck; i--) if (!(suffixQueue[i] == (*this)[i])) return false;
 1732    return true;
 1733 }
 1734 
 1735 template <class ItemType>
 1736 void
 1737 Queue<ItemType>::Normalize()
 1738 {
 1739    if (IsNormalized() == false)
 1740    {
 1741       if (_itemCount*2 <= _queueSize)
 1742       {
 1743          // There's enough space in the middle of the
 1744          // array to just copy the items over, yay!  This
 1745          // is more efficient when there are just a few
 1746          // valid items in a large array.
 1747          const bool isPerItemClearNecessary = IsPerItemClearNecessary();
 1748          const ItemType & defaultItem       = GetDefaultItem();
 1749          const uint32 startAt               = _tailIndex+1;
 1750          for (uint32 i=0; i<_itemCount; i++) 
 1751          {
 1752             ItemType & from = (*this)[i];
 1753             _queue[startAt+i] = from;
 1754             if (isPerItemClearNecessary) from = defaultItem;  // clear the old slot to avoid leaving extra Refs, etc
 1755          }
 1756          _headIndex = startAt;
 1757          _tailIndex = startAt+_itemCount-1; 
 1758       }
 1759       else
 1760       {
 1761          // There's not enough room to do a simple copy,
 1762          // so we'll rotate the entire array using this
 1763          // algorithm that was written by Paul Hsieh, taken
 1764          // from http://www.azillionmonkeys.com/qed/case8.html
 1765          uint32 c = 0;
 1766          for (uint32 v = 0; c<_queueSize; v++)
 1767          {
 1768             uint32 t  = v;
 1769             uint32 tp = v + _headIndex;
 1770             const ItemType tmp = _queue[v];
 1771             c++;
 1772             while(tp != v) 
 1773             {
 1774                _queue[t] = _queue[tp];
 1775                t = tp;
 1776                tp += _headIndex;
 1777                if (tp >= _queueSize) tp -= _queueSize;
 1778                c++;
 1779             }
 1780             _queue[t] = tmp;
 1781          }
 1782          _headIndex = 0;
 1783          _tailIndex = _itemCount-1;
 1784       }
 1785    }
 1786 }
 1787 
 1788 template <class ItemType>
 1789 ItemType * 
 1790 Queue<ItemType>::ReleaseRawDataArray(uint32 * optRetArrayLen)
 1791 {
 1792    ItemType * ret = NULL;
 1793 
 1794    if (optRetArrayLen) *optRetArrayLen = _queueSize;
 1795 
 1796    if (_queue == _smallQueue)
 1797    {
 1798       // Oops, we don't have a dynamically-created array to release!  So we'll create one
 1799       // to return, just so the user doesn't have to worry about handling a special-case.
 1800       ret = newnothrow ItemType[_queueSize];
 1801       if (ret)
 1802       {
 1803          for (uint32 i=0; i<_itemCount; i++) ret[i] = (*this)[i];
 1804          Clear();
 1805       }
 1806       else WARN_OUT_OF_MEMORY;
 1807    }
 1808    else
 1809    {
 1810       // In the non-small-Queue case we can just pass out the array-pointer
 1811       ret        = _queue;
 1812       _queue     = NULL;
 1813       _queueSize = 0;
 1814       _itemCount = 0;
 1815    }
 1816    return ret;
 1817 }
 1818 
 1819 template <class ItemType>
 1820 void 
 1821 Queue<ItemType>::AdoptRawDataArray(uint32 numItemsInArray, ItemType * array, uint32 validItemCount)
 1822 {
 1823    Clear(true);
 1824    if (array)
 1825    {
 1826       _queue     = array;
 1827       _queueSize = numItemsInArray;
 1828       _itemCount = muscleMin(numItemsInArray, validItemCount);
 1829       _headIndex = 0;
 1830       _tailIndex = 0;
 1831    }
 1832 }
 1833 
 1834 } // end namespace muscle
 1835 
 1836 #endif