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