/* vstring */
/****************************************************************************/
/*
** string-luokan osoittainen toteutus k„„nt„j„„n jossa ko. luokkaa ei ole.
**
**  Tekij„t:          Vesa Lappalainen
**                    Ohjelmointikurssi 1996
**  Tehty:            09.12.1995
**  Korjattu:         15.03.1996/vl
**  Mit„ korjattu:    lis„tty metodi varaa1 ja konstruktorit ja
**                    isonna_koko k„ytt„m„„n t„t„
**                    varaa-metodi poistaa ensin vanhan tilan
**  Korjattu:         24.10.1996/vl
**  Mit„ korjattu:    lis„tty <,>,<=,>= ja lis„ksi sekalainen m„„r„
**                    operattoreita toiminaan, mm. s = "Alku " + s2;
**                    korjattu trimmaa ja insert toimimaan oikein
**                    read_line poistettu
**                    getlinessa tarvitaan loppumerkki
**  Korjattu:         20.1.1998/vl
**  Mit„ korjattu:    string::npos, find ja alkeellinen rfind
**  Korjattu:         24.1.1998/vl
**  Mit„ korjattu:    find(string) ja find(const char *)
**                    konstruktori vstring(st,pos,n) -lis„tty
**                    copy
**  Korjattu:         25.1.1998/vl
**  Mit„ korjattu:    replace, rfind, find_first_of -sarja
**                    Muutettu kokonaan C++ Programming language 3th ed.
**                    luku 20 mukaiseksi, paitsi
**                    - ei iterator
**                    - substring -luokkaa
**                    - data on 0-loppuinen („l„ luota t„h„n)
**                      => datassa ei voi olla 0-merkki„
**                    - ei allocator -k„sittely„
**                    - ei heit„ poikkeuksia
**                    - getline ja >> kest„„ vain 400 merkin sy”t”n
**  Korjattu:         12.3.1998/vl
**                    - konstruktori vstring(int n=31,char c=0)
**                      muutettu: varaa1(n+1); ...
**
**  Korjattu:         18.1.1999/vl
**                    - npos:in k„ytt” muutettu siten, ett„ se toimii
**                      pelk„st„„n includaamalla t„m„ tiedosto
**                      my”s isoissa projekteissa.
**  Korjattu:         09.3.1999/vl
**                    - swap korjattu toimimaan
**
** Yksinkertainen string-luokka joka korvataan paremmalla.
** Oikeastihan ANSI:n mukaan t„llainen pit„isi jo tulla k„„nt„j„n mukana.
** T„m„ on toteutus mm. Turbo-C:t„ varten, jotta voidaan
** tehd„ "standardin"-mukaisia ohjelmia.
** Kopioi Turbo-C++:n tai Borland C++ 3.1:n include hakemistoon
** nimelle string.   (ei string .h eika string.cpp!)
**
** Jos k„ytt„„ metodeja:
**   find_last_of,find_last_not_of,rfind (paitsi rfind(char c))
** pit„„ linkitt„„ my”s mjonot.c ja vstring.cpp
** sek„ m„„ritell„ vakio USE_VSTRING
** Vakio USE_VSTRING pit„„ m„„ritell„ my”s jos halutaan k„ytt„„ sanaa
**   npos
** muussakin yhteydess„ kuin string::npos.  T„ll”in pit„„
** tietty my”s linkitt„„ mjonot.c ja vstring.cpp
**
*****************************************************************************/

#ifndef __VSTRING
#define __VSTRING
#define vstring string
#include <iostream.h>
#include <string.h>

#ifndef STDFIX_H
#define STDFIX_H
inline int std_dummy() { return 0; }
#define using
#define namespace
#define std
#define bool int
#define false 0
#define true (!false)

//#define new(m) new
#define try
#define catch(m) if ( std_dummy() )
#define throw(T) std_dummy()
#endif

//#define catch
//nothrow

typedef size_t size_type;
const size_t NPOS = size_t(-1); //= size_t(9999);

