local z="\050\046\049\046\048"local X,S,U=next,type,pcall local r,k=setmetatable,getmetatable local y,L=table.insert,table.sort local o,P=table.remove,table.concat local c,x,D=math.randomseed,math.random,math.huge local H,e,w,M=math.floor,math.max,math.min,math.ceil local Q=coroutine.wrap local n=coroutine.yield local F=rawget local b=table.unpack or unpack local u,R=pairs,ipairs local J=error local Y=os.clock local q={}local function l(z,X)return z>X end local function T(z,X)return z<X end local function h(z)local X=0 for z,S in u(z)do X=X+1 end return X end local function C(z,X,S,...)S=S or q.identity local U for z,r in u(z)do if not U then U=S(r,...)else local z=S(r,...)U=X(U,z)and U or z end end return U end local function m(z,X,S,U)for r=0,#z,X do local k=q.slice(z,r+1,r+X)if#k>0 then while#k<X and U do k[#k+1]=U end S(k)end end end local function Z(z,X,S,U)for r=0,#z,X-1 do local k=q.slice(z,r+1,r+X)if#k>0 and r+1<#z then while#k<X and U do k[#k+1]=U end S(k)end end end local function v(z,X,S,U)for r=0,#z,1 do local k=q.slice(z,r+1,r+X)if#k>0 and r+X<=#z then while#k<X and U do k[#k+1]=U end S(k)end end end local function A(z,X,S)if X==0 then S(z)end for U=1,X,1 do z[X],z[U]=z[U],z[X]A(z,X-1,S)z[X],z[U]=z[U],z[X]end end local function d(z)return z>=0 and 1 or-1 end local K=-1 q.operator={}q.operator.add=function(z,X)return z+X end q.operator.sub=function(z,X)return z-X end q.operator.mul=function(z,X)return z*X end q.operator.div=function(z,X)return z/X end q.operator.mod=function(z,X)return z%X end q.operator.exp=function(z,X)return z^X end q.operator.pow=q.operator.exp q.operator.unm=function(z)return-z end q.operator.neg=q.operator.unm q.operator.floordiv=function(z,X)return H(z/X)end q.operator.intdiv=function(z,X)return z>=0 and H(z/X)or M(z/X)end q.operator.eq=function(z,X)return z==X end q.operator.neq=function(z,X)return z~=X end q.operator.lt=function(z,X)return z<X end q.operator.gt=function(z,X)return z>X end q.operator.le=function(z,X)return z<=X end q.operator.ge=function(z,X)return z>=X end q.operator.land=function(z,X)return z and X end q.operator.lor=function(z,X)return z or X end q.operator.lnot=function(z)return not z end q.operator.concat=function(z,X)return z..X end q.operator.length=function(z)return#z end q.operator.len=q.operator.length function q.clear(z)for X in u(z)do z[X]=nil end return z end function q.each(z,X)for z,S in u(z)do X(S,z)end end function q.eachi(z,X)local S=q.sort(q.select(q.keys(z),q.isInteger))for S,U in R(S)do X(z[U],U)end end function q.at(z,...)local X={}for S,U in R({...})do X[#X+1]=z[U]end return X end function q.adjust(z,X,U)if z[X]==nil then J("\107\101\121 \110\111\116 \101\120\105\115\116\105\110\103 \105\110 \116\097\098\108\101")end local r=q.clone(z)r[X]=S(U)=="\102\117\110\099\116\105\111\110"and U(r[X])or U return r end function q.count(z,X)if X==nil then return q.size(z)end local S=0 for z,U in u(z)do if q.isEqual(U,X)then S=S+1 end end return S end function q.countf(z,X)local S=0 for z,U in u(z)do if X(U,z)then S=S+1 end end return S end function q.allEqual(z,S)local U,r=X(z)for z,X in u(z)do if S then if not S(r,X)then return false end else if not q.isEqual(r,X)then return false end end end return true end function q.cycle(z,S)S=S or 1 if S<=0 then return q.noop end local U,r local k=0 while true do return function()U=U and X(z,U)or X(z)r=not r and U or r if S then k=U==r and k+1 or k if k>S then return end end return z[U],U end end end function q.map(z,X)local S={}for z,U in u(z)do local r,k,y=z,X(U,z)S[y and k or r]=y or k end return S end function q.reduce(z,X,S)for z,U in u(z)do if S==nil then S=U else S=X(S,U)end end return S end function q.best(z,S)local U,r=X(z)for z,X in u(z)do if r==nil then r=X else r=S(r,X)and r or X end end return r end function q.reduceBy(z,X,S,U)return q.reduce(q.select(z,S),X,U)end function q.reduceRight(z,X,S)return q.reduce(q.reverse(z),X,S)end function q.mapReduce(z,X,S)local U={}for z,r in u(z)do U[z]=not S and r or X(S,r)S=U[z]end return U end function q.mapReduceRight(z,X,S)return q.mapReduce(q.reverse(z),X,S)end function q.include(z,X)local U=S(X)=="\102\117\110\099\116\105\111\110"and X or q.isEqual for z,S in u(z)do if U(S,X)then return true end end return false end function q.detect(z,X)local U=S(X)=="\102\117\110\099\116\105\111\110"and X or q.isEqual for z,S in u(z)do if U(S,X)then return z end end end function q.where(z,X)local S=q.select(z,function(z)for S in u(X)do if z[S]~=X[S]then return false end end return true end)return#S>0 and S or nil end function q.findWhere(z,X)local S=q.detect(z,function(z)for S in u(X)do if X[S]~=z[S]then return false end end return true end)return S and z[S]end function q.select(z,X)local S={}for z,U in u(z)do if X(U,z)then S[#S+1]=U end end return S end function q.reject(z,X)local S={}for z,U in u(z)do if not X(U,z)then S[#S+1]=U end end return S end function q.all(z,X)for z,S in u(z)do if not X(S,z)then return false end end return true end function q.invoke(z,X)return q.map(z,function(z,U)if S(z)=="\116\097\098\108\101"then if z[X]then if q.isCallable(z[X])then return z[X](z,U)else return z[X]end else if q.isCallable(X)then return X(z,U)end end elseif q.isCallable(X)then return X(z,U)end end)end function q.pluck(z,X)local S={}for z,U in u(z)do if U[X]then S[#S+1]=U[X]end end return S end function q.max(z,X)return C(z,l,X)end function q.min(z,X)return C(z,T,X)end function q.same(z,X)return q.all(z,function(z)return q.include(X,z)end)and q.all(X,function(X)return q.include(z,X)end)end function q.sort(z,X)L(z,X)return z end function q.sortedk(z,X)local S=q.keys(z)L(S,X)local U=0 return function()U=U+1 return S[U],z[S[U]]end end function q.sortedv(z,X)local S=q.keys(z)X=X or T L(S,function(S,U)return X(z[S],z[U])end)local U=0 return function()U=U+1 return S[U],z[S[U]]end end function q.sortBy(z,X,U)local r=X or q.identity if S(X)=="\115\116\114\105\110\103"then r=function(z)return z[X]end end U=U or T L(z,function(z,X)return U(r(z),r(X))end)return z end function q.groupBy(z,X)local S={}for z,U in u(z)do local r=X(U,z)if S[r]then S[r][#S[r]+1]=U else S[r]={U}end end return S end function q.countBy(z,X)local S={}for z,U in u(z)do local r=X(U,z)S[r]=(S[r]or 0)+1 end return S end function q.size(...)local z={...}local X=z[1]return S(X)=="\116\097\098\108\101"and h(z[1])or h(z)end function q.containsKeys(z,X)for X in u(X)do if not z[X]then return false end end return true end function q.sameKeys(z,X)for z in u(z)do if not X[z]then return false end end for X in u(X)do if not z[X]then return false end end return true end function q.sample(z,X,S)X=X or 1 if X==0 then return{}end if X==1 then if S then c(S)end return{z[x(1,#z)]}end return q.slice(q.shuffle(z,S),1,X)end function q.sampleProb(z,X,S)if S then c(S)end local U={}for z,S in R(z)do if x()<X then U[#U+1]=S end end return U end function q.nsorted(z,X,S)S=S or T X=X or 1 local U,r={},0 for z,S in q.sortedv(z,S)do if r<X then r=r+1 U[r]=S end end return U end function q.shuffle(z,X)if X then c(X)end local S={}for z,X in R(z)do local U=H(x()*z)+1 S[z]=S[U]S[U]=X end return S end function q.pack(...)return{...}end function q.find(z,X,S)for S=S or 1,#z,1 do if q.isEqual(z[S],X)then return S end end end function q.reverse(z)local X={}for S=#z,1,-1 do X[#X+1]=z[S]end return X end function q.fill(z,X,S,U)U=U or q.size(z)for S=S or 1,U,1 do z[S]=X end return z end function q.zeros(z)return q.fill({},0,1,z)end function q.ones(z)return q.fill({},1,1,z)end function q.vector(z,X)return q.fill({},z,1,X)end function q.selectWhile(z,X)local S={}for z,U in R(z)do if X(U,z)then S[z]=U else break end end return S end function q.dropWhile(z,X)local S for z,U in R(z)do if not X(U,z)then S=z break end end if S==nil then return{}end return q.rest(z,S)end function q.sortedIndex(z,X,S,U)local r=S or T if U==true then L(z,r)end for S=1,#z,1 do if not r(z[S],X)then return S end end return#z+1 end function q.indexOf(z,X)for S=1,#z,1 do if z[S]==X then return S end end end function q.lastIndexOf(z,X)local S=q.indexOf(q.reverse(z),X)if S then return(#z-S)+1 end end function q.findIndex(z,X)for S=1,#z,1 do if X(z[S],S)then return S end end end function q.findLastIndex(z,X)local S=q.findIndex(q.reverse(z),X)if S then return(#z-S)+1 end end function q.addTop(z,...)for X,S in R({...})do y(z,1,S)end return z end function q.prepend(z,...)return q.append({...},z)end function q.push(z,...)local X={...}for X,S in R({...})do z[#z+1]=S end return z end function q.shift(z,X)X=w(X or 1,#z)local S={}for X=1,X,1 do local U=z[1]S[#S+1]=U o(z,1)end return b(S)end function q.unshift(z,X)X=w(X or 1,#z)local S={}for X=1,X,1 do local U=z[#z]S[#S+1]=U o(z)end return b(S)end function q.pull(z,...)local X={...}for S=#z,1,-1 do local U=false for X,r in R(X)do if U==false then if q.isEqual(z[S],r)then o(z,S)U=true end end end end return z end function q.removeRange(z,X,S)X=X or 1 S=S or#z if X>S then J("\115\116\097\114\116 \099\097\110\110\111\116 \098\101 \103\114\101\097\116\101\114 \116\104\097\110 \102\105\110\105\115\104\046")end for X=S,X,-1 do o(z,X)end return z end function q.chunk(z,X)local S,U,r,k={},0 for y,L in R(z)do k=X(L,y)r=r==nil and k or r U=k~=r and U+1 or U if not S[U]then S[U]={z[y]}else S[U][#S[U]+1]=z[y]end r=k end return S end function q.slice(z,X,S)local U={}for X=X or 1,S or#z,1 do U[#U+1]=z[X]end return U end function q.first(z,X)X=X or 1 local S={}for X=1,X,1 do S[X]=z[X]end return S end function q.initial(z,X)local S=#z X=X and S-w(X,S)or S-1 local U={}for X=1,X,1 do U[X]=z[X]end return U end function q.last(z,X)local S=#z X=X and S-w(X-1,S-1)or 2 local U={}for X=X,S,1 do U[#U+1]=z[X]end return U end function q.rest(z,X)local S={}for X=X or 1,#z,1 do S[#S+1]=z[X]end return S end function q.nth(z,X)return z[X]end function q.compact(z)local X={}for z,S in u(z)do if S then X[#X+1]=S end end return X end function q.flatten(z,X)X=X or false local U local r={}for z,k in R(z)do if S(k)=="\116\097\098\108\101"then U=X and k or q.flatten(k)for z,X in R(U)do r[#r+1]=X end else r[#r+1]=k end end return r end function q.difference(z,X)if not X then return q.clone(z)end return q.select(z,function(z)return not q.include(X,z)end)end function q.union(...)return q.unique(q.flatten({...}))end function q.intersection(...)local z={...}local X=z[1]o(z,1)local S={}for X,U in R(X)do if q.all(z,function(z)return q.include(z,U)end)then S[#S+1]=U end end return S end function q.disjoint(...)return#q.intersection(...)==0 end function q.symmetricDifference(z,X)return q.difference(q.union(z,X),q.intersection(z,X))end function q.unique(z)local X={}for S=1,#z,1 do if not q.find(X,z[S])then X[#X+1]=z[S]end end return X end function q.isunique(z)return#z==#q.unique(z)end function q.duplicates(z)local X=q.invert(z)local S={}for z,U in R(z)do if X[U]~=z and not q.find(S,U)then S[#S+1]=U end end return S end function q.zip(...)local z={...}local X=q.max(z,function(z)return#z end)local S={}for X=1,X,1 do if not S[X]then S[X]={}end for z,U in R(z)do if U[X]~=nil then S[X][#S[X]+1]=U[X]end end end return S end function q.zipWith(z,...)local X={...}local S=q.max(X,function(z)return#z end)local U={}for S=1,S,1 do U[S]=z(b(q.pluck(X,S)))end return U end function q.append(z,X)local S={}for z,X in R(z)do S[z]=X end for z,X in R(X)do S[#S+1]=X end return S end function q.interleave(...)local z={...}local X=q.max(z,q.size)local S={}for X=1,X,1 do for z,U in R(z)do if U[X]then S[#S+1]=U[X]end end end return S end function q.interpose(z,X)for S=#z,2,-1 do y(z,S,X)end return z end function q.range(z,X,S)if z==nil and(X==nil and S==nil)then return{}elseif z~=nil and(X==nil and S==nil)then z,X,S=d(z),z,d(z)elseif z~=nil and(X~=nil and S==nil)then S=d(X-z)end local U={z}local r=e(H((X-z)/S),0)for X=1,r,1 do U[#U+1]=z+S*X end return U end function q.rep(z,X)local S={}for X=1,X,1 do S[X]=z end return S end function q.powerset(z)local X=#z if X==0 then return{{}}end local S={}for U=1,X,1 do for X=1,(X-U)+1,1 do S[#S+1]=q.slice(z,X,(X+U)-1)end end return S end function q.partition(z,X,S)if X<=0 then return end return Q(function()m(z,X or 1,n,S)end)end function q.overlapping(z,X,S)if X<=1 then return end return Q(function()Z(z,X or 2,n,S)end)end function q.aperture(z,X)if X<=1 then return end return Q(function()v(z,X or 2,n)end)end function q.pairwise(z)return q.aperture(z,2)end function q.permutation(z)return Q(function()A(z,#z,n)end)end function q.concat(z,X,S,U)return P(q.map(z,tostring),X,S,U)end function q.xprod(z,X)local S={}for z,U in R(z)do for z,X in R(X)do S[#S+1]={U;X}end end return S end function q.xpairs(z,X)local S={}for X,U in R(X)do S[X]={z;U}end return S end function q.xpairsRight(z,X)local S={}for X,U in R(X)do S[X]={U;z}end return S end function q.sum(z)local X=0 for z,S in R(z)do X=X+S end return X end function q.product(z)local X=1 for z,S in R(z)do X=X*S end return X end function q.mean(z)return q.sum(z)/#z end function q.median(z)local X=q.sort(q.clone(z))local S=#X if S==0 then return elseif S==1 then return X[1]end local U=M(S/2)return S%2==0 and(X[U]+X[U+1])/2 or X[U]end function q.noop()return end function q.identity(z)return z end function q.call(z,...)return z(...)end function q.constant(z)return function()return z end end function q.applySpec(z)return function(...)local X={}for z,S in u(z)do X[z]=S(...)end return X end end function q.thread(z,...)local X=z local U={...}for z,U in R(U)do if S(U)=="\102\117\110\099\116\105\111\110"then X=U(X)elseif S(U)=="\116\097\098\108\101"then local z=U[1]o(U,1)X=q.reduce(U,z,X)end end return X end function q.threadRight(z,...)local X=z local U={...}for z,U in R(U)do if S(U)=="\102\117\110\099\116\105\111\110"then X=U(X)elseif S(U)=="\116\097\098\108\101"then local z=U[1]o(U,1)y(U,X)X=q.reduce(U,z)end end return X end function q.dispatch(...)local z={...}return function(...)for z,X in R(z)do local S={X(...)}if#S>0 then return b(S)end end end end function q.memoize(z)local X=r({},{__mode="\107\118"})return function(S)if X[S]==nil then X[S]=z(S)end return X[S]end end function q.unfold(z,X)local S,U={}while true do U,X=z(X)if U~=nil then S[#S+1]=U else break end end return S end function q.once(z)local X=0 local S={}return function(...)X=X+1 if X<=1 then S={...}end return z(b(S))end end function q.before(z,X)local S=0 local U={}return function(...)S=S+1 if S<=X then U={...}end return z(b(U))end end function q.after(z,X)local S,U=X,0 return function(...)U=U+1 if U>=S then return z(...)end end end function q.compose(...)local z=q.reverse({...})return function(...)local X,S=true for z,U in R(z)do if X then X=false S=U(...)else S=U(S)end end return S end end function q.pipe(z,...)return(q.compose(...))(z)end function q.complement(z)return function(...)return not z(...)end end function q.juxtapose(z,...)local X={}for S,U in R({...})do X[S]=U(z)end return b(X)end function q.wrap(z,X)return function(...)return X(z,...)end end function q.times(z,X)local S={}for X=1,X or 1,1 do S[X]=z(X)end return S end function q.bind(z,X)return function(...)return z(X,...)end end function q.bind2(z,X)return function(S,...)return z(S,X,...)end end function q.bindn(z,...)local X={...}return function(...)return z(b(q.append(X,{...})))end end function q.bindall(z,...)local X={...}for X,S in R(X)do local U=z[S]if U then z[S]=q.bind(U,z)end end return z end function q.cond(z)return function(...)for z,X in R(z)do if X[1](...)then return X[2](...)end end end end function q.both(...)local z={...}return function(...)for z,X in R(z)do if not X(...)then return false end end return true end end function q.either(...)local z={...}return function(...)for z,X in R(z)do if X(...)then return true end end return false end end function q.neither(...)local z={...}return function(...)for z,X in R(z)do if X(...)then return false end end return true end end function q.uniqueId(z)K=K+1 if z then if S(z)=="\115\116\114\105\110\103"then return z:format(K)elseif S(z)=="\102\117\110\099\116\105\111\110"then return z(K)end end return K end function q.iterator(z,X,S)local U=0 return function()U=U+1 if S and U>S then return end X=z(X)return X end end function q.skip(z,X)for X=1,X or 1,1 do if z()==nil then return end end return z end function q.tabulate(...)local z={}for X in...do z[#z+1]=X end return z end function q.iterlen(...)local z=0 for X in...do z=z+1 end return z end function q.castArray(z)return S(z)~="\116\097\098\108\101"and{z}or z end function q.flip(z)return function(...)return z(b(q.reverse({...})))end end function q.nthArg(z)return function(...)local X={...}return X[z<0 and(#X+z)+1 or z]end end function q.unary(z)return function(...)local X={...}return z(X[1])end end function q.ary(z,X)X=X or 1 return function(...)local S={...}local U={}for z=1,X,1 do U[z]=S[z]end return z(b(U))end end function q.noarg(z)return function()return z()end end function q.rearg(z,X)return function(...)local S={...}local U={}for z,X in R(X)do U[z]=S[X]end return z(b(U))end end function q.over(...)local z={...}return function(...)local X={}for z,S in R(z)do X[#X+1]=S(...)end return X end end function q.overEvery(...)local z=q.over(...)return function(...)return q.reduce(z(...),function(z,X)return z and X end)end end function q.overSome(...)local z=q.over(...)return function(...)return q.reduce(z(...),function(z,X)return z or X end)end end function q.overArgs(z,...)local X={...}return function(...)local S={...}for z=1,#X,1 do local U=X[z]if S[z]then S[z]=U(S[z])end end return z(b(S))end end function q.converge(z,X,S)return function(...)return z(X(...),S(...))end end function q.partial(z,...)local X={...}return function(...)local S={...}local U={}for z,X in R(X)do U[z]=X=="\095"and q.shift(S)or X end return z(b(q.append(U,S)))end end function q.partialRight(z,...)local X={...}return function(...)local S={...}local U={}for z=1,#X,1 do U[z]=X[z]=="\095"and q.shift(S)or X[z]end return z(b(q.append(S,U)))end end function q.curry(z,X)X=X or 2 local S={}local function U(r)if X==1 then return z(r)end if r~=nil then S[#S+1]=r end if#S<X then return U else local X={z(b(S))}S={}return b(X)end end return U end function q.time(z,...)local X=Y()local S={z(...)}return Y()-X,b(S)end function q.keys(z)local X={}for z in u(z)do X[#X+1]=z end return X end function q.values(z)local X={}for z,S in u(z)do X[#X+1]=S end return X end function q.path(z,...)local X,S=z,{...}for z,S in R(S)do if X[S]==nil then return end X=X[S]end return X end function q.spreadPath(z,...)local X={...}for X,S in R(X)do if z[S]then for X,U in u(z[S])do z[X]=U z[S][X]=nil end end end return z end function q.flattenPath(z,...)local X={...}for X,S in R(X)do if z[S]then for X,S in u(z[S])do z[X]=S end end end return z end function q.kvpairs(z)local X={}for z,S in u(z)do X[#X+1]={z,S}end return X end function q.toObj(z)local X={}for z,S in R(z)do X[S[1]]=S[2]end return X end function q.invert(z)local X={}for z,S in u(z)do X[S]=z end return X end function q.property(z)return function(X)return X[z]end end function q.propertyOf(z)return function(X)return z[X]end end function q.toBoolean(z)return not(not z)end function q.extend(z,...)local X={...}for X,U in R(X)do if S(U)=="\116\097\098\108\101"then for X,S in u(U)do z[X]=S end end end return z end function q.functions(z,X)z=z or q local U={}for z,X in u(z)do if S(X)=="\102\117\110\099\116\105\111\110"then U[#U+1]=z end end if X then local S=k(z)if S and S.__index then local z=q.functions(S.__index,X)for z,X in R(z)do U[#U+1]=X end end end return U end function q.clone(z,X)if S(z)~="\116\097\098\108\101"then return z end local U={}for z,r in u(z)do if S(r)=="\116\097\098\108\101"then if not X then U[z]=q.clone(r,X)else U[z]=r end else U[z]=r end end return U end function q.tap(z,X)X(z)return z end function q.has(z,X)return z[X]~=nil end function q.pick(z,...)local X=q.flatten({...})local S={}for X,U in u(X)do if z[U]~=nil then S[U]=z[U]end end return S end function q.omit(z,...)local X=q.flatten({...})local S={}for z,U in u(z)do if not q.include(X,z)then S[z]=U end end return S end function q.template(z,X)if not X then return z end for X,S in u(X)do if not z[X]then z[X]=S end end return z end function q.isEqual(z,X,U)local r=S(z)local y=S(X)if r~=y then return false end if r~="\116\097\098\108\101"then return z==X end local L=k(z)local o=k(X)if U then if(L or o)and(L.__eq or o.__eq)then return L.__eq(z,X)or o.__eq(X,z)or z==X end end if q.size(z)~=q.size(X)then return false end local P for z,S in u(z)do P=X[z]if P==nil or not q.isEqual(S,P,U)then return false end end for X in u(X)do if z[X]==nil then return false end end return true end function q.result(z,X)if z[X]then if q.isCallable(z[X])then return z[X](z)else return z[X]end end if q.isCallable(X)then return X(z)end end function q.isTable(z)return S(z)=="\116\097\098\108\101"end function q.isCallable(z)return S(z)=="\102\117\110\099\116\105\111\110"or S(z)=="\116\097\098\108\101"and(k(z)and(k(z)).__call~=nil)or false end function q.isArray(z)if not(S(z)=="\116\097\098\108\101")then return false end local X=0 for S in u(z)do X=X+1 if z[X]==nil then return false end end return true end function q.isIterable(z)return q.toBoolean(U(u,z))end function q.type(z)local X=S(z)if X=="\117\115\101\114\100\097\116\097"then local X=k(z)if X==k(io.stdout)then return"\102\105\108\101"end end return X end function q.isEmpty(z)if z==nil then return true end if S(z)=="\115\116\114\105\110\103"then return#z==0 end if S(z)=="\116\097\098\108\101"then return X(z)==nil end return true end function q.isString(z)return S(z)=="\115\116\114\105\110\103"end function q.isFunction(z)return S(z)=="\102\117\110\099\116\105\111\110"end function q.isNil(z)return z==nil end function q.isNumber(z)return S(z)=="\110\117\109\098\101\114"end function q.isNaN(z)return S(z)=="\110\117\109\098\101\114"and z~=z end function q.isFinite(z)if S(z)~="\110\117\109\098\101\114"then return false end return z>-D and z<D end function q.isBoolean(z)return S(z)=="\098\111\111\108\101\097\110"end function q.isInteger(z)return S(z)=="\110\117\109\098\101\114"and H(z)==z end do q.forEach=q.each q.forEachi=q.eachi q.update=q.adjust q.alleq=q.allEqual q.loop=q.cycle q.collect=q.map q.inject=q.reduce q.foldl=q.reduce q.injectr=q.reduceRight q.foldr=q.reduceRight q.mapr=q.mapReduce q.maprr=q.mapReduceRight q.any=q.include q.some=q.include q.contains=q.include q.filter=q.select q.discard=q.reject q.every=q.all q.takeWhile=q.selectWhile q.rejectWhile=q.dropWhile q.pop=q.shift q.remove=q.pull q.rmRange=q.removeRange q.chop=q.removeRange q.sub=q.slice q.head=q.first q.take=q.first q.tail=q.rest q.without=q.difference q.diff=q.difference q.symdiff=q.symmetricDifference q.xor=q.symmetricDifference q.uniq=q.unique q.isuniq=q.isunique q.transpose=q.zip q.part=q.partition q.perm=q.permutation q.transposeWith=q.zipWith q.intersperse=q.interpose q.sliding=q.aperture q.mirror=q.invert q.join=q.concat q.average=q.mean q.always=q.constant q.cache=q.memoize q.juxt=q.juxtapose q.uid=q.uniqueid q.iter=q.iterator q.nAry=q.ary q.methods=q.functions q.choose=q.pick q.drop=q.omit q.defaults=q.template q.compare=q.isEqual q.matches=q.isEqual end do local X={}local U={}U.__index=X local function k(z)return r({_value=z,_wrapped=true},U)end r(U,{__call=function(z,X)return k(X)end,__index=function(z,S,...)return X[S]end})function U.chain(z)return k(z)end function U.value(z)return z._value end X.chain,X.value=U.chain,U.value for z,U in u(q)do if z~="\111\112\101\114\097\116\111\114"then X[z]=function(z,...)local X=S(z)=="\116\097\098\108\101"and F(z,"\095\119\114\097\112\112\101\100")or false if X then local X=z._value local S=U(X,...)return k(S)else return U(z,...)end end end end X.operator=q.operator X.op=q.operator X.import=function(z,X)z=z or _ENV or _G local S=q.functions()for S,U in R(S)do if F(z,U)~=nil then if not X then rawset(z,U,q[U])end else rawset(z,U,q[U])end end return z end U._VERSION="\077\111\115\101\115 \118"..z U._URL="\104\116\116\112\058\047\047\103\105\116\104\117\098\046\099\111\109\047\089\111\110\097\098\097\047\077\111\115\101\115"U._LICENSE="\077\073\084 \060\104\116\116\112\058\047\047\114\097\119\046\103\105\116\104\117\098\117\115\101\114\099\111\110\116\101\110\116\046\099\111\109\047\089\111\110\097\098\097\047\077\111\115\101\115\047\109\097\115\116\101\114\047\076\073\067\069\078\083\069\062"U._DESCRIPTION="\117\116\105\108\105\116\121-\098\101\108\116 \108\105\098\114\097\114\121 \102\111\114 \102\117\110\099\116\105\111\110\097\108 \112\114\111\103\114\097\109\109\105\110\103 \105\110 \076\117\097"return U end
--- Utility-belt library for functional programming in Lua ([source](http://github.com/Yonaba/Moses))
-- @author [Roland Yonaba](http://github.com/Yonaba)
-- @copyright 2012-2018
-- @license [MIT](http://www.opensource.org/licenses/mit-license.php)
-- @release 2.1.0
-- @module moses
-- @set sort=true

local _MODULEVERSION = '2.1.0'

-- Internalisation
local next, type, pcall          = next, type, pcall
local setmetatable, getmetatable = setmetatable, getmetatable
local t_insert, t_sort           = table.insert, table.sort
local t_remove,t_concat          = table.remove, table.concat
local randomseed, random, huge   = math.randomseed, math.random, math.huge
local floor, max, min, ceil      = math.floor, math.max, math.min, math.ceil
local wrap                       = coroutine.wrap
local yield                      = coroutine.yield
local rawget                     = rawget
local unpack                     = table.unpack or unpack
local pairs,ipairs               = pairs,ipairs
local error                      = error
local clock                      = os.clock
local M                          = {}


-- ======== Private helpers

local function f_max(a,b) return a>b end
local function f_min(a,b) return a<b end

local function count(t)  -- raw count of items in an map-table
  local i = 0
    for k,v in pairs(t) do i = i + 1 end
  return i
end

local function extract(list,comp,transform,...) -- extracts value from a list
  transform = transform or M.identity
  local _ans  
  for k,v in pairs(list) do
    if not _ans then _ans = transform(v,...)
    else
      local val = transform(v,...)
      _ans = comp(_ans,val) and _ans or val
    end
  end
  return _ans
end

local function partgen(t, n, f, pad) -- generates array partitions
  for i = 0, #t, n do
    local s = M.slice(t, i+1, i+n)
    if #s>0 then 
			while (#s < n and pad) do s[#s+1] = pad end			
			f(s)
		end
  end
end

local function partgen2(t, n, f, pad) -- generates overlapping array partitions
  for i = 0, #t, n-1 do
    local s = M.slice(t, i+1, i+n)
    if #s>0 and i+1<#t then 
			while (#s < n and pad) do s[#s+1] = pad end
			f(s)
		end
  end
end

local function partgen3(t, n, f, pad) -- generates sliding array partitions
  for i = 0, #t, 1 do
    local s = M.slice(t, i+1, i+n)
    if #s>0 and i+n<=#t then 
			while (#s < n and pad) do s[#s+1] = pad end
			f(s)
		end
  end
end

local function permgen(t, n, f) -- taken from PiL: http://www.lua.org/pil/9.3.html
  if n == 0 then f(t) end
  for i = 1,n do
    t[n], t[i] = t[i], t[n]
    permgen(t, n-1, f)
    t[n], t[i] = t[i], t[n]
  end
end

local function signum(a) return a>=0 and 1 or -1 end

-- Internal counter for unique ids generation
local unique_id_counter = -1

--- Operator functions
-- @section Operator functions

M.operator = {}
--- Returns a + b. <em>Aliased as `op.add`</em>.
-- @name operator.add
-- @param a a value
-- @param b a value
-- @return a + b
M.operator.add = function(a,b) return a + b end

--- Returns a - b. <em>Aliased as `op.sub`</em>.
-- @name operator.sub
-- @param a a value
-- @param b a value
-- @return a - b
M.operator.sub = function(a,b) return a - b end

--- Returns a * b. <em>Aliased as `op.mul`</em>.
-- @name operator.mul
-- @param a a value
-- @param b a value
-- @return a * b
M.operator.mul = function(a,b) return a * b end

--- Returns a / b. <em>Aliased as `op.div`</em>.
-- @name operator.div
-- @param a a value
-- @param b a value
-- @return a / b
M.operator.div = function(a,b) return a / b end

--- Returns a % b. <em>Aliased as `op.mod`</em>.
-- @name operator.mod
-- @param a a value
-- @param b a value
-- @return a % b
M.operator.mod = function(a,b) return a % b end

--- Returns a ^ b. <em>Aliased as `op.exp`, `op.pow`</em>.
-- @name operator.exp
-- @param a a value
-- @param b a value
-- @return a ^ b
M.operator.exp = function(a,b) return a ^ b end
M.operator.pow = M.operator.exp

--- Returns -a. <em>Aliased as `op.unm`, `op.neg`</em>.
-- @name operator.unm
-- @param a a value
-- @return -a
M.operator.unm = function(a) return -a end
M.operator.neg = M.operator.unm

--- Performs floor division (//) between `a` and `b`. It rounds the quotient towards minus infinity.
-- <em>Aliased as `op.floordiv`</em>.
-- @name operator.floordiv
-- @param a a value
-- @param b a value
-- @return a // b
M.operator.floordiv = function(a, b) return floor(a/b) end 

--- Performs integer division between `a` and `b`. <em>Aliased as `op.intdiv`</em>.
-- @name operator.intdiv
-- @param a a value
-- @param b a value
-- @return a / b
M.operator.intdiv = function(a,b)
  return a>=0 and floor(a/b) or ceil(a/b) 
end

--- Checks if a equals b. <em>Aliased as `op.eq`</em>.
-- @name operator.eq
-- @param a a value
-- @param b a value
-- @return a == b
M.operator.eq = function(a,b) return a == b end

--- Checks if a not equals b. <em>Aliased as `op.neq`</em>.
-- @name operator.neq
-- @param a a value
-- @param b a value
-- @return a ~= b
M.operator.neq = function(a,b) return a ~= b end

--- Checks if a is strictly less than b. <em>Aliased as `op.lt`</em>.
-- @name operator.lt
-- @param a a value
-- @param b a value
-- @return a < b
M.operator.lt = function(a,b) return a < b end

--- Checks if a is strictly greater than b. <em>Aliased as `op.gt`</em>.
-- @name operator.gt
-- @param a a value
-- @param b a value
-- @return a > b
M.operator.gt = function(a,b) return a > b end

--- Checks if a is less or equal to b. <em>Aliased as `op.le`</em>.
-- @name operator.le
-- @param a a value
-- @param b a value
-- @return a <= b
M.operator.le = function(a,b) return a <= b end

--- Checks if a is greater or equal to b. <em>Aliased as `op.ge`</em>.
-- @name operator.ge
-- @param a a value
-- @param b a value
-- @return a >= b
M.operator.ge = function(a,b) return a >= b end

--- Returns logical a and b. <em>Aliased as `op.land`</em>.
-- @name operator.ge
-- @param a a value
-- @param b a value
-- @return a and b
M.operator.land = function(a,b) return a and b end

--- Returns logical a or b. <em>Aliased as `op.lor`</em>.
-- @name operator.lor
-- @param a a value
-- @param b a value
-- @return a or b
M.operator.lor = function(a,b) return a or b end

--- Returns logical not a. <em>Aliased as `op.lnot`</em>.
-- @name operator.lnot
-- @param a a value
-- @return not a
M.operator.lnot = function(a) return not a end

--- Returns concatenation of a and b. <em>Aliased as `op.concat`</em>.
-- @name operator.concat
-- @param a a value
-- @param b a value
-- @return a .. b
M.operator.concat = function(a,b) return a..b end

--- Returns the length of a. <em>Aliased as `op.len`</em>.
-- @name operator.length
-- @param a a value
-- @return #a
M.operator.length = function(a) return #a end
M.operator.len = M.operator.length

--- Table functions
-- @section Table functions

--- Clears a table. All its values become nil.
-- @name clear
-- @param t a table
-- @return the given table, cleared.
function M.clear(t)
	for k in pairs(t) do t[k] = nil end
	return t
end



--- Iterates on key-value pairs, calling `f (v, k)` at every step.
-- <br/><em>Aliased as `forEach`</em>.
-- @name each
-- @param t a table
-- @param f a function, prototyped as `f (v, k)`
-- @see eachi
function M.each(t, f)
  for index,value in pairs(t) do
    f(value, index)
  end
end

--- Iterates on integer key-value pairs, calling `f(v, k)` every step. 
-- Only applies to values located at integer keys. The table can be a sparse array. 
-- Iteration will start from the lowest integer key found to the highest one.
-- <br/><em>Aliased as `forEachi`</em>.
-- @name eachi
-- @param t a table
-- @param f a function, prototyped as `f (v, k)`
-- @see each
function M.eachi(t, f)
  local lkeys = M.sort(M.select(M.keys(t), M.isInteger))
  for k, key in ipairs(lkeys) do
    f(t[key], key)
  end
end

--- Collects values at given keys and return them wrapped in an array.
-- @name at
-- @param t a table
-- @param ... A variable number of keys to collect values
-- @return an array-list of values
function M.at(t, ...)
  local values = {}
  for i, key in ipairs({...}) do values[#values+1] = t[key] end
  return values
end

--- Adjusts the value at a given key using a function or a value. In case `f` is a function, 
-- it should be prototyped `f(v)`. It does not mutate the given table, but rather
-- returns a new array. In case the given `key` does not exist in `t`, it throws an error.
-- @param t a table
-- @param key a key
-- @param f a function, prototyped as `f(v)` or a value
function M.adjust(t, key, f)
  if (t[key] == nil) then error("key not existing in table") end
  local _t = M.clone(t)
  _t[key] = type(f) == 'function' and f(_t[key]) or f
  return _t
end

--- Counts occurrences of a given value in a table. Uses @{isEqual} to compare values.
-- @name count
-- @param t a table
-- @param[opt] val a value to be searched in the table. If not given, the @{size} of the table will be returned
-- @return the count of occurrences of the given value
-- @see countf
-- @see size
function M.count(t, val)
  if val == nil then return M.size(t) end
  local count = 0
  for k, v in pairs(t) do
    if M.isEqual(v, val) then count = count + 1 end
  end
  return count
end

--- Counts the number of values passing a predicate test. Same as @{count}, but uses an iterator. 
-- Returns the count for values passing the test `f (v, k)`
-- @name countf
-- @param t a table
-- @param f an iterator function, prototyped as `f (v, k)`
-- @return the count of values validating the predicate
-- @see count
-- @see size
function M.countf(t, f)
  local count = 0
  for k, v in pairs(t) do
    if f(v, k) then count = count + 1 end
  end
  return count
end

--- Checks if all values in a collection are equal. Uses an optional `comp` function which is used
-- to compare values and defaults to @{isEqual} when not given.
-- <br/><em>Aliased as `alleq`</em>.
-- @name allEqual
-- @param t a table
-- @param[opt] comp a comparison function. Defaults to `isEqual`
-- @return `true` when all values in `t` are equal, `false` otherwise.
-- @see isEqual
function M.allEqual(t, comp)
  local k, pivot = next(t)
  for k, v in pairs(t) do
    if comp then 
      if not comp(pivot, v) then return false end
    else
      if not M.isEqual(pivot, v) then return false end
    end
  end
  return true
end

--- Loops `n` times through a table. In case `n` is omitted, it will loop forever.
-- In case `n` is lower or equal to 0, it returns an empty function.
-- <br/><em>Aliased as `loop`</em>.
-- @name cycle
-- @param t a table
-- @param[opt] n the number of loops
-- @return an iterator function yielding value-key pairs from the passed-in table.
function M.cycle(t, n)
  n = n or 1
  if n<=0 then return M.noop end
  local k, fk
  local i = 0
  while true do
    return function()
      k = k and next(t,k) or next(t)
      fk = not fk and k or fk
      if n then
        i = (k==fk) and i+1 or i
        if i > n then
          return
        end
      end
      return t[k], k
    end
  end
end

--- Maps `f (v, k)` on value-key pairs, collects and returns the results.
-- <br/><em>Aliased as `collect`</em>.
-- @name map
-- @param t a table
-- @param f  an iterator function, prototyped as `f (v, k)`
-- @return a table of results
function M.map(t, f)
  local _t = {}
  for index,value in pairs(t) do
    local k, kv, v = index, f(value, index)
    _t[v and kv or k] = v or kv
  end
  return _t
end

--- Reduces a table, left-to-right. Folds the table from the first element to the last element
-- to a single value, using a given iterator and an initial state.
-- The iterator takes a state and a value and returns a new state.
-- <br/><em>Aliased as `inject`, `foldl`</em>.
-- @name reduce
-- @param t a table
-- @param f an iterator function, prototyped as `f (state, value)`
-- @param[opt] state an initial state of reduction. Defaults to the first value in the table.
-- @return the final state of reduction
-- @see best
-- @see reduceRight
-- @see reduceBy
function M.reduce(t, f, state)
  for k,value in pairs(t) do
    if state == nil then state = value
    else state = f(state,value)
    end
  end
  return state
end

--- Returns the best value passing a selector function. Acts as a special case of
-- @{reduce}, using the first value in `t` as an initial state. It thens folds the given table,
-- testing each of its values `v` and selecting the value passing the call `f(state,v)` every time.
-- @name best
-- @param t a table
-- @param f an iterator function, prototyped as `f (state, value)`
-- @return the final state of reduction
-- @see reduce
-- @see reduceRight
-- @see reduceBy
function M.best(t, f)
  local _, state = next(t)
  for k,value in pairs(t) do
    if state == nil then state = value
    else state = f(state,value) and state or value
    end
  end
  return state
end

--- Reduces values in a table passing a given predicate. Folds the table left-to-right, considering
-- only values validating a given predicate.
-- @name reduceBy
-- @param t a table
-- @param f an iterator function, prototyped as `f (state, value)`
-- @param pred a predicate function `pred (v, k)` to select values to be considered for reduction
-- @param[opt] state an initial state of reduction. Defaults to the first value in the table of selected values.
-- @param[optchain] ... optional args to be passed to `pred`
-- @return the final state of reduction
-- @see reduce
-- @see best
-- @see reduceRight
function M.reduceBy(t, f, pred, state)
	return M.reduce(M.select(t, pred), f, state)
end

--- Reduces a table, right-to-left. Folds the table from the last element to the first element 
-- to single value, using a given iterator and an initial state.
-- The iterator takes a state and a value, and returns a new state.
-- <br/><em>Aliased as `injectr`, `foldr`</em>.
-- @name reduceRight
-- @param t a table
-- @param f an iterator function, prototyped as `f (state, value)`
-- @param[opt] state an initial state of reduction. Defaults to the last value in the table.
-- @return the final state of reduction
-- @see reduce
-- @see best
-- @see reduceBy
function M.reduceRight(t, f, state)
  return M.reduce(M.reverse(t),f,state)
end

--- Reduces a table while saving intermediate states. Folds the table left-to-right
-- using a given iterator and an initial state. The iterator takes a state and a value, 
-- and returns a new state. The result is an array of intermediate states.
-- <br/><em>Aliased as `mapr`</em>
-- @name mapReduce
-- @param t a table
-- @param f an iterator function, prototyped as `f (state, value)`
-- @param[opt] state an initial state of reduction. Defaults to the first value in the table.
-- @return an array of states
-- @see mapReduceRight
function M.mapReduce(t, f, state)
  local _t = {}
  for i,value in pairs(t) do
    _t[i] = not state and value or f(state,value)
    state = _t[i]
  end
  return _t
end

--- Reduces a table while saving intermediate states. Folds the table right-to-left
-- using a given iterator and an initial state. The iterator takes a state and a value, 
-- and returns a new state. The result is an array of intermediate states.
-- <br/><em>Aliased as `maprr`</em>
-- @name mapReduceRight
-- @param t a table
-- @param f an iterator function, prototyped as `f (state, value)`
-- @param[opt] state an initial state of reduction. Defaults to the last value in the table.
-- @return an array of states
-- @see mapReduce
function M.mapReduceRight(t, f, state)
  return M.mapReduce(M.reverse(t),f,state)
end

--- Performs a linear search for a value in a table. It does not work for nested tables.
-- The given value can be a function prototyped as `f (v, value)` which should return true when
-- any v in the table equals the value being searched. 
-- <br/><em>Aliased as `any`, `some`, `contains`</em>
-- @name include
-- @param t a table
-- @param value a value to search for
-- @return a boolean : `true` when found, `false` otherwise
-- @see detect
function M.include(t, value)
  local _iter = (type(value) == 'function') and value or M.isEqual
  for k,v in pairs(t) do
    if _iter(v,value) then return true end
  end
  return false
end

--- Performs a linear search for a value in a table. Returns the key of the value if found.
-- The given value can be a function prototyped as `f (v, value)` which should return true when
-- any v in the table equals the value being searched. This function is similar to @{find}, 
-- which is mostly meant to work with array.
-- @name detect
-- @param t a table
-- @param value a value to search for
-- @return the key of the value when found or __nil__
-- @see include
-- @see find
function M.detect(t, value)
  local _iter = (type(value) == 'function') and value or M.isEqual
  for key,arg in pairs(t) do
    if _iter(arg,value) then return key end
  end
end

--- Returns all values having specified keys `props`.
-- @name where
-- @param t a table
-- @param props a set of keys
-- @return an array of values from the passed-in table
-- @see findWhere
function M.where(t, props)
	local r = M.select(t, function(v)
		for key in pairs(props) do
			if v[key] ~= props[key] then return false end
		end
		return true
	end)
	return #r > 0 and r or nil
end

--- Returns the first value having specified keys `props`.
-- @name findWhere
-- @param t a table
-- @param props a set of keys
-- @return a value from the passed-in table
-- @see where
function M.findWhere(t, props)
  local index = M.detect(t, function(v)
    for key in pairs(props) do
      if props[key] ~= v[key] then return false end
    end
    return true
  end)
  return index and t[index]
end

--- Selects and returns values passing an iterator test.
-- <br/><em>Aliased as `filter`</em>.
-- @name select
-- @param t a table
-- @param f an iterator function, prototyped as `f (v, k)`
-- @return the selected values
-- @see reject
function M.select(t, f)
  local _t = {}
  for index,value in pairs(t) do
    if f(value,index) then _t[#_t+1] = value end
  end
  return _t
end

--- Clones a table while dropping values passing an iterator test.
-- <br/><em>Aliased as `discard`</em>
-- @name reject
-- @param t a table
-- @param f an iterator function, prototyped as `f (v, k)`
-- @return the remaining values
-- @see select
function M.reject(t, f)
  local _t = {}
  for index,value in pairs (t) do
    if not f(value,index) then _t[#_t+1] = value end
  end
  return _t
end

--- Checks if all values in a table are passing an iterator test.
-- <br/><em>Aliased as `every`</em>
-- @name all
-- @param t a table
-- @param f an iterator function, prototyped as `f (v, k)`
-- @return `true` if all values passes the predicate, `false` otherwise
function M.all(t, f)
  for index,value in pairs(t) do
    if not f(value,index) then return false end
  end
  return true
end

--- Invokes a method on each value in a table.
-- @name invoke
-- @param t a table
-- @param method a function, prototyped as `f (v, k)`
-- @return the result of the call `f (v, k)`
-- @see pluck
function M.invoke(t, method)
  return M.map(t, function(v, k)
    if (type(v) == 'table') then
      if v[method] then
        if M.isCallable(v[method]) then
          return v[method](v,k)
        else
          return v[method]
        end
      else
        if M.isCallable(method) then
          return method(v,k)
        end
      end
    elseif M.isCallable(method) then
      return method(v,k)
    end
  end)
end

--- Extracts values in a table having a given key.
-- @name pluck
-- @param t a table
-- @param key a key, will be used to index in each value: `value[key]`
-- @return an array of values having the given key
function M.pluck(t, key)
  local _t = {}
  for k, v in pairs(t) do
    if v[key] then _t[#_t+1] = v[key] end
  end
  return _t
end

--- Returns the max value in a collection. If a `transform` function is passed, it will
-- be used to evaluate values by which all objects will be sorted.
-- @name max
-- @param t a table
-- @param[opt] transform a transformation function, prototyped as `transform (v, k)`, defaults to @{identity}
-- @return the max value found
-- @see min
function M.max(t, transform)
  return extract(t, f_max, transform)
end

--- Returns the min value in a collection. If a `transform` function is passed, it will
-- be used to evaluate values by which all objects will be sorted.
-- @name min
-- @param t a table
-- @param[opt] transform a transformation function, prototyped as `transform (v, k)`, defaults to @{identity}
-- @return the min value found
-- @see max
function M.min(t, transform)
  return extract(t, f_min, transform)
end

--- Checks if two tables are the same. It compares if both tables features the same values,
-- but not necessarily at the same keys.
-- @name same
-- @param a a table
-- @param b another table
-- @return `true` or `false`
function M.same(a, b)
  return M.all(a, function(v) return M.include(b,v) end) 
     and M.all(b, function(v) return M.include(a,v) end)
end

--- Sorts a table, in-place. If a comparison function is given, it will be used to sort values.
-- @name sort
-- @param t a table
-- @param[opt] comp a comparison function prototyped as `comp (a, b)`, defaults to <tt><</tt> operator.
-- @return the given table, sorted.
-- @see sortBy
function M.sort(t, comp)
  t_sort(t, comp)
  return t
end

--- Iterates on values with respect to key order. Keys are sorted using `comp` function
-- which defaults to `math.min`. It returns upon each call a `key, value` pair.
-- @name sortedk
-- @param t a table 
-- @param[opt] comp a comparison function. Defaults to `<` operator
-- @return an iterator function 
-- @see sortedv 
function M.sortedk(t, comp)
  local keys = M.keys(t)
  t_sort(keys, comp)
  local i = 0
  return function ()
    i = i + 1
    return keys[i], t[keys[i]]
  end
end

--- Iterates on values with respect to values order. Values are sorted using `comp` function
-- which defaults to `math.min`. It returns upon each call a `key, value` pair.
-- @name sortedv
-- @param t a table 
-- @param[opt] comp a comparison function. Defaults to `<` operator
-- @return an iterator function 
-- @see sortedk
function M.sortedv(t, comp)
  local keys = M.keys(t)
  comp = comp or f_min
  t_sort(keys, function(a,b) return comp(t[a],t[b]) end)
  local i = 0
  return function ()
    i = i + 1
    return keys[i], t[keys[i]]
  end
end

--- Sorts a table in-place using a transform. Values are ranked in a custom order of the results of
-- running `transform (v)` on all values. `transform` may also be a string name property  sort by. 
-- `comp` is a comparison function.
-- @name sortBy
-- @param t a table
-- @param[opt] transform a `transform` function to sort elements prototyped as `transform (v)`. Defaults to @{identity}
-- @param[optchain] comp a comparison function, defaults to the `<` operator
-- @return a new array of sorted values
-- @see sort
function M.sortBy(t, transform, comp)
	local f = transform or M.identity
	if (type(transform) == 'string') then
		f = function(t) return t[transform] end
	end
	comp = comp or f_min	
	t_sort(t, function(a,b) return comp(f(a), f(b)) end)
	return t
end

--- Splits a table into subsets groups.
-- @name groupBy
-- @param t a table
-- @param iter an iterator function, prototyped as `iter (v, k)`
-- @return a table of subsets groups
function M.groupBy(t, iter)
  local _t = {}
  for k,v in pairs(t) do
    local _key = iter(v,k)
    if _t[_key] then _t[_key][#_t[_key]+1] = v
    else _t[_key] = {v}
    end
  end
  return _t
end

--- Groups values in a collection and counts them.
-- @name countBy
-- @param t a table
-- @param iter an iterator function, prototyped as `iter (v, k)`
-- @return a table of subsets groups names paired with their count
function M.countBy(t, iter)
  local stats = {}
  for i,v in pairs(t) do
    local key = iter(v,i)
    stats[key] = (stats[key] or 0)+1
  end
  return stats
end

--- Counts the number of values in a collection. If being passed more than one argument
-- it will return the count of all passed-in arguments.
-- @name size
-- @param[opt] ... Optional variable number of arguments
-- @return a count
-- @see count
-- @see countf
function M.size(...)
  local args = {...}
  local arg1 = args[1]
  return (type(arg1) == 'table') and count(args[1]) or count(args)
end

--- Checks if all the keys of `other` table exists in table `t`. It does not
-- compares values. The test is not commutative, i.e table `t` may contains keys
-- not existing in `other`.
-- @name containsKeys
-- @param t a table
-- @param other another table
-- @return `true` or `false`
-- @see sameKeys
function M.containsKeys(t, other)
  for key in pairs(other) do
    if not t[key] then return false end
  end
  return true
end

--- Checks if both given tables have the same keys. It does not compares values.
-- @name sameKeys
-- @param tA a table
-- @param tB another table
-- @return `true` or `false`
-- @see containsKeys
function M.sameKeys(tA, tB)
  for key in pairs(tA) do
    if not tB[key] then return false end
  end
  for key in pairs(tB) do
    if not tA[key] then return false end
  end
  return true
end

--- Array functions
-- @section Array functions

--- Samples `n` random values from an array. If `n` is not specified, returns a single element.
-- It uses internally @{shuffle} to shuffle the array before sampling values. If `seed` is passed,
-- it will be used for shuffling.
-- @name sample
-- @param array an array
-- @param[opt] n a number of elements to be sampled. Defaults to 1.
-- @param[optchain] seed an optional seed for shuffling 
-- @return an array of selected values
-- @see sampleProb
function M.sample(array, n, seed)
  n = n or 1    
  if n == 0 then return {} end
	if n == 1 then
		if seed then randomseed(seed) end
		return {array[random(1, #array)]}
	end
	return M.slice(M.shuffle(array, seed), 1, n)
end

--- Return elements from a sequence with a given probability. It considers each value independently. 
-- Providing a seed will result in deterministic sampling. Given the same seed it will return the same sample
-- every time.
-- @name sampleProb
-- @param array an array
-- @param prob a probability for each element in array to be selected
-- @param[opt] seed an optional seed for deterministic sampling
-- @return an array of selected values
-- @see sample
function M.sampleProb(array, prob, seed)
	if seed then randomseed(seed) end
  local t = {}
  for k, v in ipairs(array) do
    if random() < prob then t[#t+1] = v end
  end
	return t
end

--- Returns the n-top values satisfying a predicate. It takes a comparison function
-- `comp` used to sort array values, and then picks the top n-values. It leaves the original array untouched.
-- @name nsorted
-- @param array an array
-- @param[opt] n a number of values to retrieve. Defaults to 1.
-- @param[optchain] comp a comparison function. Defaults to `<` operator.
-- @return an array of top n values
function M.nsorted(array, n, comp)
  comp = comp or f_min
  n = n or 1
  local values, count = {}, 0
  for k, v in M.sortedv(array, comp) do
    if count < n then
      count = count + 1
      values[count] = v
    end
  end
  return values
end

--- Returns a shuffled copy of a given array. If a seed is provided, it will
-- be used to init the built-in pseudo random number generator (using `math.randomseed`).
-- @name shuffle
-- @param array an array
-- @param[opt] seed a seed
-- @return a shuffled copy of the given array
function M.shuffle(array, seed)
  if seed then randomseed(seed) end
  local _shuffled = {}
  for index, value in ipairs(array) do
    local randPos = floor(random()*index)+1
    _shuffled[index] = _shuffled[randPos]
    _shuffled[randPos] = value
  end
  return _shuffled
end

--- Converts a list of arguments to an array.
-- @name pack
-- @param ... a list of arguments
-- @return an array of all passed-in args
function M.pack(...) return {...} end

--- Looks for the first occurrence of a given value in an array. Returns the value index if found.
-- Uses @{isEqual} to compare values.
-- @name find
-- @param array an array of values
-- @param value a value to lookup for
-- @param[opt] from the index from where the search will start. Defaults to 1.
-- @return the index of the value if found in the array, `nil` otherwise.
-- @see detect
function M.find(array, value, from)
  for i = from or 1, #array do
    if M.isEqual(array[i], value) then return i end
  end
end

--- Returns an array where values are in reverse order. The passed-in array should not be sparse.
-- @name reverse
-- @param array an array
-- @return a reversed array
function M.reverse(array)
  local _array = {}
  for i = #array,1,-1 do
    _array[#_array+1] = array[i]
  end
  return _array
end

--- Replaces elements in a given array with a given value. In case `i` and `j` are given
-- it will only replaces values at indexes between `[i,j]`. In case `j` is greater than the array
-- size, it will append new values, increasing the array size.
-- @name fill
-- @param array an array
-- @param value a value
-- @param[opt] i the index from which to start replacing values. Defaults to 1.
-- @param[optchain] j the index where to stop replacing values. Defaults to the array size.
-- @return the original array with values changed
function M.fill(array, value, i, j)
	j = j or M.size(array)
	for i = i or 1, j do array[i] = value end
	return array
end

--- Returns an array of `n` zeros.
-- @name zeros
-- @param n a number
-- @return an array
-- @see ones
-- @see vector
function M.zeros(n) return M.fill({}, 0, 1, n) end

--- Returns an array of `n` 1's.
-- @name ones
-- @param n a number
-- @return an array
-- @see zeros
-- @see vector
function M.ones(n) return M.fill({}, 1, 1, n) end

--- Returns an array of `n` times a given value.
-- @name vector
-- @param value a value
-- @param n a number
-- @return an array
-- @see zeros
-- @see ones
function M.vector(value, n) return M.fill({}, value, 1, n) end

--- Collects values from a given array. The passed-in array should not be sparse.
-- This function collects values as long as they satisfy a given predicate and returns on the first falsy test.
-- <br/><em>Aliased as `takeWhile`</em>
-- @name selectWhile
-- @param array an array
-- @param f an iterator function prototyped as `f (v, k)`
-- @return a new table containing all values collected
-- @see dropWhile
function M.selectWhile(array, f)
  local t = {}
  for i,v in ipairs(array) do
    if f(v,i) then t[i] = v else break end
  end
  return t
end

--- Collects values from a given array. The passed-in array should not be sparse.
-- This function collects values as long as they do not satisfy a given predicate and returns on the first truthy test.
-- <br/><em>Aliased as `rejectWhile`</em>
-- @name dropWhile
-- @param array an array
-- @param f an iterator function prototyped as `f (v, k)`
-- @return a new table containing all values collected
-- @see selectWhile
function M.dropWhile(array, f)
  local _i
  for i,v in ipairs(array) do
    if not f(v, i) then
      _i = i
      break
    end
  end
  if (_i == nil) then return {} end
  return M.rest(array,_i)
end

--- Returns the index at which a value should be inserted. This index is evaluated so 
-- that it maintains the sort. If a comparison function is passed, it will be used to sort
-- values.
-- @name sortedIndex
-- @param array an array
-- @param the value to be inserted
-- @param[opt] comp an comparison function prototyped as `f (a, b)`, defaults to <tt><</tt> operator.
-- @param[optchain] sort whether or not the passed-in array should be sorted
-- @return number the index at which the passed-in value should be inserted
function M.sortedIndex(array, value, comp, sort)
  local _comp = comp or f_min
  if (sort == true) then t_sort(array,_comp) end
  for i = 1,#array do
    if not _comp(array[i],value) then return i end
  end
  return #array+1
end

--- Returns the index of the first occurrence of value in an array.
-- @name indexOf
-- @param array an array
-- @param value the value to search for
-- @return the index of the passed-in value
-- @see lastIndexOf
function M.indexOf(array, value)
  for k = 1,#array do
    if array[k] == value then return k end
  end
end

--- Returns the index of the last occurrence of value in an array.
-- @name lastIndexOf
-- @param array an array
-- @param value the value to search for
-- @return the index of the last occurrence of the passed-in value or __nil__
-- @see indexOf
function M.lastIndexOf(array, value)
  local key = M.indexOf(M.reverse(array),value)
  if key then return #array-key+1 end
end

--- Returns the first index at which a predicate returns true.
-- @name findIndex
-- @param array an array
-- @param pred a predicate function prototyped as `pred (v, k)`
-- @return the index found or __nil__
-- @see findLastIndex
function M.findIndex(array, pred)
	for k = 1, #array do
		if pred(array[k],k) then return k end
	end
end

--- Returns the last index at which a predicate returns true.
-- @name findLastIndex
-- @param array an array
-- @param pred a predicate function prototyped as `pred (k, v)`
-- @return the index found or __nil__
-- @see findIndex
function M.findLastIndex(array, pred)
  local key = M.findIndex(M.reverse(array),pred)
  if key then return #array-key+1 end
end

--- Adds all passed-in values at the top of an array. The last elements will bubble to the
-- top of the given array.
-- @name addTop
-- @param array an array
-- @param ... a variable number of arguments
-- @return the passed-in array with new values added
-- @see prepend
-- @see push
function M.addTop(array, ...)
  for k,v in ipairs({...}) do
    t_insert(array,1,v)
  end
  return array
end

--- Adds all passed-in values at the top of an array. As opposed to @{addTop}, it preserves the order
-- of the passed-in elements.
-- @name prepend
-- @param array an array
-- @param ... a variable number of arguments
-- @return the passed-in array with new values added
-- @see addTop
-- @see push
function M.prepend(array, ...)
  return M.append({...}, array)
end

--- Pushes all passed-in values at the end of an array.
-- @name push
-- @param array an array
-- @param ... a variable number of arguments
-- @return the passed-in array with new added values
-- @see addTop
-- @see prepend
function M.push(array, ...)
  local args = {...}
  for k,v in ipairs({...}) do
    array[#array+1] = v
  end
  return array
end

--- Removes and returns the values at the top of a given array.
-- <br/><em>Aliased as `pop`</em>
-- @name shift
-- @param array an array
-- @param[opt] n the number of values to be popped. Defaults to 1.
-- @return the popped values
-- @see unshift
function M.shift(array, n)
  n = min(n or 1, #array)
  local ret = {}
  for i = 1, n do 
    local retValue = array[1]
    ret[#ret + 1] = retValue
    t_remove(array,1)
  end
  return unpack(ret)
end

--- Removes and returns the values at the end of a given array.
-- @name unshift
-- @param array an array
-- @param[opt] n the number of values to be unshifted. Defaults to 1.
-- @return the values
-- @see shift
function M.unshift(array, n)
  n = min(n or 1, #array)
  local ret = {}
  for i = 1, n do
    local retValue = array[#array]
    ret[#ret + 1] = retValue
    t_remove(array)
  end
  return unpack(ret)
end

--- Removes all provided values in a given array.
-- <br/><em>Aliased as `remove`</em>
-- @name pull
-- @param array an array
-- @param ... a variable number of values to be removed from the array
-- @return the passed-in array with values removed
function M.pull(array, ...)
  local values = {...}
  for i = #array, 1, -1 do
    local remval = false
    for k, rmValue in ipairs(values) do
      if (remval == false) then
        if M.isEqual(array[i], rmValue) then
          t_remove(array, i)
          remval = true
        end
      end
    end
  end
  return array
end

--- Removes values at an index within the range `[start, finish]`.
-- <br/><em>Aliased as `rmRange`, `chop`</em>
-- @name removeRange
-- @param array an array
-- @param[opt] start the lower bound index, defaults to the first index in the array.
-- @param[optchain] finish the upper bound index, defaults to the array length.
-- @return the passed-in array with values removed
function M.removeRange(array, start, finish)
  start = start or 1
  finish = finish or #array
  if start > finish then 
    error("start cannot be greater than finish.")
  end  
  for i = finish, start, -1 do
    t_remove(array, i)
  end
  return array
end

--- Chunks together consecutive values. Values are chunked on the basis of the return
-- value of a provided predicate `f (v, k)`. Consecutive elements which return 
-- the same value are chunked together. Leaves the first argument untouched if it is not an array.
-- @name chunk
-- @param array an array
-- @param f an iterator function prototyped as `f (v, k)`
-- @return a table of chunks (arrays)
-- @see zip
function M.chunk(array, f)
  local ch, ck, prev, val = {}, 0
  for k,v in ipairs(array) do
    val = f(v, k)
    prev = (prev==nil) and val or prev
    ck = ((val~=prev) and (ck+1) or ck)
    if not ch[ck] then
      ch[ck] = {array[k]}
    else
      ch[ck][#ch[ck]+1] = array[k]
    end
    prev = val
  end
  return ch
end

--- Slices values indexed within `[start, finish]` range.
-- <br/><em>Aliased as `M.sub`</em>
-- @name slice
-- @param array an array
-- @param[opt] start the lower bound index, defaults to the first index in the array.
-- @param[optchain] finish the upper bound index, defaults to the array length.
-- @return a new array of sliced values
function M.slice(array, start, finish)
  local t = {}
  for k = start or 1, finish or #array do
    t[#t+1] = array[k]
  end
  return t
end

--- Returns the first N values in an array.
-- <br/><em>Aliased as `head`, `take` </em>
-- @name first
-- @param array an array
-- @param[opt] n the number of values to be collected, defaults to 1.
-- @return a new array
-- @see initial
-- @see last
-- @see rest
function M.first(array, n)
  n = n or 1
  local t = {}
  for k = 1, n do
    t[k] = array[k]
  end
  return t
end

--- Returns all values in an array excluding the last N values.
-- @name initial
-- @param array an array
-- @param[opt] n the number of values to be left, defaults to the array length.
-- @return a new array
-- @see first
-- @see last
-- @see rest
function M.initial(array, n)
  local l = #array
  n = n and l-(min(n,l)) or l-1
  local t = {}
  for k = 1, n do
    t[k] = array[k]
  end
  return t
end

--- Returns the last N values in an array.
-- @name last
-- @param array an array
-- @param[opt] n the number of values to be collected, defaults to the array length.
-- @return a new array
-- @see first
-- @see initial
-- @see rest
function M.last(array, n)
  local l = #array
  n = n and l-min(n-1,l-1) or 2 
  local t = {}
  for k = n, l do
    t[#t+1] = array[k]
  end
  return t
end

--- Returns all values after index.
-- <br/><em>Aliased as `tail`</em>
-- @name rest
-- @param array an array
-- @param[opt] index an index, defaults to 1
-- @return a new array
-- @see first
-- @see initial
-- @see last
function M.rest(array, index)
  local t = {}
  for k = index or 1, #array do
    t[#t+1] = array[k]
  end
  return t
end

--- Returns the value at a given index.
-- @name nth
-- @param array an array
-- @param index an index
-- @return the value at the given index
function M.nth(array, index)
  return array[index]
end

--- Returns all truthy values (removes `falses` and `nils`).
-- @name compact
-- @param array an array
-- @return a new array
function M.compact(array)
  local t = {}
  for k,v in pairs(array) do
    if v then t[#t+1] = v end
  end
  return t
end

--- Flattens a nested array. Passing `shallow` will only flatten at the first level.
-- @name flatten
-- @param array an array
-- @param[opt] shallow specifies the flattening depth. Defaults to `false`.`
-- @return a flattened array
function M.flatten(array, shallow)
  shallow = shallow or false
  local new_flattened
  local _flat = {}
  for key,value in ipairs(array) do
    if type(value) == 'table' then
      new_flattened = shallow and value or M.flatten (value)
      for k,item in ipairs(new_flattened) do _flat[#_flat+1] = item end
    else _flat[#_flat+1] = value
    end
  end
  return _flat
end

--- Returns values from an array not present in all passed-in args.
-- <br/><em>Aliased as `without` and `diff`</em>
-- @name difference
-- @param array an array
-- @param another array
-- @return a new array
-- @see union
-- @see intersection
-- @see symmetricDifference
function M.difference(array, array2)
  if not array2 then return M.clone(array) end
  return M.select(array,function(value)
    return not M.include(array2,value)
  end)
end

--- Returns the duplicate-free union of all passed in arrays.
-- @name union
-- @param ... a variable number of arrays arguments
-- @return a new array
-- @see difference
-- @see intersection
-- @see symmetricDifference
function M.union(...)
  return M.unique(M.flatten({...}))
end

--- Returns the  intersection of all passed-in arrays.
-- Each value in the result is present in each of the passed-in arrays.
-- @name intersection
-- @param ... a variable number of array arguments
-- @return a new array
-- @see difference
-- @see union
-- @see symmetricDifference
function M.intersection(...)
  local arg = {...}
  local array = arg[1]
  t_remove(arg, 1)
  local _intersect = {}
  for i,value in ipairs(array) do
    if M.all(arg,function(v) return M.include(v,value) end) then
      _intersect[#_intersect+1] = value
    end
  end
  return _intersect
end

--- Checks if all passed in arrays are disjunct.
-- @name disjoint
-- @param ... a variable number of arrays
-- @return `true` if the intersection of all arrays is not empty, `false` otherwise.
-- @see intersection
function M.disjoint(...)
  return (#M.intersection(...) == 0)
end

--- Performs a symmetric difference. Returns values from `array` not present in `array2` and also values
-- from `array2` not present in `array`.
-- <br/><em>Aliased as `symdiff`</em>
-- @name symmetricDifference
-- @param array an array
-- @param array2 another array
-- @return a new array
-- @see difference
-- @see union
-- @see intersection
function M.symmetricDifference(array, array2)
  return M.difference(
    M.union(array, array2),
    M.intersection(array,array2)
  )
end

--- Produces a duplicate-free version of a given array.
-- <br/><em>Aliased as `uniq`</em>
-- @name unique
-- @param array an array
-- @return a new array, duplicate-free
-- @see isunique
-- @see duplicates
function M.unique(array)
  local ret = {}
  for i = 1, #array do
    if not M.find(ret, array[i]) then
      ret[#ret+1] = array[i]
    end
  end
  return ret
end

--- Checks if a given array contains distinct values. Such an array is made of distinct elements,
-- which only occur once in this array.
-- <br/><em>Aliased as `isuniq`</em>
-- @name isunique
-- @param array an array
-- @return `true` if the given array is unique, `false` otherwise.
-- @see unique
-- @see duplicates
function M.isunique(array)
  return #array == #(M.unique(array))
end

--- Returns an array list of all duplicates in array.
-- @name duplicates
-- @param array an array
-- @return an array-list of duplicates
-- @see unique
function M.duplicates(array)
  local dict = M.invert(array)
  local dups = {}
  for k, v in ipairs(array) do
    if dict[v] ~= k and not M.find(dups, v) then
      dups[#dups+1] = v
    end
  end
  return dups
end

--- Merges values of each of the passed-in arrays in subsets.
-- Only values indexed with the same key in the given arrays are merged in the same subset.
-- <br/><em>Aliased as `transpose`</em>
-- @name zip
-- @param ... a variable number of array arguments
-- @return a new array
-- @see zipWith
function M.zip(...)
  local args = {...}
  local n = M.max(args, function(array) return #array end)
  local _ans = {}
  for i = 1,n do
    if not _ans[i] then _ans[i] = {} end    
    for k, array in ipairs(args) do
      if (array[i]~= nil) then _ans[i][#_ans[i]+1] = array[i] end
    end
  end
  return _ans
end

--- Merges values using a given function.
-- Only values indexed with the same key in the given arrays are merged in the same subset.
-- Function `f` is used to combine values.
-- <br/><em>Aliased as `transposeWith`</em>
-- @name zipWith
-- @param f a function
-- @param ... a variable number of array arguments
-- @return a flat array of results
-- @see zip
function M.zipWith(f, ...)
  local args = {...}
  local n = M.max(args, function(array) return #array end)
  local _ans = {}
  for i = 1,n do    
    _ans[i] = f(unpack(M.pluck(args,i)))
  end
  return _ans
end

--- Clones array and appends values from another array.
-- @name append
-- @param array an array
-- @param other an array
-- @return a new array
function M.append(array, other)
  local t = {}
  for i,v in ipairs(array) do t[i] = v end
  for i,v in ipairs(other) do t[#t+1] = v end
  return t
end

--- Interleaves arrays. It returns a single array made of values from all
-- passed in arrays in their given order, interleaved.
-- @name interleave
-- @param ... a variable list of arrays
-- @return a new array
-- @see interpose
function M.interleave(...) 
  local args = {...}
  local n = M.max(args, M.size)
  local t = {}
  for i = 1, n do  
    for k, array in ipairs(args) do
      if array[i] then t[#t+1] = array[i] end
    end
  end
  return t
end

--- Interposes value in-between consecutive pair of values in array.
-- <br/><em>Aliased as `intersperse`</em>
-- @name interpose
-- @param array an array
-- @param value a value
-- @return a new array
-- @see interleave
function M.interpose(array, value)
  for k = #array, 2,-1 do
    t_insert(array, k, value)
  end
  return array
end

--- Produces a flexible list of numbers. If one value is passed, will count from 1 to that value,
-- with a default step of 1 (or -1). If two values are passed, will count from the first one to the second one,
-- using a default step of 1 (or -1). A third value passed will be considered a step value.
-- @name range
-- @param[opt] from the initial value of the range
-- @param[optchain] to the final value of the range
-- @param[optchain] step the step of count. Defaults to 1 or -1.
-- @return a new array of numbers
function M.range(from, to, step)
  if (from == nil) and (to == nil) and (step ==nil) then
    return {}
  elseif (from ~= nil) and (to == nil) and (step == nil) then
    from, to, step = signum(from), from, signum(from)
  elseif (from ~= nil) and (to ~= nil) and (step == nil) then
    step = signum(to - from)
  end
  local _ranged = {from}
  local steps = max(floor((to-from)/step),0)
  for i=1,steps do _ranged[#_ranged+1] = from+step*i end
  return _ranged
end

--- Creates an array list of `n` values, repeated.
-- @name rep
-- @param value a value to be repeated
-- @param n the number of repetitions of value.
-- @return a new array of `n` values
function M.rep(value, n)
  local ret = {}
  for i = 1, n do ret[i] = value end
  return ret
end

--- Returns the powerset of array values. For instance, when given the set {1,2,3},
-- returns `{{1},{2},{3},{1,2},{2,3},{1,2,3}}`.
-- @name powerset
-- @param array an array
-- @return an array
function M.powerset(array)
  local n = #array
  if n == 0 then return {{}} end
  local t = {}
  for l = 1, n do  
    for s = 1, n-l+1 do
      t[#t+1] = M.slice(array,s,s+l-1)
    end
  end
  return t
end

--- Iterator returning partitions of an array. It returns arrays of length `n` 
-- made of values from the given array. If the last partition has lower elements than `n` and 
-- `pad` is supplied, it will be adjusted to `n` of elements with `pad` value.
-- @name partition
-- @param array an array
-- @param[opt] n the size of partitions. Defaults to 1.
-- @param[optchain] pads a value to adjust the last subsequence to the `n` elements
-- @return an iterator function
-- @see overlapping
-- @see aperture
function M.partition(array, n, pad)
	if n<=0 then return end
  return wrap(function()
    partgen(array, n or 1, yield, pad)
  end)
end

--- Iterator returning overlapping partitions of an array. 
-- If the last subsequence has lower elements than `n` and `pad` is 
-- supplied, it will be adjusted to `n` elements with `pad` value.
-- @name overlapping
-- @param array an array
-- @param[opt] n the size of partitions. Defaults to 2.
-- @param[optchain] pads a value to adjust the last subsequence to the `n` elements
-- @return an iterator function
-- @see partition
-- @see aperture
function M.overlapping(array, n, pad)
	if n<=1 then return end
  return wrap(function()
    partgen2(array, n or 2, yield, pad)
  end)
end

--- Iterator returning sliding partitions of an array.
-- <br/><em>Aliased as `sliding`</em>
-- @name aperture
-- @param array an array
-- @param[opt] n the size of partitions. Defaults to 2 (and then behaves like @{pairwise})
-- @return an iterator function
-- @see partition
-- @see overlapping
-- @see pairwise
function M.aperture(array, n)
	if n<=1 then return end
  return wrap(function()
    partgen3(array, n or 2, yield)
  end)
end

--- Iterator returning sliding pairs of an array.
-- @name pairwise
-- @param array an array
-- @return an iterator function
-- @see overlapping
function M.pairwise(array) return M.aperture(array, 2) end

--- Iterator returning the permutations of an array. It returns arrays made of all values
-- from the passed-in array, with values permuted.
-- @name permutation
-- @param array an array
-- @return an iterator function
function M.permutation(array)
  return wrap(function() 
    permgen(array, #array, yield)
  end)
end

--- Concatenates values in a given array. Handles booleans as well. If `sep` string is
-- passed, it will be used as a separator. Passing `i` and `j` will result in concatenating
-- only values within `[i, j]` range.
-- <br/><em>Aliased as `join`</em>
-- @name concat
-- @param array a given array
-- @param[opt] sep a separator string, defaults to the empty string `''`.
-- @param[optchain] i the starting index, defaults to 1.
-- @param[optchain] j the final index, defaults to the array length.
-- @return a string
function M.concat(array, sep, i, j)
  return t_concat(M.map(array,tostring),sep,i,j)
end

--- Returns all possible pairs built from given arrays.
-- @name xprod
-- @param array a first array
-- @param array2 a second array
-- @return an array list of all pairs
function M.xprod(array, array2)
  local p = {}
  for i, v1 in ipairs(array) do
    for j, v2 in ipairs(array2) do
      p[#p+1] = {v1, v2}
    end
  end
  return p
end

--- Creates pairs from value and array. Value is always prepended to the pair.
-- @name xpairs
-- @param valua a value
-- @param array an array
-- @return an array list of all pairs
function M.xpairs(value, array)
  local xpairs = {}
  for k, v in ipairs(array) do
    xpairs[k] = {value, v}
  end
  return xpairs
end

--- Creates pairs from value and array. Value is always appended as the last item to the pair.
-- @name xpairsRight
-- @param valua a value
-- @param array an array
-- @return an array list of all pairs
function M.xpairsRight(value, array)
  local xpairs = {}
  for k, v in ipairs(array) do
    xpairs[k] = {v, value}
  end
  return xpairs
end

--- Returns the sum of array values.
-- @name sum
-- @param array a given array
-- @return the sum of array values
function M.sum(array)
  local s = 0
  for k, v in ipairs(array) do s = s + v end
  return s
end

--- Returns the product of array values.
-- @name product
-- @param array a given array
-- @return the product of array values
function M.product(array)
  local p = 1
  for k, v in ipairs(array) do p = p * v end
  return p
end

--- Returns the mean of an array of numbers.
-- <br/><em>Aliased as `average`</em>
-- @name mean
-- @param array an array of numbers
-- @return a number
-- @see sum
-- @see product
-- @see median
function M.mean(array)
  return M.sum(array)/(#array)
end

--- Returns the median of an array of numbers.
-- @name median
-- @param array an array of numbers
-- @return a number
-- @see sum
-- @see product
-- @see mean
function M.median(array)
  local t = M.sort(M.clone(array))
  local n = #t
  if n == 0 then 
    return 
  elseif n==1 then 
    return t[1]
  end
  local mid = ceil(n/2)
  return n%2==0 and (t[mid] + t[mid+1])/2 or t[mid]
end

--- Utility functions
-- @section Utility functions

--- The no operation function.
-- @name noop
-- @return nothing
function M.noop() return end

--- Returns the passed-in value. This function is used internally
-- as a default iterator.
-- @name identity
-- @param value a value
-- @return the passed-in value
function M.identity(value) return value end

--- Calls `f` with the supplied arguments. Returns the results of `f(...)`.
-- @name call
-- @param f a function
-- @param[opt] ... a vararg list of args to `f`
-- @return the result of `f(...)` call.
function M.call(f, ...)
  return f(...)
end

--- Creates a constant function which returns the same output on every call.
-- <br/><em>Aliased as `always`</em>
-- @name constant
-- @param value a constant value
-- @return a constant function
function M.constant(value) 
  return function() return value end 
end

--- Returns a function which applies `specs` on args. This function produces an object having
-- the same structure than `specs` by mapping each property to the result of calling its 
-- associated function with the supplied arguments
-- @name applySpec
-- @param specs a table
-- @return a function
function M.applySpec(specs)
  return function (...)
    local spec = {}
    for i, f in pairs(specs) do spec[i] = f(...) end
    return spec
  end
end

--- Threads `value` through a series of functions. If a function expects more than one args,
-- it can be specified using an array list, where the first item is the function and the following
-- are the remaining args neeeded. The value is used as the first input.
-- @name thread
-- @param value a value
-- @param ... a vararg list of functions or arrays
-- @return a value
-- @see threadRight
function M.thread(value, ...)
  local state = value
  local arg = {...}
  for k, t in ipairs(arg) do
    if type(t) == 'function' then
      state = t(state)
    elseif type(t) == 'table' then
      local f = t[1]
      t_remove(t, 1)
      state = M.reduce(t, f, state)
    end
  end
  return state
end

--- Threads `value` through a series of functions. If a function expects more than one args,
-- it can be specified using an array list, where the first item is the function and the following
-- are the remaining args neeeded. The value is used as the last input.
-- @name threadRight
-- @param value a value
-- @param ... a vararg list of functions or arrays
-- @return a value
-- @see thread
function M.threadRight(value, ...)
  local state = value
  local arg = {...}
  for k, t in ipairs(arg) do
    if type(t) == 'function' then
      state = t(state)
    elseif type(t) == 'table' then
      local f = t[1]
      t_remove(t, 1)
      t_insert(t, state)
      state = M.reduce(t, f)
    end
  end
  return state
end

--- Returns a dispatching function. When called with arguments, this function invokes each of its functions
-- in the passed-in order and returns the results of the first non-nil evaluation.
-- @name dispatch
-- @param ... a vararg list of functions
-- @return a dispatch function
function M.dispatch(...)
  local funcs = {...}
  return function (...)
    for k, f in ipairs(funcs) do
      local r = {f(...)}
      if #r > 0 then return unpack(r) end
    end
  end
end

--- Memoizes a given function by caching the computed result.
-- Useful for speeding-up slow-running functions.
-- <br/><em>Aliased as `cache`</em>
-- @name memoize
-- @param f a function
-- @return a new function
function M.memoize(f)
  local _cache = setmetatable({},{__mode = 'kv'})
  return function (key)
      if (_cache[key] == nil) then
        _cache[key] = f(key)
      end
      return _cache[key]
    end
end

--- Builds a list from a seed value. Accepts an iterator function, which 
-- returns either nil to stop iteration or two values : the value to add to the list
-- of results and the seed to be used in the next call to the iterator function.
-- @name unfold
-- @param f an iterator function
-- @param seed a seed value
-- @return an array of values
function M.unfold(f, seed)
  local t, result = {}
  while true do
    result, seed = f(seed)
    if result ~= nil then t[#t+1] = result
    else break
    end
  end 
  return t
end

--- Returns a version of `f` that runs only once. Successive calls to `f`
-- will keep yielding the same output, no matter what the passed-in arguments are. 
-- It can be used to initialize variables.
-- @name once
-- @param f a function
-- @return a new function
-- @see before
-- @see after
function M.once(f)
  local _internal = 0
  local _args = {}
  return function(...)
		_internal = _internal+1
		if _internal <= 1 then _args = {...} end
		return f(unpack(_args))
  end
end

--- Returns a version of `f` that will run no more than <em>count</em> times. Next calls will
-- keep yielding the results of the count-th call.
-- @name before
-- @param f a function
-- @param count a count
-- @return a new function
-- @see once
-- @see after
function M.before(f, count)
  local _internal = 0
  local _args = {}
  return function(...)
		_internal = _internal+1
		if _internal <= count then _args = {...} end
		return f(unpack(_args))
  end
end

--- Returns a version of `f` that runs on the `count-th` call.
-- Useful when dealing with asynchronous tasks.
-- @name after
-- @param f a function
-- @param count the number of calls before `f` will start running.
-- @return a new function
-- @see once
-- @see before
function M.after(f, count)
  local _limit,_internal = count, 0
  return function(...)
		_internal = _internal+1
		if _internal >= _limit then return f(...) end
  end
end

--- Composes functions. Each passed-in function consumes the return value of the function that follows.
-- In math terms, composing the functions `f`, `g`, and `h` produces the function `f(g(h(...)))`.
-- @name compose
-- @param ... a variable number of functions
-- @return a new function
-- @see pipe
function M.compose(...)
	-- See: https://github.com/Yonaba/Moses/pull/15#issuecomment-139038895
  local f = M.reverse {...}
  return function (...)
		local first, _temp = true
		for i, func in ipairs(f) do
			if first then
				first = false
				_temp = func(...)
			else
				_temp = func(_temp)
			end
		end
		return _temp
	end
end

--- Pipes a value through a series of functions. In math terms, 
-- given some functions `f`, `g`, and `h` in that order, it returns `f(g(h(value)))`.
-- @name pipe
-- @param value a value
-- @param ... a variable number of functions
-- @return the result of the composition of function calls.
-- @see compose
function M.pipe(value, ...)
  return M.compose(...)(value)
end

--- Returns the logical complement of a given function. For a given input, the returned 
-- function will output `false` if the original function would have returned `true`, 
-- and vice-versa.
-- @name complement
-- @param f a function
-- @return  the logical complement of the given function `f`.
function M.complement(f)
  return function(...) return not f(...) end
end

--- Calls a sequence of passed-in functions with the same argument.
-- Returns a sequence of results. 
-- <br/><em>Aliased as `juxt`</em>
-- @name juxtapose
-- @param value a value
-- @param ... a variable number of functions
-- @return a list of results
function M.juxtapose(value, ...)
  local res = {}
  for i, func in ipairs({...}) do
    res[i] = func(value) 
  end
  return unpack(res)
end

--- Wraps `f` inside of the `wrapper` function. It passes `f` as the first argument to `wrapper`.
-- This allows the wrapper to execute code before and after `f` runs,
-- adjust the arguments, and execute it conditionally.
-- @name wrap
-- @param f a function to be wrapped, prototyped as `f (...)`
-- @param wrapper a wrapper function, prototyped as `wrapper (f, ...)`
-- @return the results
function M.wrap(f, wrapper)
  return function (...) return  wrapper(f,...) end
end

--- Runs `iter` function `n` times. Collects the results of each run and returns them in an array.
-- @name times
-- @param  iter an iterator function, prototyped as `iter (i)`
-- @param[opt] n the number of times `iter` should be called. Defaults to 1.
-- @return table an array of results
function M.times(iter, n)
  local results = {}
  for i = 1, (n or 1) do
    results[i] = iter(i)
  end
  return results
end

--- Binds `v` to be the first argument to `f`. Calling `f (...)` will result to `f (v, ...)`.
-- @name bind
-- @param f a function
-- @param v a value
-- @return a function
-- @see bind2
-- @see bindn
-- @see bindall
function M.bind(f, v)
  return function (...)
    return f(v,...)
  end
end

--- Binds `v` to be the second argument to `f`. Calling `f (a, ...)` will result to `f (a, v, ...)`.
-- @name bind2
-- @param f a function
-- @param v a value
-- @return a function
-- @see bind
-- @see bindn
-- @see bindall
function M.bind2(f, v)
  return function (t, ...)
    return f(t, v, ...)
  end
end

--- Binds `...` to be the N-first arguments to function `f`. 
-- Calling `f (a1, a2, ..., aN)` will result to `f (..., a1, a2, ...,aN)`.
-- @name bindn
-- @param f a function
-- @param ... a variable number of arguments
-- @return a function
-- @see bind
-- @see bind2
-- @see bindall
function M.bindn(f, ...)
  local args = {...}
  return function (...)
      return f(unpack(M.append(args,{...})))
    end
end

--- Binds methods to object. As such, whenever any of these methods is invoked, it 
-- always receives the object as its first argument.
-- @name bindall
-- @param obj an abject
-- @param ... a variable number of method names
-- @return the passed-in object with all methods bound to the object itself.
-- @see bind
-- @see bind2
-- @see bindn
function M.bindall(obj, ...)
	local methodNames = {...}
	for i, methodName in ipairs(methodNames) do
		local method = obj[methodName]
		if method then obj[methodName] = M.bind(method, obj) end
	end
	return obj
end

--- Returns a function which iterate over a set of conditions. It invokes each predicate,
-- passing it given values. It returns the value of the corresponding function of the first 
-- predicate to return a non-nil value.
-- @name cond
-- @param conds an array list of predicate-function pairs
-- @return the result of invoking `f(...)` of the first predicate to return a non-nil value
function M.cond(conds)
  return function(...)
    for k, condset in ipairs(conds) do
      if condset[1](...) then 
        return condset[2](...) 
      end
    end
  end
end

--- Returns a validation function. Given a set of functions, the validation function evaluates
-- to `true` only when all its funcs returns `true`.
-- @name both
-- @param ... an array list of functions
-- @return `true` when all given funcs returns true with input, false otherwise
function M.both(...)
  local funcs = {...}
  return function (...)
    for k, f in ipairs(funcs) do
      if not f(...) then return false end
    end
    return true
  end
end

--- Returns a validation function. Given a set of functions, the validation function evaluates
-- to `true` when at least one of its funcs returns `true`.
-- @name either
-- @param ... an array list of functions
-- @return `true` when one of the given funcs returns `true` with input, `false` otherwise
function M.either(...)
  local funcs = {...}
  return function (...)
    for k, f in ipairs(funcs) do
      if f(...) then return true end
    end
    return false
  end
end

--- Returns a validation function. Given a set of functions, the validation function evaluates
-- to `true` when neither of its func return `true`.
-- @name neither
-- @param ... an array list of functions
-- @return `true` when neither of the given funcs returns `true` with input, `false` otherwise
function M.neither(...)
  local funcs = {...}
  return function (...)
    for k, f in ipairs(funcs) do
      if f(...) then return false end
    end
    return true
  end
end

--- Generates an unique ID for the current session. If given a string `template`, it
-- will use this template for output formatting. Otherwise, if `template` is a function, it
-- will evaluate `template (id)`.
-- <br/><em>Aliased as `uid`</em>.
-- @name uniqueId
-- @param[opt] template either a string or a function template to format the ID
-- @return value an ID
function M.uniqueId(template)
  unique_id_counter = unique_id_counter + 1
  if template then
    if type(template) == 'string' then
      return template:format(unique_id_counter)
    elseif type(template) == 'function' then
      return template(unique_id_counter)
    end
  end
  return unique_id_counter
end

--- Produces an iterator which repeatedly apply a function `f` onto an input. 
-- Yields `value`, then `f(value)`, then `f(f(value))`, continuously.
-- <br/><em>Aliased as `iter`</em>.
-- @name iterator
-- @param f a function 
-- @param value an initial input to `f`
-- @param[opt] n the number of times the iterator should run
-- @return an iterator function
function M.iterator(f, value, n)
  local cnt = 0
	return function()
    cnt = cnt + 1
    if n and cnt > n then return end
		value = f(value)
		return value
	end
end

--- Consumes the first `n` values of a iterator then returns it.
-- @name skip
-- @param iter an iterator function 
-- @param[opt] n a number. Defaults to 1.
-- @return the given iterator
function M.skip(iter, n)
  for i = 1, (n or 1) do
    if iter() == nil then return end
  end
  return iter
end

--- Iterates over an iterator and returns its values in an array.
-- @name tabulate
-- @param ... an iterator function (returning a generator, a state and a value)
-- @return an array of results
function M.tabulate(...)
	local r = {}
	for v in ... do r[#r+1] = v end
	return r
end

--- Returns the length of an iterator. It consumes the iterator itself.
-- @name iterlen
-- @param ... an iterator function (returning a generator, a state and a value)
-- @return the iterator length
function M.iterlen(...)
	local l = 0
  for v in ... do l = l + 1 end
  return l
end

--- Casts value as an array if it is not one.
-- @name castArray
-- @param value a value
-- @return an array containing the given value
function M.castArray(value)
  return (type(value)~='table') and {value} or value
end

--- Creates a function of `f` with arguments flipped in reverse order.
-- @name flip
-- @param f a function 
-- @return a function
function M.flip(f)
	return function(...)
		return f(unpack(M.reverse({...})))
	end
end

--- Returns a function that gets the nth argument. 
-- If n is negative, the nth argument from the end is returned.
-- @name nthArg
-- @param n a number 
-- @return a function
function M.nthArg(n)
  return function (...)
    local args = {...}
    return args[(n < 0) and (#args + n + 1) or n]
  end
end

--- Returns a function which accepts up to one arg. It ignores any additional arguments.
-- @name unary
-- @param f a function
-- @return a function
-- @see ary
function M.unary(f)
  return function (...)
    local args = {...}
    return f(args[1])
  end
end

--- Returns a function which accepts up to `n` args. It ignores any additional arguments.
-- <br/><em>Aliased as `nAry`</em>.
-- @name ary
-- @param f a function
-- @param[opt] n a number. Defaults to 1.
-- @return a function
-- @see unary
function M.ary(f, n)
  n = n or 1
  return function (...)
    local args = {...}
    local fargs = {}
    for i = 1, n do fargs[i] = args[i] end
    return f(unpack(fargs))
  end
end

--- Returns a function with an arity of 0. The new function ignores any arguments passed to it.
-- @name noarg
-- @param f a function
-- @return a new function
function M.noarg(f)
  return function ()
    return f()
  end
end

--- Returns a function which runs with arguments rearranged. Arguments are passed to the 
-- returned function in the order of supplied `indexes` at call-time.
-- @name rearg
-- @param f a function
-- @param indexes an array list of indexes
-- @return a function
function M.rearg(f, indexes)
  return function(...)
    local args = {...}
    local reargs = {}
    for i, arg in ipairs(indexes) do reargs[i] = args[arg] end
    return f(unpack(reargs))
  end
end

--- Creates a function that runs transforms on all arguments it receives.
-- @name over
-- @param ... a set of functions which will receive all arguments to the returned function
-- @return a function
-- @see overEvery
-- @see overSome
-- @see overArgs
function M.over(...)
	local transforms = {...}
	return function(...)
		local r = {}
		for i,transform in ipairs(transforms) do
			r[#r+1] = transform(...)
		end
		return r
	end
end

--- Creates a validation function. The returned function checks if *all* of the given predicates return 
-- truthy when invoked with the arguments it receives.
-- @name overEvery
-- @param ... a list of predicate functions
-- @return a new function
-- @see over
-- @see overSome
-- @see overArgs
function M.overEvery(...)
	local f = M.over(...)
	return function(...)
		return M.reduce(f(...),function(state,v) return state and v end)
	end
end

--- Creates a validation function. The return function checks if *any* of a given predicates return 
-- truthy when invoked with the arguments it receives.
-- @name overSome
-- @param ... a list of predicate functions
-- @return a new function
-- @see over
-- @see overEvery
-- @see overArgs
function M.overSome(...)
	local f = M.over(...)
	return function(...)
		return M.reduce(f(...),function(state,v) return state or v end)
	end
end

--- Creates a function that invokes `f` with its arguments transformed. 1rst arguments will be passed to 
-- the 1rst transform, 2nd arg to the 2nd transform, etc. Remaining arguments will not be transformed.
-- @name overArgs
-- @param f a function
-- @param ... a list of transforms funcs prototyped as `f (v)`
-- @return the result of running `f` with its transformed arguments
-- @see over
-- @see overEvery
-- @see overSome
function M.overArgs(f,...)
	local _argf = {...}
	return function(...)
		local _args = {...}
		for i = 1,#_argf do
			local func = _argf[i]
			if _args[i] then _args[i] = func(_args[i]) end
		end
		return f(unpack(_args))
	end
end

--- Converges two functions into one.
-- @name converge
-- @param f a function
-- @param g a function
-- @param h a function
-- @return a new version of function f 
function M.converge(f, g, h) return function(...) return f(g(...),h(...)) end end

--- Partially apply a function by filling in any number of its arguments. 
-- One may pass a string `'M'` as a placeholder in the list of arguments to specify an argument 
-- that should not be pre-filled, but left open to be supplied at call-time. 
-- @name partial
-- @param f a function
-- @param ... a list of partial arguments to `f`
-- @return a new version of function f having some of it original arguments filled
-- @see partialRight
-- @see curry
function M.partial(f,...)
	local partial_args = {...}
	return function (...)
		local n_args = {...}	
		local f_args = {}
		for k,v in ipairs(partial_args) do
			f_args[k] = (v == '_') and M.shift(n_args) or v
		end
		return f(unpack(M.append(f_args,n_args)))
	end
end

--- Similar to @{partial}, but from the right.
-- @name partialRight
-- @param f a function
-- @param ... a list of partial arguments to `f`
-- @return a new version of function f having some of it original arguments filled
-- @see partialRight
-- @see curry
function M.partialRight(f,...)
	local partial_args = {...}
	return function (...)
		local n_args = {...}	
		local f_args = {}
		for k = 1,#partial_args do
			f_args[k] = (partial_args[k] == '_') and M.shift(n_args) or partial_args[k]
		end
		return f(unpack(M.append(n_args, f_args)))
	end
end

--- Curries a function. If the given function `f` takes multiple arguments, it returns another version of 
-- `f` that takes a single argument (the first of the arguments to the original function) and returns a new 
-- function that takes the remainder of the arguments and returns the result. 
-- @name curry
-- @param f a function
-- @param[opt] n_args the number of arguments expected for `f`. Defaults to 2.
-- @return a curried version of `f`
-- @see partial
-- @see partialRight
function M.curry(f, n_args)
	n_args = n_args or 2
	local _args = {}
	local function scurry(v)
		if n_args == 1 then return f(v) end
		if v ~= nil then _args[#_args+1] = v end
		if #_args < n_args then
			return scurry
		else
			local r = {f(unpack(_args))}
			_args = {}
			return unpack(r)
		end
	end
	return scurry
end

--- Returns the execution time of `f (...)` and its returned values.
-- @name time
-- @param f a function
-- @param[opt] ... optional args to `f`
-- @return the execution time and the results of `f (...)`
function M.time(f, ...)
	local stime = clock()
	local r = {f(...)}
	return clock() - stime, unpack(r)
end

--- Object functions
-- @section Object functions

--- Returns the keys of the object properties.
-- @name keys
-- @param obj an object
-- @return an array
function M.keys(obj)
  local keys = {}
  for key in pairs(obj) do keys[#keys+1] = key end
  return keys
end

--- Returns the values of the object properties.
-- @name values
-- @param obj an object
-- @return an array of values
function M.values(obj)
  local values = {}
  for key, value in pairs(obj) do values[#values+1] = value end
  return values
end

--- Returns the value at a given path in an object. 
-- Path is given as a vararg list of keys.
-- @name path
-- @param obj an object
-- @param ... a vararg list of keys
-- @return a value or nil
function M.path(obj, ...)
  local value, path = obj, {...}
  for i, p in ipairs(path) do
    if (value[p] == nil) then return end
    value = value[p]
  end
  return value
end

--- Spreads object under property path onto provided object. 
-- It is similar to @{flattenPath}, but removes object under the property path.
-- @name spreadPath
-- @param obj an object
-- @param ... a property path given as a vararg list
-- @return the passed-in object with changes
-- @see flattenPath
function M.spreadPath(obj, ...)
  local path = {...}
  for _, p in ipairs(path) do
    if obj[p] then
      for k, v in pairs(obj[p]) do 
        obj[k] = v
        obj[p][k] = nil
      end
    end
  end
  return obj
end

--- Flattens object under property path onto provided object. 
-- It is similar to @{spreadPath}, but preserves object under the property path.
-- @name flattenPath
-- @param obj an object
-- @param ... a property path given as a vararg list
-- @return the passed-in object with changes
-- @see spreadPath
function M.flattenPath(obj, ...)
  local path = {...}
  for _, p in ipairs(path) do
    if obj[p] then
      for k, v in pairs(obj[p]) do obj[k] = v end
    end
  end
  return obj
end

--- Converts key-value pairs to an array-list of `[k, v]` pairs.
-- @name kvpairs
-- @param obj an object
-- @return an array list of key-value pairs
-- @see toObj
function M.kvpairs(obj)
	local t = {}
	for k,v in pairs(obj) do t[#t+1] = {k,v} end
	return t
end

--- Converts an array list of `[k,v]` pairs to an object. Keys are taken
-- from the 1rst column in the `[k,v]` pairs sequence, associated with values in the 2nd
-- column.
-- @name toObj
-- @param kvpairs an array-list of `[k,v]` pairs
-- @return an object
-- @see kvpairs
function M.toObj(kvpairs)
	local obj = {}
	for k, v in ipairs(kvpairs) do
		obj[v[1]] = v[2]
	end
	return obj
end

--- Swaps keys with values. Produces a new object where previous keys are now values, 
-- while previous values are now keys.
-- <br/><em>Aliased as `mirror`</em>
-- @name invert
-- @param obj a given object
-- @return a new object
function M.invert(obj)
  local _ret = {}
  for k, v in pairs(obj) do
    _ret[v] = k
  end
  return _ret
end

--- Returns a function that will return the key property of any passed-in object.
-- @name property
-- @param key a key property name
-- @return a function which should accept an object as argument
-- @see propertyOf
function M.property(key)
	return function(obj) return obj[key] end
end

--- Returns a function which will return the value of an object property. 
-- @name propertyOf
-- @param obj an object
-- @return a function which should accept a key property argument
-- @see property
function M.propertyOf(obj)
	return function(key) return obj[key] end
end

--- Converts any given value to a boolean
-- @name toBoolean
-- @param value a value. Can be of any type
-- @return `true` if value is true, `false` otherwise (false or nil).
function M.toBoolean(value)
  return not not value
end

--- Extends an object properties. It copies the properties of extra passed-in objects
-- into the destination object, and returns the destination object. The last objects
-- will override properties of the same name.
-- @name extend
-- @param destObj a destination object
-- @param ... a list of objects
-- @return the destination object extended
function M.extend(destObj, ...)
  local sources = {...}
  for k, source in ipairs(sources) do
    if type(source) == 'table' then
      for key, value in pairs(source) do destObj[key] = value end
    end
  end
  return destObj
end

--- Returns a sorted list of all methods names found in an object. If the given object
-- has a metatable implementing an `__index` field pointing to another table, will also recurse on this
-- table if `recurseMt` is provided. If `obj` is omitted, it defaults to the library functions.
-- <br/><em>Aliased as `methods`</em>.
-- @name functions
-- @param[opt] obj an object. Defaults to Moses library functions.
-- @return an array-list of methods names
function M.functions(obj, recurseMt)
  obj = obj or M
  local _methods = {}
  for key, value in pairs(obj) do
    if type(value) == 'function' then
      _methods[#_methods+1] = key
    end
  end
  if recurseMt then
    local mt = getmetatable(obj)
    if mt and mt.__index then
      local mt_methods = M.functions(mt.__index, recurseMt)
      for k, fn in ipairs(mt_methods) do
        _methods[#_methods+1] = fn
      end
    end
  end
  return _methods
end

--- Clones a given object properties. If `shallow` is passed will also clone nested array properties.
-- @name clone
-- @param obj an object
-- @param[opt] shallow whether or not nested array-properties should be cloned, defaults to false.
-- @return a copy of the passed-in object
function M.clone(obj, shallow)
  if type(obj) ~= 'table' then return obj end
  local _obj = {}
  for i,v in pairs(obj) do
    if type(v) == 'table' then
      if not shallow then
        _obj[i] = M.clone(v,shallow)
      else _obj[i] = v
      end
    else
      _obj[i] = v
    end
  end
  return _obj
end

--- Invokes interceptor with the object, and then returns object.
-- The primary purpose of this method is to "tap into" a method chain, in order to perform operations 
-- on intermediate results within the chain.
-- @name tap
-- @param obj an object
-- @param f an interceptor function, should be prototyped as `f (obj)`
-- @return the passed-in object
function M.tap(obj, f)
  f(obj)
  return obj
end

--- Checks if a given object implements a property.
-- @name has
-- @param obj an object
-- @param key a key property to be checked
-- @return `true` or `false`
function M.has(obj, key)
  return obj[key]~=nil
end

--- Returns an object copy having white-listed properties.
-- <br/><em>Aliased as `choose`</em>.
-- @name pick
-- @param obj an object
-- @param ... a variable number of string keys
-- @return the filtered object
function M.pick(obj, ...)
  local whitelist = M.flatten {...}
  local _picked = {}
  for key, property in pairs(whitelist) do
    if (obj[property])~=nil then
      _picked[property] = obj[property]
    end
  end
  return _picked
end

--- Returns an object copy without black-listed properties.
-- <br/><em>Aliased as `drop`</em>.
-- @name omit
-- @param obj an object
-- @param ... a variable number of string keys
-- @return the filtered object
function M.omit(obj, ...)
  local blacklist = M.flatten {...}
  local _picked = {}
  for key, value in pairs(obj) do
    if not M.include(blacklist,key) then
      _picked[key] = value
    end
  end
  return _picked
end

--- Applies a template to an object, preserving non-nil properties.
-- <br/><em>Aliased as `defaults`</em>.
-- @name template
-- @param obj an object
-- @param[opt] template a template object. If `nil`, leaves `obj` untouched.
-- @return the passed-in object filled
function M.template(obj, template)
  if not template then return obj end
  for i, v in pairs(template) do
    if not obj[i] then obj[i] = v end
  end
  return obj
end

--- Performs a deep comparison test between two objects. Can compare strings, functions 
-- (by reference), nil, booleans. Compares tables by reference or by values. If `useMt` 
-- is passed, the equality operator `==` will be used if one of the given objects has a 
-- metatable implementing `__eq`.
-- <br/><em>Aliased as `M.compare`, `M.matches`</em>
-- @name isEqual
-- @param objA an object
-- @param objB another object
-- @param[opt] useMt whether or not `__eq` should be used, defaults to false.
-- @return `true` or `false`
-- @see allEqual
function M.isEqual(objA, objB, useMt)
  local typeObjA = type(objA)
  local typeObjB = type(objB)

  if typeObjA~=typeObjB then return false end
  if typeObjA~='table' then return (objA==objB) end

  local mtA = getmetatable(objA)
  local mtB = getmetatable(objB)

  if useMt then
    if (mtA or mtB) and (mtA.__eq or mtB.__eq) then
      return mtA.__eq(objA, objB) or mtB.__eq(objB, objA) or (objA==objB)
    end
  end

  if M.size(objA)~=M.size(objB) then return false end
  
  local vB
  for i,vA in pairs(objA) do
    vB = objB[i]
    if vB == nil or not M.isEqual(vA, vB, useMt) then return false end
  end

  for i in pairs(objB) do
    if objA[i] == nil then return false end
  end

  return true
end

--- Invokes an object method. It passes the object itself as the first argument. if `method` is not
-- callable, will return `obj[method]`.
-- @name result
-- @param obj an object
-- @param method a string key to index in object `obj`.
-- @return the returned value of `method (obj)` call
function M.result(obj, method)
  if obj[method] then
    if M.isCallable(obj[method]) then
      return obj[method](obj)
    else return obj[method]
    end
  end
  if M.isCallable(method) then
    return method(obj)
  end
end

--- Checks if the given arg is a table.
-- @name isTable
-- @param t a value to be tested
-- @return `true` or `false`
function M.isTable(t)
  return type(t) == 'table'
end

--- Checks if the given argument is callable. Assumes `obj` is callable if
-- it is either a function or a table having a metatable implementing `__call` metamethod.
-- @name isCallable
-- @param obj an object
-- @return `true` or `false`
function M.isCallable(obj)
  return 
    ((type(obj) == 'function') or
    ((type(obj) == 'table') and getmetatable(obj) and getmetatable(obj).__call~=nil) or
    false)
end

--- Checks if the given argument is an array. Assumes `obj` is an array
-- if is a table with consecutive integer keys starting at 1.
-- @name isArray
-- @param obj an object
-- @return `true` or `false`
function M.isArray(obj)
  if not (type(obj) == 'table') then return false end
  -- Thanks @Wojak and @Enrique García Cota for suggesting this
  -- See : http://love2d.org/forums/viewtopic.php?f=3&t=77255&start=40#p163624
  local i = 0
  for k in pairs(obj) do
     i = i + 1
     if obj[i] == nil then return false end
  end
  return true
end

--- Checks if the given object is iterable with `pairs` (or `ipairs`).
-- @name isIterable
-- @param obj an object
-- @return `true` if the object can be iterated with `pairs` (or `ipairs`), `false` otherwise
function M.isIterable(obj)
  return M.toBoolean((pcall(pairs, obj)))
end

--- Extends Lua's `type` function. It returns the type of the given object and also recognises
-- file userdata
-- @name type
-- @param obj an object
-- @return the given object type
function M.type(obj)
  local tp = type(obj)
  if tp == 'userdata' then
    local mt = getmetatable(obj)
    if mt == getmetatable(io.stdout) then 
      return 'file'
    end
  end
  return tp
end

--- Checks if the given pbject is empty. If `obj` is a string, will return `true`
-- if `#obj == 0`. Otherwise, if `obj` is a table, will return whether or not this table
-- is empty. If `obj` is `nil`, it will return true.
-- @name isEmpty
-- @param[opt] obj an object
-- @return `true` or `false`
function M.isEmpty(obj)
  if (obj == nil) then return true end
  if type(obj) == 'string' then return #obj==0 end
  if type(obj) == 'table' then return next(obj)==nil end
  return true
end

--- Checks if the given argument is a string.
-- @name isString
-- @param obj an object
-- @return `true` or `false`
function M.isString(obj)
  return type(obj) == 'string'
end

--- Checks if the given argument is a function.
-- @name isFunction
-- @param obj an object
-- @return `true` or `false`
function M.isFunction(obj)
   return type(obj) == 'function'
end

--- Checks if the given argument is nil.
-- @name isNil
-- @param obj an object
-- @return `true` or `false`
function M.isNil(obj)
  return obj==nil
end

--- Checks if the given argument is a number.
-- @name isNumber
-- @param obj an object
-- @return `true` or `false`
-- @see isNaN
function M.isNumber(obj)
  return type(obj) == 'number'
end

--- Checks if the given argument is NaN (see [Not-A-Number](http://en.wikipedia.org/wiki/NaN)).
-- @name isNaN
-- @param obj an object
-- @return `true` or `false`
-- @see isNumber
function M.isNaN(obj)
  return type(obj) == 'number' and obj~=obj
end

--- Checks if the given argument is a finite number.
-- @name isFinite
-- @param obj an object
-- @return `true` or `false`
function M.isFinite(obj)
  if type(obj) ~= 'number' then return false end
  return obj > -huge and obj < huge
end

--- Checks if the given argument is a boolean.
-- @name isBoolean
-- @param obj an object
-- @return `true` or `false`
function M.isBoolean(obj)
  return type(obj) == 'boolean'
end

--- Checks if the given argument is an integer.
-- @name isInteger
-- @param obj an object
-- @return `true` or `false`
function M.isInteger(obj)
  return type(obj) == 'number' and floor(obj)==obj
end

-- Aliases

do

  -- Table functions aliases
  M.forEach       = M.each
  M.forEachi      = M.eachi
  M.update        = M.adjust
  M.alleq         = M.allEqual
  M.loop          = M.cycle
  M.collect       = M.map
  M.inject        = M.reduce
  M.foldl         = M.reduce
  M.injectr       = M.reduceRight
  M.foldr         = M.reduceRight
  M.mapr          = M.mapReduce
  M.maprr         = M.mapReduceRight
  M.any           = M.include
  M.some          = M.include
  M.contains      = M.include
  M.filter        = M.select
  M.discard       = M.reject
  M.every         = M.all
  
  -- Array functions aliases
  M.takeWhile     = M.selectWhile
  M.rejectWhile   = M.dropWhile
  M.pop           = M.shift
  M.remove        = M.pull
  M.rmRange       = M.removeRange
  M.chop          = M.removeRange
  M.sub           = M.slice
  M.head          = M.first
  M.take          = M.first
  M.tail          = M.rest
  M.without       = M.difference
  M.diff          = M.difference
  M.symdiff       = M.symmetricDifference
  M.xor           = M.symmetricDifference
  M.uniq          = M.unique
  M.isuniq        = M.isunique
	M.transpose     = M.zip
  M.part          = M.partition
  M.perm          = M.permutation
  M.transposeWith = M.zipWith
  M.intersperse   = M.interpose
  M.sliding       = M.aperture
  M.mirror        = M.invert
  M.join          = M.concat
  M.average       = M.mean
  
  -- Utility functions aliases
  M.always        = M.constant
  M.cache         = M.memoize
  M.juxt          = M.juxtapose
  M.uid           = M.uniqueid
  M.iter          = M.iterator
  M.nAry          = M.ary
  
  -- Object functions aliases
  M.methods       = M.functions
  M.choose        = M.pick
  M.drop          = M.omit
  M.defaults      = M.template
  M.compare       = M.isEqual
  M.matches       = M.isEqual

end

-- Setting chaining and building interface

do

  -- Wrapper to Moses
  local f = {}

  -- Will be returned upon requiring, indexes into the wrapper
  local Moses = {}
  Moses.__index = f

  -- Wraps a value into an instance, and returns the wrapped object
  local function new(value)
    return setmetatable({_value = value, _wrapped = true}, Moses)
  end

  setmetatable(Moses,{
    __call  = function(self,v) return new(v) end, -- Calls returns to instantiation
    __index = function(t,key,...) return f[key] end  -- Redirects to the wrapper
  })

  --- Returns a wrapped object. Calling library functions as methods on this object
  -- will continue to return wrapped objects until @{obj:value} is used. Can be aliased as `M(value)`.
  -- @class function
  -- @name chain
  -- @param value a value to be wrapped
  -- @return a wrapped object
  function Moses.chain(value)
    return new(value)
  end

  --- Extracts the value of a wrapped object. Must be called on an chained object (see @{chain}).
  -- @class function
  -- @name obj:value
  -- @return the value previously wrapped
  function Moses:value()
    return self._value
  end

  -- Register chaining methods into the wrapper
  f.chain, f.value = Moses.chain, Moses.value

  -- Register all functions into the wrapper
  for fname,fct in pairs(M) do
    if fname ~= 'operator' then -- Prevents from wrapping op functions
      f[fname] = function(v, ...)
        local wrapped = type(v) == 'table' and rawget(v,'_wrapped') or false
        if wrapped then
          local _arg = v._value
          local _rslt = fct(_arg,...)
          return new(_rslt)
        else
          return fct(v,...)
        end
      end
    end
  end
  
  -- Exports all op functions
  f.operator = M.operator
  f.op       = M.operator

  --- Imports all library functions into a context.
  -- @name import
  -- @param[opt] context a context. Defaults to `_ENV or `_G`` (current environment).
  -- @param[optchain] noConflict if supplied, will not import conflicting functions in the destination context.
  -- @return the passed-in context
  f.import = function(context, noConflict)
    context = context or _ENV or _G
    local funcs = M.functions()
    for k, fname in ipairs(funcs) do
      if rawget(context, fname)~= nil then
        if not noConflict then
          rawset(context, fname, M[fname])
        end
      else
        rawset(context, fname, M[fname])
      end
    end
    return context
  end

  -- Descriptive tags
  Moses._VERSION     = 'Moses v'.._MODULEVERSION
  Moses._URL         = 'http://github.com/Yonaba/Moses'
  Moses._LICENSE     = 'MIT <http://raw.githubusercontent.com/Yonaba/Moses/master/LICENSE>'
  Moses._DESCRIPTION = 'utility-belt library for functional programming in Lua'
  
  return Moses

end
