// C++ Program for handling Nichols algebras via computing bilinear forms, 
// written by Eric Mueller 1998-1999, last change 16 June 1999. 
// (e-mail: emueller@rz.mathematik.uni-muenchen.de)
// No kind of warranty is given for correctness and that the program serves 
// any purpose. Please feel free to report any kinds of errors to the author.
// Usage and distribution of this program is free provided that either the 
// file is not changed or all changes are marked with the name and address
// of the person who has done the changes and the changes are reported
// below these lines.
// In UNIX systems type the following to compile the program (assuming that the
// program name should be 'nichols' and this source file is called 'nichols.cpp'):
// CC -fast -o nichols nichols.cpp
// or
// g++ -O -o nichols nichols.cpp
#include <fstream.h>
#include <iostream.h>
#include <stdlib.h>
const int maxT=20; // maximal number of algebra generators of B(V)
const int maxM=50; // Maximal length of monomials
const int maxN=20; // maximal value of the order of the root of unity q
typedef struct { int exponent; int permut[maxT];} grupp;
typedef int* Zeiger;
typedef enum {FALSE, TRUE} Boolean;
typedef enum {Normal, Ausgabedoppelt, NurDateien} Dateistatus;
typedef enum {FLUSH, ENDL} Manipulator;
struct Manip {Manipulator eintrag;}; // Manipulatoren
const Manip Flush ={FLUSH};
const Manip Endl = {ENDL};

// globale Variablen

ifstream Eingabedatei;
ofstream Ausgabedatei;
unsigned long int AbbruchZahl=1000, LimitZahl=0; // maximale Anzahl an BLF-Summanden pro BLF-Berechnung
unsigned long int Zaehler, ZweitZaehler;   // Zaehlt, wie viele BLF-Summanden vorkommen
Boolean Einfachausgabe=FALSE; // FALSE: Format fuer BLF-Wert 2+4q^3, TRUE: 2 0 0 4
Boolean Schrittanzahl=TRUE; // Angabe, wie viele Summanden fuer BLF-Wert vorkamen
Boolean Quadratfrei=FALSE; // gibt an, ob Quadrate der Erzeuger immer verschwinden 
Boolean Fehlversuchsangabe=TRUE; // gibt an, ob Angaben zur Laenge und zu Fehlversuchen ausgegeben werden sollen
Boolean GruppengradNull=FALSE; // gibt an, ob ausgegeben werden soll, dass Monom Gesamtgrad Null hat, d.h. auf jees Element trivial operiert
int N,T;  // Ordnung der Einheitswurzel, Anzahl der B(V)-Erzeuger
Boolean Charakter=TRUE; // TRUE=Charakter oder FALSE=Bicharakter
int zei[256];  // Zeichenumsetzungstabelle fuer B(V)-Erzeuger
char erzeuger[maxT]; // Erzeuger von B(V)
short int expo[maxT][maxT]; // Charakterwerte (Exponenten der Einheitswurzel)
short int* expoeinfach = &expo[0][0]; // Hilfstabelle fuer einfachen Charakter
short int a[maxT][maxT];  // a[j][i]: Element j wirkt auf Element i durch Konjugation
short int erstes[maxM]; // erstes Monom
short int* ErstMonom;  // Zeiger auf erstes Monom fuer 'ausrechnen'
short int zweites[maxM]; // zweites Monom
short int* ZweitMonom;  // zeiger auf zweites Monom fuer 'ausrechnen'
short int naechst[maxT][maxM+2]; // naechst[i][j] (bzw. vor[i][j]) gibt an, an welcher ersten Stelle                                 
short int vor[maxT][maxM+2];     // hinter (vor) Stelle j das Zeichen i im ersten Monom vorkommt.
short int naechstes[maxM+1]; // naechstes Vorkommen des Zeichens an Stelle i nach Stelle i im ersten Monom
short int M; // Monomlaenge
long int ergebnis[maxN]; // Ergebnisvektor
short int permutation[maxM]; // Hilfsfeld mit Daten ueber passende Permutation
Boolean TrivialWirkung=FALSE; // gibt an, ob Operation der Erzeuger trivial ist.
short int monomgrad[maxT]; // Grad des ersten Monoms (Angabe, wie oft jeder Erzeuger vorkommt, nur bei trivialer Wirkung

class EinAus
{
private: Dateistatus status;
public: EinAus(Dateistatus estatus) {status=estatus;}
public: EinAus() {status=Normal;}
public: int Nurdateien() {return (status==NurDateien ? 1 : 0);}
public: void Aendern(Dateistatus estatus) 
  {status=estatus;}
  friend EinAus& operator << (EinAus& dies, char ch);
  friend EinAus& operator << (EinAus& dies, char* s);
  friend EinAus& operator << (EinAus& dies, int i);
  friend EinAus& operator << (EinAus& dies, long int i);
  friend EinAus& operator << (EinAus& dies, unsigned long int i);
  friend EinAus& operator << (EinAus& dies, short int i);
  friend EinAus& operator << (EinAus& dies, Manip manip);
  friend EinAus& operator << (EinAus& dies, short int* monom);
  friend EinAus& operator >> (EinAus& dies, char& ch);
  friend EinAus& operator >> (EinAus& dies, char* s);
  friend EinAus& operator >> (EinAus& dies, int& i);
  friend EinAus& operator >> (EinAus& dies, unsigned long int& i);
};
EinAus InOut;

