xpcom/tests/TestPriorityQueue.cpp

   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 mozilla.org code.
  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 #include "nsTPriorityQueue.h"
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42
  43 template<class T, class Compare>
  44 void
  45 CheckPopSequence(const nsTPriorityQueue<T, Compare>& aQueue,
  46                  const T* aExpectedSequence, const PRUint32 aSequenceLength)
  47 {
  48   nsTPriorityQueue<T, Compare> copy(aQueue);
  49
  50   for (PRUint32 i = 0; i < aSequenceLength; i++) {
  51     if (copy.IsEmpty()) {
  52       printf("Number of elements in the queue is too short by %d.\n",
  53           aSequenceLength - i);
  54       exit(-1);
  55     }
  56
  57     T pop = copy.Pop();
  58     if (pop != aExpectedSequence[i]) {
  59       printf("Unexpected value in pop sequence at position %d\n", i);
  60       printf("  Sequence:");
  61       for (size_t j = 0; j < aSequenceLength; j++) {
  62         printf(" %d", aExpectedSequence[j]);
  63         if (j == i) {
  64           printf("**");
  65         }
  66       }
  67       printf("\n            ** Got %d instead\n", pop);
  68       exit(-1);
  69     }
  70   }
  71
  72   if (!copy.IsEmpty()) {
  73     printf("Number of elements in the queue is too long by %d.\n",
  74         copy.Length());
  75     exit(-1);
  76   }
  77 }
  78
  79 template<class A>
  80 class MaxCompare {
  81 public:
  82   PRBool LessThan(const A& a, const A& b) {
  83     return a > b;
  84   }
  85 };
  86
  87 int main()
  88 {
  89   nsTPriorityQueue<int> queue;
  90
  91   NS_ABORT_IF_FALSE(queue.IsEmpty(), "Queue not initially empty");
  92
  93   queue.Push(8);
  94   queue.Push(6);
  95   queue.Push(4);
  96   queue.Push(2);
  97   queue.Push(10);
  98   queue.Push(6);
  99   NS_ABORT_IF_FALSE(queue.Top() == 2, "Unexpected queue top");
 100   NS_ABORT_IF_FALSE(queue.Length() == 6, "Unexpected queue length");
 101   NS_ABORT_IF_FALSE(!queue.IsEmpty(), "Queue empty when populated");
 102   int expected[] = { 2, 4, 6, 6, 8, 10 };
 103   CheckPopSequence(queue, expected, sizeof(expected) / sizeof(expected[0]));
 104
 105   // copy ctor is tested by using CheckPopSequence, but check default assignment
 106   // operator
 107   nsTPriorityQueue<int> queue2;
 108   queue2 = queue;
 109   CheckPopSequence(queue2, expected, sizeof(expected) / sizeof(expected[0]));
 110
 111   queue.Clear();
 112   NS_ABORT_IF_FALSE(queue.IsEmpty(), "Queue not emptied by Clear");
 113
 114   // try same sequence with a max heap
 115   nsTPriorityQueue<int, MaxCompare<int> > max_queue;
 116   max_queue.Push(8);
 117   max_queue.Push(6);
 118   max_queue.Push(4);
 119   max_queue.Push(2);
 120   max_queue.Push(10);
 121   max_queue.Push(6);
 122   NS_ABORT_IF_FALSE(max_queue.Top() == 10, "Unexpected queue top for max heap");
 123   int expected_max[] = { 10, 8, 6, 6, 4, 2 };
 124   CheckPopSequence(max_queue, expected_max,
 125       sizeof(expected_max) / sizeof(expected_max[0]));
 126
 127   return 0;
 128 }