Clover Coverage Report
Coverage timestamp: mer. juin 27 2007 07:27:16 CEST
Overview   Package   File
    FRAMES   NO FRAMES     
41   152   7   2,56
20   95   0,54   16
16     1,38  
1    
 
  Heap       Line # 38 41 7 83,1% 0.83116883
 
  (158)
 
1    /*
2    * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2006 Daniel Le Berre
3    *
4    * Based on the original minisat specification from:
5    *
6    * An extensible SAT solver. Niklas E?n and Niklas S?rensson. Proceedings of the
7    * Sixth International Conference on Theory and Applications of Satisfiability
8    * Testing, LNCS 2919, pp 502-518, 2003.
9    *
10    * This library is free software; you can redistribute it and/or modify it under
11    * the terms of the GNU Lesser General Public License as published by the Free
12    * Software Foundation; either version 2.1 of the License, or (at your option)
13    * any later version.
14    *
15    * This library is distributed in the hope that it will be useful, but WITHOUT
16    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17    * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18    * details.
19    *
20    * You should have received a copy of the GNU Lesser General Public License
21    * along with this library; if not, write to the Free Software Foundation, Inc.,
22    * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23    *
24    */
25    package org.sat4j.minisat.core;
26   
27    import java.io.Serializable;
28   
29    import org.sat4j.core.VecInt;
30    import org.sat4j.specs.IVecInt;
31   
32    /**
33    * Heap implementation used to maintain the variables order in some heuristics.
34    *
35    * @author daniel
36    *
37    */
 
38    public class Heap implements Serializable {
39   
40    /*
41    * default serial version id
42    */
43    private static final long serialVersionUID = 1L;
44   
 
45  1968560138 toggle private final static int left(int i) {
46  1968560138 return i << 1;
47    }
48   
 
49  1744152955 toggle private final static int right(int i) {
50  1744152955 return (i << 1) ^ 1;
51    }
52   
 
53    toggle private final static int parent(int i) {
54    return i >> 1;
55    }
56   
 
57    toggle private final boolean comp(int a, int b) {
58    return activity[a] > activity[b];
59    }
60   
61    private final IVecInt heap = new VecInt(); // heap of ints
62   
63    private final IVecInt indices = new VecInt(); // int -> index in heap
64   
65    private final double[] activity;
66   
 
67  1495322002 toggle @SuppressWarnings("PMD")
68    final void percolateUp(int i) {
69  1495322002 int x = heap.get(i);
70    while (parent(i) != 0 && comp(x, heap.get(parent(i)))) {
71  1077667877 heap.set(i, heap.get(parent(i)));
72  1077667877 indices.set(heap.get(i), i);
73  1077667877 i = parent(i);
74    }
75  1495322002 heap.set(i, x);
76  1495322002 indices.set(x, i);
77    }
78   
 
79  164960036 toggle final void percolateDown(int i) {
80  164960036 int x = heap.get(i);
81  846247051 while (left(i) < heap.size()) {
82  740174033 int child = right(i) < heap.size()
83    && comp(heap.get(right(i)), heap.get(left(i))) ? right(i)
84    : left(i);
85  740174033 if (!comp(heap.get(child), x))
86  58887018 break;
87  681287015 heap.set(i, heap.get(child));
88  681287015 indices.set(heap.get(i), i);
89  681287015 i = child;
90    }
91  164960036 heap.set(i, x);
92  164960036 indices.set(x, i);
93    }
94   
 
95  1654143194 toggle boolean ok(int n) {
96  1654143194 return n >= 0 && n < indices.size();
97    }
98   
 
99  1284 toggle public Heap(double[] activity) {
100  1284 this.activity = activity;
101  1284 heap.push(-1);
102    }
103   
 
104  1283 toggle public void setBounds(int size) {
105  1283 assert (size >= 0);
106  1283 indices.growTo(size, 0);
107    }
108   
 
109  158821192 toggle public boolean inHeap(int n) {
110  158821192 assert (ok(n));
111  158821192 return indices.get(n) != 0;
112    }
113   
 
114  1329475526 toggle public void increase(int n) {
115  1329475526 assert (ok(n));
116  1329475526 assert (inHeap(n));
117  1329475526 percolateUp(indices.get(n));
118    }
119   
 
120  164960058 toggle public boolean empty() {
121  164960058 return heap.size() == 1;
122    }
123   
 
124  165846476 toggle public void insert(int n) {
125  165846476 assert (ok(n));
126  165846476 indices.set(n, heap.size());
127  165846476 heap.push(n);
128  165846476 percolateUp(indices.get(n));
129    }
130   
 
131  164960066 toggle public int getmin() {
132  164960066 int r = heap.get(1);
133  164960066 heap.set(1, heap.last());
134  164960066 indices.set(heap.get(1), 1);
135  164960066 indices.set(r, 0);
136  164960066 heap.pop();
137  164960066 if (heap.size() > 1)
138  164960036 percolateDown(1);
139  164960066 return r;
140    }
141   
 
142  0 toggle public boolean heapProperty() {
143  0 return heapProperty(1);
144    }
145   
 
146  0 toggle public boolean heapProperty(int i) {
147  0 return i >= heap.size()
148    || ((parent(i) == 0 || !comp(heap.get(i), heap.get(parent(i))))
149    && heapProperty(left(i)) && heapProperty(right(i)));
150    }
151   
152    }
 
CloverReport generated by Clover Code Coverage v2.0a5
mer. juin 27 2007 07:27:33 CEST.		   Beta Testers License registered to clover-support@cenqua.com. This license of Clover2 is provided for beta testing only. You have 5 day(s) before your Beta Tester License expires.