source: _old/app/src/lib/tft.h @ 1e121f4

#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