/*
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */

package net.ranides.assira.collection.lists;

import java.io.Serializable;
import java.util.*;
import java.util.function.BiPredicate;
import java.util.function.Function;
import java.util.function.IntFunction;
import java.util.function.Predicate;
import java.util.stream.Collectors;

import lombok.experimental.UtilityClass;
import net.ranides.assira.collection.CollectionUtils;
import net.ranides.assira.collection.Swapper;
import net.ranides.assira.collection.arrays.NativeArray;
import net.ranides.assira.collection.arrays.NativeArrayAllocator;
import net.ranides.assira.collection.arrays.NativeArraySearch;
import net.ranides.assira.collection.iterators.IteratorUtils;
import net.ranides.assira.collection.iterators.RandomAccessIterator;
import net.ranides.assira.functional.Functions.EachFunction;
import net.ranides.assira.functional.covariant.ProjectionFunction;
import net.ranides.assira.generic.Ref;

/**
 * Static methods working with List interface.
 *
 * @author Ranides Atterwim {@literal <ranides@gmail.com>}
 */
@UtilityClass
public final class ListUtils {

	/**
	 * Returns element at specified index, or none if index is out of boundaries.
	 *
	 * @param values values
	 * @param index index
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> at(List<? extends T> values, int index) {
		if(values.size() <= index) {
			return Ref.empty();
		}
		return Ref.of(values.get(index));
	}

	/**
	 * Returns first element inside collection, or none if collection is empty.
	 *
	 * @param values values
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> first(List<? extends T> values) {
		if(values.isEmpty()) {
			return Ref.empty();
		}
		return Ref.of(values.get(0));
	}

	/**
	 * Returns first element inside collection which satisfies predicate.
	 * Returns none if collection is empty or no element was accepted by predicate.
	 *
	 * @param values values
	 * @param predicate predicate
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> first(List<? extends T> values, Predicate<? super T> predicate) {
		return CollectionUtils.first(values, predicate);
	}

	/**
	 * Returns first element inside collection which satisfies predicate and is located inside specified range.
	 * Returns none if range is outside collection bounds or no element was accepted by predicate.
	 *
	 * @param values values
	 * @param begin begin
	 * @param end end
	 * @param predicate predicate
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> first(List<? extends T> values, int begin, int end, Predicate<? super T> predicate) {
		return first(values.subList(begin, end), predicate);
	}

	/**
	 * Returns last element inside collection, or none if collection is empty.
	 *
	 * @param values values
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> last(List<? extends T> values) {
		if(values.isEmpty()) {
			return Ref.empty();
		}
		return Ref.of(values.get(values.size()-1));
	}

	/**
	 * Returns last element inside collection which satisfies predicate.
	 * Returns none if collection is empty or no element was accepted by predicate.
	 *
	 * It minimizes number of operations by using backward iterator.
	 *
	 * @param values values
	 * @param predicate predicate
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> last(List<? extends T> values, Predicate<? super T> predicate) {
		ListIterator<? extends T> iterator = values.listIterator(values.size());

        while(iterator.hasPrevious()) {
            T v = iterator.previous();
            if( predicate.test(v)) {
                return Ref.of(v);
            }
        }
        return Ref.empty();
	}

	/**
	 * Returns last element inside collection which satisfies predicate and is located inside specified range.
	 * Returns none if range is outside collection bounds or no element was accepted by predicate.
	 *
	 * It minimizes number of operations by using backward iterator.
	 *
	 * @param values values
	 * @param begin begin
	 * @param end end
	 * @param predicate predicate
	 * @param <T> T
	 * @return optional
	 */
	public static <T> Ref<T> last(List<? extends T> values, int begin, int end, Predicate<? super T> predicate) {
		return last(values.subList(begin, end), predicate);
	}

	/**
	 * Returns new list filtered by predicate.
	 * Returned list is a copy, not a view.
	 *
	 * @param values values
	 * @param predicate predicate
	 * @param <T> T
	 * @return new list
	 */
	public static <T> List<T> filter(List<? extends T> values, Predicate<? super T> predicate) {
		return values.stream().filter(predicate).collect(Collectors.toList());
	}

	/**
	 * Returns new list limited by predicate.
	 * Limited list contains only begin of the list until predicate failed.
	 *
	 * @param values values
	 * @param predicate predicate
	 * @param <T> T
	 * @return new list
	 */
    public static <T> List<T> limit(List<? extends T> values, Predicate<? super T> predicate) {
        return IteratorUtils.collect(IteratorUtils.limit(values.iterator(), predicate), new ArrayList<>());
	}

	/**
	 * Returns view which maps every element using provided function.
	 * Changes introduced to source collection are visible in view.
	 *
	 * Returned view supports removing, but not set or add operations.
	 *
	 * @param values values
	 * @param function function
	 * @param <S> source type
	 * @param <T> target type
	 * @return view
	 */
	public static <S,T> List<T> map(List<? extends S> values, Function<? super S,? extends T> function) {
		return new VirtualList<T>() {
			
			private static final long serialVersionUID = 1L;
			
			@Override
			public T get(int index) {
				return function.apply(values.get(index));
			}

			@Override
			public int size() {
				return values.size();
			}
			
			@Override
            public T remove(int index) {
                return function.apply(values.remove(index));
            }
		};
    }

