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;
}
}