KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gov > nasa > jpf > util > DynamicIntArray


1 //
2 // Copyright (C) 2005 United States Government as represented by the
3 // Administrator of the National Aeronautics and Space Administration
4 // (NASA). All Rights Reserved.
5 //
6 // This software is distributed under the NASA Open Source Agreement
7 // (NOSA), version 1.3. The NOSA has been approved by the Open Source
8 // Initiative. See the file NOSA-1.3-JPF at the top of the distribution
9 // directory tree for the complete NOSA document.
10 //
11 // THE SUBJECT SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY OF ANY
12 // KIND, EITHER EXPRESSED, IMPLIED, OR STATUTORY, INCLUDING, BUT NOT
13 // LIMITED TO, ANY WARRANTY THAT THE SUBJECT SOFTWARE WILL CONFORM TO
14 // SPECIFICATIONS, ANY IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR
15 // A PARTICULAR PURPOSE, OR FREEDOM FROM INFRINGEMENT, ANY WARRANTY THAT
16 // THE SUBJECT SOFTWARE WILL BE ERROR FREE, OR ANY WARRANTY THAT
17 // DOCUMENTATION, IF PROVIDED, WILL CONFORM TO THE SUBJECT SOFTWARE.
18 //
19 package gov.nasa.jpf.util;
20
21 /**
22  * simplistic dynamic array that differentiates from ArrayList by
23  * - using chunks instead of exponential growth, thus efficiently dealing
24  * with sparse arrays
25  * - managing primitive 'int' types, i.e. not requiring box objects
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  * the API of this class is between a primitive array and a AbstractList. It's
31  * not a Collection implementation because it handles primitive types, but the
32  * API could be extended to support iterators and the like.
33  *
34  * NOTE: like standard Collection implementations/arrays, this class is not
35  * synchronized
36  */
37 public class DynamicIntArray {
38   final static int DEFAULT_CHUNKSIZE = 256;
39   final static int INIT_CHUNKS = 16;
40
41   int chunkSize; /** our allocation sizes */
42   int[][] data; /** the real data */
43   int length; /** max set element index +1 */
44
45   public DynamicIntArray () {
46     this( DEFAULT_CHUNKSIZE);
47   }
48
49   public DynamicIntArray (int chunkSize) {
50     this.chunkSize = chunkSize;
51
52     data = new int[INIT_CHUNKS][];
53   }
54
55   public boolean isEmpty () {
56     return (length == 0);
57   }
58
59   /**
60    * Ensure that the given index is valid.
61    */
62   public void grow(int index) {
63     if (index >= length) {
64       int i = index / chunkSize;
65       int j = index % chunkSize;
66
67       if (i >= data.length) {
68         // grow the meta-array by 50%
69 int new_size = (i * 3) / 2 + 1;
70         int[][] newChunk = new int[new_size][];
71         System.arraycopy(data, 0, newChunk, 0, data.length);
72         data = newChunk;
73       }
74       length = index + 1;
75     }
76   }
77
78   public int get (int index) {
79     if (index >= length) {
80       throw new IndexOutOfBoundsException JavaDoc("Index " + index +
81                                             " is outside of 0.." +
82                                             (length - 1));
83     }
84     int i = index / chunkSize;
85     int j = index % chunkSize;
86
87     if (data[i] == null) {
88       return 0;
89     } else {
90       return data[i][j];
91     }
92   }
93
94   public void set (int index, int value) {
95     int i = index / chunkSize;
96     int j = index % chunkSize;
97
98     grow(index);
99     // fill in the meta-array, if necessary
100 if (data[i] == null) {
101       data[i] = new int[chunkSize];
102     }
103     data[i][j] = value;
104   }
105
106   public int size() {
107     return length;
108   }
109
110   public String JavaDoc toString() {
111     int i;
112     StringBuffer JavaDoc sb = new StringBuffer JavaDoc(length*4);
113
114     sb.append('{');
115     int l = length-1;
116     for (i=0; i<l; i++) {
117       sb.append(get(i));
118       sb.append(',');
119     }
120     sb.append(get(i));
121     sb.append('}');
122
123     return sb.toString();
124   }
125
126   public int[] toArray (int[] buf) {
127     if (buf.length < length) {
128       buf = new int[length];
129     }
130     for (int i=0; i<length; i++) {
131       buf[i] = get(i);
132     }
133
134     return buf;
135   }
136
137   /**************************** debug & test ************
138   public void dump () {
139     int i, j;
140     for (i=0; i<chunk.length; i++) {
141       System.out.print( "[" + i + "]: ");
142       if (chunk[i] != null) {
143         System.out.print("{");
144         int l = chunk[i].length-1;
145         for (j=0; j<l; j++) {
146           System.out.print(chunk[i][j]);
147           System.out.print(',');
148         }
149         System.out.print( chunk[i][j]);
150         System.out.println("}");
151       } else {
152         System.out.println( "null");
153       }
154     }
155   }
156
157   public static void main (String[] args) {
158     int i;
159     DynamicIntArray a = new DynamicIntArray(8);
160
161     a.set(0, 42);
162     a.set(13,13);
163     a.set(24, 42);
164
165     System.out.println( "--------- " + a.size());
166     System.out.println(a);
167     System.out.println(); System.out.println();
168     a.dump();
169   }
170    ***************************** end debug & test *********/
171 }
172
173
Popular Tags