src/main/gov/nasa/jpf/util/UnsortedArrayIntSet.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 package gov.nasa.jpf.util;
  19
  20 /**
  21  * a simplistic IntSet implementation that uses an unsorted array to keep elements.
  22  * Obviously this is O(N) and therefore not a good choice if the list grows,
  23  * but if we know there are only a few elements then it isn't worth to
  24  * do any sorting or fancy lookup - the JIT would beat algorithm.
  25  *
  26  * If the set is empty there is no memory allocated for the elements
  27  */
  28 public class UnsortedArrayIntSet extends ArrayIntSet {
  29
  30   static final int DEFAULT_CAPACITY = 4;
  31   static final int GROWTH = 8;
  32
  33   public UnsortedArrayIntSet (){
  34     // nothing
  35   }
  36
  37   public UnsortedArrayIntSet (int initialCapacity){
  38     super(initialCapacity);
  39   }
  40
  41
  42
  43   @Override
  44   public boolean add (int v) {
  45     int len = size;
  46     if (len == 0){
  47       elements = new int[DEFAULT_CAPACITY];
  48
  49     } else {
  50       int[] a = elements;
  51       int i=0;
  52       for (; i<len; i++){
  53         if (a[i] == v){
  54           return false; // was already there
  55         }
  56       }
  57
  58       if (i == a.length){
  59         int[] newElements = new int[a.length + GROWTH];
  60         System.arraycopy(a, 0, newElements, 0, size);
  61         elements = newElements;
  62       }
  63     }
  64
  65     elements[size++] = v;
  66     return true;
  67   }
  68
  69   @Override
  70   public boolean remove(int v) {
  71     int len = size;
  72     if (len > 0){
  73       int[] a = elements;
  74       for (int i=0; i<len; i++){
  75         if (a[i] == v){
  76           if (len == 1){
  77             elements = null;
  78           } else {
  79             i++;
  80             if (i < len) {
  81               System.arraycopy(a, i, a, i-1, len-i);
  82             }
  83           }
  84
  85           size--;
  86           return true;
  87         }
  88       }
  89     }
  90
  91     return false; // wasn't there
  92   }
  93
  94   @Override
  95   public boolean contains(int v) {
  96     int len = size;
  97     if (len > 0){
  98       int[] a = elements;
  99       for (int i=0; i<len; i++){
 100         if (a[i] == v){
 101           return true;
 102         }
 103       }
 104     }
 105
 106     return false;
 107   }
 108 }