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 BOOST_AUTO_TEST_CASE_TEMPLATE(triviality, T, Indices) {
0028   // verify that the MultiIndex is a trivial type
0029   // this seems to be compiler-dependent; disable for now
0030   BOOST_CHECK(std::is_standard_layout_v<T>);
0031   BOOST_CHECK(std::is_trivially_default_constructible_v<T>);
0032   BOOST_CHECK(std::is_trivially_copy_constructible_v<T>);
0033   BOOST_CHECK(std::is_trivially_move_constructible_v<T>);
0034   BOOST_CHECK((std::is_trivially_assignable_v<T, T>));
0035   BOOST_CHECK((std::is_trivially_copy_assignable_v<T>));
0036   BOOST_CHECK((std::is_trivially_move_assignable_v<T>));
0037 }
0038
0039 BOOST_AUTO_TEST_CASE(index32_construct) {
0040   // construct from encoded value
0041   {
0042     Index32 idx(0xabcd2400u);
0043     BOOST_CHECK_EQUAL(idx.value(), 0xabcd2400u);
0044     BOOST_CHECK_EQUAL(idx.level(0), 0xabcdu);
0045     BOOST_CHECK_EQUAL(idx.level(1), 0x24u);
0046     BOOST_CHECK_EQUAL(idx.level(2), 0x00u);
0047   }
0048 }
0049
0050 BOOST_AUTO_TEST_CASE(index32_set) {
0051   Index32 idx = Index32::Zeros();
0052   // set a specific level within limits
0053   idx.set(0, 24u);
0054   BOOST_CHECK_EQUAL(idx.value(), 0x00180000u);
0055   BOOST_CHECK_EQUAL(idx.level(0), 24u);
0056   BOOST_CHECK_EQUAL(idx.level(1), 0u);
0057   BOOST_CHECK_EQUAL(idx.level(2), 0u);
0058   // set a specific level outside the valid range, should be truncated
0059   BOOST_CHECK_THROW(idx.set(2, 0xfff), std::out_of_range);
0060 }
0061
0062 BOOST_AUTO_TEST_CASE(index32_set_overflow) {
0063   // maximum values for each level
0064   Index32::Value maxValues[] = {
0065       (1u << 16u) - 1u,
0066       (1u << 8u) - 1u,
0067       (1u << 8u) - 1u,
0068   };
0069   // check that values above max are truncated
0070   std::size_t lvl = 0;
0071   for (auto maxValue : maxValues) {
0072     BOOST_CHECK_THROW(Index32::Zeros().set(lvl, maxValue + 1),
0073                       std::out_of_range);
0074     lvl += 1;
0075   }
0076 }
0077
0078 BOOST_AUTO_TEST_CASE(index64_set_overflow) {
0079   // maximum values for each level
0080   Index32::Value maxValues[] = {
0081       (1u << 13u) - 1u,
0082       (1u << 17u) - 1u,
0083       (1u << 21u) - 1u,
0084       (1u << 13u) - 1u,
0085   };
0086   // check that values above max are truncated
0087   std::size_t lvl = 0;
0088   for (auto maxValue : maxValues) {
0089     BOOST_CHECK_THROW(Index64::Zeros().set(lvl, maxValue + 1),
0090                       std::out_of_range);
0091     lvl += 1;
0092   }
0093 }
0094
0095 BOOST_AUTO_TEST_CASE(index32_encode) {
0096   // all three levels set
0097   auto idx3 = Index32::Encode(13u, 14u, 15u);
0098   BOOST_CHECK_EQUAL(idx3.level(0), 13u);
0099   BOOST_CHECK_EQUAL(idx3.level(1), 14u);
0100   BOOST_CHECK_EQUAL(idx3.level(2), 15u);
0101   // first two levels set
0102   auto idx2 = Index32::Encode(13u, 14u);
0103   BOOST_CHECK_EQUAL(idx2.level(0), 13u);
0104   BOOST_CHECK_EQUAL(idx2.level(1), 14u);
0105   BOOST_CHECK_EQUAL(idx2.level(2), 0u);
0106   // only the first level set
0107   auto idx1 = Index32::Encode(13u);
0108   BOOST_CHECK_EQUAL(idx1.level(0), 13u);
0109   BOOST_CHECK_EQUAL(idx1.level(1), 0u);
0110   BOOST_CHECK_EQUAL(idx1.level(2), 0u);
0111   // nothing set
0112   auto idx0 = Index32::Encode();
0113   BOOST_CHECK_EQUAL(idx0, Index32::Zeros());
0114   BOOST_CHECK_EQUAL(idx0.value(), 0u);
0115   BOOST_CHECK_EQUAL(idx0.level(0), 0u);
0116   BOOST_CHECK_EQUAL(idx0.level(1), 0u);
0117   BOOST_CHECK_EQUAL(idx0.level(2), 0u);
0118 }
0119
0120 BOOST_AUTO_TEST_CASE(index64_encode) {
0121   // all four levels set
0122   auto idx4 = Index64::Encode(23u, 14u, 15u, 17u);
0123   BOOST_CHECK_EQUAL(idx4.level(0), 23u);
0124   BOOST_CHECK_EQUAL(idx4.level(1), 14u);
0125   BOOST_CHECK_EQUAL(idx4.level(2), 15u);
0126   BOOST_CHECK_EQUAL(idx4.level(3), 17u);
0127   // first three levels set
0128   auto idx3 = Index64::Encode(23u, 14u, 15u);
0129   BOOST_CHECK_EQUAL(idx3.level(0), 23u);
0130   BOOST_CHECK_EQUAL(idx3.level(1), 14u);
0131   BOOST_CHECK_EQUAL(idx3.level(2), 15u);
0132   BOOST_CHECK_EQUAL(idx3.level(3), 0u);
0133   // first two levels set
0134   auto idx2 = Index64::Encode(23u, 14u);
0135   BOOST_CHECK_EQUAL(idx2.level(0), 23u);
0136   BOOST_CHECK_EQUAL(idx2.level(1), 14u);
0137   BOOST_CHECK_EQUAL(idx2.level(2), 0u);
0138   BOOST_CHECK_EQUAL(idx2.level(3), 0u);
0139   // only the first level set
0140   auto idx1 = Index64::Encode(23u);
0141   BOOST_CHECK_EQUAL(idx1.level(0), 23u);
0142   BOOST_CHECK_EQUAL(idx1.level(1), 0u);
0143   BOOST_CHECK_EQUAL(idx1.level(2), 0u);
0144   BOOST_CHECK_EQUAL(idx1.level(3), 0u);
0145   // nothing set
0146   auto idx0 = Index64::Encode();
0147   BOOST_CHECK_EQUAL(idx0, Index64::Zeros());
0148   BOOST_CHECK_EQUAL(idx0.value(), 0u);
0149   BOOST_CHECK_EQUAL(idx0.level(0), 0u);
0150   BOOST_CHECK_EQUAL(idx0.level(1), 0u);
0151   BOOST_CHECK_EQUAL(idx0.level(2), 0u);
0152   BOOST_CHECK_EQUAL(idx0.level(3), 0u);
0153 }
0154
0155 BOOST_AUTO_TEST_CASE(uint32_sibling) {
0156   auto idx = Index32::Encode(1u, 12u, 123u);
0157   BOOST_CHECK_EQUAL(idx.makeNextSibling(0), Index32::Encode(2u));
0158   BOOST_CHECK_EQUAL(idx.makeNextSibling(1), Index32::Encode(1u, 13u));
0159   BOOST_CHECK_EQUAL(idx.makeNextSibling(2), Index32::Encode(1u, 12u, 124u));
0160 }
0161
0162 BOOST_AUTO_TEST_CASE(uint64_sibling) {
0163   auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
0164   BOOST_CHECK_EQUAL(idx.makeNextSibling(0), Index64::Encode(2u));
0165   BOOST_CHECK_EQUAL(idx.makeNextSibling(1), Index64::Encode(1u, 13u));
0166   BOOST_CHECK_EQUAL(idx.makeNextSibling(2), Index64::Encode(1u, 12u, 124u));
0167   BOOST_CHECK_EQUAL(idx.makeNextSibling(3),
0168                     Index64::Encode(1u, 12u, 123u, 1235u));
0169 }
0170
0171 BOOST_AUTO_TEST_CASE(uint32_descendant) {
0172   auto idx = Index32::Encode(1u, 12u, 123u);
0173   BOOST_CHECK_EQUAL(idx.makeLastDescendant(0), Index32::Encode(1u, 255u, 255u));
0174   BOOST_CHECK_EQUAL(idx.makeLastDescendant(1), Index32::Encode(1u, 12u, 255u));
0175   // last index has no descendant and stays the same
0176   BOOST_CHECK_EQUAL(idx.makeLastDescendant(2), Index32::Encode(1u, 12u, 123u));
0177 }
0178
0179 BOOST_AUTO_TEST_CASE(uint64_descendant) {
0180   auto idx = Index64::Encode(1u, 12u, 123u, 1234u);
0181   // from Index64 definition above
0182   auto max1 = (1u << 17) - 1u;
0183   auto max2 = (1u << 21) - 1u;
0184   auto max3 = (1u << 13) - 1u;
0185   BOOST_CHECK_EQUAL(idx.makeLastDescendant(0),
0186                     Index64::Encode(1u, max1, max2, max3));
0187   BOOST_CHECK_EQUAL(idx.makeLastDescendant(1),
0188                     Index64::Encode(1u, 12u, max2, max3));
0189   BOOST_CHECK_EQUAL(idx.makeLastDescendant(2),
0190                     Index64::Encode(1u, 12u, 123u, max3));
0191   // last index has no descendant and stays the same
0192   BOOST_CHECK_EQUAL(idx.makeLastDescendant(3),
0193                     Index64::Encode(1u, 12u, 123u, 1234u));
0194 }
0195
0196 BOOST_AUTO_TEST_CASE(index32_as_key) {
0197   std::unordered_set<Index32> set;
0198
0199   set.emplace(Index32::Encode(1u, 2u, 4u));
0200   set.emplace(Index32::Encode(1u, 3u, 4u));
0201   set.emplace(Index32::Encode(2u));
0202
0203   BOOST_CHECK(!set.count(Index32(0u)));
0204   BOOST_CHECK(!set.count(Index32(std::numeric_limits<std::uint32_t>::max())));
0205   BOOST_CHECK_EQUAL(set.size(), 3);
0206   // Does not automatically convert encoded value to MultiIndex
0207   BOOST_CHECK(set.count(Index32{0x00010204u}));
0208   BOOST_CHECK(set.count(Index32{0x00010304u}));
0209   BOOST_CHECK(set.count(Index32::Encode(2u)));
0210 }
0211
0212 BOOST_AUTO_TEST_CASE(index64_as_key) {
0213   std::unordered_set<Index64> set;
0214
0215   set.emplace(Index64::Encode(1u, 1u, 1u));
0216   set.emplace(Index64::Encode(2u));
0217   // same as above
0218   set.emplace(Index64::Encode(2u, 0u, 0u, 0u));
0219   set.emplace(Index64::Encode(2u, 1u));
0220
0221   BOOST_CHECK(!set.count(Index64(0u)));
0222   BOOST_CHECK(!set.count(Index64(std::numeric_limits<std::uint64_t>::max())));
0223   BOOST_CHECK_EQUAL(set.size(), 3);
0224 }