22 std::vector<typename Spacetree::Item>
run(
u32 numThreads = 0) {
23 constexpr int SPLIT = 5;
27 PreSortCallback(node);
29 bool mustMove[node->
items.size()];
31 for (
i64 itemIdx = 0; itemIdx < node->
items.size(); itemIdx++) {
32 auto &item = node->
items[itemIdx];
33 mustMove[itemIdx] = !node->
range.contains(item._x);
36 auto *lastInsertionNode = supernode;
37 for (
i64 itemIdx = node->
items.size() - 1; itemIdx >= 0; itemIdx--) {
38 if (!mustMove[itemIdx])
continue;
42 if (supernode->range.contains(item._x)) {
43 lastInsertionNode = lastInsertionNode->insert(item);
45 auto *insertionNode =
state->localTree.insert(item);
46 if (!insertionNode) [[unlikely]] {
47 state->lostItems.push_back(item);
53 }, [range = this->spacetree->
range]() {
56 .lostItems = std::vector<typename Spacetree::Item>()
63 for (
auto &sortState : *sortStates) {
66 auto *localInRangeCell = iter.next().value_or(
nullptr);
68 while (localInRangeCell) {
69 for (
auto &localInRangeItem: localInRangeCell->items) {
70 if (!node->
range.contains(localInRangeItem._x))
continue;
71 node->
insert(localInRangeItem);
73 localInRangeCell = iter.next().value_or(
nullptr);
78 auto lostItemsCount = 0;
79 for (
auto &sortState : sortStates) {
80 lostItemsCount += sortState.lostItems.size();
83 std::vector<typename Spacetree::Item> lostItems;
84 lostItems.reserve(lostItemsCount);
86 for (
auto &sortState : sortStates) {
87 lostItems.insert(lostItems.end(), sortState.lostItems.begin(), sortState.lostItems.end());