386BSD 0.1 development

Work on file usr/src/lib/libg++/libg++/String.cc
Work on file usr/src/lib/libg++/g++-include/String.h

Co-Authored-By: Lynne Greer Jolitz <ljolitz@cardio.ucsf.edu>
Synthesized-from: 386BSD-0.1

diff --git a/usr/src/lib/libg++/g++-include/String.h b/usr/src/lib/libg++/g++-include/String.h
new file mode 100644 (file)
index 0000000..871b9a2
--- /dev/null
+++ b/usr/src/lib/libg++/g++-include/String.h
@@ -0,0 +1,1341 @@
+// This may look like C code, but it is really -*- C++ -*-
+/* 
+Copyright (C) 1988 Free Software Foundation
+    written by Doug Lea (dl@rocky.oswego.edu)
+
+This file is part of GNU CC.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY.  No author or distributor
+accepts responsibility to anyone for the consequences of using it
+or for whether it serves any particular purpose or works at all,
+unless he says so in writing.  Refer to the GNU CC General Public
+License for full details.
+
+Everyone is granted permission to copy, modify and redistribute
+GNU CC, but only under the conditions described in the
+GNU CC General Public License.   A copy of this license is
+supposed to have been given to you along with GNU CC so you
+can know your rights and responsibilities.  It should be in a
+file named COPYING.  Among other things, the copyright notice
+and this notice must be preserved on all copies.  
+*/
+
+#if defined(SHORT_NAMES) || defined(VMS)
+#define re_compile_pattern     recmppat
+#define re_pattern_buffer      repatbuf
+#define re_registers           reregs
+#endif
+
+#ifndef _String_h
+#ifdef __GNUG__
+#pragma once
+#pragma interface
+#endif
+#define _String_h 1
+
+#include <stream.h>
+#include <Regex.h>
+
+struct StrRep                     // internal String representations
+{
+  unsigned short    len;         // string length 
+  unsigned short    sz;          // allocated space
+  char              s[1];        // the string starts here 
+                                 // (at least 1 char for trailing null)
+                                 // allocated & expanded via non-public fcts
+};
+
+// primitive ops on StrReps -- nearly all String fns go through these.
+
+StrRep*     Salloc(StrRep*, const char*, int, int);
+StrRep*     Scopy(StrRep*, StrRep*);
+StrRep*     Sresize(StrRep*, int);
+StrRep*     Scat(StrRep*, const char*, int, const char*, int);
+StrRep*     Scat(StrRep*, const char*, int,const char*,int, const char*,int);
+StrRep*     Sprepend(StrRep*, const char*, int);
+StrRep*     Sreverse(StrRep*, StrRep*);
+StrRep*     Supcase(StrRep*, StrRep*);
+StrRep*     Sdowncase(StrRep*, StrRep*);
+StrRep*     Scapitalize(StrRep*, StrRep*);
+
+// These classes need to be defined in the order given
+
+class String;
+class SubString;
+
+class SubString
+{
+  friend class      String;
+protected:
+
+  String&           S;        // The String I'm a substring of
+  unsigned short    pos;      // starting position in S's rep
+  unsigned short    len;      // length of substring
+
+  void              assign(StrRep*, const char*, int = -1);
+                    SubString(String& x, int p, int l);
+                    SubString(const SubString& x);
+
+public:
+
+// Note there are no public constructors. SubStrings are always
+// created via String operations
+
+                   ~SubString();
+
+  void              operator =  (const String&     y);
+  void              operator =  (const SubString&  y);
+  void              operator =  (const char* t);
+  void              operator =  (char        c);
+
+// return 1 if target appears anywhere in SubString; else 0
+
+  int               contains(char        c) const;
+  int               contains(const String&     y) const;
+  int               contains(const SubString&  y) const;
+  int               contains(const char* t) const;
+  int               contains(const Regex&       r) const;
+
+// return 1 if target matches entire SubString
+
+  int               matches(const Regex&  r) const;
+
+// IO 
+
+  friend ostream&   operator<<(ostream& s, const SubString& x);
+
+// status
+
+  int               length() const;
+  int               empty() const;
+  const char*       chars() const;
+
+  int               OK() const; 
+
+};
+
+
+class String
+{
+  friend class      SubString;
+
+protected:
+  StrRep*           rep;   // Strings are pointers to their representations
+
+// some helper functions
+
+  int               search(int, int, const char*, int = -1) const;
+  int               search(int, int, char) const;
+  int               match(int, int, int, const char*, int = -1) const;
+  int               _gsub(const char*, int, const char* ,int);
+  int               _gsub(const Regex&, const char*, int);
+  SubString         _substr(int, int);
+
+public:
+
+// constructors & assignment
+
+                    String();
+                    String(const String& x);
+                    String(const SubString&  x);
+                    String(const char* t);
+                    String(const char* t, int len);
+                    String(char c);
+
+                    ~String();
+
+  void              operator =  (const String&     y);
+  void              operator =  (const char* y);
+  void              operator =  (char        c);
+  void              operator =  (const SubString&  y);
+
+// concatenation
+
+  void              operator += (const String&     y); 
+  void              operator += (const SubString&  y);
+  void              operator += (const char* t);
+  void              operator += (char        c);
+
+  void              prepend(const String&     y); 
+  void              prepend(const SubString&  y);
+  void              prepend(const char* t);
+  void              prepend(char        c);
+
+
+// procedural versions:
+// concatenate first 2 args, store result in last arg
+
+  friend void     cat(const String&, const String&, String&);
+  friend void     cat(const String&, const SubString&, String&);
+  friend void     cat(const String&, const char*, String&);
+  friend void     cat(const String&, char, String&);
+
+  friend void     cat(const SubString&, const String&, String&);
+  friend void     cat(const SubString&, const SubString&, String&);
+  friend void     cat(const SubString&, const char*, String&);
+  friend void     cat(const SubString&, char, String&);
+
+  friend void     cat(const char*, const String&, String&);
+  friend void     cat(const char*, const SubString&, String&);
+  friend void     cat(const char*, const char*, String&);
+  friend void     cat(const char*, char, String&);
+
+// double concatenation, by request. (yes, there are too many versions, 
+// but if one is supported, then the others should be too...)
+// Concatenate first 3 args, store in last arg
+
+  friend void     cat(const String&,const String&, const String&,String&);
+  friend void     cat(const String&,const String&,const SubString&,String&);
+  friend void     cat(const String&,const String&, const char*, String&);
+  friend void     cat(const String&,const String&, char, String&);
+  friend void     cat(const String&,const SubString&,const String&,String&);
+  friend void     cat(const String&,const SubString&,const SubString&,String&);
+  friend void     cat(const String&,const SubString&, const char*, String&);
+  friend void     cat(const String&,const SubString&, char, String&);
+  friend void     cat(const String&,const char*, const String&,    String&);
+  friend void     cat(const String&,const char*, const SubString&, String&);
+  friend void     cat(const String&,const char*, const char*, String&);
+  friend void     cat(const String&,const char*, char, String&);
+
+  friend void     cat(const char*, const String&, const String&,String&);
+  friend void     cat(const char*,const String&,const SubString&,String&);
+  friend void     cat(const char*,const String&, const char*, String&);
+  friend void     cat(const char*,const String&, char, String&);
+  friend void     cat(const char*,const SubString&,const String&,String&);
+  friend void     cat(const char*,const SubString&,const SubString&,String&);
+  friend void     cat(const char*,const SubString&, const char*, String&);
+  friend void     cat(const char*,const SubString&, char, String&);
+  friend void     cat(const char*,const char*, const String&,    String&);
+  friend void     cat(const char*,const char*, const SubString&, String&);
+  friend void     cat(const char*,const char*, const char*, String&);
+  friend void     cat(const char*,const char*, char, String&);
+
+
+// searching & matching
+
+// return position of target in string or -1 for failure
+
+  int               index(char        c, int startpos = 0) const;      
+  int               index(const String&     y, int startpos = 0) const;      
+  int               index(const SubString&  y, int startpos = 0) const;      
+  int               index(const char* t, int startpos = 0) const;  
+  int               index(const Regex&      r, int startpos = 0) const;       
+
+// return 1 if target appears anyhere in String; else 0
+
+  int               contains(char        c) const;
+  int               contains(const String&     y) const;
+  int               contains(const SubString&  y) const;
+  int               contains(const char* t) const;
+  int               contains(const Regex&      r) const;
+
+// return 1 if target appears anywhere after position pos 
+// (or before, if pos is negative) in String; else 0
+
+  int               contains(char        c, int pos) const;
+  int               contains(const String&     y, int pos) const;
+  int               contains(const SubString&  y, int pos) const;
+  int               contains(const char* t, int pos) const;
+  int               contains(const Regex&      r, int pos) const;
+
+// return 1 if target appears at position pos in String; else 0
+
+  int               matches(char        c, int pos = 0) const;
+  int               matches(const String&     y, int pos = 0) const;
+  int               matches(const SubString&  y, int pos = 0) const;
+  int               matches(const char* t, int pos = 0) const;
+  int               matches(const Regex&      r, int pos = 0) const;
+
+//  return number of occurences of target in String
+
+  int               freq(char        c) const; 
+  int               freq(const String&     y) const;
+  int               freq(const SubString&  y) const;
+  int               freq(const char* t) const;
+
+// SubString extraction
+
+// Note that you can't take a substring of a const String, since
+// this leaves open the possiblility of indirectly modifying the
+// String through the SubString
+
+  SubString         at(int         pos, int len);
+  SubString         operator () (int         pos, int len); // synonym for at
+
+  SubString         at(const String&     x, int startpos = 0); 
+  SubString         at(const SubString&  x, int startpos = 0); 
+  SubString         at(const char* t, int startpos = 0);
+  SubString         at(char        c, int startpos = 0);
+  SubString         at(const Regex&      r, int startpos = 0); 
+
+  SubString         before(int          pos);
+  SubString         before(const String&      x, int startpos = 0);
+  SubString         before(const SubString&   x, int startpos = 0);
+  SubString         before(const char*  t, int startpos = 0);
+  SubString         before(char         c, int startpos = 0);
+  SubString         before(const Regex&       r, int startpos = 0);
+
+  SubString         through(int          pos);
+  SubString         through(const String&      x, int startpos = 0);
+  SubString         through(const SubString&   x, int startpos = 0);
+  SubString         through(const char*  t, int startpos = 0);
+  SubString         through(char         c, int startpos = 0);
+  SubString         through(const Regex&       r, int startpos = 0);
+
+  SubString         from(int          pos);
+  SubString         from(const String&      x, int startpos = 0);
+  SubString         from(const SubString&   x, int startpos = 0);
+  SubString         from(const char*  t, int startpos = 0);
+  SubString         from(char         c, int startpos = 0);
+  SubString         from(const Regex&       r, int startpos = 0);
+
+  SubString         after(int         pos);
+  SubString         after(const String&     x, int startpos = 0);
+  SubString         after(const SubString&  x, int startpos = 0);
+  SubString         after(const char* t, int startpos = 0);
+  SubString         after(char        c, int startpos = 0);
+  SubString         after(const Regex&      r, int startpos = 0);
+
+
+// deletion
+
+// delete len chars starting at pos
+  void              del(int         pos, int len);
+
+// delete the first occurrence of target after startpos
+
+  void              del(const String&     y, int startpos = 0);
+  void              del(const SubString&  y, int startpos = 0);
+  void              del(const char* t, int startpos = 0);
+  void              del(char        c, int startpos = 0);
+  void              del(const Regex&      r, int startpos = 0);
+
+// global substitution: substitute all occurrences of pat with repl
+
+  int               gsub(const String&     pat, const String&     repl);
+  int               gsub(const SubString&  pat, const String&     repl);
+  int               gsub(const char* pat, const String&     repl);
+  int               gsub(const char* pat, const char* repl);
+  int               gsub(const Regex&      pat, const String&     repl);
+
+// friends & utilities
+
+// split string into array res at separators; return number of elements
+
+  friend int        split(const String& x, String res[], int maxn, 
+                          const String& sep);
+  friend int        split(const String& x, String res[], int maxn, 
+                          const Regex&  sep);
+
+  friend String     common_prefix(const String& x, const String& y, 
+                                  int startpos = 0);
+  friend String     common_suffix(const String& x, const String& y, 
+                                  int startpos = -1);
+  friend String     replicate(char        c, int n);
+  friend String     replicate(const String&     y, int n);
+  friend String     join(String src[], int n, const String& sep);
+
+// simple builtin transformations
+
+  friend String     reverse(const String& x);
+  friend String     upcase(const String& x);
+  friend String     downcase(const String& x);
+  friend String     capitalize(const String& x);
+
+// in-place versions of above
+
+  void              reverse();
+  void              upcase();
+  void              downcase();
+  void              capitalize();
+
+// element extraction
+
+  char&             operator [] (int i);
+  char              elem(int i) const;
+  char              firstchar() const;
+  char              lastchar() const;
+
+// conversion
+
+                    operator const char*() const;
+  const char*       chars() const;
+
+
+// IO
+
+  friend ostream&   operator<<(ostream& s, const String& x);
+  friend ostream&   operator<<(ostream& s, const SubString& x);
+  friend istream&   operator>>(istream& s, String& x);
+
+  friend int        readline(istream& s, String& x, 
+                             char terminator = '\n',
+                             int discard_terminator = 1);
+
+// status
+
+  int               length() const;
+  int               empty() const;
+
+// preallocate some space for String
+  void              alloc(int newsize);
+
+// report current allocation (not length!)
+
+  int               allocation() const;
+
+
+  volatile void     error(const char* msg) const;
+
+  int               OK() const;
+};
+
+typedef String StrTmp; // for backward compatibility
+
+// other externs
+
+int        compare(const String&    x, const String&     y);
+int        compare(const String&    x, const SubString&  y);
+int        compare(const String&    x, const char* y);
+int        compare(const SubString& x, const String&     y);
+int        compare(const SubString& x, const SubString&  y);
+int        compare(const SubString& x, const char* y);
+int        fcompare(const String&   x, const String&     y); // ignore case
+
+extern StrRep  _nilStrRep;
+extern String _nilString;
+
+// other inlines
+
+String operator + (const String& x, const String& y);
+String operator + (const String& x, const SubString& y);
+String operator + (const String& x, const char* y);
+String operator + (const String& x, char y);
+String operator + (const SubString& x, const String& y);
+String operator + (const SubString& x, const SubString& y);
+String operator + (const SubString& x, const char* y);
+String operator + (const SubString& x, char y);
+String operator + (const char* x, const String& y);
+String operator + (const char* x, const SubString& y);
+
+int operator==(const String& x, const String& y); 
+int operator!=(const String& x, const String& y);
+int operator> (const String& x, const String& y);
+int operator>=(const String& x, const String& y);
+int operator< (const String& x, const String& y);
+int operator<=(const String& x, const String& y);
+int operator==(const String& x, const SubString&  y);
+int operator!=(const String& x, const SubString&  y);
+int operator> (const String& x, const SubString&  y);
+int operator>=(const String& x, const SubString&  y);
+int operator< (const String& x, const SubString&  y);
+int operator<=(const String& x, const SubString&  y);
+int operator==(const String& x, const char* t);
+int operator!=(const String& x, const char* t);
+int operator> (const String& x, const char* t);
+int operator>=(const String& x, const char* t);
+int operator< (const String& x, const char* t);
+int operator<=(const String& x, const char* t);
+int operator==(const SubString& x, const String& y);
+int operator!=(const SubString& x, const String& y);
+int operator> (const SubString& x, const String& y);
+int operator>=(const SubString& x, const String& y);
+int operator< (const SubString& x, const String& y);
+int operator<=(const SubString& x, const String& y);
+int operator==(const SubString& x, const SubString&  y);
+int operator!=(const SubString& x, const SubString&  y);
+int operator> (const SubString& x, const SubString&  y);
+int operator>=(const SubString& x, const SubString&  y);
+int operator< (const SubString& x, const SubString&  y);
+int operator<=(const SubString& x, const SubString&  y);
+int operator==(const SubString& x, const char* t);
+int operator!=(const SubString& x, const char* t);
+int operator> (const SubString& x, const char* t);
+int operator>=(const SubString& x, const char* t);
+int operator< (const SubString& x, const char* t);
+int operator<=(const SubString& x, const char* t);
+
+#if defined(__OPTIMIZE__) || defined(USE_LIBGXX_INLINES)
+
+
+// status reports, needed before defining other things
+
+inline int         String::length() const {  return rep->len; }
+inline int         String::empty() const { return rep->len == 0; }
+inline const char* String::chars() const { return &(rep->s[0]); }
+inline int         String::allocation() const { return rep->sz; }
+inline void        String::alloc(int newsize) { rep = Sresize(rep, newsize); }
+
+inline int         SubString::length() const { return len; }
+inline int         SubString::empty() const { return len == 0; }
+inline const char* SubString::chars() const { return &(S.rep->s[pos]); }
+
+
+// constructors
+
+inline String::String() 
+  : rep(&_nilStrRep) {}
+inline String::String(const String& x) 
+  : rep(Scopy(0, x.rep)) {}
+inline String::String(const char* t) 
+  : rep(Salloc(0, t, -1, -1)) {}
+inline String::String(const char* t, int tlen)
+  : rep(Salloc(0, t, tlen, tlen)) {}
+inline String::String(const SubString& y)
+  : rep(Salloc(0, y.chars(), y.length(), y.length())) {}
+inline String::String(char c) 
+  : rep(Salloc(0, &c, 1, 1)) {}
+
+inline String::~String() { if (rep != &_nilStrRep) delete rep; }
+
+inline SubString::SubString(const SubString& x)
+  :S(x.S), pos(x.pos), len(x.len) {}
+inline SubString::SubString(String& x, int first, int l)
+  :S(x), pos(first), len(l) {}
+
+inline SubString::~SubString() {}
+
+// assignment
+
+inline void String::operator =  (const String& y)
+{ 
+  rep = Scopy(rep, y.rep);
+}
+
+inline void String::operator=(const char* t)
+{
+  rep = Salloc(rep, t, -1, -1); 
+}
+
+inline void String::operator=(const SubString&  y)
+{
+  rep = Salloc(rep, y.chars(), y.length(), y.length());
+}
+
+inline void String::operator=(char c)
+{
+  rep = Salloc(rep, &c, 1, 1); 
+}
+
+
+inline void SubString::operator = (const char* ys)
+{
+  assign(0, ys);
+}
+
+inline void SubString::operator = (char ch)
+{
+  assign(0, &ch, 1);
+}
+
+inline void SubString::operator = (const String& y)
+{
+  assign(y.rep, y.chars(), y.length());
+}
+
+inline void SubString::operator = (const SubString& y)
+{
+  assign(y.S.rep, y.chars(), y.length());
+}
+
+// Zillions of cats...
+
+inline void cat(const String& x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const String& x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const String& x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), y, -1);
+}
+
+inline void cat(const String& x, char y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), &y, 1);
+}
+
+inline void cat(const SubString& x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const SubString& x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const SubString& x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), y, -1);
+}
+
+inline void cat(const SubString& x, char y, String& r)
+{
+  r.rep = Scat(r.rep, x.chars(), x.length(), &y, 1);
+}
+
+inline void cat(const char* x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, x, -1, y.chars(), y.length());
+}
+
+inline void cat(const char* x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, x, -1, y.chars(), y.length());
+}
+
+inline void cat(const char* x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, x, -1, y, -1);
+}
+
+inline void cat(const char* x, char y, String& r)
+{
+  r.rep = Scat(r.rep, x, -1, &y, 1);
+}
+
+inline void cat(const String& a, const String& x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const String& a, const String& x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const String& a, const String& x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), y, -1);
+}
+
+inline void cat(const String& a, const String& x, char y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), &y, 1);
+}
+
+inline void cat(const String& a, const SubString& x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const String& a, const SubString& x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const String& a, const SubString& x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), y, -1);
+}
+
+inline void cat(const String& a, const SubString& x, char y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x.chars(), x.length(), &y, 1);
+}
+
+inline void cat(const String& a, const char* x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x, -1, y.chars(), y.length());
+}
+
+inline void cat(const String& a, const char* x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x, -1, y.chars(), y.length());
+}
+
+inline void cat(const String& a, const char* x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x, -1, y, -1);
+}
+
+inline void cat(const String& a, const char* x, char y, String& r)
+{
+  r.rep = Scat(r.rep, a.chars(), a.length(), x, -1, &y, 1);
+}
+
+
+inline void cat(const char* a, const String& x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const char* a, const String& x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const char* a, const String& x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), y, -1);
+}
+
+inline void cat(const char* a, const String& x, char y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), &y, 1);
+}
+
+inline void cat(const char* a, const SubString& x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const char* a, const SubString& x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), y.chars(), y.length());
+}
+
+inline void cat(const char* a, const SubString& x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), y, -1);
+}
+
+inline void cat(const char* a, const SubString& x, char y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x.chars(), x.length(), &y, 1);
+}
+
+inline void cat(const char* a, const char* x, const String& y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x, -1, y.chars(), y.length());
+}
+
+inline void cat(const char* a, const char* x, const SubString& y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x, -1, y.chars(), y.length());
+}
+
+inline void cat(const char* a, const char* x, const char* y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x, -1, y, -1);
+}
+
+inline void cat(const char* a, const char* x, char y, String& r)
+{
+  r.rep = Scat(r.rep, a, -1, x, -1, &y, 1);
+}
+
+
+// operator versions
+
+inline void String::operator +=(const String& y)
+{
+  cat(*this, y, *this);
+}
+
+inline void String::operator +=(const SubString& y)
+{
+  cat(*this, y, *this);
+}
+
+inline void String::operator += (const char* y)
+{
+  cat(*this, y, *this);
+}
+
+inline void String:: operator +=(char y)
+{
+  cat(*this, y, *this);
+}
+
+// constructive concatenation
+
+#if defined(__GNUG__) && !defined(NO_NRV)
+
+inline String operator + (const String& x, const String& y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const String& x, const SubString& y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const String& x, const char* y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const String& x, char y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const SubString& x, const String& y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const SubString& x, const SubString& y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const SubString& x, const char* y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const SubString& x, char y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const char* x, const String& y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String operator + (const char* x, const SubString& y) return r;
+{
+  cat(x, y, r);
+}
+
+inline String reverse(const String& x) return r;
+{
+  r.rep = Sreverse(x.rep, r.rep);
+}
+
+inline String upcase(const String& x) return r;
+{
+  r.rep = Supcase(x.rep, r.rep);
+}
+
+inline String downcase(const String& x) return r;
+{
+  r.rep = Sdowncase(x.rep, r.rep);
+}
+
+inline String capitalize(const String& x) return r;
+{
+  r.rep = Scapitalize(x.rep, r.rep);
+}
+
+#else /* NO_NRV */
+
+inline String operator + (const String& x, const String& y)
+{
+  String r;  cat(x, y, r);  return r;
+}
+
+inline String operator + (const String& x, const SubString& y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const String& x, const char* y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const String& x, char y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const SubString& x, const String& y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const SubString& x, const SubString& y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const SubString& x, const char* y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const SubString& x, char y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const char* x, const String& y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String operator + (const char* x, const SubString& y) 
+{
+  String r; cat(x, y, r); return r;
+}
+
+inline String reverse(const String& x) 
+{
+  String r; r.rep = Sreverse(x.rep, r.rep); return r;
+}
+
+inline String upcase(const String& x) 
+{
+  String r; r.rep = Supcase(x.rep, r.rep); return r;
+}
+
+inline String downcase(const String& x) 
+{
+  String r; r.rep = Sdowncase(x.rep, r.rep); return r;
+}
+
+inline String capitalize(const String& x) 
+{
+  String r; r.rep = Scapitalize(x.rep, r.rep); return r;
+}
+
+#endif
+
+// prepend
+
+inline void String::prepend(const String& y)
+{
+  rep = Sprepend(rep, y.chars(), y.length());
+}
+
+inline void String::prepend(const char* y)
+{
+  rep = Sprepend(rep, y, -1); 
+}
+
+inline void String::prepend(char y)
+{
+  rep = Sprepend(rep, &y, 1); 
+}
+
+inline void String::prepend(const SubString& y)
+{
+  rep = Sprepend(rep, y.chars(), y.length());
+}
+
+// misc transformations
+
+
+inline void String::reverse()
+{
+  rep = Sreverse(rep, rep);
+}
+
+
+inline void String::upcase()
+{
+  rep = Supcase(rep, rep);
+}
+
+
+inline void String::downcase()
+{
+  rep = Sdowncase(rep, rep);
+}
+
+
+inline void String::capitalize()
+{
+  rep = Scapitalize(rep, rep);
+}
+
+// element extraction
+
+inline char&  String::operator [] (int i) 
+{ 
+  if (((unsigned)i) >= length()) error("invalid index");
+  return rep->s[i];
+}
+
+inline char  String::elem (int i) const
+{ 
+  if (((unsigned)i) >= length()) error("invalid index");
+  return rep->s[i];
+}
+
+inline char  String::firstchar() const
+{ 
+  return elem(0);
+}
+
+inline char  String::lastchar() const
+{ 
+  return elem(length() - 1);
+}
+
+// searching
+
+inline int String::index(char c, int startpos) const
+{
+  return search(startpos, length(), c);
+}
+
+inline int String::index(const char* t, int startpos) const
+{   
+  return search(startpos, length(), t);
+}
+
+inline int String::index(const String& y, int startpos) const
+{   
+  return search(startpos, length(), y.chars(), y.length());
+}
+
+inline int String::index(const SubString& y, int startpos) const
+{   
+  return search(startpos, length(), y.chars(), y.length());
+}
+
+inline int String::index(const Regex& r, int startpos) const
+{
+  int unused;  return r.search(chars(), length(), unused, startpos);
+}
+
+inline int String::contains(char c) const
+{
+  return search(0, length(), c) >= 0;
+}
+
+inline int String::contains(const char* t) const
+{   
+  return search(0, length(), t) >= 0;
+}
+
+inline int String::contains(const String& y) const
+{   
+  return search(0, length(), y.chars(), y.length()) >= 0;
+}
+
+inline int String::contains(const SubString& y) const
+{   
+  return search(0, length(), y.chars(), y.length()) >= 0;
+}
+
+inline int String::contains(char c, int p) const
+{
+  return match(p, length(), 0, &c, 1) >= 0;
+}
+
+inline int String::contains(const char* t, int p) const
+{
+  return match(p, length(), 0, t) >= 0;
+}
+
+inline int String::contains(const String& y, int p) const
+{
+  return match(p, length(), 0, y.chars(), y.length()) >= 0;
+}
+
+inline int String::contains(const SubString& y, int p) const
+{
+  return match(p, length(), 0, y.chars(), y.length()) >= 0;
+}
+
+inline int String::contains(const Regex& r) const
+{
+  int unused;  return r.search(chars(), length(), unused, 0) >= 0;
+}
+
+inline int String::contains(const Regex& r, int p) const
+{
+  return r.match(chars(), length(), p) >= 0;
+}
+
+
+inline int String::matches(const SubString& y, int p) const
+{
+  return match(p, length(), 1, y.chars(), y.length()) >= 0;
+}
+
+inline int String::matches(const String& y, int p) const
+{
+  return match(p, length(), 1, y.chars(), y.length()) >= 0;
+}
+
+inline int String::matches(const char* t, int p) const
+{
+  return match(p, length(), 1, t) >= 0;
+}
+
+inline int String::matches(char c, int p) const
+{
+  return match(p, length(), 1, &c, 1) >= 0;
+}
+
+inline int String::matches(const Regex& r, int p) const
+{
+  int l = (p < 0)? -p : length() - p;
+  return r.match(chars(), length(), p) == l;
+}
+
+
+inline int SubString::contains(const char* t) const
+{   
+  return S.search(pos, pos+len, t) >= 0;
+}
+
+inline int SubString::contains(const String& y) const
+{   
+  return S.search(pos, pos+len, y.chars(), y.length()) >= 0;
+}
+
+inline int SubString::contains(const SubString&  y) const
+{   
+  return S.search(pos, pos+len, y.chars(), y.length()) >= 0;
+}
+
+inline int SubString::contains(char c) const
+{
+  return S.search(pos, pos+len, 0, c) >= 0;
+}
+
+inline int SubString::contains(const Regex& r) const
+{
+  int unused;  return r.search(chars(), len, unused, 0) >= 0;
+}
+
+inline int SubString::matches(const Regex& r) const
+{
+  return r.match(chars(), len, 0) == len;
+}
+
+
+inline int String::gsub(const String& pat, const String& r)
+{
+  return _gsub(pat.chars(), pat.length(), r.chars(), r.length());
+}
+
+inline int String::gsub(const SubString&  pat, const String& r)
+{
+  return _gsub(pat.chars(), pat.length(), r.chars(), r.length());
+}
+
+inline int String::gsub(const Regex& pat, const String& r)
+{
+  return _gsub(pat, r.chars(), r.length());
+}
+
+inline int String::gsub(const char* pat, const String& r)
+{
+  return _gsub(pat, -1, r.chars(), r.length());
+}
+
+inline int String::gsub(const char* pat, const char* r)
+{
+  return _gsub(pat, -1, r, -1);
+}
+
+
+inline String::operator const char*() const
+{ 
+  return str(chars());
+}
+
+inline  ostream& operator<<(ostream& s, const String& x)
+{
+#ifdef VMS
+   s << x.chars(); return s;
+#else
+  s.put(x.chars()); return s;
+#endif
+
+}
+
+// a zillion comparison operators
+
+inline int operator==(const String& x, const String& y) 
+{
+  return compare(x, y) == 0; 
+}
+
+inline int operator!=(const String& x, const String& y)
+{
+  return compare(x, y) != 0; 
+}
+
+inline int operator>(const String& x, const String& y)
+{
+  return compare(x, y) > 0; 
+}
+
+inline int operator>=(const String& x, const String& y)
+{
+  return compare(x, y) >= 0; 
+}
+
+inline int operator<(const String& x, const String& y)
+{
+  return compare(x, y) < 0; 
+}
+
+inline int operator<=(const String& x, const String& y)
+{
+  return compare(x, y) <= 0; 
+}
+
+inline int operator==(const String& x, const SubString&  y) 
+{
+  return compare(x, y) == 0; 
+}
+
+inline int operator!=(const String& x, const SubString&  y)
+{
+  return compare(x, y) != 0; 
+}
+
+inline int operator>(const String& x, const SubString&  y)      
+{
+  return compare(x, y) > 0; 
+}
+
+inline int operator>=(const String& x, const SubString&  y)
+{
+  return compare(x, y) >= 0; 
+}
+
+inline int operator<(const String& x, const SubString&  y) 
+{
+  return compare(x, y) < 0; 
+}
+
+inline int operator<=(const String& x, const SubString&  y)
+{
+  return compare(x, y) <= 0; 
+}
+
+inline int operator==(const String& x, const char* t) 
+{
+  return compare(x, t) == 0; 
+}
+
+inline int operator!=(const String& x, const char* t) 
+{
+  return compare(x, t) != 0; 
+}
+
+inline int operator>(const String& x, const char* t)  
+{
+  return compare(x, t) > 0; 
+}
+
+inline int operator>=(const String& x, const char* t) 
+{
+  return compare(x, t) >= 0; 
+}
+
+inline int operator<(const String& x, const char* t)  
+{
+  return compare(x, t) < 0; 
+}
+
+inline int operator<=(const String& x, const char* t) 
+{
+  return compare(x, t) <= 0; 
+}
+
+inline int operator==(const SubString& x, const String& y) 
+{
+  return compare(y, x) == 0; 
+}
+
+inline int operator!=(const SubString& x, const String& y)
+{
+  return compare(y, x) != 0;
+}
+
+inline int operator>(const SubString& x, const String& y)      
+{
+  return compare(y, x) < 0;
+}
+
+inline int operator>=(const SubString& x, const String& y)     
+{
+  return compare(y, x) <= 0;
+}
+
+inline int operator<(const SubString& x, const String& y)      
+{
+  return compare(y, x) > 0;
+}
+
+inline int operator<=(const SubString& x, const String& y)     
+{
+  return compare(y, x) >= 0;
+}
+
+inline int operator==(const SubString& x, const SubString&  y) 
+{
+  return compare(x, y) == 0; 
+}
+
+inline int operator!=(const SubString& x, const SubString&  y)
+{
+  return compare(x, y) != 0;
+}
+
+inline int operator>(const SubString& x, const SubString&  y)      
+{
+  return compare(x, y) > 0;
+}
+
+inline int operator>=(const SubString& x, const SubString&  y)
+{
+  return compare(x, y) >= 0;
+}
+
+inline int operator<(const SubString& x, const SubString&  y) 
+{
+  return compare(x, y) < 0;
+}
+
+inline int operator<=(const SubString& x, const SubString&  y)
+{
+  return compare(x, y) <= 0;
+}
+
+inline int operator==(const SubString& x, const char* t) 
+{
+  return compare(x, t) == 0; 
+}
+
+inline int operator!=(const SubString& x, const char* t) 
+{
+  return compare(x, t) != 0;
+}
+
+inline int operator>(const SubString& x, const char* t)  
+{
+  return compare(x, t) > 0; 
+}
+
+inline int operator>=(const SubString& x, const char* t) 
+{
+  return compare(x, t) >= 0; 
+}
+
+inline int operator<(const SubString& x, const char* t)  
+{
+  return compare(x, t) < 0; 
+}
+
+inline int operator<=(const SubString& x, const char* t) 
+{
+  return compare(x, t) <= 0; 
+}
+
+
+// a helper needed by at, before, etc.
+
+inline SubString String::_substr(int first, int l)
+{
+  if (first < 0 || (unsigned)(first + l) > length()) 
+    return SubString(_nilString, 0, 0) ;
+  else 
+    return SubString(*this, first, l);
+}
+
+
+#endif
+
+#endif

diff --git a/usr/src/lib/libg++/libg++/String.cc b/usr/src/lib/libg++/libg++/String.cc
new file mode 100644 (file)
index 0000000..a79a4de
--- /dev/null
+++ b/usr/src/lib/libg++/libg++/String.cc
@@ -0,0 +1,1312 @@
+/* 
+Copyright (C) 1988 Free Software Foundation
+    written by Doug Lea (dl@rocky.oswego.edu)
+
+This file is part of GNU CC.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY.  No author or distributor
+accepts responsibility to anyone for the consequences of using it
+or for whether it serves any particular purpose or works at all,
+unless he says so in writing.  Refer to the GNU CC General Public
+License for full details.
+
+Everyone is granted permission to copy, modify and redistribute
+GNU CC, but only under the conditions described in the
+GNU CC General Public License.   A copy of this license is
+supposed to have been given to you along with GNU CC so you
+can know your rights and responsibilities.  It should be in a
+file named COPYING.  Among other things, the copyright notice
+and this notice must be preserved on all copies.  
+*/
+
+/* 
+  String class implementation
+ */
+
+#ifdef __GNUG__
+#pragma implementation
+#endif
+#include <String.h>
+#include <std.h>
+#include <ctype.h>
+#include <values.h>
+#include <new.h>
+
+// extern "C" {
+#include <regex.h>
+// }
+
+volatile void String::error(const char* msg) const
+{
+  (void)((*lib_error_handler)("String", msg));
+}
+
+//  globals
+
+StrRep  _nilStrRep = { 0, 1, { 0 } }; // nil strings point here
+String _nilString;               // nil SubStrings point here
+
+
+
+
+/*
+ the following inline fcts are specially designed to work
+ in support of String classes, and are not meant as generic replacements
+ for libc "str" functions.
+
+ inline copy fcts -  I like left-to-right from->to arguments.
+ all versions assume that `to' argument is non-null
+
+ These are worth doing inline, rather than through calls because,
+ via procedural integration, adjacent copy calls can be smushed
+ together by the optimizer.
+*/
+
+// copy n bytes
+inline static void ncopy(const char* from, char* to, int n)
+{
+  if (from != to) while (--n >= 0) *to++ = *from++;
+}
+
+// copy n bytes, null-terminate
+inline static void ncopy0(const char* from, char* to, int n)
+{
+  if (from != to) 
+  {
+    while (--n >= 0) *to++ = *from++;
+    *to = 0;
+  }
+  else
+    to[n] = 0;
+}
+
+// copy until null
+inline static void scopy(const char* from, char* to)
+{
+  if (from != 0) while((*to++ = *from++) != 0);
+}
+
+// copy right-to-left
+inline static void revcopy(const char* from, char* to, short n)
+{
+  if (from != 0) while (--n >= 0) *to-- = *from--;
+}
+
+
+inline static int slen(const char* t) // inline  strlen
+{
+  if (t == 0)
+    return 0;
+  else
+  {
+    const char* a = t;
+    while (*a++ != 0);
+    return a - 1 - t;
+  }
+}
+
+// minimum & maximum representable rep size
+
+#define MAXStrRep_SIZE   ((1 << (SHORTBITS - 1)) - 1)
+#define MINStrRep_SIZE   16
+
+#ifndef MALLOC_MIN_OVERHEAD
+#define MALLOC_MIN_OVERHEAD  4
+#endif
+
+// The basic allocation primitive:
+// Always round request to something close to a power of two.
+// This ensures a bit of padding, which often means that
+// concatenations don't have to realloc. Plus it tends to
+// be faster when lots of Strings are created and discarded,
+// since just about any version of malloc (op new()) will
+// be faster when it can reuse identically-sized chunks
+
+inline static StrRep* Snew(int newsiz)
+{
+  unsigned int siz = sizeof(StrRep) + newsiz + MALLOC_MIN_OVERHEAD;
+  unsigned int allocsiz = MINStrRep_SIZE;
+  while (allocsiz < siz) allocsiz <<= 1;
+  allocsiz -= MALLOC_MIN_OVERHEAD;
+  if (allocsiz >= MAXStrRep_SIZE)
+    (*lib_error_handler)("String", "Requested length out of range");
+    
+  StrRep* rep = (StrRep *) new char[allocsiz];
+  rep->sz = allocsiz - sizeof(StrRep);
+  return rep;
+}
+
+// Do-something-while-allocating routines.
+
+// We live with two ways to signify empty Sreps: either the
+// null pointer (0) or a pointer to the nilStrRep.
+
+// We always signify unknown source lengths (usually when fed a char*)
+// via len == -1, in which case it is computed.
+
+// allocate, copying src if nonull
+
+StrRep* Salloc(StrRep* old, const char* src, int srclen, int newlen)
+{
+  if (old == &_nilStrRep) old = 0;
+  if (srclen < 0) srclen = slen(src);
+  if (newlen < srclen) newlen = srclen;
+  StrRep* rep;
+  if (old == 0 || newlen > old->sz)
+    rep = Snew(newlen);
+  else
+    rep = old;
+
+  rep->len = newlen;
+  ncopy0(src, rep->s, srclen);
+
+  if (old != rep && old != 0) delete old;
+
+  return rep;
+}
+
+// reallocate: Given the initial allocation scheme, it will
+// generally be faster in the long run to get new space & copy
+// than to call realloc
+
+StrRep* Sresize(StrRep* old, int newlen)
+{
+  if (old == &_nilStrRep) old = 0;
+  StrRep* rep;
+  if (old == 0)
+    rep = Snew(newlen);
+  else if (newlen > old->sz)
+  {
+    rep = Snew(newlen);
+    ncopy0(old->s, rep->s, old->len);
+    delete old;
+  }
+  else
+    rep = old;
+
+  rep->len = newlen;
+
+  return rep;
+}
+
+// like allocate, but we know that src is a StrRep
+
+StrRep* Scopy(StrRep* old, StrRep* s)
+{
+  if (old == &_nilStrRep) old = 0;
+  if (s == &_nilStrRep) s = 0;
+  if (old == s) 
+    return (old == 0)? &_nilStrRep : old;
+  else if (s == 0)
+  {
+    old->s[0] = 0;
+    old->len = 0;
+    return old;
+  }
+  else 
+  {
+    StrRep* rep;
+    int newlen = s->len;
+    if (old == 0 || newlen > old->sz)
+    {
+      if (old != 0) delete old;
+      rep = Snew(newlen);
+    }
+    else
+      rep = old;
+    rep->len = newlen;
+    ncopy0(s->s, rep->s, newlen);
+    return rep;
+  }
+}
+
+// allocate & concatenate
+
+StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen)
+{
+  if (old == &_nilStrRep) old = 0;
+  if (srclen < 0) srclen = slen(s);
+  if (tlen < 0) tlen = slen(t);
+  int newlen = srclen + tlen;
+  StrRep* rep;
+
+  if (old == 0 || newlen > old->sz || 
+      (t >= old->s && t < &(old->s[old->len]))) // beware of aliasing
+    rep = Snew(newlen);
+  else
+    rep = old;
+
+  rep->len = newlen;
+
+  ncopy(s, rep->s, srclen);
+  ncopy0(t, &(rep->s[srclen]), tlen);
+
+  if (old != rep && old != 0) delete old;
+
+  return rep;
+}
+
+// double-concatenate
+
+StrRep* Scat(StrRep* old, const char* s, int srclen, const char* t, int tlen,
+             const char* u, int ulen)
+{
+  if (old == &_nilStrRep) old = 0;
+  if (srclen < 0) srclen = slen(s);
+  if (tlen < 0) tlen = slen(t);
+  if (ulen < 0) tlen = slen(u);
+  int newlen = srclen + tlen + ulen;
+  StrRep* rep;
+  if (old == 0 || newlen > old->sz || 
+      (t >= old->s && t < &(old->s[old->len])) ||
+      (u >= old->s && u < &(old->s[old->len])))
+    rep = Snew(newlen);
+  else
+    rep = old;
+
+  rep->len = newlen;
+
+  ncopy(s, rep->s, srclen);
+  ncopy(t, &(rep->s[srclen]), tlen);
+  ncopy0(u, &(rep->s[srclen+tlen]), ulen);
+
+  if (old != rep && old != 0) delete old;
+
+  return rep;
+}
+
+// like cat, but we know that new stuff goes in the front of existing rep
+
+StrRep* Sprepend(StrRep* old, const char* t, int tlen)
+{
+  char* s;
+  int srclen;
+  if (old == &_nilStrRep || old == 0)
+  {
+    s = 0; old = 0; srclen = 0;
+  }
+  else
+  {
+    s = old->s; srclen = old->len;
+  }
+  if (tlen < 0) tlen = slen(t);
+  int newlen = srclen + tlen;
+  StrRep* rep;
+  if (old == 0 || newlen > old->sz || 
+      (t >= old->s && t < &(old->s[old->len])))
+    rep = Snew(newlen);
+  else
+    rep = old;
+
+  rep->len = newlen;
+
+  revcopy(&(s[srclen]), &(rep->s[newlen]), srclen+1);
+  ncopy(t, rep->s, tlen);
+
+  if (old != rep && old != 0) delete old;
+
+  return rep;
+}
+
+
+// string compare: first argument is known to be non-null
+
+inline static int scmp(const char* a, const char* b)
+{
+  if (b == 0)
+    return *a != 0;
+  else
+  {
+    signed char diff = 0;
+    while ((diff = *a - *b++) == 0 && *a++ != 0);
+    return diff;
+  }
+}
+
+
+inline static int ncmp(const char* a, int al, const char* b, int bl)
+{
+  int n = (al <= bl)? al : bl;
+  signed char diff;
+  while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
+  return al - bl;
+}
+
+int fcompare(const String& x, const String& y)
+{
+  const char* a = x.chars();
+  const char* b = y.chars();
+  int al = x.length();
+  int bl = y.length();
+  int n = (al <= bl)? al : bl;
+  signed char diff = 0;
+  while (n-- > 0)
+  {
+    char ac = *a++;
+    char bc = *b++;
+    if ((diff = ac - bc) != 0)
+    {
+      if (ac >= 'a' && ac <= 'z')
+        ac = ac - 'a' + 'A';
+      if (bc >= 'a' && bc <= 'z')
+        bc = bc - 'a' + 'A';
+      if ((diff = ac - bc) != 0)
+        return diff;
+    }
+  }
+  return al - bl;
+}
+
+// these are not inline, but pull in the above inlines, so are 
+// pretty fast
+
+int compare(const String& x, const char* b)
+{
+  return scmp(x.chars(), b);
+}
+
+int compare(const String& x, const String& y)
+{
+  return scmp(x.chars(), y.chars());
+}
+
+int compare(const String& x, const SubString& y)
+{
+  return ncmp(x.chars(), x.length(), y.chars(), y.length());
+}
+
+int compare(const SubString& x, const String& y)
+{
+  return ncmp(x.chars(), x.length(), y.chars(), y.length());
+}
+
+int compare(const SubString& x, const SubString& y)
+{
+  return ncmp(x.chars(), x.length(), y.chars(), y.length());
+}
+
+int compare(const SubString& x, const char* b)
+{
+  if (b == 0)
+    return x.length();
+  else
+  {
+    const char* a = x.chars();
+    int n = x.length();
+    signed char diff;
+    while (n-- > 0) if ((diff = *a++ - *b++) != 0) return diff;
+    return (*b == 0) ? 0 : -1;
+  }
+}
+
+/*
+ index fcts
+*/
+
+int String::search(int start, int sl, char c) const
+{
+  const char* s = chars();
+  if (sl > 0)
+  {
+    if (start >= 0)
+    {
+      const char* a = &(s[start]);
+      const char* lasta = &(s[sl]);
+      while (a < lasta) if (*a++ == c) return --a - s;
+    }
+    else
+    {
+      const char* a = &(s[sl + start + 1]);
+      while (--a >= s) if (*a == c) return a - s;
+    }
+  }
+  return -1;
+}
+
+int String::search(int start, int sl, const char* t, int tl) const
+{
+  const char* s = chars();
+  if (tl < 0) tl = slen(t);
+  if (sl > 0 && tl > 0)
+  {
+    if (start >= 0)
+    {
+      const char* lasts = &(s[sl - tl]);
+      const char* lastt = &(t[tl]);
+      const char* p = &(s[start]);
+
+      while (p <= lasts)
+      {
+        const char* x = p++;
+        const char* y = t;
+        while (*x++ == *y++) if (y >= lastt) return --p - s;
+      }
+    }
+    else
+    {
+      const char* firsts = &(s[tl - 1]);
+      const char* lastt =  &(t[tl - 1]);
+      const char* p = &(s[sl + start + 1]); 
+
+      while (--p >= firsts)
+      {
+        const char* x = p;
+        const char* y = lastt;
+        while (*x-- == *y--) if (y < t) return ++x - s;
+      }
+    }
+  }
+  return -1;
+}
+
+int String::match(int start, int sl, int exact, const char* t, int tl) const
+{
+  if (tl < 0) tl = slen(t);
+
+  if (start < 0)
+  {
+    start = sl + start - tl + 1;
+    if (start < 0 || (exact && start != 0))
+      return -1;
+  }
+  else if (exact && sl - start != tl)
+    return -1;
+
+  if (sl == 0 || tl == 0 || sl - start < tl || start >= sl)
+    return -1;
+
+  int n = tl;
+  const char* s = &(rep->s[start]);
+  while (--n >= 0) if (*s++ != *t++) return -1;
+  return tl;
+}
+
+void SubString::assign(StrRep* ysrc, const char* ys, int ylen)
+{
+  if (&S == &_nilString) return;
+
+  if (ylen < 0) ylen = slen(ys);
+  StrRep* targ = S.rep;
+  int sl = targ->len - len + ylen;
+
+  if (ysrc == targ || sl >= targ->sz)
+  {
+    StrRep* oldtarg = targ;
+    targ = Sresize(0, sl);
+    ncopy(oldtarg->s, targ->s, pos);
+    ncopy(ys, &(targ->s[pos]), ylen);
+    scopy(&(oldtarg->s[pos + len]), &(targ->s[pos + ylen]));
+    delete oldtarg;
+  }
+  else if (len == ylen)
+    ncopy(ys, &(targ->s[pos]), len);
+  else if (ylen < len)
+  {
+    ncopy(ys, &(targ->s[pos]), ylen);
+    scopy(&(targ->s[pos + len]), &(targ->s[pos + ylen]));
+  }
+  else
+  {
+    revcopy(&(targ->s[targ->len]), &(targ->s[sl]), targ->len-pos-len +1);
+    ncopy(ys, &(targ->s[pos]), ylen);
+  }
+  targ->len = sl;
+  S.rep = targ;
+}
+
+
+
+/*
+ * substitution
+ */
+
+
+int String::_gsub(const char* pat, int pl, const char* r, int rl)
+{
+  int nmatches = 0;
+  if (pl < 0) pl = slen(pat);
+  if (rl < 0) rl = slen(r);
+  int sl = length();
+  if (sl <= 0 || pl <= 0 || sl < pl)
+    return nmatches;
+  
+  const char* s = chars();
+
+  // prepare to make new rep
+  StrRep* nrep = 0;
+  int nsz = 0;
+  char* x = 0;
+
+  int si = 0;
+  int xi = 0;
+  int remaining = sl;
+
+  while (remaining >= pl)
+  {
+    int pos = search(si, sl, pat, pl);
+    if (pos < 0)
+      break;
+    else
+    {
+      ++nmatches;
+      int mustfit = xi + remaining + rl - pl;
+      if (mustfit >= nsz)
+      {
+        if (nrep != 0) nrep->len = xi;
+        nrep = Sresize(nrep, mustfit);
+        nsz = nrep->sz;
+        x = nrep->s;
+      }
+      pos -= si;
+      ncopy(&(s[si]), &(x[xi]), pos);
+      ncopy(r, &(x[xi + pos]), rl);
+      si += pos + pl;
+      remaining -= pos + pl;
+      xi += pos + rl;
+    }
+  }
+
+  if (nrep == 0)
+  {
+    if (nmatches == 0)
+      return nmatches;
+    else
+      nrep = Sresize(nrep, xi+remaining);
+  }
+
+  ncopy0(&(s[si]), &(x[xi]), remaining);
+  nrep->len = xi + remaining;
+
+  if (nrep->len <= rep->sz)   // fit back in if possible
+  {
+    rep->len = nrep->len;
+    ncopy0(nrep->s, rep->s, rep->len);
+    delete(nrep);
+  }
+  else
+  {
+    delete(rep);
+    rep = nrep;
+  }
+  return nmatches;
+}
+
+int String::_gsub(const Regex& pat, const char* r, int rl)
+{
+  int nmatches = 0;
+  int sl = length();
+  if (sl <= 0)
+    return nmatches;
+
+  if (rl < 0) rl = slen(r);
+
+  const char* s = chars();
+
+  StrRep* nrep = 0;
+  int nsz = 0;
+
+  char* x = 0;
+
+  int si = 0;
+  int xi = 0;
+  int remaining = sl;
+  int  pos, pl = 0;                              // how long is a regular expression?
+
+  while (remaining > 0)
+  {
+    pos = pat.search(s, sl, pl, si); // unlike string search, the pos returned here is absolute
+    if (pos < 0 || pl <= 0)
+      break;
+    else
+    {
+      ++nmatches;
+      int mustfit = xi + remaining + rl - pl;
+      if (mustfit >= nsz)
+      {
+        if (nrep != 0) nrep->len = xi;
+        nrep = Sresize(nrep, mustfit);
+        x = nrep->s;
+        nsz = nrep->sz;
+      }
+      pos -= si;
+      ncopy(&(s[si]), &(x[xi]), pos);
+      ncopy(r, &(x[xi + pos]), rl);
+      si += pos + pl;
+      remaining -= pos + pl;
+      xi += pos + rl;
+    }
+  }
+
+  if (nrep == 0)
+  {
+    if (nmatches == 0)
+      return nmatches;
+    else
+      nrep = Sresize(nrep, xi+remaining);
+  }
+
+  ncopy0(&(s[si]), &(x[xi]), remaining);
+  nrep->len = xi + remaining;
+
+  if (nrep->len <= rep->sz)   // fit back in if possible
+  {
+    rep->len = nrep->len;
+    ncopy0(nrep->s, rep->s, rep->len);
+    delete(nrep);
+  }
+  else
+  {
+    delete(rep);
+    rep = nrep;
+  }
+  return nmatches;
+}
+
+
+/*
+ * deletion
+ */
+
+void String::del(int pos, int len)
+{
+  if (pos < 0 || len <= 0 || pos + len > length()) return;
+  int nlen = length() - len;
+  int first = pos + len;
+  ncopy0(&(rep->s[first]), &(rep->s[pos]), length() - first);
+  rep->len = nlen;
+}
+
+void String::del(const Regex& r, int startpos)
+{
+  int mlen;
+  int first = r.search(chars(), length(), mlen, startpos);
+  del(first, mlen);
+}
+
+void String::del(const char* t, int startpos)
+{
+  int tlen = slen(t);
+  int p = search(startpos, length(), t, tlen);
+  del(p, tlen);
+}
+
+void String::del(const String& y, int startpos)
+{
+  del(search(startpos, length(), y.chars(), y.length()), y.length());
+}
+
+void String::del(const SubString& y, int startpos)
+{
+  del(search(startpos, length(), y.chars(), y.length()), y.length());
+}
+
+void String::del(char c, int startpos)
+{
+  del(search(startpos, length(), c), 1);
+}
+
+/*
+ * substring extraction
+ */
+
+
+SubString String::at(int first, int len)
+{
+  return _substr(first, len);
+}
+
+SubString String::operator() (int first, int len)
+{
+  return _substr(first, len);
+}
+
+SubString String::before(int pos)
+{
+  return _substr(0, pos);
+}
+
+SubString String::through(int pos)
+{
+  return _substr(0, pos+1);
+}
+
+SubString String::after(int pos)
+{
+  return _substr(pos + 1, length() - (pos + 1));
+}
+
+SubString String::from(int pos)
+{
+  return _substr(pos, length() - pos);
+}
+
+SubString String::at(const String& y, int startpos)
+{
+  int first = search(startpos, length(), y.chars(), y.length());
+  return _substr(first,  y.length());
+}
+
+SubString String::at(const SubString& y, int startpos)
+{
+  int first = search(startpos, length(), y.chars(), y.length());
+  return _substr(first, y.length());
+}
+
+SubString String::at(const Regex& r, int startpos)
+{
+  int mlen;
+  int first = r.search(chars(), length(), mlen, startpos);
+  return _substr(first, mlen);
+}
+
+SubString String::at(const char* t, int startpos)
+{
+  int tlen = slen(t);
+  int first = search(startpos, length(), t, tlen);
+  return _substr(first, tlen);
+}
+
+SubString String::at(char c, int startpos)
+{
+  int first = search(startpos, length(), c);
+  return _substr(first, 1);
+}
+
+SubString String::before(const String& y, int startpos)
+{
+  int last = search(startpos, length(), y.chars(), y.length());
+  return _substr(0, last);
+}
+
+SubString String::before(const SubString& y, int startpos)
+{
+  int last = search(startpos, length(), y.chars(), y.length());
+  return _substr(0, last);
+}
+
+SubString String::before(const Regex& r, int startpos)
+{
+  int mlen;
+  int first = r.search(chars(), length(), mlen, startpos);
+  return _substr(0, first);
+}
+
+SubString String::before(char c, int startpos)
+{
+  int last = search(startpos, length(), c);
+  return _substr(0, last);
+}
+
+SubString String::before(const char* t, int startpos)
+{
+  int tlen = slen(t);
+  int last = search(startpos, length(), t, tlen);
+  return _substr(0, last);
+}
+
+SubString String::through(const String& y, int startpos)
+{
+  int last = search(startpos, length(), y.chars(), y.length());
+  if (last >= 0) last += y.length();
+  return _substr(0, last);
+}
+
+SubString String::through(const SubString& y, int startpos)
+{
+  int last = search(startpos, length(), y.chars(), y.length());
+  if (last >= 0) last += y.length();
+  return _substr(0, last);
+}
+
+SubString String::through(const Regex& r, int startpos)
+{
+  int mlen;
+  int first = r.search(chars(), length(), mlen, startpos);
+  if (first >= 0) first += mlen;
+  return _substr(0, first);
+}
+
+SubString String::through(char c, int startpos)
+{
+  int last = search(startpos, length(), c);
+  if (last >= 0) last += 1;
+  return _substr(0, last);
+}
+
+SubString String::through(const char* t, int startpos)
+{
+  int tlen = slen(t);
+  int last = search(startpos, length(), t, tlen);
+  if (last >= 0) last += tlen;
+  return _substr(0, last);
+}
+
+SubString String::after(const String& y, int startpos)
+{
+  int first = search(startpos, length(), y.chars(), y.length());
+  if (first >= 0) first += y.length();
+  return _substr(first, length() - first);
+}
+
+SubString String::after(const SubString& y, int startpos)
+{
+  int first = search(startpos, length(), y.chars(), y.length());
+  if (first >= 0) first += y.length();
+  return _substr(first, length() - first);
+}
+
+SubString String::after(char c, int startpos)
+{
+  int first = search(startpos, length(), c);
+  if (first >= 0) first += 1;
+  return _substr(first, length() - first);
+}
+
+SubString String::after(const Regex& r, int startpos)
+{
+  int mlen;
+  int first = r.search(chars(), length(), mlen, startpos);
+  if (first >= 0) first += mlen;
+  return _substr(first, length() - first);
+}
+
+SubString String::after(const char* t, int startpos)
+{
+  int tlen = slen(t);
+  int first = search(startpos, length(), t, tlen);
+  if (first >= 0) first += tlen;
+  return _substr(first, length() - first);
+}
+
+SubString String::from(const String& y, int startpos)
+{
+  int first = search(startpos, length(), y.chars(), y.length());
+  return _substr(first, length() - first);
+}
+
+SubString String::from(const SubString& y, int startpos)
+{
+  int first = search(startpos, length(), y.chars(), y.length());
+  return _substr(first, length() - first);
+}
+
+SubString String::from(const Regex& r, int startpos)
+{
+  int mlen;
+  int first = r.search(chars(), length(), mlen, startpos);
+  return _substr(first, length() - first);
+}
+
+SubString String::from(char c, int startpos)
+{
+  int first = search(startpos, length(), c);
+  return _substr(first, length() - first);
+}
+
+SubString String::from(const char* t, int startpos)
+{
+  int tlen = slen(t);
+  int first = search(startpos, length(), t, tlen);
+  return _substr(first, length() - first);
+}
+
+
+
+/*
+ * split/join
+ */
+
+
+int split(const String& src, String results[], int n, const String& sep)
+{
+  String x = src;
+  const char* s = x.chars();
+  int sl = x.length();
+  int i = 0;
+  int pos = 0;
+  while (i < n && pos < sl)
+  {
+    int p = x.search(pos, sl, sep.chars(), sep.length());
+    if (p < 0)
+      p = sl;
+    results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
+    i++;
+    pos = p + sep.length();
+  }
+  return i;
+}
+
+int split(const String& src, String results[], int n, const Regex& r)
+{
+  String x = src;
+  const char* s = x.chars();
+  int sl = x.length();
+  int i = 0;
+  int pos = 0;
+  int p, matchlen;
+  while (i < n && pos < sl)
+  {
+    p = r.search(s, sl, matchlen, pos);
+    if (p < 0)
+      p = sl;
+    results[i].rep = Salloc(results[i].rep, &(s[pos]), p - pos, p - pos);
+    i++;
+    pos = p + matchlen;
+  }
+  return i;
+}
+
+
+#if defined(__GNUG__) && !defined(NO_NRV)
+
+String join(String src[], int n, const String& separator) return x;
+{
+  String sep = separator;
+  int xlen = 0;
+  for (int i = 0; i < n; ++i)
+    xlen += src[i].length();
+  xlen += (n - 1) * sep.length();
+
+  x.alloc(xlen);
+
+  int j = 0;
+  
+  for (i = 0; i < n - 1; ++i)
+  {
+    ncopy(src[i].chars(), &(x.rep->s[j]), src[i].length());
+    j += src[i].length();
+    ncopy(sep.chars(), &(x.rep->s[j]), sep.length());
+    j += sep.length();
+  }
+  ncopy0(src[i].chars(), &(x.rep->s[j]), src[i].length());
+}
+
+#else
+
+String join(String src[], int n, const String& separator)
+{
+  String x;
+  String sep = separator;
+  int xlen = 0;
+  for (int i = 0; i < n; ++i)
+    xlen += src[i].length();
+  xlen += (n - 1) * sep.length();
+
+  x.alloc(xlen);
+
+  int j = 0;
+  
+  for (i = 0; i < n - 1; ++i)
+  {
+    ncopy(src[i].chars(), &(x.rep->s[j]), src[i].length());
+    j += src[i].length();
+    ncopy(sep.chars(), &(x.rep->s[j]), sep.length());
+    j += sep.length();
+  }
+  ncopy0(src[i].chars(), &(x.rep->s[j]), src[i].length());
+  return x;
+}
+
+#endif
+  
+/*
+ misc
+*/
+
+    
+StrRep* Sreverse(StrRep* src, StrRep* dest)
+{
+  int n = src->len;
+  if (src != dest)
+    dest = Salloc(dest, src->s, n, n);
+  if (n > 0)
+  {
+    char* a = dest->s;
+    char* b = &(a[n - 1]);
+    while (a < b)
+    {
+      char t = *a;
+      *a++ = *b;
+      *b-- = t;
+    }
+  }
+  return dest;
+}
+
+
+StrRep* Supcase(StrRep* src, StrRep* dest)
+{
+  int n = src->len;
+  if (src != dest) dest = Salloc(dest, src->s, n, n);
+  char* p = dest->s;
+  char* e = &(p[n]);
+  for (; p < e; ++p) if (islower(*p)) *p = toupper(*p);
+  return dest;
+}
+
+StrRep* Sdowncase(StrRep* src, StrRep* dest)
+{
+  int n = src->len;
+  if (src != dest) dest = Salloc(dest, src->s, n, n);
+  char* p = dest->s;
+  char* e = &(p[n]);
+  for (; p < e; ++p) if (isupper(*p)) *p = tolower(*p);
+  return dest;
+}
+
+StrRep* Scapitalize(StrRep* src, StrRep* dest)
+{
+  int n = src->len;
+  if (src != dest) dest = Salloc(dest, src->s, n, n);
+
+  char* p = dest->s;
+  char* e = &(p[n]);
+  for (; p < e; ++p)
+  {
+    int at_word;
+    if (at_word = islower(*p))
+      *p = toupper(*p);
+    else 
+      at_word = isupper(*p) || isdigit(*p);
+
+    if (at_word)
+    {
+      while (++p < e)
+      {
+        if (isupper(*p))
+          *p = tolower(*p);
+        else if (!islower(*p) && !isdigit(*p))
+          break;
+      }
+    }
+  }
+  return dest;
+}
+
+#if defined(__GNUG__) && !defined(NO_NRV)
+
+String replicate(char c, int n) return w;
+{
+  w.rep = Sresize(w.rep, n);
+  char* p = w.rep->s;
+  while (n-- > 0) *p++ = c;
+  *p = 0;
+}
+
+String replicate(const String& y, int n) return w
+{
+  int len = y.length();
+  w.rep = Sresize(w.rep, n * len);
+  char* p = w.rep->s;
+  while (n-- > 0)
+  {
+    ncopy(y.chars(), p, len);
+    p += len;
+  }
+  *p = 0;
+}
+
+String common_prefix(const String& x, const String& y, int startpos) return r;
+{
+  const char* xchars = x.chars();
+  const char* ychars = y.chars();
+  const char* xs = &(xchars[startpos]);
+  const char* ss = xs;
+  const char* topx = &(xchars[x.length()]);
+  const char* ys = &(ychars[startpos]);
+  const char* topy = &(ychars[y.length()]);
+  for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
+  r.rep = Salloc(r.rep, ss, l, l);
+}
+
+String common_suffix(const String& x, const String& y, int startpos) return r;
+{
+  const char* xchars = x.chars();
+  const char* ychars = y.chars();
+  const char* xs = &(xchars[x.length() + startpos]);
+  const char* botx = xchars;
+  const char* ys = &(ychars[y.length() + startpos]);
+  const char* boty = ychars;
+  for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
+  r.rep = Salloc(r.rep, ++xs, l, l);
+}
+
+#else
+
+String replicate(char c, int n)
+{
+  String w;
+  w.rep = Sresize(w.rep, n);
+  char* p = w.rep->s;
+  while (n-- > 0) *p++ = c;
+  *p = 0;
+  return w;
+}
+
+String replicate(const String& y, int n)
+{
+  String w;
+  int len = y.length();
+  w.rep = Sresize(w.rep, n * len);
+  char* p = w.rep->s;
+  while (n-- > 0)
+  {
+    ncopy(y.chars(), p, len);
+    p += len;
+  }
+  *p = 0;
+  return w;
+}
+
+String common_prefix(const String& x, const String& y, int startpos)
+{
+  String r;
+  const char* xchars = x.chars();
+  const char* ychars = y.chars();
+  const char* xs = &(xchars[startpos]);
+  const char* ss = xs;
+  const char* topx = &(xchars[x.length()]);
+  const char* ys = &(ychars[startpos]);
+  const char* topy = &(ychars[y.length()]);
+  for (int l = 0; xs < topx && ys < topy && *xs++ == *ys++; ++l);
+  r.rep = Salloc(r.rep, ss, l, l);
+  return r;
+}
+
+String common_suffix(const String& x, const String& y, int startpos) 
+{
+  String r;
+  const char* xchars = x.chars();
+  const char* ychars = y.chars();
+  const char* xs = &(xchars[x.length() + startpos]);
+  const char* botx = xchars;
+  const char* ys = &(ychars[y.length() + startpos]);
+  const char* boty = ychars;
+  for (int l = 0; xs >= botx && ys >= boty && *xs == *ys ; --xs, --ys, ++l);
+  r.rep = Salloc(r.rep, ++xs, l, l);
+  return r;
+}
+
+#endif
+
+// IO
+
+istream& operator>>(istream& s, String& x)
+{
+  if (!s.readable())
+  {
+    s.set(_bad);
+    return s;
+  }
+  char ch;
+  int i = 0;
+  x.rep = Sresize(x.rep, 20);
+  s >> WS;
+  if (!s.good())
+  {
+    s.set(_bad);
+    return s;
+  }
+  while (s.get(ch))
+  {
+    if (isspace(ch))
+      break;
+    if (i >= x.rep->sz - 1)
+      x.rep = Sresize(x.rep, i+1);
+    x.rep->s[i++] = ch;
+  }
+  x.rep->s[i] = 0;
+  x.rep->len = i;
+  s.failif(i == 0);
+  return s;
+}
+
+int readline(istream& s, String& x, char terminator, int discard)
+{
+  if (!s.readable())
+  {
+    s.set(_bad);
+    return 0;
+  }
+  char ch;
+  int i = 0;
+  x.rep = Sresize(x.rep, 80);
+  while (s.get(ch))
+  {
+    if (ch != terminator || !discard)
+    {
+      if (i >= x.rep->sz - 1)
+        x.rep = Sresize(x.rep, i+1);
+      x.rep->s[i++] = ch;
+    }
+    if (ch == terminator)
+      break;
+  }
+  x.rep->s[i] = 0;
+  x.rep->len = i;
+  return i;
+}
+
+
+ostream& operator<<(ostream& s, const SubString& x)
+{ 
+  const char* a = x.chars();
+  const char* lasta = &(a[x.length()]);
+  while (a < lasta)
+    s.put(*a++);
+  return(s);
+}
+
+// from John.Willis@FAS.RI.CMU.EDU
+
+int String::freq(const SubString& y) const
+{
+  int found = 0;
+  for (int i = 0; i < length(); i++) 
+    if (match(i,length(),0,y.chars(), y.length())>= 0) found++;
+  return(found);
+}
+
+int String::freq(const String& y) const
+{
+  int found = 0;
+  for (int i = 0; i < length(); i++) 
+    if (match(i,length(),0,y.chars(),y.length()) >= 0) found++;
+  return(found);
+}
+
+int String::freq(const char* t) const
+{
+  int found = 0;
+  for (int i = 0; i < length(); i++) if (match(i,length(),0,t) >= 0) found++;
+  return(found);
+}
+
+int String::freq(char c) const
+{
+  int found = 0;
+  for (int i = 0; i < length(); i++) 
+    if (match(i,length(),0,&c,1) >= 0) found++;
+  return(found);
+}
+
+
+int String::OK() const
+{
+  int v = rep != 0;             // have a rep
+  v &= rep->len <= rep->sz;     // string within bounds
+  v &= rep->s[rep->len] == 0;   // null-terminated
+  if (!v) error("invariant failure");
+  return v;
+}
+
+int SubString::OK() const
+{
+  int v = S != 0;               // have a String;
+  v &= S.OK();                 // that is legal
+  v &= pos + len >= S.rep->len;// pos and len within bounds
+  if (!v) S.error("SubString invariant failure");
+  return v;
+}
+