/******************************************************************************
**	fsc.h : FastStringConcatenation
**	Helper class for accelerating concatenation of strings.
**
**	The idea is to replace the concatenation of strings by the aggregation
**	of datatypes storing the evaluation tree in nodes.
**	Finally, before the affectation to a string with the '=' operator,
**	the node representing the top concatenation evaluates recursively
**	the length of each node, reserve a string big enough, then copies
**	the source strings at the right place.
**	Pros:
**	- Avoids the creation of temporary strings.
**	- Avoids all useless memory copies.
**	- Can be totally inlined.
**	Cons:
**	- Slower compilation.
**	- Code size increase due to inlining and specialised types.
**
**	To summarize, the concatenation is done into two recursive passes
**	starting from the top node, and walking the nodes tree from left to
**	right, in depth first.
**	- The reservation passes which computes and adds the maximum number
**	of chars taken by each variable to concatenate. At the end, a string
**	is created with the right allocation size (equal or bigger than needed).
**	- The copy passes which does the same tree walks, and copies each
**	individual variable to the destination.
**
**	Usage exemple:
**	This kind of concatenation :
**	string a = string("b") + "cc" + 'd' + string("e");
**	... just need to be changed this way :
**	string a = fsc() + string("b") + "cc" + 'd' + string("e");
******************************************************************************/

#ifndef fsc_include_h
#define fsc_include_h

#include <stdlib.h>
#include <string>
#include <iterator>

using namespace std ;

namespace fsc {

/******************************************************************************
**	fake_it
**	This special kind of operator allows to reserve the memory size
**	we want, but the copy does not do anything. Works with StlPort.
******************************************************************************/

template< class _CharT >
struct fake_it {
	size_t _Capa ;
	typedef typename std::iterator_traits< _CharT *>::iterator_category
		iterator_category ;
	typedef _CharT                   value_type ;
	typedef size_t                   difference_type ;
	typedef _CharT *                 pointer ;
	typedef _CharT &                 reference ;

	inline fake_it() { };
	inline fake_it(size_t aN) : _Capa(aN) { };

	// The copy loop cannot do anything. 
	inline bool operator==( const fake_it & ) { 
		return false ; 
	};
	inline bool operator!=( const fake_it & ) { 
		return false ; 
	};
	inline size_t operator - (const fake_it & aL) const {
		return _Capa - aL._Capa ; 
	};

	inline fake_it & operator++(void) { 
		return *this ; 
	};
	inline _CharT operator * (void) const { 
		return value_type(); 
	};
};

/******************************************************************************
**	assign
**	Faster than the '=' equal operator because no copy is necessary.
******************************************************************************/
template< class T1, class T2 > class pair ;

// If the target of the '=' equal operator is a std::string.
template< class T1, class T2, class _StringT >
inline void assign( _StringT & aS, const pair< T1, T2 > & aF ) {
	aS.resize( aF._capa );
	typedef typename _StringT::value_type char_type ;
	char_type * myData = (char_type *)aS.data();
	char_type * myPtr = aF.append( myData );

	// The real length may be shorter than what was allocated.
	size_t myRealLen = myPtr - myData ;
	if( myRealLen != aF._capa ) aS.resize( myRealLen );
} // assign

/******************************************************************************
**	pair
**	Stores the concatenation of two elements.
******************************************************************************/

// Forward declaration.
template< class T > class node ;

template< class T1, class T2 >
class pair {
public:
	size_t _capa ;
	// Each contains an instance of the template class node.
	T1 _left ;
	T2 _right ;

	// T1::char_type and T2::char_type must be identical.
	typedef typename T1::char_type char_type ;

	// The constructor does the reservation pass.
	inline pair ( const T1 & aLft, const T2 & aRgt )
	: _left(aLft), _right(aRgt), _capa(aLft.capacity() + aRgt.capacity()) {};

	// The 'string' concatenation now returns a new datatype.
	template< class U >
	inline pair< pair, node< U > >
	operator + ( const U & aU ) const {
		return pair< pair, node< U > >( *this, node< U >( aU ) ) ;
	}

	// Called at reservation pass.
	inline size_t capacity(void) const { return _capa ; };

	// Called at concatenation pass. Receives  a pointer to the internal buffer
	// of the string to return. Copies its content then return the address of the
	// first free bytes where the next variable will be copied.
	// The concatenation pass is triggered by the conversion to the result string.
	inline char_type * append( char_type * aPtr ) const {
		return _right.append( _left.append( aPtr ) );
	};

