util/tests/heap_test.cc

/*
 * Copyright (C) 2017 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "chre/util/heap.h"
#include "gtest/gtest.h"

#include <algorithm>
#include <array>

using chre::DynamicVector;
using chre::FixedSizeVector;

TEST(HeapDeathTest, PushHeapWhenEmpty) {
  DynamicVector<int> v;
  std::less<int> comp;
  EXPECT_DEATH(chre::push_heap(v, comp), "");
}

TEST(HeapDeathTest, PopHeapWhenEmpty) {
  DynamicVector<int> v;
  std::less<int> comp;
  EXPECT_DEATH(chre::pop_heap(v, comp), "");
}

TEST(HeapTest, NestedPushPopHeap) {
  DynamicVector<int> v;
  std::less<int> comp;

  // generate random test data
  const size_t MaxSize = 1000;
  std::array<int, MaxSize> array;
  std::array<int, MaxSize> array_sorted;
  std::srand(0xcafe);
  for (size_t i = 0; i < MaxSize; ++i) {
    array[i] = std::rand();
    array_sorted[i] = array[i];
  }

  // make sure the popped data is in the right order of various array sizes.
  for (size_t s = 1; s < MaxSize + 1; ++s) {
    for (size_t i = 0; i < s; ++i) {
      v.push_back(array[i]);
      chre::push_heap(v, comp);
    }

    std::sort(array_sorted.begin(), array_sorted.begin() + s,
              std::greater<int>());

    for (size_t i = 0; i < s; ++i) {
      chre::pop_heap(v, comp);
      EXPECT_EQ(array_sorted[i], v[v.size() - 1]);
      v.erase(v.size() - 1);
    }
  }
}

TEST(HeapDeathTest, RemoveHeapWithInvalidIndex) {
  DynamicVector<int> v;
  std::less<int> comp;

  v.push_back(0);
  chre::push_heap(v, comp);
  EXPECT_DEATH(chre::remove_heap(v, 1, comp), "");
}

TEST(HeapTest, NestedRemoveHeap) {
  DynamicVector<int> v;
  std::less<int> comp;

  // generate random test data
  const size_t MaxSize = 1000;
  std::array<int, MaxSize> array;
  std::array<int, MaxSize> array_sorted;
  std::srand(0xcafe);
  for (size_t i = 0; i < MaxSize; ++i) {
    array[i] = std::rand();
    array_sorted[i] = array[i];
  }

  for (size_t s = 1; s < MaxSize + 1; ++s) {
    for (size_t i = 0; i < s; ++i) {
      v.push_back(array[i]);
      chre::push_heap(v, comp);
    }

    std::sort(array_sorted.begin(), array_sorted.begin() + s,
              std::greater<int>());

    // randomly remove one
    chre::remove_heap(v, std::rand() % s, comp);
    int data = v[v.size() - 1];
    v.erase(v.size() - 1);

    for (size_t i = 0; i < s; ++i) {
      if (array_sorted[i] == data) {
        continue;
      }

      chre::pop_heap(v, comp);
      EXPECT_EQ(array_sorted[i], v[v.size() - 1]);
      v.erase(v.size() - 1);
    }
  }
}

TEST(HeapTest, FixedSizeVectorMinHeap) {
  FixedSizeVector<int, 16> v;

  for (size_t i = 0; i < 5; ++i) {
    v.push_back(i);
    chre::push_heap(v, std::greater<int>());
  }

  for (size_t i = 0; i < 5; ++i) {
    chre::pop_heap(v, std::greater<int>());
    EXPECT_EQ(i, v[v.size() - 1]);
    v.erase(v.size() - 1);
  }
}