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 Object array that differentiates from ArrayList by
023: * using chunks instead of exponential growth, thus efficiently dealing
024: * with huge, potentially sparse arrays
025: *
026: * the motivation for this class is memory optimization, i.e. space efficient
027: * storage of potentially huge arrays without good a-priori size guesses
028: *
029: * this class is awefully lifted from DynamicIntArray (same motivation, but
030: * primitive types - not much factorizable functionality w/o excessive
031: * casting/boxing)
032: *
033: * the API of this class is between a primitive array and a AbstractList. Since
034: * it handles Objects, we could turn this into a Collection (and probably should)
035: *
036: * NOTE: like standard Collection implementations/arrays, this class is not
037: * synchronized
038: */
039:
040: public class DynamicObjectArray {
041: final static int DEFAULT_CHUNKSIZE = 256;
042: final static int INIT_CHUNKS = 16;
043:
044: int chunkSize;
045: /** our allocation sizes */
046: Object[][] data;
047: /** the real data */
048: int length;
049:
050: /** max set element index +1 */
051:
052: public DynamicObjectArray() {
053: this (DEFAULT_CHUNKSIZE);
054: }
055:
056: public DynamicObjectArray(int chunkSize) {
057: this .chunkSize = chunkSize;
058:
059: data = new Object[INIT_CHUNKS][];
060: }
061:
062: public boolean isEmpty() {
063: return (length == 0);
064: }
065:
066: public Object get(int index) {
067: int i = index / chunkSize;
068: int j = index % chunkSize;
069:
070: if (data[i] == null) {
071: return null;
072: } else {
073: return data[i][j];
074: }
075: }
076:
077: public void set(int index, Object value) {
078: int i = index / chunkSize;
079: int j = index % chunkSize;
080:
081: if (i >= data.length) {
082: Object[][] newChunk = new Object[i + 1][];
083: System.arraycopy(data, 0, newChunk, 0, data.length);
084: data = newChunk;
085: }
086: if (data[i] == null) {
087: data[i] = new Object[chunkSize];
088: }
089:
090: data[i][j] = value;
091:
092: if (index >= length) {
093: length = index + 1;
094: }
095: }
096:
097: public int size() {
098: return length;
099: }
100:
101: public String toString() {
102: int i;
103: StringBuffer sb = new StringBuffer(length * 4);
104:
105: sb.append('{');
106: int l = length - 1;
107: for (i = 0; i < l; i++) {
108: sb.append(get(i));
109: sb.append(',');
110: }
111: sb.append(get(i));
112: sb.append('}');
113:
114: return sb.toString();
115: }
116:
117: public Object[] toArray(Object[] buf) {
118: if (buf.length < length) {
119: buf = new Object[length];
120: }
121: for (int i = 0; i < length; i++) {
122: buf[i] = get(i);
123: }
124:
125: return buf;
126: }
127:
128: }
|