Peano
Loading...
Searching...
No Matches
sort.h
Go to the documentation of this file.
1#pragma once
2
3#include <omp.h>
4
6
7template<typename Spacetree>
9
10template<typename Spacetree, auto PreSortCallback = EmptySortCallback<Spacetree>>
12 Spacetree *spacetree = nullptr;
13
16 std::vector<typename Spacetree::Item> lostItems;
17 };
18
19public:
21
22 std::vector<typename Spacetree::Item> run(u32 numThreads = 0) {
23 constexpr int SPLIT = 5;
24
25 auto sortStates = this->spacetree->onNode([](Spacetree *node, SortWorkerState &state) {
26 node->onNode([supernode = node, state = &state](Spacetree *node) {
27 PreSortCallback(node);
28
29 bool mustMove[node->items.size()];
30
31 for (i64 itemIdx = 0; itemIdx < node->items.size(); itemIdx++) {
32 auto &item = node->items[itemIdx];
33 mustMove[itemIdx] = !node->range.contains(item._x);
34 }
35
36 auto *lastInsertionNode = supernode;
37 for (i64 itemIdx = node->items.size() - 1; itemIdx >= 0; itemIdx--) {
38 if (!mustMove[itemIdx]) continue;
39
40 auto item = node->items.unstableTake(itemIdx);
41
42 if (supernode->range.contains(item._x)) {
43 lastInsertionNode = lastInsertionNode->insert(item);
44 } else {
45 auto *insertionNode = state->localTree.insert(item);
46 if (!insertionNode) [[unlikely]] {
47 state->lostItems.push_back(item);
48 }
49 }
50 }
51 }, 1u);
52
53 }, [range = this->spacetree->range]() {
54 auto state = SortWorkerState {
55 .localTree = Spacetree(range),
56 .lostItems = std::vector<typename Spacetree::Item>()
57 };
58
59 return state;
60 }, LeafOrLevelIterator<Spacetree, SPLIT>(this->spacetree));
61
62 this->spacetree->onNode([sortStates = &sortStates](Spacetree *node) {
63 for (auto &sortState : *sortStates) {
64 auto iter = InsideRegionLeafsIterator(&sortState.localTree, node->range);
65
66 auto *localInRangeCell = iter.next().value_or(nullptr);
67
68 while (localInRangeCell) {
69 for (auto &localInRangeItem: localInRangeCell->items) {
70 if (!node->range.contains(localInRangeItem._x)) continue;
71 node->insert(localInRangeItem);
72 }
73 localInRangeCell = iter.next().value_or(nullptr);
74 }
75 }
76 }, LeafOrLevelIterator<Spacetree, SPLIT>(this->spacetree));
77
78 auto lostItemsCount = 0;
79 for (auto &sortState : sortStates) {
80 lostItemsCount += sortState.lostItems.size();
81 }
82
83 std::vector<typename Spacetree::Item> lostItems;
84 lostItems.reserve(lostItemsCount);
85
86 for (auto &sortState : sortStates) {
87 lostItems.insert(lostItems.end(), sortState.lostItems.begin(), sortState.lostItems.end());
88 }
89
90 return lostItems;
91 }
92};
AutomatonState state
Geo::Region range
Definition linked_grid.h:51
SpacetreeSorter(Spacetree *spacetree)
Definition sort.h:20
std::vector< typename Spacetree::Item > run(u32 numThreads=0)
Definition sort.h:22
Spacetree * spacetree
Definition sort.h:12
Tp unstableTake(std::size_t idx)
Definition vec.h:17
InsideRegionLeafsIterator(Spacetree *, typename Spacetree::Geo::Region region) -> InsideRegionLeafsIterator< Spacetree, TIterationOrder >
void EmptySortCallback(Spacetree *node)
Definition sort.h:8
std::vector< typename Spacetree::Item > lostItems
Definition sort.h:16
void onNode(Callback F, u32 numThreads=0)
Definition spacetree.h:196
Vector< Item > items
Definition spacetree.h:74
Spacetree * insert(Item item)
Definition spacetree.h:117
std::uint32_t u32
Definition type.h:11
std::int64_t i64
Definition type.h:12