blob: 1467c675240197679ee17760894b9ec7a7d48118 (
plain)
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
|
#pragma once
/** \file
* \ingroup bli
* \brief A min-heap / priority queue ADT
*/
#include "BLI_index_range.hh"
#include "BLI_math.h"
#include "BLI_vector.hh"
using blender::IndexRange;
using blender::Vector;
namespace blender {
template<typename T> class MinMaxHeapNode {
public:
private:
T *value;
float value;
int child1 = -1, child2 = -1, parent = -1;
};
template<typename T> class MinMaxHeap {
public:
MinMaxHeap(int reserved = 0)
{
nodes.reserve(reserved);
}
~MinMaxHeap()
{
}
private:
MinMaxHeapNode *heap_make_node()
{
nodes.append(MinMaxHeapNode());
return &nodes[nodes.size() - 1];
}
MinMaxHeapNode *heap_descent_min2(MinMaxHeapNode *n)
{
if (n->child1 != -1 && n->child2 != -1) {
MinMaxHeapNode *n1 = &nodes[n->child1];
MinMaxHeapNode *n2 = &nodes[n->child2];
return n1->value < n2->value ? n1 : n2;
}
else if (n->child1 != -1) {
return &nodes[n->child1];
}
else if (n->child2 != -1) {
return &nodes[n->child2];
}
return n;
}
MinMaxHeapNode *heap_descent_max2(MinMaxHeapNode *n)
{
if (n->child1 != -1 && n->child2 != -1) {
MinMaxHeapNode *n1 = &nodes[n->child1];
MinMaxHeapNode *n2 = &nodes[n->child2];
return n1->value > n2->value ? n1 : n2;
}
else if (n->child1 != -1) {
return &nodes[n->child1];
}
else if (n->child2 != -1) {
return &nodes[n->child2];
}
return n;
}
/* find node grandchild */
MinMaxHeapNode *heap_descent_max(MinMaxHeapNode *node)
{
if (node->child1 != -1 && node->child2 != -1) {
MinMaxHeapNode *n1 = &nodes[node->child1];
MinMaxHeapNode *n2 = &nodes[node->child2];
n1 = heap_descent_max2(heap, n1);
n2 = heap_descent_max2(heap, n2);
return n1->value > n2->value ? n1 : n2;
}
else if (node->child1 != -1) {
return heap_descent_max2(&nodes[node->child1]);
}
else if (node->child2 != -1) {
return heap_descent_max2(&nodes[node->child2]);
}
return NULL;
}
Vector<MinMaxHeapNode<T>> nodes;
};
} // namespace blender
|
