/*
 *  Copyright 2012 Anyware Services
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License 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 org.ametys.plugins.repository;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.stream.Collectors;


/**
 * Implementation of a {@link AmetysObjectIterable} based on a list of others {@link AmetysObjectIterable},
 * which returns the objects in a given order, removing duplicates.
 * Each iterable must be sorted.
 * The "collating" part is copied and adapted from Apache Commons Lang's CollatingIterator class. 
 * @param <A> the actual type of {@link AmetysObject}s.
 */
public class CollatingUniqueAmetysObjectIterable<A extends AmetysObject> implements AmetysObjectIterable<A>
{
    /** The {@link Comparator} used to evaluate order. */
    Comparator<A> _comparator;

    /** The list of iterables. */
    private List<AmetysObjectIterable<A>> _iterables;
    
    /**
     * Creates a {@link CollatingUniqueAmetysObjectIterable}.
     * @param iterables a list of {@link AmetysObjectIterable}.
     * @param comparator a comparator.
     */
    public CollatingUniqueAmetysObjectIterable(List<AmetysObjectIterable<A>> iterables, Comparator<A> comparator)
    {
        _iterables = iterables;
        _comparator = comparator;
    }
    
    /**
     * Returns the number of elements only if there is only one {@link AmetysObjectIterable} in the list.
     * If there is more than 1 {@link AmetysObjectIterable}, this always returns -1.
     * @return The size of the unique iterable or -1 if there is more than 1 iterable.
     */
    @Override
    public long getSize()
    {
        if (_iterables.size() == 1)
        {
            return _iterables.get(0).getSize();
        }
        
        // Unable to determine the exact size.
        return _iterables.size() == 0 ? 0 : -1;
    }
    
    @Override
    public AmetysObjectIterator<A> iterator()
    {
        List<AmetysObjectIterator<A>> its = _iterables.stream().map(it -> it.iterator()).collect(Collectors.toList());
        return new CollatingIterator(its, getSize());
    }
    
    @Override
    public void close()
    {
        for (AmetysObjectIterable<A> it : _iterables)
        {
            it.close();
        }
    }
    
    class CollatingIterator implements AmetysObjectIterator<A>
    {
        /** The current position in the iterator. */
        private long _position;
        
        /** {@link Iterator#next Next} objects peeked from each iterator. */
        private ArrayList<A> _nextObjects;
        
        /** Whether or not each object has been prefetched. */
        private BitSet _nextObjectSet;
        
        /** The already resolved identifiers. */
        private Set<String> _identifiers = new HashSet<>();
        
        /** The iterable count. */
        private int _itCount;
        
        private List<AmetysObjectIterator<A>> _its;
        private long _size;
        
        public CollatingIterator(List<AmetysObjectIterator<A>> its, long size)
        {
            _its = its;
            _size = size;
        }

        @Override
        public long getPosition()
        {
            return _position;
        }
        
        public long getSize()
        {
            return _size;
        }
        
        @Override
        public boolean hasNext()
        {
            _initialize();
            boolean hasNext = false;
            
            // Prefetch the next object for each iterable.
            for (int i = 0; i < _itCount && !hasNext; i++)
            {
                if (_nextObjectSet.get(i))
                {
                    // An object is already prefetched for this iterable.
                    hasNext = true;
                }
                else
                {
                    // Prefetch the next object.
                    hasNext = _setNextObject(i);
                }
            }
            
            return hasNext;
        }
        
        @Override
        public A next() throws NoSuchElementException
        {
            if (!hasNext())
            {
                throw new NoSuchElementException();
            }
            int leastIndex = _least();
            if (leastIndex == -1)
            {
                throw new NoSuchElementException();
            }
            else
            {
                _position++;
                // Get the object and clear the 'set' bit for the iterator. 
                A object = _nextObjects.get(leastIndex);
                _clear(leastIndex);
                return object;
            }
        }


        /** 
         * Initializes the collating state if it hasn't been already.
         */
        private void _initialize()
        {
            if (_nextObjects == null)
            {
                _itCount = _its.size();
                _nextObjects = new ArrayList<>(_itCount);
                _nextObjectSet = new BitSet(_itCount);
                for (int i = 0; i < _itCount; i++)
                {
                    _nextObjects.add(null);
                    _nextObjectSet.clear(i);
                }
            }
        }
        
        /** 
         * Sets the {@link #_nextObjects} and {@link #_nextObjectSet} attributes 
         * at position <i>i</i> to the next value of the 
         * {@link #_iterables iterator} at position <i>i</i>, or 
         * clear them if the <i>i</i><sup>th</sup> iterator
         * has no next value.
         *
         * @param iterableIndex The index to get in _iterables
         * @return <tt>false</tt> if there was no value to set
         */
        private boolean _setNextObject(int iterableIndex)
        {
            AmetysObjectIterator<A> it = _its.get(iterableIndex);
            while (it.hasNext())
            {
                A object = it.next();
                // Will return true if the object did not exist.
                if (_identifiers.add(object.getId()))
                {
                    _nextObjects.set(iterableIndex, object);
                    _nextObjectSet.set(iterableIndex);
                    return true;
                }
            }
            
            // No more element.
            _nextObjects.set(iterableIndex, null);
            _nextObjectSet.clear(iterableIndex);
            return false;
        }
        
        /** 
         * Clears the {@link #_nextObjects} and {@link #_nextObjectSet} attributes 
         * at position <i>i</i>.
         * @param iterableIndex The index to clear in _iterables
         */
        private void _clear(int iterableIndex)
        {
            _nextObjects.set(iterableIndex, null);
            _nextObjectSet.clear(iterableIndex);
        }
        
        /** 
         * Returns the index of the least element in {@link #_nextObjects},
         * {@link #_setNextObject(int) setting} any uninitialized values.
         * @throws IllegalStateException if an error occurred
         * @return the index of the least element
         */
        private int _least()
        {
            int leastIndex = -1;
            A leastObject = null;
            
            for (int i = 0; i < _itCount; i++)
            {
                // Set the next object value and 'set' bit for the iterable.
                if (!_nextObjectSet.get(i))
                {
                    _setNextObject(i);
                }
                // A next object is present in the iterable.
                if (_nextObjectSet.get(i))
                {
                    // First object found: store it.
                    if (leastIndex == -1)
                    {
                        leastIndex = i;
                        leastObject = _nextObjects.get(i);
                    }
                    else
                    {
                        // New object found: store it only if "lesser" than the previous stored one.
                        A curObject = _nextObjects.get(i);
                        if (_comparator.compare(curObject, leastObject) < 0)
                        {
                            leastObject = curObject;
                            leastIndex = i;
                        }
                    }
                }
            }
            
            return leastIndex;
        }
    }
}