Clover coverage report -
Coverage timestamp: jeu. sept. 29 2005 23:57:39 CEST
file stats: LOC: 121   Methods: 16
NCLOC: 94   Classes: 1
 
 Source file Conditionals Statements Methods TOTAL
Heap.java 100% 95,1% 87,5% 94%
coverage coverage
 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    }