1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
#ifndef slic3r_MutablePriorityQueue_hpp_
#define slic3r_MutablePriorityQueue_hpp_
#include <assert.h>
template<typename T, typename IndexSetter, typename LessPredicate>
class MutablePriorityQueue
{
public:
MutablePriorityQueue(IndexSetter &&index_setter, LessPredicate &&less_predicate) :
m_index_setter(std::forward<IndexSetter>(index_setter)),
m_less_predicate(std::forward<LessPredicate>(less_predicate))
{}
~MutablePriorityQueue() { clear(); }
inline void clear() { m_heap.clear(); }
inline void reserve(size_t cnt) { m_heap.reserve(cnt); }
inline void push(const T &item);
inline void push(T &&item);
inline void pop();
inline T& top() { return m_heap.front(); }
inline void remove(size_t idx);
inline void update(size_t idx) { T item = m_heap[idx]; remove(idx); push(item); }
inline size_t size() const { return m_heap.size(); }
inline bool empty() const { return m_heap.empty(); }
protected:
inline void update_heap_up(size_t top, size_t bottom);
inline void update_heap_down(size_t top, size_t bottom);
private:
std::vector<T> m_heap;
IndexSetter m_index_setter;
LessPredicate m_less_predicate;
};
template<typename T, typename IndexSetter, typename LessPredicate>
MutablePriorityQueue<T, IndexSetter, LessPredicate> make_mutable_priority_queue(IndexSetter &&index_setter, LessPredicate &&less_predicate)
{
return MutablePriorityQueue<T, IndexSetter, LessPredicate>(
std::forward<IndexSetter>(index_setter), std::forward<LessPredicate>(less_predicate));
}
template<class T, class LessPredicate, class IndexSetter>
inline void MutablePriorityQueue<T, LessPredicate, IndexSetter>::push(const T &item)
{
size_t idx = m_heap.size();
m_heap.emplace_back(item);
m_index_setter(m_heap.back(), idx);
update_heap_up(0, idx);
}
template<class T, class LessPredicate, class IndexSetter>
inline void MutablePriorityQueue<T, LessPredicate, IndexSetter>::push(T &&item)
{
size_t idx = m_heap.size();
m_heap.emplace_back(std::move(item));
m_index_setter(m_heap.back(), idx);
update_heap_up(0, idx);
}
template<class T, class LessPredicate, class IndexSetter>
inline void MutablePriorityQueue<T, LessPredicate, IndexSetter>::pop()
{
assert(! m_heap.empty());
if (m_heap.size() > 1) {
m_heap.front() = m_heap.back();
m_heap.pop_back();
m_index_setter(m_heap.front(), 0);
update_heap_down(0, m_heap.size() - 1);
} else
m_heap.clear();
}
template<class T, class LessPredicate, class IndexSetter>
inline void MutablePriorityQueue<T, LessPredicate, IndexSetter>::remove(size_t idx)
{
assert(idx < m_heap.size());
if (idx + 1 == m_heap.size()) {
m_heap.pop_back();
return;
}
m_heap[idx] = m_heap.back();
m_index_setter(m_heap[idx], idx);
m_heap.pop_back();
update_heap_down(idx, m_heap.size() - 1);
update_heap_up(0, idx);
}
template<class T, class LessPredicate, class IndexSetter>
inline void MutablePriorityQueue<T, LessPredicate, IndexSetter>::update_heap_up(size_t top, size_t bottom)
{
size_t childIdx = bottom;
T *child = &m_heap[childIdx];
for (;;) {
size_t parentIdx = (childIdx - 1) >> 1;
if (childIdx == 0 || parentIdx < top)
break;
T *parent = &m_heap[parentIdx];
// switch nodes
if (! m_less_predicate(*parent, *child)) {
T tmp = *parent;
m_index_setter(*parent, childIdx);
m_index_setter(*child, parentIdx);
m_heap[parentIdx] = *child;
m_heap[childIdx] = tmp;
}
// shift up
childIdx = parentIdx;
child = parent;
}
}
template<class T, class LessPredicate, class IndexSetter>
inline void MutablePriorityQueue<T, LessPredicate, IndexSetter>::update_heap_down(size_t top, size_t bottom)
{
size_t parentIdx = top;
T *parent = &m_heap[parentIdx];
for (;;) {
size_t childIdx = (parentIdx << 1) + 1;
if (childIdx > bottom)
break;
T *child = &m_heap[childIdx];
size_t child2Idx = childIdx + 1;
if (child2Idx <= bottom) {
T *child2 = &m_heap[child2Idx];
if (! m_less_predicate(*child, *child2)) {
child = child2;
childIdx = child2Idx;
}
}
if (m_less_predicate(*parent, *child))
return;
// switch nodes
m_index_setter(*parent, childIdx);
m_index_setter(*child, parentIdx);
T tmp = *parent;
m_heap[parentIdx] = *child;
m_heap[childIdx] = tmp;
// shift down
parentIdx = childIdx;
parent = child;
}
}
#endif /* slic3r_MutablePriorityQueue_hpp_ */
|
