src/tests/gov/nasa/jpf/util/SparseIntVectorTest.java

   1 /*
   2  * Copyright (C) 2014, United States Government, as represented by the
   3  * Administrator of the National Aeronautics and Space Administration.
   4  * All rights reserved.
   5  *
   6  * The Java Pathfinder core (jpf-core) platform is licensed under the
   7  * Apache License, Version 2.0 (the "License"); you may not use this file except
   8  * in compliance with the License. You may obtain a copy of the License at
   9  *
  10  *        http://www.apache.org/licenses/LICENSE-2.0.
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18
  19 package gov.nasa.jpf.util;
  20
  21 import org.junit.Test;
  22
  23 import gov.nasa.jpf.util.test.TestJPF;
  24
  25 public class SparseIntVectorTest extends TestJPF {
  26
  27   void assertEquals( SparseIntVector v1, SparseIntVector v2) {
  28     assertTrue( v1.size() == v2.size());
  29
  30     int n = v1.size();
  31     for (int i=0; i<n; i++) {
  32       int a = v1.get(i);
  33       int b = v2.get(i);
  34       assertTrue(a == b);
  35     }
  36   }
  37
  38   @Test
  39   public void testSetGet () {
  40     SparseIntVector v = new SparseIntVector();
  41
  42     v.set(0, 10);
  43     v.set(42, 11);
  44     v.set(111111111, 12);
  45
  46     assertTrue( v.get(0) == 10);
  47     assertTrue( v.get(42) == 11);
  48     assertTrue( v.get(111111111) == 12);
  49
  50     assertTrue( v.get(10) == 0);
  51
  52     v.clear(42);
  53     assertTrue( v.get(42) == 0);
  54   }
  55
  56   @Test
  57   public void testSnapshot () {
  58     SparseIntVector v = new SparseIntVector();
  59
  60     // all empty snapshot
  61     SparseIntVector.Snapshot snap = v.getSnapshot();
  62     int val = 42;
  63     v.set(0,  val);
  64     assertTrue(v.size() == 1 && v.get(0) == val);
  65     v.restore(snap);
  66     assertTrue(v.size() == 0);
  67
  68     //--- all full snapshot
  69     for (int i=0; i<100; i++) {
  70       v.set(i, i);
  71       assertTrue( "size out of sync: " + i, v.size() == (i+1));
  72     }
  73     SparseIntVector.Snapshot snap0 = v.getSnapshot();
  74     v.clear();
  75     v.restore(snap0);
  76     for (int i=0; i<100; i++) {
  77       assertTrue( i == v.get(i));
  78     }
  79
  80     //--- punch holes into it
  81     v.setRange(11,  20, 0);
  82     v.set( 25,0);
  83     v.set( 26, 0);
  84     v.set( 42, 0);
  85     v.setRange(70, 85, 0);
  86     SparseIntVector.Snapshot snap1 = v.getSnapshot();
  87     SparseIntVector v1 = v.clone();
  88     v.clear();
  89     v.restore(snap1);
  90     //v.printOn( System.out);
  91     assertEquals( v1, v);
  92
  93     //--- chop off the ends
  94     v.restore(snap0);
  95     v.setRange(81, 99, 0);
  96     v.setRange(0, 19, 0);
  97     SparseIntVector.Snapshot snap2 = v.getSnapshot();
  98     SparseIntVector v2 = v.clone();
  99     v.clear();
 100     v.restore(snap2);
 101     assertEquals( v2, v);
 102   }
 103
 104   static final int MAX_SIZE = 10000;
 105   static final int MAX_ROUNDS = 1000;
 106
 107   public void benchmark() {
 108     long t1, t2;
 109
 110     for (int rep = 0; rep < 2; rep++) {
 111       Runtime.getRuntime().gc();
 112       SparseIntVector siv = new SparseIntVector();
 113       t1 = System.currentTimeMillis();
 114       for (int i = 0; i < MAX_ROUNDS; i++) {
 115         SparseIntVector.Snapshot snap = siv.getSnapshot();
 116         for (int j = 0; j < MAX_SIZE; j++) {
 117           siv.set(j, j);
 118           assert siv.get(j) == j;
 119           // assert siv.size() == (j+1) : "size differs: " + siv.size() + " / "
 120           // + (j+1);
 121         }
 122         assert siv.size() == MAX_SIZE : "wrong size: " + siv.size();
 123         siv.restore(snap);
 124       }
 125       t2 = System.currentTimeMillis();
 126       System.out.printf("SparseIntVector size %d, rounds %d: %d\n", MAX_SIZE,
 127           MAX_ROUNDS, (t2 - t1));
 128
 129       Runtime.getRuntime().gc();
 130       IntTable<Integer> tbl = new IntTable<Integer>();
 131       t1 = System.currentTimeMillis();
 132       for (int i = 0; i < MAX_ROUNDS; i++) {
 133         IntTable.Snapshot<Integer> snap = tbl.getSnapshot();
 134         for (int j = 0; j < MAX_SIZE; j++) {
 135           tbl.put(j, j);
 136
 137           IntTable.Entry<Integer> e = tbl.get(j);
 138           assert e != null && e.val == j  : "wrong IntTable entry for index: " + j + " : " + e + " in round: " + i;
 139         }
 140         assert tbl.size() == MAX_SIZE : "wrong size: " + tbl.size();
 141         tbl.restore(snap);
 142       }
 143       t2 = System.currentTimeMillis();
 144       System.out.printf("IntTable size %d, rounds %d: %d\n", MAX_SIZE,
 145           MAX_ROUNDS, (t2 - t1));
 146     }
 147   }
 148 }