001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *     http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections.primitives;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.ObjectOutputStream;
022import java.io.Serializable;
023
024/**
025 * An {@link IntList} backed by an array of unsigned
026 * <code>int</code> values.
027 * This list stores <code>int</code> values
028 * in the range [{@link #MIN_VALUE <code>0</code>},
029 * {@link #MAX_VALUE <code>65535</code>}] in 16-bits 
030 * per element.  Attempts to use elements outside this 
031 * range may cause an 
032 * {@link IllegalArgumentException IllegalArgumentException} 
033 * to be thrown.
034 * <p />
035 * This implementation supports all optional methods.
036 * 
037 * @since Commons Primitives 1.0
038 * @version $Revision: 480460 $ $Date: 2006-11-29 03:14:21 -0500 (Wed, 29 Nov 2006) $
039 * 
040 * @author Rodney Waldhoff 
041 */
042public class ArrayUnsignedIntList extends RandomAccessLongList implements LongList, Serializable {
043
044    // constructors
045    //-------------------------------------------------------------------------
046
047    /** 
048     * Construct an empty list with the default
049     * initial capacity.
050     */
051    public ArrayUnsignedIntList() {
052        this(8);
053    }    
054
055    /**
056     * Construct an empty list with the given
057     * initial capacity.
058     * @throws IllegalArgumentException when <i>initialCapacity</i> is negative
059     */
060    public ArrayUnsignedIntList(int initialCapacity) {
061        if(initialCapacity < 0) {
062            throw new IllegalArgumentException("capacity " + initialCapacity);
063        }
064        _data = new int[initialCapacity];
065        _size = 0;
066    }    
067
068    /** 
069     * Constructs a list containing the elements of the given collection, 
070     * in the order they are returned by that collection's iterator.
071     * 
072     * @see AbstractLongCollection#addAll(LongCollection)
073     * @param that the non-<code>null</code> collection of <code>int</code>s 
074     *        to add
075     * @throws NullPointerException if <i>that</i> is <code>null</code>
076     */
077    public ArrayUnsignedIntList(LongCollection that) { 
078        this(that.size());
079        addAll(that);
080    }    
081
082    /**
083     * Constructs a list by copying the specified array.
084     * 
085     * @param array  the array to initialize the collection with
086     * @throws NullPointerException if the array is <code>null</code>
087     */
088    public ArrayUnsignedIntList(long[] array) { 
089        this(array.length);
090        for(int i=0;i<array.length;i++) {
091            _data[i] = fromLong(array[i]);
092        }
093        _size = array.length;
094    }
095    
096    // IntList methods
097    //-------------------------------------------------------------------------
098
099    /** 
100     * Returns the element at the specified position within 
101     * me. 
102     * By construction, the returned value will be 
103     * between {@link #MIN_VALUE} and {@link #MAX_VALUE}, inclusive.
104     * 
105     * @param index the index of the element to return
106     * @return the value of the element at the specified position
107     * @throws IndexOutOfBoundsException if the specified index is out of range
108     */
109    public long get(int index) {
110        checkRange(index);
111        return toLong(_data[index]);
112    }
113    
114    public int size() {
115        return _size;
116    }
117    
118    /** 
119     * Removes the element at the specified position in 
120     * (optional operation).  Any subsequent elements 
121     * are shifted to the left, subtracting one from their 
122     * indices.  Returns the element that was removed.
123     * By construction, the returned value will be 
124     * between {@link #MIN_VALUE} and {@link #MAX_VALUE}, inclusive.
125     * 
126     * @param index the index of the element to remove
127     * @return the value of the element that was removed
128     * 
129     * @throws UnsupportedOperationException when this operation is not 
130     *         supported
131     * @throws IndexOutOfBoundsException if the specified index is out of range
132     */
133    public long removeElementAt(int index) {
134        checkRange(index);
135        incrModCount();
136        long oldval = toLong(_data[index]);
137        int numtomove = _size - index - 1;
138        if(numtomove > 0) {
139            System.arraycopy(_data,index+1,_data,index,numtomove);
140        }
141        _size--;
142        return oldval;
143    }
144    
145    /** 
146     * Replaces the element at the specified 
147     * position in me with the specified element
148     * (optional operation). 
149     * Throws {@link IllegalArgumentException} if <i>element</i>
150     * is less than {@link #MIN_VALUE} or greater than {@link #MAX_VALUE}.
151     * 
152     * @param index the index of the element to change
153     * @param element the value to be stored at the specified position
154     * @return the value previously stored at the specified position
155     * 
156     * @throws UnsupportedOperationException when this operation is not 
157     *         supported
158     * @throws IndexOutOfBoundsException if the specified index is out of range
159     */
160    public long set(int index, long element) {
161        assertValidUnsignedInt(element);
162        checkRange(index);
163        incrModCount();
164        long oldval = toLong(_data[index]);
165        _data[index] = fromLong(element);
166        return oldval;
167    }
168        
169    /** 
170     * Inserts the specified element at the specified position 
171     * (optional operation). Shifts the element currently 
172     * at that position (if any) and any subsequent elements to the 
173     * right, increasing their indices.
174     * Throws {@link IllegalArgumentException} if <i>element</i>
175     * is less than {@link #MIN_VALUE} or greater than {@link #MAX_VALUE}.
176     * 
177     * @param index the index at which to insert the element
178     * @param element the value to insert
179     * 
180     * @throws UnsupportedOperationException when this operation is not 
181     *         supported
182     * @throws IllegalArgumentException if some aspect of the specified element 
183     *         prevents it from being added to me
184     * @throws IndexOutOfBoundsException if the specified index is out of range
185     */
186    public void add(int index, long element) {
187        assertValidUnsignedInt(element);
188        checkRangeIncludingEndpoint(index);
189        incrModCount();
190        ensureCapacity(_size+1);
191        int numtomove = _size-index;
192        System.arraycopy(_data,index,_data,index+1,numtomove);
193        _data[index] = fromLong(element);
194        _size++;
195    }
196
197    public void clear() {
198        incrModCount();
199        _size = 0;
200    }
201
202    // capacity methods
203    //-------------------------------------------------------------------------
204
205    /** 
206     * Increases my capacity, if necessary, to ensure that I can hold at 
207     * least the number of elements specified by the minimum capacity 
208     * argument without growing.
209     */
210    public void ensureCapacity(int mincap) {
211        incrModCount();
212        if(mincap > _data.length) {
213            int newcap = (_data.length * 3)/2 + 1;
214            int[] olddata = _data;
215            _data = new int[newcap < mincap ? mincap : newcap];
216            System.arraycopy(olddata,0,_data,0,_size);
217        }
218    }
219
220    /** 
221     * Reduce my capacity, if necessary, to match my
222     * current {@link #size size}.
223     */
224    public void trimToSize() {
225        incrModCount();
226        if(_size < _data.length) {
227            int[] olddata = _data;
228            _data = new int[_size];
229            System.arraycopy(olddata,0,_data,0,_size);
230        }
231    }
232
233    // private methods
234    //-------------------------------------------------------------------------
235
236    private final long toLong(int value) { 
237        return value & MAX_VALUE;
238    }
239
240    private final int fromLong(long value) {
241        return (int)(value&MAX_VALUE);
242    }
243
244    private final void assertValidUnsignedInt(long value) throws IllegalArgumentException {
245        if(value > MAX_VALUE) {
246            throw new IllegalArgumentException(value + " > " + MAX_VALUE);
247        }
248        if(value < MIN_VALUE) {
249            throw new IllegalArgumentException(value + " < " + MIN_VALUE);
250        }
251    }
252
253    private void writeObject(ObjectOutputStream out) throws IOException{
254        out.defaultWriteObject();
255        out.writeInt(_data.length);
256        for(int i=0;i<_size;i++) {
257            out.writeInt(_data[i]);
258        }
259    }
260
261    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
262        in.defaultReadObject();
263        _data = new int[in.readInt()];
264        for(int i=0;i<_size;i++) {
265            _data[i] = in.readInt();
266        }
267    }
268    
269    private final void checkRange(int index) {
270        if(index < 0 || index >= _size) {
271            throw new IndexOutOfBoundsException("Should be at least 0 and less than " + _size + ", found " + index);
272        }
273    }
274
275    private final void checkRangeIncludingEndpoint(int index) {
276        if(index < 0 || index > _size) {
277            throw new IndexOutOfBoundsException("Should be at least 0 and at most " + _size + ", found " + index);
278        }
279    }
280
281    // attributes
282    //-------------------------------------------------------------------------
283    
284    /**
285     *  The maximum possible unsigned 32-bit value.
286     */
287    public static final long MAX_VALUE = 0xFFFFFFFFL;
288
289    /**
290     *  The minimum possible unsigned 32-bit value.
291     */
292    public static final long MIN_VALUE = 0L;
293
294    private transient int[] _data = null;
295    private int _size = 0;
296
297}