39 : positions(vertices, -1)
41 heap.reserve(std::min(vertices, maximumEntries));
44 bool empty()
const {
return heap.empty(); }
46 std::size_t
size()
const {
return heap.size(); }
50 return heap.capacity() *
sizeof(
Entry) + positions.capacity() *
sizeof(int);
58 int at = positions[entry.
vertex];
60 at = int(heap.size());
61 heap.push_back(entry);
62 positions[entry.
vertex] = at;
76 const auto result = heap.front();
77 positions[result.vertex] = -1;
78 if (heap.size() == 1) {
82 heap.front() = heap.back();
84 positions[heap.front().vertex] = 0;
90 std::vector<Entry> heap;
91 std::vector<int> positions;
92 static bool before(
const Entry &a,
const Entry &b)
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;
102 void exchange(
int a,
int b)
104 std::swap(heap[a], heap[b]);
105 positions[heap[a].vertex] = a;
106 positions[heap[b].vertex] = b;
111 const int parent = (at - 1) / 2;
112 if (!before(heap[at], heap[parent]))
114 exchange(at, parent);
122 const int left = at * 2 + 1;
123 if (left >=
int(heap.size()))
125 const int right = left + 1;
127 right < int(heap.size()) && before(heap[right], heap[left]) ? right : left;
128 if (!before(heap[next], heap[at]))
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