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 <code>int</code>s.
026 * This implementation supports all optional methods.
027 * 
028 * @since Commons Primitives 1.0
029 * @version $Revision: 480460 $ $Date: 2006-11-29 03:14:21 -0500 (Wed, 29 Nov 2006) $
030 * 
031 * @author Rodney Waldhoff
032 * @author Robert Fischer
033 */
034public class ArrayIntList extends RandomAccessIntList implements IntList, Serializable {
035
036    // constructors
037    //-------------------------------------------------------------------------
038
039    /** 
040     * Construct an empty list with the default
041     * initial capacity.
042     */
043    public ArrayIntList() {
044        this(8);
045    }    
046
047    /**
048     * Construct an empty list with the given
049     * initial capacity.
050     * @throws IllegalArgumentException when <i>initialCapacity</i> is negative
051     */
052    public ArrayIntList(int initialCapacity) {
053        if(initialCapacity < 0) {
054            throw new IllegalArgumentException("capacity " + initialCapacity);
055        }
056        _data = new int[initialCapacity];
057        _size = 0;
058    }    
059
060    /** 
061     * Constructs a list containing the elements of the given collection, 
062     * in the order they are returned by that collection's iterator.
063     * 
064     * @see ArrayIntList#addAll(org.apache.commons.collections.primitives.IntCollection)
065     * @param that the non-<code>null</code> collection of <code>int</code>s 
066     *        to add
067     * @throws NullPointerException if <i>that</i> is <code>null</code>
068     */
069    public ArrayIntList(IntCollection that) { 
070        this(that.size());
071        addAll(that);
072    }    
073
074    /**
075     * Constructs a list by copying the specified array.
076     * 
077     * @param array  the array to initialize the collection with
078     * @throws NullPointerException if the array is <code>null</code>
079     */
080    public ArrayIntList(int[] array) { 
081        this(array.length);
082        System.arraycopy(array, 0, _data, 0, array.length);
083        _size = array.length;
084    }
085
086    // IntList methods
087    //-------------------------------------------------------------------------
088
089    public int get(int index) {
090        checkRange(index);
091        return _data[index];
092    }
093    
094    public int size() {
095        return _size;
096    }
097    
098    /** 
099     * Removes the element at the specified position in 
100     * (optional operation).  Any subsequent elements 
101     * are shifted to the left, subtracting one from their 
102     * indices.  Returns the element that was removed.
103     * 
104     * @param index the index of the element to remove
105     * @return the value of the element that was removed
106     * 
107     * @throws UnsupportedOperationException when this operation is not 
108     *         supported
109     * @throws IndexOutOfBoundsException if the specified index is out of range
110     */
111    public int removeElementAt(int index) {
112        checkRange(index);
113        incrModCount();
114        int oldval = _data[index];
115        int numtomove = _size - index - 1;
116        if(numtomove > 0) {
117            System.arraycopy(_data,index+1,_data,index,numtomove);
118        }
119        _size--;
120        return oldval;
121    }
122    
123    /** 
124     * Replaces the element at the specified 
125     * position in me with the specified element
126     * (optional operation). 
127     * 
128     * @param index the index of the element to change
129     * @param element the value to be stored at the specified position
130     * @return the value previously stored at the specified position
131     * 
132     * @throws UnsupportedOperationException when this operation is not 
133     *         supported
134     * @throws IndexOutOfBoundsException if the specified index is out of range
135     */
136    public int set(int index, int element) {
137        checkRange(index);
138        incrModCount();
139        int oldval = _data[index];
140        _data[index] = element;
141        return oldval;
142    }
143        
144    /** 
145     * Inserts the specified element at the specified position 
146     * (optional operation). Shifts the element currently 
147     * at that position (if any) and any subsequent elements to the 
148     * right, increasing their indices.
149     * 
150     * @param index the index at which to insert the element
151     * @param element the value to insert
152     * 
153     * @throws UnsupportedOperationException when this operation is not 
154     *         supported
155     * @throws IllegalArgumentException if some aspect of the specified element 
156     *         prevents it from being added to me
157     * @throws IndexOutOfBoundsException if the specified index is out of range
158     */
159    public void add(int index, int element) {
160        checkRangeIncludingEndpoint(index);
161        incrModCount();
162        ensureCapacity(_size+1);
163        int numtomove = _size-index;
164        System.arraycopy(_data,index,_data,index+1,numtomove);
165        _data[index] = element;
166        _size++;
167    }
168
169    public void clear() {
170        incrModCount();
171        _size = 0;
172    }
173
174    public boolean addAll(IntCollection collection) {
175                return addAll(size(), collection);
176        }
177
178        public boolean addAll(int index, IntCollection collection) {
179                if (collection.size() == 0) {
180                        return false;
181        }
182                checkRangeIncludingEndpoint(index);
183                incrModCount();
184                ensureCapacity(_size + collection.size());
185                if (index != _size) {
186                        // Need to move some elements
187                        System.arraycopy(_data, index, _data, index + collection.size(), _size - index);
188                }
189                for (IntIterator it = collection.iterator(); it.hasNext();) {
190                        _data[index] = it.next();
191                        index++;
192                }
193                _size += collection.size();
194                return true;
195        }
196
197    // capacity methods
198    //-------------------------------------------------------------------------
199
200    /** 
201     * Increases my capacity, if necessary, to ensure that I can hold at 
202     * least the number of elements specified by the minimum capacity 
203     * argument without growing.
204     */
205    public void ensureCapacity(int mincap) {
206        incrModCount();
207        if(mincap > _data.length) {
208            int newcap = (_data.length * 3)/2 + 1;
209            int[] olddata = _data;
210            _data = new int[newcap < mincap ? mincap : newcap];
211            System.arraycopy(olddata,0,_data,0,_size);
212        }
213    }
214
215    /** 
216     * Reduce my capacity, if necessary, to match my
217     * current {@link #size size}.
218     */
219    public void trimToSize() {
220        incrModCount();
221        if(_size < _data.length) {
222            int[] olddata = _data;
223            _data = new int[_size];
224            System.arraycopy(olddata,0,_data,0,_size);
225        }
226    }
227
228    // private methods
229    //-------------------------------------------------------------------------
230    
231    private void writeObject(ObjectOutputStream out) throws IOException{
232        out.defaultWriteObject();
233        out.writeInt(_data.length);
234        for(int i=0;i<_size;i++) {
235            out.writeInt(_data[i]);
236        }
237    }
238
239    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
240        in.defaultReadObject();
241        _data = new int[in.readInt()];
242        for(int i=0;i<_size;i++) {
243            _data[i] = in.readInt();
244        }
245    }
246    
247    private final void checkRange(int index) {
248        if(index < 0 || index >= _size) {
249            throw new IndexOutOfBoundsException("Should be at least 0 and less than " + _size + ", found " + index);
250        }
251    }
252
253    private final void checkRangeIncludingEndpoint(int index) {
254        if(index < 0 || index > _size) {
255            throw new IndexOutOfBoundsException("Should be at least 0 and at most " + _size + ", found " + index);
256        }
257    }
258
259    // attributes
260    //-------------------------------------------------------------------------
261    
262    private transient int[] _data = null;
263    private int _size = 0;
264
265}