#############################################################################
######      Fast heuristic, produces a subset of the right-factors     ######
#############################################################################

# Mark van Hoeij, 2020.

RFactorsHeuristic := proc(L0)
local x,tau,  P, A, ANS, L, Ord, db, i, lc, r;
	x, tau := _Env_LRE_x, _Env_LRE_tau;
	P := collect(primpart(L0, tau), tau);
	_Env_LRE_GuessM := 40 + 3 * max(map(length,indets(P,'rational')));
	Normalizer := `if`(indets(P, {'RootOf','radical','nonreal'}) = {}, normal, evala);
	Ord := degree(P, tau);
	db := RFactors(P, 0);
	ANS := {};
	# P -> subs(x=-x,tau=tau^(-1), P) is an automorphism of C(x)[tau, tau^(-1)]
	for L in [P, collect(subs(x=-x,tau=tau^(-1), P) * tau^Ord,tau)] do
		lc := {seq(i[1]+Ord, i=roots(lcoeff(L,tau),x))};
		while lc <> {} do
			r := lc[1]; lc := lc minus {r};
			if member(true,[seq(type(Normalizer(i-r),posint),i=lc)]) then
				next
			fi;				# Heuristic Factoring:
			A := [L,x,tau,Ord,r,0];		# NthTerm plus list A
			NthTerm(0, A) := 1;		# define a solution u of L.
			for i to Ord do			# MinRec below computes the
				NthTerm(-i, A) := 0	# minimal operator r of u.
			od;
			r, i := MinRec(L, Ord, x, tau, A,r, db);
			if r<>L then					# If r <> L then we found
				i := degree(r,tau);			# a non-trivial factor.
				ANS := ANS union {SimplifyR(`if`(P=L, r,
					collect(subs(x=Ord-i-x,tau=tau^(-1),r)*tau^i, tau)),x,tau)}
			fi			# reversing the -x,tau^(-1) automorphism
		od
	od;
	ANS
end:


###############################################################################
####     MinRec: Minimal Operator of a sequence given by NthTerm(n, A)     ####
###############################################################################

# Compute the n'th term of a recurrence given by a table A.
#
NthTerm := proc(n::nonnegint,A) # A = [L, x, tau, Ord, offset]
options remember;	# remember table is cleared when done.
local m,i;
	m := n-A[4];
	Normalizer(-add(eval(coeff(A[1],A[3],i   ), A[2] = A[5]+m) * thisproc(m+i,A), i = 0..A[4]-1)/
			eval(coeff(A[1],A[3],A[4]), A[2] = A[5]+m) )
end:

# To see if R divides L check if `LREtools/rightdivision`(L,R)[2] = 0.
# This is a fraction-free mod-p version of that.
#
DivisionCheck := proc(L,R,x,tau,p)
local l,r,d,rd,q;
	l := traperror( `mod/Primfield/ReduceField`([L,R], {x,tau}, p) );
	if l = lasterror or map([degree,ldegree],l,tau) <> map([degree,ldegree],[L,R],tau) then
		userinfo(3,'LREtools',"Full division check");
		return evalb(Normalizer(`LREtools/rightdivision`(L,R)[2]) = 0)
	fi;
	l,r := op(l);
	d := degree(l,tau) - degree(r,tau);
	while d >= 0 do
		rd := subs(x=x+d, r);
		q := Normal(lcoeff(l, tau)/lcoeff(rd, tau)) mod p;
		l := Primpart(denom(q)*l - numer(q) * rd * tau^d, tau) mod p;
		d := degree(l,tau) - degree(r,tau);
	od;
	userinfo(`if`(l=0,3,1),'LREtools',cat("Division check ",`if`(l=0,"passed","FAILED")));
	evalb(l = 0)	# Note: Primpart mod p already reduces algebraic extensions.
end:

#  Input is L in C(x)[tau], its order, degree-bound for factors, and
#  a table A with data to compute the NthTerm of the sequence.
#  Output is the minimal order operator that the sequence satisfies
#  for all  n >= min_n  for some finite min_n.
#
#  To ensure termination, only use a proven degree-bound (key = generalized exponents).
#
MinRec := proc(L, Ord, x, tau, A,offset, DegBound)
local tc, i, R, min_n, ord, overQ;
	userinfo(3,'LREtools',"Degree bounds", DegBound);
	tc := coeff(L,tau,0);
	if offset <> 0 then
		tc := collect(subs(x = x + offset, tc), x, Normalizer)
	fi;
	min_n := max(0, seq(`if`(type(i[1],integer), i[1]+1, NULL), i=roots(tc, x)) );
	overQ := evalb({} = indets(L,{'RootOf','radical','nonreal'}) union indets(L) minus {x,tau});
	for ord from 0 to Ord-1 do
		if _Env_LRE_GuessR = true and min_n > 2500 then break fi;
		tc := _passed[3..6], min_n,ord, `if`(ord=0,0,DegBound[ord]);
		if tc[-1] < 0 then
			next
		elif overQ then
			R := traperror(MinRecChRem(tc)); # trapping(modular inverse does not exist)
			if R=lasterror then
				userinfo(3,'LREtools', R, "Switching to Char0 code.")
			elif R = 0 then
				next
			elif DivisionCheck(L,R,x,tau, modp1(Prime(1))) then
				return R, min_n
			elif _Env_LRE_GuessR = true then
				next	# Don't call slow Char0 code under GuessRecurrence
			fi
		fi;
		R := MinRecChar0(tc);
		if R <> 0 and DivisionCheck(L,R,x,tau, modp1(Prime(1))) then
			return R, min_n
		fi
	od;
	L, min_n	# L already had minimal order.
end:

MinRecChar0 := proc(x,tau, A,offset, min_n,ord,db)
local a::nothing, i, j, m, R, eq, ne, s, var;
	# Make an ansatz for the right-factor R based on the degree bound:
	R := add(add(a[i,j] * x^i, i=0..db) * tau^j, j=0..ord);
	var := indets(R) minus {x,tau};
	s := min_n;	# The part of the sequence we use is: u(n+offset) for n >= min_n
	while var <> {} do
		ne := nops(var) + 4; # Taking 4 more equations than the minimum.
		eq := evala({seq(add(eval(coeff(R,tau,m), x = offset+i) * NthTerm(i+m,A),
			m = 0..ord), i = s .. s + ne-1)});
		if s > min_n and eq = {0} and _Env_LRE_GuessR = true then
			# GuessRecurrence uses _Env_LRE_GuessR to avoid bad recurrences
			# but that can interfere with termination. Fix:
			eq := {lcoeff(lcoeff(R,tau),x)}
		fi;
		eq := SolveTools:-Linear(eq, var);
		R := evala(Primpart( subs(eq, R), tau));
		s := s + ne;
		var := indets(R) intersect var
	od;
	R
end:

MinRecChRem := proc(x,tau,A,offset,min_n,ord,db)
local c,r,i,j;
	c := (db+1)*(ord+1);	# c unknowns and c+8 equations.
	r := c+8;
	j := [seq(NthTerm(i,A), i = min_n .. min_n + ord+r-1)];
	r := FirstSolution(j, r,c, _passed[4..7]);
	if r=0 then
		0	
	else
		add(add(r[i*(ord+1)+j+1] * x^i * tau^j, i=0..db), j=0..ord)
	fi
end:

# Compute the First element of a NullSpace basis:
#
FirstSolution := proc(terms, r,c, offset,min_n, ord,db)
local m,k,d,p,A,rnk,bp,i,s,f:=0, # Setting initial value for 'f' to avoid mint warning
		N,lc,rc,x::nothing;
	userinfo(5,'LREtools',cat("Trying order ",ord," and degree ",db));
	m := nops(terms);
	rc := `if`(_Env_LRE_GuessR = true, ceil(m/3) .. m-1, {});
	m := 1;
	k := kernelopts(wordsize);
	d := 'integer'[k/8];
	p := 2^(k/2 - 4);	# Replacing NthTerm with NthTermModP did not make it faster.
	do
		p := nextprime(p);
		A := LinearAlgebra:-Modular:-Mod(p,BuildMatrix(_passed[2..7],terms mod p, p),d);
		# Only do a full Row Reduction if m > 1 (then rank < c is likely)
		LinearAlgebra:-Modular:-RowReduce(p,A,r,c,c,0,0,'rnk',0,0, evalb(m > 1));
		if rnk = c then
			userinfo(5,'LREtools',"No solution");
			return 0
		elif m=1 then
			# NullSpace non-trivial so we need a full Row Reduction:
			LinearAlgebra:-Modular:-RowReduce(p,A,r,c,c,0,0,0,0,0,true)
		else
			bp := false;
			for i to f-1 do if A[i,i]=0 then bp := true fi od;
			if bp then
				next	# discard p
			elif A[f,f] <> 0 then
				m := 1	# discard all previous primes
			fi
		fi:
		for f while A[f,f]<>0 do od;		# First free variable
		A := LinearAlgebra:-Column(A, f);
		A[f] := -1;
		if m=1 then
			N := A; lc := rc
		else
			N := chrem([N,A], [m, p]);
		fi;
		if lc <> {} then
			s := 0; k := ord+1;
			while s=0 do
				s := add(A[i*(ord+1)+k]*x^i, i=0..db); k := k-1
			od;
			lc := {seq(`if`(eval(s, x=i+offset-k) mod p = 0, i, NULL), i=lc)}
		fi;
		m := m * p;
		if lc = {} then       # MinRec/DivisionCheck will check correctness:
			A := iratrecon(N, m, 'scaled');
			if A <> FAIL and length(m) > 3 + max(map(length,A)) then
				userinfo(3,'LREtools',"Solved"); return A
			fi
		elif m > p then       # _Env_LRE_GuessR ==> don't return a bad recurrence.
			userinfo(4,'LREtools',
				"Discarding a recurrence that does not determine higher terms");
			return 0
		fi;
		if assigned(_Env_LRE_GuessM) and length(m) > _Env_LRE_GuessM then
			return 0	# _Env_LRE_GuessM => no large coeff size.
		fi
	od				
end:

BuildMatrix := proc(r,c, offset, min_n, ord, db, vals, p)
local e,a,a1,i,j,M;
	a[0] := 1;
	M := Matrix(r,c);
	for e to r do
		a1 := min_n + offset + e - 1;
		if _npassed = 8 then a1 := a1 mod p fi:
		for i to db do
			a[i] := a1 * a[i-1];
			if _npassed = 8 then a[i] := a[i] mod p fi:
		od;
		for i from 0 to db do for j from 0 to ord do
			M[e, i*(ord+1)+j+1] := a[i] * vals[e+j]
		od od
	od;
	M
end:


#######################################################################
######         Guess Recurrence for a list of terms              ######
#######################################################################

# Similar to gfun[listtorec] but this can find larger recurrences.
#
GuessRecurrence := proc(vals::list, un::function, offset)
local x::nothing,tau::nothing, i,j,  A, c, db, ex, n, ord, overQ, r;
	if _npassed = 2 or offset = 'Minimize' then return
		thisproc(_passed[1..2], 0, _passed[3..-1])
	fi;
	ord := 0; n := 0;
	for i in vals do
		if i=0 then
			n := n+1; ord := max(n, ord)	# Initial order should be more than
		else					# the number of consecutive 0's
			n := 0				
		fi
	od;
	n := nops(vals);
	if n = ord then return un = 0 fi;
	_Env_LRE_GuessR := true;
	overQ := evalb(type(vals, list(rational)));
	do
		ord := ord + 1;
		ex := max(2, floor(n/15));
		db := floor( (n-2*ord-1-ex)/(ord+1) );
		if db < 0 then return FAIL fi;
		ord := floor( (n-db-ex-1)/(db+2) );
		c := (db+1)*(ord+1);
		r := n - ord;
		if r - c < ex then error "unexpected" fi;
		if overQ then
			A := FirstSolution(vals, r,c,offset,0,ord,db)
		else
			A := LinearAlgebra:-NullSpace(BuildMatrix(r,c,offset,0,ord,db,vals));
			if A={} then A := 0 else A := A[-1] fi
		fi;
		if A <> 0 then
			r := add(add(A[i*(ord+1)+j+1] * x^i * tau^j, i=0..db), j=0..ord);
			if _passed[-1]='Minimize' and has(r,x)	# has(r,x): Don't "simplify"
			and ldegree(r,tau) = 0 then		# a constant recurrence.
				r := evala(Primpart(r,tau));	# ldegree > 0 ==> bad initial
				j := degree(r,tau);		# conditions were given.
				A := [r,x,tau,j,offset,1];
				for i to nops(vals) do
					NthTerm(i-1, A) := vals[i]
				od;
				_Env_LRE_x, _Env_LRE_tau := x,tau;
				_Env_LRE_GuessM := 30 + 2 * max(map(length,[coeffs(r,{x,tau})]));
				i := RFactors(r,0);		# don't let coeffs grow too much
				if max(i) < n then
					r := traperror(MinRec(r,j,x,tau,A,offset,i)[1])
				fi;
				if r = lasterror then
					if r[20..27] = "division" then
						next	# We found a bad recurrence.
					else		# Maybe "return FAIL" is better?
						error r
					fi
				fi
			fi;
			return toRecurrence(SimplifyR(r,x,tau), un, x,tau)
		fi
	od