EinAus& operator << (EinAus& dies, Manip manip)
{
  if (dies.status!=Normal) 
    if (manip.eintrag==FLUSH) Ausgabedatei << flush; 
    else
      Ausgabedatei << endl;
    
  if (dies.status!=NurDateien) 
    if (manip.eintrag==FLUSH) cout << flush; 
    else
      cout << endl;
  return dies;
}

EinAus& operator << (EinAus& dies, short int* monom)
{
 // Laenge M vorausgesetzt!
  int i;
  for (i=0; i<M; i++) InOut << erzeuger[monom[i]];
  return dies;
}



EinAus& operator << (EinAus& dies, char ch)
{
  if (dies.status!=Normal) Ausgabedatei << ch;
  if (dies.status!=NurDateien) cout << ch;
  return dies;
}

EinAus& operator << (EinAus& dies, char* s)
{
  if (dies.status!=Normal) Ausgabedatei << s;
  if (dies.status!=NurDateien) cout << s;
  return dies;
}
 
EinAus& operator << (EinAus& dies, int i)
{
  if (dies.status!=Normal) Ausgabedatei << i;
  if (dies.status!=NurDateien) cout << i;
  return dies;
}

EinAus& operator << (EinAus& dies, long int i)
{
  if (dies.status!=Normal) Ausgabedatei << i;
  if (dies.status!=NurDateien) cout << i;
  return dies;
}
EinAus& operator << (EinAus& dies, unsigned long int i)
{
  if (dies.status!=Normal) Ausgabedatei << i;
  if (dies.status!=NurDateien) cout << i;
  return dies;
}

EinAus& operator << (EinAus& dies, short int i)
{
  if (dies.status!=Normal) Ausgabedatei << i;
  if (dies.status!=NurDateien) cout << i;
  return dies;
}

EinAus& operator >> (EinAus& dies, char& ch)
{
  char hilf;
  if (dies.status==NurDateien) { Eingabedatei >> ch; Eingabedatei.get(hilf);}
  else { cin >> ch; cin.get(hilf);}
  if (dies.status!=Normal) Ausgabedatei << ch << endl;
  return dies;
}
EinAus& operator >> (EinAus& dies, char* s)
{
  if (dies.status==NurDateien) Eingabedatei >> s;
  else cin >> s;
  if (dies.status!=Normal) Ausgabedatei << s << endl;
  return dies;
}

int Zahllesen(istream& datei, int Zeilennummer);


EinAus& operator >> (EinAus& dies, int& i)
{
  if (dies.status==NurDateien) i=Zahllesen(Eingabedatei,0);
  else i=Zahllesen(cin,0);
  if (dies.status!=Normal) Ausgabedatei << i << endl;
  return dies;
}
EinAus& operator >> (EinAus& dies, unsigned long int& i)
{
  if (dies.status==NurDateien) i=Zahllesen(Eingabedatei,0);
  else i=Zahllesen(cin,0);
  if (dies.status!=Normal) Ausgabedatei << i << endl;
  return dies;
}




int Fehlerbehandlung (int Fehlernummer, int Nummer, char Zeichen, int abbruch)
{
int i,j;
i=1; j=0;
cerr << "Error: ";
if (Zeichen && Zeichen !='\n') cerr << "Character \"" << Zeichen << "\" ";
if (Nummer) cerr << "in line " << Nummer << ' '; 
switch (Fehlernummer)
  {
  case 1:  cerr << "First Parameter: name of input file!"; break;
  case 2:  cerr << "Input file cannot be opened"; break;
  case 3:  cerr << "no digit!"; break;
  case 4: cerr  << "occurs twice or: a blank is not allowed!" ; break;
  case 5: cerr << "too many characters"; break;
  case 6: if (Zeichen=='\n') cerr << "must contain all generators of B(V)"; 
          else cerr << "has to be generator of B(V)"; break;
  case 7: cerr << "- line too short"; break;
  case 8: cerr << "- line too long"; break;  
  case 9: cerr << "has to be generator of the group!"; break;
  case 11: cerr << "number expected; value of number is set to 0"; break;
  case 12: cerr << "number too big or too low (minimal value 2, maximal value "
		<< maxN << ')'; break;
  case 13: cerr << "value 1 (for character) or 2 (bicharacter) nothing else"; break;
  case 14: cerr << "monomial too long"; break;
  case 16:  cerr << "Output file cannot be opened"; break;
  case 17: cerr << "wrong (only y/n)"; break;
  case 18: cerr << "wrong (only A/B/C)"; break;
  default: cerr << "Other kind of error."; break;
}
cerr << '\n';
if (abbruch) exit(Fehlernummer);
return 0;

}

void Permutationsausgabe(short int* hilfsfeld)
// erzeugt Permutationsangabe aus Ergebnissen der Durchlaeufe von 'ausrechnen' 
{
  int i,j;
  for (i=2; i<=M; i++)
    for (j=1; j<i; j++)
      if (hilfsfeld[i]<=hilfsfeld[j]) hilfsfeld[j]++;
  InOut << " (" << hilfsfeld[1];
  for (i=2; i<=M; i++) InOut << ' ' << hilfsfeld[i];
  InOut << ')' << Endl;
}
    


