source: src/lib/tft.h

#ifndef _TFT_h
#define _TFT_h
//---------------------------------------------------------------------------
#include <cstddef>
#include <iostream>
#include <typeinfo>
#include <cstring>
#include <cstdio>

//#include "top.h"
#include "ttrans.h"
//---------------------------------------------------------------------------

/// 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