A Java Language IDE

#include "stdafx.h"
#include "SuperStr.h"
#ifndef SS_STANDALONE
#include "Urror.hh"
#include "Associate.hh"
#endif
#include <locale>
#include <cstdarg>
#include <cfloat>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <strstream>
#include <limits>

// Super String implementation
// written by Phil Haubert and released into the public domain.

#ifndef SS_STANDALONE
#define ErrorMacro(error) UrrorMacro(error)
#else
#define ErrorMacro(error) throw error
#endif

static SS* null_string = 0;
SS& SS::nullref = *null_string;
const char SS::nullchar = 0;
const Pair<int> SS::nomatch (SS::notfound, SS::notfound);
char const * SS::formatStringLongLong = "%I64d";
char const * SS::formatStringULongLong = "%I64u";

const SS::FindFunc SS::whitespace (whiteP);
const SS::FindFunc SS::blackspace (blackP);
const SS::FindFunc SS::lowercase (lowerP);
const SS::FindFunc SS::uppercase (upperP);
const SS::FindFunc SS::alpha (alphaP);
const SS::FindFunc SS::digit (digitP);
const SS::FindFunc SS::alphanumeric (alphanumP);
const SS::FindFunc SS::punct (punctP);
const SS::FindFunc SS::printable (printableP);
const SS::FindFunc SS::hexdigit (hexDigitP);
const SS::FindFunc SS::cntrl (cntrlP);
const SS::FindFunc SS::graph (graphP);
const SS::FindBool SS::findtrue (true);
const SS::FindBool SS::findfalse (false);
const SS::FindBool SS::anychar (true, 1);
const SS::FindPosition SS::frontposition (0);
const SS::FindPosition SS::backposition (maxindex);
const SS::FindOr SS::endofline (FindSequence(anychar,FindString("\015\012")),FindSequence(anychar,FindChar('\012')),FindSequence(anychar,FindString("\012\015")),FindSequence(anychar,FindChar('\015')),backposition);
const SS::FindDelimit SS::singlequotedelimit('\'');
const SS::FindDelimit SS::doublequotedelimit('"');
const SS::FindDelimit SS::parendelimit('(',')');

SS::SS ()                      { _zero(); assign ("");  }
SS::SS (SS   const & s)        { _zero(); assign (s);   }
SS::SS (void const * v, int n) { _zero(); assign (v,n); }

SS::SS (DoNothing) { _zero(); }

SS::Buffer::Buffer (void const * start, int n) : _isAlloc (false), _start(start), _n(n), _fillValue(0)
{
}

SS::Buffer::Buffer (int n, SS const & fillvalue) : _isAlloc (true), _start(0), _n(n), _fillValue(new SS(fillvalue))
{
}

SS::Buffer::Buffer (Buffer const & b)
{
	copy (b);
}

SS::Buffer& SS::Buffer::operator = (Buffer const & b)
{
	delete _fillValue;
	copy (b);
	return *this;
}

void SS::Buffer::copy (Buffer const & b)
{
	_n = b._n;
	_start = b._start;
	_fillValue = new SS (*b._fillValue);
	_isAlloc = b._isAlloc;
}

SS::Buffer::~Buffer ()
{
	delete _fillValue;
}

void const * SS::Buffer::getStart () const
{
	return _start;
}

int SS::Buffer::getSize () const
{
	return _n;
}

SS SS::Buffer::getFillValue () const
{
	return _fillValue ? SS(*_fillValue) : SS("");
}

bool SS::Buffer::getAlloc () const
{
	return _isAlloc;
}

SS::~SS ()
{
	destroy();
}

void SS::destroy()
{
	if (isAlloc()) delete [] _rep;
}

SS SS::clone () const
{
	return get (0, _len);
}

SS& SS::erase ()
{
	_leng (0);
	return *this;
}

SS& SS::buffer (int n)
{
	_leng (n);
	return *this;
}

SS& SS::resize (int n) {
	int len = length();
	if (n <= len) {
		// shrinking requires no copying
		zero (n, fullength);
		_len = n;
	} else {
		// growing copies and zero fills
		checkFlags();
		char* ex = extract();
		bool alloc_ex = isAlloc();
		buffer (n);
		copy (_rep, ex, len);
		if (alloc_ex) delete [] ex;
		zero (len, fullength);
		_null();
		checkFlags();
	}
	return *this;
}

SS& SS::buffer (void const * v, int n)
{
	destroy();
	_zero();
	_rep = reinterpret_cast<char*>(const_cast<void*>(v));
	_len = n;
	setNoAlloc();
	setNoRef();
	checkFlags();
	return *this;
}

SS& SS::resizeToNullTerminator ()
{
	int pos = findNext (nullchar);
	if (pos != notfound) resize(pos);
	return *this;
}

char & SS::firstChar ()
{
	return at (0);
}

char const & SS::firstChar () const
{
	return at (0);
}

char & SS::lastChar ()
{
	return at (_len-1);
}

char const & SS::lastChar () const
{
	return at (_len-1);
}

SS SS::makeHeadSample () const
{
	SS ret = head (HeadSample);
	if (ret.length() != length()) ret += "...";
	return ret;
}

SS SS::head (int len) const
{
	return get (0, len);
}

SS SS::tail (int len) const
{
	lenAdjust (len);
	return get (_len - len, len);
}

SS SS::get (int beg, int len) const
{
	adjust (beg, len);
	SS ret ((Buffer)len);
	copy (ret, _rep+beg, len);
	return ret;
}

SS SS::get (Pair<int> const & beglen) const
{
	return get (beglen._0, beglen._1);
}

SS SS::get (std::vector< Pair<int> > const & beglen) const
{
	int n = 0;
	std::vector< Pair<int> > v (beglen);
	{for (int i=0; i<v.size(); i++) {
		adjust (v[i]._0, v[i]._1);
		n += v[i]._1;
	}}
	SS ret ((Buffer)n);
	n = 0;
	{for (int i=0; i<v.size(); i++) {
		ret.set (*this, n, v[i]);
		n += v[i]._1;
	}}
	return ret;
}

std::vector<SS>& SS::get (std::vector<SS>& s, std::vector< Pair<int> > const & beglen) const
{
	s = std::vector<SS> (beglen.size());
	{for (int i=0; i<s.size(); i++) {
		s[i] = get (beglen[i]);
	}}
	return s;
}

SS SS::getFrom (int beg) const
{
	adjust (beg);
	return get (beg, _len-beg);
}

SS& SS::reverse (int beg, int len)
{
	adjust (beg, len);
	{for (int i=0; i<len/2; i++) {
		swap (beg+i, beg+len-i-1);
	}}
	return *this;
}

SS& SS::reverse (Pair<int> const & beglen)
{
	return reverse (beglen._0, beglen._1);
}

SS& SS::reverse (std::vector< Pair<int> > const & beglen)
{
	{for (int i=0; i<beglen.size(); i++) {
		reverse (beglen[i]);
	}}
	return *this;
}

SS& SS::itemReverse (std::vector< Pair<int> > const & beglen)
{
	std::vector<SS> s;
	get (s, beglen);
	std::reverse (s.begin(), s.end());
	replaceRange (s, beglen);
	return *this;
}

SS& SS::tailReverse (int len)
{
	lenAdjust (len);
	return reverse (_len-len, len);
}

SS& SS::sort (int beg, int len)
{
	adjust (beg, len);
	std::sort (_rep+beg, _rep+beg+len);
	return *this;
}

SS& SS::sort (Pair<int> const & beglen)
{
	return sort (beglen._0, beglen._1);
}

SS& SS::sort (std::vector< Pair<int> > const & beglen)
{
	{for (int i=0; i<beglen.size(); i++) {
		sort (beglen[i]);
	}}
	return *this;
}

SS& SS::itemSort (std::vector< Pair<int> > const & beglen)
{
	std::vector<SS> s;
	get (s, beglen);
	std::sort (s.begin(), s.end());
	replaceRange (s, beglen);
	return *this;
}

SS& SS::tailSort (int len)
{
	lenAdjust (len);
	return sort (_len-len, len);
}

SS& SS::set (SS const & s, int pos, int beg, int len)
{
	if (adjust3 (s, pos, beg, len)) {
		copy (_rep+pos, s._rep+beg, len);
	}
	return *this;
}

SS& SS::set (SS const & s, int pos)
{
	return set (s, pos, 0, s._len);
}

SS& SS::set (SS const & s, int pos, Pair<int> const & beglen)
{
	return set (s, pos, beglen._0, beglen._1);
}

SS& SS::set (SS const & s, std::vector<int> const & pos)
{
	{for (int i=0; i<pos.size(); i++) {
		set (s, pos[i]);
	}}
	return *this;
}

SS& SS::set (std::vector<SS> const & s, std::vector<int> const & pos)
{
	{for (int i=0; i<pos.size(); i++) {
		if (!s.empty()) set (s[i%s.size()], pos[i]);
	}}
	return *this;
}

static inline int chooseSSVectElement (std::vector<SS> const & s, int i)
{
	if (i>=s.size()) return i%s.size();
	return i;
}

// channel the various multiple operations that resize into common code
// don't even try with the pointers to overloaded members
#define resizeOpHelper_a_SS(ss,v,s,f,x) \
{for (int i=v.size()-1; i>=0; i--) ss->f(s,v[i]); }

#define resizeOpHelper_a_VectSS(ss,v,s,f,x)              \
if (s.size()==0) {                                       \
	SS ns;                                               \
	{for (int i=v.size()-1; i>=0; i--) ss->f(ns,v[i]); } \
} else {                                                 \
	{for (int i=v.size()-1; i>=0; i--) ss->f(s[chooseSSVectElement(s,i)],v[i]); }}

#define resizeOpHelper_a_ReplSS(ss,v,s,f,x) \
{for (int i=v.size()-1; i>=0; i--) ss->f(x,s,v[i]); }

#define resizeOpHelper_b_SS(ss,v,s,f,x)      \
std::vector<int> o; SS::sortBegLenVect(v,o); \
{for (int i=v.size()-1; i>=0; i--) ss->f(s,v[o[i]]); }

#define resizeOpHelper_b_VectSS(ss,v,s,f,x)                 \
std::vector<int> o; SS::sortBegLenVect(v,o);                \
if (s.size()==0) {                                          \
	SS ns;                                                  \
	{for (int i=v.size()-1; i>=0; i--) ss->f(ns,v[o[i]]); } \
} else {                                                    \
	{for (int i=v.size()-1; i>=0; i--) ss->f(s[chooseSSVectElement(s,o[i])],v[o[i]]); }}

#define resizeOpHelper_b_ReplSS(ss,v,s,f,x)  \
std::vector<int> o; SS::sortBegLenVect(v,o); \
{for (int i=v.size()-1; i>=0; i--) ss->f(x,s,v[o[i]]); }

