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