Mercurial > hg > Members > kono > jpf-core
view src/main/gov/nasa/jpf/util/DynamicObjectArray.java @ 0:61d41facf527
initial v8 import (history reset)
author | Peter Mehlitz <Peter.C.Mehlitz@nasa.gov> |
---|---|
date | Fri, 23 Jan 2015 10:14:01 -0800 |
parents | |
children |
line wrap: on
line source
/* * Copyright (C) 2014, United States Government, as represented by the * Administrator of the National Aeronautics and Space Administration. * All rights reserved. * * The Java Pathfinder core (jpf-core) platform is licensed under the * Apache License, Version 2.0 (the "License"); you may not use this file except * in compliance with the License. You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0. * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package gov.nasa.jpf.util; import java.util.Iterator; /** * simplistic Object array that differentiates from ArrayList by * using chunks instead of exponential growth, thus efficiently dealing * with huge, potentially sparse arrays * * the motivation for this class is memory optimization, i.e. space efficient * storage of potentially huge arrays without good a-priori size guesses * * this class is awfully lifted from DynamicIntArray (same motivation, but * primitive types - not much factorizable functionality w/o excessive * casting/boxing) * * the API of this class is between a primitive array and a AbstractList. Since * it handles Objects, we could turn this into a Collection (and probably should) * * NOTE: like standard Collection implementations/arrays, this class is not * synchronized */ public final class DynamicObjectArray<E> implements Iterable<E> { final static int DEFAULT_CHUNKBITS = 8; final static int INIT_CHUNKS = 16; /** growth strategy */ Growth growth; /** our allocation sizes */ int chunkBits; int nPerChunk; // just a cache for (1<<chunkBits) /** mask for index within chunk */ int chunkMask; /** the real data. limitations in generics prevent use of E[][] */ Object[][] data; /** the maximum index set so far */ int maxIndex = -1; class DynIterator implements Iterator<E> { int i; @Override public boolean hasNext() { return (i<size()); } @Override public E next() { return get(i++); } @Override public void remove() { throw new UnsupportedOperationException(); } } public DynamicObjectArray () { this(Growth.defaultGrowth, DEFAULT_CHUNKBITS, INIT_CHUNKS); } /** * Creates a DynamicObjectArray in which each chunk has 2**chunkBits elements * and initChunks chunks are initially allocated. */ public DynamicObjectArray (int chunkBits, int initChunks) { this(Growth.defaultGrowth, chunkBits, initChunks); } public DynamicObjectArray (Growth strategy, int chunkBits, int initChunks) { if (chunkBits > 20) throw new IllegalArgumentException(); this.chunkBits = chunkBits; nPerChunk = 1<<chunkBits; this.chunkMask = nPerChunk - 1; data = new Object[initChunks][]; growth = strategy; } @Override public Iterator<E> iterator() { return new DynIterator(); } @SuppressWarnings("unchecked") public E get (int index) { int i = index >> chunkBits; if (i < data.length && data[i] != null) { int j = index & chunkMask; return (E) data[i][j]; } else { return null; } } // this is only the max size, not the max index that was accessed/set public int size() { return data.length * nPerChunk; } public int getMaxIndex() { return maxIndex; } public void set (int index, E value) { if (index > maxIndex) { maxIndex = index; } int i = index >> chunkBits; int j = index & chunkMask; if (i >= data.length) { int nChunks = growth.grow(data.length, i+1); Object[][] newChunks = new Object[nChunks][]; System.arraycopy(data, 0, newChunks, 0, data.length); data = newChunks; } if (data[i] == null) { data[i] = new Object[1 << chunkBits]; } data[i][j] = value; } @Override public String toString() { int length = data.length * (1 << chunkBits); while (length > 1 && get(length-1) == null) length--; StringBuilder sb = new StringBuilder(length); sb.append('{'); int l = length-1; for (int i=0; i<l; i++) { sb.append(get(i)); sb.append(','); } sb.append(get(l)); sb.append('}'); return sb.toString(); } // removed toArray method, which is confusing for 1.5 }