1 /*
2 * Copyright (c) 2003-2008 by Cosylab d. d.
3 *
4 * This file is part of Java-Common.
5 *
6 * Java-Common is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * Java-Common is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with Java-Common. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 package com.cosylab.util;
21
22 /**
23 * This is a gadget for storing values of prmitive <code>double</code> type
24 * with <code>java.lang.ArrayList</code>-like functionality and
25 * considerably better performance.
26 *
27 * Woohoo!
28 *
29 * @author <a href="mailto:gasper.pajor@cosylab.com">Gasper Pajor</a>
30 * @version $id$
31 *
32 */
33 public class ResizableDoubleList {
34
35 private double[] bufferArray;
36 private double[] compactArray;
37
38 // Relevant array is always between foi and fei (foi <= i < fei)
39 // If foi == fei the relevant array is empty.
40
41 private int foi; // first occupied index
42 private int fei; // first empty index
43
44 /**
45 * Constructor for ResizableDoubleList. Calls <code>this(10)</code> constructor.
46 */
47 public ResizableDoubleList() {
48 this(10);
49 }
50 /**
51 * Constructor for ResizableDoubleList.
52 * @param initialBufferSize the initial size of buffer array into which the values are stored.
53 */
54 public ResizableDoubleList(int initialBufferSize) {
55 super();
56 bufferArray = new double[initialBufferSize];
57 foi = 0;
58 fei = 0;
59 }
60
61 /**
62 * Adds a single value to the end of the array.
63 * @param d value to add
64 */
65 public void add(double d){
66
67 assureAddition(1);
68 bufferArray[fei]=d;
69 fei++;
70
71 }
72
73 /**
74 * Adds array of doubles to the end of the array.
75 * @param da array to add
76 */
77 public void add(double[] da){
78
79 assureAddition(da.length);
80 System.arraycopy(da,0,bufferArray,fei,da.length);
81 fei=fei+da.length;
82
83 }
84
85 /**
86 * Adds a single value at specified index. All values that have index equal to
87 * or larger than specified index increase their indexes by one.
88 * @param d value to add
89 * @param index the index at which the value will be inserted
90 */
91 public void add(double d, int index){
92
93 assureAddition(1);
94 if (checkIndex(index)) {
95
96 double[] tempArray = new double[fei-index];
97 System.arraycopy(bufferArray, index, tempArray, 0, tempArray.length);
98 bufferArray[index] = d;
99 System.arraycopy(tempArray,0,bufferArray, index+1, tempArray.length);
100 fei++;
101
102 } else {
103 throw new IndexOutOfBoundsException("Cannot add to specified index. Index: "+index+", Size: "+size()+".");
104 }
105 }
106
107
108 /**
109 * Adds an array of doubles at specified index. All values that have index equal to
110 * or larger than specified index increase their indexes by the lenght of the added array.
111 * @param da array to add
112 * @param index the index at which the array will be inserted
113 */
114 public void add(double[] da, int index){
115
116 assureAddition(da.length);
117 if (checkIndex(index)) {
118 double[] tempArray = new double[fei-index];
119 // values stored to tempArray for appending after the insertion of new array
120 System.arraycopy(bufferArray, index, tempArray, 0, tempArray.length);
121 // new array (da) is copied into bufferArray
122 System.arraycopy(da,0,bufferArray,index, da.length);
123 // appending tempArray
124 System.arraycopy(tempArray,0,bufferArray,index+da.length,tempArray.length);
125 fei = fei + da.length;
126 } else {
127 throw new IndexOutOfBoundsException("Cannot add to specified index. Index: "+index+", Size: "+size()+".");
128 }
129 }
130
131 /**
132 * Removes the specified number of values from (including) specified index onwards.
133 * @param index the index of first value to remove
134 * @param lenght the number of values to remove
135 */
136 public void remove(int index, int lenght){
137 if (lenght == 0) return;
138 if (checkIndex(index) && checkIndex(index+lenght-1)) {
139 if (index == 0){
140 foi = foi + lenght;
141 } else if (index+lenght == fei) {
142 fei = index;
143 } else {
144 double[] tempArray = new double[fei-(foi+index+lenght)];
145 // copies what is after the removed part into temp array
146 System.arraycopy(bufferArray, foi+index+lenght, tempArray, 0, tempArray.length);
147 // copies that back, shifted for lenght
148 System.arraycopy(tempArray, 0, bufferArray, foi+index, tempArray.length);
149 fei = fei - lenght;
150 }
151 downSize();
152 } else throw new IndexOutOfBoundsException("Cannot remove from index "+index+" to index "+(index+lenght-1) +". Size: "+size()+".");
153 }
154
155
156 /**
157 * Checks if the buffer array is to large and trimms it to prevent memory leak.
158 */
159 private void downSize() {
160 if (size()<0.25*bufferArray.length && bufferArray.length > 20) {
161 double[] tempArray = new double[(int)(0.5*bufferArray.length+1)];
162 System.arraycopy(bufferArray, foi, tempArray,0,size());
163 bufferArray = tempArray;
164 fei = fei - foi;
165 foi = 0;
166 }
167 }
168
169
170
171 /**
172 * Gets the size of the array.
173 * @return int the size of the array
174 */
175 public int size(){
176
177 return fei-foi;
178 }
179
180 /**
181 * Gets the whole array
182 * @return double[] the array
183 */
184 public double[] getArray(){
185
186 if ((compactArray==null) || (compactArray.length!=(fei-foi))) compactArray = new double[fei-foi];
187 System.arraycopy(bufferArray,foi, compactArray, 0, compactArray.length);
188
189
190 return compactArray;
191 }
192
193 /**
194 * Gets the sub-array of specified lenght from the specified index
195 * @param index the index
196 * @param lenght the lenght
197 * @return double[] the sub-array
198 */
199 public double[] getArray(int index, int lenght){
200 if (lenght == 0) return new double[0];
201 if (checkIndex(index) && checkIndex(index+lenght-1)) {
202 if ((compactArray==null) || (compactArray.length!=(lenght))) compactArray = new double[lenght];
203 System.arraycopy(bufferArray,foi+index, compactArray, 0, compactArray.length);
204 return compactArray;
205 }
206 else throw new IndexOutOfBoundsException("Cannot get sub-array from index "+index+" to index "+(index+lenght-1) +". Size: "+size()+".");
207 }
208
209 /**
210 * Gets sub-array from specified index onwards.
211 * @param index the index
212 * @return double[] the sub-array
213 */
214 public double[] getArray(int index){
215 if (checkIndex(index)) {
216 if ((compactArray==null) || (compactArray.length!=(fei-index))) compactArray = new double[fei-index];
217 System.arraycopy(bufferArray, index, compactArray, 0, compactArray.length);
218 return compactArray;
219 }
220 else throw new IndexOutOfBoundsException("Cannot get sub-array from index "+index+" onwards. Size: "+size()+".");
221 }
222
223 /**
224 * Gets the value at specified index.
225 * @param index the index
226 * @return double the value at index
227 */
228 public double get(int index){
229 if (checkIndex(index)){
230 return bufferArray[foi+index];
231 }
232 else throw new IndexOutOfBoundsException("Cannot get value from index "+index+". Size: "+size());
233 }
234
235 /**
236 * Sets the value at specified index.
237 * @param index the index
238 * @param value the new value
239 */
240 public void set(int index, double value){
241 if (checkIndex(index)){
242 bufferArray[foi+index] = value;
243 }
244 else throw new IndexOutOfBoundsException("Cannot set value at index "+index+". Size: "+size()+".");
245 }
246
247 /**
248 * Enlarges the array, if it is to small for adding new elements.
249 * @param i the number of new elements
250 */
251 private void assureAddition(int i) {
252 if (i < 0) return;
253 int freeSpacesEnd = bufferArray.length - 1 - fei;
254 if (i < freeSpacesEnd) return;
255 else {
256 double[] tempArray;
257 if (2*size()+i > bufferArray.length) tempArray = new double[2*size()+i];
258 else tempArray = bufferArray;
259 System.arraycopy(bufferArray, foi, tempArray,0,size());
260 bufferArray = tempArray;
261 fei = fei - foi;
262 foi = 0;
263 }
264 }
265
266 /**
267 * Validates the index.
268 * @param index the index to validate
269 * @return boolean true if the index is valid, false otherwise
270 */
271 private boolean checkIndex(int index) {
272 if (foi+index<fei /*|| (fei==foi && foi==index)*/) return true;
273 else return false;
274 }
275
276 /**
277 * This method is for testing and debuging purposes only.
278 * It returns the buffered array from within which the array or relevant values is stored.
279 * There should be no need to call this method unless you want to check the working of this class.
280 * @return double[] the buffer array
281 */
282 public double[] getBufferArray(){
283 return bufferArray;
284 }
285 /**
286 *
287 * Run test applet.
288 * @param args command line parameters
289 */
290 public static void main(String[] args){
291
292 //ArrayList a = new ArrayList();
293 //a.add(3, "Lala");
294 ResizableDoubleList list = new ResizableDoubleList(10);
295 list.displayIndexes();
296 list.displayRelevant();
297
298 list.add(0);
299 list.add(1);
300 list.add(2);
301 list.add(3);
302 list.add(4);
303 list.add(5);
304 list.add(6);
305 list.add(7);
306 list.add(8);
307 list.add(9);
308 list.displayRelevant();
309
310 list.remove(0,3);
311 list.displayRelevant();
312 list.remove(0,3);
313 list.displayRelevant();
314 list.remove(0,3);
315 list.displayRelevant();
316 list.remove(0,3);
317 list.displayRelevant();
318
319 /*
320 list.add(new double[]{4,6});
321 list.displayRelevant();
322
323 list.add(5,5);
324 list.displayRelevant();
325
326 list.add(0);
327 list.displayRelevant();
328 list.add(1);
329 list.displayRelevant();
330 list.add(2);
331 list.displayRelevant();
332 list.add(3);
333 list.displayRelevant();
334
335 list.add(new double[]{4,6});
336 list.displayRelevant();
337
338 list.add(5,5);
339 list.displayRelevant();
340
341 list.add(new double[]{2.1,2.2,2.3},3);
342 list.displayRelevant();
343
344 list.remove(0,2);
345 list.displayRelevant();
346
347 list.remove(0,2);
348 list.displayRelevant();
349
350 list.remove(0,2);
351 list.displayRelevant();
352
353
354
355
356
357
358 /* for (int i =0; i <list.size(); i++) System.out.println("Index: "+ i +" Value:" + list.get(i));
359
360 list.remove(1,2);
361 System.out.println("\nRemoving 2 at index 1\n");
362
363 for (int i =0; i <list.size(); i++) System.out.println("Index: "+ i +" Value:" + list.get(i));
364
365 list.remove(3,4);
366
367 System.out.println("\nRemoving 4 at index 3\n");
368
369 for (int i =0; i <list.size(); i++) System.out.println("Index: "+ i +" Value:" + list.get(i));
370
371 System.out.println("\n"+(int)(10 / 3));
372 */
373 }
374
375 /**
376 * This is merely a debug method.
377 */
378 public void displayRelevant(){
379
380 System.out.print("\n[");
381 for (int i = 0; i < foi; i++){
382 System.out.print("... ");
383 }
384 for (int i = foi; i < fei; i++){
385 System.out.print(get(i-foi)+" ");
386
387 }
388 for (int i = fei; i < bufferArray.length; i++){
389 System.out.print("... ");
390 }
391 System.out.print("] FOI: "+foi+" FEI: "+fei);
392 }
393 /**
394 * This is merely a debug method.
395 */
396 public void displayIndexes(){
397
398 System.out.print("\n ");
399 for (int i = 0; i < bufferArray.length; i++) {
400 if (i < 10) System.out.print(" "+i+" ");
401 else if (i<100) System.out.print(" "+i+" ");
402 else System.out.print(""+i+" ");
403 }
404
405 System.out.print(" ");
406 }
407
408
409
410 }