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 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 09:14:21 +0100 (Wed, 29 Nov 2006) $
039     * 
040     * @author Rodney Waldhoff 
041     */
042    public 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    }