Loading...
Searching...
No Matches
coarseningqueue.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: Apache-2.0
2#pragma once
3#include <algorithm>
4#include <cstdint>
5#include <vector>
6
7namespace meshkit
8{
9// One live entry per vertex. Updating a neighbour cannot accumulate stale heap
10// entries. Tile order retains locality; lower importance/density comes first,
11// with vertex id as a deterministic final tie. Thread confined, no callbacks.
19{
20public:
22 struct Entry {
24 float importance = 0, density = 0;
29 int vertex = -1;
31 std::uint32_t tile = 0;
32 };
33
38 explicit CoarseningQueue(std::size_t vertices, std::size_t maximumEntries = 0)
39 : positions(vertices, -1)
40 {
41 heap.reserve(std::min(vertices, maximumEntries));
42 }
43
44 bool empty() const { return heap.empty(); }
46 std::size_t size() const { return heap.size(); }
48 std::size_t capacityBytes() const
49 {
50 return heap.capacity() * sizeof(Entry) + positions.capacity() * sizeof(int);
51 }
52
56 void update(Entry entry)
57 {
58 int at = positions[entry.vertex];
59 if (at < 0) {
60 at = int(heap.size());
61 heap.push_back(entry);
62 positions[entry.vertex] = at;
63 up(at);
64 } else {
65 heap[at] = entry;
66 at = up(at);
67 down(at);
68 }
69 }
70
75 {
76 const auto result = heap.front();
77 positions[result.vertex] = -1;
78 if (heap.size() == 1) {
79 heap.pop_back();
80 return result;
81 }
82 heap.front() = heap.back();
83 heap.pop_back();
84 positions[heap.front().vertex] = 0;
85 down(0);
86 return result;
87 }
88
89private:
90 std::vector<Entry> heap;
91 std::vector<int> positions;
92 static bool before(const Entry &a, const Entry &b)
93 {
94 if (a.tile != b.tile)
95 return a.tile < b.tile;
96 if (a.importance != b.importance)
97 return a.importance < b.importance;
98 if (a.density != b.density)
99 return a.density < b.density;
100 return a.vertex < b.vertex;
101 }
102 void exchange(int a, int b)
103 {
104 std::swap(heap[a], heap[b]);
105 positions[heap[a].vertex] = a;
106 positions[heap[b].vertex] = b;
107 }
108 int up(int at)
109 {
110 while (at > 0) {
111 const int parent = (at - 1) / 2;
112 if (!before(heap[at], heap[parent]))
113 break;
114 exchange(at, parent);
115 at = parent;
116 }
117 return at;
118 }
119 void down(int at)
120 {
121 for (;;) {
122 const int left = at * 2 + 1;
123 if (left >= int(heap.size()))
124 return;
125 const int right = left + 1;
126 const int next =
127 right < int(heap.size()) && before(heap[right], heap[left]) ? right : left;
128 if (!before(heap[next], heap[at]))
129 return;
130 exchange(at, next);
131 at = next;
132 }
133 }
134};
135}
CoarseningQueue(std::size_t vertices, std::size_t maximumEntries=0)
Create an empty queue for vertex ids in [0, vertices).
Definition coarseningqueue.hpp:38
Entry pop()
Remove and return the first entry in queue order.
Definition coarseningqueue.hpp:74
void update(Entry entry)
Insert the vertex's entry, or replace its existing entry, and restore heap order.
Definition coarseningqueue.hpp:56
bool empty() const
True when no entry is queued.
Definition coarseningqueue.hpp:44
std::size_t size() const
Number of queued entries (at most one per vertex).
Definition coarseningqueue.hpp:46
std::size_t capacityBytes() const
Bytes of allocated heap and index storage (capacity, not size).
Definition coarseningqueue.hpp:48
CoarseningQueue(std::size_t vertices, std::size_t maximumEntries=0)
Create an empty queue for vertex ids in [0, vertices).
Definition coarseningqueue.hpp:38
The Qt-free MeshKit library: job events and progress (meshkit::runtime), the neutral mesh model,...
One vertex's removal priority.
Definition coarseningqueue.hpp:22
One vertex's removal priority.
Definition coarseningqueue.hpp:22
float importance
Removal importance, lower first (see resolutionRemovalImportance()).
Definition coarseningqueue.hpp:24
std::uint32_t tile
Spatial tile key, compared first so that one tile drains before the next.
Definition coarseningqueue.hpp:31
float density
Tie-break after importance, lower first; the caller passes the local actual/target size ratio.
Definition coarseningqueue.hpp:24
int vertex
Vertex id in [0, vertices) given to the constructor; not range-checked.
Definition coarseningqueue.hpp:29