/*******************************************************************************
 * Copyright (c) 2010, 2015 Sonatype, Inc.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 *    Stuart McCulloch (Sonatype, Inc.) - initial API and implementation
 *******************************************************************************/
package org.eclipse.sisu.inject;

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.concurrent.atomic.AtomicReference;

/**
 * Ordered {@link List} that arranges elements by descending rank; supports concurrent iteration and modification.
 */
final class RankedSequence<T>
    extends AtomicReference<RankedSequence.Content>
    implements Iterable<T>
{
    // ----------------------------------------------------------------------
    // Constants
    // ----------------------------------------------------------------------

    private static final long serialVersionUID = 1L;

    // ----------------------------------------------------------------------
    // Constructors
    // ----------------------------------------------------------------------

    RankedSequence()
    {
        // nothing to do
    }

    RankedSequence( final RankedSequence<T> sequence )
    {
        if ( null != sequence )
        {
            set( sequence.get() );
        }
    }

    // ----------------------------------------------------------------------
    // Public methods
    // ----------------------------------------------------------------------

    /**
     * Inserts the given element into the ordered list, using the assigned rank as a guide.
     * <p>
     * The rank can be any value from {@link Integer#MIN_VALUE} to {@link Integer#MAX_VALUE}.
     * 
     * @param element The element to insert
     * @param rank The assigned rank
     */
    public void insert( final T element, final int rank )
    {
        Content o, n;
        do
        {
            n = null != ( o = get() ) ? o.insert( element, rank ) : new Content( element, rank );
        }
        while ( !compareAndSet( o, n ) );
    }

    @SuppressWarnings( "unchecked" )
    public T peek()
    {
        final Content content = get();
        return null != content ? (T) content.objs[0] : null;
    }

    public boolean contains( final Object element )
    {
        final Content content = get();
        return null != content && content.indexOf( element ) >= 0;
    }

    public boolean containsThis( final Object element )
    {
        final Content content = get();
        return null != content && content.indexOfThis( element ) >= 0;
    }

    @SuppressWarnings( "unchecked" )
    public T remove( final Object element )
    {
        Content o, n;
        int index;
        do
        {
            if ( null == ( o = get() ) || ( index = o.indexOf( element ) ) < 0 )
            {
                return null;
            }
            n = o.remove( index );
        }
        while ( !compareAndSet( o, n ) );

        return (T) o.objs[index];
    }

    public boolean removeThis( final T element )
    {
        Content o, n;
        do
        {
            final int index;
            if ( null == ( o = get() ) || ( index = o.indexOfThis( element ) ) < 0 )
            {
                return false;
            }
            n = o.remove( index );
        }
        while ( !compareAndSet( o, n ) );

        return true;
    }

    @SuppressWarnings( { "rawtypes", "unchecked" } )
    public Iterable<T> snapshot()
    {
        final Content content = get();
        return null != content ? (List) Arrays.asList( content.objs ) : Collections.EMPTY_SET;
    }

    public void clear()
    {
        set( null );
    }

    public boolean isEmpty()
    {
        return null == get();
    }

    public int size()
    {
        final Content content = get();
        return null != content ? content.objs.length : 0;
    }

    public Itr iterator()
    {
        return new Itr();
    }

    // ----------------------------------------------------------------------
    // Implementation methods
    // ----------------------------------------------------------------------

    /**
     * Turns the given (potentially non-unique) rank into a unique id by appending a counter.
     * 
     * @param rank The assigned rank
     * @param uniq The unique counter
     * @return The unique id
     */
    static long rank2uid( final int rank, final int uniq )
    {
        return (long) ~rank << 32 | 0x00000000FFFFFFFFL & uniq;
    }

    /**
     * Extracts the original (potentially non-unique) assigned rank from the given unique id.
     * 
     * @param uid The unique id
     * @return Assigned rank
     */
    static int uid2rank( final long uid )
    {
        return (int) ( ~uid >>> 32 );
    }

    /**
     * Finds the insertion point with the nearest UID, regardless of whether the UID is in the list or not.
     * <p>
     * Unlike {@link Arrays#binarySearch} this will always return a number from zero to {@link #size()} inclusive.
     * 
     * @param uids The UIDs array
     * @param uid The UID to find
     * @return Index with nearest UID
     */
    static int safeBinarySearch( final long[] uids, final long uid )
    {
        if ( uid < uids[0] )
        {
            return 0;
        }
        int min = 0;
        int max = uids.length - 1;
        while ( min < max )
        {
            final int m = min + max >>> 1;
            if ( uid <= uids[m] )
            {
                max = m;
            }
            else
            {
                min = m + 1;
            }
        }
        if ( min == uids.length - 1 && uids[min] < uid )
        {
            min++; // append
        }
        return min;
    }

    // ----------------------------------------------------------------------
    // Implementation types
    // ----------------------------------------------------------------------

    /**
     * Represents an immutable snapshot of ranked elements.
     */
    static final class Content
    {
        // ----------------------------------------------------------------------
        // Implementation fields
        // ----------------------------------------------------------------------

        final Object[] objs;

        final long[] uids;

        final int uniq;

        // ----------------------------------------------------------------------
        // Constructors
        // ----------------------------------------------------------------------

        Content( final Object element, final int rank )
        {
            objs = new Object[] { element };
            uids = new long[] { rank2uid( rank, 0 ) };
            uniq = 1;
        }

        Content( final Object[] objs, final long[] uids, final int uniq ) // NOPMD
        {
            this.objs = objs;
            this.uids = uids;
            this.uniq = uniq;
        }

        // ----------------------------------------------------------------------
        // Public methods
        // ----------------------------------------------------------------------

        public int indexOf( final Object element )
        {
            if ( null == element )
            {
                return indexOfThis( null );
            }
            for ( int i = 0; i < objs.length; i++ )
            {
                if ( element.equals( objs[i] ) )
                {
                    return i;
                }
            }
            return -1;
        }

        public int indexOfThis( final Object element )
        {
            for ( int i = 0; i < objs.length; i++ )
            {
                if ( element == objs[i] )
                {
                    return i;
                }
            }
            return -1;
        }

        public Content insert( final Object element, final int rank )
        {
            final int size = objs.length + 1;

            final Object[] newObjs = new Object[size];
            final long[] newUIDs = new long[size];

            final long uid = rank2uid( rank, uniq );
            final int index = safeBinarySearch( uids, uid );
            if ( index > 0 )
            {
                System.arraycopy( objs, 0, newObjs, 0, index );
                System.arraycopy( uids, 0, newUIDs, 0, index );
            }

            newObjs[index] = element;
            newUIDs[index] = uid;

            final int destPos = index + 1, len = size - destPos;
            if ( len > 0 )
            {
                System.arraycopy( objs, index, newObjs, destPos, len );
                System.arraycopy( uids, index, newUIDs, destPos, len );
            }

            return new Content( newObjs, newUIDs, uniq + 1 );
        }

        public Content remove( final int index )
        {
            if ( objs.length == 1 )
            {
                return null;
            }

            final int size = objs.length - 1;

            final Object[] newObjs = new Object[size];
            final long[] newUIDs = new long[size];

            if ( index > 0 )
            {
                System.arraycopy( objs, 0, newObjs, 0, index );
                System.arraycopy( uids, 0, newUIDs, 0, index );
            }
            final int srcPos = index + 1, len = size - index;
            if ( len > 0 )
            {
                System.arraycopy( objs, srcPos, newObjs, index, len );
                System.arraycopy( uids, srcPos, newUIDs, index, len );
            }

            return new Content( newObjs, newUIDs, uniq );
        }
    }

    /**
     * Custom {@link Iterator} that copes with modification by repositioning itself in the updated list.
     */
    final class Itr
        implements Iterator<T>
    {
        // ----------------------------------------------------------------------
        // Implementation fields
        // ----------------------------------------------------------------------

        private Content content;

        private T nextObj;

        private long nextUID = Long.MIN_VALUE;

        private int index = -1;

        // ----------------------------------------------------------------------
        // Public methods
        // ----------------------------------------------------------------------

        @SuppressWarnings( "unchecked" )
        public boolean hasNext()
        {
            if ( null != nextObj )
            {
                return true;
            }
            final Content newContent = get();
            if ( content != newContent )
            {
                index = null != newContent ? safeBinarySearch( newContent.uids, nextUID ) : -1;
                content = newContent;
            }
            if ( index >= 0 && index < content.objs.length )
            {
                nextObj = (T) content.objs[index];
                nextUID = content.uids[index];
                return true;
            }
            return false;
        }

        /**
         * @return {@code true} if the next element is ranked at or above the given rank; otherwise {@code false}
         */
        public boolean hasNext( final int rank )
        {
            if ( null != nextObj )
            {
                return uid2rank( nextUID ) >= rank;
            }
            final Content newContent = get();
            if ( content != newContent )
            {
                index = null != newContent ? safeBinarySearch( newContent.uids, nextUID ) : -1;
                content = newContent;
            }
            if ( index >= 0 && index < content.uids.length )
            {
                return uid2rank( content.uids[index] ) >= rank;
            }
            return false;
        }

        public T next()
        {
            if ( hasNext() )
            {
                nextUID++; // guarantees progress when re-positioning
                index++;

                // populated by hasNext()
                final T element = nextObj;
                nextObj = null;
                return element;
            }
            throw new NoSuchElementException();
        }

        public int rank()
        {
            return uid2rank( nextUID );
        }

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