src/main/gov/nasa/jpf/util/DynamicObjectArray.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.Iterator;
  21
  22 /**
  23  * simplistic Object array that differentiates from ArrayList by
  24  * using chunks instead of exponential growth, thus efficiently dealing
  25  * with huge, potentially sparse arrays
  26  *
  27  * the motivation for this class is memory optimization, i.e. space efficient
  28  * storage of potentially huge arrays without good a-priori size guesses
  29  *
  30  * this class is awfully lifted from DynamicIntArray (same motivation, but
  31  * primitive types - not much factorizable functionality w/o excessive
  32  * casting/boxing)
  33  *
  34  * the API of this class is between a primitive array and a AbstractList. Since
  35  * it handles Objects, we could turn this into a Collection (and probably should)
  36  *
  37  * NOTE: like standard Collection implementations/arrays, this class is not
  38  * synchronized
  39  */
  40
  41 public final class DynamicObjectArray<E> implements Iterable<E> {
  42   final static int DEFAULT_CHUNKBITS = 8;
  43   final static int INIT_CHUNKS = 16;
  44
  45   /** growth strategy */
  46   Growth growth;
  47
  48   /** our allocation sizes */
  49   int chunkBits;
  50   int nPerChunk; // just a cache for (1<<chunkBits)
  51
  52   /** mask for index within chunk */
  53   int chunkMask;
  54
  55   /** the real data. limitations in generics prevent use of E[][] */
  56   Object[][] data;
  57
  58   /** the maximum index set so far */
  59   int maxIndex = -1;
  60
  61   class DynIterator implements Iterator<E> {
  62     int i;
  63
  64     @Override
  65         public boolean hasNext() {
  66       return (i<size());
  67     }
  68
  69     @Override
  70         public E next() {
  71       return get(i++);
  72     }
  73
  74     @Override
  75         public void remove() {
  76       throw new UnsupportedOperationException();
  77     }
  78   }
  79
  80   public DynamicObjectArray () {
  81     this(Growth.defaultGrowth, DEFAULT_CHUNKBITS, INIT_CHUNKS);
  82   }
  83
  84   /**
  85    * Creates a DynamicObjectArray in which each chunk has 2**chunkBits elements
  86    * and initChunks chunks are initially allocated.
  87    */
  88   public DynamicObjectArray (int chunkBits, int initChunks) {
  89     this(Growth.defaultGrowth, chunkBits, initChunks);
  90   }
  91
  92   public DynamicObjectArray (Growth strategy, int chunkBits, int initChunks) {
  93     if (chunkBits > 20) throw new IllegalArgumentException();
  94     this.chunkBits = chunkBits;
  95     nPerChunk = 1<<chunkBits;
  96     this.chunkMask = nPerChunk - 1;
  97     data = new Object[initChunks][];
  98     growth = strategy;
  99   }
 100
 101   @Override
 102   public Iterator<E> iterator() {
 103     return new DynIterator();
 104   }
 105
 106   @SuppressWarnings("unchecked")
 107   public E get (int index) {
 108     int i = index >> chunkBits;
 109     if (i < data.length && data[i] != null) {
 110       int j = index & chunkMask;
 111       return (E) data[i][j];
 112     } else {
 113       return null;
 114     }
 115   }
 116
 117   // this is only the max size, not the max index that was accessed/set
 118   public int size() {
 119     return data.length * nPerChunk;
 120   }
 121
 122   public int getMaxIndex() {
 123     return maxIndex;
 124   }
 125
 126   public void set (int index, E value) {
 127     if (index > maxIndex) {
 128       maxIndex = index;
 129     }
 130
 131     int i = index >> chunkBits;
 132     int j = index & chunkMask;
 133
 134     if (i >= data.length) {
 135       int nChunks = growth.grow(data.length, i+1);
 136       Object[][] newChunks = new Object[nChunks][];
 137       System.arraycopy(data, 0, newChunks, 0, data.length);
 138       data = newChunks;
 139     }
 140     if (data[i] == null) {
 141       data[i] = new Object[1 << chunkBits];
 142     }
 143
 144     data[i][j] = value;
 145   }
 146
 147   @Override
 148   public String toString() {
 149     int length = data.length * (1 << chunkBits);
 150     while (length > 1 && get(length-1) == null) length--;
 151
 152     StringBuilder sb = new StringBuilder(length);
 153
 154     sb.append('{');
 155     int l = length-1;
 156     for (int i=0; i<l; i++) {
 157       sb.append(get(i));
 158       sb.append(',');
 159     }
 160     sb.append(get(l));
 161     sb.append('}');
 162
 163     return sb.toString();
 164   }
 165
 166   // removed toArray method, which is confusing for 1.5
 167 }