end:

#####################################################################
######       Reduce Recurrence to proven Minimal Order         ######
#####################################################################

MinimalRecurrence := proc(R, un, init, V)
local u,n, x, tau, A, L, Ord, ext, i, j, iv, lc, m, offset, r, B,N, Range;
	if _npassed=1 or not type(un, 'function(name)') then
		u, n := map2(op,0,indets(R,'function')), indets(R,'name');
		if nops(u)*nops(n) <> 1 then
			error "second argument should be of the form u(n) for some names u,n."
		else
			return thisproc(R, u[1](n[1]), _passed[2..-1])
		fi
	fi;
	u, n := op(0,un), op(1,un);
	if not (type(u,name) and type(n,name)) then
		error "second argument should be of the form u(n) for some names u,n."
	elif type(R,set) then
		L := [seq(`if`(has(i,n),i,NULL), i=R)];
		if nops(L)<>1 then
			error "First argument should contain one linear homogeneous recurrence"
		fi;
		return thisproc(L[1], un, R minus {L[1]}, _passed[3..-1])
	elif not has(R,u) then
		error "dependent variable does not appear in the recurrence"
	fi;
	# Now check if the sequence is defined for all n
	iv := indets(init, u('anything'));
	if not type(init,set(equation)) or iv <> map(lhs,init) or has(init,n) then
		error "Third argument should be a set of initial terms {u(0)=.., u(1)=.., ...}."
	fi;
	offset := min(seq(op(1,i), i=iv));
	x, tau := _Env_LRE_x, _Env_LRE_tau;
	ext := indets([_passed], {'RootOf','radical','nonreal'});
	Normalizer := `if`(ext = {}, normal, evala);
	L := toOperator(R, u(n), x,tau);
	Ord := degree(L, tau);
	m := [seq([i, Normalizer(subs(x=offset+i, init,
					add(coeff(L,tau,j)*u(offset+i+j),j=0..Ord)))],
				 i=0..nops(init)-Ord-1)];
	m := [seq(`if`(i[2]<>0 and not has(i[2],u), i[1]+offset, NULL),i=m)];
	if m <> [] then
		userinfo(1, 'LREtools', cat("Discarding some initial conditions; Recurrence does "
			"not hold for ", n=op(m)));
		m := max(m);
		return thisproc(R, un, {seq(`if`(op(lhs(i))>m,i,NULL),i=init)}, _passed[4..-1])
	fi;
	if {seq(u(offset+i), i=0..Ord-1)} minus iv <> {} then
		error "Need at least as many initial terms as the order of the recurrence."
	fi;
	lc := `if`(offset=0, lcoeff(L,tau), evala(Expand(subs(x = x + offset, lcoeff(L,tau)))));
	m := min(seq(`if`(type(i[1],nonnegint) and not member(u(i[1]+Ord+offset), iv),
		i[1], NULL), i=roots(lc,x)));
	if m<>infinity then
		error "recurrence + initial terms do not determine", u(m+Ord+offset)
	fi;
	A := [L,x,tau,Ord,offset,2];
	for i in init do
		NthTerm(op(1,lhs(i))-offset, A) := rhs(i)
	od:
	r, m := MinRec(L, Ord, x, tau, A,offset, RFactors(L, 0, ext));
	N := degree(r,tau);
	if _npassed > 3 and _passed[-1] = `+` then

	############################################################################
	###  SumDecompose.  Write u(n) as u1(n) + u2(n) + .... of minimal order  ###
	############################################################################

		# Key step: Write the Minimal Order Operator r as an LCLM:
		L := [op(RFactorsLCLM(r))];
		forget(BasisSolutions); forget(SolSubSpace);
		m := max(m,seq(`if`(type(i[1],integer),i[1]+m+1,NULL), i = roots(
			mul(evala(Expand(eval(lcoeff(i,tau),x=x+offset) )),i=L),x)));
		B := [seq(BasSol(i,x,tau, m+offset,N), i=L)];
		j := add(B) - [seq(NthTerm(m+i,A), i=0..2*N)];
		forget(NthTerm);
		iv := indets(B,'name') minus indets(L,'name');
		B := eval(B, SolveTools:-Linear(j, iv));
		iv := iv intersect indets(B);
		B := subs({seq(iv[i] = _Z[i], i=1..nops(iv))},B);
		if _npassed > 4 and type(V,'name') then
			V :=  proc(c,n)
			options remember;
			local L, x, tau, ord, offset, i;
				L, x, tau, ord, offset := thisproc(c,infinity);
				if not type(n - offset, 'posint') then
					'thisproc(_passed)'
				else
					L := eval(L, x=n-ord);
					evala(-add(coeff(L,tau,i)*thisproc(c,n+i-ord),
						i = 0..ord-1) / lcoeff(L,tau))
				fi
			end:
			for i to nops(L) do
				V(i,infinity) := L[i], x, tau, degree(L[i],tau), m+offset;
				for j from 0 to 2*N do
					V(i,j+m+offset) := B[i][j+1]
				od
			od
		fi;
		return un = add((u || i)(n), i=1..nops(L)),
			seq(toRecurrence(SimplifyR(L[i],x,tau), (u||i)(n), x, tau),
				i=1..nops(B)), "Relation holds for", n >= offset + m
	else
		if r = L then
			Range := "Relation holds for", n >= offset, "Initial terms", init
		else
			while m > 0 and Normalizer(add(eval(coeff(r,tau,i),x = offset+m-1) *
				NthTerm(i+m-1,A),i = 0..N)) = 0 do
				m--;
			od;
			lc := {seq(m+i, i=0..N-1),
				seq(`if`(type(i[1]-m,nonnegint),i[1]+N, NULL),
					i=roots(evala(Expand(subs(x = x + offset, lcoeff(r,tau)))),x))};
			Range := "Relation holds for", n >= offset + m,
				"Initial terms", {seq(u(i+offset) = NthTerm(i, A), i=lc)}
		fi
	fi;
	forget(NthTerm);
	`if`(r=L, `if`(type(R,'`=`'),R,R=0),
			toRecurrence(SimplifyR(r,x,tau), u(n), x, tau)),
		Range
