/* ********************************
   "make_canonical.cpp"
   標準形の計算に必要な関数−実現部
   ******************************** */

#include <stdio.h>
#include <stdlib.h>

#include "list.h"
#include "braid.h"
#include "canonical.h"
#include "make_canonical.h"
#include "braid_table.h"

#define SIZE 2304
#define MAX_LEN 15

// Biを求める
void Bi_list(int num,Cell* B[][MAX_LEN]){

  List Bi;
  B[2][1]=Bi.Init(); // 初期値
  int n,i,j;
  for(n=3;n<=num;n++){
    for(i=1;i<n-1;i++){ // B[n][i]=1...n-1B[n-1][i]
      List L;
      Cell* p=L.Init();
      for(j=1;j<n;j++){
	L.Insert(p,j);
	p=L.Next(p);
      }
      List B_dec;
      B_dec.Ref_init(B[n-1][i]);
      L.Insert(p,B_dec);
      B[n][i]=L.Init();
    }
    for(i=n-1;i<n;i++){ // B[n][i]=n...1n...2...21
      List F(n);
      fundamental(F);
      Cell* p=F.Pre(F.Last());
      F.Delete(p);
      B[n][i]=F.Init();
    }
  }
}

// 逆元をBiで置き換え,基本ブレイドを左に集める
int make_positive(List& L){

  // 消去できる逆元を消去
  Cell* p=L.Pre(L.Last());
  do{
    if(L.Element(p)<0){
      int i=L.Element(p)*(-1);
      if(L.Element(L.Pre(p))==i){
	Cell* q=L.Pre(p);
	Cell* r=L.Next(p);
	L.Delete(p);
	L.Delete(q);
	p=r;
      }else if(L.Element(L.Next(p))==i){
	Cell* q=L.Next(p);
	Cell* r=L.Next(q);
	L.Delete(p);
	L.Delete(q);
	p=r;
      }else{
	p=L.Pre(p);
      }
    }else{
      p=L.Pre(p);
    }
  }while(p!=L.Init());

  // 逆元を置き換える
  Cell* Bi[L.Num()+1][MAX_LEN];
  Bi_list(L.Num(),Bi);
  p=L.Pre(L.Last());
  while(p!=L.Init()){
    if(L.Element(p)<0){
      int i=L.Element(p)*(-1);
      List A; A.Ref_init(Bi[L.Num()][i]);
      L.Insert(p,A);
    }
    p=L.Pre(p);
  }

  // 基本ブレイドを左に集める
  int u=0; // 基本ブレイドの数
  p=L.Next(L.Init());
  while(p!=L.Last()){
    if(L.Element(p)<0){
      collect_delta(L,p); u--;
      p=L.Pre(p); L.Delete(L.Next(p));
    }
    p=L.Next(p);
  }

  return u;
}

// 冗長ブレイドを,前から見て最長の順列ブレイドとその他の部分に分ける
Cell* decomp(List& L,Cell* p,Cell* hl){
  int i,j;
  Cell* q;

  // Lのpからhlまでを配列に格納
  int B[MAX_LEN];
  q=p; i=0;
  while(q!=L.Next(hl)){
    B[i]=L.Element(q);
    q=L.Next(q); i++;
  }
  int len=i;

  // 入力されたブレイドを探す
  int index;
  for(i=0;i<SIZE;i++){
    for(j=0;j<len;j++){
      if(B[j]!=R[len][i][j]) break;
    }
    if(j==len){ index=i; break; }
  }

  // Lを更新
  q=p; j=0;
  int crs=0;
  Cell* hl_new;
  while(q!=L.Next(hl)){
    L.Set_element(q,M[len][index][j]);
    crs++;
    if(crs==N[len][index]) hl_new=q;
    q=L.Next(q); j++;
  }
  
  return hl_new;
}

// 正ブレイドをleft-weightedに分解する
void decomp_head_tail(List& L,Canonical& C){

  int i=1;
  Cell* head_last=L.Init(); // headの最後
  Cell* hl;
  do{
    hl=L.Pre(L.Last()); Cell* p=hl;;
    List H(L.Num());
    // headとtailに分解する
    do{
      H.Insert(H.Init(),L.Element(p));
      int judge=judge_braid(H);
      if(judge==1){       // 順列ブレイド
	p=L.Pre(p);
      }else if(judge==2){ // 基本ブレイド
	// Δを左に集める
	Cell* q=L.Next(hl);
	int u=C.Delta(); u++; C.Set_delta(u);
	collect_delta(L,p);
	L.Delete(p,hl);
	H.Clear();
	// lastからやり直す
	hl=L.Pre(L.Last());
	p=hl;
	/*
	if(L.Pre(q)==head_last){
	  // lastからやり直す
	  hl=L.Pre(L.Last());
	  p=hl;
	}else{
	  // 1つ前の順列ブレイドからやり直す
	  List T(L.Num());
	  while(q!=L.Last()){
	    T.Insert(T.Init(),L.Element(q));
	    if(judge_braid(T)==3) break;
	    q=L.Next(q);
	  }
	  hl=L.Pre(q);
	  p=hl;
	}
	*/
      }else{              // 冗長ブレイド
	hl=decomp(L,p,hl);
	H.Clear();
	p=hl;
      }
    }while(p!=head_last);
    head_last=hl; // head確定 -> tailに対して処理を繰り返す
  }while(head_last!=L.Pre(L.Last()));

  C.Set_length(i-1);
  C.Set_glist(L);
}

// canonical formを構成する
void make_canonical(List& L,Canonical& C){
  Cell* p;
  int u;

  // 紐の本数>2のとき
  if(L.Num()>2){
    C.Set_num(L.Num());
    // リストが空でないとき
    if(L.Empty()!=true){
      // 逆元を置き換える
      u=C.Delta();
      u+=make_positive(L);
      C.Set_delta(u);
      // リストが空でないとき,left-weightedに分割
      if(L.Empty()!=true) decomp_head_tail(L,C);
    }else{
      puts("List is empty.");
    }
  }else{
    puts("Number of strings is smaller than 3.");
  }
}