IonSequenceLite.java

/*
 * Copyright 2007-2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License").
 * You may not use this file except in compliance with the License.
 * A copy of the License is located at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * or in the "license" file accompanying this file. This file is distributed
 * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
 * express or implied. See the License for the specific language governing
 * permissions and limitations under the License.
 */

package com.amazon.ion.impl.lite;

import com.amazon.ion.ContainedValueException;
import com.amazon.ion.IonSequence;
import com.amazon.ion.IonValue;
import com.amazon.ion.ValueFactory;
import com.amazon.ion.impl._Private_CurriedValueFactory;
import com.amazon.ion.impl._Private_IonValue;

import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;


abstract class IonSequenceLite
    extends IonContainerLite
    implements IonSequence
{
    /**
     * A zero-length array.
     */
    protected static final IonValueLite[] EMPTY_VALUE_ARRAY = new IonValueLite[0];

    IonSequenceLite(ContainerlessContext context, boolean isNull)
    {
        super(context, isNull);
    }

    IonSequenceLite(IonSequenceLite existing, IonContext context) {
        super(existing, context);
    }

    /**
     * Constructs a sequence value <em>not</em> backed by binary.
     *
     * @param elements
     *   the initial set of child elements.  If <code>null</code>, then the new
     *   instance will have <code>{@link #isNullValue()} == true</code>.
     *
     * @throws ContainedValueException if any value in <code>elements</code>
     * has <code>{@link IonValue#getContainer()} != null</code>.
     * @throws IllegalArgumentException
     * @throws NullPointerException
     */
    IonSequenceLite(ContainerlessContext context,
                    Collection<? extends IonValue> elements)
        throws ContainedValueException, NullPointerException,
            IllegalArgumentException
    {
        this(context, (elements == null));
        assert _children == null;

        if (elements != null)
        {
            _children = new IonValueLite[elements.size()];
            for (Iterator i = elements.iterator(); i.hasNext();)
            {
                IonValueLite element = (IonValueLite) i.next();
                super.add(element);
            }
        }
    }

    //=========================================================================

    @Override
    public IonSequence clone() {
        return (IonSequence) deepClone(false);
    }

    @Override
    // Increasing visibility
    public boolean add(IonValue element)
        throws ContainedValueException, NullPointerException
    {
        // super.add will check for the lock
        return super.add(element);
    }

    public boolean addAll(Collection<? extends IonValue> c)
    {
        checkForLock();

        if (c == null) {
            throw new NullPointerException();
        }

        boolean changed = false;

        for (IonValue v : c)
        {
            changed = add(v) || changed;
        }

        return changed;
    }

    public boolean addAll(int index, Collection<? extends IonValue> c)
    {
        checkForLock();

        if (c == null) {
            throw new NullPointerException();
        }
        if (index < 0 || index > size())
        {
            throw new IndexOutOfBoundsException();
        }

        // TODO optimize to avoid n^2 shifting and renumbering of elements.
        boolean changed = false;

        for (IonValue v : c)
        {
            add(index++, v);
            changed = true;
        }

        if (changed) {
            patch_elements_helper(index);
        }

        return changed;
    }


    public ValueFactory add()
    {
        return new _Private_CurriedValueFactory(this.getSystem())
        {
            @Override
            protected void handle(IonValue newValue)
            {
                add(newValue);
            }
        };
    }


    public void add(int index, IonValue element)
        throws ContainedValueException, NullPointerException
    {
        add(index, (IonValueLite) element);
    }

    public ValueFactory add(final int index)
    {
        return new _Private_CurriedValueFactory(getSystem())
        {
            @Override
            protected void handle(IonValue newValue)
            {
                add(index, newValue);
                patch_elements_helper(index + 1);
            }
        };
    }

    public IonValue set(int index, IonValue element)
    {
        checkForLock();
        final IonValueLite concrete = ((IonValueLite) element);

        // NOTE: size calls makeReady() so we don't have to
        if (index < 0 || index >= size())
        {
            throw new IndexOutOfBoundsException("" + index);
        }

        validateNewChild(element);

        assert _children != null; // else index would be out of bounds above.
        concrete._context = getContextForIndex(element, index);
        IonValueLite removed = set_child(index, concrete);
        concrete._elementid(index);

        removed.detachFromContainer();
        // calls setDirty(), UNLESS it hits an IOException

        return removed;
    }

    public IonValue remove(int index)
    {
        checkForLock();

        if (index < 0 || index >= get_child_count()) {
            throw new IndexOutOfBoundsException("" + index);
        }

        IonValueLite v = get_child(index);
        assert(v._elementid() == index);
        remove_child(index);
        patch_elements_helper(index);
        return v;
    }

    public boolean remove(Object o)
    {
        checkForLock();

        int idx = lastIndexOf(o);
        if (idx < 0) {
            return false;
        }
        assert(o instanceof IonValueLite); // since it's in our current array
        assert( ((IonValueLite)o)._elementid() == idx );

        remove_child(idx);
        patch_elements_helper(idx);
        return true;
    }

    public boolean removeAll(Collection<?> c)
    {
        boolean changed = false;

        checkForLock();

        // remove the collection member if it is a
        // member of our child array keep track of
        // the lowest array index for later patching
        for (Object o : c) {
            int idx = lastIndexOf(o);
            if (idx >= 0) {
                assert(o == get_child(idx));
                remove_child(idx);
                patch_elements_helper(idx);
                changed = true;
            }
        }
        return changed;
    }

    public boolean retainAll(Collection<?> c)
    {
        checkForLock();

        if (get_child_count() < 1) return false;

        // TODO this method (and probably several others) needs optimization.
        IdentityHashMap<IonValue, IonValue> keepers =
            new IdentityHashMap<IonValue, IonValue>();

        for (Object o : c)
        {
            IonValue v = (IonValue) o;
            if (this == v.getContainer()) keepers.put(v, v);
        }

        boolean changed = false;
        for (int ii = get_child_count(); ii > 0; )
        {
            ii--;
            IonValue v = get_child(ii);
            if (! keepers.containsKey(v))
            {
                remove(v);
                patch_elements_helper(ii);
                changed = true;
            }
        }

        return changed;
    }

    public boolean contains(Object o)
    {
        if (o == null) {
            throw new NullPointerException();
        }
        if (!(o instanceof IonValue)) {
            throw new ClassCastException();
        }
        return ((IonValue)o).getContainer() == this;
    }

    public boolean containsAll(Collection<?> c)
    {
        for (Object o : c)
        {
            if (! contains(o)) return false;
        }
        return true;
    }

    public int indexOf(Object o)
    {
        if (o == null) {
            throw new NullPointerException();
        }
        _Private_IonValue v = (_Private_IonValue) o;
        if (this != v.getContainer()) return -1;
        return v.getElementId();
    }

    public int lastIndexOf(Object o)
    {
        return indexOf(o);
    }

    private static void checkSublistParameters(int size, int fromIndex, int toIndex)
    {
        if(fromIndex < 0)
        {
            throw new IndexOutOfBoundsException("fromIndex is less than zero");
        }
        if(toIndex < fromIndex)
        {
            throw new IllegalArgumentException("toIndex may not be less than fromIndex");
        }
        if(toIndex > size)
        {
            throw new IndexOutOfBoundsException("toIndex exceeds size");
        }
    }

    public List<IonValue> subList(int fromIndex, int toIndex)
    {
        checkSublistParameters(this.size(), fromIndex, toIndex);
        return new SubListView(fromIndex, toIndex);
    }

    public IonValue[] toArray()
    {
        if (get_child_count() < 1) return EMPTY_VALUE_ARRAY;

        IonValue[] array = new IonValue[get_child_count()];
        System.arraycopy(_children, 0, array, 0, get_child_count());
        return array;
    }

    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a)
    {
        int size = get_child_count();
        if (a.length < size)
        {
            // TODO JDK 1.6 this could use Arrays.copyOf
            Class<?> type = a.getClass().getComponentType();
            // generates unchecked warning
            a = (T[]) Array.newInstance(type, size);
        }
        if (size > 0) {
            System.arraycopy(_children, 0, a, 0, size);
        }
        if (size < a.length) {
            // A surprising bit of spec.
            // this is required even with a 0 entries
            a[size] = null;
        }
        return a;
    }

    @SuppressWarnings("unchecked")
    public <T extends IonValue> T[] extract(Class<T> type)
    {
        checkForLock();

        if (isNullValue()) return null;
        T[] array = (T[]) Array.newInstance(type, size());
        toArray(array);
        clear();
        return array;
    }

    /**
     * SubListView throws a {@link ConcurrentModificationException} if the parent list has any
     * structural modifications, i.e. any operation that cause its size to change. To determine if
     * a parent structural modification happened it keeps track of the structural modification count
     * to compare against the parent
     *
     * Structural modifications from the sublist itself are allowed.
     */
    private class SubListView extends AbstractList<IonValue> {

        /**
         * index in top level IonSequenceLite that marks the start of this sublist view. For nested
         * sublists fromIndex will be in relation to the root parent which must be a IonSequenceLite
         */
        private final int fromIndex;
        private int size;

        private SubListView(final int fromIndex, final int toIndex) {
            this.fromIndex = fromIndex;
            this.size = toIndex - fromIndex;
            super.modCount = IonSequenceLite.this.structuralModificationCount;
        }

        @Override
        public int size() {
            checkForParentModification();
            return size;
        }

        @Override
        public boolean isEmpty() {
            checkForParentModification();
            return size == 0;
        }

        @Override
        public IonValue get(final int index) {
            checkForParentModification();
            rangeCheck(index);

            return IonSequenceLite.this.get(toParentIndex(index));
        }

        @Override
        public IonValue set(final int index, final IonValue element) {
            checkForParentModification();
            rangeCheck(index);

            return IonSequenceLite.this.set(toParentIndex(index), element);
        }

        @Override
        public boolean contains(final Object o) {
            checkForParentModification();
            return super.contains(o);
        }

        @Override
        public boolean containsAll(final Collection<?> collection) {
            checkForParentModification();
            return super.containsAll(collection);
        }

        @Override
        public Object[] toArray() {
            checkForParentModification();
            return super.toArray();
        }

        @Override
        public <T> T[] toArray(T[] ts) {
            checkForParentModification();
            return super.toArray(ts);
        }

        @Override
        public boolean add(final IonValue ionValue) {
            checkForParentModification();

            int parentIndex = toParentIndex(size);

            // adds at end of parent list
            if (parentIndex == IonSequenceLite.this.size()) {
                IonSequenceLite.this.add(ionValue);
            } else {
                IonSequenceLite.this.add(parentIndex, ionValue);
            }

            super.modCount = IonSequenceLite.this.structuralModificationCount;
            size++;

            return true;
        }

        @Override
        public void add(final int index, final IonValue ionValue) {
            checkForParentModification();
            rangeCheck(index);

            IonSequenceLite.this.add(toParentIndex(index), ionValue);

            super.modCount = IonSequenceLite.this.structuralModificationCount;
            size++;
        }


        @Override
        public boolean addAll(int i, Collection<? extends IonValue> collection) {
            checkForParentModification();
            return super.addAll(i, collection);
        }


        @Override
        public boolean addAll(Collection<? extends IonValue> collection) {
            checkForParentModification();
            return super.addAll(collection);
        }

        // retainAll has no functionality that is specific to SubListView but
        // needs to be implemented because the AbstractList<T>.retainAll() throws [UnsupportedOperationException].
        @Override
        public boolean retainAll(final Collection<?> c) {
            checkForParentModification();
            if (size < 1) {
                return false;
            }

            final Map<Object,Object> toRetain = new IdentityHashMap<Object,Object>();
            for (Object o : c) {
                toRetain.put(o, null);
            }

            final List<IonValue> toRemove = new ArrayList<IonValue>(size - c.size());
            for (int i = 0; i < size; i++) {
                final IonValue ionValue = get(i);

                if (!toRetain.containsKey(ionValue)) {
                    toRemove.add(ionValue);
                }
            }

            return removeAll(toRemove);
        }

        @Override
        public void clear() {
            checkForParentModification();

            // remove the first element size times to remove all elements
            int parentIndex = toParentIndex(0);
            for (int i = 0; i < size; i++) {
                IonSequenceLite.this.remove(parentIndex);
            }

            size = 0;
            super.modCount = IonSequenceLite.this.structuralModificationCount;
        }

        @Override
        public IonValue remove(final int index) {
            checkForParentModification();
            rangeCheck(index);

            final IonValue removed = IonSequenceLite.this.remove(toParentIndex(index));

            super.modCount = IonSequenceLite.this.structuralModificationCount;
            size--;

            return removed;
        }

        // remove(Object) contains no functionality that is specific to SubListView but
        // needs to be implemented because the AbstractList<T>.remove(Object) throws [UnsupportedOperationException].
        @Override
        public boolean remove(final Object o) {
            checkForParentModification();
            int index = indexOf(o);
            if (index < 0) {
                return false;
            }

            remove(index);
            return true;
        }

        // removeAll(Collection<?>) contains no functionality that is specific to SubListView but
        // needs to be implemented because the AbstractList<T>.remove(Object) throws [UnsupportedOperationException].
        @Override
        public boolean removeAll(final Collection<?> c) {
            checkForParentModification();
            boolean changed = false;
            for (Object o : c) {
                if (remove(o)) {
                    changed = true;
                }
            }

            return changed;
        }

        @Override
        public int indexOf(final Object o) {
            checkForParentModification();
            return super.indexOf(o);
        }

        @Override
        public int lastIndexOf(Object o) {
            checkForParentModification();
            return super.lastIndexOf(o);
        }

        @Override
        protected void removeRange(int from, int to) {
            checkForParentModification();
            super.removeRange(from, to);
        }


        @Override
        public Iterator<IonValue> iterator() {
            return listIterator(0);
        }

        @Override
        public ListIterator<IonValue> listIterator() {
            return listIterator(0);
        }

        @Override
        public ListIterator<IonValue> listIterator(final int index) {
            checkForParentModification();

            return new ListIterator<IonValue>() {
                private int lastReturnedIndex = index;
                private int nextIndex = index;

                public boolean hasNext() {
                    return nextIndex < SubListView.this.size();
                }

                public IonValue next() {
                    lastReturnedIndex = nextIndex++;
                    return SubListView.this.get(lastReturnedIndex);
                }

                public boolean hasPrevious() {
                    return nextIndex > 0;
                }

                public IonValue previous() {
                    lastReturnedIndex = --nextIndex;
                    return SubListView.this.get(lastReturnedIndex);
                }

                public int nextIndex() {
                    return nextIndex;
                }

                public int previousIndex() {
                    return nextIndex - 1;
                }

                public void remove() {
                    throw new UnsupportedOperationException();
                }

                public void set(final IonValue ionValue) {
                    SubListView.this.set(lastReturnedIndex, ionValue);
                }

                public void add(final IonValue ionValue) {
                    SubListView.this.add(lastReturnedIndex, ionValue);
                }
            };
        }

        @Override
        public List<IonValue> subList(final int fromIndex, final int toIndex) {
            checkSublistParameters(this.size(), fromIndex, toIndex);
            checkForParentModification();
            return new SubListView(toParentIndex(fromIndex), toParentIndex(toIndex));
        }

        @Override
        public boolean equals(Object o) {
            checkForParentModification();
            return super.equals(o);
        }

        @Override
        public int hashCode() {
            checkForParentModification();
            return super.hashCode();
        }

        @Override
        public String toString() {
            checkForParentModification();
            return super.toString();
        }

        private void rangeCheck(int index) {
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException(String.valueOf(index));
            }
        }

        private int toParentIndex(int index) {
            return index + fromIndex;
        }

        private void checkForParentModification() {
            if (super.modCount != IonSequenceLite.this.structuralModificationCount) {
                throw new ConcurrentModificationException();
            }
        }
    }
}