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