1 |
| package org.sat4j.minisat.core; |
2 |
| |
3 |
| import java.io.Serializable; |
4 |
| |
5 |
| import org.sat4j.core.VecInt; |
6 |
| import org.sat4j.specs.IVecInt; |
7 |
| |
8 |
| public class Heap implements Serializable { |
9 |
| |
10 |
| |
11 |
| |
12 |
| |
13 |
| private static final long serialVersionUID = 1L; |
14 |
| |
15 |
287976762
| private final static int left(int i) {
|
16 |
287976762
| return i + i;
|
17 |
| } |
18 |
| |
19 |
260878741
| private final static int right(int i) {
|
20 |
260878741
| return i + i + 1;
|
21 |
| } |
22 |
| |
23 |
889228953
| private final static int parent(int i) {
|
24 |
889228953
| return i >> 1;
|
25 |
| } |
26 |
| |
27 |
497605938
| private final boolean comp(int a, int b) {
|
28 |
497605938
| return activity[a] > activity[b];
|
29 |
| } |
30 |
| |
31 |
| private IVecInt heap = new VecInt(); |
32 |
| |
33 |
| private IVecInt indices = new VecInt(); |
34 |
| |
35 |
| private final double [] activity; |
36 |
| |
37 |
188402954
| final void percolateUp(int i) {
|
38 |
188402954
| int x = heap.get(i);
|
39 |
188402954
| while (parent(i) != 0 && comp(x, heap.get(parent(i)))) {
|
40 |
137924398
| heap.set(i, heap.get(parent(i)));
|
41 |
137924398
| indices.set(heap.get(i), i);
|
42 |
137924398
| i = parent(i);
|
43 |
| } |
44 |
188402954
| heap.set(i, x);
|
45 |
188402954
| indices.set(x, i);
|
46 |
| } |
47 |
| |
48 |
27776276
| final void percolateDown(int i) {
|
49 |
27776276
| int x = heap.get(i);
|
50 |
27776276
| while (left(i) < heap.size()) {
|
51 |
109253851
| int child = right(i) < heap.size()
|
52 |
| && comp(heap.get(right(i)), heap.get(left(i))) ? right(i) |
53 |
| : left(i); |
54 |
109253851
| if (!comp(heap.get(child), x))
|
55 |
9280890
| break;
|
56 |
99972961
| heap.set(i, heap.get(child));
|
57 |
99972961
| indices.set(heap.get(i), i);
|
58 |
99972961
| i = child;
|
59 |
| } |
60 |
27776276
| heap.set(i, x);
|
61 |
27776276
| indices.set(x, i);
|
62 |
| } |
63 |
| |
64 |
1396233618
| boolean ok(int n) {
|
65 |
1396233618
| return n >= 0 && n < indices.size();
|
66 |
| } |
67 |
| |
68 |
10
| public Heap(double [] activity) {
|
69 |
10
| this.activity = activity;
|
70 |
10
| heap.push(-1);
|
71 |
| } |
72 |
| |
73 |
9
| public void setBounds(int size) {
|
74 |
| assert (size >= 0); |
75 |
9
| indices.growTo(size, 0);
|
76 |
| } |
77 |
| |
78 |
1207830664
| public boolean inHeap(int n) {
|
79 |
| assert (ok(n)); |
80 |
1207830664
| return indices.get(n) != 0;
|
81 |
| } |
82 |
| |
83 |
160626165
| public void increase(int n) {
|
84 |
| assert (ok(n)); |
85 |
| assert (inHeap(n)); |
86 |
160626165
| percolateUp(indices.get(n));
|
87 |
| } |
88 |
| |
89 |
27776271
| public boolean empty() {
|
90 |
27776271
| return heap.size() == 1;
|
91 |
| } |
92 |
| |
93 |
27776789
| public void insert(int n) {
|
94 |
| assert (ok(n)); |
95 |
27776789
| indices.set(n, heap.size());
|
96 |
27776789
| heap.push(n);
|
97 |
27776789
| percolateUp(indices.get(n));
|
98 |
| } |
99 |
| |
100 |
27776279
| public int getmin() {
|
101 |
27776279
| int r = heap.get(1);
|
102 |
27776279
| heap.set(1, heap.last());
|
103 |
27776279
| indices.set(heap.get(1), 1);
|
104 |
27776279
| indices.set(r, 0);
|
105 |
27776279
| heap.pop();
|
106 |
27776279
| if (heap.size() > 1)
|
107 |
27776276
| percolateDown(1);
|
108 |
27776279
| return r;
|
109 |
| } |
110 |
| |
111 |
0
| public boolean heapProperty() {
|
112 |
0
| return heapProperty(1);
|
113 |
| } |
114 |
| |
115 |
0
| public boolean heapProperty(int i) {
|
116 |
0
| return i >= heap.size()
|
117 |
| || ((parent(i) == 0 || !comp(heap.get(i), heap.get(parent(i)))) |
118 |
| && heapProperty(left(i)) && heapProperty(right(i))); |
119 |
| } |
120 |
| |
121 |
| } |