home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / strclass.C < prev    next >
C/C++ Source or Header  |  1998-09-22  |  31KB  |  1,435 lines
  1. // $Id: strclass.C,v 1.20 1998/09/22 11:31:33 zeller Exp $ -*- C++ -*-
  2. // The libg++ String class, but named "string" for coexistence with Xt
  3.  
  4. /* 
  5. Copyright (C) 1988 Free Software Foundation
  6.     written by Doug Lea (dl@rocky.oswego.edu)
  7.  
  8. This file is part of the GNU C++ Library.  This library is free
  9. software; you can redistribute it and/or modify it under the terms of
  10. the GNU Library General Public License as published by the Free
  11. Software Foundation; either version 2 of the License, or (at your
  12. option) any later version.  This library is distributed in the hope
  13. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  14. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15. PURPOSE.  See the GNU Library General Public License for more details.
  16. You should have received a copy of the GNU Library General Public
  17. License along with this library; if not, write to the Free Software
  18. Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19. */
  20.  
  21. char strclass_rcsid[] = 
  22.     "$Id: strclass.C,v 1.20 1998/09/22 11:31:33 zeller Exp $";
  23.  
  24. /* 
  25.   string class implementation
  26.  */
  27.  
  28. #ifdef __GNUG__
  29. #pragma implementation
  30. #endif
  31.  
  32. #ifndef MALLOC_DEBUG
  33. #define MALLOC_DEBUG 0
  34. #endif
  35.  
  36. #if MALLOC_DEBUG
  37. extern "C" int malloc_verify();
  38. #include "assert.h"
  39. #endif
  40.  
  41. #include "strclass.h"
  42. #include "config.h"
  43. #include "return.h"
  44. #include <ctype.h>
  45. #include <limits.h>
  46. #include <new.h>
  47. #include <stdlib.h>
  48.  
  49. #if HAVE_LIMITS_H
  50. #include <limits.h>
  51. #endif
  52.  
  53. void string::error(const char* msg) const
  54. {
  55.     cerr << "string: " << msg << "\n";
  56.     abort();
  57. }
  58.  
  59. string::operator const char*() const
  60. { 
  61.     return (const char *)chars();
  62. }
  63.  
  64. string::operator char*() const
  65. { 
  66.     return (char *)chars();
  67. }
  68.  
  69. //  globals
  70.  
  71. // nil strings point here
  72. strRep _nilstrRep = { 0, 1, &(_nilstrRep.mem[0]), { '\0' } };
  73.  
  74. // nil subStrings point here
  75. string _nilstring;
  76.  
  77.  
  78.  
  79.  
  80. /*
  81.  the following inline fcts are specially designed to work
  82.  in support of string classes, and are not meant as generic replacements
  83.  for libc "str" functions.
  84.  
  85.  inline copy fcts -  I like left-to-right from->to arguments.
  86.  all versions assume that `to' argument is non-null
  87.  
  88.  These are worth doing inline, rather than through calls because,
  89.  via procedural integration, adjacent copy calls can be smushed
  90.  together by the optimizer.
  91. */
  92.  
  93. // copy n bytes
  94. inline static void ncopy(const char* from, char* to, int n)
  95. {
  96.     if (from != to) while (--n >= 0) *to++ = *from++;
  97. }
  98.  
  99. // copy n bytes, null-terminate
  100. inline static void ncopy0(const char* from, char* to, int n)
  101. {
  102.     if (from != to) 
  103.     {
  104.     while (--n >= 0) *to++ = *from++;
  105.     *to = 0;
  106.     }
  107.     else
  108.     to[n] = 0;
  109. }
  110.  
  111. // copy until null
  112. inline static void scopy(const char* from, char* to)
  113. {
  114.     if (from != 0) while((*to++ = *from++) != 0);
  115. }
  116.  
  117. // copy right-to-left
  118. inline static void revcopy(const char* from, char* to, int n)
  119. {
  120.     if (from != 0) while (--n >= 0) *to-- = *from--;
  121. }
  122.  
  123.  
  124. inline static int slen(const char* t) // inline  strlen
  125. {
  126.     if (t == 0)
  127.     return 0;
  128.     else
  129.     {
  130.     const char* a = t;
  131.     while (*a++ != 0);
  132.     return a - 1 - t;
  133.     }
  134. }
  135.  
  136.  
  137.  
  138. // The remaining size for the current string in REP
  139. inline unsigned int string_Sremainder(strRep *rep)
  140. {
  141.     return rep->allocated - (rep->s - &(rep->mem[0]));
  142. }
  143.  
  144.  
  145. // minimum & maximum representable rep size
  146.  
  147. #if 0
  148. const unsigned long MAX_STRREP_SIZE = (1 << (sizeof(int) * CHAR_BIT - 1)) - 1;
  149. #endif
  150.  
  151. const unsigned long MIN_STRREP_SIZE = 16;
  152.  
  153. #ifndef MALLOC_MIN_OVERHEAD
  154. #define MALLOC_MIN_OVERHEAD  4
  155. #endif
  156.  
  157. // The basic allocation primitive:
  158. // Always round request to something close to a power of two.
  159. // This ensures a bit of padding, which often means that
  160. // concatenations don't have to realloc. Plus it tends to
  161. // be faster when lots of Strings are created and discarded,
  162. // since just about any version of malloc (op new()) will
  163. // be faster when it can reuse identically-sized chunks
  164.  
  165. inline static strRep* string_Snew(int newsiz)
  166. {
  167.     unsigned int siz = sizeof(strRep) + newsiz + MALLOC_MIN_OVERHEAD;
  168.     unsigned int allocsiz = MIN_STRREP_SIZE;
  169.     while (allocsiz < siz) allocsiz <<= 1;
  170.     allocsiz -= MALLOC_MIN_OVERHEAD;
  171.  
  172. #if 0
  173.     if ((unsigned long)allocsiz >= MAX_STRREP_SIZE)
  174.     {
  175.     cerr << "string: requested length out of range\n";
  176.     abort();
  177.     }
  178. #endif
  179.  
  180. #if HAVE_PLACEMENT_NEW
  181.     strRep* rep = new (operator new (allocsiz)) strRep;
  182. #else
  183.     strRep* rep = (strRep *) new char[allocsiz];
  184. #endif
  185.     rep->allocated = allocsiz - sizeof(strRep);
  186.     rep->s  = &rep->mem[0];
  187.     return rep;
  188. }
  189.  
  190. // Do-something-while-allocating routines.
  191.  
  192. // We live with two ways to signify empty Sreps: either the
  193. // null pointer (0) or a pointer to the nilstrRep.
  194.  
  195. // We always signify unknown source lengths (usually when fed a char*)
  196. // via len == -1, in which case it is computed.
  197.  
  198. // allocate, copying src if nonull
  199.  
  200. strRep* string_Salloc(strRep* old, const char* src, int srclen, int newlen)
  201. {
  202. #if MALLOC_DEBUG
  203.     assert(malloc_verify());
  204. #endif
  205.  
  206.     if (old == &_nilstrRep) old = 0;
  207.     if (srclen < 0) srclen = slen(src);
  208.     if (newlen < srclen) newlen = srclen;
  209.     strRep* rep;
  210.     if (old == 0 || unsigned(newlen) > old->allocated)
  211.     rep = string_Snew(newlen);
  212.     else
  213.     rep = old;
  214.  
  215.     rep->len = newlen;
  216.     rep->s   = &(rep->mem[0]);
  217.     ncopy0(src, rep->s, srclen);
  218.  
  219.     if (old != rep && old != 0)
  220.     string_DeleteRep(old);
  221.  
  222.     return rep;
  223. }
  224.  
  225. // reallocate: Given the initial allocation scheme, it will
  226. // generally be faster in the long run to get new space & copy
  227. // than to call realloc
  228.  
  229. static strRep *string_Sresize(strRep* old, int newlen)
  230. {
  231. #if MALLOC_DEBUG
  232.     assert(malloc_verify());
  233. #endif
  234.  
  235.     if (old == &_nilstrRep) old = 0;
  236.     strRep* rep;
  237.     if (old == 0)
  238.     rep = string_Snew(newlen);
  239.     else if (unsigned(newlen) > old->allocated)
  240.     {
  241.     rep = string_Snew(newlen);
  242.     ncopy0(old->s, rep->s, old->len);
  243.     string_DeleteRep(old);
  244.     }
  245.     else
  246.     rep = old;
  247.  
  248.     rep->len = newlen;
  249.  
  250.     return rep;
  251. }
  252.  
  253. void string::alloc (int newsize)
  254. {
  255.     unsigned short old_len = rep->len;
  256.     rep = string_Sresize(rep, newsize);
  257.     rep->len = old_len;
  258. }
  259.  
  260.  
  261. // like allocate, but we know that src is a strRep
  262.  
  263. strRep* string_Scopy(strRep* old, strRep* s)
  264. {
  265. #if MALLOC_DEBUG
  266.     assert(malloc_verify());
  267. #endif
  268.  
  269.     if (old == &_nilstrRep) old = 0;
  270.     if (s == &_nilstrRep) s = 0;
  271.     if (old == s) 
  272.     return (old == 0)? &_nilstrRep : old;
  273.     else if (s == 0)
  274.     {
  275.     old->s[0] = 0;
  276.     old->len = 0;
  277.     return old;
  278.     }
  279.     else 
  280.     {
  281.     strRep* rep;
  282.     unsigned newlen = s->len;
  283.     if (old == 0 || newlen > old->allocated)
  284.     {
  285.         if (old != 0) 
  286.         string_DeleteRep(old);
  287.         rep = string_Snew(newlen);
  288.     }
  289.     else
  290.         rep = old;
  291.  
  292.     rep->len = newlen;
  293.     rep->s = &(rep->mem[0]);
  294.     ncopy0(s->s, rep->s, newlen);
  295.     return rep;
  296.     }
  297. }
  298.  
  299. // allocate & concatenate
  300.  
  301. strRep* string_Scat(strRep* old, 
  302.             const char* s, 
  303.             int srclen, 
  304.             const char* t, 
  305.             int tlen)
  306. {
  307. #if MALLOC_DEBUG
  308.     assert(malloc_verify());
  309. #endif
  310.  
  311.     if (old == &_nilstrRep) old = 0;
  312.     if (srclen < 0) srclen = slen(s);
  313.     if (tlen < 0) tlen = slen(t);
  314.     unsigned newlen = srclen + tlen;
  315.     strRep* rep;
  316.  
  317.     if (old == 0 || newlen > old->allocated || 
  318.     (t >= old->s && t < &(old->s[old->len]))) // beware of aliasing
  319.     rep = string_Snew(newlen);
  320.     else
  321.     rep = old;
  322.  
  323.     rep->len = newlen;
  324.     rep->s = &(rep->mem[0]);
  325.  
  326.     ncopy(s, rep->s, srclen);
  327.     ncopy0(t, &(rep->s[srclen]), tlen);
  328.  
  329.     if (old != rep && old != 0)
  330.     string_DeleteRep(old);
  331.  
  332.     return rep;
  333. }
  334.  
  335. // double-concatenate
  336.  
  337. strRep* string_Scat(strRep* old, const char* s, int srclen, 
  338.             const char* t, int tlen,
  339.             const char* u, int ulen)
  340. {
  341. #if MALLOC_DEBUG
  342.     assert(malloc_verify());
  343. #endif
  344.  
  345.     if (old == &_nilstrRep) old = 0;
  346.     if (srclen < 0) srclen = slen(s);
  347.     if (tlen < 0) tlen = slen(t);
  348.     if (ulen < 0) ulen = slen(u);
  349.     unsigned newlen = srclen + tlen + ulen;
  350.     strRep* rep;
  351.     if (old == 0 || newlen > old->allocated || 
  352.     (t >= old->s && t < &(old->s[old->len])) ||
  353.     (u >= old->s && u < &(old->s[old->len])))
  354.     rep = string_Snew(newlen);
  355.     else
  356.     rep = old;
  357.  
  358.     rep->len = newlen;
  359.     rep->s = &(rep->mem[0]);
  360.  
  361.     ncopy(s, rep->s, srclen);
  362.     ncopy(t, &(rep->s[srclen]), tlen);
  363.     ncopy0(u, &(rep->s[srclen+tlen]), ulen);
  364.  
  365.     if (old != rep && old != 0)
  366.     string_DeleteRep(old);
  367.  
  368.     return rep;
  369. }
  370.  
  371. // like cat, but we know that new stuff goes in the front of existing rep
  372.  
  373. strRep* string_Sprepend(strRep* old, const char* t, int tlen)
  374. {
  375. #if MALLOC_DEBUG
  376.     assert(malloc_verify());
  377. #endif
  378.  
  379.     char* s;
  380.     int srclen;
  381.     if (old == &_nilstrRep || old == 0)
  382.     {
  383.     s = 0; old = 0; srclen = 0;
  384.     }
  385.     else
  386.     {
  387.     s = old->s; srclen = old->len;
  388.     }
  389.     if (tlen < 0) tlen = slen(t);
  390.     unsigned newlen = srclen + tlen;
  391.     strRep* rep;
  392.     if (old == 0 || newlen > string_Sremainder(old) || 
  393.     (t >= old->s && t < &(old->s[old->len])))
  394.     rep = string_Snew(newlen);
  395.     else
  396.     rep = old;
  397.  
  398.     rep->len = newlen;
  399.  
  400.     revcopy(&(s[srclen]), &(rep->s[newlen]), srclen+1);
  401.     ncopy(t, rep->s, tlen);
  402.  
  403.     if (old != rep && old != 0)
  404.     string_DeleteRep(old);
  405.  
  406.     return rep;
  407. }
  408.  
  409.  
  410. // string compare: first argument is known to be non-null
  411.  
  412. inline static int scmp(const char* a, const char* b)
  413. {
  414.     if (b == 0)
  415.     return *a != 0;
  416.     else
  417.     {
  418.     signed char diff = 0;
  419.     while ((diff = *a - *b++) == 0 && *a++ != 0);
  420.     return diff;
  421.     }
  422. }
  423.  
  424.  
  425. inline static int ncmp(const char* a, int al, const char* b, int bl)
  426. {
  427.     int n = (al <= bl)? al : bl;
  428.     signed char diff;
  429.     while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
  430.     return al - bl;
  431. }
  432.  
  433. int fcompare(const string& x, const string& y)
  434. {
  435.     const char* a = x.chars();
  436.     const char* b = y.chars();
  437.     int al = x.length();
  438.     int bl = y.length();
  439.     int n = (al <= bl)? al : bl;
  440.     signed char diff = 0;
  441.     while (n-- > 0)
  442.     {
  443.     char ac = *a++;
  444.     char bc = *b++;
  445.     if ((diff = ac - bc) != 0)
  446.     {
  447.         if (ac >= 'a' && ac <= 'z')
  448.         ac = ac - 'a' + 'A';
  449.         if (bc >= 'a' && bc <= 'z')
  450.         bc = bc - 'a' + 'A';
  451.         if ((diff = ac - bc) != 0)
  452.         return diff;
  453.     }
  454.     }
  455.     return al - bl;
  456. }
  457.  
  458. // these are not inline, but pull in the above inlines, so are 
  459. // pretty fast
  460.  
  461. int compare(const string& x, const char* b)
  462. {
  463.     return scmp(x.chars(), b);
  464. }
  465.  
  466. int compare(const char *x, const string& y)
  467. {
  468.     return scmp(x, y.chars());
  469. }
  470.  
  471. int compare(const string& x, const string& y)
  472. {
  473.     return scmp(x.chars(), y.chars());
  474. }
  475.  
  476. int compare(const string& x, const subString& y)
  477. {
  478.     return ncmp(x.chars(), x.length(), y.chars(), y.length());
  479. }
  480.  
  481. int compare(const subString& x, const string& y)
  482. {
  483.     return ncmp(x.chars(), x.length(), y.chars(), y.length());
  484. }
  485.  
  486. int compare(const subString& x, const subString& y)
  487. {
  488.     return ncmp(x.chars(), x.length(), y.chars(), y.length());
  489. }
  490.  
  491. int compare(const subString& x, const char* y)
  492. {
  493.     if (y == 0)
  494.     return x.length();
  495.     else
  496.     {
  497.     const char* a = x.chars();
  498.     int n = x.length();
  499.     signed char diff;
  500.     while (n-- > 0) if ((diff = *a++ - *y++) != 0) return diff;
  501.     return (*y == 0) ? 0 : -1;
  502.     }
  503. }
  504.  
  505. int compare(const char *x, const subString& y)
  506. {
  507.     if (x == 0)
  508.     return y.length();
  509.     else
  510.     {
  511.     const char* a = y.chars();
  512.     int n = y.length();
  513.     signed char diff;
  514.     while (n-- > 0) if ((diff = *x++ - *a++) != 0) return diff;
  515.     return (*x == 0) ? 0 : -1;
  516.     }
  517. }
  518.  
  519.  
  520. /*
  521.  index fcts
  522. */
  523.  
  524. int string::search(int start, int sl, char c) const
  525. {
  526.     const char* s = chars();
  527.     if (sl > 0)
  528.     {
  529.     if (start >= 0)
  530.     {
  531.         const char* a = &(s[start]);
  532.         const char* lasta = &(s[sl]);
  533.         while (a < lasta) if (*a++ == c) return --a - s;
  534.     }
  535.     else
  536.     {
  537.         const char* a = &(s[sl + start + 1]);
  538.         while (--a >= s) if (*a == c) return a - s;
  539.     }
  540.     }
  541.     return -1;
  542. }
  543.  
  544. int string::search(int start, int sl, const char* t, int tl) const
  545. {
  546.     const char* s = chars();
  547.     if (tl < 0) tl = slen(t);
  548.     if (sl > 0 && tl > 0)
  549.     {
  550.     if (start >= 0)
  551.     {
  552.         const char* lasts = &(s[sl - tl]);
  553.         const char* lastt = &(t[tl]);
  554.         const char* p = &(s[start]);
  555.  
  556.         while (p <= lasts)
  557.         {
  558.         const char* x = p++;
  559.         const char* y = t;
  560.         while (*x++ == *y++) if (y >= lastt) return --p - s;
  561.         }
  562.     }
  563.     else
  564.     {
  565.         const char* firsts = &(s[tl - 1]);
  566.         const char* lastt =  &(t[tl - 1]);
  567.         const char* p = &(s[sl + start + 1]); 
  568.  
  569.         while (--p >= firsts)
  570.         {
  571.         const char* x = p;
  572.         const char* y = lastt;
  573.         while (*x-- == *y--) if (y < t) return ++x - s;
  574.         }
  575.     }
  576.     }
  577.     return -1;
  578. }
  579.  
  580. int string::match(int start, int sl, int exact, const char* t, int tl) const
  581. {
  582.     if (tl < 0) tl = slen(t);
  583.  
  584.     if (start < 0)
  585.     {
  586.     start = sl + start - tl + 1;
  587.     if (start < 0 || (exact && start != 0))
  588.         return -1;
  589.     }
  590.     else if (exact && sl - start != tl)
  591.     return -1;
  592.  
  593.     if (sl == 0 || tl == 0 || sl - start < tl || start >= sl)
  594.     return -1;
  595.  
  596.     int n = tl;
  597.     const char* s = &(rep->s[start]);
  598.     while (--n >= 0) if (*s++ != *t++) return -1;
  599.     return tl;
  600. }
  601.  
  602. void subString::assign(strRep* ysrc, const char* ys, int ylen)
  603. {
  604.     if (&S == &_nilstring) return;
  605.  
  606.     assert(!S.consuming());
  607.  
  608.     if (ylen < 0) ylen = slen(ys);
  609.     strRep* targ = S.rep;
  610.     unsigned sl = targ->len - len + ylen;
  611.  
  612.     if (ysrc == targ || sl >= string_Sremainder(targ))
  613.     {
  614.     strRep* oldtarg = targ;
  615.     targ = string_Sresize(0, sl);
  616.     ncopy(oldtarg->s, targ->s, pos);
  617.     ncopy(ys, &(targ->s[pos]), ylen);
  618.     scopy(&(oldtarg->s[pos + len]), &(targ->s[pos + ylen]));
  619.     string_DeleteRep(oldtarg);
  620.     }
  621.     else if (len == unsigned(ylen))
  622.     ncopy(ys, &(targ->s[pos]), len);
  623.     else if (unsigned(ylen) < len)
  624.     {
  625.     ncopy(ys, &(targ->s[pos]), ylen);
  626.     scopy(&(targ->s[pos + len]), &(targ->s[pos + ylen]));
  627.     }
  628.     else
  629.     {
  630.     revcopy(&(targ->s[targ->len]), &(targ->s[sl]), targ->len-pos-len +1);
  631.     ncopy(ys, &(targ->s[pos]), ylen);
  632.     }
  633.     targ->len = sl;
  634.     S.rep = targ;
  635. }
  636.  
  637.  
  638.  
  639. /*
  640.  * substitution
  641.  */
  642.  
  643.  
  644. int string::_gsub(const char* pat, int pl, const char* r, int rl)
  645. {
  646.     assert(!consuming());
  647.  
  648.     int nmatches = 0;
  649.     if (pl < 0) pl = slen(pat);
  650.     if (rl < 0) rl = slen(r);
  651.     int sl = length();
  652.     if (sl <= 0 || pl <= 0 || sl < pl)
  653.     return nmatches;
  654.   
  655.     const char* s = chars();
  656.  
  657.     // prepare to make new rep
  658.     strRep* nrep = 0;
  659.     int nsz = 0;
  660.     char* x = 0;
  661.  
  662.     int si = 0;
  663.     int xi = 0;
  664.     int remaining = sl;
  665.  
  666.     while (remaining >= pl)
  667.     {
  668.     int pos = search(si, sl, pat, pl);
  669.     if (pos < 0)
  670.         break;
  671.     else
  672.     {
  673.         ++nmatches;
  674.         int mustfit = xi + remaining + rl - pl;
  675.         if (mustfit >= nsz)
  676.         {
  677.         if (nrep != 0) nrep->len = xi;
  678.         nrep = string_Sresize(nrep, mustfit);
  679.         nsz = string_Sremainder(nrep);
  680.         x = nrep->s;
  681.         }
  682.         pos -= si;
  683.         ncopy(&(s[si]), &(x[xi]), pos);
  684.         ncopy(r, &(x[xi + pos]), rl);
  685.         si += pos + pl;
  686.         remaining -= pos + pl;
  687.         xi += pos + rl;
  688.     }
  689.     }
  690.  
  691.     if (nrep == 0)
  692.     {
  693.     if (nmatches == 0)
  694.         return nmatches;
  695.     else
  696.         nrep = string_Sresize(nrep, xi+remaining);
  697.     }
  698.  
  699.     ncopy0(&(s[si]), &(x[xi]), remaining);
  700.     nrep->len = xi + remaining;
  701.  
  702.     if (nrep->len <= rep->allocated)   // fit back in if possible
  703.     {
  704.     rep->len = nrep->len;
  705.     rep->s = &(rep->mem[0]);
  706.     ncopy0(nrep->s, rep->s, rep->len);
  707.     string_DeleteRep(nrep);
  708.     }
  709.     else
  710.     {
  711.     string_DeleteRep(rep);
  712.     rep = nrep;
  713.     }
  714.     return nmatches;
  715. }
  716.  
  717. int string::_gsub(const regex& pat, const char* r, int rl)
  718. {
  719.     assert(!consuming());
  720.  
  721.     int nmatches = 0;
  722.     int sl = length();
  723.     if (sl <= 0)
  724.     return nmatches;
  725.  
  726.     if (rl < 0) rl = slen(r);
  727.  
  728.     const char* s = chars();
  729.  
  730.     strRep* nrep = 0;
  731.     int nsz = 0;
  732.  
  733.     char* x = 0;
  734.  
  735.     int si = 0;
  736.     int xi = 0;
  737.     int remaining = sl;
  738.     int  pos, pl = 0;        // how long is a regular expression?
  739.  
  740.     while (remaining > 0)
  741.     {
  742.     // unlike string search, the pos returned here is absolute
  743.     pos = pat.search(s, sl, pl, si);
  744.     if (pos < 0 || pl <= 0)
  745.         break;
  746.     else
  747.     {
  748.         ++nmatches;
  749.         int mustfit = xi + remaining + rl - pl;
  750.         if (mustfit >= nsz)
  751.         {
  752.         if (nrep != 0) nrep->len = xi;
  753.         nrep = string_Sresize(nrep, mustfit);
  754.         x = nrep->s;
  755.         nsz = string_Sremainder(nrep);
  756.         }
  757.         pos -= si;
  758.         ncopy(&(s[si]), &(x[xi]), pos);
  759.         ncopy(r, &(x[xi + pos]), rl);
  760.         si += pos + pl;
  761.         remaining -= pos + pl;
  762.         xi += pos + rl;
  763.     }
  764.     }
  765.  
  766.     if (nrep == 0)
  767.     {
  768.     if (nmatches == 0)
  769.         return nmatches;
  770.     else
  771.         nrep = string_Sresize(nrep, xi+remaining);
  772.     }
  773.  
  774.     ncopy0(&(s[si]), &(x[xi]), remaining);
  775.     nrep->len = xi + remaining;
  776.  
  777.     if (nrep->len <= rep->allocated)   // fit back in if possible
  778.     {
  779.     rep->len = nrep->len;
  780.     rep->s = &(rep->mem[0]);
  781.     ncopy0(nrep->s, rep->s, rep->len);
  782.     string_DeleteRep(nrep);
  783.     }
  784.     else
  785.     {
  786.     string_DeleteRep(rep);
  787.     rep = nrep;
  788.     }
  789.     return nmatches;
  790. }
  791.  
  792.  
  793. /*
  794.  * deletion
  795.  */
  796.  
  797. void string::del(int pos, int len)
  798. {
  799.     assert(!consuming());
  800.  
  801.     if (pos < 0 || len <= 0 || (unsigned)(pos + len) > length()) return;
  802.     int nlen = length() - len;
  803.     int first = pos + len;
  804.     ncopy0(&(rep->s[first]), &(rep->s[pos]), length() - first);
  805.     rep->len = nlen;
  806. }
  807.  
  808. void string::del(const regex& r, int startpos)
  809. {
  810.     int mlen;
  811.     int first = r.search(chars(), length(), mlen, startpos);
  812.     del(first, mlen);
  813. }
  814.  
  815. void string::del(const char* t, int startpos)
  816. {
  817.     int tlen = slen(t);
  818.     int p = search(startpos, length(), t, tlen);
  819.     del(p, tlen);
  820. }
  821.  
  822. void string::del(const string& y, int startpos)
  823. {
  824.     del(search(startpos, length(), y.chars(), y.length()), y.length());
  825. }
  826.  
  827. void string::del(const subString& y, int startpos)
  828. {
  829.     del(search(startpos, length(), y.chars(), y.length()), y.length());
  830. }
  831.  
  832. void string::del(char c, int startpos)
  833. {
  834.     del(search(startpos, length(), c), 1);
  835. }
  836.  
  837. /*
  838.  * subString extraction
  839.  */
  840.  
  841.  
  842. subString string::at(int first, int len)
  843. {
  844.     return _substr(first, len);
  845. }
  846.  
  847. subString string::operator() (int first, int len)
  848. {
  849.     return _substr(first, len);
  850. }
  851.  
  852. subString string::before(int pos)
  853. {
  854.     return _substr(0, pos);
  855. }
  856.  
  857. subString string::through(int pos)
  858. {
  859.     return _substr(0, pos+1);
  860. }
  861.  
  862. subString string::after(int pos)
  863. {
  864.     return _substr(pos + 1, length() - (pos + 1));
  865. }
  866.  
  867. subString string::from(int pos)
  868. {
  869.     return _substr(pos, length() - pos);
  870. }
  871.  
  872. subString string::at(const string& y, int startpos)
  873. {
  874.     int first = search(startpos, length(), y.chars(), y.length());
  875.     return _substr(first,  y.length());
  876. }
  877.  
  878. subString string::at(const subString& y, int startpos)
  879. {
  880.     int first = search(startpos, length(), y.chars(), y.length());
  881.     return _substr(first, y.length());
  882. }
  883.  
  884. subString string::at(const regex& r, int startpos)
  885. {
  886.     int mlen;
  887.     int first = r.search(chars(), length(), mlen, startpos);
  888.     return _substr(first, mlen);
  889. }
  890.  
  891. subString string::at(const char* t, int startpos)
  892. {
  893.     int tlen = slen(t);
  894.     int first = search(startpos, length(), t, tlen);
  895.     return _substr(first, tlen);
  896. }
  897.  
  898. subString string::at(char c, int startpos)
  899. {
  900.     int first = search(startpos, length(), c);
  901.     return _substr(first, 1);
  902. }
  903.  
  904. subString string::before(const string& y, int startpos)
  905. {
  906.     int last = search(startpos, length(), y.chars(), y.length());
  907.     return _substr(0, last);
  908. }
  909.  
  910. subString string::before(const subString& y, int startpos)
  911. {
  912.     int last = search(startpos, length(), y.chars(), y.length());
  913.     return _substr(0, last);
  914. }
  915.  
  916. subString string::before(const regex& r, int startpos)
  917. {
  918.     int mlen;
  919.     int first = r.search(chars(), length(), mlen, startpos);
  920.     return _substr(0, first);
  921. }
  922.  
  923. subString string::before(char c, int startpos)
  924. {
  925.     int last = search(startpos, length(), c);
  926.     return _substr(0, last);
  927. }
  928.  
  929. subString string::before(const char* t, int startpos)
  930. {
  931.     int tlen = slen(t);
  932.     int last = search(startpos, length(), t, tlen);
  933.     return _substr(0, last);
  934. }
  935.  
  936. subString string::through(const string& y, int startpos)
  937. {
  938.     int last = search(startpos, length(), y.chars(), y.length());
  939.     if (last >= 0) last += y.length();
  940.     return _substr(0, last);
  941. }
  942.  
  943. subString string::through(const subString& y, int startpos)
  944. {
  945.     int last = search(startpos, length(), y.chars(), y.length());
  946.     if (last >= 0) last += y.length();
  947.     return _substr(0, last);
  948. }
  949.  
  950. subString string::through(const regex& r, int startpos)
  951. {
  952.     int mlen;
  953.     int first = r.search(chars(), length(), mlen, startpos);
  954.     if (first >= 0) first += mlen;
  955.     return _substr(0, first);
  956. }
  957.  
  958. subString string::through(char c, int startpos)
  959. {
  960.     int last = search(startpos, length(), c);
  961.     if (last >= 0) last += 1;
  962.     return _substr(0, last);
  963. }
  964.  
  965. subString string::through(const char* t, int startpos)
  966. {
  967.     int tlen = slen(t);
  968.     int last = search(startpos, length(), t, tlen);
  969.     if (last >= 0) last += tlen;
  970.     return _substr(0, last);
  971. }
  972.  
  973. subString string::after(const string& y, int startpos)
  974. {
  975.     int first = search(startpos, length(), y.chars(), y.length());
  976.     if (first >= 0) first += y.length();
  977.     return _substr(first, length() - first);
  978. }
  979.  
  980. subString string::after(const subString& y, int startpos)
  981. {
  982.     int first = search(startpos, length(), y.chars(), y.length());
  983.     if (first >= 0) first += y.length();
  984.     return _substr(first, length() - first);
  985. }
  986.  
  987. subString string::after(char c, int startpos)
  988. {
  989.     int first = search(startpos, length(), c);
  990.     if (first >= 0) first += 1;
  991.     return _substr(first, length() - first);
  992. }
  993.  
  994. subString string::after(const regex& r, int startpos)
  995. {
  996.     int mlen;
  997.     int first = r.search(chars(), length(), mlen, startpos);
  998.     if (first >= 0) first += mlen;
  999.     return _substr(first, length() - first);
  1000. }
  1001.  
  1002. subString string::after(const char* t, int startpos)
  1003. {
  1004.     int tlen = slen(t);
  1005.     int first = search(startpos, length(), t, tlen);
  1006.     if (first >= 0) first += tlen;
  1007.     return _substr(first, length() - first);
  1008. }
  1009.  
  1010. subString string::from(const string& y, int startpos)
  1011. {
  1012.     int first = search(startpos, length(), y.chars(), y.length());
  1013.     return _substr(first, length() - first);
  1014. }
  1015.  
  1016. subString string::from(const subString& y, int startpos)
  1017. {
  1018.     int first = search(startpos, length(), y.chars(), y.length());
  1019.     return _substr(first, length() - first);
  1020. }
  1021.  
  1022. subString string::from(const regex& r, int startpos)
  1023. {
  1024.     int mlen;
  1025.     int first = r.search(chars(), length(), mlen, startpos);
  1026.     return _substr(first, length() - first);
  1027. }
  1028.  
  1029. subString string::from(char c, int startpos)
  1030. {
  1031.     int first = search(startpos, length(), c);
  1032.     return _substr(first, length() - first);
  1033. }
  1034.  
  1035. subString string::from(const char* t, int startpos)
  1036. {
  1037.     int tlen = slen(t);
  1038.     int first = search(startpos, length(), t, tlen);
  1039.     return _substr(first, length() - first);
  1040. }
  1041.  
  1042.  
  1043.  
  1044. /*
  1045.  * split/join
  1046.  */
  1047.  
  1048.  
  1049. int split(const string& src, string *results, int n, const string& sep)
  1050. {
  1051.     string x = src;
  1052.     const char* s = x.chars();
  1053.     int sl = x.length();
  1054.     int i = 0;
  1055.     int pos = 0;
  1056.     while (i < n && pos < sl)
  1057.     {
  1058.     int p = x.search(pos, sl, sep.chars(), sep.length());
  1059.     if (p < 0)
  1060.         p = sl;
  1061.     results[i].rep = string_Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  1062.     i++;
  1063.     pos = p + sep.length();
  1064.     }
  1065.     return i;
  1066. }
  1067.  
  1068. int split(const string& src, string *results, int n, const regex& r)
  1069. {
  1070.     string x = src;
  1071.     const char* s = x.chars();
  1072.     int sl = x.length();
  1073.     int i = 0;
  1074.     int pos = 0;
  1075.     int p, matchlen;
  1076.     while (i < n && pos < sl)
  1077.     {
  1078.     p = r.search(s, sl, matchlen, pos);
  1079.     if (p < 0)
  1080.         p = sl;
  1081.     results[i].rep = string_Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
  1082.     i++;
  1083.     pos = p + matchlen;
  1084.     }
  1085.     return i;
  1086. }
  1087.  
  1088. string join(string *src, int n, const string& separator) RETURNS(x)
  1089. {
  1090.     RETURN_OBJECT(string, x);
  1091.     string sep = separator;
  1092.     int xlen = 0;
  1093.     int i;
  1094.     for (i = 0; i < n; ++i)
  1095.     xlen += src[i].length();
  1096.     xlen += (n - 1) * sep.length();
  1097.  
  1098.     x.alloc(xlen);
  1099.     x.rep->len = xlen;
  1100.  
  1101.     int j = 0;
  1102.   
  1103.     for (i = 0; i < n - 1; ++i)
  1104.     {
  1105.     ncopy(src[i].chars(), &(x.rep->s[j]), src[i].length());
  1106.     j += src[i].length();
  1107.     ncopy(sep.chars(), &(x.rep->s[j]), sep.length());
  1108.     j += sep.length();
  1109.     }
  1110.     ncopy0(src[i].chars(), &(x.rep->s[j]), src[i].length());
  1111.     RETURN(x);
  1112. }
  1113.  
  1114.   
  1115. /*
  1116.  misc
  1117. */
  1118.  
  1119.     
  1120. strRep* string_Sreverse(strRep* src, strRep* dest)
  1121. {
  1122.     int n = src->len;
  1123.     if (src != dest)
  1124.     dest = string_Salloc(dest, src->s, n, n);
  1125.     if (n > 0)
  1126.     {
  1127.     char* a = dest->s;
  1128.     char* b = &(a[n - 1]);
  1129.     while (a < b)
  1130.     {
  1131.         char t = *a;
  1132.         *a++ = *b;
  1133.         *b-- = t;
  1134.     }
  1135.     }
  1136.     return dest;
  1137. }
  1138.  
  1139.  
  1140. strRep* string_Supcase(strRep* src, strRep* dest)
  1141. {
  1142.     int n = src->len;
  1143.     if (src != dest) dest = string_Salloc(dest, src->s, n, n);
  1144.     char* p = dest->s;
  1145.     char* e = &(p[n]);
  1146.     for (; p < e; ++p) if (islower(*p)) *p = toupper(*p);
  1147.     return dest;
  1148. }
  1149.  
  1150. strRep* string_Sdowncase(strRep* src, strRep* dest)
  1151. {
  1152.     int n = src->len;
  1153.     if (src != dest) dest = string_Salloc(dest, src->s, n, n);
  1154.     char* p = dest->s;
  1155.     char* e = &(p[n]);
  1156.     for (; p < e; ++p) if (isupper(*p)) *p = tolower(*p);
  1157.     return dest;
  1158. }
  1159.  
  1160. strRep* string_Scapitalize(strRep* src, strRep* dest)
  1161. {
  1162.     int n = src->len;
  1163.     if (src != dest) dest = string_Salloc(dest, src->s, n, n);
  1164.  
  1165.     char* p = dest->s;
  1166.     char* e = &(p[n]);
  1167.     for (; p < e; ++p)
  1168.     {
  1169.     int at_word;
  1170.     if ((at_word = islower(*p)))
  1171.         *p = toupper(*p);
  1172.     else 
  1173.         at_word = isupper(*p) || isdigit(*p);
  1174.  
  1175.     if (at_word)
  1176.     {
  1177.         while (++p < e)
  1178.         {
  1179.         if (isupper(*p))
  1180.             *p = tolower(*p);
  1181.         else if (!islower(*p) && !isdigit(*p))
  1182.             break;
  1183.         }
  1184.     }
  1185.     }
  1186.     return dest;
  1187. }
  1188.  
  1189. #if HAVE_NAMED_RETURN_VALUES
  1190.  
  1191. #if 0                // already defined in -lg++
  1192. string replicate(char c, int n) return w;
  1193. {
  1194.     w.rep = string_Sresize(w.rep, n);
  1195.     char* p = w.rep->s;
  1196.     while (n-- > 0) *p++ = c;
  1197.     *p = 0;
  1198. }
  1199. #endif
  1200.  
  1201. string replicate(const string& y, int n) return w
  1202. {
  1203.     int len = y.length();
  1204.     w.rep = string_Sresize(w.rep, n * len);
  1205.     char* p = w.rep->s;
  1206.     while (n-- > 0)
  1207.     {
  1208.     ncopy(y.chars(), p, len);
  1209.     p += len;
  1210.     }
  1211.     *p = 0;
  1212. }
  1213.  
  1214. string common_prefix(const string& x, const string& y, int startpos) return r;
  1215. {
  1216.     const char* xchars = x.chars();
  1217.     const char* ychars = y.chars();
  1218.     const char* xs = &(xchars[startpos]);
  1219.     const char* ss = xs;
  1220.     const char* topx = &(xchars[x.length()]);
  1221.     const char* ys = &(ychars[startpos]);
  1222.     const char* topy = &(ychars[y.length()]);
  1223.     int l;
  1224.     for (l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1225.     r.rep = string_Salloc(r.rep, ss, l, l);
  1226. }
  1227.  
  1228. string common_suffix(const string& x, const string& y, int startpos) return r;
  1229. {
  1230.     const char* xchars = x.chars();
  1231.     const char* ychars = y.chars();
  1232.     const char* xs = &(xchars[x.length() + startpos]);
  1233.     const char* botx = xchars;
  1234.     const char* ys = &(ychars[y.length() + startpos]);
  1235.     const char* boty = ychars;
  1236.     int l;
  1237.     for (l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1238.     r.rep = string_Salloc(r.rep, ++xs, l, l);
  1239. }
  1240.  
  1241. #else // !HAVE_NAMED_RETURN_VALUES
  1242.  
  1243. #if 0
  1244. string replicate(char c, int n)
  1245. {
  1246.     string w;
  1247.     w.rep = string_Sresize(w.rep, n);
  1248.     char* p = w.rep->s;
  1249.     while (n-- > 0) *p++ = c;
  1250.     *p = 0;
  1251.     return w;
  1252. }
  1253. #endif
  1254.  
  1255. string replicate(const string& y, int n)
  1256. {
  1257.     string w;
  1258.     int len = y.length();
  1259.     w.rep = string_Sresize(w.rep, n * len);
  1260.     char* p = w.rep->s;
  1261.     while (n-- > 0)
  1262.     {
  1263.     ncopy(y.chars(), p, len);
  1264.     p += len;
  1265.     }
  1266.     *p = 0;
  1267.     return w;
  1268. }
  1269.  
  1270. string common_prefix(const string& x, const string& y, int startpos)
  1271. {
  1272.     string r;
  1273.     const char* xchars = x.chars();
  1274.     const char* ychars = y.chars();
  1275.     const char* xs = &(xchars[startpos]);
  1276.     const char* ss = xs;
  1277.     const char* topx = &(xchars[x.length()]);
  1278.     const char* ys = &(ychars[startpos]);
  1279.     const char* topy = &(ychars[y.length()]);
  1280.     int l;
  1281.     for (l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
  1282.     r.rep = string_Salloc(r.rep, ss, l, l);
  1283.     return r;
  1284. }
  1285.  
  1286. string common_suffix(const string& x, const string& y, int startpos) 
  1287. {
  1288.     string r;
  1289.     const char* xchars = x.chars();
  1290.     const char* ychars = y.chars();
  1291.     const char* xs = &(xchars[x.length() + startpos]);
  1292.     const char* botx = xchars;
  1293.     const char* ys = &(ychars[y.length() + startpos]);
  1294.     const char* boty = ychars;
  1295.     int l;
  1296.     for (l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
  1297.     r.rep = string_Salloc(r.rep, ++xs, l, l);
  1298.     return r;
  1299. }
  1300.  
  1301. #endif // !HAVE_NAMED_RETURN_VALUES
  1302.  
  1303. // IO
  1304.  
  1305. istream& operator>>(istream& s, string& x)
  1306. {
  1307. #ifdef _OLD_STREAMS
  1308.     if (!s.good())
  1309.     {
  1310.     return s;
  1311.     }
  1312.     s >> ws;
  1313.     if (!s.good())
  1314.     {
  1315.     return s;
  1316.     }
  1317. #else
  1318.     if (!s.ipfx(0) || (!(s.flags() & ios::skipws) && !ws(s)))
  1319.     {
  1320.     s.clear(ios::failbit|s.rdstate()); // Redundant if using GNU iostreams.
  1321.     return s;
  1322.     }
  1323. #endif
  1324.     int ch;
  1325.     unsigned i = 0;
  1326.     x.rep = string_Sresize(x.rep, 20);
  1327.     register streambuf *sb = s.rdbuf();
  1328.     while ((ch = sb->sbumpc()) != EOF)
  1329.     {
  1330.     if (isspace(ch))
  1331.         break;
  1332.     if (i >= string_Sremainder(x.rep) - 1)
  1333.         x.rep = string_Sresize(x.rep, i+1);
  1334.     x.rep->s[i++] = ch;
  1335.     }
  1336.     x.rep->s[i] = 0;
  1337.     x.rep->len = i;
  1338.     int new_state = s.rdstate();
  1339.     if (i == 0) new_state |= ios::failbit;
  1340.     if (ch == EOF) new_state |= ios::eofbit;
  1341.     s.clear(new_state);
  1342.     return s;
  1343. }
  1344.  
  1345. int readline(istream& s, string& x, char terminator, int discard)
  1346. {
  1347.     assert(!x.consuming());
  1348.  
  1349. #ifdef _OLD_STREAMS
  1350.     if (!s.good())
  1351. #else
  1352.     if (!s.ipfx(0))
  1353. #endif
  1354.     {
  1355.         return 0;
  1356.     }
  1357.     int ch;
  1358.     unsigned i = 0;
  1359.     x.rep = string_Sresize(x.rep, 80);
  1360.     register streambuf *sb = s.rdbuf();
  1361.     while ((ch = sb->sbumpc()) != EOF)
  1362.     {
  1363.     if (ch != terminator || !discard)
  1364.     {
  1365.         if (i >= string_Sremainder(x.rep) - 1)
  1366.         x.rep = string_Sresize(x.rep, i+1);
  1367.         x.rep->s[i++] = ch;
  1368.     }
  1369.     if (ch == terminator)
  1370.         break;
  1371.     }
  1372.     x.rep->s[i] = 0;
  1373.     x.rep->len = i;
  1374.     if (ch == EOF) s.clear(s.rdstate() | ios::eofbit);
  1375.     return i;
  1376. }
  1377.  
  1378.  
  1379.  
  1380.  
  1381. // from John.Willis@FAS.RI.CMU.EDU
  1382.  
  1383. int string::freq(const subString& y) const
  1384. {
  1385.     int found = 0;
  1386.     for (unsigned int i = 0; i < length(); i++) 
  1387.     if (match(i,length(),0,y.chars(), y.length())>= 0) found++;
  1388.     return(found);
  1389. }
  1390.  
  1391. int string::freq(const string& y) const
  1392. {
  1393.     int found = 0;
  1394.     for (unsigned int i = 0; i < length(); i++) 
  1395.     if (match(i,length(),0,y.chars(),y.length()) >= 0) found++;
  1396.     return(found);
  1397. }
  1398.  
  1399. int string::freq(const char* t) const
  1400. {
  1401.     int found = 0;
  1402.     for (unsigned int i = 0; i < length(); i++) 
  1403.     if (match(i,length(),0,t) >= 0) found++;
  1404.     return(found);
  1405. }
  1406.  
  1407. int string::freq(char c) const
  1408. {
  1409.     int found = 0;
  1410.     for (unsigned int i = 0; i < length(); i++) 
  1411.     if (match(i,length(),0,&c,1) >= 0) found++;
  1412.     return(found);
  1413. }
  1414.  
  1415.  
  1416. bool string::OK() const
  1417. {
  1418.     if (rep == 0                       // Don't have a rep
  1419.     || rep->len > string_Sremainder(rep)   // Len out of bounds
  1420.     || rep->s < rep->mem                   // Ptr out of bounds
  1421.     || rep->s >= rep->mem + rep->allocated // Ptr out of bounds
  1422.     || rep->s[rep->len] != '\0')           // Not null-terminated
  1423.     error("invariant failure");
  1424.  
  1425.     return true;
  1426. }
  1427.  
  1428. bool subString::OK() const
  1429. {
  1430.     // Check for legal string and pos and len outside bounds
  1431.     if (!S.OK() || pos + len > S.rep->len)
  1432.     S.error("subString invariant failure");
  1433.     return true;
  1434. }
  1435.