end:

# A variation on "BasisSolutions" described in Section RFactorsLCLM below.
BasSol := proc(L,x,tau, offset,n)
local A, i, a::nothing;
	A := [L,x,tau,degree(L,tau),offset,a];
	for i to degree(L,tau) do
		NthTerm(i-1, A) := a[i]
	od;
	[seq(NthTerm(i, A), i=0..2*n)]
end:


###########################################################################
###      Write L as an LCLM of lower order operators when possible      ###
###########################################################################

# Write L as a Complete LCLM of operators, meaning that the output
# operators can not be further decomposed as an LCLM of lower order
# operators (that does not imply that they are irreducible!) (instead,
# it means that they have a {unique} irreducible left-factor).
#
# This allows a sequence u(n) to be decomposed as u(n) = u1(n) + ...
# Completeness means that each term does not allow a further sum
# decomposition. We need the recurrence for u(n) to have minimal order
# which is why "SumDecompose" sits inside program MinimalRecurrence.
#
RFactorsLCLM := proc(L)
local S, ds, d, v, n, red, x,tau;
global `LREtools/FactTable`;
options remember;
	x, tau := _Env_LRE_x, _Env_LRE_tau;
	n := degree(L,tau);
	if n < 2 then return {L} fi;
	S := RFactorsHeuristic(L);
	if Complete(S,L,x,tau,'red') then return red fi;
	ds := [seq(`if`(n=2*d,d,op([d,n-d])),d=1..floor(n/2))];
	for d in ds do
		v := RightFactors(L,d,'select');
		if v <> {} then
			S := S union v;
			if Complete(S,L,x,tau,'red') then return red fi;
		fi
	od;
	`LREtools/FactTable`[L] := S;	# For use in SolveLRE
	{L}
end:

# At any stage in RFactorsLCLM,  S is a subset of the set of right-factors.
# This program checks if L = LCLM(S).
# It does this by taking bases of solutions of the operators in S and
# checking if their combined rank is order(L).
# These BasisSolutions are represented by their values in some range.
#
# If L = LCLM(S), the program checks if still holds after removing elements
# of S, starting with the largest ones. After that, to ensure a complete
# decomposition, it applies recursion (RFactorsLCLM) to S.
#
Complete := proc(S, L,x,tau, red)
local R, A, B, Ord, i;
	Ord := degree(L,tau);
	if add(degree(i,tau),i=S) < Ord then return false fi;
	B := BasisSolutions(L,x,tau,0) ;
	B := {seq(SolSubSpace(R, B,x,tau), R=S)};
	if LinearAlgebra:-Rank(Matrix([op(B)])) < Ord then
		return false
	elif _npassed < 5 then
		return true
	fi;
	A := [seq([i, degree(i,tau), degree(i,x)], i=S)];
	A := sort(A, (i,j) -> (i[2]>j[2] or (i[2]=j[2] and i[3]>j[3])));
	A := map(i -> i[1], A);
	i := 1;
	while i <= nops(A) do
		B := subsop(i = NULL, A);
		if Complete(B, L,x,tau) then A := B else i := i+1 fi
	od;
	A := {op(A)}; i := nops(A);
	if _passed[-1] <> 0 then
		A := map(op,map(RFactorsLCLM,A));
		if nops(A) > i then
			thisproc(A, L,x,tau, 'A', 0)
		fi
	fi;
	red := A; true
end:

BasisSolutions := proc(L,x,tau, offset)
local A, i, j, m, n, v, a::nothing;
options remember;		# remember table is cleared when done.
	m := 0;
	n := degree(L,tau);
	v := [tcoeff(L,tau), lcoeff(L,tau)];
	if offset <> 0 then
		v := evala(Expand( subs(x=x+offset, v) ))
	fi;
	for j to 2 do for i in roots(v[j],x) do if type(i[1],integer) then
		m := max(m, i[1]+1)
	fi od od;
	m := m + offset;
	A := [L,x,tau,n,m,a];
	for i to n do
		NthTerm(i-1, A) := a[i]
	od;
	[m, {seq(a[i], i=1..n)}, [seq(NthTerm(i, A), i=0..2*n)]]
end:

# The subspace of SPAN(B) that satisfies R.
#
SolSubSpace := proc(R, B, x,tau)
local S, m, n, var, i;
options remember;		# remember table is cleared when done.
	m, n:= B[1], nops(B[2]);
	S := SolveTools:-Linear({ApplyR(m, B[3], R, x,tau,degree(R,tau))}, B[2]);
	S := eval(B[3][1..n], S);
	var := indets(S) intersect B[2];
	if nops(var) <> degree(R,tau) then error "dimension mismatch" fi;
	seq(map(coeff,S,i), i=var);
end:

ApplyR := proc(m,b,R, x,tau,ord)
local i,j;
	seq(add(eval( coeff(R,tau,i), x=m+j) * b[1+i+j], i=0..ord), j=0..nops(b)-ord-1)
end:

# In case there are families with infinitely many factors, see procedure PluckerRelations
# for the format, then we have to select finitely many of them. This works best when
# these families have low dimension d and few equations eq, which tends to be the case
# when when using MinimalRecurrence. 
#
SelectFactors := proc(S,id)
local i, R, a, d, eq, s, v;
	if type(S,list) then
		R, d, eq := S[1], S[3], S[5];		# R is d-dimensional family with equations eq.
		v := indets(R) minus id;		# Find a value for the unknowns in v.
		for s from 0 to nops(v)-d do
			a := solve(eq union v[s+1..s+d], v);	# Want 1 member of a d-dimensional family,
			if a<>NULL then				# so we equated d unknowns from v to 0.
				a := sort([a],length)[1];
				if indets(map(rhs,a), {'RootOf','radical','nonreal'}) minus id = {} then
					# Avoiding new algebraic numbers
					eq := {seq(i=0, i=indets(map(rhs,a)) intersect v)};
					return eval(eval(R, a), eq)
				fi
			fi
		od;
		NULL
	elif type(S,set) then
		map(thisproc,S,id)
	else
		S
	fi
end:
