001/*
002 *  Copyright 2012 Anyware Services
003 *
004 *  Licensed under the Apache License, Version 2.0 (the "License");
005 *  you may not use this file except in compliance with the License.
006 *  You may obtain a copy of the License at
007 *
008 *      http://www.apache.org/licenses/LICENSE-2.0
009 *
010 *  Unless required by applicable law or agreed to in writing, software
011 *  distributed under the License is distributed on an "AS IS" BASIS,
012 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 *  See the License for the specific language governing permissions and
014 *  limitations under the License.
015 */
016package org.ametys.plugins.repository;
017
018import java.util.ArrayList;
019import java.util.BitSet;
020import java.util.Comparator;
021import java.util.HashSet;
022import java.util.Iterator;
023import java.util.List;
024import java.util.NoSuchElementException;
025import java.util.Set;
026import java.util.stream.Collectors;
027
028
029/**
030 * Implementation of a {@link AmetysObjectIterable} based on a list of others {@link AmetysObjectIterable},
031 * which returns the objects in a given order, removing duplicates.
032 * Each iterable must be sorted.
033 * The "collating" part is copied and adapted from Apache Commons Lang's CollatingIterator class. 
034 * @param <A> the actual type of {@link AmetysObject}s.
035 */
036public class CollatingUniqueAmetysObjectIterable<A extends AmetysObject> implements AmetysObjectIterable<A>
037{
038    /** The {@link Comparator} used to evaluate order. */
039    Comparator<A> _comparator;
040
041    /** The list of iterables. */
042    private List<AmetysObjectIterable<A>> _iterables;
043    
044    /**
045     * Creates a {@link CollatingUniqueAmetysObjectIterable}.
046     * @param iterables a list of {@link AmetysObjectIterable}.
047     * @param comparator a comparator.
048     */
049    public CollatingUniqueAmetysObjectIterable(List<AmetysObjectIterable<A>> iterables, Comparator<A> comparator)
050    {
051        _iterables = iterables;
052        _comparator = comparator;
053    }
054    
055    /**
056     * Returns the number of elements only if there is only one {@link AmetysObjectIterable} in the list.
057     * If there is more than 1 {@link AmetysObjectIterable}, this always returns -1.
058     * @return The size of the unique iterable or -1 if there is more than 1 iterable.
059     */
060    @Override
061    public long getSize()
062    {
063        if (_iterables.size() == 1)
064        {
065            return _iterables.get(0).getSize();
066        }
067        
068        // Unable to determine the exact size.
069        return _iterables.size() == 0 ? 0 : -1;
070    }
071    
072    @Override
073    public AmetysObjectIterator<A> iterator()
074    {
075        List<AmetysObjectIterator<A>> its = _iterables.stream().map(it -> it.iterator()).collect(Collectors.toList());
076        return new CollatingIterator(its, getSize());
077    }
078    
079    @Override
080    public void close()
081    {
082        for (AmetysObjectIterable<A> it : _iterables)
083        {
084            it.close();
085        }
086    }
087    
088    class CollatingIterator implements AmetysObjectIterator<A>
089    {
090        /** The current position in the iterator. */
091        private long _position;
092        
093        /** {@link Iterator#next Next} objects peeked from each iterator. */
094        private ArrayList<A> _nextObjects;
095        
096        /** Whether or not each object has been prefetched. */
097        private BitSet _nextObjectSet;
098        
099        /** The already resolved identifiers. */
100        private Set<String> _identifiers = new HashSet<>();
101        
102        /** The iterable count. */
103        private int _itCount;
104        
105        private List<AmetysObjectIterator<A>> _its;
106        private long _size;
107        
108        public CollatingIterator(List<AmetysObjectIterator<A>> its, long size)
109        {
110            _its = its;
111            _size = size;
112        }
113
114        @Override
115        public long getPosition()
116        {
117            return _position;
118        }
119        
120        public long getSize()
121        {
122            return _size;
123        }
124        
125        @Override
126        public boolean hasNext()
127        {
128            _initialize();
129            boolean hasNext = false;
130            
131            // Prefetch the next object for each iterable.
132            for (int i = 0; i < _itCount && !hasNext; i++)
133            {
134                if (_nextObjectSet.get(i))
135                {
136                    // An object is already prefetched for this iterable.
137                    hasNext = true;
138                }
139                else
140                {
141                    // Prefetch the next object.
142                    hasNext = _setNextObject(i);
143                }
144            }
145            
146            return hasNext;
147        }
148        
149        @Override
150        public A next() throws NoSuchElementException
151        {
152            if (!hasNext())
153            {
154                throw new NoSuchElementException();
155            }
156            int leastIndex = _least();
157            if (leastIndex == -1)
158            {
159                throw new NoSuchElementException();
160            }
161            else
162            {
163                _position++;
164                // Get the object and clear the 'set' bit for the iterator. 
165                A object = _nextObjects.get(leastIndex);
166                _clear(leastIndex);
167                return object;
168            }
169        }
170
171
172        /** 
173         * Initializes the collating state if it hasn't been already.
174         */
175        private void _initialize()
176        {
177            if (_nextObjects == null)
178            {
179                _itCount = _its.size();
180                _nextObjects = new ArrayList<>(_itCount);
181                _nextObjectSet = new BitSet(_itCount);
182                for (int i = 0; i < _itCount; i++)
183                {
184                    _nextObjects.add(null);
185                    _nextObjectSet.clear(i);
186                }
187            }
188        }
189        
190        /** 
191         * Sets the {@link #_nextObjects} and {@link #_nextObjectSet} attributes 
192         * at position <i>i</i> to the next value of the 
193         * {@link #_iterables iterator} at position <i>i</i>, or 
194         * clear them if the <i>i</i><sup>th</sup> iterator
195         * has no next value.
196         *
197         * @param iterableIndex The index to get in _iterables
198         * @return <code>false</code> if there was no value to set
199         */
200        private boolean _setNextObject(int iterableIndex)
201        {
202            AmetysObjectIterator<A> it = _its.get(iterableIndex);
203            while (it.hasNext())
204            {
205                A object = it.next();
206                // Will return true if the object did not exist.
207                if (_identifiers.add(object.getId()))
208                {
209                    _nextObjects.set(iterableIndex, object);
210                    _nextObjectSet.set(iterableIndex);
211                    return true;
212                }
213            }
214            
215            // No more element.
216            _nextObjects.set(iterableIndex, null);
217            _nextObjectSet.clear(iterableIndex);
218            return false;
219        }
220        
221        /** 
222         * Clears the {@link #_nextObjects} and {@link #_nextObjectSet} attributes 
223         * at position <i>i</i>.
224         * @param iterableIndex The index to clear in _iterables
225         */
226        private void _clear(int iterableIndex)
227        {
228            _nextObjects.set(iterableIndex, null);
229            _nextObjectSet.clear(iterableIndex);
230        }
231        
232        /** 
233         * Returns the index of the least element in {@link #_nextObjects},
234         * {@link #_setNextObject(int) setting} any uninitialized values.
235         * @throws IllegalStateException if an error occurred
236         * @return the index of the least element
237         */
238        private int _least()
239        {
240            int leastIndex = -1;
241            A leastObject = null;
242            
243            for (int i = 0; i < _itCount; i++)
244            {
245                // Set the next object value and 'set' bit for the iterable.
246                if (!_nextObjectSet.get(i))
247                {
248                    _setNextObject(i);
249                }
250                // A next object is present in the iterable.
251                if (_nextObjectSet.get(i))
252                {
253                    // First object found: store it.
254                    if (leastIndex == -1)
255                    {
256                        leastIndex = i;
257                        leastObject = _nextObjects.get(i);
258                    }
259                    else
260                    {
261                        // New object found: store it only if "lesser" than the previous stored one.
262                        A curObject = _nextObjects.get(i);
263                        if (_comparator.compare(curObject, leastObject) < 0)
264                        {
265                            leastObject = curObject;
266                            leastIndex = i;
267                        }
268                    }
269                }
270            }
271            
272            return leastIndex;
273        }
274    }
275}