######################### BEGIN COPYRIGHT MESSAGE #########################
# GBNP - computing Gröbner bases of noncommutative polynomials
# Copyright 2001-2010 by Arjeh M. Cohen, Dié A.H. Gijsbers, Jan Willem
# Knopper, Chris Krook. Address: Discrete Algebra and Geometry (DAM) group
# at the Department of Mathematics and Computer Science of Eindhoven
# University of Technology.
#
# For acknowledgements see the manual. The manual can be found in several
# formats in the doc subdirectory of the GBNP distribution. The
# acknowledgements formatted as text can be found in the file chap0.txt.
#
# GBNP is free software; you can redistribute it and/or modify it under
# the terms of the Lesser GNU General Public License as published by the
# Free Software Foundation (FSF); either version 2.1 of the License, or
# (at your option) any later version. For details, see the file 'LGPL' in
# the doc subdirectory of the GBNP distribution or see the FSF's own site:
#
https://www.gnu.org/licenses/lgpl.html
########################## END COPYRIGHT MESSAGE ##########################
### filename = "tree.gi"
### author: Chris Krook
### This is an add-on for the GBNP package, version 0.9
# This file contains auxiliary functions that are used by the file
# fincheck.g. All functions in this file are constructors or operators on
# a tree structure, that can be used to store a set of monomials,
# of which none divides another.
#
# Formally:
# Given an alphabet A and a set of monomials M, none of which divides
# another, the tree T is defined to be a list s.t.
# T[m_n +1][m_(n-1) +1]...[m_1 +1]<>0 iff m=m_1 m_2 ... m_n in M.
# T is unbound on all other positions.
# (the actual value in the tree is not used by the functions
# that these functions support, but is used in some other GBNP-functions.
# Therefore we are sloppy with the actual values and the corresponding
# arrays as present in the tree-structure. By doing this some functions
# are more efficient.)
# Example: M={xx,yyx,yyy} -> T=[,[,[1],[,,[1]]],[,,[,,[1]]]]
# Here T[1+1][2+1][2+1]=[1] and [2,2,1]~yyx is in M
# functions that are defined in this file:
# GBNP.IsFullTree :=function(Tree,alphabetsize)
# GBNP.RedAddToTree :=function(u,T,n);
# GBNP.RedAddListToTree :=function(ulist,Tree,alphabetsize)
# GBNP.SuffixOfTree :=function(u,l,Tree)
# GBNP.TreeToList :=function(Tree,[],[])
#######################
### GBNP.IsFullTree ###
#######################
### - Checks whether a given tree consists of precisely n leafs
### where n is alphabetsize.
###
### Arguments:
### Tree - a tree
### alphabetsize - the alphabetsize
###
### Returns:
### true: - Tree[1]..Tree[n] are leafs
### false: - Otherwise
###
### #GBNP.IsFullTree uses:#
### #GBNP.IsFullTree is used in: GBNP.RedAddToTree#
###
GBNP.IsFullTree:=function(Tree,alphabetsize) local i;
i:=1;
while i<=alphabetsize do
if not IsBound(Tree[i+1]) or (IsList(Tree[i+1]) and Length(Tree[i+1])>1) then
return(false);
else
i:=i+1;
fi;
od;
return(true);
end;
#########################
### GBNP.RedAddToTree ###
#########################
### - Adds an element u to the tree T, instantly reducing full
### subtrees to nodes.
###
### Arguments:
### u - monomial
### T - a tree of reversed relations.
### alphabetsize - the alphabetsize
###
### Returns:
### - nothing. called for its side effect.
### Alters Tree as to add u to it.
###
### Uses:
### - GBNP.RedAddToTree (tree.g)
### - GBNP.CreateOccurTreeLR
### - GBNP.IsFullTree (tree.g)
###
### #GBNP.RedAddToTree uses: GBNP.CreateOccurTreeLR GBNP.IsFullTree GBNP.RedAddToTree
#
### #GBNP.RedAddToTree is used in: GBNP.IncrT GBNP.RedAddListToTree GBNP.RedAddToTree PreprocessAnalysisQA#
###
GBNP.RedAddToTree:=function(u,T,n) local i;
i:=Length(u);
if i>1 and IsBound(T[u[i]+1]) then
if IsList(T[u[i]+1]) and Length(T[u[i]+1])>1 then
GBNP.RedAddToTree(u{[1..Length(u)-1]},T[u[i]+1],n);
else
return;
fi;
elif i=1 then
T[u[i]+1]:=[1];
else
T[u[i]+1]:=GBNP.CreateOccurTreeLR([u{[1..Length(u)-1]}],false).tree;
fi;
if i>0 and GBNP.IsFullTree(T[u[i]+1],n) then
T[u[i]+1]:=[1];
fi;
end;;
### #GBNP.RedAddListToTree uses: GBNP.RedAddToTree#
### #GBNP.RedAddListToTree is used in:#
###
GBNP.RedAddListToTree:=function(ulist,Tree,alphabetsize) local u;
for u in ulist do
GBNP.RedAddToTree(u,Tree,alphabetsize);
od;
end;;
#########################
### GBNP.SuffixOfTree ###
#########################
### - Checks whether some u is a strict suffix of some relation in
### the tree.
###
### Arguments:
### u - monomial (not reversed, just the
### original monomial)
### l - pointer s.t. u[1..l] is the monomial
### Tree - a tree of reversed relations.
###
### Returns:
### true - u is strict suffix of some relation
### false - otherwise
###
### #GBNP.SuffixOfTree uses:#
### #GBNP.SuffixOfTree is used in: GraphOfNormalWords#
###
GBNP.SuffixOfTree:=function(u,l,Tree) local T;
if Tree=[] then return(false); fi;
T:=ShallowCopy(Tree);
while l>0 do
if IsBound(T[u[l]+1]) and IsList(T[u[l]+1]) then
T:=T[u[l]+1];
l:=l-1;
else
return(false);
fi;
od;
if IsList(T) and Length(T)>1 then return(true);
else return(false);
fi;
end;;
#######################
### GBNP.TreeToList ###
#######################
### - Gives the relations from the tree
###
###
### Arguments:
### Tree - a tree of reversed relations.
### Rels, Temp - should both be [];
###
### Returns:
### a list of the relations
###
### #GBNP.TreeToList uses: GBNP.TreeToList#
### #GBNP.TreeToList is used in: GBNP.TreeToList PreprocessAnalysisQA#
###
GBNP.TreeToList:=function(Tree,Rels,Temp) local i;
for i in [2..Length(Tree)] do
if IsBound(Tree[i]) then
if Length(Tree[i])>1 then
GBNP.TreeToList(Tree[i],Rels,Concatenation([i-1],Temp));
else
Add(Rels, Concatenation([i-1],Temp));
fi;
fi;
od;
return(Rels);
end;;