	/**
	 * Returns view which maps every element using provided function.
	 * Changes introduced to source collection are visible in view.
	 *
	 * Returned view supports removing, but not set or add operations.
	 *
	 * @param values values
	 * @param function function
	 * @param <S> source type
	 * @param <T> target type
	 * @return view
	 */
	public static <S,T> List<T> mapEach(List<? extends S> values, EachFunction<? super S,? extends T> function) {
		return new VirtualList<T>() {

			private static final long serialVersionUID = 1L;

			@Override
			public T get(int index) {
				return function.apply(index, values.get(index));
			}

			@Override
			public int size() {
				return values.size();
			}

			@Override
			public T remove(int index) {
				return function.apply(index, values.remove(index));
			}
		};
	}

	/**
	 * Returns mutable view which maps every element using provided projection.
	 * Changes introduced to source collection are visible in view and vice versa.
	 *
	 * Returned view supports all operation: remove, set or add.
	 *
	 * @param values values
	 * @param function function
	 * @param <S> source type
	 * @param <T> target type
	 * @return view
	 */
	public static <S,T> List<T> map(List<S> values, ProjectionFunction<S,T> function) {
        return new VirtualList<T>() {
			@Override
			public T get(int index) {
				return function.apply(values.get(index));
			}

			@Override
			public int size() {
				return values.size();
			}

            @Override
            public T set(int index, T element) {
                S prev = values.set(index, function.invert(element));
                return null==prev ? null : function.apply(prev);
            }

            @Override
            public void add(int index, T element) {
                values.add(index, function.invert(element));
            }

            @Override
            public T remove(int index) {
                return function.apply(values.remove(index));
            }
            
		};
    }

	/**
	 * Returns new virtual list of specified size, which contains elements calculated by "function" at every access.
	 *
	 * Virtual list does not support modifications.
	 *
	 * @param size size
	 * @param function function
	 * @param <T> T
	 * @return virtual
	 */
    public static <T> List<T> produce(int size, IntFunction<? extends T> function) {
		return VirtualList.of(size, function);
    }

	/**
	 * Returns sublist.
	 * Returned view is correctly marked as RandomAccess if source was marked by it.
	 *
	 * @param list list
	 * @param begin begin
	 * @param end end
	 * @param <T> T
	 * @return view
	 */
	public static <T> List<T> sublist(List<T> list, int begin, int end) {
		NativeArrayAllocator.ensureFromTo(list.size(), begin, end);
		if(list instanceof RandomAccess) {
			return new RandomSubList<>(list, begin, end);
		} else {
			return new SubList<>(list, begin, end);
		}
	}

	/**
	 * Checks if provided collections contain equal elements using provided comparison function.
	 * Order of elements is important.
	 *
	 * @param a a
	 * @param b b
	 * @param predicate predicate
	 * @param <T> T
	 * @return bool
	 */
	public static <T> boolean equals(List<? extends T> a, List<? extends T> b, BiPredicate<? super T,? super T> predicate) {
        return (a.size() == b.size()) && IteratorUtils.equals(a.iterator(), b.iterator(), predicate);
    }

	/**
	 * Checks if provided collections contain equal elements using provided comparison function.
	 * Order of elements is important.
	 * It is three-value version, which returns +1, 0, -1
	 *
	 * @param a a
	 * @param b b
	 * @param cmp cmp
	 * @param <T> T
	 * @return int
	 */
	public static <T> int compare(List<? extends T> a, List<? extends T> b, Comparator<? super T> cmp) {
        return IteratorUtils.compare(a.iterator(), b.iterator(), cmp);
    }

	/**
	 * Returns swapper for specified list.
	 *
	 * Swappers can be used for example by sort algorithms or shuffle algorithms to make swaps in efficient way
	 * without knowing if they work on list or on array.
	 *
	 * @param list list
	 * @param <T> T
	 * @return swapper
	 */
    public static <T> Swapper swapper(List<T> list) {
        return (a,b) -> swap(list,a,b);
    }

	/**
	 * Swaps elements inside list.
	 *
	 * @param list list
	 * @param a a
	 * @param b b
	 * @param <T> T
	 */
    public static <T> void swap(List<T> list, int a, int b) {
        T t = list.get(a);
        list.set(a, list.get(b));
        list.set(b, t);
    }

	/**
	 * Binary search operation.
	 * Returns index of "value", or negative index if not found.
	 * Negative index can be used as insertion position: -(index-1)
	 *
	 * List must be sorted in natural order.
	 *
	 * @param list list
	 * @param value value
	 * @param <T> T
	 * @return int
	 */
	public static <T extends Comparable<T>> int binarySearch(List<T> list, T value) {
		return binarySearch(list, 0, list.size(), value);
	}

