Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package fmlist;
- import fj.F;
- import fj.F2;
- import fj.P2;
- import fj.P;
- import fj.Function;
- import fj.Monoid;
- import fj.Ord;
- import fj.Ordering;
- import fj.Hash;
- import fj.Show;
- import fj.Semigroup;
- import fj.Equal;
- import fj.data.Option;
- import fj.data.Either;
- import java.util.Collection;
- import java.util.Collections;
- import java.util.List;
- import java.util.Deque;
- import java.util.Iterator;
- import java.util.ListIterator;
- import java.util.ArrayList;
- import java.util.NoSuchElementException;
- import java.util.Comparator;
- /**
- * @author Alexander Altman
- * @param <E> the element type
- */
- public final class FMList<E> implements List<E>, Deque<E>, Cloneable {
- /**
- * Produces a first-class function that casts it's input to it's output's
- * type
- *
- * @param <A> the input type of the first-class function
- * @param <B> the output type of the first-class function
- * @return the requested first-class function
- */
- public static <A, B> F<A, B> castFunc() {
- return new F<A, B>() {
- @Override
- @SuppressWarnings("unchecked")
- public B f(A a) {
- return (B) a;
- }
- };
- }
- private FM<E> inner;
- /**
- * finds out if this list could possibly be finite
- *
- * @return whether or not the list is possibly finite
- */
- public boolean couldBeFinite() {
- return getInner().couldBeFinite();
- }
- /**
- * Produces the dual of a monoid
- *
- * @param <E> the monoid's domain
- * @param m the original monoid
- * @return the requested monoid
- */
- public static <E> Monoid<E> dualMonoid(Monoid<E> m) {
- return Monoid.monoid(Function.uncurryF2(m.sum()).flip(), m.zero());
- }
- /**
- * Produces the dual of a semigroup
- *
- * @param <E> the semigroup's domain
- * @param m the original semigroup
- * @return the requested semigroup
- */
- public static <E> Semigroup<E> dualSemigroup(Semigroup<E> m) {
- return Semigroup.semigroup(Function.uncurryF2(m.sum()).flip());
- }
- /**
- * The monoid of composition over endomorphisms
- *
- * @param <A> the (co)domain of the endomorphisms in question
- * @return the requested monoid
- */
- public static <A> Monoid<F<A, A>> endoMonoid() {
- final F<F<A, A>, F<F<A, A>, F<A, A>>> co = Function.compose();
- final F<A, A> id = Function.identity();
- return Monoid.monoid(co, id);
- }
- /**
- * The semigroup of composition over endomorphisms
- *
- * @param <A> the (co)domain of the endomorphisms in question
- * @return the requested semigroup
- */
- public static <A> Semigroup<F<A, A>> endoSemigroup() {
- final F<F<A, A>, F<F<A, A>, F<A, A>>> co = Function.compose();
- return Semigroup.semigroup(co);
- }
- /**
- * The monoid of append() over FMLists
- *
- * @param <E> the element type
- * @return the requested monoid
- */
- public static <E> Monoid<FMList<E>> fmListMonoid() {
- final F2<FMList<E>, FMList<E>, FMList<E>> append = FMList.append();
- final FMList<E> zero = new FMList<E>();
- return Monoid.monoid(append, zero);
- }
- /**
- * The hash concept over FMLists
- *
- * @param <E> the element type
- * @return the requested hash concept
- */
- public static <E> Hash<FMList<E>> fmListHash() {
- return Hash.anyHash();
- }
- /**
- * The ordering concept over FMLists
- *
- * @param <E> the type of elements to compare
- * @return the requested ordering concept
- */
- public static <E extends Comparable<E>> Ord<FMList<E>> fmListOrd() {
- return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {
- @Override
- public Ordering f(FMList<E> a, FMList<E> b) {
- final int k = a.zipWith((new F2<E, E, Integer>() {
- @Override
- public Integer f(E a, E b) {
- return a.compareTo(b);
- }
- }), b).foldr1(new F2<Integer, Integer, Integer>() {
- @Override
- public Integer f(Integer a_, Integer b) {
- final int a = a_.intValue();
- if (a == 0) {
- return b;
- } else {
- return a;
- }
- }
- }).intValue();
- if (k < 0) {
- return Ordering.LT;
- } else if (k == 0) {
- return Ordering.EQ;
- } else {
- return Ordering.GT;
- }
- }
- }));
- }
- /**
- * The ordering concept over FMLists
- *
- * @param <E> the type of elements to compare
- * @param cmp the ordering concept to use for the elements
- * @return the requested ordering concept
- */
- public static <E> Ord<FMList<E>> fmListOrd(Ord<E> cmp) {
- final Ord<E> qq = cmp;
- return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {
- @Override
- public Ordering f(FMList<E> a, FMList<E> b) {
- return a.zipWith((new F2<E, E, Ordering>() {
- @Override
- public Ordering f(E a, E b) {
- return qq.compare(a, b);
- }
- }), b).foldr1(new F2<Ordering, Ordering, Ordering>() {
- @Override
- public Ordering f(Ordering a, Ordering b) {
- if (a.equals(Ordering.EQ)) {
- return b;
- } else {
- return a;
- }
- }
- });
- }
- }));
- }
- /**
- * The ordering concept over FMLists
- *
- * @param <E> the type of elements to compare
- * @param cmp the comparator to use for the elements
- * @return the requested ordering concept
- */
- public static <E> Ord<FMList<E>> fmListOrd(Comparator<E> cmp) {
- final Comparator<E> qq = cmp;
- return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {
- @Override
- public Ordering f(FMList<E> a, FMList<E> b) {
- return a.zipWith((new F2<E, E, Ordering>() {
- @Override
- public Ordering f(E a, E b) {
- final int z = qq.compare(a, b);
- if (z < 0) {
- return Ordering.LT;
- } else if (z == 0) {
- return Ordering.EQ;
- } else {
- return Ordering.GT;
- }
- }
- }), b).foldr1(new F2<Ordering, Ordering, Ordering>() {
- @Override
- public Ordering f(Ordering a, Ordering b) {
- if (a.equals(Ordering.EQ)) {
- return b;
- } else {
- return a;
- }
- }
- });
- }
- }));
- }
- /**
- * The equality concept over FMLists
- *
- * @param <E> the element type
- * @return the requested equality concept
- */
- public static <E> Equal<FMList<E>> fmListEqual() {
- return Equal.anyEqual();
- }
- /**
- * The string conversion concept over FMLists
- *
- * @param <E> the element type
- * @return the requested string conversion concept
- */
- public static <E> Show<FMList<E>> fmListShow() {
- return Show.anyShow();
- }
- /**
- * The string conversion concept over FMLists
- *
- * @param <E> the element type
- * @param showDict the string conversion concept to use for the elements
- * @return the requested string conversion concept
- */
- public static <E> Show<FMList<E>> fmListShow(Show<E> showDict) {
- final Show<E> sD = showDict;
- return Show.showS(new F<FMList<E>, String>() {
- @Override
- public String f(FMList<E> a) {
- return (new StringBuilder("FMList: [")).append(sD.showS(a.head())).append(a.tail().foldMap(Monoid.stringBuilderMonoid, (new F<E, StringBuilder>() {
- @Override
- public StringBuilder f(E a) {
- return (new StringBuilder(", ")).append(sD.showS(a));
- }
- }))).toString();
- }
- });
- }
- @Override
- public FMList<E> clone() {
- return new FMList<E>(getInner());
- }
- /**
- * The classic "zipWith" function, applied to FMLists
- *
- * @param <N> the other input list's element type
- * @param <Q> the final result list's element type
- * @param zipFunc the function to use for zipping
- * @param other the other input list
- * @return the final result list
- */
- public <N, Q> FMList<Q> zipWith(F2<E, N, Q> zipFunc, FMList<N> other) {
- final F2<E, N, Q> t = zipFunc;
- final FM<E> i1 = getInner();
- final FMList<N> il2 = other;
- return new FMList<Q>(new FM<Q>() {
- @Override
- boolean couldBeFinite() {
- return i1.couldBeFinite() || il2.couldBeFinite();
- }
- @Override
- <X> X fm(Monoid<X> monoid, F<Q, X> mapFunc) {
- return i1.transformCS((new TransformCSFunc<E, Q, FMList<N>>() {
- @Override
- <M> M f(Monoid<M> m, F<Q, M> f_, E e, F2<M, FMList<N>, M> c_, FMList<N> i) {
- final Monoid<M> monoid = m;
- final F<Q, M> f = f_;
- final E e2 = e;
- final F2<M, FMList<N>, M> c = c_;
- final FMList<N> r1 = i;
- return r1.foldr((new F2<N, M, M>() {
- @Override
- public M f(N e1, M b__) {
- return c.f(f.f(t.f(e2, e1)), r1);
- }
- }), m.zero());
- }
- }), il2).fm(monoid, mapFunc);
- }
- });
- }
- /**
- * Converts a pair of lists into a list of pairs
- *
- * @param <N> the other input list's element type
- * @param other the other input list
- * @return the zipped output list
- */
- public <N> FMList<P2<E, N>> zip(FMList<N> other) {
- final F<E, F<N, P2<E, N>>> f = P.p2();
- return zipWith(Function.uncurryF2(f), other);
- }
- /**
- * Forces the evaluation of all of the internal delay structures, avoiding
- * potential stack overflows in finite lists. Please note that if enough
- * nested delays must be forced, this could be quite an expensive operation.
- * WARNING: do not use on infinite lists! It will <i>cause</i> stack
- * overflows if used with infinities.
- *
- * @throws InfiniteListException if called on an infinite FMList
- */
- public void force() throws InfiniteListException {
- if (!couldBeFinite()) {
- throw new InfiniteListException(this, "cannnot not force an infinite list");
- } else {
- setInner(FM.newFM(this));
- }
- }
- @Override
- public String toString() {
- return (new StringBuilder("FMList: [")).append(head()).append(tail().foldMap(Monoid.stringBuilderMonoid, new F<E, StringBuilder>() {
- @Override
- public StringBuilder f(E a) {
- return new StringBuilder(", ").append(a);
- }
- })).append("]").toString();
- }
- @Override
- public boolean equals(Object o) {
- if (!(o instanceof FMList)) {
- return false;
- } else {
- final FMList<? extends Object> other = (FMList<? extends Object>) o;
- boolean result = size() == other.size();
- for (int i = 0; i < size(); i++) {
- if (result) {
- result = result && get(i).equals(other.get(i));
- } else {
- return false;
- }
- }
- return result;
- }
- }
- @Override
- public int hashCode() {
- return foldr((new F2<E, Integer, Integer>() {
- @Override
- public Integer f(E a, Integer b) {
- return (47 * b) + (a.hashCode());
- }
- }), 7);
- }
- FMList(FM<E> i) {
- setInner(i);
- }
- /**
- * Constructs an new empty FMList
- */
- public FMList() {
- final FM<E> k = FM.newFM();
- setInner(k);
- }
- /**
- * Constructs a new FMList with the contents of an existing Iterable
- *
- * @param i the source Iterable
- */
- public FMList(Iterable<? extends E> i) {
- final FM<E> k = FM.newFM(i);
- setInner(k);
- }
- /**
- * Specialization of the FMList(Iterable) constructor so that it can handle
- * infinite FMLists (and both infinite and finite ones in O(1))
- *
- * @param i the other FMList
- */
- public FMList(FMList<E> i) {
- setInner(i.getInner());
- }
- /**
- * Constructs a new FMList with just one element
- *
- * @param e the sole element
- */
- public FMList(E e) {
- final FM<E> k = FM.newFM(e);
- setInner(k);
- }
- /**
- * Constructs a new FMList with just two elements
- *
- * @param e1 the first element
- * @param e2 the second element
- */
- public FMList(E e1, E e2) {
- final FM<E> k1 = FM.newFM(e1);
- final FM<E> k2 = FM.newFM(e2);
- setInner(k1.appendFM(k2));
- }
- /**
- * Constructs a new FMList with just three elements
- *
- * @param e1 the first element
- * @param e2 the second element
- * @param e3 the third element
- */
- public FMList(E e1, E e2, E e3) {
- final FM<E> k1 = FM.newFM(e1);
- final FM<E> k2 = FM.newFM(e2);
- final FM<E> k3 = FM.newFM(e3);
- setInner(k1.appendFM(k2).appendFM(k3));
- }
- /**
- * Maps "mapFunc" over the list, then folds using "monoid". This is the core
- * operation that enables FMLists to work.
- *
- * @param <X> "monoid"'s domain
- * @param monoid the monoid to use for folding
- * @param mapFunc the function to use for mapping
- * @return the final folded value
- */
- public <X> X foldMap(Monoid<X> monoid, F<E, X> mapFunc) {
- return getInner().fm(monoid, mapFunc);
- }
- /**
- * First-class version of foldMap()
- *
- * @param <X> the domain of the to-be-provided monoid
- * @return the first-class function
- */
- public <X> F2<Monoid<X>, F<E, X>, X> foldMap() {
- return getInner().fm();
- }
- /**
- * Partially applied version of foldMap()
- *
- * @param <X> "monoid"'s domain
- * @param monoid the monoid to use for folding
- * @return the partially applied function
- */
- public <X> F<F<E, X>, X> foldMap(Monoid<X> monoid) {
- return getInner().fm(monoid);
- }
- /**
- * Monoidal fold operation
- *
- * @param monoid the monoid to use for folding
- * @return the final folded result
- */
- public E fold(Monoid<E> monoid) {
- final F<E, E> id = Function.identity();
- return foldMap(monoid, id);
- }
- /**
- * First-class version of fold()
- *
- * @return the first-class function
- */
- public F<Monoid<E>, E> fold() {
- final FMList<E> self = this;
- return new F<Monoid<E>, E>() {
- @Override
- public E f(Monoid<E> a) {
- return self.fold(a);
- }
- };
- }
- /**
- * Right-biased fold operation
- *
- * @param <N> The type of the final folded result
- * @param f the function to use for folding
- * @param z the seed value for the fold
- * @return the final folded result
- */
- public <N> N foldr(F2<E, N, N> f, N z) {
- final Monoid<F<N, N>> eM = endoMonoid();
- return foldMap(eM, f.curry()).f(z);
- }
- /**
- * Partially applied version of foldr()
- *
- * @param <N> The type of the final folded result
- * @param f the function to use for folding
- * @return the partially applied function
- */
- public <N> F<N, N> foldr(F2<E, N, N> f) {
- final Monoid<F<N, N>> eM = endoMonoid();
- return foldMap(eM, f.curry());
- }
- /**
- * First-class version of foldr()
- *
- * @param <N> The type of the final folded result
- * @return the first-class function
- */
- public <N> F2<F2<E, N, N>, N, N> foldr() {
- final FMList<E> self = this;
- return new F2<F2<E, N, N>, N, N>() {
- @Override
- public N f(F2<E, N, N> a, N b) {
- return self.foldr(a, b);
- }
- };
- }
- /**
- * Left-biased fold operation
- *
- * @param <N> The type of the final folded result
- * @param f the function to use for folding
- * @param z the seed value for the fold
- * @return the final folded result
- */
- public <N> N foldl(F2<N, E, N> f, N z) {
- final Monoid<F<N, N>> eM = endoMonoid();
- return foldMap(dualMonoid(eM), f.flip().curry()).f(z);
- }
- /**
- * Partially applied version of foldl()
- *
- * @param <N> The type of the final folded result
- * @param f the function to use for folding
- * @return the partially applied function
- */
- public <N> F<N, N> foldl(F2<N, E, N> f) {
- final Monoid<F<N, N>> eM = endoMonoid();
- return foldMap(dualMonoid(eM), f.flip().curry());
- }
- /**
- * First-class version of foldl()
- *
- * @param <N> The type of the final folded result
- * @return the first-class function
- */
- public <N> F2<F2<N, E, N>, N, N> foldl() {
- final FMList<E> self = this;
- return new F2<F2<N, E, N>, N, N>() {
- @Override
- public N f(F2<N, E, N> a, N b) {
- return self.foldl(a, b);
- }
- };
- }
- /**
- * Applies "mapFunc" to each element in the list
- *
- * @param <N> the final element type after mapping
- * @param mapFunc the function to use for mapping
- * @return the mapped version of the list
- */
- public <N> FMList<N> map(F<E, N> mapFunc) {
- final F<E, N> mf = mapFunc;
- return new FMList<N>(getInner().transform(new TransformFunc<N, E>() {
- @Override
- <M> M f(Monoid<M> monoid, F<N, M> func, E val) {
- return func.f(mf.f(val));
- }
- }));
- }
- /**
- * First-class version of map()
- *
- * @param <N> the final element type after mapping
- * @return the first-class function
- */
- public <N> F<F<E, N>, FMList<N>> map() {
- final FMList<E> self = this;
- return new F<F<E, N>, FMList<N>>() {
- @Override
- public FMList<N> f(F<E, N> a) {
- return self.map(a);
- }
- };
- }
- /**
- * Concatenates all of the sublists together into one large
- * single-dimensional list
- *
- * @param <E>
- * @param lls the nested list
- * @return the flattened version of "lls"
- */
- public static <E> FMList<E> flatten(FMList<FMList<E>> lls) {
- return new FMList<E>(lls.getInner().transform(new TransformFunc<E, FMList<E>>() {
- @Override
- <M> M f(Monoid<M> monoid, F<E, M> func, FMList<E> val) {
- return val.foldMap(monoid, func);
- }
- }));
- }
- /**
- * Concatenates this list to beginning of the given one
- *
- * @param other the other list
- * @return the appended result
- */
- public FMList<E> append(FMList<E> other) {
- return new FMList<E>(getInner().appendFM(other.getInner()));
- }
- /**
- * First-class version of append()
- *
- * @param <E> the element type
- * @return the first-class function
- */
- public static <E> F2<FMList<E>, FMList<E>, FMList<E>> append() {
- return new F2<FMList<E>, FMList<E>, FMList<E>>() {
- @Override
- public FMList<E> f(FMList<E> a, FMList<E> b) {
- return a.append(b);
- }
- };
- }
- /**
- * adds an element at the beginning
- *
- * @param e the new element
- */
- public void cons(E e) {
- final FM<E> k = FM.newFM(e);
- setInner(k.appendFM(getInner()));
- }
- /**
- * adds an element at the end
- *
- * @param e the new element
- */
- public void snoc(E e) {
- final FM<E> k = FM.newFM(e);
- setInner(getInner().appendFM(k));
- }
- /**
- * first-class copying version of cons()
- *
- * @return the first-class function
- */
- public F<E, FMList<E>> cons() {
- final FMList<E> self = this;
- return new F<E, FMList<E>>() {
- @Override
- public FMList<E> f(E a) {
- final FMList<E> ll = self.clone();
- ll.cons(a);
- return ll;
- }
- };
- }
- /**
- * first-class copying version of snoc()
- *
- * @return the first-class function
- */
- public F<E, FMList<E>> snoc() {
- final FMList<E> self = this;
- return new F<E, FMList<E>>() {
- @Override
- public FMList<E> f(E a) {
- final FMList<E> ll = self.clone();
- ll.snoc(a);
- return ll;
- }
- };
- }
- /**
- * finds the first element
- *
- * @return the first element
- */
- public E head() {
- final Monoid<Option<E>> m = Monoid.firstOptionMonoid();
- final F<E, Option<E>> f = Option.some_();
- return getInner().fm(m, f).valueE("Empty list!");
- }
- /**
- * Deletes all entries for which "filtFunc" is false
- *
- * @param filtFunc the predicate to use for filtering
- */
- public void filter(F<E, Boolean> filtFunc) {
- final F<E, Boolean> fF = filtFunc;
- setInner(getInner().transform(new TransformFunc<E, E>() {
- @Override
- <M> M f(Monoid<M> monoid, F<E, M> func, E val) {
- if (fF.f(val)) {
- return func.f(val);
- } else {
- return monoid.zero();
- }
- }
- }));
- }
- /**
- * finds the last element
- *
- * @return the last element
- */
- public E last() {
- final Monoid<Option<E>> m = Monoid.lastOptionMonoid();
- final F<E, Option<E>> f = Option.some_();
- return getInner().fm(m, f).valueE("Empty list!");
- }
- /**
- * Cuts this list down to the first "num" elements. Fast but unsafe with left infinities.
- *
- * @param num the number of elements to take
- */
- public void take(int num) {
- setInner(getInner().transformCS((new TransformCSFunc<E, E, Integer>() {
- @Override
- <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Integer, M> c, Integer i) {
- if (i.intValue() > 0) {
- return c.f(f.f(e), (i.intValue()) - 1);
- } else {
- return m.zero();
- }
- }
- }), num));
- }
- /**
- * Cuts this list down to all except the first "num" elements.
- *
- * @param num the number of elements to drop
- */
- public void drop(int num) {
- setInner(getInner().transformCS((new TransformCSFunc<E, E, Integer>() {
- @Override
- <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Integer, M> c, Integer i) {
- if (i.intValue() > 0) {
- return c.f(m.zero(), (i.intValue() - 1));
- } else {
- return c.f(f.f(e), 0);
- }
- }
- }), num));
- }
- /**
- * Cuts this list down to the first "num" elements. Somewhat slower than
- * take() but safe with left infinities.
- *
- * @param num the number of elements to take
- */
- public void keepFirst(int num) {
- final FMList<E> internal = new FMList<E>();
- for (int j = 0; j < num; j++) {
- internal.cons(get(j));
- }
- setInner(internal.getInner());
- }
- /**
- * Synonym for drop()
- *
- * @param num the number of elements to take
- */
- public void keepNotFirst(int num) {
- drop(num);
- }
- /**
- * Cuts this list down to the last "num" elements. Somewhat slower than
- * reverse(); take() but safe with right infinities.
- *
- * @param num the number of elements to take
- */
- public void keepLast(int num) {
- final FMList<E> internal1 = clone();
- internal1.reverse();
- final FMList<E> internal2 = new FMList<E>();
- for (int j = 0; j < num; j++) {
- internal2.snoc(internal1.get(j));
- }
- setInner(internal2.getInner());
- }
- /**
- * Synonym for reverse(); drop(); reverse()
- *
- * @param num the number of elements to take
- */
- public void keepNotLast(int num) {
- reverse();
- drop(num);
- reverse();
- }
- /**
- * Cuts this list down to all the elements before the first one that matches
- * "filtFunc"
- *
- * @param filtFunc the predicate to search with
- */
- public void takeWhile(F<E, Boolean> filtFunc) {
- final F<E, Boolean> p = filtFunc;
- setInner(getInner().transformCS((new TransformCSFunc<E, E, Boolean>() {
- @Override
- <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Boolean, M> c, Boolean i) {
- if (p.f(e)) {
- return c.f(f.f(e), true);
- } else {
- return m.zero();
- }
- }
- }), true));
- }
- /**
- * Cuts this list down to the first element that matches "filtFunc" plus all
- * the elements after that one
- *
- * @param filtFunc the predicate to search with
- */
- public void dropWhile(F<E, Boolean> filtFunc) {
- final F<E, Boolean> p = filtFunc;
- setInner(getInner().transformCS((new TransformCSFunc<E, E, Boolean>() {
- @Override
- <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Boolean, M> c, Boolean ok) {
- if (ok && p.f(e)) {
- return c.f(m.zero(), true);
- } else {
- return c.f(f.f(e), false);
- }
- }
- }), true));
- }
- public <N> FMList<N> castElements() {
- final F<E, N> cf = castFunc();
- return map(cf);
- }
- /**
- * Gets the first element that matches filtFunc
- *
- * @param filtFunc the predicate to search with
- * @return the element involved
- * @throws NoSuchElementException if no element matches "filtFunc"
- */
- public E find(F<E, Boolean> filtFunc) throws NoSuchElementException {
- final FMList<E> internal = clone();
- internal.dropWhile(filtFunc);
- if (internal.isEmpty()) {
- throw new NoSuchElementException("no element matches the supplied predicate");
- } else {
- return internal.head();
- }
- }
- /**
- * gets all except the first element
- *
- * @return the 'tail' of the list
- */
- public FMList<E> tail() {
- final FMList<E> other = clone();
- other.drop(1);
- return other;
- }
- /**
- * gets all except the last element
- *
- * @return the 'init' of the list
- */
- public FMList<E> init() {
- final FMList<E> other = this.clone();
- other.reverse();
- other.drop(1);
- return other;
- }
- /**
- * reverses this list
- */
- public void reverse() {
- final FM<E> i = getInner();
- setInner(new FM<E>() {
- @Override
- <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
- return i.fm(dualMonoid(monoid), mapFunc);
- }
- @Override
- boolean couldBeFinite() {
- return i.couldBeFinite();
- }
- });
- }
- @Override
- public int size() {
- F<E, Integer> cst1 = Function.constant(1);
- return foldMap(Monoid.intAdditionMonoid, cst1).intValue();
- }
- @Override
- public boolean isEmpty() {
- return size() == 0;
- }
- @Override
- public boolean contains(Object o) {
- final Object r = o;
- final FMList<E> testList = this.clone();
- testList.filter(new F<E, Boolean>() {
- @Override
- public Boolean f(E a) {
- return (r == null ? a == null : r.equals(a));
- }
- });
- return !(testList.isEmpty());
- }
- @Override
- public Iterator<E> iterator() {
- final FMList<E> self = this;
- return new Iterator<E>() {
- private int currentIndex = 0;
- @Override
- public boolean hasNext() {
- return currentIndex != self.size();
- }
- @Override
- public E next() {
- if (hasNext()) {
- currentIndex++;
- return self.get(currentIndex);
- } else {
- throw new NoSuchElementException("this FMList is right-finite");
- }
- }
- @Override
- public void remove() {
- self.remove(currentIndex);
- currentIndex--;
- }
- };
- }
- @Override
- public Object[] toArray() {
- final int s = size();
- final Object[] outArray = new Object[s];
- for (int i = 0; i < s; i++) {
- outArray[i] = get(i);
- }
- return outArray;
- }
- @Override
- @SuppressWarnings({"unchecked", "unchecked"})
- public <T> T[] toArray(T[] ts) {
- final int s1 = size();
- final int s2 = ts.length;
- if (s2 > s1) {
- final T[] outArray;
- outArray = ts;
- for (int i = 0; i < s1; i++) {
- outArray[i] = (T) get(i);
- }
- return outArray;
- } else {
- final ArrayList<T> outList = new ArrayList<T>(s1);
- for (E x : this) {
- outList.add((T) x);
- }
- return outList.toArray(ts);
- }
- }
- @Override
- public boolean add(E e) {
- this.snoc(e);
- return true;
- }
- @Override
- public boolean remove(Object o) {
- final Object r = o;
- final F<E, Boolean> filtFunc = new F<E, Boolean>() {
- @Override
- public Boolean f(E a) {
- return !(r == null ? a == null : r.equals(a));
- }
- };
- final FMList<E> testList = clone();
- testList.filter(filtFunc);
- boolean answer = !(testList.isEmpty());
- if (answer) {
- final FMList<E> internal1 = clone();
- final FMList<E> internal2 = clone();
- internal1.takeWhile(filtFunc);
- internal2.dropWhile(filtFunc);
- internal2.tail();
- setInner(internal1.getInner().appendFM(internal2.getInner()));
- }
- return answer;
- }
- @Override
- public boolean containsAll(Collection<?> clctn) {
- final FMList<Object> c = new FMList<Object>(clctn);
- final FMList<E> self = this;
- return c.foldMap(Monoid.conjunctionMonoid, (new F<Object, Boolean>() {
- @Override
- @SuppressWarnings("unchecked")
- public Boolean f(Object a) {
- return self.contains(a);
- }
- }));
- }
- @Override
- public boolean addAll(Collection<? extends E> clctn) {
- return addAll(0, clctn);
- }
- @Override
- public boolean addAll(int i, Collection<? extends E> clctn) {
- final FMList<E> alt1 = clone();
- final FMList<E> alt3 = clone();
- alt1.keepFirst(i);
- alt3.drop(i);
- final FMList<E> alt2 = new FMList<E>(clctn);
- setInner(alt1.getInner().appendFM(alt2.getInner()).appendFM(alt3.getInner()));
- return true;
- }
- /**
- * Monadic core operation
- *
- * @param <N> the final element type
- * @param bindFunc the function to bind this list to
- * @return the result of the binding
- */
- public <N> FMList<N> bind(F<E, FMList<N>> bindFunc) {
- final F<E, FMList<N>> g = bindFunc;
- return new FMList<N>(getInner().transform(new TransformFunc<N, E>() {
- @Override
- <M> M f(Monoid<M> monoid, F<N, M> func, E val) {
- return g.f(val).foldMap(monoid, func);
- }
- }));
- }
- /**
- * Applicative core operation
- *
- * @param <N> the final element type
- * @param appFuncList the list of functions to apply over this list
- * @return the result of the application
- */
- public <N> FMList<N> apply(FMList<F<E, N>> appFuncList) {
- final FM<F<E, N>> gs = appFuncList.getInner();
- final FM<E> xs = getInner();
- return new FMList<N>(gs.transform(new TransformFunc<N, F<E, N>>() {
- @Override
- <M> M f(Monoid<M> monoid, F<N, M> func, F<E, N> val) {
- return xs.fm(monoid, func.o(val));
- }
- }));
- }
- /**
- * Deconstructs this list into head() and tail()
- *
- * @return a tuple containing head() and tail()
- */
- public P2<E, FMList<E>> decons() {
- return P.p(head(), tail());
- }
- /**
- * Deconstructs this list into init() and last()
- *
- * @return a tuple containing init() and last()
- */
- public P2<FMList<E>, E> desnoc() {
- return P.p(init(), last());
- }
- /**
- * splits the list on the given index
- *
- * @param splitIndex the index after which to split the list
- * @return the split lists
- */
- public P2<FMList<E>, FMList<E>> split(int splitIndex) {
- final FMList<E> a = clone();
- final FMList<E> b = clone();
- a.keepFirst(splitIndex + 1);
- b.drop(splitIndex + 1);
- return P.p(a, b);
- }
- /**
- * Splits the list after the first element that matches "filtFunc"
- *
- * @param filtFunc the predicate by which to split the list
- * @return the split lists
- */
- public P2<FMList<E>, FMList<E>> splitOn(F<E, Boolean> filtFunc) {
- final FMList<E> a = clone();
- final FMList<E> b = clone();
- a.takeWhile(filtFunc);
- b.dropWhile(filtFunc);
- a.snoc(b.head());
- return P.p(a, b.tail());
- }
- /**
- * Produces a right-infinite list that contains the progressively iterated
- * application of "iterFunc" to "initialValue", starting with "initialValue"
- * itself
- *
- * @param <E>
- * @param iterFunc
- * @param initialValue
- * @return the infinite list
- */
- public static <E> FMList<E> iterate(F<E, E> iterFunc, E initialValue) {
- final F<E, E> f = iterFunc;
- final E x = initialValue;
- final FM<E> iterFM = new FM<E>() {
- @Override
- <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
- return monoid.sum(mapFunc.f(x), fm(monoid, mapFunc));
- }
- @Override
- boolean couldBeFinite() {
- return false;
- }
- };
- return new FMList<E>(iterFM);
- }
- /**
- * cycleM()s a single element
- *
- * @param <E>
- * @param elem
- * @return the infinite list
- */
- public static <E> FMList<E> repeatM(E elem) {
- final FMList<E> result = new FMList<E>(elem);
- result.cycleM();
- return result;
- }
- /**
- * Repeats this list infinitely in the middle
- */
- public void cycleM() {
- final FM<E> l = getInner();
- final FMList<E> self = this;
- final FM<E> cycleFM = new FM<E>() {
- @Override
- <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
- final FMList<E> xx = self.clone();
- xx.cycleM();
- return (l.appendFM(xx.getInner()).appendFM(l)).fm(monoid, mapFunc);
- }
- @Override
- boolean couldBeFinite() {
- return false;
- }
- };
- setInner(cycleFM);
- }
- /**
- * cycleR()s a single element
- *
- * @param <E>
- * @param elem
- * @return the infinite list
- */
- public static <E> FMList<E> repeatR(E elem) {
- final FMList<E> result = new FMList<E>(elem);
- result.cycleR();
- return result;
- }
- /**
- * Repeats this list infinitely to the right
- */
- public void cycleR() {
- final FM<E> l = getInner();
- final FMList<E> self = this;
- final FM<E> cycleFM = new FM<E>() {
- @Override
- <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
- final FMList<E> xx = self.clone();
- xx.cycleR();
- return ((xx.getInner()).appendFM(l)).fm(monoid, mapFunc);
- }
- @Override
- boolean couldBeFinite() {
- return false;
- }
- };
- setInner(cycleFM);
- }
- /**
- * cycleL()s a single element
- *
- * @param <E>
- * @param elem
- * @return the infinite list
- */
- public static <E> FMList<E> repeatL(E elem) {
- final FMList<E> result = new FMList<E>(elem);
- result.cycleL();
- return result;
- }
- /**
- * Repeats this list infinitely to the left
- */
- public void cycleL() {
- final FM<E> l = getInner();
- final FMList<E> self = this;
- final FM<E> cycleFM = new FM<E>() {
- @Override
- <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
- final FMList<E> xx = self.clone();
- xx.cycleL();
- return (l.appendFM(xx.getInner())).fm(monoid, mapFunc);
- }
- @Override
- boolean couldBeFinite() {
- return false;
- }
- };
- setInner(cycleFM);
- }
- /**
- * cycleB()s a single element
- *
- * @param <E>
- * @param elem
- * @return the infinite list
- */
- public static <E> FMList<E> repeatB(E elem) {
- final FMList<E> result = new FMList<E>(elem);
- result.cycleB();
- return result;
- }
- /**
- * Repeats this list infinitely to the left and right
- */
- public void cycleB() {
- final FM<E> l = getInner();
- final FMList<E> self = this;
- final FM<E> cycleFM = new FM<E>() {
- @Override
- <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
- final FMList<E> xx = self.clone();
- xx.cycleB();
- final FM<E> xi = xx.getInner();
- return (xi.appendFM(l).appendFM(xi)).fm(monoid, mapFunc);
- }
- @Override
- boolean couldBeFinite() {
- return false;
- }
- };
- setInner(cycleFM);
- }
- /**
- * Builds a list from a seed value. unfold() takes a seed and calls "bFunc"
- * on it. If the result is in right(), then it is appended to the prior. If
- * the result in in left(), then it is used in the core recursive call.
- *
- * @param <E>
- * @param <N>
- * @param bFunc
- * @param seedValue
- * @return the unfolded list
- */
- public static <E, N> FMList<E> unfold(F<N, FMList<Either<N, E>>> bFunc, N seedValue) {
- return new FMList<E>(FM.unfold(bFunc.andThen(new F<FMList<Either<N, E>>, FM<Either<N, E>>>() {
- @Override
- public FM<Either<N, E>> f(FMList<Either<N, E>> a) {
- return a.getInner();
- }
- }), seedValue));
- }
- /**
- * right-biased Option-based version of unfold()
- *
- * @param <E> the final element type
- * @param <N> the seed type
- * @param bFunc the function to use for unfolding
- * @param seedValue the initial seed value
- * @return the unfolded list
- */
- public static <E, N> FMList<E> unfoldr(F<N, Option<P2<E, N>>> bFunc, N seedValue) {
- final F<N, Option<P2<E, N>>> g = bFunc;
- return unfold((new F<N, FMList<Either<N, E>>>() {
- @Override
- public FMList<Either<N, E>> f(N a) {
- final Option<P2<E, N>> k = g.f(a);
- if (k.isNone()) {
- return new FMList<Either<N, E>>();
- } else {
- final P2<E, N> p = k.some();
- final Either<N, E> va = Either.right(p._1());
- final Either<N, E> vb = Either.left(p._2());
- return new FMList<Either<N, E>>(va, vb);
- }
- }
- }), seedValue);
- }
- /**
- * left-biased Option-based version of unfold()
- *
- * @param <E> the final element type
- * @param <N> the seed type
- * @param bFunc the function to use for unfolding
- * @param seedValue the initial seed value
- * @return the unfolded list
- */
- public static <E, N> FMList<E> unfoldl(F<N, Option<P2<E, N>>> bFunc, N seedValue) {
- FMList<E> result = unfoldr(bFunc, seedValue);
- result.reverse();
- return result;
- }
- @Override
- public boolean removeAll(Collection<?> clctn) {
- final FMList<Object> c = new FMList<Object>(clctn);
- final FMList<E> self = this;
- return c.foldMap(Monoid.conjunctionMonoid, (new F<Object, Boolean>() {
- @Override
- public Boolean f(Object a) {
- return self.remove(a);
- }
- }));
- }
- @Override
- public boolean retainAll(Collection<?> clctn) {
- final FMList<Object> internal = (new FMList<Object>(clctn));
- internal.filter(new F<Object, Boolean>() {
- @Override
- public Boolean f(Object a) {
- throw new UnsupportedOperationException("Not supported yet.");
- }
- });
- setInner(internal.map(new F<Object, E>() {
- @Override
- @SuppressWarnings("unchecked")
- public E f(Object a) {
- return (E) a;
- }
- }).getInner());
- return true;
- }
- @Override
- public void clear() {
- FM<E> ii = FM.newFM();
- setInner(ii);
- }
- @Override
- public E get(int i) {
- final FMList<E> internal = clone();
- internal.drop(i);
- return internal.head();
- }
- @Override
- public E set(int i, E e) {
- final FMList<E> internal1 = clone();
- final FMList<E> internal2 = clone();
- internal1.take(i);
- internal2.drop(i + 1);
- final FM<E> i3 = FM.newFM(e);
- final E old = get(i);
- setInner(internal1.getInner().appendFM(i3).appendFM(internal2.getInner()));
- return old;
- }
- @Override
- public void add(int i, E e) {
- final FMList<E> internal1 = clone();
- final FMList<E> internal2 = clone();
- internal1.take(i);
- internal2.drop(i);
- final FM<E> i3 = FM.newFM(e);
- setInner(internal1.getInner().appendFM(i3).appendFM(internal2.getInner()));
- }
- @Override
- public E remove(int i) {
- final FMList<E> internal1 = clone();
- final FMList<E> internal2 = clone();
- internal1.take(i);
- internal2.drop(i + 1);
- final E old = get(i);
- setInner(internal1.getInner().appendFM(internal2.getInner()));
- return old;
- }
- public FMList<P2<Integer, E>> number() {
- final FMList<E> self = this;
- return self.tail().foldl((new F2<FMList<P2<Integer, E>>, E, FMList<P2<Integer, E>>>() {
- @Override
- public FMList<P2<Integer, E>> f(FMList<P2<Integer, E>> a, E b) {
- final int k = a.last()._1().intValue();
- a.snoc(P.p((k + 1), b));
- return a;
- }
- }), (new FMList<P2<Integer, E>>(P.p(0, self.head()))));
- }
- @Override
- public int indexOf(Object o) {
- final FMList<P2<Integer, E>> internal = number();
- internal.retainAll(Collections.singletonList(o));
- if (internal.isEmpty()) {
- return -1;
- } else {
- return internal.head()._1().intValue();
- }
- }
- @Override
- public int lastIndexOf(Object o) {
- final FMList<P2<Integer, E>> internal = number();
- internal.retainAll(Collections.singletonList(o));
- if (internal.isEmpty()) {
- return -1;
- } else {
- return internal.last()._1().intValue();
- }
- }
- private static interface FMListIterator<E> extends ListIterator<E> {
- void setCurrentIndex(int i);
- }
- private FMListIterator<E> fmListIterator() {
- final FMList<E> self = this;
- return new FMListIterator<E>() {
- private int currentIndex = 0;
- @Override
- public boolean hasNext() {
- return currentIndex != self.size();
- }
- @Override
- public E next() {
- if (hasNext()) {
- currentIndex++;
- return self.get(currentIndex);
- } else {
- throw new NoSuchElementException("this FMList is right-finite");
- }
- }
- @Override
- public void remove() {
- self.remove(currentIndex);
- currentIndex--;
- }
- @Override
- public boolean hasPrevious() {
- return currentIndex != 0;
- }
- @Override
- public E previous() {
- if (hasPrevious()) {
- currentIndex--;
- return self.get(currentIndex);
- } else {
- throw new NoSuchElementException("this FMList is left-finite");
- }
- }
- @Override
- public int nextIndex() {
- return currentIndex + 1;
- }
- @Override
- public int previousIndex() {
- return currentIndex - 1;
- }
- @Override
- public void set(E e) {
- self.set(currentIndex, e);
- }
- @Override
- public void add(E e) {
- self.add(currentIndex, e);
- currentIndex++;
- }
- @Override
- public void setCurrentIndex(int i) {
- currentIndex = i;
- }
- };
- }
- @Override
- public ListIterator<E> listIterator() {
- return fmListIterator();
- }
- @Override
- public ListIterator<E> listIterator(int i) {
- final FMListIterator<E> li = fmListIterator();
- li.setCurrentIndex(i - 1);
- return li;
- }
- @Override
- public FMList<E> subList(int i, int i1) {
- FMList<E> internal = clone();
- internal.take(i);
- internal.drop(i1 - i);
- return internal;
- }
- @Override
- public void addFirst(E e) {
- cons(e);
- }
- @Override
- public void addLast(E e) {
- snoc(e);
- }
- @Override
- public boolean offerFirst(E e) {
- cons(e);
- return true;
- }
- @Override
- public boolean offerLast(E e) {
- snoc(e);
- return true;
- }
- @Override
- public E removeFirst() {
- E e = head();
- drop(1);
- return e;
- }
- @Override
- public E removeLast() {
- E e = last();
- take(size() - 1);
- return e;
- }
- @Override
- public E pollFirst() {
- if (isEmpty()) {
- return null;
- } else {
- return removeFirst();
- }
- }
- @Override
- public E pollLast() {
- if (isEmpty()) {
- return null;
- } else {
- return removeLast();
- }
- }
- @Override
- public E getFirst() {
- return head();
- }
- @Override
- public E getLast() {
- return last();
- }
- @Override
- public E peekFirst() {
- if (isEmpty()) {
- return null;
- } else {
- return getFirst();
- }
- }
- @Override
- public E peekLast() {
- if (isEmpty()) {
- return null;
- } else {
- return getLast();
- }
- }
- @Override
- public boolean removeFirstOccurrence(Object o) {
- return remove(o);
- }
- @Override
- public boolean removeLastOccurrence(Object o) {
- reverse();
- final boolean r = remove(o);
- reverse();
- return r;
- }
- @Override
- public boolean offer(E e) {
- return offerLast(e);
- }
- @Override
- public E remove() {
- return removeFirst();
- }
- @Override
- public E poll() {
- return pollFirst();
- }
- @Override
- public E element() {
- return getFirst();
- }
- @Override
- public E peek() {
- return peekFirst();
- }
- @Override
- public void push(E e) {
- addFirst(e);
- }
- @Override
- public E pop() {
- return removeFirst();
- }
- /**
- * Unseeded foldr()
- *
- * @param f the folding function
- * @return the final folded value
- * @throws NoSuchElementException if this list is empty
- */
- public E foldr1(F2<E, E, E> f) throws NoSuchElementException {
- if (isEmpty()) {
- throw new NoSuchElementException("cannot do an unseeded fold on an empty list");
- }
- return tail().foldr(f, head());
- }
- /**
- * First-class version of foldr1()
- *
- * @return the first-class function
- */
- public F<F2<E, E, E>, E> foldr1() {
- final FMList<E> self = this;
- return new F<F2<E, E, E>, E>() {
- @Override
- public E f(F2<E, E, E> a) {
- return self.foldr1(a);
- }
- };
- }
- /**
- * Unseeded foldl()
- *
- * @param f the folding function
- * @return the final folded value
- * @throws NoSuchElementException if this list is empty
- */
- public E foldl1(F2<E, E, E> f) {
- if (isEmpty()) {
- throw new NoSuchElementException("cannot do an unseeded fold on an empty list");
- }
- return init().foldl(f, last());
- }
- /**
- * First-class version of foldl1()
- *
- * @return the first-class function
- */
- public F<F2<E, E, E>, E> foldl1() {
- final FMList<E> self = this;
- return new F<F2<E, E, E>, E>() {
- @Override
- public E f(F2<E, E, E> a) {
- return self.foldl1(a);
- }
- };
- }
- /**
- * append()s all the inner lists
- *
- * @param <E> the inner element type
- * @param lli the multi-layer list
- * @return the joined list
- */
- public static <E> FMList<E> concat(FMList<FMList<E>> lli) {
- final Monoid<FMList<E>> m = fmListMonoid();
- return lli.fold(m);
- }
- /**
- * Gets the "&&" of all the booleans in "lli"
- *
- * @param lli the list to be folded
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public static Boolean and(FMList<Boolean> lli) throws InfiniteListException {
- if (!(lli.couldBeFinite())) {
- throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
- }
- final Monoid<Boolean> m = Monoid.conjunctionMonoid;
- return lli.fold(m);
- }
- /**
- * Gets the "||" of all the booleans in "lli"
- *
- * @param lli the list to be folded
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public static Boolean or(FMList<Boolean> lli) throws InfiniteListException {
- if (!(lli.couldBeFinite())) {
- throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
- }
- final Monoid<Boolean> m = Monoid.disjunctionMonoid;
- return lli.fold(m);
- }
- /**
- * map()s the list to booleans using "f", then "||"'s them
- *
- * @param f
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public Boolean any(F<E, Boolean> f) throws InfiniteListException {
- if (!(couldBeFinite())) {
- throw new InfiniteListException(this, "cannot fold an infinite list to a point");
- }
- final Monoid<Boolean> m = Monoid.disjunctionMonoid;
- return foldMap(m, f);
- }
- /**
- * map()s the list to booleans using "f", then "&&"'s them
- *
- * @param f
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public Boolean all(F<E, Boolean> f) throws InfiniteListException {
- if (!(couldBeFinite())) {
- throw new InfiniteListException(this, "cannot fold an infinite list to a point");
- }
- final Monoid<Boolean> m = Monoid.conjunctionMonoid;
- return foldMap(m, f);
- }
- /**
- * Gets the maximum value among all the "Comparable"'s in "lli"
- *
- * @param <E>
- * @param lli the list to be folded
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public static <E extends Comparable<E>> E maximum(FMList<E> lli) throws InfiniteListException {
- if (!(lli.couldBeFinite())) {
- throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
- }
- return lli.foldr1(new F2<E, E, E>() {
- @Override
- public E f(E a, E b) {
- final int z = a.compareTo(b);
- if (z <= 0) {
- return b;
- } else {
- return a;
- }
- }
- });
- }
- /**
- * Gets the minimum value among all the "Comparable"'s in "lli"
- *
- * @param <E>
- * @param lli the list to be folded
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public static <E extends Comparable<E>> E minimum(FMList<E> lli) throws InfiniteListException {
- if (!(lli.couldBeFinite())) {
- throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
- }
- return lli.foldr1(new F2<E, E, E>() {
- @Override
- public E f(E a, E b) {
- final int z = a.compareTo(b);
- if (z <= 0) {
- return a;
- } else {
- return b;
- }
- }
- });
- }
- /**
- * Gets the maximum value among all the values in the list
- *
- * @param cmp the ordering to use when comparing
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public E maximum(Ord<E> cmp) throws InfiniteListException {
- if (!(couldBeFinite())) {
- throw new InfiniteListException(this, "cannot fold an infinite list to a point");
- }
- return foldr1(Function.uncurryF2(cmp.max));
- }
- /**
- * Gets the minimum value among all the values in the list
- *
- * @param cmp the ordering to use when comparing
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public E minimum(Ord<E> cmp) throws InfiniteListException {
- if (!(couldBeFinite())) {
- throw new InfiniteListException(this, "cannot fold an infinite list to a point");
- }
- return foldr1(Function.uncurryF2(cmp.min));
- }
- /**
- * Gets the maximum value among all the values in the list
- *
- * @param cmp the comparator to use when comparing
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public E maximum(Comparator<E> cmp) throws InfiniteListException {
- if (!(couldBeFinite())) {
- throw new InfiniteListException(this, "cannot fold an infinite list to a point");
- }
- final Comparator<E> k = cmp;
- return foldr1(new F2<E, E, E>() {
- @Override
- public E f(E a, E b) {
- if (k.compare(a, b) < 0) {
- return b;
- } else {
- return a;
- }
- }
- });
- }
- /**
- * Gets the minimum value among all the values in the list
- *
- * @param cmp the comparator to use when comparing
- * @return the final folded value
- * @throws InfiniteListException if "lli" is infinite
- */
- public E minimum(Comparator<E> cmp) throws InfiniteListException {
- if (!(couldBeFinite())) {
- throw new InfiniteListException(this, "cannot fold an infinite list to a point");
- }
- final Comparator<E> k = cmp;
- return foldr1(new F2<E, E, E>() {
- @Override
- public E f(E a, E b) {
- if (k.compare(a, b) < 0) {
- return a;
- } else {
- return b;
- }
- }
- });
- }
- @Override
- public Iterator<E> descendingIterator() {
- final FMList<E> self = this;
- return new Iterator<E>() {
- private int currentIndex = self.size();
- ;
- @Override
- public boolean hasNext() {
- return currentIndex != 0;
- }
- @Override
- public E next() {
- if (hasNext()) {
- currentIndex--;
- return self.get(currentIndex);
- } else {
- throw new NoSuchElementException("this FMList is left-finite");
- }
- }
- @Override
- public void remove() {
- self.remove(currentIndex);
- currentIndex--;
- }
- };
- }
- FM<E> getInner() {
- return inner;
- }
- private void setInner(FM<E> inner) {
- this.inner = inner;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement