#ifndef _TFT_h
#define _TFT_h
//---------------------------------------------------------------------------
#include <stddef.h>
#include <iostream>
#include <typeinfo>
#include <cstring>

#include <cstdio>

//#include "top.h"
#include "ttrans.h"
using namespace std;
//---------------------------------------------------------------------------

/// Klasa bazowa przetwornika sko�czonego.
/**
    \remark Po co ta klasa? Co dotyczy samych przej��, przenie�� do TTrans,
    reszt� wcieli� do TFT.
*/
class FT
{
public:
  FT() : copy_default(false), print_mode(OO), ttn(0) {};

//print mode
  enum OUTPUT { II,                         ///< tylko symbole wej�ciowe
                OO,                         ///< tylko symbole wyj�ciowe
                IOIO,                       ///< symbol wyj�ciowy po wej�ciowym
                OIOI,                       ///< symbol wyj�ciowy przed wej�ciowym
                IIOO,                       ///< ca�e wej�cie, potem ca�e wyj�cie
                OOII                        ///< ca�e wyj�cie, potem ca�e wej�cie

              };

/// maks d�ugo�� �cie�ki
  static const unsigned int ftMAXPATH=500;

/// maks d�ugo�� opisu typu symbolu we/wy
/**
    \remark Przenie�� do TTrans
*/
  static const unsigned int ftTYPELEN=32;

/// specjalny symbol dla warto�ci 'epsilon'
/**
    \remark Przenie�� do TTrans
*/
  static const char ftEPSILON='~';

/// specialny symbol dla warto�ci 'default'
/**
    \remark Przenie�� do TTrans
*/
  static const char ftDEFAULT='@';

/// domy�lny symbol wyj�ciowy (true-'@', flase-'~')
/**
    \remark Przenie�� do TTrans(???)
*/
  bool copy_default;

/// tryb wyj�cia
  OUTPUT print_mode;

/// false, je�li automat nie ma przej��
  operator bool() { return (bool)ttn; };

  virtual const char* intype() { return itype; };
  virtual const char* outtype() { return otype; };

protected:

/// liczba element�w tablicy tt
  unsigned long ttn;

/// liczba stan�w
  unsigned long states;

/// liczba przej��
  unsigned long transitions;

/// typ symboli wej�ciowych (napis)
/**
    \remark Przenie�� do TTrans(???)
*/
  char itype[ftTYPELEN];

/// typ symboli wyj�ciowych (napis)
/**
    \remark Przenie�� do TTrans(???)
*/
  char otype[ftTYPELEN];
};

//---------------------------------------------------------------------------

/// Szablon przetwornika sko�czonego
/**
    \param I - typ symbolu wej�ciowego
    \param Ipass - typ, jaki ma by� u�yty przy przekazywaniu symbolu we jako parametru
                   do funkcji (metody), r�wny \a I lub \a I&
    \param O - typ symbolu wyj�ciowego
    \param Opass - typ, jaki ma by� u�yty przy przekazywaniu symbolu wy jako parametru
                   do funkcji (metody), r�wny \a O lub \a O&
    \param - typ przej�cia, musi by� podklas� TTrans
*/
template<class I, class Ipass, class O, class Opass, class TT>
class TFT : public FT
{


public:

  TFT() : FT(), tt(NULL) { setiotypes(); };

/**
\name Metody poziomu 1
Poziom przej��.
*/

//@{

/// Test, czy przej�cie \a t akceptuje symbol \a in.
  bool accepts(long t, Ipass in) const;

/// Test, czy lista przej�� dla aktualnego stanu jest kontynuowana po \a t.
  bool continued(long t) const;

/// Stan, do kt�rego prowadzi przej�cie \a t.
/**
    \pre !empty(t)
*/
  long next(long t) const;

/// Symbol wej�ciowy przej�cia \a t.
  Ipass input(long t) const;

/// Symbol wyj�ciowy przej�cia \a t.
  Opass output(long t) const;

/// Zwraca \c true, je�li symbolem we przej�cia \a t jest epsilon.
  bool epsi(long t) const;

/// Zwraca \c true, je�li symbolem we przej�cia \a t jest symbol domy�lny.
  bool defi(long t) const;

/// Zwraca \c true, je�li symbolem wy przej�cia \a t jest epsilon.
  bool epso(long t) const;

/// Zwraca \c true, je�li symbolem wy przej�cia \a t jest symbol domy�lny.
  bool defo(long t) const;

/// Indeks przej�cia przez \a in.
  long tra(long t, Ipass in) const;

/// Indeks przej�cia przez \a in - non-deterministic.
  long tra_nd(long t, Ipass in, long nth) const;

//@}

/**
\name Poziom 2
Poziom stan�w. Stan (indeks stanu) = indeks jego pierwszego przej�cia
*/
//@{
/// Zwraca \c true je�li stan \a s jest pusty (nie ma z niego przej��).
  bool empty(long s) const { return tt[s].empty(); }

/// Zwraca \c true je�li stan \a s jest stanem ko�cowym.
  bool final(long s) const { return tt[s].final(); }

