001    /*
002     * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
003     * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
004     *
005     *
006     *
007     *
008     *
009     *
010     *
011     *
012     *
013     *
014     *
015     *
016     *
017     *
018     *
019     *
020     *
021     *
022     *
023     *
024     */
025    
026    package railo.commons.util.mod;
027    
028    import java.util.Arrays;
029    import java.util.Collection;
030    import java.util.Iterator;
031    
032    public abstract class AbstractCollection<E> implements Collection<E> {
033        /**
034         * Sole constructor.  (For invocation by subclass constructors, typically
035         * implicit.)
036         */
037        protected AbstractCollection() {
038        }
039    
040        // Query Operations
041    
042        /**
043         * Returns an iterator over the elements contained in this collection.
044         *
045         * @return an iterator over the elements contained in this collection
046         */
047        public abstract Iterator<E> iterator();
048    
049        public abstract int size();
050    
051        /**
052         * {@inheritDoc}
053         *
054         * <p>This implementation returns <tt>size() == 0</tt>.
055         */
056        public boolean isEmpty() {
057            return size() == 0;
058        }
059    
060        /**
061         * {@inheritDoc}
062         *
063         * <p>This implementation iterates over the elements in the collection,
064         * checking each element in turn for equality with the specified element.
065         *
066         * @throws ClassCastException   {@inheritDoc}
067         * @throws NullPointerException {@inheritDoc}
068         */
069        public boolean contains(Object o) {
070            Iterator<E> it = iterator();
071            if (o==null) {
072                while (it.hasNext())
073                    if (it.next()==null)
074                        return true;
075            } else {
076                while (it.hasNext())
077                    if (o.equals(it.next()))
078                        return true;
079            }
080            return false;
081        }
082    
083        /**
084         * {@inheritDoc}
085         *
086         * <p>This implementation returns an array containing all the elements
087         * returned by this collection's iterator, in the same order, stored in
088         * consecutive elements of the array, starting with index {@code 0}.
089         * The length of the returned array is equal to the number of elements
090         * returned by the iterator, even if the size of this collection changes
091         * during iteration, as might happen if the collection permits
092         * concurrent modification during iteration.  The {@code size} method is
093         * called only as an optimization hint; the correct result is returned
094         * even if the iterator returns a different number of elements.
095         *
096         * <p>This method is equivalent to:
097         *
098         *  <pre> {@code
099         * List<E> list = new ArrayList<E>(size());
100         * for (E e : this)
101         *     list.add(e);
102         * return list.toArray();
103         * }</pre>
104         */
105        public Object[] toArray() {
106            // Estimate size of array; be prepared to see more or fewer elements
107            Object[] r = new Object[size()];
108            Iterator<E> it = iterator();
109            for (int i = 0; i < r.length; i++) {
110                if (! it.hasNext()) // fewer elements than expected
111                    return Arrays.copyOf(r, i);
112                r[i] = it.next();
113            }
114            return it.hasNext() ? finishToArray(r, it) : r;
115        }
116    
117        /**
118         * {@inheritDoc}
119         *
120         * <p>This implementation returns an array containing all the elements
121         * returned by this collection's iterator in the same order, stored in
122         * consecutive elements of the array, starting with index {@code 0}.
123         * If the number of elements returned by the iterator is too large to
124         * fit into the specified array, then the elements are returned in a
125         * newly allocated array with length equal to the number of elements
126         * returned by the iterator, even if the size of this collection
127         * changes during iteration, as might happen if the collection permits
128         * concurrent modification during iteration.  The {@code size} method is
129         * called only as an optimization hint; the correct result is returned
130         * even if the iterator returns a different number of elements.
131         *
132         * <p>This method is equivalent to:
133         *
134         *  <pre> {@code
135         * List<E> list = new ArrayList<E>(size());
136         * for (E e : this)
137         *     list.add(e);
138         * return list.toArray(a);
139         * }</pre>
140         *
141         * @throws ArrayStoreException  {@inheritDoc}
142         * @throws NullPointerException {@inheritDoc}
143         */
144        public <T> T[] toArray(T[] a) {
145            // Estimate size of array; be prepared to see more or fewer elements
146            int size = size();
147            T[] r = a.length >= size ? a :
148                      (T[])java.lang.reflect.Array
149                      .newInstance(a.getClass().getComponentType(), size);
150            Iterator<E> it = iterator();
151    
152            for (int i = 0; i < r.length; i++) {
153                if (! it.hasNext()) { // fewer elements than expected
154                    if (a != r)
155                        return Arrays.copyOf(r, i);
156                    r[i] = null; // null-terminate
157                    return r;
158                }
159                r[i] = (T)it.next();
160            }
161            return it.hasNext() ? finishToArray(r, it) : r;
162        }
163    
164        /**
165         * The maximum size of array to allocate.
166         * Some VMs reserve some header words in an array.
167         * Attempts to allocate larger arrays may result in
168         * OutOfMemoryError: Requested array size exceeds VM limit
169         */
170        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
171    
172        /**
173         * Reallocates the array being used within toArray when the iterator
174         * returned more elements than expected, and finishes filling it from
175         * the iterator.
176         *
177         * @param r the array, replete with previously stored elements
178         * @param it the in-progress iterator over this collection
179         * @return array containing the elements in the given array, plus any
180         *         further elements returned by the iterator, trimmed to size
181         */
182        private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
183            int i = r.length;
184            while (it.hasNext()) {
185                int cap = r.length;
186                if (i == cap) {
187                    int newCap = cap + (cap >> 1) + 1;
188                    // overflow-conscious code
189                    if (newCap - MAX_ARRAY_SIZE > 0)
190                        newCap = hugeCapacity(cap + 1);
191                    r = Arrays.copyOf(r, newCap);
192                }
193                r[i++] = (T)it.next();
194            }
195            // trim if overallocated
196            return (i == r.length) ? r : Arrays.copyOf(r, i);
197        }
198    
199        private static int hugeCapacity(int minCapacity) {
200            if (minCapacity < 0) // overflow
201                throw new OutOfMemoryError
202                    ("Required array size too large");
203            return (minCapacity > MAX_ARRAY_SIZE) ?
204                Integer.MAX_VALUE :
205                MAX_ARRAY_SIZE;
206        }
207    
208        // Modification Operations
209    
210        /**
211         * {@inheritDoc}
212         *
213         * <p>This implementation always throws an
214         * <tt>UnsupportedOperationException</tt>.
215         *
216         * @throws UnsupportedOperationException {@inheritDoc}
217         * @throws ClassCastException            {@inheritDoc}
218         * @throws NullPointerException          {@inheritDoc}
219         * @throws IllegalArgumentException      {@inheritDoc}
220         * @throws IllegalStateException         {@inheritDoc}
221         */
222        public boolean add(E e) {
223            throw new UnsupportedOperationException();
224        }
225    
226        /**
227         * {@inheritDoc}
228         *
229         * <p>This implementation iterates over the collection looking for the
230         * specified element.  If it finds the element, it removes the element
231         * from the collection using the iterator's remove method.
232         *
233         * <p>Note that this implementation throws an
234         * <tt>UnsupportedOperationException</tt> if the iterator returned by this
235         * collection's iterator method does not implement the <tt>remove</tt>
236         * method and this collection contains the specified object.
237         *
238         * @throws UnsupportedOperationException {@inheritDoc}
239         * @throws ClassCastException            {@inheritDoc}
240         * @throws NullPointerException          {@inheritDoc}
241         */
242        public boolean remove(Object o) {
243            Iterator<E> it = iterator();
244            if (o==null) {
245                while (it.hasNext()) {
246                    if (it.next()==null) {
247                        it.remove();
248                        return true;
249                    }
250                }
251            } else {
252                while (it.hasNext()) {
253                    if (o.equals(it.next())) {
254                        it.remove();
255                        return true;
256                    }
257                }
258            }
259            return false;
260        }
261    
262    
263        // Bulk Operations
264    
265        @Override
266        public boolean containsAll(Collection<?> c) {
267            for (Object e : c)
268                if (!contains(e))
269                    return false;
270            return true;
271        }
272    
273        @Override
274        public boolean addAll(Collection<? extends E> c) {
275            boolean modified = false;
276            for (E e : c)
277                if (add(e))
278                    modified = true;
279            return modified;
280        }
281    
282        @Override
283        public boolean removeAll(Collection<?> c) {
284            boolean modified = false;
285            Iterator<?> it = iterator();
286            while (it.hasNext()) {
287                if (c.contains(it.next())) {
288                    it.remove();
289                    modified = true;
290                }
291            }
292            return modified;
293        }
294    
295        @Override
296        public boolean retainAll(Collection<?> c) {
297            boolean modified = false;
298            Iterator<E> it = iterator();
299            while (it.hasNext()) {
300                if (!c.contains(it.next())) {
301                    it.remove();
302                    modified = true;
303                }
304            }
305            return modified;
306        }
307    
308        /**
309         * {@inheritDoc}
310         *
311         * <p>This implementation iterates over this collection, removing each
312         * element using the <tt>Iterator.remove</tt> operation.  Most
313         * implementations will probably choose to override this method for
314         * efficiency.
315         *
316         * <p>Note that this implementation will throw an
317         * <tt>UnsupportedOperationException</tt> if the iterator returned by this
318         * collection's <tt>iterator</tt> method does not implement the
319         * <tt>remove</tt> method and this collection is non-empty.
320         *
321         * @throws UnsupportedOperationException {@inheritDoc}
322         */
323        public void clear() {
324            Iterator<E> it = iterator();
325            while (it.hasNext()) {
326                it.next();
327                it.remove();
328            }
329        }
330    
331    
332        //  String conversion
333    
334        /**
335         * Returns a string representation of this collection.  The string
336         * representation consists of a list of the collection's elements in the
337         * order they are returned by its iterator, enclosed in square brackets
338         * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
339         * <tt>", "</tt> (comma and space).  Elements are converted to strings as
340         * by {@link String#valueOf(Object)}.
341         *
342         * @return a string representation of this collection
343         */
344        public String toString() {
345            Iterator<E> it = iterator();
346            if (! it.hasNext())
347                return "[]";
348    
349            StringBuilder sb = new StringBuilder();
350            sb.append('[');
351            for (;;) {
352                E e = it.next();
353                sb.append(e == this ? "(this Collection)" : e);
354                if (! it.hasNext())
355                    return sb.append(']').toString();
356                sb.append(',').append(' ');
357            }
358        }
359    
360    }