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.util.ConcurrentModificationException;
020import java.util.NoSuchElementException;
021
022/**
023 * Abstract base class for {@link IntList}s backed 
024 * by random access structures like arrays.
025 * <p />
026 * Read-only subclasses must override {@link #get}
027 * and {@link #size}.  Mutable subclasses
028 * should also override {@link #set}.  Variably-sized
029 * subclasses should also override {@link #add(int)} 
030 * and {@link #removeElementAt}.  All other methods
031 * have at least some base implementation derived from 
032 * these.  Subclasses may choose to override these methods
033 * to provide a more efficient implementation.
034 * 
035 * @since Commons Primitives 1.0
036 * @version $Revision: 480460 $ $Date: 2006-11-29 03:14:21 -0500 (Wed, 29 Nov 2006) $
037 * 
038 * @author Rodney Waldhoff 
039 */
040public abstract class RandomAccessIntList extends AbstractIntCollection implements IntList {
041
042    // constructors
043    //-------------------------------------------------------------------------
044
045    /** Constructs an empty list. */
046    protected RandomAccessIntList() { 
047    }    
048
049    // fully abstract methods
050    //-------------------------------------------------------------------------
051    
052    public abstract int get(int index);
053    public abstract int size();
054
055    // unsupported in base
056    //-------------------------------------------------------------------------
057    
058    /** 
059     * Unsupported in this implementation. 
060     * @throws UnsupportedOperationException since this method is not supported
061     */
062    public int removeElementAt(int index) {
063        throw new UnsupportedOperationException();
064    }
065    
066    /** 
067     * Unsupported in this implementation. 
068     * @throws UnsupportedOperationException since this method is not supported
069     */
070    public int set(int index, int element) {
071        throw new UnsupportedOperationException();
072    }
073        
074    /** 
075     * Unsupported in this implementation. 
076     * @throws UnsupportedOperationException since this method is not supported
077     */
078    public void add(int index, int element) {
079        throw new UnsupportedOperationException();
080    }
081
082    //-------------------------------------------------------------------------
083
084    // javadocs here are inherited
085    
086    public boolean add(int element) {
087        add(size(),element);
088        return true;
089    }
090
091    public boolean addAll(int index, IntCollection collection) {
092        boolean modified = false;
093        for(IntIterator iter = collection.iterator(); iter.hasNext(); ) {
094            add(index++,iter.next());
095            modified = true;
096        }
097        return modified;
098    }
099
100    public int indexOf(int element) {
101        int i = 0;
102        for(IntIterator iter = iterator(); iter.hasNext(); ) {
103            if(iter.next() == element) { 
104                return i;
105            } else {
106                i++;
107            }
108        }
109        return -1;
110    }
111
112    public int lastIndexOf(int element) {
113        for(IntListIterator iter = listIterator(size()); iter.hasPrevious(); ) {
114            if(iter.previous() == element) {
115                return iter.nextIndex();
116            }
117        }
118        return -1;
119    }
120
121    public IntIterator iterator() {
122        return listIterator();
123    }
124
125    public IntListIterator listIterator() {
126        return listIterator(0);
127    }
128
129    public IntListIterator listIterator(int index) {
130        return new RandomAccessIntListIterator(this,index);            
131    }
132
133    public IntList subList(int fromIndex, int toIndex) {
134        return new RandomAccessIntSubList(this,fromIndex,toIndex);
135    }
136
137    public boolean equals(Object that) {
138        if(this == that) { 
139            return true; 
140        } else if(that instanceof IntList) {
141            IntList thatList = (IntList)that;
142            if(size() != thatList.size()) {
143                return false;
144            }
145            for(IntIterator thatIter = thatList.iterator(), thisIter = iterator(); thisIter.hasNext();) {
146                if(thisIter.next() != thatIter.next()) { 
147                    return false; 
148                }
149            }
150            return true;
151        } else {
152            return false;
153        }        
154    }
155    
156    public int hashCode() {
157        int hash = 1;
158        for(IntIterator iter = iterator(); iter.hasNext(); ) {
159            hash = 31*hash + iter.next();
160        }
161        return hash;
162    }
163    
164    public String toString() {
165        StringBuffer buf = new StringBuffer();
166        buf.append("[");
167        for(IntIterator iter = iterator(); iter.hasNext();) {
168            buf.append(iter.next());
169            if(iter.hasNext()) {
170                buf.append(", ");
171            }
172        }
173        buf.append("]");
174        return buf.toString();
175    }
176    
177    // protected utilities
178    //-------------------------------------------------------------------------
179    
180    /** Get my count of structural modifications. */
181    protected int getModCount() {
182        return _modCount;
183    }
184
185    /** Increment my count of structural modifications. */
186    protected void incrModCount() {
187        _modCount++;
188    }
189
190    // attributes
191    //-------------------------------------------------------------------------
192    
193    private int _modCount = 0;
194
195    // inner classes
196    //-------------------------------------------------------------------------
197    
198    private static class ComodChecker {
199        ComodChecker(RandomAccessIntList source) {
200            _source = source;  
201            resyncModCount();             
202        }
203        
204        protected RandomAccessIntList getList() {
205            return _source;
206        }
207        
208        protected void assertNotComodified() throws ConcurrentModificationException {
209            if(_expectedModCount != getList().getModCount()) {
210                throw new ConcurrentModificationException();
211            }
212        }
213            
214        protected void resyncModCount() {
215            _expectedModCount = getList().getModCount();
216        }
217        
218        private RandomAccessIntList _source = null;
219        private int _expectedModCount = -1;
220    }
221    
222    protected static class RandomAccessIntListIterator extends ComodChecker implements IntListIterator {
223        RandomAccessIntListIterator(RandomAccessIntList list, int index) {
224            super(list);
225            if(index < 0 || index > getList().size()) {
226                throw new IndexOutOfBoundsException("Index " + index + " not in [0," + getList().size() + ")");
227            } else {
228                _nextIndex = index;
229                resyncModCount();
230            }
231        }
232            
233        public boolean hasNext() {
234            assertNotComodified();
235            return _nextIndex < getList().size();
236        }
237        
238        public boolean hasPrevious() {
239            assertNotComodified();
240            return _nextIndex > 0;
241        }
242        
243        public int nextIndex() {
244            assertNotComodified();
245            return _nextIndex;
246        }
247        
248        public int previousIndex() {
249            assertNotComodified();
250            return _nextIndex - 1;
251        }
252        
253        public int next() {
254            assertNotComodified();
255            if(!hasNext()) {
256                throw new NoSuchElementException();
257            } else {
258                int val = getList().get(_nextIndex);
259                _lastReturnedIndex = _nextIndex;
260                _nextIndex++;
261                return val;
262            }
263        }
264        
265        public int previous() {
266            assertNotComodified();
267            if(!hasPrevious()) {
268                throw new NoSuchElementException();
269            } else {
270                int val = getList().get(_nextIndex-1);
271                _lastReturnedIndex = _nextIndex-1;
272                _nextIndex--;
273                return val;
274            }
275        }
276        
277        public void add(int value) {
278            assertNotComodified();
279            getList().add(_nextIndex,value);
280            _nextIndex++;
281            _lastReturnedIndex = -1;
282            resyncModCount();
283        }
284    
285        public void remove() {
286            assertNotComodified();
287            if (_lastReturnedIndex == -1) {
288                throw new IllegalStateException();
289            }
290            if (_lastReturnedIndex == _nextIndex) {
291                // remove() following previous()
292                getList().removeElementAt(_lastReturnedIndex);
293            } else {
294                // remove() following next()
295                getList().removeElementAt(_lastReturnedIndex);
296                _nextIndex--;
297            }
298            _lastReturnedIndex = -1;
299            resyncModCount();
300        }
301        
302        public void set(int value) {
303            assertNotComodified();
304            if(-1 == _lastReturnedIndex) {
305                throw new IllegalStateException();
306            } else {
307                getList().set(_lastReturnedIndex,value);
308                resyncModCount();
309            }
310        }
311        
312        private int _nextIndex = 0;
313        private int _lastReturnedIndex = -1;        
314    }   
315
316    protected static class RandomAccessIntSubList extends RandomAccessIntList implements IntList {
317        RandomAccessIntSubList(RandomAccessIntList list, int fromIndex, int toIndex) {
318            if(fromIndex < 0 || toIndex > list.size()) {
319                throw new IndexOutOfBoundsException();
320            } else if(fromIndex > toIndex) {
321                throw new IllegalArgumentException();                
322            } else {
323                _list = list;
324                _offset = fromIndex;
325                _limit = toIndex - fromIndex;
326                _comod = new ComodChecker(list);
327                _comod.resyncModCount();
328            }            
329        }
330    
331        public int get(int index) {
332            checkRange(index);
333            _comod.assertNotComodified();
334            return _list.get(toUnderlyingIndex(index));
335        }
336    
337        public int removeElementAt(int index) {
338            checkRange(index);
339            _comod.assertNotComodified();
340            int val = _list.removeElementAt(toUnderlyingIndex(index));
341            _limit--;
342            _comod.resyncModCount();
343            incrModCount();
344            return val;
345        }
346    
347        public int set(int index, int element) {
348            checkRange(index);
349            _comod.assertNotComodified();
350            int val = _list.set(toUnderlyingIndex(index),element);
351            incrModCount();
352            _comod.resyncModCount();
353            return val;
354        }
355    
356        public void add(int index, int element) {
357            checkRangeIncludingEndpoint(index);
358            _comod.assertNotComodified();
359             _list.add(toUnderlyingIndex(index),element);
360            _limit++;
361            _comod.resyncModCount();
362            incrModCount();
363        }
364    
365        public int size() {
366            _comod.assertNotComodified();
367            return _limit;
368        }
369    
370        private void checkRange(int index) {
371            if(index < 0 || index >= size()) {
372                throw new IndexOutOfBoundsException("index " + index + " not in [0," + size() + ")");
373            }
374        }
375          
376        private void checkRangeIncludingEndpoint(int index) {
377            if(index < 0 || index > size()) {
378                throw new IndexOutOfBoundsException("index " + index + " not in [0," + size() + "]");
379            }
380        }
381          
382        private int toUnderlyingIndex(int index) {
383            return (index + _offset);
384        }
385        
386        private int _offset = 0;        
387        private int _limit = 0; 
388        private RandomAccessIntList _list = null;
389        private ComodChecker _comod = null;
390    
391    }
392}
393