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 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 */
036public 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