#include <boost/numeric/conversion/cast.hpp>
#include <boost/test/unit_test.hpp>
#include "partitioner/bisection_to_partition.hpp"
#define CHECK_SIZE_RANGE(range, ref) BOOST_CHECK_EQUAL(range.end() - range.begin(), ref)
#define CHECK_EQUAL_RANGE(range, ref) \
do \
{ \
const auto &lhs = range; \
const auto &rhs = ref; \
BOOST_CHECK_EQUAL_COLLECTIONS(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); \
} while (0)
using namespace osrm;
using namespace osrm::partitioner;
BOOST_AUTO_TEST_SUITE(bisection_to_partition_tests)
BOOST_AUTO_TEST_CASE(unsplitable_case)
{
std::vector<Partition> partitions;
std::vector<std::uint32_t> num_cells;
/*
0 | 1
/ \
0 | 1 \
/ \ |
0 | 1 0 | 1 |
/ \ / \ / \
| | | | / \
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
*/
const std::vector<BisectionID> ids_1 = {
0b000,
0b000,
0b001,
0b001,
0b010,
0b010,
0b011,
0b011,
0b100,
0b100,
0b100,
0b100,
0b100,
0b100,
0b100,
0b100,
};
// If cell sizes are not a factor of two we will see sub-optimal results like below
std::tie(partitions, num_cells) = bisectionToPartition(ids_1, {2, 4, 8, 16});
BOOST_CHECK_EQUAL(partitions.size(), 4);
std::vector<std::uint32_t> reference_num_cells = {5, 3, 2, 1};
CHECK_EQUAL_RANGE(reference_num_cells, num_cells);
// Four cells of size 2 and one of size 4 (could not be split)
const std::vector<CellID> reference_l1{partitions[0][0], // 0
partitions[0][0], // 1
partitions[0][2], // 2
partitions[0][2], // 3
partitions[0][4], // 4
partitions[0][4], // 5
partitions[0][6], // 6
partitions[0][6], // 7
partitions[0][8], // 8
partitions[0][8], // 9
partitions[0][8], // 10
partitions[0][8], // 11
partitions[0][8], // 12
partitions[0][8], // 13
partitions[0][8], // 14
partitions[0][8]}; // 15
// Two cells of size 4 and one of size 8
const std::vector<CellID> reference_l2{partitions[1][0], // 0
partitions[1][0], // 1
partitions[1][0], // 2
partitions[1][0], // 3
partitions[1][4], // 4
partitions[1][4], // 5
partitions[1][4], // 6
partitions[1][4], // 7
partitions[1][8], // 8
partitions[1][8], // 9
partitions[1][8], // 10
partitions[1][8], // 11
partitions[1][8], // 12
partitions[1][8], // 13
partitions[1][8], // 14
partitions[1][8]}; // 15
// Two cells of size 8
const std::vector<CellID> reference_l3{partitions[2][0], // 0
partitions[2][0], // 1
partitions[2][0], // 2
partitions[2][0], // 3
partitions[2][0], // 4
partitions[2][0], // 5
partitions[2][0], // 6
partitions[2][0], // 7
partitions[2][8], // 8
partitions[2][8], // 9
partitions[2][8], // 10
partitions[2][8], // 11
partitions[2][8], // 12
partitions[2][8], // 13
partitions[2][8], // 14
partitions[2][8]}; // 15
// All in one cell
const std::vector<CellID> reference_l4{partitions[3][0], // 0
partitions[3][0], // 1
partitions[3][0], // 2
partitions[3][0], // 3
partitions[3][0], // 4
partitions[3][0], // 5
partitions[3][0], // 6
partitions[3][0], // 7
partitions[3][0], // 8
partitions[3][0], // 9
partitions[3][0], // 10
partitions[3][0], // 11
partitions[3][0], // 12
partitions[3][0], // 13
partitions[3][0], // 14
partitions[3][0]}; // 15
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
}
BOOST_AUTO_TEST_CASE(power_of_two_case)
{
std::vector<Partition> partitions;
std::vector<std::uint32_t> num_cells;
/*
0 | 1
/ \
0 | 1 |
/ \ |
0 | 1 0 | 1 0 | 1
/ \ / \ / \
| | | | | |
0 1 2 3 4 5 6 7 8 9 10 11
*/
const std::vector<BisectionID> ids_1 = {
0b000, 0b000, 0b001, 0b001, 0b010, 0b010, 0b011, 0b011, 0b100, 0b100, 0b101, 0b101,
};
// If cell sizes are not a factor of two we will see sub-optimal results like below
std::tie(partitions, num_cells) = bisectionToPartition(ids_1, {2, 4, 8, 16});
BOOST_CHECK_EQUAL(partitions.size(), 4);
std::vector<std::uint32_t> reference_num_cells = {6, 3, 2, 1};
CHECK_EQUAL_RANGE(reference_num_cells, num_cells);
// Six cells of size 2
const std::vector<CellID> reference_l1{partitions[0][0], // 0
partitions[0][0], // 1
partitions[0][2], // 2
partitions[0][2], // 3
partitions[0][4], // 4
partitions[0][4], // 5
partitions[0][6], // 6
partitions[0][6], // 7
partitions[0][8], // 8
partitions[0][8], // 9
partitions[0][10], // 10
partitions[0][10]}; // 11
// Three cells of size 4
const std::vector<CellID> reference_l2{partitions[1][0], // 0
partitions[1][0], // 1
partitions[1][0], // 2
partitions[1][0], // 3
partitions[1][4], // 4
partitions[1][4], // 5
partitions[1][4], // 6
partitions[1][4], // 7
partitions[1][8], // 8
partitions[1][8], // 9
partitions[1][8], // 10
partitions[1][8]}; // 11
// Two cells of size 8 and 4
const std::vector<CellID> reference_l3{partitions[2][0], // 0
partitions[2][0], // 1
partitions[2][0], // 2
partitions[2][0], // 3
partitions[2][0], // 4
partitions[2][0], // 5
partitions[2][0], // 6
partitions[2][0], // 7
partitions[2][8], // 8
partitions[2][8], // 9
partitions[2][8], // 10
partitions[2][8]}; // 11
// All in one cell
const std::vector<CellID> reference_l4{partitions[3][0], // 0
partitions[3][0], // 1
partitions[3][0], // 2
partitions[3][0], // 3
partitions[3][0], // 4
partitions[3][0], // 5
partitions[3][0], // 6
partitions[3][0], // 7
partitions[3][0], // 8
partitions[3][0], // 9
partitions[3][0], // 10
partitions[3][0]}; // 11
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
// Inserting zeros at bit position 0, and 2 should not change the result
const std::vector<BisectionID> ids_2 = {
0b00000,
0b00000,
0b00010,
0b00010,
0b00100,
0b00100,
0b00110,
0b00110,
0b10000,
0b10000,
0b10010,
0b10010,
};
std::tie(partitions, num_cells) = bisectionToPartition(ids_2, {2, 4, 8, 16});
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
// Inserting a prefix should not change anything
const std::vector<BisectionID> ids_3 = {
0b101000,
0b101000,
0b101001,
0b101001,
0b101010,
0b101010,
0b101011,
0b101011,
0b101100,
0b101100,
0b101101,
0b101101,
};
std::tie(partitions, num_cells) = bisectionToPartition(ids_3, {2, 4, 8, 16});
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
}
BOOST_AUTO_TEST_CASE(non_factor_two_case)
{
std::vector<Partition> partitions;
std::vector<std::uint32_t> num_cells;
/*
0 | 1
/ \
0 | 1 |
/ \ |
0 | 1 0 | 1 0 | 1
/ \ / \ / \
| | | | | |
0 1 2 3 4 5 6 7 8 9 10 11
*/
const std::vector<BisectionID> ids_1 = {
0b000, 0b000, 0b001, 0b001, 0b010, 0b010, 0b011, 0b011, 0b100, 0b100, 0b101, 0b101,
};
// If cell sizes are not a factor of two we will see sub-optimal results like below
std::tie(partitions, num_cells) = bisectionToPartition(ids_1, {2, 4, 6, 12});
BOOST_CHECK_EQUAL(partitions.size(), 4);
std::vector<std::uint32_t> reference_num_cells = {6, 3, 3, 1};
CHECK_EQUAL_RANGE(reference_num_cells, num_cells);
// Six cells of size 2
const std::vector<CellID> reference_l1{partitions[0][0], // 0
partitions[0][0], // 1
partitions[0][2], // 2
partitions[0][2], // 3
partitions[0][4], // 4
partitions[0][4], // 5
partitions[0][6], // 6
partitions[0][6], // 7
partitions[0][8], // 8
partitions[0][8], // 9
partitions[0][10], // 10
partitions[0][10]}; // 11
// Three cells of size 4
const std::vector<CellID> reference_l2{partitions[1][0], // 0
partitions[1][0], // 1
partitions[1][0], // 2
partitions[1][0], // 3
partitions[1][4], // 4
partitions[1][4], // 5
partitions[1][4], // 6
partitions[1][4], // 7
partitions[1][8], // 8
partitions[1][8], // 9
partitions[1][8], // 10
partitions[1][8]}; // 11
// Again three cells of size 4 (bad)
const std::vector<CellID> reference_l3{partitions[2][0], // 0
partitions[2][0], // 1
partitions[2][0], // 2
partitions[2][0], // 3
partitions[2][4], // 4
partitions[2][4], // 5
partitions[2][4], // 6
partitions[2][4], // 7
partitions[2][8], // 8
partitions[2][8], // 9
partitions[2][8], // 10
partitions[2][8]}; // 11
// All in one cell
const std::vector<CellID> reference_l4{partitions[3][0], // 0
partitions[3][0], // 1
partitions[3][0], // 2
partitions[3][0], // 3
partitions[3][0], // 4
partitions[3][0], // 5
partitions[3][0], // 6
partitions[3][0], // 7
partitions[3][0], // 8
partitions[3][0], // 9
partitions[3][0], // 10
partitions[3][0]}; // 11
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
// Inserting zeros at bit position 0, and 2 should not change the result
const std::vector<BisectionID> ids_2 = {
0b00000,
0b00000,
0b00010,
0b00010,
0b00100,
0b00100,
0b00110,
0b00110,
0b10000,
0b10000,
0b10010,
0b10010,
};
std::tie(partitions, num_cells) = bisectionToPartition(ids_2, {2, 4, 6, 12});
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
// Inserting a prefix should not change anything
const std::vector<BisectionID> ids_3 = {
0b101000,
0b101000,
0b101001,
0b101001,
0b101010,
0b101010,
0b101011,
0b101011,
0b101100,
0b101100,
0b101101,
0b101101,
};
std::tie(partitions, num_cells) = bisectionToPartition(ids_3, {2, 4, 6, 12});
CHECK_EQUAL_RANGE(reference_l1, partitions[0]);
CHECK_EQUAL_RANGE(reference_l2, partitions[1]);
CHECK_EQUAL_RANGE(reference_l3, partitions[2]);
CHECK_EQUAL_RANGE(reference_l4, partitions[3]);
}
BOOST_AUTO_TEST_SUITE_END()