utility/tests/PrimeNumber_unittest.cpp

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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 <cstddef>
#include <cstdint>
#include <limits>

#include "gtest/gtest.h"
#include "utility/PrimeNumber.hpp"

namespace quickstep {

TEST(PrimeNumberTest, GetNextPrimeTest) {
  // Test some small primes.
  EXPECT_EQ(2u, get_next_prime_number(0));
  EXPECT_EQ(2u, get_next_prime_number(2));
  EXPECT_EQ(3u, get_next_prime_number(3));
  EXPECT_EQ(5u, get_next_prime_number(4));
  EXPECT_EQ(5u, get_next_prime_number(5));
  EXPECT_EQ(7u, get_next_prime_number(6));
  EXPECT_EQ(53u, get_next_prime_number(49));
  EXPECT_EQ(211u, get_next_prime_number(200));
  EXPECT_EQ(907u, get_next_prime_number(890));
  EXPECT_EQ(10007u, get_next_prime_number(10000));
  EXPECT_EQ(30047u, get_next_prime_number(30030));
  EXPECT_EQ(65521u, get_next_prime_number(65520));
  EXPECT_EQ(65521u, get_next_prime_number(65521));

  // Try larger, non-baked-in primes.
  EXPECT_EQ(65537u, get_next_prime_number(65536));
  EXPECT_EQ(101917u, get_next_prime_number(101900));

  // Try some big Mersenne primes.
  EXPECT_EQ((1u << 17) - 1, get_next_prime_number(131064));
  EXPECT_EQ((1u << 17) - 1, get_next_prime_number(131071));

  EXPECT_EQ((1u << 19) - 1, get_next_prime_number(524270));
  EXPECT_EQ((1u << 19) - 1, get_next_prime_number(524287));

  EXPECT_EQ((1u << 31) - 1, get_next_prime_number(2147483647u));

  if (sizeof(std::size_t) >= 8) {
    EXPECT_EQ((UINT64_C(1) << 61) - 1,
              get_next_prime_number(
                  static_cast<std::size_t>(UINT64_C(2305843009213693951))));

    // Search for the largest 64-bit prime, starting from the
    // second largest + 1.
    EXPECT_EQ(static_cast<std::size_t>(UINT64_C(18446744073709551557)),
              get_next_prime_number(
                  static_cast<std::size_t>(UINT64_C(18446744073709551534))));
  }
}

TEST(PrimeNumberTest, GetPreviousPrimeTest) {
  // Numbers smaller than any prime.
  EXPECT_EQ(0u, get_previous_prime_number(0));
  EXPECT_EQ(0u, get_previous_prime_number(1));

  // Test some small primes.
  EXPECT_EQ(2u, get_previous_prime_number(2));
  EXPECT_EQ(3u, get_previous_prime_number(3));
  EXPECT_EQ(3u, get_previous_prime_number(4));
  EXPECT_EQ(5u, get_previous_prime_number(5));
  EXPECT_EQ(7u, get_previous_prime_number(8));
  EXPECT_EQ(47u, get_previous_prime_number(49));
  EXPECT_EQ(199u, get_previous_prime_number(200));
  EXPECT_EQ(887u, get_previous_prime_number(890));
  EXPECT_EQ(9973u, get_previous_prime_number(10000));
  EXPECT_EQ(30029u, get_previous_prime_number(30030));
  EXPECT_EQ(65519u, get_previous_prime_number(65520));
  EXPECT_EQ(65521u, get_previous_prime_number(65521));

  // Try larger, non-baked-in primes.
  EXPECT_EQ(65521u, get_previous_prime_number(65522));
  EXPECT_EQ(65521u, get_previous_prime_number(65536));
  EXPECT_EQ(65537u, get_previous_prime_number(65537));
  EXPECT_EQ(65537u, get_previous_prime_number(65538));
  EXPECT_EQ(101891u, get_previous_prime_number(101900));

  // Try some big Mersenne primes.
  EXPECT_EQ((1u << 17) - 1, get_previous_prime_number(131071));
  EXPECT_EQ((1u << 17) - 1, get_previous_prime_number(131076));

  EXPECT_EQ((1u << 19) - 1, get_previous_prime_number(524287));
  EXPECT_EQ((1u << 19) - 1, get_previous_prime_number(524290));

  EXPECT_EQ((1u << 31) - 1, get_previous_prime_number(2147483647u));

  if (sizeof(std::size_t) >= 8) {
    EXPECT_EQ((UINT64_C(1) << 61) - 1,
              get_previous_prime_number(
                  static_cast<std::size_t>(UINT64_C(2305843009213693951))));

    // Search for the largest 64-bit prime, starting from the max size_t value.
    EXPECT_EQ(static_cast<std::size_t>(UINT64_C(18446744073709551557)),
              get_previous_prime_number(std::numeric_limits<std::size_t>::max()));
  }
}

}  // namespace quickstep