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 LongList}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(long)} 
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 0.1
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 RandomAccessLongList extends AbstractLongCollection implements LongList {
041
042    // constructors
043    //-------------------------------------------------------------------------
044
045    /** Constructs an empty list. */
046    protected RandomAccessLongList() { 
047    }    
048
049    // fully abstract methods
050    //-------------------------------------------------------------------------
051    
052    public abstract long 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 long 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 long set(int index, long 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, long element) {
079        throw new UnsupportedOperationException();
080    }
081
082    //-------------------------------------------------------------------------
083
084    // javadocs here are inherited
085    
086    public boolean add(long element) {
087        add(size(),element);
088        return true;
089    }
090
091    public boolean addAll(int index, LongCollection collection) {
092        boolean modified = false;
093        for(LongIterator iter = collection.iterator(); iter.hasNext(); ) {
094            add(index++,iter.next());
095            modified = true;
096        }
097        return modified;
098    }
099
100    public int indexOf(long element) {
101        int i = 0;
102        for(LongIterator 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(long element) {
113        for(LongListIterator iter = listIterator(size()); iter.hasPrevious(); ) {
114            if(iter.previous() == element) {
115                return iter.nextIndex();
116            }
117        }
118        return -1;
119    }
120
121    public LongIterator iterator() {
122        return listIterator();
123    }
124
125    public LongListIterator listIterator() {
126        return listIterator(0);
127    }
128
129    public LongListIterator listIterator(int index) {
130        return new RandomAccessLongListIterator(this,index);            
131    }
132
133    public LongList subList(int fromIndex, int toIndex) {
134        return new RandomAccessLongSubList(this,fromIndex,toIndex);
135    }
136
137    public boolean equals(Object that) {
138        if(this == that) { 
139            return true; 
140        } else if(that instanceof LongList) {
141            LongList thatList = (LongList)that;
142            if(size() != thatList.size()) {
143                return false;
144            }
145            for(LongIterator 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(LongIterator iter = iterator(); iter.hasNext(); ) {
159                long val = iter.next();
160            hash = 31*hash + ((int)(val ^ (val >>> 32)));
161        }
162        return hash;
163    }
164    
165    public String toString() {
166        StringBuffer buf = new StringBuffer();
167        buf.append("[");
168        for(LongIterator iter = iterator(); iter.hasNext();) {
169            buf.append(iter.next());
170            if(iter.hasNext()) {
171                buf.append(", ");
172            }
173        }
174        buf.append("]");
175        return buf.toString();
176    }
177    
178    // protected utilities
179    //-------------------------------------------------------------------------
180    
181    /** Get my count of structural modifications. */
182    protected int getModCount() {
183        return _modCount;
184    }
185
186    /** Increment my count of structural modifications. */
187    protected void incrModCount() {
188        _modCount++;
189    }
190
191    // attributes
192    //-------------------------------------------------------------------------
193    
194    private int _modCount = 0;
195
196    // inner classes
197    //-------------------------------------------------------------------------
198    
199    private static class ComodChecker {
200        ComodChecker(RandomAccessLongList source) {
201            _source = source;  
202            resyncModCount();             
203        }
204        
205        protected RandomAccessLongList getList() {
206            return _source;
207        }
208        
209        protected void assertNotComodified() throws ConcurrentModificationException {
210            if(_expectedModCount != getList().getModCount()) {
211                throw new ConcurrentModificationException();
212            }
213        }
214            
215        protected void resyncModCount() {
216            _expectedModCount = getList().getModCount();
217        }
218        
219        private RandomAccessLongList _source = null;
220        private int _expectedModCount = -1;
221    }
222    
223    protected static class RandomAccessLongListIterator extends ComodChecker implements LongListIterator {
224        RandomAccessLongListIterator(RandomAccessLongList list, int index) {
225            super(list);
226            if(index < 0 || index > getList().size()) {
227                throw new IndexOutOfBoundsException("Index " + index + " not in [0," + getList().size() + ")");
228            } else {
229                _nextIndex = index;
230                resyncModCount();
231            }
232        }
233            
234        public boolean hasNext() {
235            assertNotComodified();
236            return _nextIndex < getList().size();
237        }
238        
239        public boolean hasPrevious() {
240            assertNotComodified();
241            return _nextIndex > 0;
242        }
243        
244        public int nextIndex() {
245            assertNotComodified();
246            return _nextIndex;
247        }
248        
249        public int previousIndex() {
250            assertNotComodified();
251            return _nextIndex - 1;
252        }
253        
254        public long next() {
255            assertNotComodified();
256            if(!hasNext()) {
257                throw new NoSuchElementException();
258            } else {
259                long val = getList().get(_nextIndex);
260                _lastReturnedIndex = _nextIndex;
261                _nextIndex++;
262                return val;
263            }
264        }
265        
266        public long previous() {
267            assertNotComodified();
268            if(!hasPrevious()) {
269                throw new NoSuchElementException();
270            } else {
271                long val = getList().get(_nextIndex-1);
272                _lastReturnedIndex = _nextIndex-1;
273                _nextIndex--;
274                return val;
275            }
276        }
277        
278        public void add(long value) {
279            assertNotComodified();
280            getList().add(_nextIndex,value);
281            _nextIndex++;
282            _lastReturnedIndex = -1;
283            resyncModCount();
284        }
285    
286        public void remove() {
287            assertNotComodified();
288            if (_lastReturnedIndex == -1) {
289                throw new IllegalStateException();
290            }
291            if (_lastReturnedIndex == _nextIndex) {
292                // remove() following previous()
293                getList().removeElementAt(_lastReturnedIndex);
294            } else {
295                // remove() following next()
296                getList().removeElementAt(_lastReturnedIndex);
297                _nextIndex--;
298            }
299            _lastReturnedIndex = -1;
300            resyncModCount();
301        }
302        
303        public void set(long value) {
304            assertNotComodified();
305            if(-1 == _lastReturnedIndex) {
306                throw new IllegalStateException();
307            } else {
308                getList().set(_lastReturnedIndex,value);
309                resyncModCount();
310            }
311        }
312        
313        private int _nextIndex = 0;
314        private int _lastReturnedIndex = -1;        
315    }   
316
317    protected static class RandomAccessLongSubList extends RandomAccessLongList implements LongList {
318        RandomAccessLongSubList(RandomAccessLongList list, int fromIndex, int toIndex) {
319            if(fromIndex < 0 || toIndex > list.size()) {
320                throw new IndexOutOfBoundsException();
321            } else if(fromIndex > toIndex) {
322                throw new IllegalArgumentException();                
323            } else {
324                _list = list;
325                _offset = fromIndex;
326                _limit = toIndex - fromIndex;
327                _comod = new ComodChecker(list);
328                _comod.resyncModCount();
329            }            
330        }
331    
332        public long get(int index) {
333            checkRange(index);
334            _comod.assertNotComodified();
335            return _list.get(toUnderlyingIndex(index));
336        }
337    
338        public long removeElementAt(int index) {
339            checkRange(index);
340            _comod.assertNotComodified();
341            long val = _list.removeElementAt(toUnderlyingIndex(index));
342            _limit--;
343            _comod.resyncModCount();
344            incrModCount();
345            return val;
346        }
347    
348        public long set(int index, long element) {
349            checkRange(index);
350            _comod.assertNotComodified();
351            long val = _list.set(toUnderlyingIndex(index),element);
352            incrModCount();
353            _comod.resyncModCount();
354            return val;
355        }
356    
357        public void add(int index, long element) {
358            checkRangeIncludingEndpoint(index);
359            _comod.assertNotComodified();
360             _list.add(toUnderlyingIndex(index),element);
361            _limit++;
362            _comod.resyncModCount();
363            incrModCount();
364        }
365    
366        public int size() {
367            _comod.assertNotComodified();
368            return _limit;
369        }
370    
371        private void checkRange(int index) {
372            if(index < 0 || index >= size()) {
373                throw new IndexOutOfBoundsException("index " + index + " not in [0," + size() + ")");
374            }
375        }
376          
377        private void checkRangeIncludingEndpoint(int index) {
378            if(index < 0 || index > size()) {
379                throw new IndexOutOfBoundsException("index " + index + " not in [0," + size() + "]");
380            }
381        }
382          
383        private int toUnderlyingIndex(int index) {
384            return (index + _offset);
385        }
386        
387        private int _offset = 0;        
388        private int _limit = 0; 
389        private RandomAccessLongList _list = null;
390        private ComodChecker _comod = null;
391    
392    }
393}
394