//----------------------------------------------------------------------------
class vstring {
public:
#ifndef USE_VSTRING
#define npos Npos()
  static size_t Npos() { return NPOS; }
#else
  static const size_t npos;
#endif

private:
  char *cstr;
  char tyhja[2]; // Tyhja paikka sit„ varten jos tilaa ei saada
  size_t maxkoko;  // Varatun C-merkkijonon koko
  size_t pituus;
  int  varaa1(int koko=81)               { cstr = new char[koko]; maxkoko = 1;
                                           tyhja[0] = 0;
                                           if ( cstr ) {
                                             cstr[0] = 0; maxkoko = koko; }
                                           else cstr = tyhja;
                                           pituus = 0;
                                           return maxkoko;
                                         }
  int  varaa(int koko=81)                { poista();  return varaa1(koko);   }
  void vapauta(char *p)                  { if ( p != NULL && p != tyhja )
                                             delete [] p;
                                         }
  int poista()                           { if ( maxkoko ) vapauta(cstr);
                                           maxkoko = 0; cstr = tyhja;
                                           pituus = 0; return 0;
                                         }
  int tarkista_koko(size_t n)            { if ( n == maxkoko ) return 0;
                                           return varaa(n);                  }
  int isonna_koko(size_t n)              { if ( n <= maxkoko ) return 0;
                                           char *p = cstr;
                                           varaa1(n); vcopy(p);
                                           vapauta(p);
                                           return maxkoko;
                                         }
  void vcopy(const char *s2)             { strncpy(cstr,s2,maxkoko);
                                           cstr[maxkoko-1] = 0;
                                           pituus = strlen(cstr);
                                         }
  void ccopy(const char *s2)             { tarkista_koko(strlen(s2)+1);
                                           vcopy(s2);
                                         }
  const char &merkki(size_t pos) const   { if ( pituus <= pos )
                                             return tyhja[0];
                                           return cstr[pos];
                                         }
  char &merkki(size_t pos)               { if ( pituus <= pos )
                                             return tyhja[0];
                                           return cstr[pos];
                                         }
  vstring &trimmaa(int i)                { char *p = new char[i+1];
                                           if ( p == NULL ) return *this;
                                           strncpy(p,cstr,i+1); p[i] = 0;
                                           vapauta(cstr);
                                           cstr = p; pituus = strlen(cstr);
                                           maxkoko = i+1;
                                           return *this;
                                         }

  size_t alusta(const char *s, size_t pos=0, size_t n=npos) {
    int len = strlen(s);
    if ( pos > len ) { varaa(1); memset(cstr,1,0); }
    else {
      if ( n > len - pos ) n = len - pos;
      varaa(n+1);
      strncpy(cstr,s+pos,n); cstr[n] = 0;
      pituus = n; maxkoko = n+1;
    }
    return pituus;
  }

  int vlisaa_alkuun(char *s, const char *k)
  {
    int lk=strlen(k);
    int ls=strlen(s);

    memmove(s+lk,s,ls+1);
    memcpy(s,k,lk);
    return 0;
  }

  void vpoista_alusta(char *s,int n)
  {
    if ( s == NULL ) return;
    // Jos poistetaan enemm„n merkkej„ kuin jonon pituus
    if ( (int)strlen(s) <= n ) { s[0] = 0; }

    int len = strlen(s+n);
    memmove(s,s+n,len+1);
  }

//-------------------------------------------------------------------------
public: // Remove ei taida kuulua Bjarnen mukaan stringiin?
  vstring &remove(size_t pos, size_t n=npos)  {
    if ( pos >= pituus ) return *this;
    if ( ( n == npos ) || ( pos + n >= pituus ) ) return trimmaa(pos);
    vpoista_alusta(cstr+pos,n);
    return trimmaa(pituus-n);
  }


//-------------------------------------------------------------------------
public:
//-------------------------------------------------------------------------

// Element Access ---------------------------------------------------------

  char operator[](size_t pos) const      { return merkki(pos);               }
  char &operator[](size_t pos)           { return merkki(pos);               }
  char at(size_t n) const                { return merkki(n);                 }
  char &at(size_t n)                     { return merkki(n);                 }

// Constructors -----------------------------------------------------------

  vstring(const vstring &st, size_t pos,size_t n=npos) {
    maxkoko = 0; alusta(st.cstr,pos,n);
  }

  vstring(const char *s, size_t n) {
    int len = strlen(s); if ( len > n ) n = len;
    varaa1(n+1); vcopy(s);
  }

  vstring(const char *s)                  { varaa1(strlen(s)+1);
                                            vcopy(s);
                                          }
  vstring(int n=31,char c=0)              { varaa1(n+1); memset(cstr,c,n);
                                            cstr[n] = 0;
                                          }
  vstring(const vstring &alustus)         { varaa1(alustus.maxkoko);
                                            vcopy(alustus.cstr);
                                          }
  vstring(vstring &alustus)               { varaa1(alustus.maxkoko);
                                            vcopy(alustus.cstr);
                                          }

  // Destructor -----------------------------------------------------------
  ~vstring()                              { poista();                         }

// Assignment -------------------------------------------------------------