int Zahllesen(istream& datei, int Zeilennummer)
{ 
  int i=0, j=0;
  char ch;
  ch='0';
  while (datei.get(ch) && ch!='\n')
    { 
      j=1;
      if (ch>='0' && ch<='9') {i*= 10; i+= (ch-'0');}
      else { Fehlerbehandlung(3, Zeilennummer, ch, 1);}
    };
  if (ch=='\n' && j == 0) 
    {
      Fehlerbehandlung(11, Zeilennummer, '\0', 0); i=0;
    }
  return i;  
}


void Konvertieren() 
  // konvertiert Ergebnisvektor, damit hoechste Stelle 0 ist.
{
  int i;
  long int hilf;
  // Konvertieren des Ergebnisses
  if ((hilf=ergebnis[N-1])!=0)
  { ergebnis[N-1]=0; for (i=0; i<N-1; i++) ergebnis[i]-=hilf; }
}

int BLFungleichNull() // gibt an, ob Wert der Bilinearform 0 ist,
{
int i;
Konvertieren();
for(i=0;i<N-1; i++)
  if (ergebnis[i]) return 1;
return 0;
}


void Wertausgabe()
{
  int i;
  Boolean ausgabe=FALSE; // ist schon etwas ausgegeben worden?
  if (Schrittanzahl==TRUE)
  {InOut << (char) '(';
  InOut << (unsigned long int) (Zaehler+ZweitZaehler*AbbruchZahl); 
  InOut << "): ";}
  else InOut << ' ';
  Konvertieren();
  if (Einfachausgabe==TRUE)
    for (i=0; i< N-1; i++) InOut << ergebnis[i] << ' ';
  else
    {
      for (i=0; i< N-1; i++)
	{ 
	  if (ausgabe && ergebnis[i]>0) InOut << '+';
	  if (ergebnis[i]!=0 && (i==0 || ergebnis[i]!=1))
	    {
	      if (i>0 && ergebnis[i]==-1) InOut << (char) '-';
	      else
		InOut << (int) ergebnis[i];
	      ausgabe=TRUE;
	    }
	  if (i>0 && ergebnis[i]!=0) 
	    { 
	      InOut << 'q';
	      if (i>1) InOut << '^' << i;
	      ausgabe=TRUE;
	    }
	}
      if (!ausgabe) InOut << '0';
    }
  InOut << Endl;
}

Boolean EinzelMonomEingabe(short int* ausgabe, short int& i, Boolean punkt)
{  // i: Laenge des Monoms; Ausgabewert: ob Eingabe mit Punkt beginnt.
 int nummer;
 Boolean punkt_kommt_vor=FALSE;
 char s[maxM+2];
 char* zeiger=s;
    InOut >> s;
    i=0;
    if (punkt==TRUE && s[0]=='.') {punkt_kommt_vor=TRUE; zeiger++; }
    while(i<maxM && (nummer=zeiger[i]))
      {
	if ((nummer=zei[nummer])==-1) Fehlerbehandlung(6,0,zeiger[i],1);
	else
	  ausgabe[i]=nummer;
	i++;
      }
    if (i==maxM && zeiger[maxM]) Fehlerbehandlung(5,0,'\0',1); // Monom zu lang
    return punkt_kommt_vor;
}


Boolean MonomGrad(short int* Monom)
  // gibt an, ob Monomgrad (d. h. Produkt der Permutationen des Monoms)
  // invariant unter jedem der Erzeuger ist.
{
  int i,j;
  short int Hilfsmonom[maxM];
  short int Monompermutation[maxT];
  short int k, opfer;
  short int * hilfa;
  // Feststellen der Monompermutation
  for (k=1; k<T; k++)
    {
      opfer = k;
      for (i=0; i<M; i++)
	opfer=a[Monom[i]][opfer];
      Monompermutation[k]=opfer;
    }
  // Monompermutation des veraenderten Monoms
  for (j=0; j<T; j++)
    {
      hilfa=a[j];
      // Neues Monom erstellen
      for (i=0; i<M; i++) 
	Hilfsmonom[i]=hilfa[Monom[i]];
      for (k=1; k<T; k++)
	{
	  opfer = k;
	  for (i=0; i<M; i++)
	    opfer=a[Hilfsmonom[i]][opfer];
	  if (opfer!=Monompermutation[k]) return FALSE;
	}
    }
  return TRUE;
}

Boolean Trivialwirkung()
// gibt an, ob Wirkung insgesamt trivial ist, also j=a[i][j] fuer alle i,j
{
  int i,j;
  for (i=0; i<T; i++)
    for (j=1; j<T; j++)
      if (j!=a[i][j]) return FALSE;
  return TRUE;
}


Boolean Zwischenausgabe(Boolean b, int Zweitzaehler)
{
  if (Fehlversuchsangabe==TRUE)
    { 
      InOut << '.' << Flush; 
      if ((Zweitzaehler > 0) && (Zweitzaehler % 80) == 0)  // nicht zu viele Punkte pro Zeile
	{
          InOut << Endl;
	}  
      if (b) 
	{
	  InOut << ZweitMonom << '!' << Endl; 
	}
    }
  return b;
}


int Quadratfinden(short int* Monom)
  // gibt kleinsten Index aus, an dem in Monom zwei gleiche Faktoren vorkommen
  // (bzw. Monomlaenge M, wenn es keinen solchen gibt): fuer Monom abc ist
  // Wert 3, fuer Monom aab ist Wert 1, fuer Monom baa ist Wert 2.
{
  int i;
  for (i=1; i<M; i++)
    if (Monom[i]==Monom[i-1]) return i;
  return M;
}

