Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
       2             : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
       3             : /* This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       5             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #ifndef NS_TPRIORITY_QUEUE_H_
       8             : #define NS_TPRIORITY_QUEUE_H_
       9             : 
      10             : #include "nsTArray.h"
      11             : #include "nsDebug.h"
      12             : 
      13             : /**
      14             :  * A templatized priority queue data structure that uses an nsTArray to serve as
      15             :  * a binary heap. The default comparator causes this to act like a min-heap.
      16             :  * Only the LessThan method of the comparator is used.
      17             :  */
      18             : template<class T, class Compare = nsDefaultComparator<T, T>>
      19           0 : class nsTPriorityQueue
      20             : {
      21             : public:
      22             :   typedef typename nsTArray<T>::size_type size_type;
      23             : 
      24             :   /**
      25             :    * Default constructor also creates a comparator object using the default
      26             :    * constructor for type Compare.
      27             :    */
      28          44 :   nsTPriorityQueue() : mCompare(Compare()) {}
      29             : 
      30             :   /**
      31             :    * Constructor to allow a specific instance of a comparator object to be
      32             :    * used.
      33             :    */
      34             :   explicit nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) {}
      35             : 
      36             :   /**
      37             :    * Copy constructor
      38             :    */
      39             :   nsTPriorityQueue(const nsTPriorityQueue& aOther)
      40             :     : mElements(aOther.mElements)
      41             :     , mCompare(aOther.mCompare)
      42             :   {
      43             :   }
      44             : 
      45             :   /**
      46             :    * @return True if the queue is empty or false otherwise.
      47             :    */
      48          58 :   bool IsEmpty() const { return mElements.IsEmpty(); }
      49             : 
      50             :   /**
      51             :    * @return The number of elements in the queue.
      52             :    */
      53         103 :   size_type Length() const { return mElements.Length(); }
      54             : 
      55             :   /**
      56             :    * @return The topmost element in the queue without changing the queue. This
      57             :    * is the element 'a' such that there is no other element 'b' in the queue for
      58             :    * which Compare(b, a) returns true. (Since this container does not check
      59             :    * for duplicate entries there may exist 'b' for which Compare(a, b) returns
      60             :    * false.)
      61             :    */
      62           0 :   const T& Top() const
      63             :   {
      64           0 :     MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
      65           0 :     return mElements[0];
      66             :   }
      67             : 
      68             :   /**
      69             :    * Adds an element to the queue
      70             :    * @param aElement The element to add
      71             :    * @return true on success, false on out of memory.
      72             :    */
      73           0 :   bool Push(const T& aElement)
      74             :   {
      75           0 :     T* elem = mElements.AppendElement(aElement);
      76           0 :     if (!elem) {
      77           0 :       return false;  // Out of memory
      78             :     }
      79             : 
      80             :     // Sift up
      81           0 :     size_type i = mElements.Length() - 1;
      82           0 :     while (i) {
      83           0 :       size_type parent = (size_type)((i - 1) / 2);
      84           0 :       if (mCompare.LessThan(mElements[parent], mElements[i])) {
      85           0 :         break;
      86             :       }
      87           0 :       Swap(i, parent);
      88           0 :       i = parent;
      89             :     }
      90             : 
      91           0 :     return true;
      92             :   }
      93             : 
      94             :   /**
      95             :    * Removes and returns the top-most element from the queue.
      96             :    * @return The topmost element, that is, the element 'a' such that there is no
      97             :    * other element 'b' in the queue for which Compare(b, a) returns true.
      98             :    * @see Top()
      99             :    */
     100           0 :   T Pop()
     101             :   {
     102           0 :     MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
     103           0 :     T pop = mElements[0];
     104             : 
     105             :     // Move last to front
     106           0 :     mElements[0] = mElements[mElements.Length() - 1];
     107           0 :     mElements.TruncateLength(mElements.Length() - 1);
     108             : 
     109             :     // Sift down
     110           0 :     size_type i = 0;
     111           0 :     while (2 * i + 1 < mElements.Length()) {
     112           0 :       size_type swap = i;
     113           0 :       size_type l_child = 2 * i + 1;
     114           0 :       if (mCompare.LessThan(mElements[l_child], mElements[i])) {
     115           0 :         swap = l_child;
     116             :       }
     117           0 :       size_type r_child = l_child + 1;
     118           0 :       if (r_child < mElements.Length() &&
     119           0 :           mCompare.LessThan(mElements[r_child], mElements[swap])) {
     120           0 :         swap = r_child;
     121             :       }
     122           0 :       if (swap == i) {
     123           0 :         break;
     124             :       }
     125           0 :       Swap(i, swap);
     126           0 :       i = swap;
     127             :     }
     128             : 
     129           0 :     return pop;
     130             :   }
     131             : 
     132             :   /**
     133             :    * Removes all elements from the queue.
     134             :    */
     135          58 :   void Clear() { mElements.Clear(); }
     136             : 
     137             :   /**
     138             :    * Provides readonly access to the queue elements as an array. Generally this
     139             :    * should be avoided but may be needed in some situations such as when the
     140             :    * elements contained in the queue need to be enumerated for cycle-collection.
     141             :    * @return A pointer to the first element of the array.  If the array is
     142             :    * empty, then this pointer must not be dereferenced.
     143             :    */
     144         206 :   const T* Elements() const { return mElements.Elements(); }
     145             : 
     146             : protected:
     147             :   /**
     148             :    * Swaps the elements at the specified indices.
     149             :    */
     150           0 :   void Swap(size_type aIndexA, size_type aIndexB)
     151             :   {
     152           0 :     T temp = mElements[aIndexA];
     153           0 :     mElements[aIndexA] = mElements[aIndexB];
     154           0 :     mElements[aIndexB] = temp;
     155           0 :   }
     156             : 
     157             :   nsTArray<T> mElements;
     158             :   Compare mCompare; // Comparator object
     159             : };
     160             : 
     161             : #endif // NS_TPRIORITY_QUEUE_H_