Mercurial > hg > Members > kono > jpf-core

comparison src/main/gov/nasa/jpf/util/DynamicObjectArray.java @ 0:61d41facf527

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial v8 import (history reset)
author Peter Mehlitz <Peter.C.Mehlitz@nasa.gov>
date Fri, 23 Jan 2015 10:14:01 -0800
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:61d41facf527
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 }