  vstring &operator=(const vstring &s2)   { if ( this != &s2 ) ccopy(s2.cstr);
                                            return *this;
                                          }
  vstring &operator=(const char *s2)      { ccopy(s2); return *this;          }

  vstring &operator=(char c)              { char s[2]; s[0]=c; s[1]=0;
                                            ccopy(s); return *this;           }

  vstring &assign(const vstring &st)      { return operator=(st);             }
  vstring &assign(const vstring &st, size_t pos, size_t n)  {
    return assign(vstring(st,pos,n));
  }
  vstring &assign(const char *s, size_t n)  { return assign(vstring(s,n));    }
  vstring &assign(const char *s)            { return operator=(s);            }
  vstring &assign(size_t n, char c)         { return assign(vstring(n,c));    }


// Conversion to C-Style Strings ------------------------------------------

  size_t copy(char *s,size_t n, size_t pos=0) {
    *s = 0;
    if ( pos >= length() ) return 0;
    if ( n >= length()-pos ) n = length()-pos;
    strncpy(s,cstr+pos,n); s[n] = 0;
    return n;
  }
  const char *c_str() const               { return cstr;                      }
  const char *data() const                { return cstr;                      }
  // EI saa tehd„ typecastia vstring => char * !!!
  //  operator const char *() const       { return cstr;                      }


// Comparisons ------------------------------------------------------------

  int compare(const vstring &st) const    { return compare(st.cstr);          }
  int compare(const char *s)    const     { return strcmp(cstr,s);            }
  int compare(size_t pos, size_t n, const vstring &st) const {
    return strncmp(cstr+pos,st.cstr,n);
  }
  int compare(size_t pos, size_t n, const vstring &st,
              size_t pos2, size_t n2) const {
    if ( n > n2 ) n = n2;
    return strncmp(cstr+pos,st.cstr+pos2,n);
  }
  int compare(size_t pos, size_t n, const char *s, size_t n2 = npos) const {
    if ( n > n2 ) n = n2;
    return strncmp(cstr+pos,s,n);
  }
  int operator==(const char *s2) const    { return compare(s2) == 0;          }
  int operator!=(const char *s2) const    { return compare(s2) != 0;          }
  int operator==(const vstring &s2) const { return compare(s2.cstr) == 0;     }
  int operator!=(const vstring &s2) const { return compare(s2.cstr) != 0;     }

// read_line ei olekkaan mukana :-(
//  istream &read_line(istream &is)         { vstring s(400,0);
//                                            is.getline(s.cstr,s.maxkoko);
//                                            ccopy(s.cstr); return is;
//                                          }


// Insert ------------------------------------------------------------------

  vstring &operator+=(const vstring &s2)   { return operator+=(s2.cstr);      }

  vstring &operator+=(const char *s2) {
    isonna_koko(strlen(cstr)+strlen(s2)+1);
//    liita_jono(cstr,maxkoko,s2);
    strncat(cstr,s2,maxkoko-pituus-1);
    pituus = strlen(cstr);
    return *this;
   }

  vstring &operator+=(char c)   {
    char s2[2]; s2[0] = c; s2[1] = 0;
    return operator+=(s2);
   }

  void push_back(char c) { operator+=(c); }

  vstring &append(const vstring &st) { return operator+=(st); }
  vstring &append(const vstring &st, size_t pos, size_t n) {
    return operator+=(string(st,pos,n));
  }
  vstring &append(const char *s, size_t n) { return operator+=(vstring(s,n)); }
  vstring &append(const char *s)           { return operator+=(s);    }
  vstring &append(size_t n, char c)        { return operator+=(vstring(n,c)); }

  vstring &insert(size_t pos, const vstring &st) {
    return insert(pos, st.c_str());
  }

  vstring &insert(size_t pos, const vstring &st, size_t pos2, size_t n) {
    return insert(pos, vstring(st,pos2,n));
  }

  vstring &insert(size_t pos, const char *s, size_t n) {
    return insert(pos, vstring(s,n));
  }

  vstring &insert(size_t pos, const char *s) {
    int len = strlen(s) + pituus;
    trimmaa(len);
    vlisaa_alkuun(cstr+pos,s);
    pituus = len;
    return *this;
  }

  vstring &insert(size_t pos, size_t n, char c) {
    return insert(pos,vstring(n,c));
  }

// Concatenation ----------------------------------------------------------

  vstring operator+(const char *s2) const {
    vstring s(strlen(cstr)+strlen(s2)+1,0);
    s.vcopy(cstr);
    return s+=s2;
  }

// Find -------------------------------------------------------------------

