Clover coverage report -

Coverage timestamp: jeu. sept. 29 2005 23:57:39 CEST

FRAMES NO FRAMES

file stats:	LOC:	121		Methods:	16
	NCLOC:	94		Classes:	1

Source file

Conditionals

Statements

Methods

TOTAL

Heap.java

100%

95,1%

87,5%

94%

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		* default serial version id
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(); // heap of ints
32
33		private IVecInt indices = new VecInt(); // int -> index in heap
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		}