KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > trove > TFloatArrayList


1 ///////////////////////////////////////////////////////////////////////////////
2
// Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
3
//
4
// This library is free software; you can redistribute it and/or
5
// modify it under the terms of the GNU Lesser General Public
6
// License as published by the Free Software Foundation; either
7
// version 2.1 of the License, or (at your option) any later version.
8
//
9
// This library is distributed in the hope that it will be useful,
10
// but WITHOUT ANY WARRANTY; without even the implied warranty of
11
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
// GNU General Public License for more details.
13
//
14
// You should have received a copy of the GNU Lesser General Public
15
// License along with this program; if not, write to the Free Software
16
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17
///////////////////////////////////////////////////////////////////////////////
18

19 package gnu.trove;
20
21 import java.io.Serializable;
22 import java.util.Arrays;
23 import java.util.Random;
24
25 /**
26  * A resizable, array-backed list of float primitives.
27  *
28  * Created: Sat Dec 29 14:21:12 2001
29  *
30  * @author Eric D. Friedman
31  * @version $Id: TFloatArrayList.java,v 1.18 2005/03/26 18:04:42 ericdf Exp $
32  */

33
34 public class TFloatArrayList implements Serializable, Cloneable {
35
36     /** compatible serialization ID - not present in 1.1b3 and earlier */
37     static final long serialVersionUID = 1L;
38
39     /** the data of the list */
40     protected float[] _data;
41
42     /** the index after the last entry in the list */
43     protected int _pos;
44
45     /** the default capacity for new lists */
46     protected static final int DEFAULT_CAPACITY = 10;
47
48     /**
49      * Creates a new <code>TFloatArrayList</code> instance with the
50      * default capacity.
51      */

52     public TFloatArrayList() {
53         this(DEFAULT_CAPACITY);
54     }
55
56     /**
57      * Creates a new <code>TFloatArrayList</code> instance with the
58      * specified capacity.
59      *
60      * @param capacity an <code>int</code> value
61      */

62     public TFloatArrayList(int capacity) {
63         _data = new float[capacity];
64         _pos = 0;
65     }
66
67     /**
68      * Creates a new <code>TFloatArrayList</code> instance whose
69      * capacity is the greater of the length of <tt>values</tt> and
70      * DEFAULT_CAPACITY and whose initial contents are the specified
71      * values.
72      *
73      * @param values an <code>float[]</code> value
74      */

75     public TFloatArrayList(float[] values) {
76         this(Math.max(values.length, DEFAULT_CAPACITY));
77         add(values);
78     }
79
80     // sizing
81

82     /**
83      * Grow the internal array as needed to accomodate the specified
84      * number of elements. The size of the array doubles on each
85      * resize unless <tt>capacity</tt> requires more than twice the
86      * current capacity.
87      *
88      * @param capacity an <code>int</code> value
89      */

90     public void ensureCapacity(int capacity) {
91         if (capacity > _data.length) {
92             int newCap = Math.max(_data.length << 1, capacity);
93             float[] tmp = new float[newCap];
94             System.arraycopy(_data, 0, tmp, 0, _data.length);
95             _data = tmp;
96         }
97     }
98
99     /**
100      * Returns the number of values in the list.
101      *
102      * @return the number of values in the list.
103      */

104     public int size() {
105         return _pos;
106     }
107
108     /**
109      * Tests whether this list contains any values.
110      *
111      * @return true if the list is empty.
112      */

113     public boolean isEmpty() {
114         return _pos == 0;
115     }
116
117     /**
118      * Sheds any excess capacity above and beyond the current size of
119      * the list.
120      */

121     public void trimToSize() {
122         if (_data.length > size()) {
123             float[] tmp = new float[size()];
124             toNativeArray(tmp, 0, tmp.length);
125             _data = tmp;
126         }
127     }
128
129     // modifying
130

131     /**
132      * Adds <tt>val</tt> to the end of the list, growing as needed.
133      *
134      * @param val an <code>float</code> value
135      */

136     public void add(float val) {
137         ensureCapacity(_pos + 1);
138         _data[_pos++] = val;
139     }
140
141     /**
142      * Adds the values in the array <tt>vals</tt> to the end of the
143      * list, in order.
144      *
145      * @param vals an <code>float[]</code> value
146      */

147     public void add(float[] vals) {
148         add(vals, 0, vals.length);
149     }
150
151     /**
152      * Adds a subset of the values in the array <tt>vals</tt> to the
153      * end of the list, in order.
154      *
155      * @param vals an <code>float[]</code> value
156      * @param offset the offset at which to start copying
157      * @param length the number of values to copy.
158      */

159     public void add(float[] vals, int offset, int length) {
160         ensureCapacity(_pos + length);
161         System.arraycopy(vals, offset, _data, _pos, length);
162         _pos += length;
163     }
164
165     /**
166      * Inserts <tt>value</tt> into the list at <tt>offset</tt>. All
167      * values including and to the right of <tt>offset</tt> are shifted
168      * to the right.
169      *
170      * @param offset an <code>int</code> value
171      * @param value an <code>float</code> value
172      */

173     public void insert(int offset, float value) {
174         if (offset == _pos) {
175             add(value);
176             return;
177         }
178         ensureCapacity(_pos + 1);
179         // shift right
180
System.arraycopy(_data, offset, _data, offset + 1, _pos - offset);
181         // insert
182
_data[offset] = value;
183         _pos++;
184     }
185
186     /**
187      * Inserts the array of <tt>values</tt> into the list at
188      * <tt>offset</tt>. All values including and to the right of
189      * <tt>offset</tt> are shifted to the right.
190      *
191      * @param offset an <code>int</code> value
192      * @param values an <code>float[]</code> value
193      */

194     public void insert(int offset, float[] values) {
195         insert(offset, values, 0, values.length);
196     }
197
198     /**
199      * Inserts a slice of the array of <tt>values</tt> into the list
200      * at <tt>offset</tt>. All values including and to the right of
201      * <tt>offset</tt> are shifted to the right.
202      *
203      * @param offset an <code>int</code> value
204      * @param values an <code>float[]</code> value
205      * @param valOffset the offset in the values array at which to
206      * start copying.
207      * @param len the number of values to copy from the values array
208      */

209     public void insert(int offset, float[] values, int valOffset, int len) {
210         if (offset == _pos) {
211             add(values, valOffset, len);
212             return;
213         }
214
215         ensureCapacity(_pos + len);
216         // shift right
217
System.arraycopy(_data, offset, _data, offset + len, _pos - offset);
218         // insert
219
System.arraycopy(values, valOffset, _data, offset, len);
220         _pos += len;
221     }
222
223     /**
224      * Returns the value at the specified offset.
225      *
226      * @param offset an <code>int</code> value
227      * @return an <code>float</code> value
228      */

229     public float get(int offset) {
230         if (offset >= _pos) {
231             throw new ArrayIndexOutOfBoundsException(offset);
232         }
233         return _data[offset];
234     }
235
236     /**
237      * Returns the value at the specified offset without doing any
238      * bounds checking.
239      *
240      * @param offset an <code>int</code> value
241      * @return an <code>float</code> value
242      */

243     public float getQuick(int offset) {
244         return _data[offset];
245     }
246
247     /**
248      * Sets the value at the specified offset.
249      *
250      * @param offset an <code>int</code> value
251      * @param val an <code>float</code> value
252      */

253     public void set(int offset, float val) {
254         if (offset >= _pos) {
255             throw new ArrayIndexOutOfBoundsException(offset);
256         }
257         _data[offset] = val;
258     }
259
260     /**
261      * Sets the value at the specified offset and returns the
262      * previously stored value.
263      *
264      * @param offset an <code>int</code> value
265      * @param val an <code>float</code> value
266      * @return the value previously stored at offset.
267      */

268     public float getSet(int offset, float val) {
269         if (offset >= _pos) {
270             throw new ArrayIndexOutOfBoundsException(offset);
271         }
272         float old = _data[offset];
273         _data[offset] = val;
274         return old;
275     }
276
277     /**
278      * Replace the values in the list starting at <tt>offset</tt> with
279      * the contents of the <tt>values</tt> array.
280      *
281      * @param offset the first offset to replace
282      * @param values the source of the new values
283      */

284     public void set(int offset, float[] values) {
285         set(offset, values, 0, values.length);
286     }
287
288     /**
289      * Replace the values in the list starting at <tt>offset</tt> with
290      * <tt>length</tt> values from the <tt>values</tt> array, starting
291      * at valOffset.
292      *
293      * @param offset the first offset to replace
294      * @param values the source of the new values
295      * @param valOffset the first value to copy from the values array
296      * @param length the number of values to copy
297      */

298     public void set(int offset, float[] values, int valOffset, int length) {
299         if (offset < 0 || offset + length >= _pos) {
300             throw new ArrayIndexOutOfBoundsException(offset);
301         }
302         System.arraycopy(values, valOffset, _data, offset, length);
303     }
304
305     /**
306      * Sets the value at the specified offset without doing any bounds
307      * checking.
308      *
309      * @param offset an <code>int</code> value
310      * @param val an <code>float</code> value
311      */

312     public void setQuick(int offset, float val) {
313         _data[offset] = val;
314     }
315
316     /**
317      * Flushes the internal state of the list, resetting the capacity
318      * to the default.
319      */

320     public void clear() {
321         clear(DEFAULT_CAPACITY);
322     }
323
324     /**
325      * Flushes the internal state of the list, setting the capacity of
326      * the empty list to <tt>capacity</tt>.
327      *
328      * @param capacity an <code>int</code> value
329      */

330     public void clear(int capacity) {
331         _data = new float[capacity];
332         _pos = 0;
333     }
334
335     /**
336      * Sets the size of the list to 0, but does not change its
337      * capacity. This method can be used as an alternative to the
338      * {@link #clear clear} method if you want to recyle a list without
339      * allocating new backing arrays.
340      *
341      * @see #clear
342      */

343     public void reset() {
344         _pos = 0;
345         fill((float)0);
346     }
347
348     /**
349      * Sets the size of the list to 0, but does not change its
350      * capacity. This method can be used as an alternative to the
351      * {@link #clear clear} method if you want to recyle a list
352      * without allocating new backing arrays. This method differs
353      * from {@link #reset reset} in that it does not clear the old
354      * values in the backing array. Thus, it is possible for {@link
355      * #getQuick getQuick} to return stale data if this method is used
356      * and the caller is careless about bounds checking.
357      *
358      * @see #reset
359      * @see #clear
360      * @see #getQuick
361      */

362     public void resetQuick() {
363         _pos = 0;
364     }
365
366     /**
367      * Removes the value at <tt>offset</tt> from the list.
368      *
369      * @param offset an <code>int</code> value
370      * @return the value previously stored at offset.
371      */

372     public float remove(int offset) {
373         float old = get(offset);
374         remove(offset, 1);
375         return old;
376     }
377
378     /**
379      * Removes <tt>length</tt> values from the list, starting at
380      * <tt>offset</tt>
381      *
382      * @param offset an <code>int</code> value
383      * @param length an <code>int</code> value
384      */

385     public void remove(int offset, int length) {
386         if (offset < 0 || offset >= _pos) {
387             throw new ArrayIndexOutOfBoundsException(offset);
388         }
389
390         if (offset == 0) {
391             // data at the front
392
System.arraycopy(_data, length, _data, 0, _pos - length);
393         } else if (_pos - length == offset) {
394             // no copy to make, decrementing pos "deletes" values at
395
// the end
396
} else {
397             // data in the middle
398
System.arraycopy(_data, offset + length,
399                              _data, offset, _pos - (offset + length));
400         }
401         _pos -= length;
402         // no need to clear old values beyond _pos, because this is a
403
// primitive collection and 0 takes as much room as any other
404
// value
405
}
406
407     /**
408      * Transform each value in the list using the specified function.
409      *
410      * @param function a <code>TFloatFunction</code> value
411      */

412     public void transformValues(TFloatFunction function) {
413         for (int i = _pos; i-- > 0;) {
414             _data[i] = function.execute(_data[i]);
415         }
416     }
417
418     /**
419      * Reverse the order of the elements in the list.
420      */

421     public void reverse() {
422         reverse(0, _pos);
423     }
424
425     /**
426      * Reverse the order of the elements in the range of the list.
427      *
428      * @param from the inclusive index at which to start reversing
429      * @param to the exclusive index at which to stop reversing
430      */

431     public void reverse(int from, int to) {
432         if (from == to) {
433             return; // nothing to do
434
}
435         if (from > to) {
436             throw new IllegalArgumentException("from cannot be greater than to");
437         }
438         for (int i = from, j = to - 1; i < j; i++, j--) {
439             swap(i, j);
440         }
441     }
442
443     /**
444      * Shuffle the elements of the list using the specified random
445      * number generator.
446      *
447      * @param rand a <code>Random</code> value
448      */

449     public void shuffle(Random rand) {
450         for (int i = _pos; i-- > 1;) {
451             swap(i, rand.nextInt(i));
452         }
453     }
454
455     /**
456      * Swap the values at offsets <tt>i</tt> and <tt>j</tt>.
457      *
458      * @param i an offset into the data array
459      * @param j an offset into the data array
460      */

461     private final void swap(int i, int j) {
462         float tmp = _data[i];
463         _data[i] = _data[j];
464         _data[j] = tmp;
465     }
466
467     // copying
468

469     /**
470      * Returns a clone of this list. Since this is a primitive
471      * collection, this will be a deep clone.
472      *
473      * @return a deep clone of the list.
474      */

475     public Object clone() {
476         TFloatArrayList list = null;
477         try {
478             list = (TFloatArrayList) super.clone();
479             list._data = toNativeArray();
480         } catch (CloneNotSupportedException e) {
481             // it's supported
482
} // end of try-catch
483
return list;
484     }
485
486     /**
487      * Copies the contents of the list into a native array.
488      *
489      * @return an <code>float[]</code> value
490      */

491     public float[] toNativeArray() {
492         return toNativeArray(0, _pos);
493     }
494
495     /**
496      * Copies a slice of the list into a native array.
497      *
498      * @param offset the offset at which to start copying
499      * @param len the number of values to copy.
500      * @return an <code>float[]</code> value
501      */

502     public float[] toNativeArray(int offset, int len) {
503         float[] rv = new float[len];
504         toNativeArray(rv, offset, len);
505         return rv;
506     }
507
508     /**
509      * Copies a slice of the list into a native array.
510      *
511      * @param dest the array to copy into.
512      * @param offset the offset of the first value to copy
513      * @param len the number of values to copy.
514      */

515     public void toNativeArray(float[] dest, int offset, int len) {
516         if (len == 0) {
517             return; // nothing to copy
518
}
519         if (offset < 0 || offset >= _pos) {
520             throw new ArrayIndexOutOfBoundsException(offset);
521         }
522         System.arraycopy(_data, 0, dest, offset, len);
523     }
524
525     // comparing
526

527     /**
528      * Compares this list to another list, value by value.
529      *
530      * @param other the object to compare against
531      * @return true if other is a TFloatArrayList and has exactly the
532      * same values.
533      */

534     public boolean equals(Object other) {
535         if (other == this) {
536             return true;
537         } else if (other instanceof TFloatArrayList) {
538             TFloatArrayList that = (TFloatArrayList)other;
539             if (that.size() != this.size()) {
540                 return false;
541             } else {
542                 for (int i = _pos; i-- > 0;) {
543                     if (this._data[i] != that._data[i]) {
544                         return false;
545                     }
546                 }
547                 return true;
548             }
549         } else {
550             return false;
551         }
552     }
553
554     public int hashCode() {
555         int h = 0;
556         for (int i = _pos; i-- > 0;) {
557             h += HashFunctions.hash(_data[i]);
558         }
559         return h;
560     }
561
562     // procedures
563

564     /**
565      * Applies the procedure to each value in the list in ascending
566      * (front to back) order.
567      *
568      * @param procedure a <code>TFloatProcedure</code> value
569      * @return true if the procedure did not terminate prematurely.
570      */

571     public boolean forEach(TFloatProcedure procedure) {
572         for (int i = 0; i < _pos; i++) {
573             if (! procedure.execute(_data[i])) {
574                 return false;
575             }
576         }
577         return true;
578     }
579
580     /**
581      * Applies the procedure to each value in the list in descending
582      * (back to front) order.
583      *
584      * @param procedure a <code>TFloatProcedure</code> value
585      * @return true if the procedure did not terminate prematurely.
586      */

587     public boolean forEachDescending(TFloatProcedure procedure) {
588         for (int i = _pos; i-- > 0;) {
589             if (! procedure.execute(_data[i])) {
590                 return false;
591             }
592         }
593         return true;
594     }
595
596     // sorting
597

598     /**
599      * Sort the values in the list (ascending) using the Sun quicksort
600      * implementation.
601      *
602      * @see java.util.Arrays#sort
603      */

604     public void sort() {
605         Arrays.sort(_data, 0, _pos);
606     }
607
608     /**
609      * Sort a slice of the list (ascending) using the Sun quicksort
610      * implementation.
611      *
612      * @param fromIndex the index at which to start sorting (inclusive)
613      * @param toIndex the index at which to stop sorting (exclusive)
614      * @see java.util.Arrays#sort
615      */

616     public void sort(int fromIndex, int toIndex) {
617         Arrays.sort(_data, fromIndex, toIndex);
618     }
619
620     // filling
621

622     /**
623      * Fills every slot in the list with the specified value.
624      *
625      * @param val the value to use when filling
626      */

627     public void fill(float val) {
628         Arrays.fill(_data, 0, _pos, val);
629     }
630
631     /**
632      * Fills a range in the list with the specified value.
633      *
634      * @param fromIndex the offset at which to start filling (inclusive)
635      * @param toIndex the offset at which to stop filling (exclusive)
636      * @param val the value to use when filling
637      */

638     public void fill(int fromIndex, int toIndex, float val) {
639         if (toIndex > _pos) {
640           ensureCapacity(toIndex);
641           _pos = toIndex;
642         }
643         Arrays.fill(_data, fromIndex, toIndex, val);
644     }
645
646     // searching
647

648     /**
649      * Performs a binary search for <tt>value</tt> in the entire list.
650      * Note that you <b>must</b> @{link #sort sort} the list before
651      * doing a search.
652      *
653      * @param value the value to search for
654      * @return the absolute offset in the list of the value, or its
655      * negative insertion point into the sorted list.
656      */

657     public int binarySearch(float value) {
658         return binarySearch(value, 0, _pos);
659     }
660
661     /**
662      * Performs a binary search for <tt>value</tt> in the specified
663      * range. Note that you <b>must</b> @{link #sort sort} the list
664      * or the range before doing a search.
665      *
666      * @param value the value to search for
667      * @param fromIndex the lower boundary of the range (inclusive)
668      * @param toIndex the upper boundary of the range (exclusive)
669      * @return the absolute offset in the list of the value, or its
670      * negative insertion point into the sorted list.
671      */

672     public int binarySearch(float value, int fromIndex, int toIndex) {
673         if (fromIndex < 0) {
674             throw new ArrayIndexOutOfBoundsException(fromIndex);
675         }
676         if (toIndex > _pos) {
677             throw new ArrayIndexOutOfBoundsException(toIndex);
678         }
679
680         int low = fromIndex;
681         int high = toIndex - 1;
682
683         while (low <= high) {
684             int mid = (low + high) >> 1;
685             float midVal = _data[mid];
686
687             if (midVal < value) {
688                 low = mid + 1;
689             } else if (midVal > value) {
690                 high = mid - 1;
691             } else {
692                 return mid; // value found
693
}
694         }
695         return -(low + 1); // value not found.
696
}
697
698     /**
699      * Searches the list front to back for the index of
700      * <tt>value</tt>.
701      *
702      * @param value an <code>float</code> value
703      * @return the first offset of the value, or -1 if it is not in
704      * the list.
705      * @see #binarySearch for faster searches on sorted lists
706      */

707     public int indexOf(float value) {
708         return indexOf(0, value);
709     }
710
711     /**
712      * Searches the list front to back for the index of
713      * <tt>value</tt>, starting at <tt>offset</tt>.
714      *
715      * @param offset the offset at which to start the linear search
716      * (inclusive)
717      * @param value an <code>float</code> value
718      * @return the first offset of the value, or -1 if it is not in
719      * the list.
720      * @see #binarySearch for faster searches on sorted lists
721      */

722     public int indexOf(int offset, float value) {
723         for (int i = offset; i < _pos; i++) {
724             if (_data[i] == value) {
725                 return i;
726             }
727         }
728         return -1;
729     }
730
731     /**
732      * Searches the list back to front for the last index of
733      * <tt>value</tt>.
734      *
735      * @param value an <code>float</code> value
736      * @return the last offset of the value, or -1 if it is not in
737      * the list.
738      * @see #binarySearch for faster searches on sorted lists
739      */

740     public int lastIndexOf(float value) {
741         return lastIndexOf(_pos, value);
742     }
743
744     /**
745      * Searches the list back to front for the last index of
746      * <tt>value</tt>, starting at <tt>offset</tt>.
747      *
748      * @param offset the offset at which to start the linear search
749      * (exclusive)
750      * @param value an <code>float</code> value
751      * @return the last offset of the value, or -1 if it is not in
752      * the list.
753      * @see #binarySearch for faster searches on sorted lists
754      */

755     public int lastIndexOf(int offset, float value) {
756         for (int i = offset; i-- > 0;) {
757             if (_data[i] == value) {
758                 return i;
759             }
760         }
761         return -1;
762     }
763
764     /**
765      * Searches the list for <tt>value</tt>
766      *
767      * @param value an <code>float</code> value
768      * @return true if value is in the list.
769      */

770     public boolean contains(float value) {
771         return lastIndexOf(value) >= 0;
772     }
773
774     /**
775      * Searches the list for values satisfying <tt>condition</tt> in
776      * the manner of the *nix <tt>grep</tt> utility.
777      *
778      * @param condition a condition to apply to each element in the list
779      * @return a list of values which match the condition.
780      */

781     public TFloatArrayList grep(TFloatProcedure condition) {
782         TFloatArrayList list = new TFloatArrayList();
783         for (int i = 0; i < _pos; i++) {
784             if (condition.execute(_data[i])) {
785                 list.add(_data[i]);
786             }
787         }
788         return list;
789     }
790
791     /**
792      * Searches the list for values which do <b>not</b> satisfy
793      * <tt>condition</tt>. This is akin to *nix <code>grep -v</code>.
794      *
795      * @param condition a condition to apply to each element in the list
796      * @return a list of values which do not match the condition.
797      */

798     public TFloatArrayList inverseGrep(TFloatProcedure condition) {
799         TFloatArrayList list = new TFloatArrayList();
800         for (int i = 0; i < _pos; i++) {
801             if (! condition.execute(_data[i])) {
802                 list.add(_data[i]);
803             }
804         }
805         return list;
806     }
807
808     /**
809      * Finds the maximum value in the list.
810      *
811      * @return the largest value in the list.
812      * @exception IllegalStateException if the list is empty
813      */

814     public float max() {
815         if (size() == 0) {
816             throw new IllegalStateException("cannot find maximum of an empty list");
817         }
818         float max = _data[_pos - 1];
819         for (int i = _pos - 1; i-- > 0;) {
820             if (_data[i] > max) {
821                 max = _data[i];
822             }
823         }
824         return max;
825     }
826
827     /**
828      * Finds the minimum value in the list.
829      *
830      * @return the smallest value in the list.
831      * @exception IllegalStateException if the list is empty
832      */

833     public float min() {
834         if (size() == 0) {
835             throw new IllegalStateException("cannot find minimum of an empty list");
836         }
837         float min = _data[_pos - 1];
838         for (int i = _pos - 1; i-- > 0;) {
839             if (_data[i] < min) {
840                 min = _data[i];
841             }
842         }
843         return min;
844     }
845
846     // stringification
847

848     /**
849      * Returns a String representation of the list, front to back.
850      *
851      * @return a <code>String</code> value
852      */

853     public String toString() {
854         StringBuffer buf = new StringBuffer("{");
855         for (int i = 0, end = _pos - 1; i < end; i++) {
856             buf.append(_data[i]);
857             buf.append(", ");
858         }
859         if (size() > 0) {
860             buf.append(_data[_pos - 1]);
861         }
862         buf.append("}");
863         return buf.toString();
864     }
865 } // TFloatArrayList
866
Popular Tags