int Passend(short int* ErstesMonom, short int *Monom)
  // nur fuer triviale Operation: gibt an, bis zu welcher Stelle zweites
  // Monom gleichen Grad wie erstes haben kann. Bsp: Monome aaa, bbb: 0,
  // aba, bab: 2, aab, bab: 2.
{
  short int Grad[maxT];
  int i;
  for (i=0; i<T; i++) Grad[i]=0;
  for (i=0; i<M; i++) Grad[ErstesMonom[i]]++;
  for (i=0; i<M; i++) 
    if (Grad[Monom[i]]==0) return i;
    else Grad[Monom[i]]--;
  return M;
} 
						 


Boolean NaechsterWert(int stufe, Boolean Quadratausschluss, 
		      Boolean Laengenanpassung, short int* ErstesMonom, 
		      short int* Monom)
  // berechnet lexikographisch naechstes Monom nach Eingegebenem;
  // wobei zumindest an Stelle "stufe" erhoeht wird (erster Faktor
  // des Monoms hat Stelle 0); 
  // Falls Quadratausschluss==TRUE, werden Monome uebersprungen,
  // die zwei gleiche Eintraege an aufeinanderfolgenden Stellen haben;
  // ist Laengenanpassung==TRUE, so wird Monomlaenge immer auf letzte
  // veraenderte Stelle abgekuerzt (ansonsten werden restliche Stellen
  // auf niedrigstmoeglichen Wert gesetzt)
  // Funktionswert: TRUE, wenn Erhoehung erfolgreich, sonst FALSE.
  // ist "stufe" anfangs groesser als M, wird nur dann geaendert, wenn
  // Monom mit "unguenstigen" Eigenschaften vorliegt.
{
  int i;
  if (stufe==M) stufe=M-1;
  while (stufe!=M)
    {
      if (stufe<M)
	{
	  if (Monom[stufe]==T-1)
	    {
	      if (stufe==0) // zu Ende: nichts kann mehr erhoeht werden
		{
		  if (Laengenanpassung) InOut << "End" << Flush;
		  return FALSE;
		}
	      else stufe--; // Aendern an vorangehender Stufe
	    }
	  else
	    { 
	      Monom[stufe]++; 
	      // Behandeln der weiteren Stellen: entweder auf 0 setzen oder
	      // Monomlaenge verkuerzen.
	      if (Laengenanpassung==FALSE) 
		{
		  for (i=stufe+1; i<M; i++) Monom[i]=0;
		}
	      else M=stufe+1;
	      stufe=M; // Abbrechen der Schleife
	    }
	}
      // Weitere Monome mit "unguenstigen" Eigenschaften ueberspringen
      if (Quadratausschluss==TRUE && stufe>=M)
	stufe=Quadratfinden(Monom);
      if (TrivialWirkung==TRUE && stufe>=M)
	stufe=Passend(ErstesMonom,Monom);
      // Abfangen von zu grossem Wert, um Endlosschleife zu vermeiden
      if (stufe>M) stufe=M;
    }
  return TRUE;
}




void Tabellenausgabe()
{
int i,j;
  InOut << "Left generator of B(V) acts on the upper as ...; on the right: values of chi\n  ";
  for (i=0; i<T; i++) 
    {
      InOut << erzeuger[i];
    }
  if (Charakter==FALSE) 
    {
      InOut << "  ";
      for (j=0; j<T; j++) 
	InOut << "  " << erzeuger[j];
    }
  InOut << '\n';
  for (j=0; j<T; j++) 
    {
      InOut << erzeuger[j] << ' ';
      for (i=0; i<T; i++) 
	InOut << erzeuger[a[j][i]];
      InOut << "  ";
      if (Charakter) 
	InOut << expoeinfach[j];
      else
	for (i=0; i<T; i++) 
	  {
	    if (expo[j][i]<100) 
	      {
		InOut << ' ';
		if (expo[j][i]<10) InOut << ' ';
	      }
	    InOut << expo[j][i];
	   } 
      InOut << Endl;
    }
}
	  



