/* ****************************
   "braid.cpp"
   ブレイドに対する操作−実現部
   **************************** */

#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "braid.h"
#include "canonical.h"
#include "make_canonical.h"

// 生成元リストの作成(ファイル入力)
void create_list(List& L,FILE* in){
  int n;
  fscanf(in,"%d",&n);
  L.Set_num(n);

  L.Clear();

  Cell* p=L.Init();
  int x;
  while(true){
    fscanf(in,"%d",&x); if(x==0) break;
    L.Insert(p,x); p=L.Next(p);
  }
}

// 生成元リストの作成
void create_list(List& L){
  int n;
  printf("Number of strings:"); scanf("%d",&n);
  L.Set_num(n);

  L.Clear();

  Cell* p=L.Init();
  printf("Artin's generator:");
  int x;
  while(true){
    scanf("%d",&x); if(x==0) break;
    L.Insert(p,x); p=L.Next(p);
  }
}

// 生成元リストの表示(ファイル出力)
void display_list(List& L,FILE* out){
  Cell* p;
  p=L.Next(L.Init());

  while(p!=L.Last()){ 
    fprintf(out,"%3d",L.Element(p));
    p=L.Next(p);
  }
  fprintf(out,"\n");
}

// 生成元リストの表示
void display_list(List& L){
  Cell* p;
  p=L.Next(L.Init());

  while(p!=L.Last()){ 
    printf("%3d",L.Element(p));
    p=L.Next(p);
  }
  putchar('\n');
}

// 標準形の表示(ファイル出力)
void display_canonical(Canonical& C,FILE* out){
  fprintf(out,"delta^%d",C.Delta());
  List L; C.GList(L);
  display_list(L,out);
}

// 標準形の表示
void display_canonical(Canonical& C){
  printf("delta^%d",C.Delta());
  List L; C.GList(L);
  display_list(L);
}

// 標準形を生成元の積に戻す
void restore_canonical(Canonical& C,List& L){
  L.Set_num(C.Num());
  C.GList(L);

  int u=C.Delta();
  if(u!=0){
    List F(C.Num()); fundamental(F);
    List F_inverse; inverse(F,F_inverse);
    Cell* p=L.Init();
    if(u>0) while(u-->0) L.Insert(p,F);
    else while(u++<0) L.Insert(p,F_inverse);
  }
}

// リストのコピー
void copy_list(List& A,List& B){
  Cell* p=A.Next(A.Init());
  Cell* q=B.Init();

  while(p!=A.Last()){
    B.Insert(q,A.Element(p));
    p=A.Next(p);
    q=B.Next(q);    
  }
}

// 生成元の積で表されたブレイドの積を計算
void product(List& A,List& B,List& AB){

  int n;
  if(A.Num()>=B.Num()) n=A.Num();
  else n=B.Num();
  AB.Set_num(n);

  AB.Insert(AB.Init(),B);
  AB.Insert(AB.Init(),A);
}

// 標準形で表されたブレイドの積を計算(紐の本数が同じときに限る)
void product(Canonical& A,Canonical& B,Canonical& AB){

  List A_list(A.Num());
  A.GList(A_list);
  List B_list(B.Num());
  B.GList(B_list);
  List AB_list(A.Num());
    
  if(B.Delta()%2==1 || B.Delta()%2==-1){
    Cell* p=A_list.Last();
    collect_delta(A_list,p);
  }
  AB.Set_delta(A.Delta()+B.Delta());

  AB_list.Insert(AB_list.Init(),B_list);
  AB_list.Insert(AB_list.Init(),A_list);

  make_canonical(AB_list,AB);
}

// 生成元の積で表されたブレイドの逆元を作成
void inverse(List& L,List& I){

  I.Set_num(L.Num());  

  Cell* p=L.Pre(L.Last());
  Cell* q=I.Init();  
  while(p!=L.Init()){
    I.Insert(q,L.Element(p)*(-1));
    p=L.Pre(p); q=I.Next(q);
  }
}

// 標準形で表されたブレイドの逆元を作成
void inverse(Canonical& C,Canonical& I){
  
  List L; restore_canonical(C,L);
  List L_inverse; inverse(L,L_inverse);
  make_canonical(L_inverse,I);
}

// 基本ブレイドの作成
void fundamental(List& F){

  if(F.Num()==0) puts("Number of strings is not set.");

  int i,j;
  Cell* p=F.Init();

  for(i=1;i<F.Num();i++){
    for(j=F.Num()-1;j>=i;j--){
      F.Insert(p,j);
      p=F.Next(p);
    }
  }
}

// 基本ブレイドを左に集める
void collect_delta(List& L,Cell* p){
  Cell* q=L.Pre(p);

  while(q!=L.Init()){
    L.Set_element(q,L.Num()-L.Element(q));
    q=L.Pre(q);
  }
}

// 順列,基本,冗長ブレイドの判定
int judge_braid(List& L){
  int i,j;

  int C[L.Num()+1][L.Num()+1]; // 交差を記録
  for(i=1;i<=L.Num();i++)
    for(j=1;j<=L.Num();j++) C[i][j]=0;
  int S[L.Num()+1];            // 紐の動きを記録
  for(i=1;i<=L.Num();i++) S[i]=i;
  int crs=0;                   // 交差の数
    
  Cell* p=L.Next(L.Init());
  do{
    int x=L.Element(p);
    int tmp=S[x]; S[x]=S[x+1]; S[x+1]=tmp;
    i=S[x]; j=S[x+1];
    if(C[i][j]==1) return 3; // 冗長ブレイド
    C[i][j]=C[j][i]=1; crs++;
    p=L.Next(p);
  }while(p!=L.Last());

  if(crs==L.Num()*(L.Num()-1)/2) return 2; // 基本ブレイド
  else return 1; // 順列ブレイド
}