001: //
002: // Copyright (C) 2005 United States Government as represented by the
003: // Administrator of the National Aeronautics and Space Administration
004: // (NASA). All Rights Reserved.
005: //
006: // This software is distributed under the NASA Open Source Agreement
007: // (NOSA), version 1.3. The NOSA has been approved by the Open Source
008: // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
009: // directory tree for the complete NOSA document.
010: //
011: // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
012: // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
013: // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
014: // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
015: // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
016: // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
017: // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
018: //
019: package gov.nasa.jpf.util;
020:
021: /**
022: * simplistic dynamic array that differentiates from ArrayList by
023: * - using chunks instead of exponential growth, thus efficiently dealing
024: * with sparse arrays
025: * - managing primitive 'int' types, i.e. not requiring box objects
026: *
027: * the motivation for this class is memory optimization, i.e. space efficient
028: * storage of potentially huge arrays without good a-priori size guesses
029: *
030: * the API of this class is between a primitive array and a AbstractList. It's
031: * not a Collection implementation because it handles primitive types, but the
032: * API could be extended to support iterators and the like.
033: *
034: * NOTE: like standard Collection implementations/arrays, this class is not
035: * synchronized
036: */
037: public class DynamicIntArray {
038: final static int DEFAULT_CHUNKSIZE = 256;
039: final static int INIT_CHUNKS = 16;
040:
041: int chunkSize;
042: /** our allocation sizes */
043: int[][] data;
044: /** the real data */
045: int length;
046:
047: /** max set element index +1 */
048:
049: public DynamicIntArray() {
050: this (DEFAULT_CHUNKSIZE);
051: }
052:
053: public DynamicIntArray(int chunkSize) {
054: this .chunkSize = chunkSize;
055:
056: data = new int[INIT_CHUNKS][];
057: }
058:
059: public boolean isEmpty() {
060: return (length == 0);
061: }
062:
063: /**
064: * Ensure that the given index is valid.
065: */
066: public void grow(int index) {
067: if (index >= length) {
068: int i = index / chunkSize;
069: int j = index % chunkSize;
070:
071: if (i >= data.length) {
072: // grow the meta-array by 50%
073: int new_size = (i * 3) / 2 + 1;
074: int[][] newChunk = new int[new_size][];
075: System.arraycopy(data, 0, newChunk, 0, data.length);
076: data = newChunk;
077: }
078: length = index + 1;
079: }
080: }
081:
082: public int get(int index) {
083: if (index >= length) {
084: throw new IndexOutOfBoundsException("Index " + index
085: + " is outside of 0.." + (length - 1));
086: }
087: int i = index / chunkSize;
088: int j = index % chunkSize;
089:
090: if (data[i] == null) {
091: return 0;
092: } else {
093: return data[i][j];
094: }
095: }
096:
097: public void set(int index, int value) {
098: int i = index / chunkSize;
099: int j = index % chunkSize;
100:
101: grow(index);
102: // fill in the meta-array, if necessary
103: if (data[i] == null) {
104: data[i] = new int[chunkSize];
105: }
106: data[i][j] = value;
107: }
108:
109: public int size() {
110: return length;
111: }
112:
113: public String toString() {
114: int i;
115: StringBuffer sb = new StringBuffer(length * 4);
116:
117: sb.append('{');
118: int l = length - 1;
119: for (i = 0; i < l; i++) {
120: sb.append(get(i));
121: sb.append(',');
122: }
123: sb.append(get(i));
124: sb.append('}');
125:
126: return sb.toString();
127: }
128:
129: public int[] toArray(int[] buf) {
130: if (buf.length < length) {
131: buf = new int[length];
132: }
133: for (int i = 0; i < length; i++) {
134: buf[i] = get(i);
135: }
136:
137: return buf;
138: }
139:
140: /**************************** debug & test ************
141: public void dump () {
142: int i, j;
143: for (i=0; i<chunk.length; i++) {
144: System.out.print( "[" + i + "]: ");
145: if (chunk[i] != null) {
146: System.out.print("{");
147: int l = chunk[i].length-1;
148: for (j=0; j<l; j++) {
149: System.out.print(chunk[i][j]);
150: System.out.print(',');
151: }
152: System.out.print( chunk[i][j]);
153: System.out.println("}");
154: } else {
155: System.out.println( "null");
156: }
157: }
158: }
159:
160: public static void main (String[] args) {
161: int i;
162: DynamicIntArray a = new DynamicIntArray(8);
163:
164: a.set(0, 42);
165: a.set(13,13);
166: a.set(24, 42);
167:
168: System.out.println( "--------- " + a.size());
169: System.out.println(a);
170: System.out.println(); System.out.println();
171: a.dump();
172: }
173: ***************************** end debug & test *********/
174: }
|