int Gruppen(istream& datei)
{ 
  int i,j,k,nummer,zeilennummer;
  char ch;
  int hilfe[maxT];
  grupp* gru[256];
  grupp* hilfg;
  short int* zwischen;
  zeilennummer=3;
  // Feld a initialisieren, Feld expo initialisieren
  for (i=0; i<T; i++)
    { 
      for (j=0; j<T; j++) 
	{
	  a[i][j]=j; expo[i][j]=0;
	}
    }
  // Feld gru initialisieren
  for (i=0; i<256; i++) gru[i]=0;
  // Neue Zeile lesen:
    while (datei.get(ch) )
    { 
      if (ch=='\n') ; // Leerzeile
      else   
	{ 
	  zeilennummer++;
	  if (zei[ch]==-1)
	    { // neuer Gruppenerzeuger
	      if (gru[ch] == 0) 
		{
		  hilfg=new(grupp);
		  gru[ch]=hilfg;
		  for (i=0; i<T; i++) hilfg->permut[i]=i; hilfg->exponent=0;
		}
	      else
		{
		  hilfg=gru[ch];
		}
	      for (j=0; j<T; j++)
		{ 
		  if (!datei.get(ch)) Fehlerbehandlung(7, zeilennummer,'\0',1);
		  else
		    { 
		      if (j==0 && ch==' ' && Charakter) 
			{
			  hilfg->exponent=Zahllesen(datei,zeilennummer);
			  j=T; // Schleifenende!
			}
		      else
			if ((nummer=zei[ch])==-1) Fehlerbehandlung(6,zeilennummer,ch,1);
			else
			  { // doppeltes Zeichen:
			    for (k=0; k<j; k++) 
			      if (hilfg->permut[k] == nummer)
				Fehlerbehandlung(4,zeilennummer,ch,1);
			    // alles richtig:
			    hilfg->permut[j]=nummer;
			  }
		    }	    
		}
	    }
	  else
	    { // B(V)-Erzeuger wird zusammengesetzt oder Bicharakterwerte
	      nummer = zei[ch];
	      if (datei.get(ch) && ch != '\n')
	      { 
		if (Charakter==FALSE && zei[ch]>-1) 
		  expo[nummer][zei[ch]]=Zahllesen(datei,zeilennummer++);
		else
		  {
		    while(ch !='\n')
		      { 
			if (gru[ch]== 0) 
			  Fehlerbehandlung(9, zeilennummer, ch,1);
			else 
			  { 
			    zwischen=a[nummer];
			    for (j=0; j<T; j++) hilfe[j]=zwischen[j];
			    for (j=0; j<T; j++) zwischen[j]=gru[ch]->permut[hilfe[j]];
			    if (Charakter)
			      {
				expoeinfach[nummer]+= gru[ch]->exponent;
				expoeinfach[nummer]%= N;
			      }
			  }
                        if (!datei.get(ch)) ch='\n'; // Schleife beenden, falls nichts mehr
		      }
		  }
	      }      
	    }
	}
    }
    for (i=0; i<256; i++) if (gru[i]) delete(gru[i]);
    Tabellenausgabe();
    TrivialWirkung=Trivialwirkung();
    return 0;
}


     




Boolean ausrechnen(const int stufe, short int* alte_erste, int exponent, int stelle,
int stelle_in_erstes)
  // benoetigt Vorbereitung in BLFberechnung
  // Achtung: aus historischen Gruenden bei ErstMonom Indizierung von 1 bis M,
  // bei ZweitMonom wie ueblich von 0 bis M-1.
  // Ergebniswert: TRUE, wenn nicht abgebrochen wegen zu hoher Schrittzahl
  {
    const int stufeminuseins=stufe-1;
    const int stufepluseins=stufe+1;
    short int neue_erste[maxM];
    register short int j,k, RechteGrenze=M+1, 
      NeuesElement=ZweitMonom[stufe], hilf, hilf1, hilf2;
    //    register short int i=0;
    permutation[stufe]=stelle;
    { register short int i=0, hilf, hilf3;
    register short int * p=neue_erste;
    // Kopieren des ersten Teils von  alte_erste  auf  neue_erste
    while(i<stelle) { *p++=alte_erste[i]; i++; }
    // An Stelle  stelle  ist jetzt neu hinzugekommenes Element von oben
    hilf=*p++=stelle_in_erstes; 
    // evtl. verschieben sich jetzt ein paar Positionen
    while (i<stufeminuseins)
      {
	if (hilf<(hilf3=alte_erste[i])) { *p++=hilf3; i++; break; }
	else
	  hilf3=naechstes[hilf3];
	while (hilf3<=hilf)
	  hilf3=naechstes[hilf3];
	hilf=*p++=hilf3; i++;
      }
    // ab jetzt kann man  alte_erste  wieder in  neue_erste  kopieren
    while (i<stufeminuseins)
      {
	*p++=alte_erste[i]; i++; 
      }
    }
    if (stufepluseins<M) // Schleife mit rekursivem Funktionsaufruf
      {
	for (j=stufe; j>0; j--)
	  { 
	    if (j+1>=RechteGrenze) return TRUE; // in diesem Schleifendurchlauf
	    // kann kein Treffer mehr gefunden werden, da RechteGrenze
	    // zu niedrig und RechteGrenze-j monoton faellt.
	    if ((hilf=naechst[NeuesElement][(hilf1=neue_erste[j-1])])<RechteGrenze)
	      {	
		if (!ausrechnen(stufepluseins, neue_erste, exponent, j, hilf))
		  return FALSE;
	      }
	    if (Charakter==TRUE) 
	      exponent += expoeinfach[(hilf2=ErstMonom[hilf1])];
	    else 
	      exponent += expo[(hilf2=ErstMonom[hilf1])][NeuesElement];
	    NeuesElement=a[hilf2][NeuesElement];
	    RechteGrenze = vor[hilf2][RechteGrenze];
	  }
	// Fall j=0:
	if ((hilf= *naechst[NeuesElement])<RechteGrenze)
	  { 
	    return ausrechnen(stufepluseins, neue_erste, exponent,0,hilf);
	  }
      } 
    else // neue Bilinearformwerte
      {
	for (j=stufe; j>0; j--)
	  {
	    if (j+1>=RechteGrenze) return TRUE; // in diesem Schleifendurchlauf
	      // kann kein Treffer mehr gefunden werden, da RechteGrenze
	      // zu niedrig und RechteGrenze-j monoton faellt
	    if (naechst[NeuesElement][(hilf1=neue_erste[j-1])]<RechteGrenze)
	      { // Neuer Bilinearformwert
		exponent %= N;
		ergebnis[exponent]++;
		Zaehler++; if (Zaehler >= AbbruchZahl) 
		  { 
		    if (AbbruchZahl==1)
		      { // Ausgabe der Permutation
			InOut << exponent; 
			short int hilfsfeld[maxM+1];
			for (k=1; k<M; k++) hilfsfeld[k]=permutation[k]+1;
			hilfsfeld[M]=j+1;
			Permutationsausgabe(hilfsfeld);
		      }
		    Zaehler=0; ZweitZaehler++;
		    if (Zwischenausgabe((Boolean) (ZweitZaehler==LimitZahl),ZweitZaehler))
		       return FALSE;
		  }
	      }
	    if (Charakter==TRUE) 
	      exponent += expoeinfach[(hilf2=ErstMonom[hilf1])];
	    else 
	      exponent += expo[(hilf2=ErstMonom[hilf1])][NeuesElement];
	    NeuesElement=a[hilf2][NeuesElement];
	    RechteGrenze = vor[hilf2][RechteGrenze];
	  }
	// Fall j=0:
	if ( *naechst[NeuesElement] <RechteGrenze)
	  { // Neuer Bilinearformwert
	    exponent %= N;
	    ergebnis[exponent]++;
	    Zaehler++; if (Zaehler >=AbbruchZahl) 
	      {
		if (AbbruchZahl==1)
		  { // Ausgabe der Permutation
		    InOut << exponent; 
		    short int hilfsfeld[maxM+1];
		    for (k=1; k<M; k++) hilfsfeld[k]=permutation[k]+1;
		    hilfsfeld[M]=1;
		    Permutationsausgabe(hilfsfeld);
		  }
		Zaehler=0; ZweitZaehler++;
		if (Zwischenausgabe((Boolean) (ZweitZaehler==LimitZahl), ZweitZaehler))
		  return FALSE;		
	      }
	  }
      }
    return TRUE;
  }


  