#define resizeOpHelper(ss,vect,s,f,a,vtype,stype,x)                  \
std::vector< vtype > v = vect;                                       \
{for (int i=0; i<v.size(); i++) a(v[i]); }                           \
if (SS::alreadySorted (v)) { resizeOpHelper_a_##stype(ss,v,s,f,x); } \
else                       { resizeOpHelper_b_##stype(ss,v,s,f,x); }

SS& SS::cut (SS& s, int beg, int len)
{
	adjust (beg, len);
	s = get (beg, len);
	if (beg==0) {
		if (len==_len) {
			*this = "";
		} else {
			*this = getRegion (len,_len-len);
		}
	} else {
		if (len==_len) {
			*this = getRegion (0, beg);
		} else {
			*this = getRegion (0, beg) + getRegion (beg+len,_len-len-beg);
		}
	}
	return s;
}

SS& SS::cut (SS& s, Pair<int> const & beglen)
{
	return cut (s, beglen._0, beglen._1);
}

SS SS::cut (int beg, int len)
{
	SS ret;
	return cut (ret, beg, len);
}

SS SS::cut (Pair<int> const & beglen)
{
	return cut (beglen._0, beglen._1);
}

std::vector<SS>& SS::cut (std::vector<SS>& s, std::vector< Pair<int> > const & beglen)
{
	s = std::vector<SS>(beglen.size());
	resizeOpHelper(this,beglen,s,cut,adjust,Pair<int>,VectSS,0);
	return s;
}

SS SS::cutFrom (int beg)
{
	adjust (beg);
	return cut (beg, _len-beg);
}

SS& SS::paste (SS const & s, int pos, int beg, int len)
{
	pasteAdjust (pos);
	s.adjust (beg, len);
	if (pos==0) {
		if (beg==0 && len==s._len) {
			*this = s + *this;
		} else {
			*this = s.getRegion (beg,len) + *this;
		}
	} else if (pos==_len) {
		if (beg==0 && len==s._len) {
			*this = *this + s;
		} else {
			*this = *this + s.getRegion (beg,len);
		}
	} else {
		if (beg==0 && len==s._len) {
			*this = getRegion (0,pos) + s + getRegion (pos,_len-pos);
		} else {
			*this = getRegion (0,pos) + s.getRegion (beg,len) + getRegion (pos,_len-pos);
		}
	}
	return *this;
}

SS& SS::paste (SS const & s, int pos)
{
	return paste (s, pos, 0, s._len);
}

SS& SS::paste (SS const & s, int pos, Pair<int> const & beglen)
{
	return paste (s, pos, beglen._0, beglen._1);
}

SS& SS::paste (SS const & s, std::vector<int> const & pos)
{
	resizeOpHelper(this,pos,s,paste,pasteAdjust,int,SS,0);
	return *this;
}

SS& SS::paste (std::vector<SS> const & s, std::vector<int> const & pos)
{
	resizeOpHelper(this,pos,s,paste,pasteAdjust,int,VectSS,0);
	return *this;
}

SS& SS::fill (char c, int beg, int len)
{
	adjust (beg, len);
	fill (_rep+beg, c, len);
	return *this;
}

SS& SS::fill (char c, Pair<int> const & beglen)
{
	return fill (c, beglen._0, beglen._1);
}

SS& SS::fill (char c, std::vector< Pair<int> > const & beglen)
{
	{for (int i=0; i<beglen.size(); i++) {
		fill (c, beglen[i]);
	}}
	return *this;
}

SS& SS::repeat (SS const & s, int beg, int len)
{
	int beg0 = translateIndex(beg);
	adjust (beg, len);
	if (s._len == 1) {
		fill (_rep+beg, s[0], len);
	} else {
		int fillsize = s._len;
		// shift pattern to accommodate out of range beg
		int begchars = (beg0-beg) % fillsize;
		if (begchars<0) begchars += fillsize;
		int begchars_start = fillsize-begchars;
		if (begchars>len) begchars = len;
		len -= begchars;
		int nunits = len/fillsize;
		int endchars = len - nunits*fillsize;
		if (begchars) {
			set (s, beg, begchars_start, begchars);
		}
		beg += begchars;
		{for (int i=0; i<nunits; i++) {
			set (s, beg + i*fillsize);
		}}
		if (endchars) {
			set (s, beg + nunits*fillsize, 0, endchars);
		}
	}
	return *this;
}

SS& SS::repeat (SS const & s, Pair<int> const & beglen)
{
	return repeat (s, beglen._0, beglen._1);
}

SS& SS::repeat (SS const & s, std::vector< Pair<int> > const & beglen)
{
	{for (int i=0; i<beglen.size(); i++) {
		repeat (s, beglen[i]);
	}}
	return *this;
}

SS& SS::zero ()
{
	return zero (nullchar, _len);
}

SS& SS::zero (int beg, int len)
{
	return fill (nullchar, beg, len);
}

int SS::compareBool (bool a, bool b)
{
	if (a == b) return 0;
	if (a) return 1;
	return -1;
}

int SS::compareChar (char b) const
{
	char s[1];
	s[0]=b;
	return compare (_rep, _len, s, 1);
}

int SS::compare (SS const & s) const { return compare (_rep, _len, s._rep, s._len); }
int SS::compare (string const & s) const { return compareString (_rep, _len, s); }
int SS::compare (std::vector<char> const & v) const { return compareVector (_rep, _len, v); }
int SS::compare (char const * s) const { return compare (_rep, _len, s, strLen(s)); }
int SS::compare (unsigned char const * s) const { return compare (_rep, _len, s, strLen(s)); }
int SS::compare (signed char const * s) const { return compare (_rep, _len, s, strLen(s)); }
int SS::compare (void const * v, int n) const { return compare (_rep, _len, v, n); }
int SS::compare (char          v) const { return compareChar (v); }
int SS::compare (unsigned char v) const { return compareChar (static_cast<char>(v)); }
int SS::compare (signed char   v) const { return compareChar (static_cast<char>(v)); }
int SS::compare (bool           v) const { return compareBool (toBool(),v); }
int SS::compare (short          v) const { return compareNumeric (toShort(),v); }
int SS::compare (unsigned short v) const { return compareNumeric (toUShort(),v); }
int SS::compare (int            v) const { return compareNumeric (toInt(),v); }
int SS::compare (unsigned int   v) const { return compareNumeric (toUInt(),v); }
int SS::compare (long           v) const { return compareNumeric (toLong(),v); }
int SS::compare (unsigned long  v) const { return compareNumeric (toULong(),v); }
int SS::compare (LongLong       v) const { return compareNumeric (toLongLong(),v); }
int SS::compare (ULongLong      v) const { return compareNumeric (toULongLong(),v); }

template <class T> static inline int compareDouble (T a, T b)
{
	T e = 3*std::numeric_limits<T>::epsilon();
	if (b == 0.0) {
		if (a > 0.0) return 1;
		if (a < 0.0) return -1;
		return 0;
	}
	T q = a/b;
	if (q<0) {
		if (a<0) return -1;
		return 1;
	}
	if (a<0) {
		if (q > 1.+e) return -1;
		if (q < 1.-e) return 1;
		return 0;
	}
	if (q > 1.+e) return 1;
	if (q < 1.-e) return -1;
	return 0;
}

int SS::compare (float v) const
{
//	return compareDouble (toFloat(), v, 3*FLT_EPSILON);
	return compareDouble (toFloat(), v);
}

int SS::compare (double v) const
{
//	return compareDouble (toDouble(), v, 3*DBL_EPSILON);
	return compareDouble (toDouble(), v);
}

int SS::compare (long double v) const
{
	return compareDouble (toLongDouble(), v);
}

int SS::findNext (Find const & finder, int beg, SS& result) const
{
	return doFind (finder, beg, result, 1);
}

int SS::findPrev (Find const & finder, int beg, SS& result) const
{
	return doFind (finder, beg, result, -1);
}

int SS::findNext (SS const & sequence, int beg, SS& result) const
{
	return doFindString (sequence, beg, result, 1);
}

int SS::findPrev (SS const & sequence, int beg, SS& result) const
{
	return doFindString (sequence, beg, result, -1);
}

int SS::findNextOf (SS const & charset, int beg, SS& result) const
{
	return doFind (FindSet(charset), beg, result, 1);
}

int SS::findPrevOf (SS const & charset, int beg, SS& result) const
{
	return doFind (FindSet(charset), beg, result, -1);
}

int SS::findNextNoCase (SS const & sequence, int beg, SS& result) const
{
	return doFind (FindStringNoCase (sequence), beg, result, 1);
}

int SS::findPrevNoCase (SS const & sequence, int beg, SS& result) const
{
	return doFind (FindStringNoCase (sequence), beg, result, -1);
}

Pair<int> SS::findNextMatch (SS const & sequence, int beg) const
{
	return doFindStringMatch (sequence, beg, 1);
}

Pair<int> SS::findPrevMatch (SS const & sequence, int beg) const
{
	return doFindStringMatch (sequence, beg, -1);
}

Pair<int> SS::findNextMatch (Find const & finder, int beg) const
{
	return doFindMatch (finder, beg, 1);
}

Pair<int> SS::findPrevMatch (Find const & finder, int beg) const
{
	return doFindMatch (finder, beg, -1);
}

Pair<int> SS::findNextNoCaseMatch (SS const & sequence, int beg) const
{
	return doFindMatch (FindStringNoCase (sequence), beg, 1);
}

Pair<int> SS::findPrevNoCaseMatch (SS const & sequence, int beg) const
{
	return doFindMatch (FindStringNoCase (sequence), beg, -1);
}

// a macro because SubSS is private
#define findSubStringHelper(t,beg,inc) \
int len=0; \
int pos = find (t, beg, &len, fullength, inc); \
if (pos < 0) ErrorMacro(ErrorNotFound("SS::findString - match not found in \""+makeHeadSample()+"\"")); \
return sub (pos, len);

SS SS::findNextString (SS const & sequence, int beg) const
{
	findSubStringHelper (sequence, beg, 1);
}

SS SS::findPrevString (SS const & sequence, int beg) const
{
	findSubStringHelper (sequence, beg, -1);
}

SS SS::findNextString (Find const & finder, int beg) const
{
	findSubStringHelper (finder, beg, 1);
}

SS SS::findPrevString (Find const & finder, int beg) const
{
	findSubStringHelper (finder, beg, -1);
}

SS::SubSS SS::findNextSubString (SS const & sequence, int beg)
{
	findSubStringHelper (sequence, beg, 1);
}

SS::SubSS SS::findPrevSubString (SS const & sequence, int beg)
{
	findSubStringHelper (sequence, beg, -1);
}

SS::SubSS SS::findNextSubString (Find const & finder, int beg)
{
	findSubStringHelper (finder, beg, 1);
}

SS::SubSS SS::findPrevSubString (Find const & finder, int beg)
{
	findSubStringHelper (finder, beg, -1);
}

bool SS::match (SS const & sequence, int pos, SS& result) const
{
	if (&result != &nullref) result = "";
	if (!matchAdjust (pos)) return false;
	bool ret = matchString (sequence._rep, sequence._len, pos);
	if (ret && &result != &nullref) result = get (pos, sequence._len);
	return ret;
}

bool SS::match (Find const & finder, int pos, SS& result) const
{
	int len;
	if (&result != &nullref) result = "";
	if (!matchAdjust (pos)) return false;
	bool ret = finder.found (*this, pos, len);
	if (ret && &result != &nullref) result = get (pos, len);
	return ret;
}

int SS::findChar (char c, int beg, int end, int inc) const
{
	if (inc==1) {
		int res = findNext (_rep+beg, c, end-beg+1);
		if (res>=0) return beg + res;
	} else if (inc>0) {
		{for (int i=beg; i<=end; i+=inc) {
			if (_rep[i] == c) return i;
		}}
	} else if (inc<0) {
		{for (int i=beg; i>=end; i+=inc) {
			if (_rep[i] == c) return i;
		}}
	}
	return notfound;
}

bool SS::matchString (char const * rep, int len, int pos) const
{
	if (pos <= _len - len) {
		{for (int i=0; i<len; i++) {
			if (_rep[pos+i] != rep[i]) return false;
		}}
		return true;
	}
	return false;
}

int SS::doFind (Find const & finder, int beg, SS& result, int inc) const
{
	if (&result != &nullref) result = "";
	int len=0;
	int ret = find (finder, beg, &len, fullength, inc);
	if (ret != notfound && &result != &nullref) result = get (ret, len);
	return ret;
}

int SS::doFindString (SS const & s, int beg, SS& result, int inc) const
{
	if (&result != &nullref) result = "";
	int ret = findString (s, beg, fullength, inc);
	if (ret != notfound && &result != &nullref) result = get (ret, s._len);
	return ret;
}

Pair<int> SS::doFindMatch (Find const & finder, int beg, int inc) const
{
	int len=0;
	int pos = find (finder, beg, &len, fullength, inc);
	return pos == notfound ? nomatch : Pair<int> (pos,len);
}

Pair<int> SS::doFindStringMatch (SS const & s, int beg, int inc) const
{
	int pos = findString (s, beg, fullength, inc);
	return pos == notfound ? nomatch : Pair<int> (pos,s._len);
}

int SS::findString (SS const & s, int beg, int end, int inc) const
{
	int ret = notfound;
	try {
		if (!findCheck (beg, end, inc)) return notfound;
		modAdjust (beg, end, inc);
		if (s._len==1) {
			ret = findChar (s[0], beg, end, inc);
		} else if (s._len>0) {
			ret = findStringHelper (s, beg, end, inc);
		}
	} catch (Error) {
	}
	return ret;
}

int SS::findStringHelper (SS const & s, int beg, int end, int inc) const
{
	int pos=beg;
	int n=s._len;
	while ((pos = findChar (s[0], pos, end, inc)) != notfound) {
		if (inc > 0 && pos > _len-n) break;
		if (n == 1) return pos;
		if (matchString (s._rep+1, n-1, pos+1)) return pos;
		pos += inc;
		if (inc < 0 && pos < end) break;
	}
	return notfound;
}

int SS::findFinder (Find const & finder, int beg, int end, int inc, int* len) const
{
	int ret = notfound;
	int leng=0;
	if (inc>0) {
		{for (int i=beg; i<=end; i+=inc) {
			if (finder.found (*this, i, leng)) {
				ret = i;	
				break;
			}
		}}
	} else if (inc<0) {
		{for (int i=beg; i>=end; i+=inc) {
			if (finder.found (*this, i, leng)) {
				ret = i;
				break;
			}
		}}
	}
	if (len) *len = leng;
	return ret;
}

int SS::find (Find const & finder, int beg, int* len, int end, int inc) const
{
	int ret = notfound;
	int leng=0;
	if (len) *len = 0;
	try {
		if (!findCheck (beg, end, inc)) return notfound;
		modAdjust (beg, end, inc);
		if (typeid (finder) == typeid (FindChar)) {
			leng=1;
			char c = dynamic_cast<FindChar const &>(finder)._c;
			ret = findChar (c, beg, end, inc);
		} else if (typeid (finder) == typeid (FindString)) {
			SS const & sequence = *(dynamic_cast<FindString const &>(finder)._str);
			leng = sequence.size();
			if (leng==1) {
				char c = sequence._rep[0];
				ret = findChar (c, beg, end, inc);
			} else if (leng>0) {
				ret = findStringHelper (sequence, beg, end, inc);
			}
		} else if (typeid (finder) == typeid (FindSet)) {
			SS const & set = *(dynamic_cast<FindSet const &>(finder)._set);
			leng = 1;
			int set_size = set._len;
			if (set_size==1) {
				char c = set._rep[0];
				ret = findChar (c, beg, end, inc);
			} else if (set_size>0) {
				ret = findFinder (finder, beg, end, inc, &leng);
			}
		} else {
			ret = findFinder (finder, beg, end, inc, &leng);
		}
	} catch (Error) {
	}
	if (len) *len = leng;
	return ret;
}

int SS::rfind (Find const & finder, int beg, int* len, int end) const
{
	return find (finder, beg, len, end, -1);
}

int SS::find (SS const & sequence, int beg, int* len, int end, int inc) const
{
	return find (FindString(sequence), beg, len, end, inc);
}

int SS::rfind (SS const & sequence, int beg, int* len, int end) const
{
	return find (FindString(sequence), beg, len, end, -1);
}

template <class T>
static inline bool containsHelper0 (SS const * s, T const & t, int beg, int len)
{
	return s->getRegion (beg, len).findNext (t) >= 0;
}

template <class T>
static inline bool containsHelper1 (SS const * s, T const & t, std::vector< Pair<int> > const & beglen)
{
	{for (int i=0; i<beglen.size(); i++) {
		if (containsHelper0 (s, t, beglen[i]._0, beglen[i]._1)) return true;
	}}
	return false;
}

bool SS::contains (SS const & sequence, int beg, int len) const
{
	return containsHelper0 (this, sequence, beg, len);
}

bool SS::contains (Find const & finder, int beg, int len) const
{
	return containsHelper0 (this, finder, beg, len);
}

bool SS::contains (SS const & sequence, Pair<int> const & beglen) const
{
	return contains (sequence, beglen._0, beglen._1);
}

bool SS::contains (Find const & finder, Pair<int> const & beglen) const
{
	return contains (finder, beglen._0, beglen._1);
}

bool SS::contains (SS const & sequence, std::vector< Pair<int> > const & beglen) const
{
	return containsHelper1 (this, sequence, beglen);
}

bool SS::contains (Find const & finder, std::vector< Pair<int> > const & beglen) const
{
	return containsHelper1 (this, finder, beglen);
}

template <class T>
static inline int populationHelper0 (SS const * s, T const & t, int beg, int len)
{
	int n=0;
	int pos=0;
	SS str = s->getRegion (beg, len);
	SS result;
	while ( (pos = str.findNext (t, pos, result)) >= 0) {
		n++;
		pos += result.length();
	}
	return n;
}

template <class T>
static inline int populationHelper1 (SS const * s, T const & t, std::vector< Pair<int> > const & beglen)
{
	int ret = 0;
	{for (int i=0; i<beglen.size(); i++) {
		ret += populationHelper0 (s, t, beglen[i]._0, beglen[i]._1);
	}}
	return ret;
}

int SS::population (SS const & sequence, int beg, int len) const
{
	return populationHelper0 (this, sequence, beg, len);
}

int SS::population (Find const & finder, int beg, int len) const
{
	return populationHelper0 (this, finder, beg, len);
}

int SS::population (SS const & sequence, Pair<int> const & beglen) const
{
	return population (sequence, beglen._0, beglen._1);
}

int SS::population (Find const & finder, Pair<int> const & beglen) const
{
	return population (finder, beglen._0, beglen._1);
}

int SS::population (SS const & sequence, std::vector< Pair<int> > const & beglen) const
{
	return populationHelper1 (this, sequence, beglen);
}

int SS::population (Find const & finder, std::vector< Pair<int> > const & beglen) const
{
	return populationHelper1 (this, finder, beglen);
}

SS& SS::remove (SS const & oldseq, int beg, int len)
{
	return replace (oldseq, "", beg, len);
}

SS& SS::remove (Find const & finder, int beg, int len)
{
	return replace (finder, "", beg, len);
}

SS& SS::remove (SS const & oldseq, Pair<int> const & beglen)
{
	return replace (oldseq, "", beglen);
}

SS& SS::remove (Find const & finder, Pair<int> const & beglen)
{
	return replace (finder, "", beglen);
}

SS& SS::remove (SS const & oldseq, std::vector< Pair<int> > const & beglen)
{
	return replace (oldseq, "", beglen);
}

SS& SS::remove (Find const & finder, std::vector< Pair<int> > const & beglen)
{
	return replace (finder, "", beglen);
}

SS& SS::removeRange (int beg, int len)
{
	return replaceRange ("", beg, len);
}

SS& SS::removeRange (Pair<int> const & beglen)
{
	return replaceRange ("", beglen);
}

SS& SS::removeRange (std::vector< Pair<int> > const & beglen)
{
	return replaceRange ("", beglen);
}

SS& SS::replaceRange (SS const & newseq, int beg, int len)
{
	adjust (beg, len);
	sub (beg, len) = newseq;
	return *this;
}

SS& SS::replaceRange (SS const & newseq, Pair<int> const & beglen)
{
	return replaceRange (newseq, beglen._0, beglen._1);
}

SS& SS::replaceRange (SS const & newseq, std::vector< Pair<int> > const & beglen)
{
	resizeOpHelper(this,beglen,newseq,replaceRange,adjust,Pair<int>,SS,0);
	return *this;
}

SS& SS::replaceRange (std::vector<SS> const & s, std::vector< Pair<int> > const & beglen)
{
	resizeOpHelper(this,beglen,s,replaceRange,adjust,Pair<int>,VectSS,0);
	return *this;
}

template <class T>
static inline SS& replaceHelper (SS* s, T const & t, SS const & newseq, int beg, int len)
{
	SS str = s->getRegion (beg, len);
	std::vector< Pair<int> > mat;
	str.match (t, mat);
	{for (int i=0; i<mat.size(); i++) {
		mat[i]._0 += beg;
	}}
	return s->replaceRange (newseq, mat);
}

SS& SS::replace (SS const & oldseq, SS const & newseq, int beg, int len)
{
	return replaceHelper (this, oldseq, newseq, beg, len);
}

SS& SS::replace (Find const & finder, SS const & newseq, int beg, int len)
{
	return replaceHelper (this, finder, newseq, beg, len);
}

SS& SS::replace (SS const & oldseq, SS const & newseq, Pair<int> const & beglen)
{
	return replace (oldseq, newseq, beglen._0, beglen._1);
}

SS& SS::replace (Find const & finder, SS const & newseq, Pair<int> const & beglen)
{
	return replace (finder, newseq, beglen._0, beglen._1);
}

SS& SS::replace (SS const & oldseq, SS const & newseq, std::vector< Pair<int> > const & beglen)
{
	resizeOpHelper(this,beglen,newseq,replace,adjust,Pair<int>,ReplSS,oldseq);
	return *this;
}

SS& SS::replace (Find const & finder, SS const & newseq, std::vector< Pair<int> > const & beglen)
{
	resizeOpHelper(this,beglen,newseq,replace,adjust,Pair<int>,ReplSS,finder);
	return *this;
}

template <class T>
static inline std::vector< Pair<int> >& matchHelper0 (SS const * s, T const & t, std::vector< Pair<int> >& beglen, int count, int beg, int len, bool forward)
{
	beglen.clear();
	if (count>0 || count==SS::allitems) {
		s->adjust (beg, len);
		SS str = s->getRegion (beg, len);
		if (forward) {
			int n=0,pos=0;
			SS result;
			while ( (pos = str.findNext (t, pos, result)) >= 0) {
				int len = result.length();
				beglen.insert (beglen.end(), Pair<int>(beg+pos, len));
				n++;
				if (count!=SS::allitems && n==count) break;
				pos += len;
			}
		} else {
			int n=0,pos=SS::maxindex;
			SS result;
			while ( (pos = str.findPrev (t, pos, result)) >= 0) {
				int len = result.length();
				beglen.insert (beglen.begin(), Pair<int>(beg+pos, len));
				n++;
				if (count!=SS::allitems && n==count) break;
				--pos;
			}
		}
	}
	return beglen;
}

template <class T>
static inline std::vector< Pair<int> >& matchHelper1 (SS const * s, T const & t, std::vector< Pair<int> >& beglen, int beg, int len)
{
	return matchHelper0 (s, t, beglen, SS::allitems, beg, len, true);
}

template <class T>
static inline std::vector< Pair<int> >& matchHelper2 (SS const * s, T const & t, std::vector< Pair<int> >& beglen, std::vector< Pair<int> > const & beglen_src)
{
	beglen.clear();
	{for (int i=0; i<beglen_src.size(); i++) {
		std::vector< Pair<int> > v;
		matchHelper0 (s, t, v, SS::allitems, beglen_src[i]._0, beglen_src[i]._1, true);
		beglen.insert (beglen.end(), v.begin(), v.end());
	}}
	return beglen;
}

std::vector< Pair<int> >& SS::match (SS const & sequence, std::vector< Pair<int> >& beglen, int beg, int len) const
{
	return matchHelper1 (this, sequence, beglen, beg, len);
}

std::vector< Pair<int> >& SS::match (Find const & finder, std::vector< Pair<int> >& beglen, int beg, int len) const
{
	return matchHelper1 (this, finder, beglen, beg, len);
}

std::vector< Pair<int> >& SS::match (SS const & sequence, std::vector< Pair<int> >& beglen, Pair<int> const & beglen_src) const
{
	return match (sequence, beglen, beglen_src._0, beglen_src._1);
}

std::vector< Pair<int> >& SS::match (Find const & finder, std::vector< Pair<int> >& beglen, Pair<int> const & beglen_src) const
{
	return match (finder, beglen, beglen_src._0, beglen_src._1);
}

std::vector< Pair<int> >& SS::match (SS const & sequence, std::vector< Pair<int> >& beglen, std::vector< Pair<int> > const & beglen_src) const
{
	return matchHelper2 (this, sequence, beglen, beglen_src);
}

std::vector< Pair<int> >& SS::match (Find const & finder, std::vector< Pair<int> >& beglen, std::vector< Pair<int> > const & beglen_src) const
{
	return matchHelper2 (this, finder, beglen, beglen_src);
}

std::vector< Pair<int> >& SS::matchForward (SS const & sequence, std::vector< Pair<int> >& beglen, int count, int beg, int len) const
{
	return matchHelper0 (this, sequence, beglen, count, beg, len, true);
}

std::vector< Pair<int> >& SS::matchForward  (Find const & finder, std::vector< Pair<int> >& beglen, int count, int beg, int len) const
{
	return matchHelper0 (this, finder, beglen, count, beg, len, true);
}

std::vector< Pair<int> >& SS::matchBackward (SS const & sequence, std::vector< Pair<int> >& beglen, int count, int beg, int len) const
{
	return matchHelper0 (this, sequence, beglen, count, beg, len, false);
}

std::vector< Pair<int> >& SS::matchBackward (Find const & finder, std::vector< Pair<int> >& beglen, int count, int beg, int len) const
{
	return matchHelper0 (this, finder, beglen, count, beg, len, false);
}

int SS::removeForward (SS const & oldseq, int count, int beg, int len)
{
	return replaceForward (oldseq, "", count, beg, len);
}

int SS::removeForward (Find const & finder, int count, int beg, int len)
{
	return replaceForward (finder, "", count, beg, len);
}

int SS::removeBackward (SS const & oldseq, int count, int beg, int len)
{
	return replaceBackward (oldseq, "", count, beg, len);
}

int SS::removeBackward (Find const & finder, int count, int beg, int len)
{
	return replaceBackward (finder, "", count, beg, len);
}

template <class T>
static inline int replaceDirHelper (SS* s, T const & t, SS const & newseq, int count, int beg, int len, bool forward)
{
	std::vector< Pair<int> > beglen;
	matchHelper0 (s, t, beglen, count, beg, len, forward);
	s->replaceRange (newseq, beglen);
	return beglen.size();
}

int SS::replaceForward (SS const & oldseq, SS const newseq, int count, int beg, int len)
{
	return replaceDirHelper (this, oldseq, newseq, count, beg, len, true);
}

int SS::replaceForward (Find const & finder, SS const newseq, int count, int beg, int len)
{
	return replaceDirHelper (this, finder, newseq, count, beg, len, true);
}

int SS::replaceBackward (SS const & oldseq, SS const newseq, int count, int beg, int len)
{
	return replaceDirHelper (this, oldseq, newseq, count, beg, len, false);
}

int SS::replaceBackward (Find const & finder, SS const newseq, int count, int beg, int len)
{
	return replaceDirHelper (this, finder, newseq, count, beg, len, false);
}

SS& SS::swap (int pos0, int pos1)
{
	char& c0 = at (pos0);
	char& c1 = at (pos1);
	char c = c0;
	c0 = c1;
	c1 = c;
	return *this;
}

// old value of this destroyed when tmp goes out of scope
SS& SS::become (SS& s)
{
	SS tmp;
	tmp.swap (s);
	swap (tmp);
	return *this;
}

SS& SS::swap (SS& s)
{
	SS tmp;
	tmp._setData (s);
	s._setData (*this);
	_setData (tmp);
	tmp._zero();
	return *this;
}

bool SS::isUpperCase (int pos) const
{
	return upperP (_rep[pos]);
}

bool SS::isLowerCase (int pos) const
{
	return lowerP (_rep[pos]);
}

bool SS::isWhiteSpace (int pos) const
{
	return whiteP (_rep[pos]);
}

bool SS::isBlackSpace (int pos) const
{
	return blackP (_rep[pos]);
}

bool SS::isAlpha (int pos) const
{
	return alphaP (_rep[pos]);
}

bool SS::isDigit (int pos) const
{
	return digitP (_rep[pos]);
}

bool SS::isHexDigit (int pos) const
{
	return hexDigitP (_rep[pos]);
}

bool SS::isPrintable (int pos) const
{
	return printableP (_rep[pos]);
}

bool SS::isAlphaNumeric (int pos) const
{
	return alphaP (_rep[pos]);
}

bool SS::isPunct (int pos) const
{
	return punctP (_rep[pos]);
}

bool SS::isCntrl (int pos) const
{
	return cntrlP (_rep[pos]);
}

bool SS::isGraph (int pos) const
{
	return graphP (_rep[pos]);
}

bool SS::upperP (char c)
{
	return std::isupper (c, std::locale());
}

bool SS::lowerP (char c)
{
	return std::islower (c, std::locale());
}

bool SS::whiteP (char c)
{
	return std::isspace (c, std::locale());
}

bool SS::blackP (char c)
{
	return std::isgraph (c, std::locale());
}

bool SS::alphaP (char c)
{
	return std::isalpha (c, std::locale());
}

bool SS::digitP (char c)
{
	return std::isdigit(c, std::locale());
}

bool SS::printableP (char c)
{
	return std::isprint(c, std::locale());
}

bool SS::hexDigitP (char c)
{
	return std::isxdigit(c, std::locale());
}

bool SS::cntrlP (char c)
{
	return std::iscntrl(c, std::locale());
}

bool SS::punctP (char c)
{
	return std::ispunct(c, std::locale());
}

bool SS::alphanumP (char c)
{
	return std::isalnum(c, std::locale());
}

bool SS::graphP (char c)
{
	return std::isgraph(c, std::locale());
}

char SS::getLower (char c)
{
	return tolower(c);
}

char SS::getUpper (char c)
{
	return toupper(c);
}

void SS::to_lower (char& c)
{
	c = getLower(c);
}

void SS::to_upper (char& c)
{
	c = getUpper(c);
}

SS& SS::toLower ()
{
	{for (int i=0; i<length(); i++) {
		to_lower(_rep [i]);
	}}
	return *this;
}

SS& SS::toLower (int pos)
{
	to_lower (_rep[pos]);
	return *this;
}

SS& SS::toUpper ()
{
	{for (int i=0; i<length(); i++) {
		to_upper (_rep[i]);
	}}
	return *this;
}

SS& SS::toUpper (int pos)
{
	to_upper (_rep[pos]);
	return *this;
}

SS SS::toHex () const
{
	const char hex_codes [] = "0123456789abcdef";
	SS ret (Buffer(2*_len));
	{for (int i=0; i<_len; i++) {
		unsigned char byte = _rep[i];
		ret._rep[2*i]   = hex_codes [byte >> 4];
		ret._rep[2*i+1] = hex_codes [byte & 0xf];
	}}
	return ret;
}

SS SS::fromHex () const
{
	std::vector<char> ret;
	int pos = maxindex;
	SS hexchar;
	// find one or preferably two hex digits
	while ( (pos=findPrev (hexdigit, pos)) >= 0) {
		SS res;
		if (match (hexdigit, pos-1)) {
			hexchar = get (pos-1,2);
			pos -= 2;
		} else {
			hexchar = get (pos, 1);
			pos--;
		}
		int x=0;
		sscanf (hexchar, "%x", &x);
		char c = x;
		ret.insert (ret.end(), c);
	}
	std::reverse (ret.begin(), ret.end());
	return ret;
}

SS SS::outputHex () const
{
	const char hex_codes [] = "0123456789abcdef";
	const int bytesPerLine = 16;
	int offsetBytes = 0;
	{for (int tmp=_len; tmp; tmp >>= 8) offsetBytes++; }
	int hexOffset = 2*offsetBytes + 2; // colon and space
	int lineLength = hexOffset + 4*bytesPerLine + 2;
	int asciiOffset = lineLength - bytesPerLine - 1;
	int numberOfLines = (_len + bytesPerLine - 1) / bytesPerLine;

	SS ret (Buffer(numberOfLines*lineLength));
	ret.fill(' ');
	{for (int i=0; i<numberOfLines; i++) {
		int beg = i * bytesPerLine;
		int len = bytesPerLine;
		if (beg + len > _len) len = _len - beg;
		char* buff = ret._rep + i * lineLength;
		char* start = _rep + beg;
		int pos = 0;
		{
			unsigned char* byte = (unsigned char*)&beg;
			{for (int i=offsetBytes-1; i>=0; i--) {
				buff [pos++] = hex_codes [byte[i] >> 4];
				buff [pos++] = hex_codes [byte[i] & 0xf];
			}}
			buff [pos++] = ':';
		}
		{
			{for (int i=0; i<len; i++) {
				buff [pos++] = ' ';
				unsigned char byte = start[i];
				buff [pos++] = hex_codes [byte >> 4];
				buff [pos++] = hex_codes [byte & 0xf];
				buff [asciiOffset + i] = printableP(byte) ? byte : '.';
			}}
			buff [asciiOffset - 2] = buff [asciiOffset - 1] = ' ';
			buff [lineLength - 1] = '\n';
			buff [hexOffset+11] = buff [hexOffset+23] = buff [hexOffset+35] = '|';
		}
	}}
	return ret;
}

SS SS::trim () const
{
	int i0 = findNext (blackspace);
	if (i0==notfound) return "";
	int i1 = findPrev (blackspace);
	return get (i0, i1 - i0 + 1);
}

SS SS::dup (int n) const
{
	if (n<0) ErrorMacro(ErrorOutOfRange("SS::dup - n can't be < 0"));
	SS ret ((Buffer)(n*length()));
	ret.repeat (*this);
	return ret;
}

char* SS::extract ()
{
	setNoAlloc();
	checkFlags();
	return _rep;
}

long SS::hash () const
{
	return hash (_rep, size());
}

long SS::hash (void const * v, int n)
{
  const int halfchar = 4;
  const int threechar = 24;
  const unsigned long mask = ~(~(unsigned long)(0) >> halfchar);
  unsigned long p = 0;
  for (int i=0; i<n; i++) {
	p = ( p << halfchar) + ((char const *)v)[i];
	unsigned long q = p & mask;
	if (q) {
	  p ^= q >> threechar;
	  p &= ~mask;
    }
  }
  return p;
}

SS const & SS::copyTo (void* dst, int n, int beg) const
{
	adjust (beg, n);
	copy (dst, _rep+beg, n);
	return *this;
}

SS& SS::copyFrom (void* src, int n, int beg)
{
	adjust (beg, n);
	copy (_rep+beg, src, n);
	return *this;
}

SS& SS::assignFrom (void* src, int n)
{
	assign (src, n);
	return *this;
}

void SS::copy (void* dst, void const * src, int n)
{
	memmove (dst, src, n);
}

void SS::copy (void * dst, int l0, void const * src, int l1)
{
	int n = l0 < l1 ? l0 : l1;
	copy (dst, src, n);
}

int SS::compare (void const * bf0, void const * bf1, int n)
{
	return memcmp (bf0, bf1, n);
}

// include logic for unequal lengths
int SS::compare (void const * bf0, int l0, void const * bf1, int l1)
{
	int n = l0 < l1 ? l0 : l1;
	int ret = SS::compare (bf0, bf1, n);
	if (ret==0 && l0 != l1) {
		ret = l0 < l1 ? -1 : 1;
	}
	return ret;
}

static inline bool ss_less_than (char a, char b)
{
	return a < b;
}

static inline bool ss_nc_less_than (char a, char b)
{
	return SS::getLower(a) < SS::getLower(b);
}

template <class T>
static inline int compareHelper (char const * a, int l0, T const & b, int l1, bool(less_than)(char,char) = ss_less_than)
{
	int n = l0 < l1 ? l0 : l1;
	int ret = 0;
	{for (int i=0; i<n; i++) {
		if (less_than (a[i],b[i])) {
			ret = -1;
			break;
		} else if (less_than (b[i],a[i])) {
			ret = 1;
			break;
		}
	}}
	if (ret==0 && l0 != l1) {
		ret = l0 < l1 ? -1 : 1;
	}
	return ret;
}

int SS::compareString (char const * a, int l0, string const & b)
{
	return compareHelper (a, l0, b, b.length());
}

int SS::compareVector (char const * a, int l0, std::vector<char> const & b)
{
	return compareHelper (a, l0, b, b.size());
}

int SS::compareNoCase (SS const & s) const
{
	return compareHelper (_rep, _len, s._rep, s._len, ss_nc_less_than);
}

bool SS::compare (Find const & f) const
{
	int len;
	int res = find (f, 0, &len);
	return len == _len && res == 0;
}

void SS::fill (void * dst, char c, int n)
{
	memset (dst, c, n);
}

int SS::findNext (void const * dat, char c, int n)
{
	char const * ret = (char const *)memchr (dat, c, n);
	return ret ? ret-(char const *)dat : notfound;
}

int SS::strLen (char const * s)
{
	return s ? strlen (s) : 0;
}

int SS::strLen (signed char const * s)
{
	return strLen (reinterpret_cast<char const *>(s));
}

int SS::strLen (unsigned char const * s)
{
	return strLen (reinterpret_cast<char const *>(s));
}

// primitive for operator's +
SS SS::concatenate (SS const & u, SS const & w)
{
  SS t (Buffer (u._len + w._len));
  t.set (u);
  return t.set (w, u._len);
}

SS SS::concatenate (std::vector<SS>& s)
{
	int len=0;
	{for (int i=0; i<s.size(); i++) {
		len += s[i].length();
	}}
	SS ret ((Buffer)len);
	len = 0;
	{for (int i=0; i<s.size(); i++) {
		ret.set (s[i], len);
		len += s[i].length();
	}}
	return ret;
}

// doesn't report overflow
template <class T>
static inline T strToNumericBase (SS const & s, int base)
{
	if (base<2 || base>36) ErrorMacro(SS::ErrorNumberFormat((SS)"strToNumeric - base of " + base + " is invalid"));
	bool is_signed = false;
	int left = 0;
	if (s[left] == '+') {
		left = 1;
	} else if (s[left] == '-') {
		left = 1;
		is_signed = true;
	}
	T ret = 0;
	{for (int i=left; i<s.size(); i++) {
		char digit = s[i];
		T x=0;
		if (digit >= '0' && digit <= '9') {
			x = digit-'0';
		} else if (digit >= 'A' && digit <= 'Z') {
			x = 10 + digit-'A';
		} else if (digit >= 'a' && digit <= 'z') {
			x = 10 + digit-'a';
		} else {
			ErrorMacro(SS::ErrorNumberFormat((SS)"strToNumeric - digit #"+ i + ", '"+digit+"' in base " + base + " is invalid"));
		}
		if (x<base) {
			ret = x + base*ret;
		} else {
			ErrorMacro(SS::ErrorNumberFormat((SS)"strToNumeric - digit #"+ i + ", '"+digit+"' in base " + base + " is invalid"));
		}
	}}
	if (is_signed) return -ret;
	return ret;
}

template <class T>
static inline T strToNumeric (SS const & s)
{
	if (s.size()>2 && s.head(2).toLower() == "0x") {
		return strToNumericBase<T> (s.getFrom(2), 16);
	}
	return strToNumericBase<T> (s, 10);
}

bool SS::toBool () const
{
	if (*this == "true"  || *this == "1") return true;
	if (*this == "false" || *this == "0") return false;
	ErrorMacro(ErrorNumberFormat ((SS)"SS::toBool - can't convert " + *this));
	return false;
}

short SS::toShort () const
{
	return strToNumeric<short> (*this);
}

unsigned short SS::toUShort () const
{
	return strToNumeric<unsigned short> (*this);
}

int SS::toInt () const
{
	return strToNumeric<int> (*this);
}

unsigned int SS::toUInt () const
{
	return strToNumeric<unsigned int> (*this);
}

long SS::toLong () const
{
	return strToNumeric<long> (*this);
}

unsigned long SS::toULong () const
{
	return strToNumeric<unsigned long> (*this);
}

SS::LongLong SS::toLongLong () const
{
	return strToNumeric<LongLong> (*this);
}

SS::ULongLong SS::toULongLong () const
{
	return strToNumeric<ULongLong> (*this);
}

short SS::toShort (int base) const
{
	return strToNumericBase<short> (*this, base);
}

unsigned short SS::toUShort (int base) const
{
	return strToNumericBase<unsigned short> (*this, base);
}

int SS::toInt (int base) const
{
	return strToNumericBase<int> (*this, base);
}

unsigned int SS::toUInt (int base) const
{
	return strToNumericBase<unsigned int> (*this, base);
}

long SS::toLong (int base) const
{
	return strToNumericBase<long> (*this, base);
}

unsigned long SS::toULong (int base) const
{
	return strToNumericBase<unsigned long> (*this, base);
}

SS::LongLong SS::toLongLong (int base) const
{
	return strToNumericBase<LongLong> (*this, base);
}

SS::ULongLong SS::toULongLong (int base) const
{
	return strToNumericBase<ULongLong> (*this, base);
}

template <class T> static inline T extract_using_strstream (SS const & s, T& t)
{
	std::istrstream is (s.data());
	is >> t;
	if (is.fail() || is.bad()) {
		ErrorMacro(SS::ErrorNumberFormat ((SS)"SS - extract_using_strstream - \"" + s + "\" not convertable"));
	}
	return t;
}

float SS::toFloat () const
{
	float v;
	return extract_using_strstream (*this, v);
//	return toDouble();
}

double SS::toDouble () const
{
	double v;
	return extract_using_strstream (*this, v);
//  	char* end = 0;
//  	char const * beg = *this;
//  	double ret = strtod (beg, &end);
//  	if (end == beg || *end != nullchar) {
//  		ErrorMacro(ErrorNumberFormat ((SS)"SS::toDouble - \"" + *this + "\" not convertable"));
//  	}
//  	return ret;
}

long double SS::toLongDouble () const
{
	long double v;
	return extract_using_strstream (*this, v);
}

SS::string SS::toString () const
{
	return string (_rep, _len);
}

std::vector<char> SS::toVector () const
{
	std::vector<char> ret(_len);
	{for (int i=0; i<_len; i++) {
		ret[i] = _rep[i];
	}}
	return ret;
}

void SS::toInteger (short & number) const
{
	number = strToNumeric<short> (*this);
}

void SS::toInteger (unsigned short & number) const
{
	number = strToNumeric<unsigned short> (*this);
}

void SS::toInteger (int & number) const
{
	number = strToNumeric<int> (*this);
}

void SS::toInteger (unsigned int & number) const
{
	number = strToNumeric<unsigned int> (*this);
}

void SS::toInteger (long & number) const
{
	number = strToNumeric<long> (*this);
}

void SS::toInteger (unsigned long & number) const
{
	number = strToNumeric<unsigned long> (*this);
}

void SS::toInteger (LongLong & number) const
{
	number = strToNumeric<LongLong> (*this);
}

void SS::toInteger (ULongLong & number) const
{
	number = strToNumeric<ULongLong> (*this);
}

void SS::toInteger (short & number, int base) const
{
	number = strToNumericBase<short> (*this, base);
}

void SS::toInteger (unsigned short & number, int base) const
{
	number = strToNumericBase<unsigned short> (*this, base);
}

void SS::toInteger (int & number, int base) const
{
	number = strToNumericBase<int> (*this, base);
}

void SS::toInteger (unsigned int & number, int base) const
{
	number = strToNumericBase<unsigned int> (*this, base);
}

void SS::toInteger (long & number, int base) const
{
	number = strToNumericBase<long> (*this, base);
}

void SS::toInteger (unsigned long & number, int base) const
{
	number = strToNumericBase<unsigned long> (*this, base);
}

void SS::toInteger (LongLong & number, int base) const
{
	number = strToNumericBase<LongLong> (*this, base);
}

void SS::toInteger (ULongLong & number, int base) const
{
	number = strToNumericBase<ULongLong> (*this, base);
}

template <class T>
static inline SS toBaseImpl (T number, int base)
{
	if (base<2 || base>36) ErrorMacro(SS::ErrorNumberFormat((SS)"toBase - base of " + base + " is invalid"));
	bool is_signed = false;
	if (number < 0) {
		is_signed = true;
		number = -number;
	}
	std::vector<T> digits;
	T rem = number;
	while (rem >= base) {
		T p = rem/base;
		T q = rem - p*base;
		rem = p;
		digits.insert (digits.begin(), q);
	}
	digits.insert (digits.begin(), rem);
	SS ret (SS::Buffer(digits.size()));
	char* digit_array = "0123456789abcdefghijklmnopqrstuvwxyz";
	{for (int i=0; i<ret.size(); i++) {
		ret[i] = digit_array [digits[i]];
	}}
	if (is_signed) return ret = '-' + ret;
	return ret;
}

SS SS::toBase (short number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (unsigned short number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (int number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (unsigned int number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (long number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (unsigned long number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (LongLong number, int base)
{
	return toBaseImpl (number, base);
}

SS SS::toBase (ULongLong number, int base)
{
	return toBaseImpl (number, base);
}

bool SS::verify (int ind) const
{
	try {
		ind = translateIndex(ind);
	} catch (ErrorBadArg error) {
		return false;
	}
	return ind>=0 && ind<_len;
}

bool SS::verify (int beg, int len) const
{
	bool ret = verify(beg);
	if (len != fullength) {
		if (len>0) {
			ret = ret && verify(beg+len-1);
		} else {
			ret = false;
		}
	}
	return ret;
}

bool SS::verify3 (SS const & s, int pos, int beg, int len) const
{
	return pos>=0 && pos<_len && beg>=0 && beg<s._len && len>0 && pos+len<=_len && beg+len<=s._len;
}

int SS::translateIndex (int ind) const
{
	if (ind == fullength || ind == notfound || ind == allitems) {
		ErrorMacro(ErrorBadArg((SS)"SS::translateIndex - an index parameter cannot take the value "+ind));
	}
	return ind == maxindex ? _len-1 : ind;
}

int SS::translateLength (int len) const
{
	if (len == maxindex || len == notfound || len == allitems) {
		ErrorMacro(ErrorBadArg((SS)"SS::translateLength - a length parameter cannot take the value "+len));
	}
	return len == fullength ? _len : len;
}

int SS::translateCheck (int ind) const
{
	ind = translateIndex (ind);
	check (ind);
	return ind;
}

void SS::check (int ind) const
{
	if (ind < 0 || ind >= _len) {
		SS err = (SS)"Index of " + ind + " in \"" + makeHeadSample() + "\" is ";
		if (ind < 0) {
			err += "less than zero";
		} else {
			err += "greater than the maximum of ";
			err +=  _len-1;
		}
		ErrorMacro (ErrorOutOfRange(err));
	}
}

bool SS::findCheck (int beg, int end, int inc) const
{
	if (beg == notfound || end == notfound || inc == 0) return false;
	if (beg == maxindex) beg = _len-1;
	if (end == maxindex) end = _len-1;
	if (inc>0) {
		if (end == fullength) end = _len-1;
		if (beg >= _len || end < 0 || end < beg) return false;
	} else {
		if (end == fullength) end = 0;
		if (end >= _len || beg < 0 || end > beg) return false;
	}
	return true;
}

void SS::adjust (int& ind) const
{
	ind = translateIndex (ind);
	if (ind <  0       ) ind = 0;
	if (ind > _len - 1 ) ind = _len - 1;
}

void SS::lenAdjust (int& len) const
{
	len = translateLength (len);
	if (len > _len)     len = _len;
	if (len < 0)        len = 0;
}

void SS::pasteAdjust (int& ind) const
{
	if (ind==maxindex) ind = _len -1;
	ind = translateLength (ind);
	if (ind > _len)     ind = _len;
	if (ind < 0)        ind = 0;
}

void SS::modAdjust (int& beg, int& end, int inc) const
{
	if (end == fullength) end = inc>0?_len-1:0;
	beg = translateIndex (beg);
	end = translateIndex (end);
	int abeg = beg > 0 ? beg : -beg;
	int aend = end > 0 ? end : -end;
	int ainc = inc > 0 ? inc : -inc;
	if (beg < 0)        beg += ((abeg - 1   )/ainc+1)*ainc;
	if (beg > _len -1 ) beg -= ((abeg - _len)/ainc+1)*ainc;
	if (end < 0)        end += ((aend - 1   )/ainc+1)*ainc;
	if (end > _len -1 ) end -= ((aend - _len)/ainc+1)*ainc;
}

bool SS::matchAdjust (int& beg) const
{
	try {
		beg = translateIndex (beg);
	} catch (ErrorBadArg error) {
		return false;
	}
	if (beg >= _len) return false;
	if (beg < 0) return false;
	return true;
}

// b<0 l<0       -> 0,0           *  b+l<0
// b<0 l>0 b+l<0 -> 0,0           *
// b<0 l>0 b+l>0 -> 0,b+l
// b>0 l<0 b+l<0 -> 0,b
// b>0 l<0 b+l>0 -> b+l,-l
// b>0 l>0       -> b,l
// b>n l<0 b+l>n -> n-1,0                    *  b+l>n
// b<n l>0 b+l>n -> b,n-b
// b>n l<0 b+l<n -> b+l,n-b-l
// b>n l>0       -> n-1,0                    *
void SS::adjust (int& beg, int& len) const
{
	beg = translateIndex (beg);
	if (beg<0 && len==fullength) beg=0;
	len = translateLength (len);
	int end = beg + len;
	if (len<0) {
//		end = beg+1; // char counting pov
		end = beg;   // metrics pov
		beg = end+len;
	}
	if (beg>=_len) {
		beg = _len-1;
		end = beg;
	}
	if (beg<0) beg = 0;
	if (end<0) end = 0;
	if (end>_len) end = _len;
	len = end - beg;
}

void SS::adjust (Pair<int>& beglen) const
{
	adjust (beglen._0, beglen._1);
}

//    p
//        ##########
//  **|******|*
//    b      b+l
//                     p
//        ##########
//            **|******|*
//             b+l     b
bool SS::adjust3 (SS const & s, int& p, int& b, int& l) const
{
	p = translateIndex (p);
	b = s.translateIndex (b);
	l = s.translateLength (l);
	if (!verify3 (s,p,b,l)) {
		// switch mark and point for negative length
		if (l<0) {
			p += l;
			b += l;
			l = -l;
		}
		// normalize with respect to target string
		int p1 = p;
		lenAdjust(p1);
		int d_p1_p = p1 - p;
		int b1 = b + d_p1_p;
		int l1 = l - d_p1_p;
		// normalize with respect to source string
		b = b1;
		s.lenAdjust (b);
		int d_b_b1 = b - b1;
		p = p1 + d_b_b1;
		l = l1 - d_b_b1;
		// truncate len with respect to both strings
		if (p+l>_len) l = _len-p;
		if (b+l>s._len) l = s._len-b;
		// if results invalid assume no overlap
		if (!verify3 (s,p,b,l)) return false;
	}
	return true;
}

void SS::_leng  (int n)
{
	destroy();
	_rep = new char [n+1];
	_len = n;
	_allocLength = _len;
	_null();
	setAlloc();
	setNoRef();
}

void SS::_data (void const * s)
{
	copy (_rep, s, _len);
}

void SS::_data  (string const & s)
{
	for (int i=0; i<_len; i++) {
		_rep[i] = s[i];
	}
}

void SS::_data (std::vector<char> const & v)
{
	for (int i=0; i<_len; i++) _rep[i] = v[i];
}


void SS::assign (SS const & s)
{
	if (&s != this) {
		// a ref copies to a ref
		if (s.isRef()) {
			s.checkFlags();
			_setData (s);
		} else {
			_leng (s._len);
			_data (s._rep);
		}
	}
}

void SS::assign (Buffer const & v)
{
	if (v.getAlloc()) {
		buffer (v.getSize());
		SS fill_value = v.getFillValue();
		if (!fill_value.empty()) {
			repeat (fill_value);
		}
	} else {
		buffer (v.getStart(), v.getSize());
	}
}

// make a copy of char* if memory region about to be deleted
void SS::assign (char const * s)
{
	if (isAlloc() && addressInside (s)) {
		assign (SS(s));
	} else {
		_leng (strLen(s));
		_data(s);
	}
}

void SS::assign (unsigned char const * s)
{
	if (isAlloc() && addressInside (s)) {
		assign (SS(s));
	} else {
		_leng (strLen(s));
		_data(s);
	}
}

void SS::assign (signed char const * s)
{
	if (isAlloc() && addressInside (s)) {
		assign (SS(s));
	} else {
		_leng (strLen(s));
		_data(s);
	}
}

void SS::assign (void const * v, int n)
{
	if (isAlloc() && addressInside (v)) {
		assign (SS(v,n));
	} else {
		_leng (n);
		_data(v);
	}
}

//  template <class T> static inline SS format_using_strstream (T t)
//  {
//  	std::strstream os;
//  	os << t;
//  	return SS(os.str(),os.pcount());
//  }

void SS::assign (char           v) { _leng (1); _rep[0] =                   v; }
void SS::assign (unsigned char  v) { _leng (1); _rep[0] = static_cast<char>(v); }
void SS::assign (signed char    v) { _leng (1); _rep[0] = static_cast<char>(v); }
void SS::assign (bool           v) { assign (v ? "true" : "false"); }
void SS::assign (short          v) { assign (sprint ("%d",v)); }
void SS::assign (unsigned short v) { assign (sprint ("%u",v)); }
void SS::assign (int            v) { assign (sprint ("%d",v)); }
void SS::assign (unsigned int   v) { assign (sprint ("%u",v)); }
void SS::assign (long           v) { assign (sprint ("%ld",v)); }
void SS::assign (unsigned long  v) { assign (sprint ("%lu",v)); }
void SS::assign (LongLong       v) { assign (sprint (formatStringLongLong,v)); }
void SS::assign (ULongLong      v) { assign (sprint (formatStringULongLong,v)); }
void SS::assign (float          v) { assign (sprint ("%g",v)); }
void SS::assign (double         v) { assign (sprint ("%.20g",v)); }
// long double treated as double here
void SS::assign (long double    v) { assign (sprint ("%.20g",v)); }
void SS::assign (std::vector<char> const & v) { _leng (v.size()); _data(v); }
void SS::assign (string const & s) { _leng (s.length()); _data (s); }

void SS::_setData (char * rep, int len, int flags, int allocLength)
{
	_rep         = rep;
	_len         = len;
	_flags       = flags;
	_allocLength = allocLength;
}

void SS::_setData (SS const & s)
{
	_setData (s._rep, s._len, s._flags, s._allocLength);
}

void SS::_zero ()
{
	_setData (0, 0, 0, 0);
}

void SS::_null ()
{
	_rep [_len] = nullchar;
}

bool SS::isAlloc () const
{
	return (_flags & Alloc) == 0;
}

void SS::setAlloc ()
{
	_flags &= ~Alloc;
}

void SS::setNoAlloc ()
{
	_flags |= Alloc;
}

bool SS::isRef () const
{
	return (_flags & Ref) != 0;
}

void SS::setRef ()
{
	_flags |= Ref;
}

void SS::setNoRef ()
{
	_flags &= ~Ref;
}

// the flags are not exposed; calling this <should> be redundant
void SS::checkFlags () const
{
	if (isAlloc() && isRef()) {
		ErrorMacro(ErrorBadState((SS)"checkFlags - alloc="+isAlloc()+" ref="+isRef()+" are inconsistent"));
	}
}

// the problem here is that SS const &'s are judged ambiguous
SS   SS::operator +  (SS s)       { return concatenate (*this,s); }
SS   SS::operator +  (SS s) const { return concatenate (*this,s); }
bool SS::operator == (SS s)       { return compare (s) == 0; }
bool SS::operator == (SS s) const { return compare (s) == 0; }
bool SS::operator != (SS s)       { return compare (s) != 0; }
bool SS::operator != (SS s) const { return compare (s) != 0; }
bool SS::operator <  (SS s)       { return compare (s) <  0; }
bool SS::operator <  (SS s) const { return compare (s) <  0; }
bool SS::operator >  (SS s)       { return compare (s) >  0; }
bool SS::operator >  (SS s) const { return compare (s) >  0; }
bool SS::operator <= (SS s)       { return compare (s) <= 0; }
bool SS::operator <= (SS s) const { return compare (s) <= 0; }
bool SS::operator >= (SS s)       { return compare (s) >= 0; }
bool SS::operator >= (SS s) const { return compare (s) >= 0; }

bool SS::addressInside (void const * p) const
{
	bool ret = false;
	if (p) {
		char const * q = reinterpret_cast<char const *>(p);
		char const * beg = _rep;
		char const * end = isAlloc() ? beg + _allocLength : beg + _len - 1;
		if (q >= beg && q <=end) ret = true;
	}
	return ret;
}

int alreadySortedHelperValue (int v) { return v; }
int alreadySortedHelperValue (Pair<int> v) { return v._0; }

// assumes indices adjusted before this
template <class T>
static inline bool alreadySortedHelper (std::vector<T> const & v)
{
	if (v.empty()) return true;
	int beg = -1;
	{for (int i=0; i<v.size(); i++) {
		int x = alreadySortedHelperValue(v[i]);
		if (x < beg) return false;
		beg = x;
	}}
	return true;
}

bool SS::alreadySorted (std::vector<int> const & v)
{
	return alreadySortedHelper (v);
}

bool SS::alreadySorted (std::vector< Pair<int> > const & v)
{
	return alreadySortedHelper (v);
}

struct SortBegLenVectPairHelper {
	bool operator () (Pair<int> const & x, Pair<int> const & y) { return x._0 < y._0; }
};

static inline int sortBegLenVectElement (int e) { return e; }
static inline int sortBegLenVectElement (Pair<int> e) { return e._0; }

template <class T>
static inline void sortBegLenVectHelper (std::vector<T> const & v, std::vector<int> & o)
{
	std::vector< Pair<int> > sv (v.size());
	{for (int i=0; i<sv.size(); i++) {
		sv[i] = Pair<int> (sortBegLenVectElement(v[i]),i);
	}}
	std::sort (sv.begin(), sv.end(), SortBegLenVectPairHelper());
	o = std::vector<int> (v.size());
	{for (int i=0; i<o.size(); i++) {
		o[i] = sv[i]._1;
	}}
}

void SS::sortBegLenVect (std::vector<int> const & v, std::vector<int> & o)
{
	sortBegLenVectHelper (v, o);
}

void SS::sortBegLenVect (std::vector< Pair<int> > const & v, std::vector<int> & o)
{
	sortBegLenVectHelper (v, o);
}

SS SS::sprint (const char * fmt, ...)
{
	va_list args;
	va_start(args, fmt);
	SS ret;
	int const BUFFSIZE [] = {1024, 64*1024, 1024*1024, 16*1024*1024};
	int nbuff = sizeof(BUFFSIZE)/sizeof(BUFFSIZE[0]);
//	const int BUFFSIZE=1024;
	char smallbuff[1024+1];
	char* allocbuff [] = {smallbuff,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
	int res = -1;
	{for (int i=0; res==-1 && i<nbuff; i++) {
		int len = BUFFSIZE[i];
		char* buff = allocbuff[i] ? allocbuff[i] : new char[len+1];
		res = _vsnprintf (buff, len, fmt, args);
		if (res != -1) { // succeeded
			buff[res] = nullchar;
			ret = buff;
		}
		if (!allocbuff[i]) delete [] buff;
	}}
	va_end(args);
	if (res == -1) ErrorMacro(ErrorOverflow("SS::sprint - buffer overflow"));
	return ret;
}

SS::SubSS::SubSS (SS* s, int beg, int len) : _rep(s), _beg(beg), _len(len) { }

//SS::SubSS::operator SS () const
//{
//	return _rep->get (_beg, _len);
//}

SS SS::SubSS::get () const
{
	return _rep->get (_beg, _len);
}

SS& SS::SubSS::operator = (SS s)
{
	if (!_rep->isAlloc() && _len == s.length()) {
		_rep->set (s, _beg);
	} else {
		_rep->cut (_beg, _len);
		_rep->paste (s, _beg);
	}
	return *_rep;
}

SS::SubSS SS::sub (int beg, int len)
{
	adjust (beg, len);
	return SubSS (this, beg, len);
}

SS SS::sub (int beg, int len) const
{
	adjust (beg, len);
	return get (beg, len);
}

SS::SubSS SS::operator () (int beg, int len)
{
	return sub (beg, len);
}

SS SS::operator () (int beg, int len) const
{
	return sub (beg, len);
}

SS::SubSS SS::operator () (Pair<int> const & beglen)
{
	return sub (beglen._0, beglen._1);
}

SS SS::operator () (Pair<int> const & beglen) const
{
	return sub (beglen._0, beglen._1);
}

SS SS::getRegion (int beg, int len) const
{
	adjust (beg, len);
	SS ret (Buffer (_rep+beg, len));
	ret.setRef();
	return ret;
}

SS SS::getRegion (Pair<int> const & beglen) const
{
	return getRegion (beglen._0, beglen._1);
}

std::vector<SS>& SS::getRegion (std::vector<SS>& s, std::vector< Pair<int> > const & beglen) const
{
	s = std::vector<SS> (beglen.size());
	{for (int i=0; i<s.size(); i++) {
		s[i] = getRegion (beglen[i]);
	}}
	return s;
}

std::vector< Pair<int> >& SS::tokenize (std::vector< Pair<int> >& beglen) const
{
	return tokenize (SS::whitespace, beglen);
}

std::vector< Pair<int> >& SS::tokenize (SS const & delimiter, std::vector< Pair<int> >& beglen) const
{
	return tokenize (FindString (delimiter), beglen);
}

std::vector< Pair<int> >& SS::tokenize (Find const & finder, std::vector< Pair<int> >& beglen) const
{
	beglen.clear();
	int pos=0;
	int end=_len;
	int begpos=pos;
	SS result;
	bool in_token = false;
	while (pos < end) {
		if (match (finder, pos, result)) {
			if (in_token) {
				beglen.back()._1 = pos - begpos;
				in_token = false;
			}
			pos += result._len;
		} else {
			if (!in_token) {
				beglen.insert (beglen.end());
				beglen.back()._0 = pos;
				in_token = true;
				begpos = pos;
			}
			pos++;
			if (pos == end) {
				beglen.back()._1 = pos - begpos;
			}
		}
	}
	return beglen;
}

SS::SSCopyPointer::SSCopyPointer (SS const & s)
{
	_rep = new SS(s);
}

SS::SSCopyPointer::SSCopyPointer (SSCopyPointer const & p)
{
	_rep = new SS(*p._rep);
}

SS * SS::SSCopyPointer::operator -> ()
{
	return _rep;
}

SS const * SS::SSCopyPointer::operator -> () const
{
	return _rep;
}

SS & SS::SSCopyPointer::operator * ()
{
	return *_rep;
}

SS const & SS::SSCopyPointer::operator * () const
{
	return *_rep;
}

SS::SSCopyPointer::operator = (SSCopyPointer const & p)
{
	delete _rep;
	_rep = new SS(*p._rep);
}

SS::SSCopyPointer::~SSCopyPointer ()
{
	delete _rep;
}

SS::Find::Find () : _rep (0)
{
}

SS::Find::Find (Find const & f)
{
	_rep = f.clone();
}

SS::Find& SS::Find::operator = (Find const & f)
{
	delete _rep;
	_rep = f.clone();
	return *this;
}

bool SS::Find::found (SS const & s, int pos, int& len) const
{
	if (_rep) return _rep->found (s,pos,len);
	return false;
}

SS::Finder* SS::Find::clone () const
{
	return _rep ? _rep->clone() : 0;
}

SS::Find::~Find ()
{
	delete _rep;
}

// for use with stl functions requiring a unary predicate
// if one of the predicates or components thereof need to examine multiple
// chars or absolute position this won't work
bool SS::Find::operator () (char c)
{
	int len;
	return found (c, 0, len);
}

SS::FindChar::FindChar (char c) : _c(c)
{
}

SS::Finder* SS::FindChar::clone () const
{
	return new FindChar (*this);
}

bool SS::FindChar::found (SS const & s, int pos, int& len) const
{
	len = 1;
	return s[pos] == _c;
}

SS::FindCharNoCase::FindCharNoCase (char c) : FindChar(getLower(c))
{
}

SS::Finder* SS::FindCharNoCase::clone () const
{
	return new FindCharNoCase (*this);
}

bool SS::FindCharNoCase::found (SS const & s, int pos, int& len) const
{
	len = 1;
	return getLower(s[pos]) == _c;
}

SS::FindFunc::FindFunc (Func f) : _f(f)
{
}

SS::Finder* SS::FindFunc::clone () const
{
	return new FindFunc (*this);
}

bool SS::FindFunc::found (SS const & s, int pos, int& len) const
{
	len = 1;
	return _f(s[pos]);
}

SS::FindSet::FindSet (SS const & charset) : _set (charset)
{
}

bool SS::FindSet::found (SS const & s, int pos, int& len) const
{
	len = 1;
	return _set->contains(s[pos]);
}

SS::Finder* SS::FindSet::clone () const
{
	return new FindSet (*this);
}

SS::FindString::FindString (SS const & str) : _str (str)
{
}

bool SS::FindString::found (SS const & s, int pos, int& len) const
{
	len = _str->_len;
	return s.matchString (_str->_rep, len, pos);
}

SS::Finder* SS::FindString::clone () const
{
	return new FindString (*this);
}

SS::FindVector::FindVector (int n)
{
	_rep = new std::vector<Find const *>(n);
}

SS::FindVector::FindVector (FindVector const & fv)
{
	_rep = new std::vector<Find const *>(fv.size());
	{for (int i=0; i<size(); i++) {
		(*_rep)[i] = fv[i].clone();
	}}
}

SS::Finder* SS::FindVector::clone () const
{
	return new FindVector (*this);
}

void SS::FindVector::add (F f)
{
	_rep->insert (_rep->end(), f.clone());
}

int SS::FindVector::size () const
{
	return _rep->size();
}

SS::Find const & SS::FindVector::operator [] (int i) const
{
	return *(*_rep)[i];
}

SS::FindVector::~FindVector ()
{
	for (int i=0; i<_rep->size(); i++) delete (*_rep)[i];
	delete _rep;
}

SS::FindSequence::FindSequence ()
{
}

SS::FindSequence::FindSequence (F f0, F f1)
{
	add(f0); add(f1);
}

SS::FindSequence::FindSequence (F f0, F f1, F f2)
{
	add(f0); add(f1); add(f2);
}

SS::FindSequence::FindSequence (F f0, F f1, F f2, F f3)
{
	add(f0); add(f1); add(f2); add(f3);
}

SS::FindSequence::FindSequence (F f0, F f1, F f2, F f3, F f4)
{
	add(f0); add(f1); add(f2); add(f3); add(f4);
}

SS::FindSequence::FindSequence (F f0, F f1, F f2, F f3, F f4, F f5)
{
	add(f0); add(f1); add(f2); add(f3); add(f4); add(f5);
}

SS::FindSequence::FindSequence (F f0, F f1, F f2, F f3, F f4, F f5, F f6)
{
	add(f0); add(f1); add(f2); add(f3); add(f4); add(f5); add(f6);
}

bool SS::FindSequence::found (SS const & s, int pos, int& len) const
{
	len = 0;
	{for (int i=0; i<size(); i++) {
		if (pos >= s.length()) return false;
		int leng=0;
		if (!(*this)[i].found (s, pos, leng)) return false;
		pos += leng;
		len += leng;
	}}
	return true;
}

SS::Finder* SS::FindSequence::clone () const
{
	return new FindSequence (*this);
}

SS::FindStringNoCase::FindStringNoCase (SS const & s)
{
	{for (int i=0; i<s.length(); i++) {
		add (FindCharNoCase(s[i]));
	}}
}

SS::FindProxy::FindProxy (Find const & f) : _f(f.clone())
{
}

SS::FindProxy::FindProxy (FindProxy const & f)
{
	_f = f._f->clone();
}

SS::FindProxy::~FindProxy ()
{
	delete _f;
}

bool SS::FindProxy::found (SS const & s, int pos, int& len) const
{
	return _f->found (s, pos, len);
}

SS::Finder* SS::FindProxy::clone () const
{
	return new FindProxy (*this);
}

SS::FindNot::FindNot (Find const & f) : FindProxy(f)
{
}

SS::FindNot::FindNot (FindNot const & f) : FindProxy(f)
{
}

SS::Finder* SS::FindNot::clone () const
{
	return new FindNot (*this);
}

bool SS::FindNot::found (SS const & s, int pos, int& len) const
{
	return !FindProxy::found (s, pos, len);
}

SS::FindOr::FindOr ()
{
}

SS::FindOr::FindOr (F f0, F f1)
{
	add(f0); add(f1);
}

SS::FindOr::FindOr (F f0, F f1, F f2)
{
	add(f0); add(f1); add(f2);
}

SS::FindOr::FindOr (F f0, F f1, F f2, F f3)
{
	add(f0); add(f1); add(f2); add(f3);
}

SS::FindOr::FindOr (F f0, F f1, F f2, F f3, F f4)
{
	add(f0); add(f1); add(f2); add(f3); add(f4);
}

SS::FindOr::FindOr (F f0, F f1, F f2, F f3, F f4, F f5)
{
	add(f0); add(f1); add(f2); add(f3); add(f4); add(f5);
}

SS::FindOr::FindOr (F f0, F f1, F f2, F f3, F f4, F f5, F f6)
{
	add(f0); add(f1); add(f2); add(f3); add(f4); add(f5); add(f6);
}

bool SS::FindOr::found (SS const & s, int pos, int& len) const
{
	len = 0;
	bool ret = false;
	{for (int i=0; i<size(); i++) {
		int leng=0;
		if ((*this)[i].found (s, pos, leng)) {
			ret = true;
			if (leng>len) len = leng;
		}
	}}
	return ret;
}

SS::Finder* SS::FindOr::clone () const
{
	return new FindOr (*this);
}

SS::FindAnd::FindAnd ()
{
}

SS::FindAnd::FindAnd (F f0, F f1)
{
	add(f0); add(f1);
}

SS::FindAnd::FindAnd (F f0, F f1, F f2)
{
	add(f0); add(f1); add(f2);
}

SS::FindAnd::FindAnd (F f0, F f1, F f2, F f3)
{
	add(f0); add(f1); add(f2); add(f3);
}

SS::FindAnd::FindAnd (F f0, F f1, F f2, F f3, F f4)
{
	add(f0); add(f1); add(f2); add(f3); add(f4);
}

SS::FindAnd::FindAnd (F f0, F f1, F f2, F f3, F f4, F f5)
{
	add(f0); add(f1); add(f2); add(f3); add(f4); add(f5);
}

SS::FindAnd::FindAnd (F f0, F f1, F f2, F f3, F f4, F f5, F f6)
{
	add(f0); add(f1); add(f2); add(f3); add(f4); add(f5); add(f6);
}

bool SS::FindAnd::found (SS const & s, int pos, int& len) const
{
	len = 0;
	bool ret = true;
	{for (int i=0; i<size(); i++) {
		int leng=0;
		if ((*this)[i].found (s, pos, leng)) {
			if (leng>len) len = leng;
		} else {
			ret = false;
		}
	}}
	return ret;
}

SS::Finder* SS::FindAnd::clone () const
{
	return new FindAnd (*this);
}

static bool findCharGT (char u, char w) { return u>w; }
static bool findCharGE (char u, char w) { return u>=w; }
static bool findCharLT (char u, char w) { return u<w; }
static bool findCharLE (char u, char w) { return u<=w; }

SS::FindCharCompare::FindCharCompare (char w, Comp comp) : FindChar(w), _comp(comp)
{
}

bool SS::FindCharCompare::found (SS const & s, int pos, int& len) const
{
	len = 1;
	return _comp (s[pos],_c);
}

SS::Finder* SS::FindCharCompare::clone () const
{
	return new FindCharCompare (*this);
}

SS::FindCharGreaterThan::FindCharGreaterThan (char w) : FindCharCompare(w,findCharGT)
{
}

SS::FindCharGreaterThanEqual::FindCharGreaterThanEqual (char w) : FindCharCompare(w,findCharGE)
{
}

SS::FindCharLessThan::FindCharLessThan (char w) : FindCharCompare(w,findCharLT)
{
}

SS::FindCharLessThanEqual::FindCharLessThanEqual (char w) : FindCharCompare(w,findCharLE)
{
}

SS::FindCharInRange::FindCharInRange (char w_low, char w_high) : FindAnd(FindCharGreaterThanEqual(w_low),FindCharLessThanEqual(w_high))
{
}

static bool findCompareGT (SS const & u, SS const & w) { return u>w; }
static bool findCompareGE (SS const & u, SS const & w) { return u>=w; }
static bool findCompareLT (SS const & u, SS const & w) { return u<w; }
static bool findCompareLE (SS const & u, SS const & w) { return u<=w; }

SS::FindCompare::FindCompare (Find const & f, SS const & w, Comp comp) : FindProxy(f),_w(w),_comp(comp)
{
}

bool SS::FindCompare::found (SS const & s, int pos, int& len) const
{
	if (FindProxy::found (s,pos,len)) {
		// _comp is user set so use zero terminated string
		return _comp (s(pos,len),*_w);
	}
	return false;
}

SS::Finder* SS::FindCompare::clone () const
{
	return new FindCompare (*this);
}

SS::FindGreaterThan::FindGreaterThan (Find const & f, SS const & w) : FindCompare(f,w,findCompareGT)
{
}

SS::FindGreaterThanEqual::FindGreaterThanEqual (Find const & f, SS const & w) : FindCompare(f,w,findCompareGE)
{
}

SS::FindLessThan::FindLessThan (Find const & f, SS const & w) : FindCompare(f,w,findCompareLT)
{
}

SS::FindLessThanEqual::FindLessThanEqual (Find const & f, SS const & w) : FindCompare(f,w,findCompareLE)
{
}

SS::FindInRange::FindInRange (Find const & f, SS const & w_low, SS const & w_high) : FindAnd(FindGreaterThanEqual(f,w_low),FindLessThanEqual(f,w_high))
{
}

SS::FindBool::FindBool (bool b, int l) : _b(b), _l(l)
{
	if (_l<0 && _l!=fullength) ErrorMacro(ErrorOutOfRange("FindBool - l must be >= 0"));
}

bool SS::FindBool::found (SS const & s, int pos, int& len) const
{
	len = _l == fullength ? s.length()-pos : _l;
	if (pos + len > s.length()) return false;
	return _b;
}

SS::Finder* SS::FindBool::clone () const
{
	return new FindBool (*this);
}

SS::FindPosition::FindPosition (int n) : _n(n)
{
}

bool SS::FindPosition::found (SS const & s, int pos, int& len) const
{
	len = 1;
	return _n == maxindex ? pos == s.length()-1 : pos == _n;
}

SS::Finder* SS::FindPosition::clone () const
{
	return new FindPosition (*this);
}

SS::FindRange::FindRange (int n, int l) : _n(n), _l(l)
{
	if (_n<0 && _n!=maxindex) ErrorMacro(ErrorOutOfRange("FindRange - n must be >= 0"));
	if (_l<0 && _l!=fullength) ErrorMacro(ErrorOutOfRange("FindRange - l must be >= 0"));
}

bool SS::FindRange::found (SS const & s, int pos, int& len) const
{
	len = _l == fullength ? s.length()-pos : _l;
	if (pos + len > s.length()) return false;
	return _n == maxindex ? pos == s.length()-1 : pos == _n;
}

SS::Finder* SS::FindRange::clone () const
{
	return new FindRange (*this);
}

SS::FindDisplacedBy::FindDisplacedBy (Find const & f, int n) : FindProxy(f), _n(n)
{
}

bool SS::FindDisplacedBy::found (SS const & s, int pos, int& len) const
{
	pos += _n;
	if (pos<0 || pos>=s.length()) return false;
	return FindProxy::found (s,pos,len);
}

SS::Finder* SS::FindDisplacedBy::clone () const
{
	return new FindDisplacedBy (*this);
}

SS::FindMultiple::FindMultiple (Find const & f, int n) : FindProxy(f), _n(n), _m(n)
{
	if (_n<0) ErrorMacro(ErrorOutOfRange("FindMultiple - n must be >= 0"));
}

SS::FindMultiple::FindMultiple (Find const & f, int n_min, int n_max) : FindProxy(f), _n(n_min), _m(n_max)
{
	if (_n<0) ErrorMacro(ErrorOutOfRange("FindMultiple - n must be >= 0"));
	if (_m>=0 && _m<_n) ErrorMacro(ErrorOutOfRange("FindMultiple - n_max must be >= n_min"));
}

SS::FindMultiple::FindMultiple (FindMultiple const & f) : FindProxy(f), _n(f._n), _m(f._m)
{
}

bool SS::FindMultiple::found (SS const & s, int pos, int& len) const
{
	len = 0;
	bool ret = _n==0 ? true : false;
	bool notdone = true;
	int n = 0;
	while (notdone && pos<s.length() && (_m<0 ? true : n<_m)) {
		int leng=0;
		notdone = FindProxy::found (s, pos, leng);
		if (notdone) {
			n++;
			if (n>=_n) ret = true;
			pos += leng;
			len += leng;
		}
	}
	return ret;
}

SS::Finder* SS::FindMultiple::clone () const
{
	return new FindMultiple (*this);
}

SS::FindOneOrMore::FindOneOrMore (Find const & f) : FindMultiple(f,1,-1)
{
}

SS::FindAtLeast::FindAtLeast (Find const & f, int n) : FindMultiple(f,n,-1)
{
}

SS::FindUpTo::FindUpTo (Find const & f, int n) : FindMultiple(f,n==0?0:1,n)
{
}

SS::FindZeroOrMore::FindZeroOrMore (Find const & f) : FindMultiple(f,0,-1)
{
}

SS::FindZeroOrOne::FindZeroOrOne (Find const & f) : FindMultiple(f,0,1)
{
}

SS::FindAfter::FindAfter (F f0, F f1)
{
	add(f0); add(f1);
}

bool SS::FindAfter::found (SS const & s, int pos, int& len) const
{
	if ((*this)[0].found (s, pos, len)) {
		int l;
		int p = s.find((*this)[1],pos+len,&l);
		if (p!=notfound) {
			len = p+l-pos;
			return true;
		}
	}
	return false;
}

SS::Finder* SS::FindAfter::clone () const
{
	return new FindAfter (*this);
}

SS::FindWithin::FindWithin (F f0, F f1) : FindAfter (f0,f1)
{
}

bool SS::FindWithin::found (SS const & s, int pos, int& len) const
{
	if ((*this)[0].found (s, pos, len)) {
		int l;
		return s.find((*this)[1],pos,&l,pos+len-1) != notfound;
	}
	return false;
}

SS::Finder* SS::FindWithin::clone () const
{
	return new FindWithin (*this);
}

SS::FindSeparatedBy::FindSeparatedBy (F f0, F f1, int n) : FindAfter (f0,f1), _n(n)
{
	if (_n<0) ErrorMacro(ErrorOutOfRange("FindSeparatedBy - n must be >= 0"));
}

bool SS::FindSeparatedBy::found (SS const & s, int pos, int& len) const
{
	if ((*this)[0].found (s, pos, len)) {
		int l;
		int p = pos+len+_n;
		if (p<s.length() && (*this)[1].found(s,p,l)) {
			len += _n+l;
			return true;
		}
	}
	return false;
}

SS::Finder* SS::FindSeparatedBy::clone () const
{
	return new FindSeparatedBy (*this);
}

SS::FindCloserThan::FindCloserThan (F f0, F f1, int n) : FindSeparatedBy (f0,f1,n)
{
}

bool SS::FindCloserThan::found (SS const & s, int pos, int& len) const
{
	if ((*this)[0].found (s, pos, len)) {
		SS result;
		int l;
		int p = s.find((*this)[1],pos+len,&l,pos+len+_n-1);
		if (p!=notfound) {
			len = p+l-pos;
			return true;
		}
	}
	return false;
}

SS::Finder* SS::FindCloserThan::clone () const
{
	return new FindCloserThan (*this);
}

SS::FindFartherThan::FindFartherThan (F f0, F f1, int n) : FindSeparatedBy (f0,f1,n)
{
}

bool SS::FindFartherThan::found (SS const & s, int pos, int& len) const
{
	if ((*this)[0].found (s, pos, len)) {
		int l;
		int p = s.find((*this)[1],pos+len+_n+1,&l);
		if (p!=notfound) {
			len = p+l-pos;
			return true;
		}
	}
	return false;
}

SS::Finder* SS::FindFartherThan::clone () const
{
	return new FindFartherThan (*this);
}

SS::FindDelimit::FindDelimit (char c) : _c0(c), _c1(c)
{
}

SS::FindDelimit::FindDelimit (char left, char right) : _c0(left), _c1(right)
{
}

bool SS::FindDelimit::found (SS const & s, int pos, int& len) const
{
	if (s[pos]==_c0 && pos<s.length()-1 && s[pos+1]==_c1) {
		len=0;
		return true;
	}
	if (pos>0 && s[pos-1]==_c0) {
		int l;
		int p = s.find(FindChar(_c1),pos,&l);
		if (p!=notfound) {
			len = p - pos;
			return true;
		}
	}
	return false;
}

SS::Finder* SS::FindDelimit::clone () const
{
	return new FindDelimit (*this);
}

void SSconvert (SS const & u,                SS & w) { w.assign(u); }
void SSconvert (char const * u,              SS & w) { w.assign(u); }
void SSconvert (unsigned char const * u,     SS & w) { w.assign(u); }
void SSconvert (signed char const * u,       SS & w) { w.assign(u); }
void SSconvert (char u,                      SS & w) { w.assign(u); }
void SSconvert (unsigned char u,             SS & w) { w.assign(u); }
void SSconvert (signed char u,               SS & w) { w.assign(u); }
void SSconvert (bool u,                      SS & w) { w.assign(u); }
void SSconvert (short u,                     SS & w) { w.assign(u); }
void SSconvert (unsigned short u,            SS & w) { w.assign(u); }
void SSconvert (int u,                       SS & w) { w.assign(u); }
void SSconvert (unsigned int u,              SS & w) { w.assign(u); }
void SSconvert (long u,                      SS & w) { w.assign(u); }
void SSconvert (unsigned long u,             SS & w) { w.assign(u); }
void SSconvert (SS::LongLong u,              SS & w) { w.assign(u); }
void SSconvert (SS::ULongLong u,             SS & w) { w.assign(u); }
void SSconvert (float u,                     SS & w) { w.assign(u); }
void SSconvert (double u,                    SS & w) { w.assign(u); }
void SSconvert (long double u,               SS & w) { w.assign(u); }
void SSconvert (SS::string        const & u, SS & w) { w.assign(u); }
void SSconvert (std::vector<char> const & u, SS & w) { w.assign(u); }
void SSconvert (SS::Buffer        const & u, SS & w) { w.assign(u); }

void SSconvertFrom (SS const & u, SS                    & w) { w = u; }
void SSconvertFrom (SS const & u, char const          * & w) { w = u.data(); }
void SSconvertFrom (SS const & u, unsigned char const * & w) { w = reinterpret_cast<unsigned char const *>(u.data()); }
void SSconvertFrom (SS const & u, signed char const   * & w) { w = reinterpret_cast<signed char const *>(u.data()); }
void SSconvertFrom (SS const & u, char                  & w) { w = u.firstChar(); }
void SSconvertFrom (SS const & u, unsigned char         & w) { w = static_cast<unsigned char>(u.firstChar()); }
void SSconvertFrom (SS const & u, signed char           & w) { w = static_cast<signed char>(u.firstChar()); }
void SSconvertFrom (SS const & u, bool                  & w) { w = u.toBool(); }
void SSconvertFrom (SS const & u, short                 & w) { w = u.toShort(); }
void SSconvertFrom (SS const & u, unsigned short        & w) { w = u.toUShort(); }
void SSconvertFrom (SS const & u, int                   & w) { w = u.toInt(); }
void SSconvertFrom (SS const & u, unsigned int          & w) { w = u.toUInt(); }
void SSconvertFrom (SS const & u, long                  & w) { w = u.toLong(); }
void SSconvertFrom (SS const & u, unsigned long         & w) { w = u.toULong(); }
void SSconvertFrom (SS const & u, SS::LongLong          & w) { w = u.toLongLong(); }
void SSconvertFrom (SS const & u, SS::ULongLong         & w) { w = u.toULongLong(); }
void SSconvertFrom (SS const & u, float                 & w) { w = u.toFloat(); }
void SSconvertFrom (SS const & u, double                & w) { w = u.toDouble(); }
void SSconvertFrom (SS const & u, long double           & w) { w = u.toLongDouble(); }
void SSconvertFrom (SS const & u, SS::string            & w) { w = u.toString(); }
void SSconvertFrom (SS const & u, std::vector<char>     & w) { w = u.toVector(); }
void SSconvertFrom (SS const & u, SS::Buffer            & w) { w = SS::Buffer(u.size()); }

int SScompare (SS const & u, SS                const & w) { return u.compare(w); }
int SScompare (SS const & u, char              const * w) { return u.compare(w); }
int SScompare (SS const & u, unsigned char     const * w) { return u.compare(w); }
int SScompare (SS const & u, signed char       const * w) { return u.compare(w); }
int SScompare (SS const & u, char                      w) { return u.compare(w); }
int SScompare (SS const & u, unsigned char             w) { return u.compare(w); }
int SScompare (SS const & u, signed char               w) { return u.compare(w); }
int SScompare (SS const & u, bool                      w) { return u.compare(w); }
int SScompare (SS const & u, short                     w) { return u.compare(w); }
int SScompare (SS const & u, unsigned short            w) { return u.compare(w); }
int SScompare (SS const & u, int                       w) { return u.compare(w); }
int SScompare (SS const & u, unsigned int              w) { return u.compare(w); }
int SScompare (SS const & u, long                      w) { return u.compare(w); }
int SScompare (SS const & u, unsigned long             w) { return u.compare(w); }
int SScompare (SS const & u, SS::LongLong              w) { return u.compare(w); }
int SScompare (SS const & u, SS::ULongLong             w) { return u.compare(w); }
int SScompare (SS const & u, float                     w) { return u.compare(w); }
int SScompare (SS const & u, double                    w) { return u.compare(w); }
int SScompare (SS const & u, long double               w) { return u.compare(w); }
int SScompare (SS const & u, SS::string        const & w) { return u.compare(w); }
int SScompare (SS const & u, std::vector<char> const & w) { return u.compare(w); }

std::ostream& operator << (std::ostream& os, SS const & s)
{
	return os.write (s.data(), s.length());
}