Core/Utilities/MultiIndexTests.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #include <boost/test/tools/old/interface.hpp>
0010 #include <boost/test/unit_test.hpp>
0011
0012 #include "Acts/Utilities/MultiIndex.hpp"
0013
0014 #include <array>
0015 #include <cstddef>
0016 #include <cstdint>
0017 #include <unordered_set>
0018
0019 #include <boost/mpl/list.hpp>
0020
0021 // 32bit split into a three level hierarchy.
0022 using Index32 = Acts::MultiIndex<std::uint32_t, 16, 8, 8>;
0023 // 64bit split into a four level hierarchy
0024 using Index64 = Acts::MultiIndex<std::uint64_t, 13, 17, 21, 13>;
0025 using Indices = boost::mpl::list<Index32, Index64>;
0026
0027 namespace ActsTests {
0028
0029 BOOST_AUTO_TEST_SUITE(UtilitiesSuite)
0030
0031 BOOST_AUTO_TEST_CASE_TEMPLATE(triviality, T, Indices) {
0032   // verify that the MultiIndex is a trivial type
0033   // this seems to be compiler-dependent; disable for now
0034   BOOST_CHECK(std::is_standard_layout_v<T>);
0035   BOOST_CHECK(std::is_trivially_default_constructible_v<T>);
0036   BOOST_CHECK(std::is_trivially_copy_constructible_v<T>);
0037   BOOST_CHECK(std::is_trivially_move_constructible_v<T>);
0038   BOOST_CHECK((std::is_trivially_assignable_v<T, T>));
0039   BOOST_CHECK((std::is_trivially_copy_assignable_v<T>));
0040   BOOST_CHECK((std::is_trivially_move_assignable_v<T>));
0041 }
0042
0043 BOOST_AUTO_TEST_CASE(index32_construct) {
0044   // construct from encoded value
0045   {
0046     Index32 idx(0xabcd2400u);
0047     BOOST_CHECK_EQUAL(idx.value(), 0xabcd2400u);
0048     BOOST_CHECK_EQUAL(idx.level(0), 0xabcdu);
0049     BOOST_CHECK_EQUAL(idx.level(1), 0x24u);
0050     BOOST_CHECK_EQUAL(idx.level(2), 0x00u);
0051   }
0052 }
0053
0054 BOOST_AUTO_TEST_CASE(index32_set) {
0055   Index32 idx = Index32::Zeros();
0056   // set a specific level within limits
0057   idx.set(0, 24u);
0058   BOOST_CHECK_EQUAL(idx.value(), 0x00180000u);
0059   BOOST_CHECK_EQUAL(idx.level(0), 24u);
0060   BOOST_CHECK_EQUAL(idx.level(1), 0u);
0061   BOOST_CHECK_EQUAL(idx.level(2), 0u);
0062   // set a specific level outside the valid range, should be truncated
0063   BOOST_CHECK_THROW(idx.set(2, 0xfff), std::out_of_range);
0064 }
0065
0066 BOOST_AUTO_TEST_CASE(index32_set_overflow) {
0067   // maximum values for each level
0068   Index32::Value maxValues[] = {
0069       (1u << 16u) - 1u,
0070       (1u << 8u) - 1u,
0071       (1u << 8u) - 1u,
0072   };
0073   // check that values above max are truncated
0074   std::size_t lvl = 0;
0075   for (auto maxValue : maxValues) {
0076     BOOST_CHECK_THROW(Index32::Zeros().set(lvl, maxValue + 1),
0077                       std::out_of_range);
0078     lvl += 1;
0079   }
0080 }
0081
0082 BOOST_AUTO_TEST_CASE(index64_set_overflow) {
0083   // maximum values for each level
0084   Index32::Value maxValues[] = {
0085       (1u << 13u) - 1u,
0086       (1u << 17u) - 1u,
0087       (1u << 21u) - 1u,
0088       (1u << 13u) - 1u,
0089   };
0090   // check that values above max are truncated
0091   std::size_t lvl = 0;
0092   for (auto maxValue : maxValues) {
0093     BOOST_CHECK_THROW(Index64::Zeros().set(lvl, maxValue + 1),
0094                       std::out_of_range);
0095     lvl += 1;
0096   }
0097 }
0098
0099 BOOST_AUTO_TEST_CASE(index32_encode) {
0100   // all three levels set
0101   auto idx3 = Index32::Encode(13u, 14u, 15u);
0102   BOOST_CHECK_EQUAL(idx3.level(0), 13u);
0103   BOOST_CHECK_EQUAL(idx3.level(1), 14u);
0104   BOOST_CHECK_EQUAL(idx3.level(2), 15u);
0105   // first two levels set
0106   auto idx2 = Index32::Encode(13u, 14u);
0107   BOOST_CHECK_EQUAL(idx2.level(0), 13u);
0108   BOOST_CHECK_EQUAL(idx2.level(1), 14u);
0109   BOOST_CHECK_EQUAL(idx2.level(2), 0u);
0110   // only the first level set
0111   auto idx1 = Index32::Encode(13u);
0112   BOOST_CHECK_EQUAL(idx1.level(0), 13u);
0113   BOOST_CHECK_EQUAL(idx1.level(1), 0u);
0114   BOOST_CHECK_EQUAL(idx1.level(2), 0u);
0115   // nothing set
0116   auto idx0 = Index32::Encode();
0117   BOOST_CHECK_EQUAL(idx0, Index32::Zeros());
0118   BOOST_CHECK_EQUAL(idx0.value(), 0u);
0119   BOOST_CHECK_EQUAL(idx0.level(0), 0u);
0120   BOOST_CHECK_EQUAL(idx0.level(1), 0u);
0121   BOOST_CHECK_EQUAL(idx0.level(2), 0u);
0122 }
0123
0124 BOOST_AUTO_TEST_CASE(index64_encode) {
0125   // all four levels set
0126   auto idx4 = Index64::Encode(23u, 14u, 15u, 17u);
0127   BOOST_CHECK_EQUAL(idx4.level(0), 23u);
0128   BOOST_CHECK_EQUAL(idx4.level(1), 14u);
0129   BOOST_CHECK_EQUAL(idx4.level(2), 15u);
0130   BOOST_CHECK_EQUAL(idx4.level(3), 17u);
0131   // first three levels set
0132   auto idx3 = Index64::Encode(23u, 14u, 15u);
0133   BOOST_CHECK_EQUAL(idx3.level(0), 23u);
0134   BOOST_CHECK_EQUAL(idx3.level(1), 14u);
0135   BOOST_CHECK_EQUAL(idx3.level(2), 15u);
0136   BOOST_CHECK_EQUAL(idx3.level(3), 0u);
0137   // first two levels set
0138   auto idx2 = Index64::Encode(23u, 14u);
0139   BOOST_CHECK_EQUAL(idx2.level(0), 23u);
0140   BOOST_CHECK_EQUAL(idx2.level(1), 14u);
0141   BOOST_CHECK_EQUAL(idx2.level(2), 0u);
0142   BOOST_CHECK_EQUAL(idx2.level(3), 0u);
0143   // only the first level set
0144   auto idx1 = Index64::Encode(23u);
0145   BOOST_CHECK_EQUAL(idx1.level(0), 23u);
0146   BOOST_CHECK_EQUAL(idx1.level(1), 0u);
0147   BOOST_CHECK_EQUAL(idx1.level(2), 0u);
0148   BOOST_CHECK_EQUAL(idx1.level(3), 0u);
0149   // nothing set
0150   auto idx0 = Index64::Encode();
0151   BOOST_CHECK_EQUAL(idx0, Index64::Zeros());
0152   BOOST_CHECK_EQUAL(idx0.value(), 0u);
0153   BOOST_CHECK_EQUAL(idx0.level(0), 0u);
0154   BOOST_CHECK_EQUAL(idx0.level(1), 0u);
0155   BOOST_CHECK_EQUAL(idx0.level(2), 0u);
0156   BOOST_CHECK_EQUAL(idx0.level(3), 0u);
0157 }
0158
0159 BOOST_AUTO_TEST_CASE(uint32_sibling) {
0160   auto idx = Index32::Encode(1u, 12u, 123u);
0161   BOOST_CHECK_EQUAL(idx.makeNextSibling(0), Index32::Encode(2u));
0162   BOOST_CHECK_EQUAL(idx.makeNextSibling(1), Index32::Encode(1u, 13u));
0163   BOOST_CHECK_EQUAL(idx.makeNextSibling(2), Index32::Encode(1u, 12u, 124u));
0164 }
0165
0166 BOOST_AUTO_TEST_CASE(uint64_sibling) {
0167   auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
0168   BOOST_CHECK_EQUAL(idx.makeNextSibling(0), Index64::Encode(2u));
0169   BOOST_CHECK_EQUAL(idx.makeNextSibling(1), Index64::Encode(1u, 13u));
0170   BOOST_CHECK_EQUAL(idx.makeNextSibling(2), Index64::Encode(1u, 12u, 124u));
0171   BOOST_CHECK_EQUAL(idx.makeNextSibling(3),
0172                     Index64::Encode(1u, 12u, 123u, 1235u));
0173 }
0174
0175 BOOST_AUTO_TEST_CASE(uint32_descendant) {
0176   auto idx = Index32::Encode(1u, 12u, 123u);
0177   BOOST_CHECK_EQUAL(idx.makeLastDescendant(0), Index32::Encode(1u, 255u, 255u));
0178   BOOST_CHECK_EQUAL(idx.makeLastDescendant(1), Index32::Encode(1u, 12u, 255u));
0179   // last index has no descendant and stays the same
0180   BOOST_CHECK_EQUAL(idx.makeLastDescendant(2), Index32::Encode(1u, 12u, 123u));
0181 }
0182
0183 BOOST_AUTO_TEST_CASE(uint64_descendant) {
0184   auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
0185   // from Index64 definition above
0186   auto max1 = (1u << 17) - 1u;
0187   auto max2 = (1u << 21) - 1u;
0188   auto max3 = (1u << 13) - 1u;
0189   BOOST_CHECK_EQUAL(idx.makeLastDescendant(0),
0190                     Index64::Encode(1u, max1, max2, max3));
0191   BOOST_CHECK_EQUAL(idx.makeLastDescendant(1),
0192                     Index64::Encode(1u, 12u, max2, max3));
0193   BOOST_CHECK_EQUAL(idx.makeLastDescendant(2),
0194                     Index64::Encode(1u, 12u, 123u, max3));
0195   // last index has no descendant and stays the same
0196   BOOST_CHECK_EQUAL(idx.makeLastDescendant(3),
0197                     Index64::Encode(1u, 12u, 123u, 1234u));
0198 }
0199
0200 BOOST_AUTO_TEST_CASE(index32_as_key) {
0201   std::unordered_set<Index32> set;
0202
0203   set.emplace(Index32::Encode(1u, 2u, 4u));
0204   set.emplace(Index32::Encode(1u, 3u, 4u));
0205   set.emplace(Index32::Encode(2u));
0206
0207   BOOST_CHECK(!set.count(Index32(0u)));
0208   BOOST_CHECK(!set.count(Index32(std::numeric_limits<std::uint32_t>::max())));
0209   BOOST_CHECK_EQUAL(set.size(), 3);
0210   // Does not automatically convert encoded value to MultiIndex
0211   BOOST_CHECK(set.count(Index32{0x00010204u}));
0212   BOOST_CHECK(set.count(Index32{0x00010304u}));
0213   BOOST_CHECK(set.count(Index32::Encode(2u)));
0214 }
0215
0216 BOOST_AUTO_TEST_CASE(index64_as_key) {
0217   std::unordered_set<Index64> set;
0218
0219   set.emplace(Index64::Encode(1u, 1u, 1u));
0220   set.emplace(Index64::Encode(2u));
0221   // same as above
0222   set.emplace(Index64::Encode(2u, 0u, 0u, 0u));
0223   set.emplace(Index64::Encode(2u, 1u));
0224
0225   BOOST_CHECK(!set.count(Index64(0u)));
0226   BOOST_CHECK(!set.count(Index64(std::numeric_limits<std::uint64_t>::max())));
0227   BOOST_CHECK_EQUAL(set.size(), 3);
0228 }
0229
0230 BOOST_AUTO_TEST_SUITE_END()
0231
0232 }  // namespace ActsTests