  long next(long t, Ipass in) const;

//long trans(const I* si, I* so, long& olen) const;

  long gtra(long s, const I* w, long maxpath=ftMAXPATH) const;

//@}

/**
\name Poziom 3
Poziom ...
*/
//@{
  long cont(long s=-1, I* c=NULL) const;

  long match(const I* w=NULL, long* p=NULL) const;

  long match_nd(const I* w=NULL, long* p=NULL) const;

  long lgstmatch(const I* w, long* p, long& plen, long maxpath=ftMAXPATH) const;

  /*NOWE*/

  long lgstpath(I*& buf, long*& path, long start=0) const;

  long pref(I*& buf, I sep, long start=0) const;

//@}

protected:

  TT* tt;                // tablica przej��

  long prn(const I* si, long* p, O* so) const;

  void prntt(ostream& os);

  void sort();

  void setiotypes();     // NIE DZIA�A (dlaczego???)

//  friend ostream& operator<<(ostream&,const CDFA&);
//  friend istream& operator>>(istream&,CDFA&);

private:
  long prn_oo(const I* si, long* p, O* so) const;
  long prn_ioio(const I* si, long* p, O* so) const;
  long prn_oioi(const I* si, long* p, O* so) const;
  long prn_iioo(const I* si, long* p, O* so) const;
  long prn_ooii(const I* si, long* p, O* so) const;
};


//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

/**
    stan = indeks pierwszego przej�cia

    state(t) = stan, do kt�rego nale�y t

    symbol zerowy = symbol s, dla kt�rego (bool)s zwraca \c false,
    w przypadku znak�w - '\0'
*/

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------


template <class I, class Ipass, class O, class Opass, class TT>
inline
bool TFT<I,Ipass,O,Opass,TT>::accepts(long t, Ipass in) const
{ return tt[t].accepts(in); }

/// Test whether the transition list continues after \a t.
template <class I, class Ipass, class O, class Opass, class TT>
inline
bool TFT<I,Ipass,O,Opass,TT>::continued(long t) const
{ return tt[t].continued(); }

/**
    \pre !empty(t)
*/
template <class I, class Ipass, class O, class Opass, class TT>
inline
long TFT<I,Ipass,O,Opass,TT>::next(long t) const
{ return tt[t].next(); }

template <class I, class Ipass, class O, class Opass, class TT>
inline
Ipass TFT<I,Ipass,O,Opass,TT>::input(long t) const
{ return tt[t].in(); }

template <class I, class Ipass, class O, class Opass, class TT>
inline
Opass TFT<I,Ipass,O,Opass,TT>::output(long t) const
{ return tt[t].out(); }

template <class I, class Ipass, class O, class Opass, class TT>
inline
bool TFT<I,Ipass,O,Opass,TT>::epsi(long t) const
{ return tt[t].epsi(); }

template <class I, class Ipass, class O, class Opass, class TT>
inline
bool TFT<I,Ipass,O,Opass,TT>::defi(long t) const
{ return tt[t].defi(); }

template <class I, class Ipass, class O, class Opass, class TT>
inline
bool TFT<I,Ipass,O,Opass,TT>::epso(long t) const
{ return tt[t].epso(); }

template <class I, class Ipass, class O, class Opass, class TT>
inline
bool TFT<I,Ipass,O,Opass,TT>::defo(long t) const
{ return tt[t].defo(); }