Boolean BLFberechnung(Boolean vorbereitung, short int* Erstes, short int* Zweites)
  // BLF-Berechnung von Monomen in interner Darstellung. Falls vorbereitung,
  // werden Positionstabellen fuer erstes Monom gebildet. Voraussetzung:
  // Beide Monome haben Laenge M.
  {
    int i,j,nummer, hilf;
    // Initialisierungen
    if (vorbereitung)
      {
	for (i=0; i<maxT; i++)
	  for (j=0; j<M+2; j++) 
	    { 
	      naechst[i][j]=maxM+1; vor[i][j]=0;
	    }
	for (i=1; i<=M; i++)
	  {
	    nummer=Erstes[i-1];
	    for (j=i-1; j>=0 && naechst[nummer][j]>maxM; j--)
	      naechst[nummer][j]=i; 
	    for (j=i+1; j<=maxM+1 && vor[nummer][j]<i; j++)
	      vor[nummer][j]=i;
	  }
	for (i=1; i<=M; i++)
	  naechstes[i]=naechst[Erstes[i-1]][i];
	ErstMonom=Erstes-1; // Funktion 'ausrechnen' benoetigt erstes Monom mit um 1 verschobenem Index.
      }

    ZweitZaehler=Zaehler=0;
    for (i=0; i< N; i++) ergebnis[i]=0;
    for (i=1; i<=M; i++) permutation[i]=M+1; // wird von 'ausrechnen' 
                 // belegt, gibt danach Aufschluss, wie gut Monome zusammenpassen.
    if ((hilf=naechst[Zweites[0]][0])>M) return TRUE;  // Bilinearform muss 0 sein, da letzte
    // Stelle des 2. Monoms nicht im ersten vorkommt.       
    if (M==1)
      {
	ergebnis[0]=(Zweites[0]==Erstes[0]); return TRUE;
      }
    // Monomlaenge mindestens 2: Normales Ausrechnen
    ZweitMonom=Zweites; // Funktion 'ausrechnen' benoetigt globale Variable 'ZweitMonom'
    return ausrechnen(1,NULL,0,0,hilf);
  }

