Clover Coverage Report
Coverage timestamp: mer. juin 27 2007 07:27:16 CEST
Overview   Package   File
    FRAMES   NO FRAMES     
133   458   30   3,59
74   263   0,5   37
37     1,78  
1    
 
  Vec       Line # 44 133 30 75% 0.75
 
  (228)
 
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   
26    package org.sat4j.core;
27   
28    import java.io.Serializable;
29    import java.util.Arrays;
30    import java.util.Comparator;
31    import java.util.Iterator;
32    import java.util.NoSuchElementException;
33    import java.util.Random;
34   
35    import org.sat4j.specs.IVec;
36   
37    /**
38    * Simple but efficient vector implementation, based on the vector
39    * implementation available in MiniSAT. Note that the elements are compared
40    * using their references, not using the equals method.
41    *
42    * @author leberre
43    */
 
44    public class Vec<T> implements Serializable, IVec<T> {
45   
46    private static final long serialVersionUID = 1L;
47   
48    private static final int RANDOM_SEED = 91648253;
49   
50    /**
51    * Create a Vector with an initial capacity of 5 elements.
52    */
 
53  7183713 toggle public Vec() {
54  7183713 this(5);
55    }
56   
57    /**
58    * Adapter method to translate an array of int into an IVec.
59    *
60    * The array is used inside the Vec, so the elements may be modified outside
61    * the Vec. But it should not take much memory. The size of the created Vec
62    * is the length of the array.
63    *
64    * @param elts
65    * a filled array of T.
66    */
 
67  397410 toggle public Vec(T[] elts) {
68  397410 myarray = elts;
69  397410 nbelem = elts.length;
70    }
71   
72    /**
73    * Create a Vector with a given capacity.
74    *
75    * @param size
76    * the capacity of the vector.
77    */
 
78  9249733 toggle @SuppressWarnings("unchecked")
79    public Vec(int size) {
80  9249733 myarray = (T[]) new Object[size];
81    }
82   
83    /**
84    * Construit un vecteur contenant de taille size rempli a l'aide de size
85    * pad.
86    *
87    * @param size
88    * la taille du vecteur
89    * @param pad
90    * l'objet servant a remplir le vecteur
91    */
 
92  15 toggle @SuppressWarnings("unchecked")
93    public Vec(int size, T pad) {
94  15 myarray = (T[]) new Object[size];
95  74 for (int i = 0; i < size; i++) {
96  59 myarray[i] = pad;
97    }
98  15 nbelem = size;
99    }
100   
 
101  2052217704 toggle public int size() {
102  2052217704 return nbelem;
103    }
104   
105    /**
106    * Remove nofelems from the Vector. It is assumed that the number of
107    * elements to remove is smaller or equals to the current number of elements
108    * in the vector
109    *
110    * @param nofelems
111    * the number of elements to remove.
112    */
 
113  2 toggle public void shrink(int nofelems) {
114  2 assert nofelems <= nbelem;
115  12 while (nofelems-- > 0) {
116  10 myarray[--nbelem] = null;
117    }
118    }
119   
120    /**
121    * reduce the Vector to exactly newsize elements
122    *
123    * @param newsize
124    * the new size of the vector.
125    */
 
126  5 toggle public void shrinkTo(final int newsize) {
127  5 assert newsize <= size();
128  30256 for (int i = nbelem; i > newsize; i--) {
129  30251 myarray[i - 1] = null;
130    }
131  5 nbelem = newsize;
132  5 assert size() == newsize;
133    }
134   
135    /**
136    * Pop the last element on the stack. It is assumed that the stack is not
137    * empty!
138    */
 
139    toggle public void pop() {
140    assert size() > 0;
141    myarray[--nbelem] = null;
142    }
143   
 
144  14 toggle public void growTo(final int newsize, final T pad) {
145  14 assert newsize >= size();
146  14 ensure(newsize);
147  108 for (int i = nbelem; i < newsize; i++) {
148  94 myarray[i] = pad;
149    }
150  14 nbelem = newsize;
151    }
152   
 
153    toggle @SuppressWarnings("unchecked")
154    public final void ensure(final int nsize) {
155    if (nsize >= myarray.length) {
156  223603990 T[] narray = (T[]) new Object[Math.max(nsize, nbelem * 2)];
157  223603990 System.arraycopy(myarray, 0, narray, 0, nbelem);
158  223603990 myarray = narray;
159    }
160    }
161   
 
162  571358376 toggle public IVec<T> push(final T elem) {
163  571358376 ensure(nbelem + 1);
164  571358376 myarray[nbelem++] = elem;
165  571358376 return this;
166    }
167   
 
168  0 toggle public void unsafePush(final T elem) {
169  0 myarray[nbelem++] = elem;
170    }
171   
172    /**
173    * Insert an element at the very begining of the vector. The former first
174    * element is appended to the end of the vector in order to have a constant
175    * time operation.
176    *
177    * @param elem
178    * the element to put first in the vector.
179    */
 
180  0 toggle public void insertFirst(final T elem) {
181  0 if (nbelem > 0) {
182  0 push(myarray[0]);
183  0 myarray[0] = elem;
184  0 return;
185    }
186  0 push(elem);
187    }
188   
 
189  74457 toggle public void insertFirstWithShifting(final T elem) {
190  74457 if (nbelem > 0) {
191  10732 ensure(nbelem + 1);
192  59433 for (int i = nbelem; i > 0; i--) {
193  48701 myarray[i] = myarray[i - 1];
194    }
195  10732 myarray[0] = elem;
196  10732 nbelem++;
197  10732 return;
198    }
199  63725 push(elem);
200    }
201   
 
202  2040041842 toggle public void clear() {
203  2040041842 Arrays.fill(myarray, 0, nbelem, null);
204  2040041842 nbelem = 0;
205    }
206   
207    /**
208    * return the latest element on the stack. It is assumed that the stack is
209    * not empty!
210    *
211    * @return the last element on the stack (the one on the top)
212    */
 
213    toggle public T last() {
214    assert size() != 0;
215    return myarray[nbelem - 1];
216    }
217   
 
218    toggle public T get(final int index) {
219    return myarray[index];
220    }
221   
 
222  55653 toggle public void set(int index, T elem) {
223  55653 myarray[index] = elem;
224    }
225   
226    /**
227    * Remove an element that belongs to the Vector. The method will break if
228    * the element does not belong to the vector.
229    *
230    * @param elem
231    * an element from the vector.
232    */
 
233  60504 toggle public void remove(T elem) {
234  60504 assert size() > 0;
235  60504 int j = 0;
236  38393904 for (; myarray[j] != elem; j++) {
237  38333400 assert j < size();
238    }
239    // arraycopy is always faster than manual copy
240  60504 System.arraycopy(myarray, j + 1, myarray, j, size() - j - 1);
241  60504 myarray[--nbelem] = null;
242    }
243   
244    /**
245    * Delete the ith element of the vector. The latest element of the vector
246    * replaces the removed element at the ith indexer.
247    *
248    * @param index
249    * the indexer of the element in the vector
250    * @return the former ith element of the vector that is now removed from the
251    * vector
252    */
 
253  2 toggle public T delete(int index) {
254  2 assert index >= 0 && index < nbelem;
255  2 T ith = myarray[index];
256  2 myarray[index] = myarray[--nbelem];
257  2 myarray[nbelem] = null;
258  2 return ith;
259    }
260   
261    /**
262    * Ces operations devraient se faire en temps constant. Ce n'est pas le
263    * cas ici.
264    *
265    * @param copy
266    */
 
267    toggle public void copyTo(IVec<T> copy) {
268    final Vec<T> ncopy = (Vec<T>) copy;
269    final int nsize = nbelem + ncopy.nbelem;
270    copy.ensure(nsize);
271    System.arraycopy(myarray, 0, ncopy.myarray, ncopy.nbelem, nbelem);
272    ncopy.nbelem = nsize;
273    }
274   
275    /**
276    * @param dest
277    */
 
278  2897309 toggle public <E> void copyTo(E[] dest) {
279  2897309 assert dest.length >= nbelem;
280  2897309 System.arraycopy(myarray, 0, dest, 0, nbelem);
281    }
282   
283    /*
284    * Copy one vector to another (cleaning the first), in constant time.
285    */
 
286    toggle public void moveTo(IVec<T> dest) {
287    copyTo(dest);
288    clear();
289    }
290   
 
291  0 toggle public void moveTo(int dest, int source) {
292  0 myarray[dest] = myarray[source];
293  0 myarray[source] = null;
294    }
295   
 
296  0 toggle public T[] toArray() {
297  0 return myarray;
298    }
299   
300    private int nbelem;
301   
302    private T[] myarray;
303   
304    /*
305    * (non-Javadoc)
306    *
307    * @see java.lang.Object#toString()
308    */
 
309  90 toggle @Override
310    public String toString() {
311  90 StringBuffer stb = new StringBuffer();
312  1800 for (int i = 0; i < nbelem - 1; i++) {
313  1710 stb.append(myarray[i]);
314  1710 stb.append(","); //$NON-NLS-1$
315    }
316  90 if (nbelem > 0) {
317  90 stb.append(myarray[nbelem - 1]);
318    }
319  90 return stb.toString();
320    }
321   
322    private static Random rand = new Random(RANDOM_SEED);
323   
 
324  7335 toggle void selectionSort(int from, int to, Comparator<T> cmp) {
325  7335 int i, j, best_i;
326  7335 T tmp;
327   
328  60779 for (i = from; i < to - 1; i++) {
329  53444 best_i = i;
330  338440 for (j = i + 1; j < to; j++) {
331  284996 if (cmp.compare(myarray[j], myarray[best_i]) < 0)
332  52972 best_i = j;
333    }
334  53444 tmp = myarray[i];
335  53444 myarray[i] = myarray[best_i];
336  53444 myarray[best_i] = tmp;
337    }
338    }
339   
 
340  14662 toggle void sort(int from, int to, Comparator<T> cmp) {
341  14662 int width = to - from;
342  14662 if (to - from <= 15)
343  7334 selectionSort(from, to, cmp);
344   
345    else {
346  7328 T pivot = myarray[rand.nextInt(width) + from];
347  7328 T tmp;
348  7328 int i = from - 1;
349  7328 int j = to;
350   
351  7328 for (;;) {
352  147194 do
353  498077 i++;
354  498077 while (cmp.compare(myarray[i], pivot) < 0);
355  147194 do
356  472835 j--;
357  472835 while (cmp.compare(pivot, myarray[j]) < 0);
358   
359  147194 if (i >= j)
360  7328 break;
361   
362  139866 tmp = myarray[i];
363  139866 myarray[i] = myarray[j];
364  139866 myarray[j] = tmp;
365    }
366   
367  7328 sort(from, i, cmp);
368  7328 sort(i, to, cmp);
369    }
370    }
371   
372    /**
373    * @param comparator
374    */
 
375  5 toggle public void sort(Comparator<T> comparator) {
376  5 sort(0, nbelem, comparator);
377    }
378   
 
379  1 toggle public void sortUnique(Comparator<T> cmp) {
380  1 int i, j;
381  1 T last;
382   
383  1 if (nbelem == 0)
384  0 return;
385   
386  1 sort(0, nbelem, cmp);
387   
388  1 i = 1;
389  1 last = myarray[0];
390  106 for (j = 1; j < nbelem; j++) {
391  105 if (cmp.compare(last, myarray[j]) < 0) {
392  100 last = myarray[i] = myarray[j];
393  100 i++;
394    }
395    }
396   
397  1 nbelem = i;
398    }
399   
400    /*
401    * (non-Javadoc)
402    *
403    * @see java.lang.Object#equals(java.lang.Object)
404    */
 
405  21 toggle @Override
406    public boolean equals(Object obj) {
407  21 if (obj instanceof IVec) {
408  21 IVec<?> v = (IVec<?>) obj;
409  21 if (v.size() != size())
410  2 return false;
411  334 for (int i = 0; i < size(); i++) {
412  316 if (!v.get(i).equals(get(i))) {
413  1 return false;
414    }
415    }
416  18 return true;
417    }
418  0 return false;
419    }
420   
421    /*
422    * (non-Javadoc)
423    *
424    * @see java.lang.Object#hashCode()
425    */
 
426  0 toggle @Override
427    public int hashCode() {
428  0 int sum = 0;
429  0 for (int i = 0; i < nbelem; i++) {
430  0 sum += myarray[i].hashCode() / nbelem;
431    }
432  0 return sum;
433    }
434   
 
435  6 toggle public Iterator<T> iterator() {
436  6 return new Iterator<T>() {
437    private int i = 0;
438   
 
439  9 toggle public boolean hasNext() {
440  9 return i < nbelem;
441    }
442   
 
443  4 toggle public T next() {
444  4 if (i == nbelem)
445  1 throw new NoSuchElementException();
446  3 return myarray[i++];
447    }
448   
 
449  0 toggle public void remove() {
450  0 throw new UnsupportedOperationException();
451    }
452    };
453    }
454   
 
455  0 toggle public boolean isEmpty() {
456  0 return nbelem == 0;
457    }
458    }
 
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.