	/**
	 * Binary search operation inside specified range.
	 * Returns index of "value", or negative index if not found.
	 * Negative index can be used as insertion position: -(index-1)
	 *
	 * Returned index is not "begin-based" but "0-based" and can be used directly for list access.
	 * Of course, if begin or end is reached, returned index is clipped to specified range.
	 *
	 * List must be sorted in natural order.
	 *
	 * @param list list
	 * @param begin begin
	 * @param end end
	 * @param value value
	 * @param <T> T
	 * @return int
	 */
	public static <T extends Comparable<T>> int binarySearch(List<T> list, int begin, int end, T value) {
		NativeArray.NativeComparator ncmp = index -> -value.compareTo(list.get(index));
		return NativeArraySearch.binarySearch(ncmp, begin, end);
	}

	/**
	 * Binary search operation.
	 * Returns index of "value", or negative index if not found.
	 * Negative index can be used as insertion position: -(index-1)
	 *
	 * List must be in order imposed by "cmp".
	 *
	 * @param list list
	 * @param value value
	 * @param cmp cmp
	 * @param <T> T
	 * @return int
	 */
	public static <T> int binarySearch(List<T> list, T value, Comparator<? super T> cmp) {
		return binarySearch(list, 0, list.size(), value, cmp);
	}

	/**
	 * Binary search operation inside specified range.
	 * Returns index of "value", or negative index if not found.
	 * Negative index can be used as insertion position: -(index-1)
	 *
	 * Returned index is not "begin-based" but "0-based" and can be used directly for list access.
	 * Of course, if begin or end is reached, returned index is clipped to specified range.
	 *
	 * List must be in order imposed by "cmp".
	 *
	 * @param list list
	 * @param begin begin
	 * @param end end
	 * @param value value
	 * @param cmp cmp
	 * @param <T> T
	 * @return int
	 */
	public static <T> int binarySearch(List<T> list, int begin, int end, T value, Comparator<? super T> cmp) {
		NativeArray.NativeComparator ncmp = index -> cmp.compare(list.get(index), value);
		return NativeArraySearch.binarySearch(ncmp, begin, end);
	}
	
	private static class RandomSubList<T> extends SubList<T> implements RandomAccess {
		
		public RandomSubList(List<T> list, int begin, int end) {
			super(list, begin, end);
		}

		@Override
		public ListIterator<T> listIterator(int offset) {
			return new RandomAccessIterator<T>(offset){
				@Override
				protected int size() {
					return RandomSubList.this.size();
				}

				@Override
				protected T get(int index) {
					return RandomSubList.this.get(index);
				}

                @Override
                protected void set(int index, T value) {
                    RandomSubList.this.set(index, value);
                }

                @Override
                protected void add(int index, T value) {
                    RandomSubList.this.add(index, value);
                }

                @Override
                protected void remove(int index) {
                    RandomSubList.this.remove(index);
                }
                
                
				
			};
		}
		
	}
	
	private static class SubList<T> extends AbstractList<T> implements Serializable {

        private static final long serialVersionUID = 2;

        protected final List<T> data;
        protected final int begin;
        protected int end;

        public SubList(List<T> list, int begin, int end) {
            this.data = list;
            this.begin = begin;
            this.end = end;
        }

        @Override
        public void add(int index, T value) {
            data.add(begin + index, value);
            end++;
        }

        @Override
        public boolean addAll(int index, Collection<? extends T> values) {
            if( data.addAll(begin + index, values) ) {
				end += values.size();
				return true;
			}
            return false;
        }

        @Override
        public T get(int index) {
            return data.get(begin + index);
        }

        @Override
        public T remove(int index) {
            T prev = data.remove(begin + index);
			end--;
			return prev;
        }

        @Override
        public T set(int index, T value) {
            return data.set(begin + index, value);
        }

        @Override
        public void clear() {
			super.clear();
			end = begin;
        }

        @Override
        public int size() {
            return end - begin;
        }

        @Override
        public ListIterator<T> listIterator(int index) {
            return new SIterator(index);
        }

        @Override
        public List<T> subList(int from, int to) {
			NativeArrayAllocator.ensureFromTo(size(), from, to);
            return new SubList<>(this, from, to);
        }

        protected final class SIterator implements ListIterator<T> {
			
			private final ListIterator<T> delegate;

			public SIterator(int index) {
				this.delegate = data.listIterator(begin + index);
			}

			@Override
			public boolean hasNext() {
				return delegate.nextIndex() < end;
			}

			@Override
			public T next() {
				if(!hasNext()) {
					throw new NoSuchElementException();
				}
				return delegate.next();
			}

			@Override
			public boolean hasPrevious() {
				return delegate.previousIndex() >= begin;
			}

			@Override
			public T previous() {
				if(!hasPrevious()) {
					throw new NoSuchElementException();
				}
				return delegate.previous();
			}

			@Override
			public int nextIndex() {
				return delegate.nextIndex() - begin;
			}

			@Override
			public int previousIndex() {
				return delegate.previousIndex() - begin;
			}

			@Override
			public void remove() {
				delegate.remove();
				end--;
			}

			@Override
			public void set(T e) {
				delegate.set(e);
			}

			@Override
			public void add(T e) {
				delegate.add(e);
				end++;
			}
			
        }
    }

}
