# Iterables.java

    /*
     * Copyright (c) 2010, Rickard Öberg. 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.
     * 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.qi4j.functional;

    import java.lang.reflect.Array;
    import java.text.MessageFormat;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.Enumeration;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.List;
    import java.util.NoSuchElementException;
    import java.util.Set;

    /**
     * Utility methods for working with Iterables. See test for examples of how to use.
     */
    public final class Iterables
    {
        @SuppressWarnings( "raw" )
        private static final Iterable EMPTY = new Iterable()
        {
            Iterator iterator = new Iterator()
            {
                @Override
                public boolean hasNext()
                {
                    return false;
                }

                @Override
                public Object next()
                {
                    throw new NoSuchElementException();
                }

                @Override
                public void remove()
                {
                }
            };

            @Override
            public Iterator iterator()
            {
                return iterator;
            }
        };

        @SuppressWarnings( "unchecked" )
        public static <T> Iterable<T> empty()
        {
            return EMPTY;
        }

        public static <T> Iterable<T> constant( final T item )
        {
            return new Iterable<T>()
            {
                @Override
                public Iterator<T> iterator()
                {
                    return new Iterator<T>()
                    {
                        @Override
                        public boolean hasNext()
                        {
                            return true;
                        }

                        @Override
                        public T next()
                        {
                            return item;
                        }

                        @Override
                        public void remove()
                        {
                        }
                    };
                }
            };
        }

        public static <T> Iterable<T> limit( final int limitItems, final Iterable<T> iterable )
        {
            return new Iterable<T>()
            {
                @Override
                public Iterator<T> iterator()
                {
                    final Iterator<T> iterator = iterable.iterator();

                    return new Iterator<T>()
                    {
                        int count;

                        @Override
                        public boolean hasNext()
                        {
                            return count < limitItems && iterator.hasNext();
                        }

                        @Override
                        public T next()
                        {
                            count++;
                            return iterator.next();
                        }

                        @Override
                        public void remove()
                        {
                            iterator.remove();
                        }
                    };
                }
            };
        }

        public static <T> Iterable<T> unique( final Iterable<T> iterable )
        {
            return new Iterable<T>()
            {
                @Override
                public Iterator<T> iterator()
                {
                    final Iterator<T> iterator = iterable.iterator();

                    return new Iterator<T>()
                    {
                        private final Set<T> items = new HashSet<>();
                        private T nextItem;

                        @Override
                        public boolean hasNext()
                        {
                            while( iterator.hasNext() )
                            {
                                nextItem = iterator.next();
                                if( items.add( nextItem ) )
                                {
                                    return true;
                                }
                            }

                            return false;
                        }

                        @Override
                        public T next()
                        {
                            if( nextItem == null && !hasNext() )
                            {
                                throw new NoSuchElementException();
                            }

                            return nextItem;
                        }

                        @Override
                        public void remove()
                        {
                        }
                    };
                }
            };
        }

        public static <T, C extends Collection<T>> C addAll( C collection, Iterable<? extends T> iterable )
        {
            for( T item : iterable )
            {
                collection.add( item );
            }
            return collection;
        }

        public static long count( Iterable<?> iterable )
        {
            long c = 0;
            for( Object anIterable : iterable )
            {
                c++;
            }
            return c;
        }

        @SuppressWarnings( "unchecked" )
        public static <X> Iterable<X> filter( Specification<? /* super X*/> specification, Iterable<X> i )
        {
            return new FilterIterable<>( i, (Specification<? super X>) specification );
        }

        public static <X> X first( Iterable<X> i )
        {
            Iterator<X> iter = i.iterator();
            if( iter.hasNext() )
            {
                return iter.next();
            }
            else
            {
                return null;
            }
        }

        public static <X> X single( Iterable<X> i )
        {
            Iterator<X> iter = i.iterator();
            if( iter.hasNext() )
            {
                X result = iter.next();

                if( iter.hasNext() )
                {
                    throw new IllegalArgumentException( "More than one element in iterable" );
                }

                return result;
            }
            else
            {
                throw new IllegalArgumentException( "No elements in iterable" );
            }
        }

        public static <X> Iterable<X> skip( final int skip, final Iterable<X> iterable )
        {
            return new Iterable<X>()
            {
                @Override
                public Iterator<X> iterator()
                {
                    Iterator<X> iterator = iterable.iterator();

                    for( int i = 0; i < skip; i++ )
                    {
                        if( iterator.hasNext() )
                        {
                            iterator.next();
                        }
                        else
                        {
                            return Iterables.<X>empty().iterator();
                        }
                    }

                    return iterator;
                }
            };
        }

        public static <X> X last( Iterable<X> i )
        {
            Iterator<X> iter = i.iterator();
            X item = null;
            while( iter.hasNext() )
            {
                item = iter.next();
            }

            return item;
        }

        public static <X> Iterable<X> reverse( Iterable<X> iterable )
        {
            List<X> list = toList( iterable );
            Collections.reverse( list );
            return list;
        }

        public static <T> boolean matchesAny( Specification<? super T> specification, Iterable<T> iterable )
        {
            boolean result = false;

            for( T item : iterable )
            {
                if( ( (Specification<? super T>) specification ).satisfiedBy( item ) )
                {
                    result = true;
                    break;
                }
            }

            return result;
        }

        public static <T> boolean matchesAll( Specification<? super T> specification, Iterable<T> iterable )
        {
            boolean result = true;
            for( T item : iterable )
            {
                if( !specification.satisfiedBy( item ) )
                {
                    result = false;
                }
            }

            return result;
        }

        public static <X> Iterable<X> flatten( Iterable<?>... multiIterator )
        {
            return new FlattenIterable<>( Iterables.<Iterable<X>>cast( Arrays.asList( multiIterator ) ) );
        }

        public static <X, I extends Iterable<? extends X>> Iterable<X> flattenIterables( Iterable<I> multiIterator )
        // public static <X> Iterable<X> flattenIterables( Iterable<Iterable<?>> multiIterator )
        {
            return new FlattenIterable<>( Iterables.<Iterable<X>>cast( multiIterator ) );
        }

        @SafeVarargs
        public static <T> Iterable<T> mix( final Iterable<T>... iterables )
        {
            return new Iterable<T>()
            {
                @Override
                public Iterator<T> iterator()
                {
                    final Iterable<Iterator<T>> iterators = toList( map( new Function<Iterable<T>, Iterator<T>>()
                    {
                        @Override
                        public Iterator<T> map( Iterable<T> iterable )
                        {
                            return iterable.iterator();
                        }
                    }, Iterables.iterable( iterables ) ) );

                    return new Iterator<T>()
                    {
                        Iterator<Iterator<T>> iterator;

                        Iterator<T> iter;

                        @Override
                        public boolean hasNext()
                        {
                            for( Iterator<T> iterator : iterators )
                            {
                                if( iterator.hasNext() )
                                {
                                    return true;
                                }
                            }

                            return false;
                        }

                        @Override
                        public T next()
                        {
                            if( iterator == null )
                            {
                                iterator = iterators.iterator();
                            }

                            while( iterator.hasNext() )
                            {
                                iter = iterator.next();

                                if( iter.hasNext() )
                                {
                                    return iter.next();
                                }
                            }

                            iterator = null;

                            return next();
                        }

                        @Override
                        public void remove()
                        {
                            if( iter != null )
                            {
                                iter.remove();
                            }
                        }
                    };
                }
            };
        }

        @SuppressWarnings( "unchecked" )
        public static <FROM, TO> Iterable<TO> map( Function<? /* super FROM */, TO> function, Iterable<FROM> from )
        {
            return new MapIterable<>( from, (Function<FROM, TO>) function );
        }

        public static <T> Iterable<T> iterable( Enumeration<T> enumeration )
        {
            List<T> list = new ArrayList<>();
            while( enumeration.hasMoreElements() )
            {
                T item = enumeration.nextElement();
                list.add( item );
            }

            return list;
        }

        @SafeVarargs
        public static <T> Iterable<T> iterable( T... items )
        {
            return Arrays.asList( items );
        }

        @SuppressWarnings( {"raw", "unchecked"} )
        public static <T> Iterable<T> cast( Iterable<?> iterable )
        {
            Iterable iter = iterable;
            return iter;
        }

        public static <FROM, TO> Function<FROM, TO> cast()
        {
            return new Function<FROM, TO>()
            {
                @Override
                @SuppressWarnings( "unchecked" )
                public TO map( FROM from )
                {
                    return (TO) from;
                }
            };
        }

        public static <FROM, TO> TO fold( Function<? super FROM, TO> function, Iterable<? extends FROM> i )
        {
            return last( map( function, i ) );
        }

        public static <T> Iterable<T> prepend( final T item, final Iterable<T> iterable )
        {
            return new Iterable<T>()
            {
                @Override
                public Iterator<T> iterator()
                {
                    return new Iterator<T>()
                    {
                        T first = item;
                        Iterator<T> iterator;

                        @Override
                        public boolean hasNext()
                        {
                            if( first != null )
                            {
                                return true;
                            }
                            else
                            {
                                if( iterator == null )
                                {
                                    iterator = iterable.iterator();
                                }
                            }

                            return iterator.hasNext();
                        }

                        @Override
                        public T next()
                        {
                            if( first != null )
                            {
                                try
                                {
                                    return first;
                                }
                                finally
                                {
                                    first = null;
                                }
                            }
                            else
                            {
                                return iterator.next();
                            }
                        }

                        @Override
                        public void remove()
                        {
                        }
                    };
                }
            };
        }

        public static <T> Iterable<T> append( final T item, final Iterable<T> iterable )
        {
            return new Iterable<T>()
            {
                @Override
                public Iterator<T> iterator()
                {
                    final Iterator<T> iterator = iterable.iterator();

                    return new Iterator<T>()
                    {
                        T last = item;

                        @Override
                        public boolean hasNext()
                        {
                            if( iterator.hasNext() )
                            {
                                return true;
                            }
                            else
                            {
                                return last != null;
                            }
                        }

                        @Override
                        public T next()
                        {
                            if( iterator.hasNext() )
                            {
                                return iterator.next();
                            }
                            else
                            {
                                try
                                {
                                    return last;
                                }
                                finally
                                {
                                    last = null;
                                }
                            }
                        }

                        @Override
                        public void remove()
                        {
                        }
                    };
                }
            };
        }

        @SafeVarargs
        public static <T> Iterable<T> debug( String format,
                                             final Iterable<T> iterable,
                                             final Function<T, String>... functions
        )
        {
            final MessageFormat msgFormat = new MessageFormat( format );

            return map( new Function<T, T>()
            {
                @Override
                public T map( T t )
                {
                    if( functions.length != 0 )
                    {
                        String[] mapped = new String[ functions.length ];
                        for( int i = 0; i < functions.length; i++ )
                        {
                            Function<T, String> function = functions[i];
                            mapped[i] = function.map( t );
                        }
                    }
                    return t;
                }
            }, iterable );
        }

        public static <T> Iterable<T> cache( Iterable<T> iterable )
        {
            return new CacheIterable<>( iterable );
        }

        public static <T> String toString( Iterable<T> iterable )
        {
            return toString( iterable, new Function<T, String>()
            {
                @Override
                public String map( T t )
                {
                    return t == null ? "[null]" : t.toString();
                }
            }, "," );
        }

        public static <T> String toString( Iterable<T> iterable, Function<T, String> toStringFunction, String separator )
        {
            StringBuilder builder = new StringBuilder();
            boolean first = true;
            for( T item : iterable )
            {
                if( !first )
                {
                    builder.append( separator );
                }
                builder.append( toStringFunction.map( item ) );
                first = false;
            }
            return builder.toString();
        }

        public static <T> List<T> toList( Iterable<T> iterable )
        {
            return addAll( new ArrayList<T>(), iterable );
        }

        public static Object[] toArray( Iterable<Object> iterable )
        {
            return toArray( Object.class, iterable );
        }

        @SuppressWarnings( "unchecked" )
        public static <T> T[] toArray( Class<T> componentType, Iterable<T> iterable )
        {
            if( iterable == null )
            {
                return null;
            }
            List<T> list = toList( iterable );
            return list.toArray( (T[]) Array.newInstance( componentType, list.size() ) );
        }

        @SuppressWarnings( {"raw", "unchecked"} )
        public static <X extends Comparable> Iterable<X> sort( Iterable<X> iterable )
        {
            List<X> list = toList( iterable );
            Collections.sort( list );
            return list;
        }

        public static <X> Iterable<X> sort( Comparator<? super X> comparator, Iterable<X> iterable )
        {
            List<X> list = toList( iterable );
            Collections.sort( list, comparator );
            return list;
        }

        private static class MapIterable<FROM, TO>
            implements Iterable<TO>
        {
            private final Iterable<FROM> from;
            private final Function<? super FROM, TO> function;

            private MapIterable( Iterable<FROM> from, Function<? super FROM, TO> function )
            {
                this.from = from;
                this.function = function;
            }

            @Override
            public Iterator<TO> iterator()
            {
                return new MapIterator<>( from.iterator(), function );
            }

            static class MapIterator<FROM, TO>
                implements Iterator<TO>
            {
                private final Iterator<FROM> fromIterator;
                private final Function<? super FROM, TO> function;

                private MapIterator( Iterator<FROM> fromIterator, Function<? super FROM, TO> function )
                {
                    this.fromIterator = fromIterator;
                    this.function = function;
                }

                @Override
                public boolean hasNext()
                {
                    return fromIterator.hasNext();
                }

                @Override
                public TO next()
                {
                    FROM from = fromIterator.next();
                    return function.map( from );
                }

                @Override
                public void remove()
                {
                    fromIterator.remove();
                }
            }

        }

        private static class FilterIterable<T>
            implements Iterable<T>
        {
            private final Iterable<T> iterable;

            private final Specification<? super T> specification;

            private FilterIterable( Iterable<T> iterable, Specification<? super T> specification )
            {
                this.iterable = iterable;
                this.specification = specification;
            }

            @Override
            public Iterator<T> iterator()
            {
                return new FilterIterator<>( iterable.iterator(), specification );
            }

            private static class FilterIterator<T>
                implements Iterator<T>
            {
                private final Iterator<T> iterator;

                private final Specification<? super T> specification;

                private T currentValue;
                boolean finished = false;
                boolean nextConsumed = true;

                private FilterIterator( Iterator<T> iterator, Specification<? super T> specification )
                {
                    this.specification = specification;
                    this.iterator = iterator;
                }

                public boolean moveToNextValid()
                {
                    boolean found = false;
                    while( !found && iterator.hasNext() )
                    {
                        T currentValue = iterator.next();
                        boolean satisfies = specification.satisfiedBy( currentValue );

                        if( satisfies )
                        {
                            found = true;
                            this.currentValue = currentValue;
                            nextConsumed = false;
                        }
                    }
                    if( !found )
                    {
                        finished = true;
                    }
                    return found;
                }

                @Override
                public T next()
                {
                    if( !nextConsumed )
                    {
                        nextConsumed = true;
                        return currentValue;
                    }
                    else
                    {
                        if( !finished )
                        {
                            if( moveToNextValid() )
                            {
                                nextConsumed = true;
                                return currentValue;
                            }
                        }
                    }
                    return null;
                }

                @Override
                public boolean hasNext()
                {
                    return !finished
                           && ( !nextConsumed || moveToNextValid() );
                }

                @Override
                public void remove()
                {
                }
            }

        }

        private static class FlattenIterable<T, I extends Iterable<? extends T>>
            implements Iterable<T>
        {
            private final Iterable<I> iterable;

            private FlattenIterable( Iterable<I> iterable )
            {
                this.iterable = iterable;
            }

            @Override
            public Iterator<T> iterator()
            {
                return new FlattenIterator<>( iterable.iterator() );
            }

            static class FlattenIterator<T, I extends Iterable<? extends T>>
                implements Iterator<T>
            {
                private final Iterator<I> iterator;
                private Iterator<? extends T> currentIterator;

                private FlattenIterator( Iterator<I> iterator )
                {
                    this.iterator = iterator;
                    currentIterator = null;
                }

                @Override
                public boolean hasNext()
                {
                    if( currentIterator == null )
                    {
                        if( iterator.hasNext() )
                        {
                            I next = iterator.next();
                            currentIterator = next.iterator();
                        }
                        else
                        {
                            return false;
                        }
                    }

                    while( !currentIterator.hasNext()
                           && iterator.hasNext() )
                    {
                        currentIterator = iterator.next().iterator();
                    }

                    return currentIterator.hasNext();
                }

                @Override
                public T next()
                {
                    return currentIterator.next();
                }

                @Override
                public void remove()
                {
                    if( currentIterator == null )
                    {
                        throw new IllegalStateException();
                    }

                    currentIterator.remove();
                }
            }

        }

        private static class CacheIterable<T>
            implements Iterable<T>
        {
            private final Iterable<T> iterable;
            private Iterable<T> cache;

            private CacheIterable( Iterable<T> iterable )
            {
                this.iterable = iterable;
            }

            @Override
            public Iterator<T> iterator()
            {
                if( cache != null )
                {
                    return cache.iterator();
                }

                final Iterator<T> source = iterable.iterator();

                return new Iterator<T>()
                {
                    List<T> iteratorCache = new ArrayList<>();

                    @Override
                    public boolean hasNext()
                    {
                        boolean hasNext = source.hasNext();
                        if( !hasNext )
                        {
                            cache = iteratorCache;
                        }
                        return hasNext;
                    }

                    @Override
                    public T next()
                    {
                        T next = source.next();
                        iteratorCache.add( next );
                        return next;
                    }

                    @Override
                    public void remove()
                    {

                    }
                };
            }
        }

        private Iterables()
        {
        }

    }