src/main/gov/nasa/jpf/util/ArrayIntSet.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 import java.util.NoSuchElementException;
  21 import gov.nasa.jpf.JPFException;
  22
  23 /**
  24  * common base for array based IntSet implementations
  25  */
  26 public abstract class ArrayIntSet implements IntSet, Cloneable {
  27
  28   protected int size;
  29   protected int[] elements;
  30
  31   private class Iterator implements IntIterator {
  32     int next = 0;
  33
  34     @Override
  35     public void remove() {
  36       int idx = next-1;
  37       if (idx >=0){
  38         if (idx < size-1){
  39           System.arraycopy(elements, next, elements, idx, size-idx);
  40         }
  41         size--;
  42         next = idx;
  43       }
  44     }
  45
  46     @Override
  47     public boolean hasNext() {
  48       return (next < size);
  49     }
  50
  51     @Override
  52     public int next() {
  53       if (next < size){
  54         return elements[next++];
  55       } else {
  56         throw new NoSuchElementException();
  57       }
  58     }
  59   }
  60
  61   protected ArrayIntSet (){
  62     // nothing
  63   }
  64
  65   protected ArrayIntSet (int initialCapacity){
  66     elements = new int[initialCapacity];
  67   }
  68
  69   @Override
  70   public  boolean isEmpty(){
  71     return (size == 0);
  72   }
  73
  74   @Override
  75   public int size(){
  76     return size;
  77   }
  78
  79   @Override
  80   public void clear(){
  81     size = 0;
  82     elements = null;
  83   }
  84
  85   @Override
  86   public String toString(){
  87     StringBuilder sb = new StringBuilder(/*getClass().getName()*/);
  88     sb.append('{');
  89     for (int i=0; i<size; i++){
  90       if (i>0){
  91         sb.append(',');
  92       }
  93       sb.append(elements[i]);
  94     }
  95     sb.append('}');
  96     return sb.toString();
  97   }
  98
  99   @Override
 100   public ArrayIntSet clone(){
 101     try {
 102       ArrayIntSet other = (ArrayIntSet) super.clone();
 103       other.size = size;
 104       if (elements != null) {
 105         other.elements = elements.clone();
 106       }
 107       return other;
 108
 109     } catch (CloneNotSupportedException cnsx){
 110       throw new JPFException("clone failed " + this);
 111     }
 112   }
 113
 114   /**
 115    * this is probably a bad hash function, but we just need something that
 116    * is order independent
 117    */
 118   @Override
 119   public int hashCode(){
 120     int[] a = elements;
 121     int n = size;
 122     int h = (n << 16) + (n % 3);
 123
 124     for (int i = 0; i < n; i++) {
 125       int e = a[i];
 126       if (e == 0){
 127         e = Integer.MAX_VALUE;
 128       }
 129       int rot = e % 31;
 130       h ^= (h << rot) | (h >>> (32 - rot)); // rotate left
 131     }
 132
 133     return h;
 134   }
 135
 136   @Override
 137   public boolean equals (Object o){
 138     if (o instanceof IntSet){
 139       IntSet other = (IntSet)o;
 140       if (size == other.size()){
 141         int len = size;
 142         int[] a = elements;
 143         for (int i=0; i<len; i++){
 144           if (!other.contains(a[i])){
 145             return false;
 146           }
 147         }
 148         return true;
 149       }
 150     }
 151     return false;
 152   }
 153
 154   @Override
 155   public IntIterator intIterator (){
 156     return new Iterator();
 157   }
 158 }