src/main/gov/nasa/jpf/util/IdentityArrayObjectSet.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  * simple identity set for objects
  26  * we don't sort&bisect, assuming the number of entries will be small
  27  * be aware this doesn't scale to large sets
  28  */
  29 public class IdentityArrayObjectSet<E> implements IdentityObjectSet<E> {
  30
  31   static final int DEFAULT_CAPACITY = 4;
  32
  33   private class StoreOrderIterator implements Iterator<E> {
  34     int next = 0;
  35
  36     @Override
  37     public void remove() {
  38       int idx = next-1;
  39       if (idx >=0){
  40         if (idx < size-1){
  41           System.arraycopy(elements, next, elements, idx, size-idx);
  42         }
  43         size--;
  44         next = idx;
  45       }
  46     }
  47
  48     @Override
  49     public boolean hasNext() {
  50       return (next < size);
  51     }
  52
  53     @Override
  54     public E next() {
  55       if (next < size){
  56         return (E) elements[next++];
  57       } else {
  58         throw new NoSuchElementException();
  59       }
  60     }
  61   }
  62
  63   protected int size;
  64   protected Object[] elements;
  65
  66   public IdentityArrayObjectSet(){
  67     // nothing, elements allocated on demand
  68   }
  69
  70   public IdentityArrayObjectSet (int initialCapacity){
  71     elements = new Object[initialCapacity];
  72   }
  73
  74   public IdentityArrayObjectSet (E initialElement){
  75     elements = new Object[DEFAULT_CAPACITY];
  76
  77     elements[0] = initialElement;
  78     size = 1;
  79   }
  80
  81   @Override
  82   public int size(){
  83     return size;
  84   }
  85
  86   public boolean isEmpty(){
  87     return (size == 0);
  88   }
  89
  90   @Override
  91   public boolean add (E obj){
  92     for (int i=0; i<size; i++){
  93       if (elements[i] == obj){
  94         return false;
  95       }
  96     }
  97
  98     if (size == 0){
  99       elements = new Object[DEFAULT_CAPACITY];
 100     } else if (size == elements.length){
 101       Object[] newElements = new Object[elements.length * 3 / 2];
 102       System.arraycopy(elements, 0, newElements, 0, size);
 103       elements = newElements;
 104     }
 105
 106     elements[size] = obj;
 107     size++;
 108     return true;
 109   }
 110
 111   @Override
 112   public boolean contains (E obj){
 113     for (int i=0; i<size; i++){
 114       if (elements[i] == obj){
 115         return true;
 116       }
 117     }
 118
 119     return false;
 120   }
 121
 122   @Override
 123   public boolean remove (E obj){
 124     int len = size;
 125     for (int i=0; i<len; i++){
 126       if (elements[i] == obj){
 127         len--;
 128         if (len == 0){
 129           size = 0;
 130           elements = null;
 131
 132         } else if (i < len){
 133           System.arraycopy(elements, i+1, elements, i, len-i);
 134         } else {
 135           elements[len] = null; // avoid memory leak
 136         }
 137
 138         size = len;
 139         return true;
 140       }
 141     }
 142
 143     return false;
 144   }
 145
 146   @Override
 147   public ObjectSet<E> clone(){
 148     try {
 149       return (ObjectSet<E>)super.clone();
 150     } catch (CloneNotSupportedException x){
 151       // can't happen
 152       return null;
 153     }
 154   }
 155
 156   @Override
 157   public Iterator<E> iterator(){
 158     return new StoreOrderIterator();
 159   }
 160
 161   @Override
 162   public String toString(){
 163     StringBuilder sb = new StringBuilder(/*getClass().getName()*/);
 164     sb.append('{');
 165     for (int i=0; i<size; i++){
 166       if (i>0){
 167         sb.append(',');
 168       }
 169       sb.append(elements[i]);
 170     }
 171     sb.append('}');
 172     return sb.toString();
 173   }
 174 }