src/tests/gov/nasa/jpf/util/ArrayObjectQueueTest.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 gov.nasa.jpf.util.test.TestJPF;
  22 import java.util.Iterator;
  23 import java.util.NoSuchElementException;
  24 import org.junit.Test;
  25
  26 /**
  27  *
  28  */
  29 public class ArrayObjectQueueTest extends TestJPF {
  30
  31   <E> void printLogicalOrder (ArrayObjectQueue<E> q){
  32     int n = 0;
  33     System.out.print('{');
  34     for (E e : q){
  35       if (n > 0){
  36         System.out.print(',');
  37       }
  38       System.out.print(e);
  39       n++;
  40     }
  41     System.out.println('}');
  42   }
  43
  44   <E> void printPhysicalOrder (ArrayObjectQueue<E> q){
  45     int n = 0;
  46     System.out.print('{');
  47     for (Iterator<E> it = q.storageIterator(); it.hasNext(); ){
  48       E e = it.next();
  49       if (n > 0){
  50         System.out.print(',');
  51       }
  52       System.out.print(e);
  53       n++;
  54     }
  55     System.out.println('}');
  56   }
  57
  58
  59   @Test
  60   public void testBasic(){
  61     ArrayObjectQueue<String> q = new ArrayObjectQueue<String>(4);
  62
  63     assertTrue( q.isEmpty());
  64     assertTrue( q.size() == 0);
  65
  66     q.add("1");
  67     assertFalse( q.isEmpty());
  68     assertTrue( q.size() == 1);
  69
  70     printLogicalOrder(q);
  71
  72     q.add("2");
  73     q.add("3");
  74     q.add("4");
  75
  76     printLogicalOrder(q);
  77
  78     // now we need to grow
  79     q.add("5");
  80
  81     printLogicalOrder(q);
  82
  83     assertTrue( "1".equals( q.remove()));
  84     assertTrue(q.size() == 4);
  85     printLogicalOrder(q);
  86
  87     assertTrue( "2".equals( q.remove()));
  88     assertTrue( "3".equals( q.remove()));
  89     assertTrue( "4".equals( q.remove()));
  90     assertTrue( "5".equals( q.remove()));
  91
  92     printLogicalOrder(q);
  93     assertTrue(q.isEmpty());
  94
  95     try {
  96       q.remove();
  97       fail("should never get here");
  98     } catch (NoSuchElementException x){
  99       // good exception
 100     }
 101   }
 102
 103   @Test
 104   public void testTailChasing(){
 105     ArrayObjectQueue<String> q = new ArrayObjectQueue<String>(4);
 106     q.add("1");
 107     q.add("2");
 108     q.add("3");
 109     q.add("4");
 110
 111     q.remove(); // should remove "1"
 112     q.add("5"); // should make use of the free space
 113
 114     printLogicalOrder(q);
 115     assertTrue( q.getCurrentCapacity() == 4);
 116
 117     q.remove(); // should remove "2"
 118     q.remove(); // should remove "3"
 119     q.add("6");
 120
 121     printLogicalOrder(q);
 122     printPhysicalOrder(q);
 123
 124     String s = q.remove();
 125     assertTrue( "4".equals(s));
 126     // next remove should wrap around
 127     assertTrue( "5".equals(q.remove()));
 128
 129     printLogicalOrder(q);
 130     printPhysicalOrder(q);
 131   }
 132
 133
 134   @Test
 135   public void testMidGrow(){
 136     ArrayObjectQueue<String> q = new ArrayObjectQueue<String>(4);
 137     q.add("1");
 138     q.add("2");
 139     q.add("3");
 140     q.add("4");
 141
 142     q.remove(); // 1
 143     q.add("5"); // that shouldn't grow yet
 144     int len = q.getCurrentCapacity();
 145     assertTrue( len == 4);
 146     printPhysicalOrder(q);
 147
 148     q.add("6"); // that should grow
 149     assertTrue(q.getCurrentCapacity() > len);
 150
 151     printLogicalOrder(q);
 152     printPhysicalOrder(q);
 153   }
 154
 155   //--- queue processing
 156
 157   static class E {
 158     String name;
 159     E left, right;
 160     boolean visited;
 161
 162     E (String name){ this.name = name; }
 163   }
 164
 165   static class EProcessor implements Processor<E> {
 166     ArrayObjectQueue queue;
 167     int processed = 0;
 168
 169     EProcessor (ArrayObjectQueue<E> queue){
 170       this.queue = queue;
 171     }
 172
 173     @Override
 174         public void process(E e){
 175       e.visited = true;
 176       processed++;
 177       System.out.println("processed: " + e.name);
 178
 179       E ref = e.left;
 180       if (ref != null && !ref.visited) {
 181         ref.visited = true;
 182         queue.add(ref);
 183       }
 184
 185       ref = e.right;
 186       if (ref != null && !ref.visited) {
 187         ref.visited = true;
 188         queue.add(ref);
 189       }
 190     }
 191   }
 192
 193   @Test
 194   public void testProcessing(){
 195     E a = new E("a");
 196     E b = new E("b");
 197     E c = new E("c");
 198     E d = new E("d");
 199     E e = new E("e");
 200     E f = new E("f");
 201     E g = new E("g");
 202
 203     a.left  = b;
 204     b.right = c;
 205     c.left  = d;
 206     d.left  = a;  d.right = e;
 207     e.left  = f;  e.right = g;
 208     g.left  = a;
 209
 210     ArrayObjectQueue<E> q = new ArrayObjectQueue<E>();
 211     q.add(a);
 212     q.add(g);
 213
 214     EProcessor proc = new EProcessor(q);
 215     q.process(proc);
 216
 217     assertTrue(a.visited);
 218     assertTrue(b.visited);
 219     assertTrue(c.visited);
 220     assertTrue(d.visited);
 221     assertTrue(e.visited);
 222     assertTrue(f.visited);
 223     assertTrue(g.visited);
 224
 225     assertTrue( proc.processed == 7);
 226   }
 227 }