The Tor Browser / file diff

     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/xpcom/tests/TestPriorityQueue.cpp	Wed Dec 31 06:09:35 2014 +0100
     1.3 @@ -0,0 +1,96 @@
     1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
     1.5 +/* vim:set ts=2 sw=2 sts=2 et cindent: */
     1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
     1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
     1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
     1.9 +
    1.10 +#include "nsTPriorityQueue.h"
    1.11 +#include <stdio.h>
    1.12 +#include <stdlib.h>
    1.13 +
    1.14 +template<class T, class Compare>
    1.15 +void
    1.16 +CheckPopSequence(const nsTPriorityQueue<T, Compare>& aQueue,
    1.17 +                 const T* aExpectedSequence, const uint32_t aSequenceLength)
    1.18 +{
    1.19 +  nsTPriorityQueue<T, Compare> copy(aQueue);
    1.20 +
    1.21 +  for (uint32_t i = 0; i < aSequenceLength; i++) {
    1.22 +    if (copy.IsEmpty()) {
    1.23 +      printf("Number of elements in the queue is too short by %d.\n",
    1.24 +          aSequenceLength - i);
    1.25 +      exit(-1);
    1.26 +    }
    1.27 +
    1.28 +    T pop = copy.Pop();
    1.29 +    if (pop != aExpectedSequence[i]) {
    1.30 +      printf("Unexpected value in pop sequence at position %d\n", i);
    1.31 +      printf("  Sequence:");
    1.32 +      for (size_t j = 0; j < aSequenceLength; j++) {
    1.33 +        printf(" %d", aExpectedSequence[j]);
    1.34 +        if (j == i) {
    1.35 +          printf("**");
    1.36 +        }
    1.37 +      }
    1.38 +      printf("\n            ** Got %d instead\n", pop);
    1.39 +      exit(-1);
    1.40 +    }
    1.41 +  }
    1.42 +
    1.43 +  if (!copy.IsEmpty()) {
    1.44 +    printf("Number of elements in the queue is too long by %d.\n",
    1.45 +        copy.Length());
    1.46 +    exit(-1);
    1.47 +  }
    1.48 +}
    1.49 +
    1.50 +template<class A>
    1.51 +class MaxCompare {
    1.52 +public:
    1.53 +  bool LessThan(const A& a, const A& b) {
    1.54 +    return a > b;
    1.55 +  }
    1.56 +};
    1.57 +
    1.58 +int main()
    1.59 +{
    1.60 +  nsTPriorityQueue<int> queue;
    1.61 +
    1.62 +  NS_ABORT_IF_FALSE(queue.IsEmpty(), "Queue not initially empty");
    1.63 +
    1.64 +  queue.Push(8);
    1.65 +  queue.Push(6);
    1.66 +  queue.Push(4);
    1.67 +  queue.Push(2);
    1.68 +  queue.Push(10);
    1.69 +  queue.Push(6);
    1.70 +  NS_ABORT_IF_FALSE(queue.Top() == 2, "Unexpected queue top");
    1.71 +  NS_ABORT_IF_FALSE(queue.Length() == 6, "Unexpected queue length");
    1.72 +  NS_ABORT_IF_FALSE(!queue.IsEmpty(), "Queue empty when populated");
    1.73 +  int expected[] = { 2, 4, 6, 6, 8, 10 };
    1.74 +  CheckPopSequence(queue, expected, sizeof(expected) / sizeof(expected[0]));
    1.75 +
    1.76 +  // copy ctor is tested by using CheckPopSequence, but check default assignment
    1.77 +  // operator
    1.78 +  nsTPriorityQueue<int> queue2;
    1.79 +  queue2 = queue;
    1.80 +  CheckPopSequence(queue2, expected, sizeof(expected) / sizeof(expected[0]));
    1.81 +
    1.82 +  queue.Clear();
    1.83 +  NS_ABORT_IF_FALSE(queue.IsEmpty(), "Queue not emptied by Clear");
    1.84 +
    1.85 +  // try same sequence with a max heap
    1.86 +  nsTPriorityQueue<int, MaxCompare<int> > max_queue;
    1.87 +  max_queue.Push(8);
    1.88 +  max_queue.Push(6);
    1.89 +  max_queue.Push(4);
    1.90 +  max_queue.Push(2);
    1.91 +  max_queue.Push(10);
    1.92 +  max_queue.Push(6);
    1.93 +  NS_ABORT_IF_FALSE(max_queue.Top() == 10, "Unexpected queue top for max heap");
    1.94 +  int expected_max[] = { 10, 8, 6, 6, 4, 2 };
    1.95 +  CheckPopSequence(max_queue, expected_max,
    1.96 +      sizeof(expected_max) / sizeof(expected_max[0]));
    1.97 +
    1.98 +  return 0;
    1.99 +}