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.util.ConcurrentModificationException;
020    import 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 09:14:21 +0100 (Wed, 29 Nov 2006) $
037     * 
038     * @author Rodney Waldhoff 
039     */
040    public 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