1######################### BEGIN COPYRIGHT MESSAGE #########################
2# GBNP - computing Gröbner bases of noncommutative polynomials
3# Copyright 2001-2010 by Arjeh M. Cohen, Dié A.H. Gijsbers, Jan Willem
4# Knopper, Chris Krook. Address: Discrete Algebra and Geometry (DAM) group
5# at the Department of Mathematics and Computer Science of Eindhoven
6# University of Technology.
7#
8# For acknowledgements see the manual. The manual can be found in several
9# formats in the doc subdirectory of the GBNP distribution. The
10# acknowledgements formatted as text can be found in the file chap0.txt.
11#
12# GBNP is free software; you can redistribute it and/or modify it under
13# the terms of the Lesser GNU General Public License as published by the
14# Free Software Foundation (FSF); either version 2.1 of the License, or
15# (at your option) any later version. For details, see the file 'LGPL' in
16# the doc subdirectory of the GBNP distribution or see the FSF's own site:
17# http://www.gnu.org/licenses/lgpl.html
18########################## END COPYRIGHT MESSAGE ##########################
19
20# $Id: occurtree.gi 14294 2011-05-24 12:54:55Z jwk $
21
22# createtree
23# special case GB 1
24# different defintion.
25# integer in place 1 of the array or in place pg+1 of the PTS array
26
27### things to search for (first line a monomial, second the list represented by
28### the tree):
29###
30### -----===-----       ===       -----===
31###      ===	   -----===-----       ===-----
32###	type 1         type 2         type 3
33###
34
35### Functions:
36###
37### - tree manipulation:
38### GBNP.CreateOccurTreeLR
39### GBNP.CreateOccurTreePTSLR
40### GBNP.CreateOccurTreePTSLRimpl
41### GBNP.AddMonToTreePTSLR
42### GBNP.RemoveMonFromTreePTSLR
43### GBNP.SortParallelOT
44### - lookup helpfuncions		type	LR	extra
45### GBNP.LookUpOccurTreeAllPTSLRPos	1	LR	all
46### GBNP.LookUpOccurTreePTSLRPos	1	LR	-
47### GBNP.LookUpOccurTreeForObsPTSLRPos	3	LR	all
48###
49### - lookup functions			type	LR
50### GBNP.OccurInLstT                    1	L	-
51### GBNP.OccurInLstPTSLR		1	LR	-
52### GBNP.OccurLeftInLstT		1	L	from start
53### GBNP.LookUpOccurTreeAllLstPTSLR	1	LR	all
54### GBNP.LookUpOccurTreeForObsPTSLR	3	LR	all
55
56#####################################
57### GBNP.CreateOccurTreePTSLRimpl ###
58#####################################
59### Creates an occurtree, possibly with module generators
60###
61### impl -> the actual implementation; no changes on pg (like in the PTSLR
62### variant)
63###
64### Arguments:
65###
66### - L		list of monomials
67### - pg	number of monomial generators
68### - left	boolean, true means non-reversed
69###
70### Returns:
71### - the occurtree formed
72###
73### #GBNP.CreateOccurTreePTSLRimpl uses: GBNP.AddMonToTreePTSLR#
74### #GBNP.CreateOccurTreePTSLRimpl is used in: GBNP.CreateOccurTreeLR GBNP.CreateOccurTreePTSLR#
75###
76
77GBNP.CreateOccurTreePTSLRimpl:=function(L,pg,left)
78local i,OT;
79	OT:=rec(tree:=[],tree2arr:=[],arr2tree:=[],nextnum:=1,pg:=pg);
80	for i in [1..Length(L)] do
81		GBNP.AddMonToTreePTSLR(L[i],i,OT,left);
82	od;
83	return OT;
84end;
85
86##############################
87### GBNP.CreateOccurTreeLR ###
88##############################
89### Creates an occurtree, without module generators
90###
91### Arguments:
92### - L		list of monomials
93### - left	boolean, true means non-reversed
94###
95### Returns:
96### - the occurtree formed
97###
98### #GBNP.CreateOccurTreeLR uses: GBNP.CreateOccurTreePTSLRimpl#
99### #GBNP.CreateOccurTreeLR is used in: DetermineGrowthQA FinCheckQA GBNP.RedAddToTree GraphOfChains GraphOfNormalWords HilbertSeriesQA#
100###
101
102GBNP.CreateOccurTreeLR:=function(L,left)
103	return GBNP.CreateOccurTreePTSLRimpl(L,0,left);
104end;
105
106#################################
107### GBNP.CreateOccurTreePTSLR ###
108#################################
109### Creates an occurtree, possibly with module generators
110###
111### Arguments:
112###
113### - L		list of monomials
114### - pg	number of monomial generators
115### - left	boolean, true means non-reversed
116###
117### Returns:
118### - the occurtree formed
119###
120### #GBNP.CreateOccurTreePTSLR uses: GBNP.CreateOccurTreePTSLRimpl GBNP.GetOptions#
121### #GBNP.CreateOccurTreePTSLR is used in: GBNP.AllObs GBNP.IsGrobnerBasisTest GBNP.LeftObsT GBNP.NondivMonsPTS GBNP.NondivMonsPTSenum GBNP.ReducePol2 GBNP.RightObsT GBNP.SGrobnerLoops GBNP.StrongNormalFormTall IsGrobnerPair MakeGrobnerPair#
122###
123
124GBNP.CreateOccurTreePTSLR:=function(L,pg,left)
125        if (pg <> GBNP.GetOptions().pg) then
126		Info(InfoGBNP,2,"Warning: CreateOccurTreePTSLR: pg argument (",pg,") is not the same as pg option (",GBNP.GetOptions().pg,")\n");
127	fi;
128
129	# also take into account options for safety (warn if these are
130	# different)
131	pg:=Maximum(GBNP.GetOptions().pg,pg);
132
133	return GBNP.CreateOccurTreePTSLRimpl(L, pg, left);
134end;
135
136#######################################
137### GBNP.LookUpOccurTreeAllPTSLRPos ###
138#######################################
139###
140### Looks up all monomials in the tree that occur in the monomial mon from
141### position startpos.
142###
143### Arguments:
144### - mon		monomial to check
145### - OT		occurtree to use for lookup
146### - left		true: non-reversed
147### - startpos		position of mon to start checking
148###
149### Returns:
150### - the array indices of all matching monomials
151###
152### #GBNP.LookUpOccurTreeAllPTSLRPos uses:#
153### #GBNP.LookUpOccurTreeAllPTSLRPos is used in: GBNP.LookUpOccurTreeAllLstPTSLR#
154###
155
156GBNP.LookUpOccurTreeAllPTSLRPos:=function(mon,OT,left,startpos)
157local	pos,	# index of mon
158	r,	# part of the tree
159	pi,	# add to index
160	ans,	# all indices found sofar
161	len, 	# length of the monomial
162	pos2;	# pos corrected for left/right
163
164		# arrays go from 1..
165		# first pg entries are prefix gens, the next one is skipped
166		# and the rest is for two-sided generators
167
168	pi:=OT.pg+1;
169	ans:=[];
170
171	r:=OT.tree;len:=Length(mon);
172	pos:=startpos; # 1 is a usual start
173
174	#follow OT as far as possible
175	while (pos<=len) do
176		if left then
177			pos2:=pos;
178		else
179			pos2:=len-pos+1;
180		fi;
181
182		if IsBound(r[pi]) then
183			# found the answer early
184			Add(ans,OT.tree2arr[r[pi]]);
185		fi;
186
187		if IsBound(r[mon[pos2]+pi]) then
188			r:=r[mon[pos2]+pi];
189		else	# nothing more can be found
190			return ans;
191		fi;
192		pos:=pos+1;
193	od;
194
195	# nothing left to check
196
197	if IsBound(r[pi]) then
198		Add(ans,OT.tree2arr[r[pi]]);
199	fi;
200	return ans; # note that ans is sorted (smallest ones found first)
201end;
202
203####################################
204### GBNP.LookUpOccurTreePTSLRPos ###
205####################################
206###
207### Looks for a monomial occurring in mon from position startpos.
208###
209###   startpos		(image for left=true case)
210###      |
211### -----====-----	type 1
212###      ====
213###
214### Arguments:
215###
216### - mon		monomial to check
217### - OT		occurtree used
218### - left	true: non-reversed
219### - startpos	position of mon to start checking
220###
221### Returns:
222### - the array index of a monomial or 0 if no monomials can be found
223###
224### #GBNP.LookUpOccurTreePTSLRPos uses:#
225### #GBNP.LookUpOccurTreePTSLRPos is used in: DetermineGrowthQA FinCheckQA GBNP.LeftObsT GBNP.NondivMonsPTS GBNP.OccurInLstPTSLR GBNP.OccurLeftInLstT GBNP.RightObsT countfun#
226###
227
228GBNP.LookUpOccurTreePTSLRPos:=function(mon,OT,left,startpos)
229local	pos,	# index of mon
230	r,	# part of the tree
231	pi,	# add to index
232	len, 	# length of the monomial
233	pos2;	# pos corrected for left/right
234
235		# arrays go from 1..
236		# first pg entries are prefix gens, the next one is skipped
237		# and the rest is for two-sided generators
238
239	pi:=OT.pg+1;
240
241	r:=OT.tree;len:=Length(mon);
242	pos:=startpos; # 1 is a usual start
243
244	#follow OT as far as possible
245	while (pos<=len) do
246		if left then
247			pos2:=pos;
248		else
249			pos2:=len-pos+1;
250		fi;
251
252		if IsBound(r[pi]) then
253			# found the answer early
254			return OT.tree2arr[r[pi]];
255		fi;
256
257		if IsBound(r[mon[pos2]+pi]) then
258			r:=r[mon[pos2]+pi];
259		else	# nothing can be found
260			return 0;
261		fi;
262		pos:=pos+1;
263	od;
264
265	# nothing left to check
266
267	if IsBound(r[pi]) then
268		return OT.tree2arr[r[pi]];
269	fi;
270
271	return 0;
272end;
273
274
275########################
276### GBNP.OccurInLstT ###
277########################
278###
279### Searches for monomials from the list in <mon>.
280###
281### Arguments:
282### - mon	monomial to check
283### - LOT	a left-occur tree
284###
285### Returns:
286### - [nr,i]
287### 	Where nr = the array number of the monomial found
288### 	and i = the position from the left (i is as small as possible)
289### 	if nothing is found then [0,0] is returned.
290###
291### #GBNP.OccurInLstT uses: GBNP.OccurInLstPTSLR#
292### #GBNP.OccurInLstT is used in: GBNP.NormalForm2T GBNP.SGrobnerLoops GBNP.StrongNormalForm2Tall GBNP.StrongNormalForm3Dall GBNP.THeapOTCheck#
293###
294
295GBNP.OccurInLstT:=function(mon,LOT)
296	return GBNP.OccurInLstPTSLR(mon,LOT,true);
297end;
298
299############################
300### GBNP.OccurInLstPTSLR ###
301############################
302###
303### Searches for monomials from the list in <mon>.
304###
305### Arguments:
306### - mon	monomial to check
307### - LOT	a left-occur tree
308### - left	true -> non-reversed
309###
310### Returns:
311### - [nr,i]
312### 	Where nr = the array number of the monomial found
313### 	and i = the position from the left (right if left=false) (i is as small
314###     as possible) if nothing is found then [0,0] is returned.
315###
316### #GBNP.OccurInLstPTSLR uses: GBNP.LookUpOccurTreePTSLRPos#
317### #GBNP.OccurInLstPTSLR is used in: GBNP.OccurInLstT GraphOfChains GraphOfNormalWords HilbertSeriesQA IsGrobnerPair MakeGrobnerPair#
318###
319
320GBNP.OccurInLstPTSLR:=function(mon,LOT,left)
321local 	i,
322	ans;
323	for i in [1..Length(mon)] do
324		ans:=GBNP.LookUpOccurTreePTSLRPos(mon,LOT,left,i);
325		if ans<>0 then
326			return [ans,i];
327		fi;
328	od;
329
330	return [0,0];
331end;
332
333############################
334### GBNP.OccurLeftInLstT ###
335############################
336###
337### Searches for monomials from the list occurring at the left in <mon>.
338###
339### Arguments:
340### - mon	monomial to check
341### - LOT	occurtree used (left occur tree)
342###
343### Returns:
344### - [nr,i]
345### 	Where nr = the array number of the monomial found
346### 	and i = 1 if a monomial is found (compatible with GBNP.OccurInLstT)
347### 	if nothing is found then [0,0] is returned.
348###
349### #GBNP.OccurLeftInLstT uses: GBNP.LookUpOccurTreePTSLRPos#
350### #GBNP.OccurLeftInLstT is used in:#
351###
352
353GBNP.OccurLeftInLstT:=function(mon,LOT)
354local ans;
355	ans:=GBNP.LookUpOccurTreePTSLRPos(mon,LOT,true,1);
356	if ans<>0 then
357		return [ans,1];
358	fi;
359	return [0,0];
360end;
361
362#######################################
363### GBNP.LookUpOccurTreeAllLstPTSLR ###
364#######################################
365###
366### Looks up all monomials from a list starting with <mon>
367###
368### Arguments:
369### - mon	the monomial to check
370### - OT	the occur tree used
371### - left	true if not reversed
372###
373### Returns:
374### - A list of matches in the form [nr, i], where nr is the monomial found and
375###   i the left-most position where it is found
376###
377### #GBNP.LookUpOccurTreeAllLstPTSLR uses: GBNP.LookUpOccurTreeAllPTSLRPos#
378### #GBNP.LookUpOccurTreeAllLstPTSLR is used in: GBNP.SGrobnerLoops GBNP.StrongNormalForm2TS GBNP.StrongNormalForm2TSPTS GBNP.StrongNormalForm3Dall#
379###
380
381GBNP.LookUpOccurTreeAllLstPTSLR:=function(mon,OT,left)
382local 	i,j,	# counter
383	allans,	# sparse list of answer
384	ansind,	# indices of ans
385	ans;	# what will be returned
386
387	allans:=[];ansind:=[];
388	for i in [1..Maximum(1,Length(mon))] do
389		for j in GBNP.LookUpOccurTreeAllPTSLRPos(mon,OT,left,i) do
390			if not IsBound(allans[j]) then
391				allans[j]:=i;
392				AddSet(ansind,j);
393			fi;
394		od;
395	od;
396	ans:=[];
397	for i in ansind do
398		Add(ans,[i,allans[i]]);
399	od;
400	return ans;# not sorted
401end;
402
403##########################################
404### GBNP.LookUpOccurTreeForObsPTSLRPos ###
405##########################################
406###
407### function to search for obstructions with occur trees (partial task)
408###
409### searches for obstructions of the form:
410###		    startpos
411###                 |
412### mon:	----===		type 3 (picture for left=true)
413### 		    ===----
414###
415### Arguments:
416### - mon		Monomial to look for obstructions in
417### - OT		occur tree
418### - left		true -> non-reversed
419### - startpos		startposition of YYYY in mon
420###
421### Returns:
422### - A list of indices of monomials from the tree that match.
423###
424### #GBNP.LookUpOccurTreeForObsPTSLRPos uses:#
425### #GBNP.LookUpOccurTreeForObsPTSLRPos is used in: GBNP.LookUpOccurTreeForObsPTSLR#
426###
427
428GBNP.LookUpOccurTreeForObsPTSLRPos:=function(mon,OT,left,startpos)
429local	pos,	# index of mon
430	r,	# part of the tree
431	pi,	# add to index
432	ans,	# all indices found sofar
433	len, 	# length of the monomial
434	pos2,	# pos corrected for left/right
435	f;
436
437		# arrays go from 1..
438		# first pg entries are prefix gens, the next one is skipped
439		# and the rest is for two-sided generators
440
441	pi:=OT.pg+1;
442
443	r:=OT.tree;len:=Length(mon);
444	pos:=startpos; # 1 is a usual start
445
446	#follow OT as far as possible
447	while (pos<=len) do
448		if left then
449			pos2:=pos;
450		else
451			pos2:=len-pos+1;
452		fi;
453
454		if IsBound(r[pi]) then
455			# found the answer early
456		fi;
457
458		if IsBound(r[mon[pos2]+pi]) then
459			r:=r[mon[pos2]+pi];
460		else	# nothing more can be found
461			return [];
462		fi;
463		pos:=pos+1;
464	od;
465
466	# now return things still left in r:
467
468	return List(Flat(r),x->OT.tree2arr[x]);
469end;
470
471#######################################
472### GBNP.LookUpOccurTreeForObsPTSLR ###
473#######################################
474###
475### function to search for obstructions with occur trees
476###
477### searches for obstructions of the form:
478### mon:	xxxxxYYYYY
479### 		     YYYYYzzz
480### where xxxx is as small as possible
481###
482### Arguments:
483### - mon	monomial to check
484### - j		number of the monomial (to filter out itself), can be 0 ->
485###			filter out nothing
486### - GOT	Occur tree of G
487### - left	true -> non-reversed
488###
489### Returns:
490### - an array of lists [nr,i], where nr is the index in the array and i the
491### 	position of the first 'Y'
492###
493### #GBNP.LookUpOccurTreeForObsPTSLR uses: GBNP.LookUpOccurTreeForObsPTSLRPos#
494### #GBNP.LookUpOccurTreeForObsPTSLR is used in: GBNP.LeftObsT GBNP.RightObsT GraphOfChains HilbertSeriesQA#
495###
496
497GBNP.LookUpOccurTreeForObsPTSLR:=function(mon,j,GOT,left)
498local	i,o,
499	allans,
500	ansind,
501	ans;
502
503	ans:=[];
504	for i in [1..Length(mon)] do
505		for o in GBNP.LookUpOccurTreeForObsPTSLRPos(mon,GOT,left,i)
506		do
507			if not (i=1 and o=j) then # why this condition ?
508		        	Add(ans,[o,i]);
509			fi;
510		od;
511	od;
512
513	return ans;# not sorted
514end;
515
516##############################
517### GBNP.AddMonToTreePTSLR ###
518##############################
519###
520### Adds a monomial <mon> to the tree <OT> that does not occur in the tree
521### already.
522###
523### Arguments:
524### - mon	the monomial to add
525### - i		the index in the corresponding array (assumed to be unique)
526###		i=-1 means adding to the end of the array
527### - OT	occur tree
528### - left	true -> non-reversed
529###
530### Returns:
531###  - nothing returned (but the tree <OT> is updated)
532###
533### #GBNP.AddMonToTreePTSLR uses:#
534### #GBNP.AddMonToTreePTSLR is used in: GBNP.AllObs GBNP.CentralT GBNP.CreateOccurTreePTSLRimpl GBNP.IsGrobnerBasisTest GBNP.LeftObsT GBNP.ObsTall GBNP.ReducePol2 GBNP.RightObsT GBNP.SGrobnerLoops MakeGrobnerPair THeapOT#
535###
536
537GBNP.AddMonToTreePTSLR:=function(mon,i,OT,left)
538local	pos,	# index of mon
539	r,oldr,	# part of the tree
540	pi,	# addition factor
541	pos2,	# pos with left/right correction
542	len, 	# length of the monomial
543	arrnum,	# index in arr2tree
544	treenum,# index in tree
545	j,lat;
546
547	#Info(InfoGBNP,4,"AddMonToTreePTSLR i:",i," mon:",mon);
548	pi:=OT.pg+1;
549
550	r:=OT.tree;len:=Length(mon);
551	pos:=1;oldr:=OT.tree;
552	treenum:=OT.nextnum;
553
554	if IsBound(OT.tree2arr[OT.nextnum]) then
555		OT.nextnum:=OT.tree2arr[OT.nextnum];
556	else
557		OT.nextnum:=OT.nextnum+1; # end of the tree
558	fi;
559
560	if (i=-1) then
561		arrnum:=Length(OT.arr2tree)+1;
562		OT.tree2arr[treenum]:=arrnum;
563		Add(OT.arr2tree,treenum);
564	else
565		arrnum:=i;
566		InsertElmList(OT.arr2tree,i,treenum);
567		for j in [i..Length(OT.arr2tree)] do
568			OT.tree2arr[OT.arr2tree[j]]:=j;
569		od;
570	fi;
571	#Info(InfoGBNP,5,"AddMonToTreePTSLR arrnum:",arrnum);
572
573	#follow OT as far as possible
574	while (pos<=len) do
575		if left then
576			pos2:=pos;
577		else
578			pos2:=len-pos+1;
579		fi;
580
581		#if IsBound(r[pi]) then
582		#	# nevermind adding, use the shorter one instead
583		#	return;
584		# add anyway, easier for proving
585		if IsBound(r[mon[pos2]+pi]) then # follow the existing prefix
586			r:=r[mon[pos2]+pi];
587		else # add a new prefix
588			r[mon[pos2]+pi]:=[];
589			r:=r[mon[pos2]+pi];
590		fi;
591		pos:=pos+1;
592	od;
593	if not IsBound(r[pi]) then
594		r[pi]:=treenum;
595	fi;
596end;
597
598###################################
599### GBNP.RemoveMonFromTreePTSLR ###
600###################################
601###
602### Removes a monomial <mon> from the occurtree <OT>
603###
604### Arguments:
605### - mon	the monomial to remove
606### - i		the index of the monomial
607### - OT	the tree to remove <mon> from
608### - left	true -> non-reversed
609###
610### Returns:
611### 	nothing, but removes <mon> from <OT>
612###
613### #GBNP.RemoveMonFromTreePTSLR uses:#
614### #GBNP.RemoveMonFromTreePTSLR is used in: GBNP.ReducePol2 GBNP.SGrobnerLoops THeapOT#
615###
616
617GBNP.RemoveMonFromTreePTSLR:=function(mon,i,OT,left)
618local	pos,	# index of mon
619	r,oldr,	# part of the tree
620	oldind,
621	pi,
622	len, 	# length of the monomial
623	pos2,	# pos corrected for left/right
624	j;
625
626
627	# if a monomial is not in the tree then nothing is deleted
628	#Assert(1,i=GBNP.LookUpRightOccurTree(mon,OT),
629	#	"Monomial not in tree.");
630	#Info(InfoGBNP,4,"RemoveMonFromTreePTSLR i:",i," mon:",mon);
631
632	pi:=OT.pg+1;
633
634	r:=OT.tree;
635	len:=Length(mon);pos:=1;
636
637	oldr:=0;
638
639	if len=0 then
640		oldind:=pi;
641	else
642		if left then
643			pos2:=pos;
644		else
645			pos2:=len-pos+1;
646		fi;
647
648		oldind:=mon[pos2]+pi;
649	fi;
650
651	#follow OT as far as possible
652	while (pos<=len) do
653		if left then
654			pos2:=pos;
655		else
656			pos2:=len-pos+1;
657		fi;
658
659		#if IsBound(r) then
660		#	# not added, so nothing to remove
661		#	return OT;
662		if IsBound(r[mon[pos2]+pi]) then # follow the existing prefix
663			if Number(r)<>1 then
664				# if number=1 than this could be the tail for
665				# this one
666				oldr:=r;oldind:=mon[pos2]+pi;
667			fi;
668			r:=r[mon[pos2]+pi];
669		else # not added, so nothing to remove
670			Info(InfoGBNP,3,"could not remove!");
671			return ;
672		fi;
673		pos:=pos+1;
674	od;
675
676	if IsBound(r[pi]) and OT.tree2arr[r[pi]]=i then # remove
677		if Number(r)<>1 then
678			Unbind(r[pi]);
679		else
680			if oldr=0 then #clean the whole tree
681				Unbind(OT.tree[oldind]);
682			else
683				# r should now be i
684				Unbind(oldr[oldind]);
685				# remove the tail that is exclusively for
686				# this function
687			fi;
688		fi;
689	fi;
690	OT.tree2arr[OT.arr2tree[i]]:=OT.nextnum;
691	OT.nextnum:=OT.arr2tree[i];
692	RemoveElmList(OT.arr2tree,i);
693	for j in [i..Length(OT.arr2tree)] do
694		OT.tree2arr[OT.arr2tree[j]]:=j;
695	od;
696end;
697
698###########################
699### GBNP.SortParallelOT ###
700###########################
701###
702### Use this function when sorting the array corresponding with the indices.
703### In case of a parallelsort, the unsorted parallel can be copied beforehand
704### and used as argument for this function, which updates the two arrays
705### of the occur tree
706###
707### Arguments:
708### - l			the help list
709### - OT		the tree (with arrays arr2tree and tree2arr)
710### - searchfun		the search function (usually LtNP)
711###
712### Returns:
713### 	nothing, but changes the tree: sorts arr2tree (and updates tree2arr)
714###
715### #GBNP.SortParallelOT uses:#
716### #GBNP.SortParallelOT is used in: GBNP.ObsTall THeapOT#
717###
718
719GBNP.SortParallelOT:=function(l,OT,searchfun)
720local i;
721	SortParallel(l,OT.arr2tree,searchfun);
722	for i in [1..Length(OT.arr2tree)]
723	do
724		OT.tree2arr[OT.arr2tree[i]]:=i;
725	od;
726end;
727
728
729#######################
730### GBNP.NondivMons ###
731#######################
732###
733### Arguments:
734### lts	 	- list of leading terms
735### t		- number of elements in the alphabet
736### maxno	- maximum number of monomials to be found
737###
738### Returns:
739### ans		- List of nondiv. monomials
740###
741### #GBNP.NondivMons uses: GBNP.NondivMonsPTS#
742### #GBNP.NondivMons is used in: BaseQA#
743###
744
745GBNP.NondivMons := function(lts,t,maxno)
746	return GBNP.NondivMonsPTS([],lts,t,0,maxno);
747end;
748
749##########################
750### GBNP.NondivMonsPTS ###
751##########################
752###
753### Arguments:
754### plts	- list of leading terms for prefix rules
755### lts	 	- list of leading terms
756### t		- number of elements in the alphabet
757### mt		- number of elements in the module-alphabet
758### maxno	- maximum number of monomials to be found
759###
760### Returns:
761### ans		- List of nondiv. monomials
762###
763### #GBNP.NondivMonsPTS uses: GBNP.CreateOccurTreePTSLR GBNP.LookUpOccurTreePTSLRPos GBNP.OccurInLst#
764### #GBNP.NondivMonsPTS is used in: BaseQM GBNP.NondivMons#
765###
766
767GBNP.NondivMonsPTS := function(plts,lts,t,mt,maxno) local h,i,ct,hi,tt,ans,idf,lvl,cont,ROT,pLOT;
768
769#jwk schreef uitzetten op 11 aug 2009
770#mt:=GBNP.GetOptions().pg; 		# XXX even not longer needed
771    if plts<>[] then			# XXX mt should not be changed here
772    	lts:=Concatenation(plts,lts);	# XXX
773    	plts:=[];			# XXX
774    fi;					# XXX
775    cont := true;
776
777    if maxno = 0 then idf := true; else idf := false; fi;
778    if Length(lts) = 0 and maxno = 0 then return "error: empty input and no maximum"; fi;
779    if GBNP.OccurInLst([],lts)[1] > 0 then return []; fi;
780    if Length(lts)>0 then
781        ROT := GBNP.CreateOccurTreePTSLR(lts,mt,false);
782    fi;
783    #pLOT := GBNP.CreateOccurTreePTSLR(plts,mt,true); # XXX remove plts and this
784    ans := [];
785    lvl := 1;
786    if mt >0 then
787    	ans[1] := [];
788	for i in [-mt,-mt+1..-1] do
789                if Length(lts)=0 or GBNP.LookUpOccurTreePTSLRPos([i],ROT,false,1) = 0 then
790			Add(ans[1],[i]);
791		fi;
792	od;
793    else
794    	ans[1] := [[]];
795    fi;
796    ct := Length(ans[1]);
797
798    while cont and ((ct <= maxno) or idf) do
799         #Info(InfoGBNP,3,"sofar found ",ct," monomials");
800         lvl := lvl+ 1;
801         tt := [];
802         #Info(InfoGBNP,3,"busy with lvl ",lvl);
803         cont := false;
804         for h in ans[lvl-1] do
805            for i in [1..t] do
806                hi := StructuralCopy(h);
807                Append(hi,[i]);
808                if Length(lts)=0 or GBNP.LookUpOccurTreePTSLRPos(hi,ROT,false,1) = 0
809                	# XXX and GBNP.LookUpOccurTreePTSLRPos(hi,pLOT,true,1)= 0 #remove plts and this
810		then
811                   ct := ct+ 1;
812                   Append(tt,[hi]);
813                   cont := true;
814                fi;
815            od;
816         od;
817         ans[lvl] := tt;
818    od;
819    return(ans);
820end;
821
822##############################
823### GBNP.NondivMonsPTSenum ###
824##############################
825###
826### depth first version - only counts and therefor uses much less memory and it
827### should be faster
828###
829### Arguments:
830### plts	- list of leading terms for prefix rules
831### lts	 	- list of leading terms
832### t		- number of elements in the alphabet
833### mt		- number of elements in the module-alphabet
834### maxno	- maximum number of monomials to be found
835###
836### Returns:
837### ans		- List of nondiv. monomials
838###
839### #GBNP.NondivMonsPTSenum uses: GBNP.CreateOccurTreePTSLR GBNP.GetOptions GBNP.OccurInLst#
840### #GBNP.NondivMonsPTSenum is used in: DimQA DimQM GBNP.SGrobnerLoops#
841###
842
843GBNP.NondivMonsPTSenum := function(plts,lts,t,mt,max)
844local lvl,ROT, pol, todo, found_new, countfun, count;
845
846    #mt:=GBNP.GetOptions().pg; 		# XXX even not longer needed
847    if plts<>[] then			# XXX mt should not be changed here
848    	lts:=Concatenation(plts,lts);	# XXX
849    	plts:=[];			# XXX
850    fi;					# XXX
851
852    if Length(lts) = 0 then return "error: empty input"; fi;
853    if GBNP.OccurInLst([],lts)[1] > 0 then return 0; fi;
854    ROT := GBNP.CreateOccurTreePTSLR(lts,mt,false);
855    #pLOT := GBNP.CreateOccurTreePTSLR(plts,mt,true); # XXX remove plts and this
856    if mt >0 then
857    	todo := List([-mt,-mt+1..-1],x->[x]);
858        lvl := 2;
859    else
860    	todo := [[]];
861        lvl := 1;
862    fi;
863
864    countfun:=function(pol,lvl)
865    	local i, count;
866
867	if max>0 and lvl>max then return 1; fi;
868
869	count:=0;
870	for i in [1..t]  do
871	    pol[lvl]:=i;
872            if GBNP.LookUpOccurTreePTSLRPos(pol,ROT,false,1) = 0 then
873	        count:=count+countfun(pol,lvl+1)+1;
874		Unbind(pol[lvl+1]);
875	    fi;
876	    if max>0 and count>max then
877	    	return count;
878	    fi;
879	od;
880
881	return count;
882    end;
883
884    count:=0;
885    for pol in todo do
886        if GBNP.LookUpOccurTreePTSLRPos(pol,ROT,false,1) = 0 then
887    	    count:=count+countfun(pol,lvl)+1;
888	    if max>0 and count>max then
889	    	return max;
890	    fi;
891	    Unbind(pol[lvl+1]);
892	fi;
893    od;
894
895    return count;
896end;
897