  // find -----------------------------------------------------------------

  size_t find(char c, size_t i=0) const {
    int len = length();
    if ( i > len ) return npos;
    const char *p = strchr(cstr+i,c);
    if ( !p ) return npos;
    return size_t(p-(cstr));
  }

  size_t find(const char *c, size_t i=0) const {
    int len = length();
    if ( i > len ) return npos;
    const char *p = strstr(cstr+i,c);
    if ( !p ) return npos;
    return size_t(p-(cstr));
  }

  size_t find(const char *s, size_t i, size_t n) const {
    return find(vstring(s,n),i);
  }

  size_t find(const vstring &st, size_t i=0) const {
    return find(st.cstr,i);
  }

  // rfind ----------------------------------------------------------------

  size_t rfind(const char *s, size_t i=npos) const;

  size_t rfind(const vstring &st, size_t i=npos) const {
    return rfind(st.c_str(),i);
  }

  size_t rfind(const char *s, size_t i, size_t n) const {
    return rfind(vstring(s,n),i);
  }

  size_t rfind(char c, size_t i=npos) const {
    int len = length();
    if ( i >= len ) i=len-1;
    vstring st(*this,0,i+1);
    const char *p = strrchr(st.cstr,c);
    if ( !p ) return npos;
    return size_t(p-(st.cstr));
  }

  // find_first_of --------------------------------------------------------

  size_t find_first_of(const char *s,size_t pos=0) const {
    if ( pos >= length() ) return npos;
    size_t i = strcspn(cstr+pos,s);
    if ( cstr[i+pos] == 0 ) return npos;
    return i+pos;
  }

  size_t find_first_of(const vstring &st,size_t pos=0) const {
    return find_first_of(st.c_str(),pos);
  }

  size_t find_first_of(const char *s,size_t pos, size_t n) const {
    return find_first_of(vstring(s,0,n),pos);
  }

  size_t find_first_of(char c,size_t pos=0) const {
    return find(c,pos);
  }

  // find_last_of ---------------------------------------------------------

  size_t find_last_of(const char *s,size_t pos=npos) const;

  size_t find_last_of(const vstring &st,size_t pos=npos) const {
    return find_last_of(st.c_str(),pos);
  }

  size_t find_last_of(const char *s,size_t pos, size_t n) const {
    return find_last_of(vstring(s,0,n),pos);
  }

  size_t find_last_of(char c,size_t pos=npos) const {
    return rfind(c,pos);
  }

  // find_first_not of ----------------------------------------------------

  size_t find_first_not_of(const char *s,size_t pos=0) const {
    if ( pos >= length() ) return npos;
    size_t i = strspn(cstr+pos,s);
    if ( cstr[i+pos] == 0 ) return npos;
    return i+pos;
  }

  size_t find_first_not_of(const vstring &st,size_t pos=0) const {
    return find_first_not_of(st.c_str(),pos);
  }

  size_t find_first_not_of(const char *s,size_t pos, size_t n) const {
    return find_first_not_of(vstring(s,0,n),pos);
  }

  size_t find_first_not_of(char c,size_t pos=0) const {
    return find_first_not_of(vstring(1,c),pos);
  }

  // find_last_not_of -----------------------------------------------------

  size_t find_last_not_of(const char *s,size_t pos=npos) const;

  size_t find_last_not_of(const vstring &st,size_t pos=npos) const {
    return find_last_not_of(st.c_str(),pos);
  }

  size_t find_last_not_of(const char *s,size_t pos, size_t n) const {
    return find_last_not_of(vstring(s,0,n),pos);
  }

  size_t find_last_not_of(char c,size_t pos=npos) const {
    return find_last_not_of(vstring(1,c),pos);
  }

// Replace ----------------------------------------------------------------

  vstring &replace(size_t i, size_t n, const vstring &st) {
    return replace(i,n,st.c_str());
  }
  vstring &replace(size_t i, size_t n, const vstring &st, size_t i2, size_t n2) {
    return replace(i,n,vstring(st,i2,n2));
  }
  vstring &replace(size_t i, size_t n, const char *s, size_t n2) {
    return replace(i,n,vstring(s,n2));
  }
  vstring &replace(size_t i, size_t n, const char *s) {
    remove(i,n);  return insert(i,s);
  }

  vstring &replace(size_t i, size_t n, size_t n2, char c) {
    return replace(i,n,vstring(n2,c));
  }

  vstring &erase(size_t i=0, size_t n=npos) { return remove(i,n); }

// Substrings -------------------------------------------------------------

