xpcom/glue/nsTPriorityQueue.h

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is C++ priority queue implementation.
  17  *
  18  * The Initial Developer of the Original Code is Brian Birtles.
  19  * Portions created by the Initial Developer are Copyright (C) 2009
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   Brian Birtles <birtles@gmail.com>
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either of the GNU General Public License Version 2 or later (the "GPL"),
  27  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #ifndef NS_TPRIORITY_QUEUE_H_
  40 #define NS_TPRIORITY_QUEUE_H_
  41
  42 #include "nsTArray.h"
  43 #include "nsDebug.h"
  44
  45 /**
  46  * A templatized priority queue data structure that uses an nsTArray to serve as
  47  * a binary heap. The default comparator causes this to act like a min-heap.
  48  * Only the LessThan method of the comparator is used.
  49  */
  50 template<class T, class Compare = nsDefaultComparator<T, T> >
  51 class nsTPriorityQueue
  52 {
  53 public:
  54   typedef typename nsTArray<T>::size_type size_type;
  55
  56   /**
  57    * Default constructor also creates a comparator object using the default
  58    * constructor for type Compare.
  59    */
  60   nsTPriorityQueue() : mCompare(Compare()) { }
  61
  62   /**
  63    * Constructor to allow a specific instance of a comparator object to be
  64    * used.
  65    */
  66   nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) { }
  67
  68   /**
  69    * Copy constructor
  70    */
  71   nsTPriorityQueue(const nsTPriorityQueue& aOther)
  72     : mElements(aOther.mElements),
  73       mCompare(aOther.mCompare)
  74   { }
  75
  76   /**
  77    * @return True if the queue is empty or false otherwise.
  78    */
  79   PRBool IsEmpty() const
  80   {
  81     return mElements.IsEmpty();
  82   }
  83
  84   /**
  85    * @return The number of elements in the queue.
  86    */
  87   size_type Length() const
  88   {
  89     return mElements.Length();
  90   }
  91
  92   /**
  93    * @return The topmost element in the queue without changing the queue. This
  94    * is the element 'a' such that there is no other element 'b' in the queue for
  95    * which Compare(b, a) returns PR_TRUE. (Since this container does not check
  96    * for duplicate entries there may exist 'b' for which Compare(a, b) returns
  97    * PR_FALSE.)
  98    */
  99   const T& Top() const
 100   {
 101     NS_ABORT_IF_FALSE(!mElements.IsEmpty(), "Empty queue");
 102     return mElements[0];
 103   }
 104
 105   /**
 106    * Adds an element to the queue
 107    * @param aElement The element to add
 108    * @return PR_TRUE on success, PR_FALSE on out of memory.
 109    */
 110   PRBool Push(const T& aElement)
 111   {
 112     T* elem = mElements.AppendElement(aElement);
 113     if (!elem)
 114       return PR_FALSE; // Out of memory
 115
 116     // Sift up
 117     size_type i = mElements.Length() - 1;
 118     while (i) {
 119       size_type parent = (size_type)((i - 1) / 2);
 120       if (mCompare.LessThan(mElements[parent], mElements[i])) {
 121         break;
 122       }
 123       Swap(i, parent);
 124       i = parent;
 125     }
 126
 127     return PR_TRUE;
 128   }
 129
 130   /**
 131    * Removes and returns the top-most element from the queue.
 132    * @return The topmost element, that is, the element 'a' such that there is no
 133    * other element 'b' in the queue for which Compare(b, a) returns PR_TRUE.
 134    * @see Top()
 135    */
 136   T Pop()
 137   {
 138     NS_ABORT_IF_FALSE(!mElements.IsEmpty(), "Empty queue");
 139     T pop = mElements[0];
 140
 141     // Move last to front
 142     mElements[0] = mElements[mElements.Length() - 1];
 143     mElements.TruncateLength(mElements.Length() - 1);
 144
 145     // Sift down
 146     size_type i = 0;
 147     while (2*i + 1 < mElements.Length()) {
 148       size_type swap = i;
 149       size_type l_child = 2*i + 1;
 150       if (mCompare.LessThan(mElements[l_child], mElements[i])) {
 151         swap = l_child;
 152       }
 153       size_type r_child = l_child + 1;
 154       if (r_child < mElements.Length() &&
 155           mCompare.LessThan(mElements[r_child], mElements[swap])) {
 156         swap = r_child;
 157       }
 158       if (swap == i) {
 159         break;
 160       }
 161       Swap(i, swap);
 162       i = swap;
 163     }
 164
 165     return pop;
 166   }
 167
 168   /**
 169    * Removes all elements from the queue.
 170    */
 171   void Clear()
 172   {
 173     mElements.Clear();
 174   }
 175
 176   /**
 177    * Provides readonly access to the queue elements as an array. Generally this
 178    * should be avoided but may be needed in some situations such as when the
 179    * elements contained in the queue need to be enumerated for cycle-collection.
 180    * @return A pointer to the first element of the array.  If the array is
 181    * empty, then this pointer must not be dereferenced.
 182    */
 183   const T* Elements() const
 184   {
 185     return mElements.Elements();
 186   }
 187
 188 protected:
 189   /**
 190    * Swaps the elements at the specified indices.
 191    */
 192   void Swap(size_type aIndexA, size_type aIndexB)
 193   {
 194     T temp = mElements[aIndexA];
 195     mElements[aIndexA] = mElements[aIndexB];
 196     mElements[aIndexB] = temp;
 197   }
 198
 199   nsTArray<T> mElements;
 200   Compare mCompare; // Comparator object
 201 };
 202
 203 #endif // NS_TPRIORITY_QUEUE_H_