/**
    \param +t - indeks przej�cia
    \param +in - symbol we
    \return Indeks przj�cia (>=\a t) dla bie��cego stanu, kt�re
    akceptuje symbol we \a in lub -1, je�li nie ma takiego przej�cia
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::tra(long t, Ipass in) const
{
  if(t<0 || t>=ttn)
    return -1;

  if(empty(t)) return -1;
  while(!accepts(t,in))
    if(continued(t))
      t++;
    else
      return -1;
  return t;
}

//---------------------------------------------------------------------------
/// Indeks przej�cia - wersja dla automatu niedeterministycznego.
/**
    \param +t  - indeks przej�cia
    \param +in - symbol we
    \return Indeks przj�cia (>=\a t) dla bie��cego stanu, kt�re
    akceptuje symbol we \a in lub -1, je�li nie ma takiego przej�cia
    Je�li nth==0, t1>=t, w przeciwnym razie t1>t.
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::tra_nd(long t, Ipass in, long nth) const
{
  if(t<0 || t>=ttn)
    return -1;

  if(nth)
    if(continued(t))
      t++;
    else
      return -1;
  else
  { if(empty(t)) return -1; }

  while(!accepts(t,in))
    if(continued(t))
      t++;
    else
      return -1;

  return t;
}

//}

//---------------------------------------------------------------------------
//----------------------------------------------------------------------------


/// Funkcja przej�cia.
/**
    \param t - stan
    \param in - symbol we
    \return Stan, do kt�rego mo�na przej�� z \a t po wp�ywem symbolu \a in
    lub -1, je�li nie ma przej�cia przez \a in

*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::next(long t, Ipass in) const
{
  if(t<0 || (unsigned long)t>=ttn)
    return -1;

  if(empty(t)) return -1;
  while(!accepts(t,in))
    if(continued(t))
      t++;
    else {
      return -1;
    }

  return next(t);
}

//---------------------------------------------------------------------------

//----------------------------------------------------------------------------
/// Uog�lniona funkcja przejscia.
/**
    \param +s - stan
    \param +w - wska�nik pierwszego elementu ci�gu symboli we, zako�czonego symbolem zerowym
    \param maxpath maksymalna d�ugo�� �cie�ki, domy�lnie ftMAXPATH
    \return stan osi�galny z \a s pod wp�ywem \a w (na �cie�ce mog� si� pojawi�
    epsilon-przej�cia
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::gtra(long s, const I* w, long maxpath) const
{
  if(s<0 || (unsigned long)s>=ttn)
    return -1;

  long i=0;
  while(*w)
  {
    if(i>maxpath || empty(s)) return -1;
    while(!accepts(s,*w))
      if(continued(s))
        s++;
      else
        return -1;
    if(!epsi(s)) w++;
    s=next(s);
    i++;
  }
  return s;
}

//----------------------------------------------------------------------------

/// Kontynuacja.
/**
...
\param +s stan, je�li -1 - poszukiwane jest nast�pne rozwi�zanie
\param -c ci�g symboli we ze �cie�ki prowadz�cej z \a s do
       stanu ko�cowego
\return d�ugo�� ci�gu \a c (= d�ugo�� �cie�ki)
\remark DZIA�A TYLKO DLA ZNAK�W!!!
        EPSILON-PRZEJ�CIA NIEDOZWOLONE!!!
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::cont(long s, I* c) const
{
  static unsigned long path[ftMAXPATH]={0};
  static unsigned long  i=0;
  static bool more=false;

  bool found=false;

  if(s!=-1)
  {
    if(s<0 || (unsigned long)s>=ttn)
      more=false;
    else
    {
      i=0;
      c[0]=0;
      path[0]=s;
      more=true;
      if(final(s))
        found=true;
    }
  }

  while(more && !found)
  {
    if(!empty(path[i]) && i<ftMAXPATH)
    {
      path[i+1]=next(path[i]);
      c[i]=input(path[i]);
      i++;
    }
    else
    {
      do
      {
        if(i>0)
          c[--i]=0;
        else
          more=false;
      }while(more && !continued(path[i]));
      path[i]=path[i]+1;
    }
    if(final(path[i]))
    {
      found=true;
      c[i]=0;
    }
  }
  return i;
}

//----------------------------------------------------------------------------
/// Dopasowannie.
/**
    \remark Nie zaimplementowane.
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::match(const I* w, long* p) const
{}

//----------------------------------------------------------------------------
/// Dopasowanie niedeterministyczne.
/**
    \param +w - wska�nik pierwszego elementu ci�gu symboli we, zako�czonego symbolem zerowym,
    je�li NULL - poszukiwane jest nast�pne rozwi�zanie
    \param -p ci�g przej�� zako�czony -1
    \return d�ugo�� dopasowania (PO CO?)
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::match_nd(const I* w, long* p) const
{
  static bool more=false;
  static I *w0, *wc;
  static long s=0, *p0, *pc, *pc_bound;

  bool found=false;

  if(w)
  {
    wc=w0=w;
    pc=p0=p;
    more=true;
    pc_bound=pc+ftMAXPATH;
    if(final(s=0))
    {
      *pc=-1; return 0;
    }
  }

  while(more)
  {
    if(*wc && pc<pc_bound && (*pc=trand(s,*wc,0))>=0)
    { if(!epsi(*pc)) wc++; s=next(*pc); pc++; }
    else
      while(true)
      {
        if(pc==p0) { more=false; return -1; }
        if(!epsi(*(--pc))) wc--;
        if((*pc=trand(*pc,*wc,1))>=0)
        { if(!epsi(*pc)) wc++; s=next(*pc); pc++; break; }
      }
    if(final(s)) { *pc=-1; return wc-w0; }
  }
  return -1;
}

//----------------------------------------------------------------------------
/// Najd�u�sze dopasowanie.
/**
    \param +w wska�nik pierwszego elementu ci�gu symboli wej�ciowych
    \param -p �cie�ka
    \param -plen d�ugo�� �cie�ki
    \param +maxpath maks dd�ugo�� �cie�ki, domy�lnie FT::ftMAXPATH
    \return d�ugo�� skonsumowanego wej�cia
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>
        ::lgstmatch(const I* w, long* p, long& plen, long maxpath) const
{
  long s=0;
  long t;
  long i=0;
  const char* w0=w;
  long ilen=0;
  while(*w && i<maxpath && (t=tra(s,*w))>=0)
  {
    if(!epsi(t)) w++;
    s=next(t);
    i++;
    *(p++)=t;
    if(final(s)) { plen=i; ilen=w-w0; }
  }
  *p=-1;
  return ilen;
}

//----------------------------------------------------------------------------
/// Najd�u�sza �cie�ka.
/**
    \param +buf  wska�nik pierwszego elementu ci�gu symboli wej�ciowych
    \param -buf  pozycja jeden za skonsumowanym prefiksem
    \param +path wska�nik pierwszego elementu wektora przej��
    \param -path wska�nik jeden za ostatnim przej�ciem
    \return d�ugo�� skonsumowanego prefiksu (PO CO? LEPIEJ D� �CIE�KI)
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>
        ::lgstpath(I*& buf, long*& path, long start) const
{
  long s=start;
  long t;
  const char* buf0=buf;
  const long* pathlimit=path+FT::ftMAXPATH;
  while(*buf && path<pathlimit && (t=tra(s,*buf))>=0)
  {
    if(!epsi(t)) buf++;
    s=next(t);
    *(path++)=t;
  }
  return buf-buf0;
}

//----------------------------------------------------------------------------
/// Najd�u�szy prefiks.
/**
    \param +buf  wska�nik pierwszego elementu ci�gu symboli wej�ciowych
    \param -buf  pozycja jeden za skonsumowanym prefiksem
    \param +sep  separator
    \return stan po przej�ciu przez \a sep
    \remark Dzia�a tylko dla automat�w deterministycznych, minimalnych, eps-wolnych,
              gdzie d�. �cie�ki == d�. dopasowania.
*/
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>
        ::pref(I*& buf, I sep, long start) const
{
  static long pathtab[ftMAXPATH];
  //  static long* path=pathtab;	
  long* path=pathtab;
  static bool more;

  long s;
  if(*buf)                     // pierwsze wywo�anie
  {
    if(!lgstpath(buf,path,start))
      return -1;
    --path;
    more=true;
  }
  else                         // kolejne  wywo�anie
    --buf,--path;
  while(more)
    if(path>=pathtab)
      if((s=next(next(*path),sep))>=0) {
        return s;
      }
      else
        --buf, --path;
    else
    {
      more=false;
      return -1;
    }
  return -1;
}