void Monomeingabe()
  {
    char ch, SpecialMode;
    short int i;
    int maxstufe; 
    int j,k, nummer;
    short int hilfslaenge; // Hilfsvariable: Laenge des 2. Monoms
    short int hilfszweit[maxM]; // 2. Monom
    Boolean Schleifenbeginn=TRUE, Schleifenfortfuehrung=FALSE;
    InOut << "Input of monomials, maximal length " << maxM << '\n';
    while (Schleifenbeginn || Schleifenfortfuehrung)
      {
	InOut << "First monomial: ";
	Schleifenbeginn=EinzelMonomEingabe(erstes, M, TRUE);
	if (Schleifenfortfuehrung==TRUE && M==1) return;
	if (Schleifenbeginn) InOut << "The following input is considered repeatedly until first monomial has length 1.\n";
	if (Schleifenbeginn) Schleifenfortfuehrung=TRUE;
	if (Schleifenbeginn || !Schleifenfortfuehrung)
	  {
	    InOut << "Second monomial (if of length 1: special modes): ";
	    EinzelMonomEingabe(&zweites[0], hilfslaenge, FALSE);
	  }
	if (M>1 && hilfslaenge==1)
	  { // Sonderfunktionen:
	    if (Schleifenbeginn || !Schleifenfortfuehrung)
	      {
		InOut << "Special modes (A: comparison with all monomials\n";
		InOut << "B: like A, but with limit\n";
		InOut << "C: automatic search for big non-zero monomial): ";
		InOut >> SpecialMode; 
		if (SpecialMode>='a' && SpecialMode<='c') SpecialMode= 'A'+(SpecialMode-'a'); // Umwandlung in Grossbuchstaben
		if (SpecialMode<'A' || SpecialMode>'C') Fehlerbehandlung(18,0,SpecialMode,1);
	      }
	    if (SpecialMode=='B' || SpecialMode=='C')
	      {
		if (Schleifenbeginn || !Schleifenfortfuehrung)
		  {
		    InOut << "Limit of summands: "; 
		    InOut >> j;
		    if (j>1 && j<=AbbruchZahl) 
		      { AbbruchZahl=j;
		  LimitZahl=1; }
		    if (j>AbbruchZahl)
		      { 
			LimitZahl=j/AbbruchZahl;
			if (LimitZahl*AbbruchZahl < j) 
			  InOut << "changed to " << LimitZahl*AbbruchZahl << '\n';
		      }
		  }
	      }
	    if (SpecialMode=='A' || SpecialMode=='B')
	      { 
		if (Schleifenbeginn || !Schleifenfortfuehrung)
		  {
		    InOut << "Start value for the second monomial: ";
		    EinzelMonomEingabe(hilfszweit, i, FALSE);
		    if (i<M)
		      for (j=i; j<M; j++) hilfszweit[j]=0;
		    InOut << "The program starts with " << hilfszweit << Endl;
		  }
		// Kopieren hilfszweit -> zweites; mit letzterem wird weiter gerechnet
		for (i=0; i< M; i++) zweites[i]=hilfszweit[i];
		if (NaechsterWert(M+1, Quadratfrei, FALSE, erstes, &zweites[0]) &&
BLFberechnung(TRUE, erstes, &zweites[0]) && BLFungleichNull())
		  {
		    InOut << zweites;
		    Wertausgabe(); 
		  }
 		
		// Berechnen, wie weit 'ausrechnen' gekommen ist.
		maxstufe=0; 
		while(maxstufe<M-1 && permutation[maxstufe+1]<=M) maxstufe++;
		while (NaechsterWert(maxstufe, Quadratfrei, FALSE,
				     erstes, &zweites[0]))
		  {
		    if (BLFberechnung(FALSE, erstes, &zweites[0]) && BLFungleichNull())
		      {
			InOut << zweites;
			Wertausgabe(); 
		      }
		    // Berechnen, wie weit 'ausrechnen' gekommen ist.
		    maxstufe=0; 
		    while(maxstufe<M-1 && permutation[maxstufe+1]<=M) maxstufe++;		    
		  }
	      }
	    if (SpecialMode=='C')
	      { // Durchprobieren der Laengen
		Boolean Monomlaengenangabe=TRUE;
		if (Schleifenbeginn || !Schleifenfortfuehrung)
		  {
		    InOut << "Indicate the lengths of the monomials (y/n)? ";
		    InOut >> ch;
		    if (ch!='y' && ch!='Y' && ch!= 'n' && ch!='N') Fehlerbehandlung(17,0,ch,1);
		    if (ch=='n' || ch=='N') Monomlaengenangabe=FALSE;		 
		    if (!TrivialWirkung) 
		      { 
			InOut << "Indicate whether total degree is invariant (y/n)? ";
			InOut >> ch; 
			if (ch!='y' && ch!='Y' && ch!= 'n' && ch!='N') Fehlerbehandlung(17,0,ch,1);
			if (ch=='n' || ch=='N') GruppengradNull=FALSE;
			else GruppengradNull=TRUE;
		      }
		  }
		while (1)
		  {
		    if (NaechsterWert(M+1, Quadratfrei, TRUE, erstes, erstes) &&
			BLFberechnung(TRUE, erstes, erstes) 
			&& BLFungleichNull())
		      {
			if (Monomlaengenangabe) InOut << M << ' ';
			{
			  InOut << erstes;
			  if (GruppengradNull==TRUE && MonomGrad(erstes)) InOut << '.';
			  Wertausgabe(); 
			}
			// naechster Wert:
			M++; if (M>maxM) { InOut << "Monomial too long. End." << Endl; break;}
			if (Quadratfrei && erstes[M-2]==0)
			  erstes[M-1]=1;
			else erstes[M-1]=0;
		      }
		    else
		      { 
			if (Fehlversuchsangabe) InOut << ':' << Flush;
			if (!NaechsterWert(M, Quadratfrei, TRUE, erstes,
					   erstes)) break;
		      }
		  }
	      }
	  }
	else
	  { 
	    if (hilfslaenge!=M) InOut << '0' << Endl; 
	    else { 
	      BLFberechnung(TRUE, erstes, zweites);
	      Wertausgabe(); 
	    }
	  }
      }
  }
