001: /*
002: * $Header: /home/cvs/jakarta-commons/primitives/src/java/org/apache/commons/collections/primitives/ArrayUnsignedIntList.java,v 1.3 2003/10/16 20:49:36 scolebourne Exp $
003: * ====================================================================
004: * The Apache Software License, Version 1.1
005: *
006: * Copyright (c) 2002-2003 The Apache Software Foundation. All rights
007: * reserved.
008: *
009: * Redistribution and use in source and binary forms, with or without
010: * modification, are permitted provided that the following conditions
011: * are met:
012: *
013: * 1. Redistributions of source code must retain the above copyright
014: * notice, this list of conditions and the following disclaimer.
015: *
016: * 2. Redistributions in binary form must reproduce the above copyright
017: * notice, this list of conditions and the following disclaimer in
018: * the documentation and/or other materials provided with the
019: * distribution.
020: *
021: * 3. The end-user documentation included with the redistribution, if
022: * any, must include the following acknowledgement:
023: * "This product includes software developed by the
024: * Apache Software Foundation (http://www.apache.org/)."
025: * Alternately, this acknowledgement may appear in the software itself,
026: * if and wherever such third-party acknowledgements normally appear.
027: *
028: * 4. The names "The Jakarta Project", "Commons", and "Apache Software
029: * Foundation" must not be used to endorse or promote products derived
030: * from this software without prior written permission. For written
031: * permission, please contact apache@apache.org.
032: *
033: * 5. Products derived from this software may not be called "Apache"
034: * nor may "Apache" appear in their names without prior written
035: * permission of the Apache Software Foundation.
036: *
037: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
038: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
039: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
040: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
041: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
042: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
043: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
044: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
045: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
046: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
047: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
048: * SUCH DAMAGE.
049: * ====================================================================
050: *
051: * This software consists of voluntary contributions made by many
052: * individuals on behalf of the Apache Software Foundation. For more
053: * information on the Apache Software Foundation, please see
054: * <http://www.apache.org/>.
055: *
056: */
057:
058: package org.apache.commons.collections.primitives;
059:
060: import java.io.IOException;
061: import java.io.ObjectInputStream;
062: import java.io.ObjectOutputStream;
063: import java.io.Serializable;
064:
065: /**
066: * An {@link IntList} backed by an array of unsigned
067: * <code>int</code> values.
068: * This list stores <code>int</code> values
069: * in the range [{@link #MIN_VALUE <code>0</code>},
070: * {@link #MAX_VALUE <code>65535</code>}] in 16-bits
071: * per element. Attempts to use elements outside this
072: * range may cause an
073: * {@link IllegalArgumentException IllegalArgumentException}
074: * to be thrown.
075: * <p />
076: * This implementation supports all optional methods.
077: *
078: * @since Commons Primitives 1.0
079: * @version $Revision: 1.3 $ $Date: 2003/10/16 20:49:36 $
080: *
081: * @author Rodney Waldhoff
082: */
083: public class ArrayUnsignedIntList extends RandomAccessLongList
084: implements LongList, Serializable {
085:
086: // constructors
087: //-------------------------------------------------------------------------
088:
089: /**
090: * Construct an empty list with the default
091: * initial capacity.
092: */
093: public ArrayUnsignedIntList() {
094: this (8);
095: }
096:
097: /**
098: * Construct an empty list with the given
099: * initial capacity.
100: * @throws IllegalArgumentException when <i>initialCapacity</i> is negative
101: */
102: public ArrayUnsignedIntList(int initialCapacity) {
103: if (initialCapacity < 0) {
104: throw new IllegalArgumentException("capacity "
105: + initialCapacity);
106: }
107: _data = new int[initialCapacity];
108: _size = 0;
109: }
110:
111: /**
112: * Constructs a list containing the elements of the given collection,
113: * in the order they are returned by that collection's iterator.
114: *
115: * @see AbstractLongCollection#addAll(LongCollection)
116: * @param that the non-<code>null</code> collection of <code>int</code>s
117: * to add
118: * @throws NullPointerException if <i>that</i> is <code>null</code>
119: */
120: public ArrayUnsignedIntList(LongCollection that) {
121: this (that.size());
122: addAll(that);
123: }
124:
125: // IntList methods
126: //-------------------------------------------------------------------------
127:
128: /**
129: * Returns the element at the specified position within
130: * me.
131: * By construction, the returned value will be
132: * between {@link #MIN_VALUE} and {@link #MAX_VALUE}, inclusive.
133: *
134: * @param index the index of the element to return
135: * @return the value of the element at the specified position
136: * @throws IndexOutOfBoundsException if the specified index is out of range
137: */
138: public long get(int index) {
139: checkRange(index);
140: return toLong(_data[index]);
141: }
142:
143: public int size() {
144: return _size;
145: }
146:
147: /**
148: * Removes the element at the specified position in
149: * (optional operation). Any subsequent elements
150: * are shifted to the left, subtracting one from their
151: * indices. Returns the element that was removed.
152: * By construction, the returned value will be
153: * between {@link #MIN_VALUE} and {@link #MAX_VALUE}, inclusive.
154: *
155: * @param index the index of the element to remove
156: * @return the value of the element that was removed
157: *
158: * @throws UnsupportedOperationException when this operation is not
159: * supported
160: * @throws IndexOutOfBoundsException if the specified index is out of range
161: */
162: public long removeElementAt(int index) {
163: checkRange(index);
164: incrModCount();
165: long oldval = toLong(_data[index]);
166: int numtomove = _size - index - 1;
167: if (numtomove > 0) {
168: System.arraycopy(_data, index + 1, _data, index, numtomove);
169: }
170: _size--;
171: return oldval;
172: }
173:
174: /**
175: * Replaces the element at the specified
176: * position in me with the specified element
177: * (optional operation).
178: * Throws {@link IllegalArgumentException} if <i>element</i>
179: * is less than {@link #MIN_VALUE} or greater than {@link #MAX_VALUE}.
180: *
181: * @param index the index of the element to change
182: * @param element the value to be stored at the specified position
183: * @return the value previously stored at the specified position
184: *
185: * @throws UnsupportedOperationException when this operation is not
186: * supported
187: * @throws IndexOutOfBoundsException if the specified index is out of range
188: */
189: public long set(int index, long element) {
190: assertValidUnsignedInt(element);
191: checkRange(index);
192: incrModCount();
193: long oldval = toLong(_data[index]);
194: _data[index] = fromLong(element);
195: return oldval;
196: }
197:
198: /**
199: * Inserts the specified element at the specified position
200: * (optional operation). Shifts the element currently
201: * at that position (if any) and any subsequent elements to the
202: * right, increasing their indices.
203: * Throws {@link IllegalArgumentException} if <i>element</i>
204: * is less than {@link #MIN_VALUE} or greater than {@link #MAX_VALUE}.
205: *
206: * @param index the index at which to insert the element
207: * @param element the value to insert
208: *
209: * @throws UnsupportedOperationException when this operation is not
210: * supported
211: * @throws IllegalArgumentException if some aspect of the specified element
212: * prevents it from being added to me
213: * @throws IndexOutOfBoundsException if the specified index is out of range
214: */
215: public void add(int index, long element) {
216: assertValidUnsignedInt(element);
217: checkRangeIncludingEndpoint(index);
218: incrModCount();
219: ensureCapacity(_size + 1);
220: int numtomove = _size - index;
221: System.arraycopy(_data, index, _data, index + 1, numtomove);
222: _data[index] = fromLong(element);
223: _size++;
224: }
225:
226: // capacity methods
227: //-------------------------------------------------------------------------
228:
229: /**
230: * Increases my capacity, if necessary, to ensure that I can hold at
231: * least the number of elements specified by the minimum capacity
232: * argument without growing.
233: */
234: public void ensureCapacity(int mincap) {
235: incrModCount();
236: if (mincap > _data.length) {
237: int newcap = (_data.length * 3) / 2 + 1;
238: int[] olddata = _data;
239: _data = new int[newcap < mincap ? mincap : newcap];
240: System.arraycopy(olddata, 0, _data, 0, _size);
241: }
242: }
243:
244: /**
245: * Reduce my capacity, if necessary, to match my
246: * current {@link #size size}.
247: */
248: public void trimToSize() {
249: incrModCount();
250: if (_size < _data.length) {
251: int[] olddata = _data;
252: _data = new int[_size];
253: System.arraycopy(olddata, 0, _data, 0, _size);
254: }
255: }
256:
257: // private methods
258: //-------------------------------------------------------------------------
259:
260: private final long toLong(int value) {
261: return ((long) value) & MAX_VALUE;
262: }
263:
264: private final int fromLong(long value) {
265: return (int) (value & MAX_VALUE);
266: }
267:
268: private final void assertValidUnsignedInt(long value)
269: throws IllegalArgumentException {
270: if (value > MAX_VALUE) {
271: throw new IllegalArgumentException(value + " > "
272: + MAX_VALUE);
273: }
274: if (value < MIN_VALUE) {
275: throw new IllegalArgumentException(value + " < "
276: + MIN_VALUE);
277: }
278: }
279:
280: private void writeObject(ObjectOutputStream out) throws IOException {
281: out.defaultWriteObject();
282: out.writeInt(_data.length);
283: for (int i = 0; i < _size; i++) {
284: out.writeInt(_data[i]);
285: }
286: }
287:
288: private void readObject(ObjectInputStream in) throws IOException,
289: ClassNotFoundException {
290: in.defaultReadObject();
291: _data = new int[in.readInt()];
292: for (int i = 0; i < _size; i++) {
293: _data[i] = in.readInt();
294: }
295: }
296:
297: private final void checkRange(int index) {
298: if (index < 0 || index >= _size) {
299: throw new IndexOutOfBoundsException(
300: "Should be at least 0 and less than " + _size
301: + ", found " + index);
302: }
303: }
304:
305: private final void checkRangeIncludingEndpoint(int index) {
306: if (index < 0 || index > _size) {
307: throw new IndexOutOfBoundsException(
308: "Should be at least 0 and at most " + _size
309: + ", found " + index);
310: }
311: }
312:
313: // attributes
314: //-------------------------------------------------------------------------
315:
316: /**
317: * The maximum possible unsigned 32-bit value.
318: */
319: public static final long MAX_VALUE = 0xFFFFFFFFL;
320:
321: /**
322: * The minimum possible unsigned 32-bit value.
323: */
324: public static final long MIN_VALUE = 0L;
325:
326: private transient int[] _data = null;
327: private int _size = 0;
328:
329: }
|