src/main/gov/nasa/jpf/util/SortedArrayIntSet.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 /**
  22  * a set of integers that uses a simple sorted int array and binary search
  23  *
  24  * To be used in a context where
  25  *
  26  *  - the number of elements does not have a hard limit
  27  *  - the number of elements is assumed to be small, but potentially sparse
  28  *  - the following operations are time critical
  29  *     + inclusion check
  30  *     + size check
  31  *     + cloning
  32  *     + iteration over elements
  33  *  - adding/removing should be better than O(N)
  34  *
  35  */
  36 public class SortedArrayIntSet extends ArrayIntSet {
  37
  38   static final int DEFAULT_CAPACITY = 8;
  39   static final int GROWTH = 8;
  40
  41   //--- private methods
  42
  43   // returns the index where the match should be
  44   // caller has to make sure size > 0
  45   protected final int bisect (int val){
  46     int min = 0;
  47     int max = size-1;
  48     int[] a = elements;
  49
  50     while (max > min) {
  51       int mid = (min + max) / 2;
  52
  53       if (a[mid] < val) {
  54         min = mid + 1;
  55       } else {
  56         max = mid;
  57       }
  58     }
  59
  60     return min;
  61   }
  62
  63
  64   // if we already have elements, idx has to be within range
  65   protected final void insertElement (int idx){
  66     if (elements == null){
  67       elements = new int[DEFAULT_CAPACITY];
  68
  69     } else {
  70       int[] a = elements;
  71
  72       if (size == a.length){
  73         int newLength = a.length + GROWTH;
  74         int[] newElements = new int[newLength];
  75         if (idx > 0){
  76           System.arraycopy(a, 0, newElements, 0, idx);
  77         }
  78         if (idx < size){
  79           System.arraycopy(a, idx, newElements, idx+1, size-idx);
  80         }
  81         elements = newElements;
  82
  83       } else {
  84         System.arraycopy(a, idx, a, idx+1, size-idx);
  85       }
  86     }
  87   }
  88
  89
  90   //--- public methods
  91
  92   public SortedArrayIntSet (){
  93     // nothing
  94   }
  95
  96   public SortedArrayIntSet (int initialCapacity){
  97     super(initialCapacity);
  98   }
  99
 100   @Override
 101   public boolean contains (int v) {
 102     return ((size > 0) && elements[bisect(v)] == v);
 103   }
 104
 105   @Override
 106   public boolean add (int v){
 107     if (size == 0){
 108       elements = new int[DEFAULT_CAPACITY];
 109       elements[0] = v;
 110       size++;
 111       return true;
 112
 113     } else {
 114       int i = bisect(v);
 115       int e = elements[i];
 116       if (e != v){
 117         if (e < v) {
 118           i++;
 119         }
 120
 121         insertElement(i);
 122         elements[i] = v;
 123         size++;
 124         return true;
 125
 126       } else {
 127         return false; // was already there
 128       }
 129     }
 130   }
 131
 132   @Override
 133   public boolean remove (int v) {
 134     int len = size;
 135
 136     if (len > 0){
 137       int[] a = elements;
 138       int i = bisect(v);
 139       if (a[i] == v) {
 140         len--;
 141         if (len == 0){
 142           elements = null;
 143           size = 0;
 144
 145         } else {
 146           if (i < len){
 147             System.arraycopy(a, i + 1, a, i, (len - i));
 148           }
 149           size = len;
 150         }
 151
 152         return true;
 153       }
 154     }
 155
 156     return false; // wasn't there
 157   }
 158
 159 }