src/main/gov/nasa/jpf/util/SortedArrayObjectSet.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 java.util.Iterator;
  22 import java.util.NoSuchElementException;
  23
  24 /**
  25  * a generic set of comparable objects with value based inclusion check
  26  * (i.e. using equals())
  27  * objects that return compareTo() == 0 are entered LIFO
  28  */
  29 public class SortedArrayObjectSet<T extends Comparable<T>> implements Iterable<T> {
  30
  31   static final int DEFAULT_CAPACITY = 8;
  32   static final int GROWTH = 8;
  33
  34   class StorageIterator implements Iterator<T>{
  35     int next;
  36
  37     @Override
  38         public boolean hasNext() {
  39       return (next < size);
  40     }
  41
  42     @Override
  43         public T next() {
  44       if (next < size){
  45         return (T)elements[next++];
  46       } else {
  47         throw new NoSuchElementException();
  48       }
  49     }
  50
  51     @Override
  52         public void remove() {
  53       int idx = next-1;
  54       if (idx >=0){
  55         if (idx < size-1){
  56           System.arraycopy(elements, next, elements, idx, size-idx);
  57         }
  58         size--;
  59         next = idx;
  60       }
  61     }
  62   }
  63
  64
  65   int size;
  66   Comparable<T>[] elements;
  67
  68   //--- private methods
  69
  70   // returns the index where the match should be
  71   // caller has to make sure size > 0
  72   protected final int bisect (T val){
  73     int min = 0;
  74     int max = size-1;
  75     Comparable<T>[] a = elements;
  76
  77     while (max > min) {
  78       int mid = (min + max) / 2;
  79
  80       if (a[mid].compareTo(val) < 0) {
  81         min = mid + 1;
  82       } else {
  83         max = mid;
  84       }
  85     }
  86
  87     return min;
  88   }
  89
  90
  91   // if we already have elements, idx has to be within range
  92   protected final void insertElement (int idx){
  93     if (elements == null){
  94       elements = new Comparable[DEFAULT_CAPACITY];
  95
  96     } else {
  97       Comparable[] a = elements;
  98
  99       if (size == a.length){
 100         int newLength = a.length + GROWTH;
 101         Comparable[] newElements = new Comparable[newLength];
 102         if (idx > 0){
 103           System.arraycopy(a, 0, newElements, 0, idx);
 104         }
 105         if (idx < size){
 106           System.arraycopy(a, idx, newElements, idx+1, size-idx);
 107         }
 108         elements = newElements;
 109
 110       } else {
 111         System.arraycopy(a, idx, a, idx+1, size-idx);
 112       }
 113     }
 114   }
 115
 116
 117   //--- public methods
 118
 119   public SortedArrayObjectSet (){
 120     // nothing
 121   }
 122
 123   public SortedArrayObjectSet (int initialCapacity){
 124     elements = new Comparable[initialCapacity];
 125   }
 126
 127   public int size(){
 128     return size;
 129   }
 130
 131   public boolean isEmpty(){
 132     return (size == 0);
 133   }
 134
 135   public boolean contains (T v) {
 136     return ((size > 0) && elements[bisect(v)].equals(v));
 137   }
 138
 139   public void add (T v){
 140     if (size == 0){
 141       elements = new Comparable[DEFAULT_CAPACITY];
 142       elements[0] = v;
 143       size++;
 144
 145     } else {
 146       int i = bisect(v);
 147       Comparable<T> e = elements[i];
 148       if (!e.equals(v)){
 149         if (e.compareTo(v) < 0){
 150           i++;
 151         }
 152
 153         insertElement(i);
 154         elements[i] = v;
 155         size++;
 156       }
 157     }
 158   }
 159
 160   public void remove (T v) {
 161     int len = size;
 162
 163     if (len > 0){
 164       Comparable<T>[] a = elements;
 165
 166       for (int i = bisect(v); i<size && a[i].compareTo(v) == 0; i++) {
 167         if (v.equals(a[i])){
 168           len--;
 169           if (len == 0) {
 170             elements = null;
 171             size = 0;
 172
 173           } else {
 174             if (i < len) {
 175               System.arraycopy(a, i + 1, a, i, (len - i));
 176             }
 177             size = len;
 178           }
 179
 180           return;
 181         }
 182       }
 183     }
 184   }
 185
 186   @Override
 187   public Iterator<T> iterator(){
 188     return new StorageIterator();
 189   }
 190
 191   @Override
 192   public String toString (){
 193
 194     StringBuilder sb = new StringBuilder("{");
 195
 196     for (int i=0; i<size; i++){
 197       if (i > 0){
 198         sb.append(',');
 199       }
 200       sb.append(elements[i]);
 201     }
 202
 203     sb.append('}');
 204     return sb.toString();
 205   }
 206 }