	// If the target of the '=' equal operator is a std::string.
	template< typename _Traits, typename _Alloc >
	inline operator std::basic_string< char_type,_Traits,_Alloc >() const {
		typedef std::basic_string< char_type,_Traits,_Alloc > _StringT ;
		_StringT myRes( fake_it< char_type >(0), fake_it< char_type >(_capa) );
		char_type * myData = (char_type *)myRes.data();
		char_type * myPtr = append( myData );

		// The real length may be shorter than what was allocated.
		// This is easier to find the biggest possible size
		// of an temp string.
		size_t myRealLen = myPtr - myData ;
		if( myRealLen != _capa ) myRes.resize( myRealLen );

		return myRes ;
	}
}; // pair

/******************************************************************************
**	node
**	This objects stores each final node (i.e. each base element to be
**	concatenated into the final string). There is a specialised template
**	for each datatype that can be concatenated into a string.
******************************************************************************/

// The default template class should never be instantiated: This would mean
// that a specialization is not setup. Each of these specializations must
// have two members :
// capacity() which returns the maximum size of the string.
// append() which actually concats its string representation and returns
// the next pointer.
template< class T > class node {};

template< class T, class U > inline pair< node< T >, node< U > >
operator + ( const node< T > &aT, const U & aU ) {
	return pair< node< T >, node< U > >( aT, node< U >(aU) );
}

template< class _CharT, class _Traits, class _Alloc >
class node< basic_string< _CharT,_Traits,_Alloc > > {
	typedef basic_string< _CharT,_Traits,_Alloc > _StringT ;
	const _StringT & _obj ;
public:
	typedef _CharT char_type ;
	inline node( const _StringT & aObj ) : _obj(aObj) {}
	inline size_t capacity(void) const {
		// This function is inlined, and it is faster to call it
		// twice than to store its result in this object.
		return _obj.size();
	};
        inline char_type * append( char_type * aPtr ) const {
		return std::copy( _obj.begin(), _obj.end(), aPtr );
	};
};

template< class _CharT > class node< _CharT * > {
	const _CharT  * _obj ; // Reference to the string to concat.
	mutable size_t  _len ;
public:
	typedef _CharT char_type ;
	inline node( const _CharT * aObj ) : _obj(aObj) {}
	inline size_t capacity(void) const {
		return _len = std::char_traits< _CharT >::length(_obj) ;
	};
        inline char_type * append( char_type * aPtr ) const {
		return std::char_traits< _CharT >::copy( aPtr, _obj, _len ) + _len ;
	};
};

template< class _CharT > class node< const _CharT * > {
	const _CharT  * _obj ; // Reference to the string to concat.
	mutable size_t  _len ;
public:
	typedef _CharT char_type ;
	inline node( const _CharT * aObj ) : _obj(aObj) {}
	inline size_t capacity(void) const {
		return _len = std::char_traits< _CharT >::length(_obj) ;
	};
        inline char_type * append( char_type * aPtr ) const {
		return std::char_traits< _CharT >::copy( aPtr, _obj, _len ) + _len ;
	};
};

// When concatenating a fixed-size char array (A constant string).
template< class _CharT, int N >
class node< _CharT[ N ] > {
	const _CharT * _obj ; // Reference to the string to concat.

	static const int Sz = N - 1 ; // Chops the ending 0 char.
	// No need to store the string length because it is a template parameter.

	// For copying memory. Works ok if memory padding is big enough.
	typedef struct { _CharT anonymous[Sz]; } carrN ;
public:
	typedef _CharT char_type ;
	inline node( const _CharT aObj[Sz] ) : _obj(aObj) {}
	inline size_t capacity(void) const { return Sz ; };
        inline char_type * append( char_type * aPtr ) const {
		// Faster than memcpy(), because the compiler knows the size.
		*( carrN * )aPtr = *( const carrN * )_obj ;
		return aPtr + Sz ;
	};
};

// When an 'char' is concatenated to a string.
// Any other datatype can be specialised this way.
template<> class node< char > {
	char _obj ;
public:
	typedef char char_type ;
	inline node( char aObj ) : _obj(aObj) {}
	inline size_t capacity(void) const { return 1 ; };
        inline char * append( char * aPtr ) const {
		*aPtr = _obj ;
		return aPtr + 1 ;
	};
};

template<> class node< wchar_t > {
	wchar_t _obj ;
public:
	typedef wchar_t char_type ;
	inline node( wchar_t aObj ) : _obj(aObj) {}
	inline size_t capacity(void) const { return 1 ; };
        inline wchar_t * append( wchar_t * aPtr ) const {
		*aPtr = _obj ;
		return aPtr + 1 ;
	};
};

/******************************************************************************
**	setup
** To benefit from these concatenation speed ups, an object of this type,
** must be put just after the '=' equal sign. Then all following objects
** or variables to be concatenated are, converted to TSO_One<> objects,
** which themselves are recursively assembled into pair<> objects.
** Ex:
** std::string myR = std::string("a") + "b" + "c"
**    ... must be changed into ...
** std::string myR = fsc() + std::string("a") + "b" + "c"
******************************************************************************/
class fsc {
public:
	template<class T> inline node< T >
	operator + ( const T & aT ) const {
		return node< T >(aT);
	}
};

} // namespace fsc ;

#endif // fsc_include_h
/******************************************************************************
**
******************************************************************************/