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     */
017    package org.apache.commons.collections.primitives;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.ObjectOutputStream;
022    import 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 09:14:21 +0100 (Wed, 29 Nov 2006) $
030     * 
031     * @author Rodney Waldhoff
032     * @author Robert Fischer
033     */
034    public 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    }