home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / gnu / g__lib / string.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1993-07-23  |  24.4 KB  |  1,178 lines
  1. /* 
  2. Copyright (C) 1988 Free Software Foundation
  3.     written by Doug Lea (dl@rocky.oswego.edu)
  4.  
  5. This file is part of GNU CC.
  6.  
  7. GNU CC is distributed in the hope that it will be useful,
  8. but WITHOUT ANY WARRANTY.  No author or distributor
  9. accepts responsibility to anyone for the consequences of using it
  10. or for whether it serves any particular purpose or works at all,
  11. unless he says so in writing.  Refer to the GNU CC General Public
  12. License for full details.
  13.  
  14. Everyone is granted permission to copy, modify and redistribute
  15. GNU CC, but only under the conditions described in the
  16. GNU CC General Public License.   A copy of this license is
  17. supposed to have been given to you along with GNU CC so you
  18. can know your rights and responsibilities.  It should be in a
  19. file named COPYING.  Among other things, the copyright notice
  20. and this notice must be preserved on all copies.  
  21. */
  22.  
  23. /* 
  24.   String class implementation
  25.  */
  26.  
  27. #include <String.h>
  28. #include <std.h>
  29. #include <ctype.h>
  30. #include "libconfig.h"
  31.  
  32. extern "C" {
  33. #include <regex.h>
  34. }
  35.  
  36. void String::error(char* msg)
  37. {
  38.   (*lib_error_handler)("String", msg);
  39. }
  40.  
  41. //  globals
  42.  
  43. StrRep  _nilStrRep = { 0, 1, { 0 } }; // nil strings point here
  44. String _nilString;               // nil SubStrings point here
  45.  
  46.  
  47.  
  48.  
  49. /*
  50.  the following inline fcts are specially designed to work
  51.  in support of String classes, and are not meant as generic replacements
  52.  for libc "str" functions.
  53.  
  54.  inline copy fcts -  I like left-to-right from->to arguments.
  55.  all versions assume that `to' argument is non-null
  56. */
  57.  
  58. // copy n bytes
  59. inline static void ncopy(const char* from, char* to, int n)
  60. {
  61.   if (n > 0 && from != to) bcopy((void*)from, (void*) to, n);
  62. }
  63.  
  64. // copy n bytes, null-terminate
  65. inline static void ncopy0(const char* from, char* to, int n)
  66. {
  67.   if (n > 0 && from != to) bcopy((void*)from, (void*) to, n);
  68.   to[n] = 0;
  69. }
  70.  
  71. // copy until null
  72. inline static void scopy(const char* from, char* to)
  73. {
  74.   if (from != 0) while((*to++ = *from++) != 0);
  75. }
  76.  
  77. // copy right-to-left
  78. inline static void revcopy(const char* from, char* to, short n)
  79. {
  80.   if (from != 0) while (n-- > 0) *to-- = *from--;
  81. }
  82.  
  83.  
  84. inline static int slen(const char* t) // inline  strlen
  85. {
  86.   if (t == 0)
  87.     return 0;
  88.   else
  89.   {
  90.     const char* a = t;
  91.     while (*a++ != 0);
  92.     return a - 1 - t;
  93.   }
  94. }
  95.  
  96. // minimum and maximum possible rep sizes
  97. // these are always allocated in blocks of
  98. // a power of 2 minus MALLOC_OVERHEAD, which
  99. // is the least wasteful & fastest size for standard versions of malloc
  100.  
  101. #define MAXStrRep_SIZE   (1 << (SHORTBITS - 1) - 1)
  102. #define MINStrRep_SIZE   16
  103. #define MALLOC_OVERHEAD 4
  104.  
  105. inline static StrRep* Snew(int newsiz)
  106. {
  107.   unsigned int siz = sizeof(StrRep) + newsiz + MALLOC_OVERHEAD;
  108.   unsigned int allocsiz = MINStrRep_SIZE;
  109.   while (allocsiz < siz) allocsiz <<= 1;
  110.   allocsiz -= MALLOC_OVERHEAD;
  111.   if (allocsiz >= MAXStrRep_SIZE)
  112.     (*lib_error_handler)("String", "Requested length out of range");
  113.     
  114.   StrRep* rep = (StrRep *) new char[allocsiz];
  115.   rep->sz = allocsiz - sizeof(StrRep);
  116.   return rep;
  117. }
  118.  
  119. StrRep* Salloc(StrRep* old, const char* src, int srclen, int newlen)
  120. {
  121.   if (old == &_nilStrRep) old = 0;
  122.   if (srclen < 0) srclen = slen(src);
  123.   if (newlen < srclen) newlen = srclen;
  124.   StrRep* rep;
  125.   if (old == 0 || newlen > old->sz)
  126.     rep = Snew(newlen);
  127.   else
  128.     rep = old;
  129.  
  130.   rep->len = newlen;
  131.  
  132.   ncopy0(src, rep->s, srclen);
  133.  
  134.   if (old != rep && old != 0) delete old;
  135.  
  136.   return rep;
  137. }
  138.  
  139. StrRep* Sresize(StrRep* old, int newlen)
  140. {
  141.   if (old == &_nilStrRep) old = 0;
  142.   StrRep* rep;
  143.   if (old == 0)
  144.     rep = Snew(newlen);
  145.   else if (newlen > old->sz)
  146.   {
  147.     rep = Snew(newlen);
  148.     bcopy(old->s, rep->s, old->len);
  149.     delete old;
  150.   }
  151.   else
  152.     rep = old;
  153.  
  154.   rep->len = newlen;
  155.  
  156.   return rep;
  157. }
  158.  
  159. StrRep* Scopy(StrRep* old, StrRep* s)
  160. {
  161.   if (old == &_nilStrRep) old = 0;
  162.   if (s == &_nilStrRep) s = 0;
  163.   if (old == s) 
  164.     return (old == 0)? &_nilStrRep : old;
  165.   else if (s == 0)
  166.   {
  167.     old->s[0] = 0;
  168.     old->len = 0;
  169.     return old;
  170.   }
  171.   else 
  172.   {
  173.     StrRep* rep;
  174.     int newlen = s->len;
  175.     if (old == 0 || newlen > old->sz)
  176.     {
  177.       rep = Snew(newlen);
  178.       if (old != 0) delete old;
  179.     }
  180.     else
  181.       rep = old;
  182.     rep->len = newlen;
  183.     ncopy0(s->s, rep->s, newlen);
  184.     return rep;
  185.   }
  186. }
  187.  
  188. StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen)
  189. {
  190.   if (old == &_nilStrRep) old = 0;
  191.   if (srclen < 0) srclen = slen(s);
  192.   if (tlen < 0) tlen = slen(t);
  193.   int newlen = srclen + tlen;
  194.   StrRep* rep;
  195.   if (old == 0 || newlen > old->sz)
  196.     rep = Snew(newlen);
  197.   else
  198.     rep = old;
  199.  
  200.   rep->len = newlen;
  201.  
  202.   ncopy(s, rep->s, srclen);
  203.   ncopy0(t, &(rep->s[srclen]), tlen);
  204.  
  205.   if (old != rep && old != 0) delete old;
  206.  
  207.   return rep;
  208. }
  209.  
  210. StrRep* Sprepend(StrRep* old, const char* t, int tlen)
  211. {
  212.   char* s;
  213.   int srclen;
  214.   if (old == &_nilStrRep || old == 0)
  215.   {
  216.     s = 0; old = 0; srclen = 0;
  217.   }
  218.   else
  219.   {
  220.     s = old->s; srclen = old->len;
  221.   }
  222.   if (tlen < 0) tlen = slen(t);
  223.   int newlen = srclen + tlen;
  224.   StrRep* rep;
  225.   if (old == 0 || newlen > old->sz || (t >= old->s && t <= old->s+old->len))
  226.     rep = Snew(newlen);
  227.   else
  228.     rep = old;
  229.  
  230.   rep->len = newlen;
  231.  
  232.   revcopy(&(s[srclen]), &(rep->s[newlen]), srclen+1);
  233.   ncopy(t, rep->s, tlen);
  234.  
  235.   if (old != rep && old != 0) delete old;
  236.  
  237.   return rep;
  238. }
  239.  
  240.  
  241. // string compare: first argument is known to be non-null
  242.  
  243. inline static int scmp(const char* a, const char* b)
  244. {
  245.   if (b == 0)
  246.     return *a != 0;
  247.   else
  248.   {
  249.     signed char diff = 0;
  250.     while ((diff = *a - *b++) == 0 && *a++ != 0);
  251.     return diff;
  252.   }
  253. }
  254.  
  255. inline static int ncmp(const char* a, int al, const char* b, int bl)
  256. {
  257.   int n = al <? bl;
  258.   signed char diff;
  259.   while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  260.   return al - bl;
  261. }
  262.  
  263. int fcompare(String& x, String& y)
  264. {
  265.   const char* a = x.rep->s;
  266.   const char* b = y.rep->s;
  267.   int al = x.rep->len;
  268.   int bl = y.rep->len;
  269.   int n = al <? bl;
  270.   signed char diff = 0;
  271.   while (n-- > 0)
  272.   {
  273.     char ac = *a++;
  274.     char bc = *b++;
  275.     if ((diff = ac - bc) != 0)
  276.     {
  277.       if (ac >= 'a' && ac <= 'z')
  278.         ac = ac - 'a' + 'A';
  279.       if (bc >= 'a' && bc <= 'z')
  280.         bc = bc - 'a' + 'A';
  281.       if ((diff = ac - bc) != 0)
  282.         return diff;
  283.     }
  284.   }
  285.   return al - bl;
  286. }
  287.  
  288. // these are not inline, but pull in the above inlines, so are 
  289. // pretty fast
  290.  
  291. int compare(String& x, const char* b)
  292. {
  293.   return scmp(x.rep->s, b);
  294. }
  295.  
  296. int compare(String& x, String& y)
  297. {
  298.   return scmp(x.rep->s, y.rep->s);
  299. }
  300.  
  301. int compare(String& x, SubString& y)
  302. {
  303.   return ncmp(x.rep->s, x.rep->len, &(y.S->rep->s[y.pos]), y.len);
  304. }
  305.  
  306. int compare(SubString& x, String& y)
  307. {
  308.   return ncmp(&(x.S->rep->s[x.pos]), x.len, y.rep->s, y.rep->len);
  309. }
  310.  
  311. int compare(SubString& x, SubString& y)
  312. {
  313.   return ncmp(&(x.S->rep->s[x.pos]), x.len, &(y.S->rep->s[y.pos]), y.len);
  314. }
  315.  
  316. int compare(SubString& x, const char* b)
  317. {
  318.   if (b == 0)
  319.     return x.len;
  320.   else
  321.   {
  322.     const char* a = &(x.S->rep->s[x.pos]);
  323.     int n = x.len;
  324.     signed char diff;
  325.     while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  326.     return (*b == 0) ? 0 : -1;
  327.   }
  328. }
  329.  
  330. /*
  331.  index fcts
  332. */
  333.  
  334. int String::search(int start, int sl, char c)
  335. {
  336.   const char* s = rep->s;
  337.   if (sl > 0)
  338.   {
  339.     if (start >= 0)
  340.     {
  341.       const char* a = &(s[start]);
  342.       const char* lasta = &(s[sl]);
  343.       while (a < lasta) if (*a++ == c) return --a - s;
  344.     }
  345.     else
  346.     {
  347.       const char* a = &(s[sl + start + 1]);
  348.       while (--a >= s) if (*a == c) return a - s;
  349.     }
  350.   }
  351.   return -1;
  352. }
  353.  
  354. int String::search(int start, int sl, const char* t, int tl = -1)
  355. {
  356.   const char* s = rep->s;
  357.   if (tl < 0) tl = slen(t);
  358.   if (sl > 0 && tl > 0)
  359.   {
  360.     if (start >= 0)
  361.     {
  362.       const char* lasts = &(s[sl - tl]);
  363.       const char* lastt = &(t[tl]);
  364.       const char* p = &(s[start]);
  365.  
  366.       while (p <= lasts)
  367.       {
  368.         const char* x = p++;
  369.         const char* y = t;
  370.         while (*x++ == *y++) if (y >= lastt) return --p - s;
  371.       }
  372.     }
  373.     else
  374.     {
  375.       const char* firsts = &(s[tl - 1]);
  376.       const char* lastt =  &(t[tl - 1]);
  377.       const char* p = &(s[sl + start + 1]); 
  378.  
  379.       while (--p >= firsts)
  380.       {
  381.         const char* x = p;
  382.         const char* y = lastt;
  383.         while (*x-- == *y--) if (y < t) return ++x - s;
  384.       }
  385.     }
  386.   }
  387.   return -1;
  388. }
  389.  
  390.  
  391. int String::match(int start, int sl, int exact, const char* t, int tl = -1)
  392. {
  393.   if (tl < 0) tl = slen(t);
  394.  
  395.   if (start < 0)
  396.   {
  397.     start = sl + start - tl + 1;
  398.     if (start < 0 || (exact && start != 0))
  399.       return 0;
  400.   }
  401.   else if (exact && sl - start != tl)
  402.     return 0;
  403.  
  404.   if (sl == 0 || tl == 0 || sl - start < tl || start >= sl)
  405.     return 0;
  406.  
  407.   int n = tl;
  408.   const char* s = &(rep->s[start]);
  409.   while (n-- > 0) if (*s++ != *t++) return 0;
  410.   return tl;
  411. }
  412.  
  413.  
  414.  
  415. void SubString::assign(StrRep* ysrc, const char* ys, int ylen=-1)
  416. {
  417.   if (S == &_nilString) return;
  418.  
  419.   if (ylen < 0) ylen = slen(ys);
  420.   StrRep* targ = S->rep;
  421.   int sl = targ->len - len + ylen;
  422.  
  423.   if (ysrc == targ || sl >= targ->sz)
  424.   {
  425.     StrRep* oldtarg = targ;
  426.     targ = Sresize(0, sl);
  427.     ncopy(oldtarg->s, targ->s, pos);
  428.     ncopy(ys, &(targ->s[pos]), ylen);
  429.     scopy(&(oldtarg->s[pos + len]), &(targ->s[pos + ylen]));
  430.     delete oldtarg;
  431.   }
  432.   else if (len == ylen)
  433.     ncopy(ys, &(targ->s[pos]), len);
  434.   else if (ylen < len)
  435.   {
  436.     ncopy(ys, &(targ->s[pos]), ylen);
  437.     scopy(&(targ->s[pos + len]), &(targ->s[pos + ylen]));
  438.   }
  439.   else
  440.   {
  441.     revcopy(&(targ->s[targ->len]), &(targ->s[sl]), targ->len-pos-len +1);
  442.     ncopy(ys, &(targ->s[pos]), ylen);
  443.   }
  444.   targ->len = sl;
  445.   S->rep = targ;
  446. }
  447.  
  448. // Regex stuff
  449.  
  450. Regex::~Regex()
  451. {
  452.   delete(buf->buffer);
  453.   delete(buf->fastmap);
  454.   delete(buf);
  455.   delete(reg);
  456. }
  457.  
  458. void Regex::initialize(const char* t, int tlen, int fast, int bufsize, 
  459.                        const char* transtable)
  460. {
  461.   if (tlen < 0) tlen = slen(t);
  462.   buf = new re_pattern_buffer;
  463.   reg = new re_registers;
  464.   if (fast)
  465.     buf->fastmap = new char[256];
  466.   else
  467.     buf->fastmap = 0;
  468.   buf->translate = (char*)transtable;
  469.   if (tlen > bufsize)
  470.     bufsize = tlen;
  471.   buf->allocated = bufsize;
  472.   buf->buffer = new char [buf->allocated];
  473.   char* msg = re_compile_pattern((char*)t, tlen, buf);
  474.   if (msg != 0)
  475.     (*lib_error_handler)("Regex", msg);
  476.   else if (fast)
  477.     re_compile_fastmap(buf);
  478. }
  479.  
  480. int Regex::match_info(int& start, int& length, int nth = 0)
  481. {
  482.   if ((unsigned)(nth) >= RE_NREGS)
  483.     return 0;
  484.   else
  485.   {
  486.     start = reg->start[nth];
  487.     length = reg->end[nth] - start;
  488.     return start >= 0 && length >= 0;
  489.   }
  490. }
  491.  
  492. int Regex::search(const char* s, int len, int& matchlen, int startpos = 0)
  493. {
  494.   int matchpos, pos, range;
  495.   if (startpos >= 0)
  496.   {
  497.     pos = startpos;
  498.     range = len - startpos;
  499.   }
  500.   else
  501.   {
  502.     pos = len + startpos;
  503.     range = -pos;
  504.   }
  505.   matchpos = re_search_2(buf, 0, 0, (char*)s, len, pos, range, reg, len);
  506.   if (matchpos >= 0)
  507.     matchlen = reg->end[0] - reg->start[0];
  508.   else
  509.     matchlen = 0;
  510.   return matchpos;
  511. }
  512.  
  513. int Regex::match(const char*s, int len, int p = 0)
  514. {
  515.   if (p < 0)
  516.   {
  517.     p += len;
  518.     if (p >= len)
  519.       return 0;
  520.     return re_match_2(buf, 0, 0, (unsigned char*)s, p, 0, reg, p);
  521.   }
  522.   else if (p >= len)
  523.     return 0;
  524.   else
  525.     return re_match_2(buf, 0, 0, (unsigned char*)s, len, p, reg, len);
  526. }
  527.  
  528.  
  529. /*
  530.  * substitution
  531.  */
  532.  
  533.  
  534. int String::_gsub(const char* pat, int pl, const char* r, int rl)
  535. {
  536.   int nmatches = 0;
  537.   if (pl < 0) pl = slen(pat);
  538.   if (rl < 0) rl = slen(r);
  539.   int sl = rep->len;
  540.   if (sl <= 0 || pl <= 0 || sl < pl)
  541.     return nmatches;
  542.   
  543.   const char* s = rep->s;
  544.  
  545.   StrRep* nrep = Sresize(0, 2 * sl); // guess size
  546.   char* x = nrep->s;
  547.  
  548.   int si = 0;
  549.   int xi = 0;
  550.   int remaining = sl;
  551.  
  552.   while (remaining >= pl)
  553.   {
  554.     int pos = search(si, sl, pat, pl);
  555.     if (pos < 0)
  556.       break;
  557.     else
  558.     {
  559.       ++nmatches;
  560.       int mustfit = xi + remaining + rl - pl;
  561.       if (mustfit >= nrep->sz)
  562.       {
  563.         nrep = Sresize(nrep, mustfit);
  564.         x = nrep->s;
  565.       }
  566.       pos -= si;
  567.       ncopy(&(s[si]), &(x[xi]), pos);
  568.       ncopy(r, &(x[xi + pos]), rl);
  569.       si += pos + pl;
  570.       remaining -= pos + pl;
  571.       xi += pos + rl;
  572.     }
  573.   }
  574.  
  575.   ncopy0(&(s[si]), &(x[xi]), remaining);
  576.   nrep->len = xi + remaining;
  577.  
  578.   if (nrep->len <= rep->sz)   // fit back in if possible
  579.   {
  580.     rep->len = nrep->len;
  581.     ncopy0(nrep->s, rep->s, rep->len);
  582.     delete(nrep);
  583.   }
  584.   else
  585.   {
  586.     delete(rep);
  587.     rep = nrep;
  588.   }
  589.   return nmatches;
  590. }
  591.  
  592. int String::_gsub(Regex& pat, const char* r, int rl)
  593. {
  594.   int nmatches = 0;
  595.   int sl = rep->len;
  596.   if (sl <= 0)
  597.     return nmatches;
  598.  
  599.   if (rl < 0) rl = slen(r);
  600.  
  601.   const char* s = rep->s;
  602.  
  603.   StrRep* nrep = Sresize(0, 2 * sl); // guess size
  604.   char* x = nrep->s;
  605.  
  606.   int si = 0;
  607.   int xi = 0;
  608.   int remaining = sl;
  609.   int  pos, pl = 0;                  // how long is a regular expression?
  610.  
  611.   while (remaining > 0)
  612.   {
  613.     pos = pat.search(s, sl, pl, si); // unlike string search, the pos returned here is absolute
  614.     if (pos < 0 || pl <= 0)
  615.       break;
  616.     else
  617.     {
  618.       ++nmatches;
  619.       int mustfit = xi + remaining + rl - pl;
  620.       if (mustfit >= nrep->sz)
  621.       {
  622.         nrep = Sresize(nrep, mustfit);
  623.         x = nrep->s;
  624.       }
  625.         pos -= si;
  626.       ncopy(&(s[si]), &(x[xi]), pos);
  627.       ncopy(r, &(x[xi + pos]), rl);
  628.       si += pos + pl;
  629.       remaining -= pos + pl;
  630.       xi += pos + rl;
  631.     }
  632.   }
  633.  
  634.   ncopy0(&(s[si]), &(x[xi]), remaining);
  635.   nrep->len = xi + remaining;
  636.  
  637.   if (nrep->len <= rep->sz)   // fit back in if possible
  638.   {
  639.     rep->len = nrep->len;
  640.     ncopy0(nrep->s, rep->s, rep->len);
  641.     delete(nrep);
  642.   }
  643.   else
  644.   {
  645.     delete(rep);
  646.     rep = nrep;
  647.   }
  648.   return nmatches;
  649. }
  650.  
  651.  
  652. /*
  653.  * deletion
  654.  */
  655.  
  656. void String::del(int pos, int len)
  657. {
  658.   if (pos <= 0 || len <= 0 || pos + len > rep->len) return;
  659.   int nlen = rep->len - len;
  660.   int first = pos + len;
  661.   ncopy0(&(rep->s[first]), &(rep->s[pos]), rep->len - first);
  662.   rep->len = nlen;
  663. }
  664.  
  665. void String::del(Regex& r, int startpos = 0)
  666. {
  667.   int mlen;
  668.   int first = r.search(rep->s, rep->len, mlen, startpos);
  669.   del(first, mlen);
  670. }
  671.  
  672. void String::del(const char* t, int startpos = 0)
  673. {
  674.   int tlen = slen(t);
  675.   int p = search(startpos, rep->len, t, tlen);
  676.   del(p, tlen);
  677. }
  678.  
  679. /*
  680.  * substring extraction
  681.  */
  682.  
  683.  
  684. SubString String::at(String& y, int startpos = 0)
  685. {
  686.   int first = search(startpos, rep->len, y.rep->s, y.rep->len);
  687.   return SubString(this, first,  y.rep->len);
  688. }
  689.  
  690. SubString String::at(SubString& y, int startpos = 0)
  691. {
  692.   int first = search(startpos, rep->len, &(y.S->rep->s[y.pos]), y.len);
  693.   return SubString(this, first, y.len);
  694. }
  695.  
  696. SubString String::at(Regex& r, int startpos = 0)
  697. {
  698.   int mlen;
  699.   int first = r.search(rep->s, rep->len, mlen, startpos);
  700.   return SubString(this, first, mlen);
  701. }
  702.  
  703. SubString String::at(const char* t, int startpos = 0)
  704. {
  705.   int tlen = slen(t);
  706.   int first = search(startpos, rep->len, t, tlen);
  707.   return SubString(this, first, tlen);
  708. }
  709.  
  710. SubString String::at(char c, int startpos = 0)
  711. {
  712.   int first = search(startpos, rep->len, c);
  713.   return SubString(this, first, 1);
  714. }
  715.  
  716.  
  717. SubString String::before(String& y, int startpos = 0)
  718. {
  719.   int last = search(startpos, rep->len, y.rep->s, y.rep->len);
  720.   return SubString(this, 0, last);
  721. }
  722.  
  723.  
  724. SubString String::before(SubString& y, int startpos = 0)
  725. {
  726.   int last = search(startpos, rep->len, &(y.S->rep->s[y.pos]), y.len);
  727.   return SubString(this, 0, last);
  728. }
  729.  
  730. SubString String::before(Regex& r, int startpos = 0)
  731. {
  732.   int mlen;
  733.   int first = r.search(rep->s, rep->len, mlen, startpos);
  734.   return SubString(this, 0, first);
  735. }
  736.  
  737. SubString String::before(char c, int startpos = 0)
  738. {
  739.   int last = search(startpos, rep->len, c);
  740.   return SubString(this, 0, last);
  741. }
  742.  
  743. SubString String::before(const char* t, int startpos = 0)
  744. {
  745.   int tlen = slen(t);
  746.   int last = search(startpos, rep->len, t, tlen);
  747.   return SubString(this, 0, last);
  748. }
  749.  
  750.  
  751. SubString String::through(String& y, int startpos = 0)
  752. {
  753.   int last = search(startpos, rep->len, y.rep->s, y.rep->len);
  754.   if (last >= 0) last += y.rep->len;
  755.   return SubString(this, 0, last);
  756. }
  757.  
  758.  
  759. SubString String::through(SubString& y, int startpos = 0)
  760. {
  761.   int last = search(startpos, rep->len, &(y.S->rep->s[y.pos]), y.len);
  762.   if (last >= 0) last += y.len;
  763.   return SubString(this, 0, last);
  764. }
  765.  
  766.  
  767. SubString String::through(Regex& r, int startpos = 0)
  768. {
  769.   int mlen;
  770.   int first = r.search(rep->s, rep->len, mlen, startpos);
  771.   if (first >= 0) first += mlen;
  772.   return SubString(this, 0, first);
  773. }
  774.  
  775. SubString String::through(char c, int startpos = 0)
  776. {
  777.   int last = search(startpos, rep->len, c);
  778.   if (last >= 0) last += 1;
  779.   return SubString(this, 0, last);
  780. }
  781.  
  782. SubString String::through(const char* t, int startpos = 0)
  783. {
  784.   int tlen = slen(t);
  785.   int last = search(startpos, rep->len, t, tlen);
  786.   if (last >= 0) last += tlen;
  787.   return SubString(this, 0, last);
  788. }
  789.  
  790.  
  791. SubString String::after(String& y, int startpos = 0)
  792. {
  793.   int first = search(startpos, rep->len, y.rep->s, y.rep->len);
  794.   if (first >= 0) first += y.rep->len;
  795.   return SubString(this, first, rep->len - first);
  796. }
  797.  
  798. SubString String::after(SubString& y, int startpos = 0)
  799. {
  800.   int first = search(startpos, rep->len, &(y.S->rep->s[y.pos]), y.len);
  801.   if (first >= 0) first += y.len;
  802.   return SubString(this, first, rep->len - first);
  803. }
  804.  
  805. SubString String::after(char c, int startpos = 0)
  806. {
  807.   int first = search(startpos, rep->len, c);
  808.   if (first >= 0) first += 1;
  809.   return SubString(this, first, rep->len - first);
  810. }
  811.  
  812. SubString String::after(Regex& r, int startpos = 0)
  813. {
  814.   int mlen;
  815.   int first = r.search(rep->s, rep->len, mlen, startpos);
  816.   if (first >= 0) first += mlen;
  817.   return SubString(this, first, rep->len - first);
  818. }
  819.  
  820. SubString String::after(const char* t, int startpos = 0)
  821. {
  822.   int tlen = slen(t);
  823.   int first = search(startpos, rep->len, t, tlen);
  824.   if (first >= 0) first += tlen;
  825.   return SubString(this, first, rep->len - first);
  826. }
  827.  
  828. SubString String::from(String& y, int startpos = 0)
  829. {
  830.   int first = search(startpos, rep->len, y.rep->s, y.rep->len);
  831.   return SubString(this, first, rep->len - first);
  832. }
  833.  
  834.  
  835. SubString String::from(SubString& y, int startpos = 0)
  836. {
  837.   int first = search(startpos, rep->len, &(y.S->rep->s[y.pos]), y.len);
  838.   return SubString(this, first, rep->len - first);
  839. }
  840.  
  841. SubString String::from(Regex& r, int startpos = 0)
  842. {
  843.   int mlen;
  844.   int first = r.search(rep->s, rep->len, mlen, startpos);
  845.   return SubString(this, first, rep->len - first);
  846. }
  847.  
  848. SubString String::from(char c, int startpos = 0)
  849. {
  850.   int first = search(startpos, rep->len, c);
  851.   return SubString(this, first, rep->len - first);
  852. }
  853.  
  854. SubString String::from(const char* t, int startpos = 0)
  855. {
  856.   int tlen = slen(t);
  857.   int first = search(startpos, rep->len, t, tlen);
  858.   return SubString(this, first, rep->len - first);
  859. }
  860.  
  861. /*
  862.  * split/join
  863.  */
  864.  
  865.  
  866. int split(String& src, String results[], int n, String& sep)
  867. {
  868.   String x = src;
  869.   const char* s = x.rep->s;
  870.   int sl = x.rep->len;
  871.   int i = 0;
  872.   int pos = 0;
  873.   while (i < n && pos < sl)
  874.   {
  875.     int p = x.search(pos, sl, sep.rep->s, sep.rep->len);
  876.     if (p < 0)
  877.       p = sl;
  878.     results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  879.     i++;
  880.     pos = p + sep.rep->len;
  881.   }
  882.   return(i);
  883. }
  884.  
  885. int split(String& src, String results[], int n, Regex& r)
  886. {
  887.   String x = src;
  888.   char* s = x.rep->s;
  889.   int sl = x.rep->len;
  890.   int i = 0;
  891.   int pos = 0;
  892.   int p, matchlen;
  893.   while (i < n && pos < sl)
  894.   {
  895.     p = r.search(s, sl, matchlen, pos);
  896.     if (p < 0)
  897.       p = sl;
  898.     results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  899.     i++;
  900.     pos = p + matchlen;
  901.   }
  902.   return(i);
  903. }
  904.  
  905.  
  906. StrTmp join(String src[], int n, String& separator)
  907. {
  908.   String sep = separator;
  909.   int xlen = 0;
  910.   for (int i = 0; i < n; ++i)
  911.     xlen += src[i].rep->len;
  912.   xlen += (n - 1) * sep.rep->len;
  913.  
  914.   StrRep* x = Sresize(0, xlen);
  915.  
  916.   int j = 0;
  917.   
  918.   for (i = 0; i < n - 1; ++i)
  919.   {
  920.     ncopy(src[i].rep->s, &(x->s[j]), src[i].rep->len);
  921.     j += src[i].rep->len;
  922.     ncopy(sep.rep->s, &(x->s[j]), sep.rep->len);
  923.     j += sep.rep->len;
  924.   }
  925.   ncopy0(src[i].rep->s, &(x->s[j]), src[i].rep->len);
  926.   return StrTmp(x);
  927. }
  928.  
  929.   
  930. /*
  931.  misc
  932. */
  933.  
  934.     
  935. StrRep* Sreverse(StrRep* src, StrRep* dest)
  936. {
  937.   int n = src->len;
  938.   if (src != dest)
  939.     dest = Salloc(dest, src->s, n, n);
  940.   if (n > 0)
  941.   {
  942.     char* a = dest->s;
  943.     char* b = &(a[n - 1]);
  944.     while (a < b)
  945.     {
  946.       char t = *a;
  947.       *a++ = *b;
  948.       *b-- = t;
  949.     }
  950.   }
  951.   return dest;
  952. }
  953.  
  954.  
  955. StrRep* Supcase(StrRep* src, StrRep* dest)
  956. {
  957.   int n = src->len;
  958.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  959.   char* p = dest->s;
  960.   char* e = &(p[n]);
  961.   for (; p < e; ++p) if (islower(*p)) *p = toupper(*p);
  962.   return dest;
  963. }
  964.  
  965. StrRep* Sdowncase(StrRep* src, StrRep* dest)
  966. {
  967.   int n = src->len;
  968.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  969.   char* p = dest->s;
  970.   char* e = &(p[n]);
  971.   for (; p < e; ++p) if (isupper(*p)) *p = tolower(*p);
  972.   return dest;
  973. }
  974.  
  975. StrRep* Scapitalize(StrRep* src, StrRep* dest)
  976. {
  977.   int n = src->len;
  978.   if (src != dest) dest = Salloc(dest, src->s, n, n);
  979.  
  980.   char* p = dest->s;
  981.   char* e = &(p[n]);
  982.   for (; p < e; ++p)
  983.   {
  984.     int at_word;
  985.     if (at_word = islower(*p))
  986.       *p = toupper(*p);
  987.     else 
  988.       at_word = isupper(*p) || isdigit(*p);
  989.  
  990.     if (at_word)
  991.     {
  992.       while (++p < e)
  993.       {
  994.         if (isupper(*p))
  995.           *p = tolower(*p);
  996.         else if (!islower(*p) && !isdigit(*p))
  997.           break;
  998.       }
  999.     }
  1000.   }
  1001.   return dest;
  1002. }
  1003.  
  1004. StrTmp replicate(char c, int n)
  1005. {
  1006.   StrRep* w = Sresize(0, n);
  1007.   char* p = w->s;
  1008.   while (n-- > 0) *p++ = c;
  1009.   *p = 0;
  1010.   return (w);
  1011. }
  1012.  
  1013. StrTmp replicate(String& y, int n)
  1014. {
  1015.   int len = y.rep->len;
  1016.   StrRep* w = Sresize(0, n * len);
  1017.   char* p = w->s;
  1018.   while (n-- > 0)
  1019.   {
  1020.     ncopy(y.rep->s, p, len);
  1021.     p += len;
  1022.   }
  1023.   *p = 0;
  1024.   return (w);
  1025. }
  1026.  
  1027. StrTmp common_prefix(String& x, String& y, int startpos = 0)
  1028. {
  1029.   const char* xs = &(x.rep->s[startpos]);
  1030.   const char* ss = xs;
  1031.   const char* topx = &(x.rep->s[x.rep->len]);
  1032.   const char* ys = &(y.rep->s[startpos]);
  1033.   const char* topy = &(y.rep->s[y.rep->len]);
  1034.   for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1035.   return StrTmp(Salloc(0, ss, l, l));
  1036. }
  1037.  
  1038.  
  1039. StrTmp common_suffix(String& x, String& y, int startpos = -1)
  1040. {
  1041.   const char* xs = &(x.rep->s[x.rep->len + startpos]);
  1042.   const char* botx = x.rep->s;
  1043.   const char* ys = &(y.rep->s[y.rep->len + startpos]);
  1044.   const char* boty = y.rep->s;
  1045.   for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1046.   return StrTmp(Salloc(0, ++xs, l, l));
  1047. }
  1048.  
  1049. // IO
  1050.  
  1051. istream& operator>>(istream& s, String& x)
  1052. {
  1053.   char ch;
  1054.   int i = 0;
  1055.   x.rep = Sresize(x.rep, 20);
  1056.   s >> WS;
  1057.   while (s.good())
  1058.   {
  1059.     s.get(ch);
  1060.     if (isspace(ch))
  1061.       break;
  1062.     if (i >= x.rep->sz - 1)
  1063.       x.rep = Sresize(x.rep, i+1);
  1064.     x.rep->s[i++] = ch;
  1065.   }
  1066.   x.rep->s[i] = 0;
  1067.   x.rep->len = i;
  1068.   s.failif(i == 0);
  1069.   return s;
  1070. }
  1071.  
  1072. int readline(istream& s, String& x, char terminator = '\n', int discard = 1)
  1073. {
  1074.   char ch;
  1075.   int i = 0;
  1076.   x.rep = Sresize(x.rep, 80);
  1077.   while (s.good())
  1078.   {
  1079.     s.get(ch);
  1080.     if (ch != terminator || !discard)
  1081.     {
  1082.       if (i >= x.rep->sz - 1)
  1083.         x.rep = Sresize(x.rep, i+1);
  1084.       x.rep->s[i++] = ch;
  1085.     }
  1086.     if (ch == terminator)
  1087.       break;
  1088.   }
  1089.   x.rep->s[i] = 0;
  1090.   x.rep->len = i;
  1091.   return i;
  1092. }
  1093.  
  1094.  
  1095. ostream& operator<<(ostream& s, SubString& x)
  1096. { 
  1097.   const char* a = &(x.S->rep->s[x.pos]);
  1098.   const char* lasta = &(a[x.len]);
  1099.   while (a < lasta)
  1100.     s.put(*a++);
  1101.   return(s);
  1102. }
  1103.  
  1104. // from John.Willis@FAS.RI.CMU.EDU
  1105.  
  1106. int String::freq(SubString& y)
  1107. {
  1108.   int found = 0;
  1109.   for (int i = 0; i < rep->len; i++) 
  1110.     if (match(i,rep->len,0,&(y.S->rep->s[y.pos]), y.len)) found++;
  1111.   return(found);
  1112. }
  1113.  
  1114. int String::freq(String& y)
  1115. {
  1116.   int found = 0;
  1117.   for (int i = 0; i < rep->len; i++) 
  1118.     if (match(i,rep->len,0,y.rep->s,y.rep->len)) found++;
  1119.   return(found);
  1120. }
  1121.  
  1122. int String::freq(const char* t)
  1123. {
  1124.   int found = 0;
  1125.   for (int i = 0; i < rep->len; i++) if (match(i,rep->len,0,t)) found++;
  1126.   return(found);
  1127. }
  1128.  
  1129. int String::freq(char c)
  1130. {
  1131.   int found = 0;
  1132.   for (int i = 0; i < rep->len; i++) 
  1133.     if (match(i,rep->len,0,&c,1)) found++;
  1134.   return(found);
  1135. }
  1136.  
  1137.  
  1138. int String::OK()
  1139. {
  1140.   int v = rep != 0;             // have a rep
  1141.   v &= rep->len <= rep->sz;     // string within bounds
  1142.   v &= rep->s[rep->len] == 0;   // null-terminated
  1143.   if (!v) error("invariant failure");
  1144.   return v;
  1145. }
  1146.  
  1147. int SubString::OK()
  1148. {
  1149.   int v = S != 0;               // have a String;
  1150.   v &= S->OK();                 // that is legal
  1151.   v &= pos + len >= S->rep->len;// pos and len within bounds
  1152.   if (!v) S->error("SubString invariant failure");
  1153.   return v;
  1154. }
  1155.  
  1156. int Regex::OK()
  1157. {
  1158. // can't verify much, since we've lost the original string
  1159.   int v = buf != 0;             // have a regex buf
  1160.   v &= buf->buffer != 0;        // with a pat
  1161.   if (!v) (*lib_error_handler)("Regex", "invariant failure");
  1162.   return v;
  1163. }
  1164.  
  1165. /*
  1166.  some built-in Regular expressions
  1167. */
  1168.  
  1169. Regex RXwhite("[ \n\t]+", 1);
  1170. Regex RXint("-?[0-9]+", 1);
  1171. Regex RXdouble("-?\\(\\([0-9]+\\.[0-9]*\\)\\|\\([0-9]+\\)\\|\\(\\.[0-9]+\\)\\)\\([eE][---+]?[0-9]+\\)?", 1, 200);
  1172. Regex RXalpha("[A-Za-z]+", 1);
  1173. Regex RXlowercase("[a-z]+", 1);
  1174. Regex RXuppercase("[A-Z]+", 1);
  1175. Regex RXalphanum("[0-9A-Za-z]+", 1);
  1176. Regex RXidentifier("[A-Za-z_][A-Za-z0-9_]*", 1);
  1177.  
  1178.