  vstring substr(size_t i=0, size_t n=npos) {
    int len = length();
    vstring ts(len);
//    if ( i < 0 ) { n += i; i = 0; } // Ei ole negat i !
    if ( n + i > len ) n = len - i;
    if ( n <= 0 ) return ts;
    strncpy(ts.cstr,cstr+i,n); ts.cstr[n] = 0;
    ts.trimmaa(n);
    return ts;
  }

// Size and capacity ------------------------------------------------------

  size_t size() const                    { return pituus;                    }
  size_t max_size() const                { return size_t(-2);                }
  size_t length() const                  { return pituus;                    }
  bool empty() const                     { return size() == 0;               }
  void resize(size_t n, char c)          {
    size_t old_s = length();
    trimmaa(old_s+n);
    memset(cstr+old_s,c,n);
    cstr[old_s+n] = 0;
  }
  void resize(size_t n)                  { resize(n,0);                      }
  size_t capacity() const                { return maxkoko-1;                 }
  void reserve(size_t res_arg = 0)       { trimmaa(pituus+res_arg);          }


// I/O Operations ---------------------------------------------------------

  friend istream &getline(istream &is,vstring &s,char end);


};


// Comparisons --------------------------------------------------------------

inline int operator==(const char *s1,const vstring &s2) {
  return s2 == s1;
}

inline int operator!=(const char *s1,const vstring &s2) {
  return s2 != s1;
}


inline int operator<(const vstring &s1,const vstring &s2) {
  return s1.compare(s2) < 0;
}

inline int operator>(const vstring &s1,const vstring &s2) {
  return s1.compare(s2) > 0;
}

inline int operator<=(const vstring &s1,const vstring &s2) {
  return s1.compare(s2) <= 0;
}

inline int operator>=(const vstring &s1,const vstring &s2) {
  return s1.compare(s2) >= 0;
}


inline int operator<(const char *s1,const vstring &s2) {
  return s2.compare(s1) > 0;
}

inline int operator>(const char *s1,const vstring &s2) {
  return s2.compare(s1) < 0;
}

inline int operator<=(const char *s1,const vstring &s2) {
  return s2.compare(s1) >= 0;
}

inline int operator>=(const char *s1,const vstring &s2) {
  return s2.compare(s1) <= 0;
}

// Concatenation  -----------------------------------------------------------

inline vstring operator+(const vstring &s1,const vstring &s2) {
  vstring s(s1);
  s += s2;
  return s;
}

inline vstring operator+(const char *s1,const vstring &s2) {
  vstring s(s1);
  s += s2;
  return s;
}

inline vstring operator+(char c, const vstring &s1) {
  vstring s(1,c);
  s += s1;
  return s;
}

inline vstring operator+(const vstring &s1,char c) {
  vstring s(s1);
  s += c;
  return s;
}

// I/O Operations -----------------------------------------------------------

inline ostream &operator<<(ostream &os,const vstring &st) {
  os << st.c_str();
  return os;
}

inline istream &operator>>(istream &is,vstring &st) {
  char s[400];
  is >> s;
  st.assign(s);
  return is;
}

inline istream &getline(istream &is,vstring &s,char end)
{
  vstring as(400,0);
  is.getline(as.cstr,as.maxkoko,end);
  s = as;
  return is;
}

inline istream &getline(istream &is,vstring &s)
{
  return getline(is,s,'\n');
}

// Swap ---------------------------------------------------------------------

inline void swap(string &st1, string &st2) {
  string t(st1);
  st1 = st2;
  st2 = t;
}

#pragma option -w-inl
#pragma warn -inl

#if 0
inline size_t vstring::find_last_of(const char *s,size_t pos) const
{
  if ( pos >= pituus ) pos = pituus-1;
  for (int i=pos; i>=0; i--)
    if ( strchr(s,cstr[i]) != NULL ) return i;
  return npos;
}

inline size_t vstring::find_last_not_of(const char *s,size_t pos) const
{
  if ( pos >= pituus ) pos = pituus-1;
  for (int i=pos; i>=0; i--)
    if ( strchr(s,cstr[i]) == NULL ) return i;
  return npos;
}

//
//     456
// 0123456

inline size_t vstring::rfind(const char *s, size_t i) const
{
  int len = length();
  int slen = strlen(s);
  if ( i >= len-slen ) i=len-slen;
  size_t j;
  for (j=i; j != npos; j--)
    if ( strncmp(cstr+j,s,slen) == 0 ) return j;
  return npos;
}

#endif

#endif // __VSTRING