//----------------------------------------------------------------------------

/*
template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::trans(const I* si, O* so, long& olen) const
{
  long p[ftMAXPATH];
  long ilen;
  long plen;
  if((ilen=lgstmatch(si,p,plen))>0)
    olen=prn(si,p,so);
  else
    ilen=olen=0;
  return ilen;
}
*/
//----------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::prn(const I* si, long* p, O* so) const
{
  switch(print_mode)
  {
    case OO: return prn_oo(si,p,so);
    case IOIO: return prn_ioio(si,p,so);
    case OIOI: return prn_oioi(si,p,so);
    case IIOO: return prn_iioo(si,p,so);
    case OOII: return prn_ooii(si,p,so);
  }
}

//----------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::prn_oo(const I* si, long* p, O* so) const
{
  char* so0=so;
  while(*p>=0)
  {
    long t=*p;
    if(!epso(t))
    {
      if(defo(t))
        *(so++)=*si;
      else
        *(so++)=output(t);
    }
    if(!epsi(t)) si++;
    p++;

  }
  return so-so0;
}

//----------------------------------------------------------------------------


template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::prn_ioio(const I* si, long* p, O* so) const
{
  char* so0=so;
  while(*p>=0)
  {
    long t=*p;
    if(!epsi(t))
      *(so++)=*si;
    if(!epso(t))
      if(defo(t))
        *(so++)=*si;
      else
        *(so++)=output(t);
    if(!epsi(t)) si++;
    p++;
  }
  return so-so0;
}


//----------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::prn_oioi(const I* si, long* p, O* so) const
{
  char* so0=so;
  while(*p>=0)
  {
    long t=*p;
    if(!epso(t))
    {
      if(defo(t))
        *(so++)=*si;
      else
        *(so++)=output(t);
    }
    if(!epsi(t))
      *(so++)=*(si++);
    p++;
  }
  return so-so0;
}

//----------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::prn_iioo(const I* si, long* p, O* so) const
{
  const char* si0=si;
  long* p0=p;
  char* so0=so;
  while(*p>=0)
  {
    long t=*p;
    if(!epsi(t))
    {
      *(so++)=*si;
      si++;
    }
    p++;
  }
  si=si0;
  p=p0;
  while(*p>=0)
  {
    long t=*p;
    if(!epso(t))
      if(defo(t))
        *(so++)=*si;
      else
        *(so++)=output(t);
    if(!epsi(t)) si++;
    p++;
  }
  return so-so0;
}

//----------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
long TFT<I,Ipass,O,Opass,TT>::prn_ooii(const I* si, long* p, O* so) const
{

  const char* si0=si;
  long* p0=p;
  char* so0=so;
  while(*p>=0)
  {
    long t=*p;
    if(!epso(t))
    {
      if(defo(t))
        *(so++)=*si;
      else
        *(so++)=output(t);
    }
    if(!epsi(t)) si++;
    p++;
  }
  si=si0;
  p=p0;
  while(*p>=0)
  {
    long t=*p;
    if(!epsi(t))
      *(so++)=*(si++);
    p++;
  }
  return so-so0;
}

//---------------------------------------------------------------------------

template<class I, class Ipass, class O, class Opass, class TT>
void TFT<I,Ipass,O,Opass,TT>::sort()
{
  long t=0;
  while(t<ttn)
  {
    long t0=t;
    long tn=1;
    while(continued(t++)) tn++;
    if(tn>1)
    {
      long eps=-1;
      long def=-1;
      for(int i=0; i<tn; i++)
      {
        if(defi(t0+i))
          if(epsi(t0+i)) eps=i; else def=i;
      }
      if(eps>=0 && eps<tn-1)
      {
        TT temp=tt[t0+eps];
        memmove(tt+t0+eps+1,tt+t0+eps,tn-eps-1);
        tt[t-1]=temp;
      }
      if(def>eps) def--;
      if(def>=0 && def<tn-1)
      {
        TT temp=tt[t0+def];
        if(eps>=0)
        {
          memmove(tt+t0+def+1,tt+t0+def,tn-eps-2);
          tt[t-2]=temp;
        }
        else
        {
          memmove(tt+t0+def+1,tt+t0+def,tn-eps-2);
          tt[t-1]=temp;
        }
      }
      while(t0<t-1)
        tt[t0++].continued(true);
      tt[t-1].continued(false);
    }
  }
}

//---------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
void TFT<I,Ipass,O,Opass,TT>::setiotypes()
{
  int i=0;
  const char* it=typeid(I).name();
  while(*it)
    if(*it==' ')
    { it++; continue; }
    else
      itype[i++]=*(it++);
  itype[i]='\0';

  i=0;
  const char* ot=typeid(O).name();
  while(*ot)
    if(*ot==' ')
    { ot++; continue; }
    else
      otype[i++]=*(ot++);
  otype[i]='\0';
};

//---------------------------------------------------------------------------

template <class I, class Ipass, class O, class Opass, class TT>
void TFT<I,Ipass,O,Opass,TT>::prntt(ostream& os)
{
  for(long i=0; i<ttn; ++i)
  {
    os << i << ':';
    os << tt[i];
  }
}

#endif