main(int argc, char* argv[])
  {
    char ch;
    int i,j,k,l;
    if (argc < 2 || argc > 3)
      { return Fehlerbehandlung(1,0,'\0',1); }
    // Test, ob Ausgabedatei vorhanden (fuer Eingaben!)
    if (argc==3) 
      {
	Eingabedatei.open(argv[2], ios::in);
	if (Eingabedatei)  
	  { 
	    if (Eingabedatei.get(ch) && ch!=' ')
	      InOut.Aendern(NurDateien); 
	    else
	      InOut.Aendern(Ausgabedoppelt);
	    Eingabedatei.close(); 
	  }
	else InOut.Aendern(Ausgabedoppelt);
	Ausgabedatei.open(argv[2], ios::app);
	if (!Ausgabedatei) {return Fehlerbehandlung(16,0,'\0',1); }
      }
    Eingabedatei.open(argv[1], ios::in);
    if (!Eingabedatei)
      { return Fehlerbehandlung(2,0,'\0',1); }
    // Einlesen der Eingabedatei
    // 1. Zeile: Wert von N
    N=Zahllesen(Eingabedatei,1);
    if (N>maxN || N<2) Fehlerbehandlung(12,1,'\0',1);
    InOut << " Order of the root of unity: " << N << '\n';
    // 2. Zeile: Charakter 1 oder Bicharakter 2
    if (Eingabedatei.get(ch) && ch!='\n')
      switch (ch)
	{
          case '1': Charakter=TRUE; break;
          case '2': Charakter=FALSE; break;
          default: Fehlerbehandlung(13,2,'\0',1); break;
	}  
    // 2. Zeile: Quadrate Null
    if (ch!='\n' && Eingabedatei.get(ch) && ch!='\n')
      switch (ch)
	{	
          case 'j': case 'J': case 'Y': case 'y': Quadratfrei=TRUE; break;
	case 'n': case 'N': Quadratfrei=FALSE; break;
	case ' ': AbbruchZahl=Zahllesen(Eingabedatei,2); ch='\n'; break;
          default: Fehlerbehandlung(17,2,ch,1); break;
	}  
    if (Quadratfrei==TRUE) 
      InOut << "Squares of the generators vanish.\n";
    // 2. Zeile: Angabe der Schrittanzahl
    if (ch!='\n' && Eingabedatei.get(ch) && ch!='\n')
      switch (ch)
	{
          case 'j': case 'J': case 'Y': case 'y': 
	    Schrittanzahl=TRUE; break;
          case 'n': case 'N': Schrittanzahl=FALSE; break;
	case ' ': AbbruchZahl=Zahllesen(Eingabedatei,2); ch='\n'; break;
          default: Fehlerbehandlung(17,2,ch,1); break;
	}  
    if (Schrittanzahl==TRUE) 
      InOut << "The number of steps is indicated.\n"; 
    // 2. Zeile: Angabe der Fehlversuche
    if (ch!='\n' && Eingabedatei.get(ch) && ch!='\n')
      switch (ch)
	{
          case 'j': case 'J': case 'Y': case 'y': Fehlversuchsangabe=TRUE; break;
          case 'n': case 'N': Fehlversuchsangabe=FALSE; break;
	case ' ': AbbruchZahl=Zahllesen(Eingabedatei,2); ch='\n'; break;
          default: Fehlerbehandlung(17,2,ch,1); break;
	}  
    if (Fehlversuchsangabe==TRUE)
      InOut << "Information about lengths and aborted computations is given.\n"; 
    // 2. Zeile: einfache Ausgabe
    if (ch!='\n' && Eingabedatei.get(ch) && ch!='\n')
      switch (ch)
	{
          case 'j': case 'J': case 'Y': case 'y': Einfachausgabe=TRUE; break;
          case 'n': case 'N': Einfachausgabe=FALSE; break;
	case ' ': AbbruchZahl=Zahllesen(Eingabedatei,2); ch='\n'; break;
          default: Fehlerbehandlung(17,2,ch,1); break;
	}  
    if (Einfachausgabe==TRUE)
      InOut << "Simple output of values of bilinear form\n"; 
    if (ch!='\n' && Eingabedatei.get(ch))
      {
	if (ch==' ') { AbbruchZahl=Zahllesen(Eingabedatei,2); ch='\n'; }
	else if (ch!='\n')
	  Fehlerbehandlung(8,2,'\0',1);
      }
    if (AbbruchZahl==0) AbbruchZahl=1;
    if (AbbruchZahl==1)
      InOut << "Indicate how the first element is shuffled to fit to the second.\n";
    else
    InOut << "Print out a dot for each multiple of " << AbbruchZahl << " computed summands\n"; 
    // 3. Zeile: zei initialisieren
    for (i=0; i<256; i++) zei[i]=-1;
    zei[' ']=0; // Leerzeichen darf nicht vorkommen
    zei['.']=0; // Punkt darf nicht vorkommen
    InOut << "Generators of B(V): ";
    while (Eingabedatei.get(ch) && ch != '\n')
      {  
	if (zei[ch] <0) {zei[ch]=T; erzeuger[T]=ch; T++;} 
	else Fehlerbehandlung(4, 3, ch,1); 
	if (T>maxT) Fehlerbehandlung(5,3, '\0',1);
	InOut << ch;
      }
    InOut << '\n';
    // ab 4. Zeile: 
    Gruppen(Eingabedatei);
    Eingabedatei.close();
    // Monomeingabe von Tastatur, Auswertung:
    if (InOut.Nurdateien())
      {
	Eingabedatei.open(argv[2], ios::in);
      }	
    Monomeingabe(); 
  }