#ifndef SSTRING_H
#define SSTRING_H

/**
 * sstring is a C++ string class utilizing both stack and heap
 * allocations and having an STL-compatible interface.
 *
 * WARNING: This is a work in progress.  It generally works but
 * the interface is not fully implemented, and a test suite has
 * not yet been written.
 *
 * The main purpose of this class is to provide a string that
 * allocates its memory predominately or entirely from the stack
 * rather than the heap.  The reason for avoiding heap allocations is
 * that they can be relatively expensive (and may also introduce
 * memory fragmentation).  Heap-predominant implementations like STL's
 * std::basic_string can be an order or magnitude slower than pure
 * stack implementations such as char arrays.  See the included
 * sstring_benchmark.cpp for benchmark comparisons using this class.
 * In a simple test, one finds sstring to be up to an order of
 * magnitude faster than std::basic_string and a bit slower than char
 * arrays.  However, this class may be worse in other situations, so
 * use it only when the benefit is clear.
 *
 * The implementation of this class contains a char buffer of size N
 * specified as a template parameter, e.g.
 *
 *   sstring<100> s;
 *
 * If such a string is declared on the stack, then it contains a
 * buffer of size 100 characters also contained on the stack.  If the
 * string grows beyond the space allocated on the stack, then
 * sufficient memory is transparently allocated from the heap to avoid
 * overflow.  It is implemented like this:
 *
 *   template <size_t N, class C = char, class T = std::char_traits<char> >
 *   class sstring {
 *     ...
 *     size_t m_size;   // size of string buffer
 *     size_t m_length; // length of string
 *     C m_buf[N+1];    // stack space
 *     C * m_p;         // pointer to string (stack or heap space)
 *     bool m_is_stack; // whether stack space is used
 *   };
 *
 * This class provides an interface similar to STL's std::basic_string
 * (http://www.sgi.com/tech/stl/basic_string.html).  Therefore, a
 * major advantage is that it can be used with the Boost string
 * algorithms library
 * (http://www.boost.org/doc/html/string_algo.html).
 *
 * Some implementations of the STL std::basic_string (e.g. as in
 * MSVC++2005) actually do take a similar approach as this class.  The
 * only difference is that the size of the buffer on the stack is
 * fixed at some small number (16 on MSVC++2005) and cannot be changed
 * by the client.  That may provide a performance enhancement for
 * small strings but has little benefit (in fact would make things
 * worse) for larger strings such as file names up to length MAX_PATH
 * (a few hundred characters).
 *
 * The approach and goals here are also similar to that by Olivier
 * Lombart in
 * ( http://www.codeproject.com/string/Allocdynstringsonstack.asp ).
 * However, that used C macros (rather than templates here) and does
 * not have the benefits of the STL interface such as Boost string
 * algorithms support.
 *
 * Another approach I had tried was to write my own memory allocator
 * for STL's std::basic_string to allocate from the stack.
 * This allocator was either my own trivial memory
 * pool or a slightly more complete Boost pool
 * (http://www.boost.org/libs/pool/doc/index.html) that allocated
 * preferentially from the stack, else from the heap.  The memory
 * manager was easily replaced upon entering and exiting scope.
 * Here is an example usage:
 *   void test() {
 *     // allocate 500 chars from stack and install a localized memory
 *     // manager for stack_string objects. This is destroyed on
 *     // scope exit via RAII*.
 *     stack_pool<char, 500>;
 *     stack_string s = "test"; // allocate srting from the above stack pool.
 *   }
 *   // * http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization
 * Here's some related references on customer memory allocators in STL:
 *   http://www.codeguru.com/Cpp/Cpp/cpp_mfc/stl/article.php/c4079/
 *   http://www.sgi.com/tech/stl/alloc.html
 *   http://www.ddj.com/dept/cpp/184403759
 *   http://bmagic.sourceforge.net/memalloc.html
 * The advantage of this approach was that 100% compatibility with
 * std::basic_string was easily achieved, and it can be easily and
 * transparently used in other STL classes (e.g. std::vector).  The
 * only problem with this was that real speed improvements were not
 * achieved on std::basic_string.  I confirmed that the slowness was
 * not due to the memory manager but rather it was likely due to the
 * complexity of STL std::basic_string itself.  In fact, the
 * std::basic_string approach is non-optimal since as mentioned above
 * some implementations already use local stack memory space, which is
 * redundant.  Also, the approach requires some care to avoid string
 * objects hanging around after its stack space has gone out of
 * scope.  That's easy to avoid, but it does make the approach feel
 * less natural.
 *
 * This class also has some similarity to boost::array
 * (http://www.boost.org/doc/html/array.html), but it works like
 * a string (having a variable length and '\0' termination)
 * and can allocate off the heap if stack space runs out.
 *
 * The comments in the std::basic_string implementation in STLport
 * (www.stlport.org) (stl/_string.h) are interesting.  One may
 * ask why use a std::basic_string when you can use a std::vector.
 * There's isn't much good reason except std::basic_string has various
 * accessory string manipulation functions.  However, I think it would
 * be better for these functions not to be part of the string class
 * but rather be accessible in the manner of the Boost string algorithms
 * library (http://www.boost.org/doc/html/string_algo.html).  For example,
 *   vector<char> s;
 *   s.push_back(' '); s.push_back('o'); s.push_back('k'); s.push_back(' ');
 *   trim(s);  // a Boost string function
 *   vector<char> s2; s.push_back('o');
 *   vector<char> s3; s.push_back('z'); s.push_back('z');
 *   replace(s, s2, s3);  // a Boost string function
 * 
 * Like many implementations of std::string, this class does not
 * attempt copy-on-write (COW) or such (http://www.ddj.com/dept/cpp/184403784).
 *
 * @author David Manura, 2006-07
 * (c) 2006 David Manura
 * Distributed under the Boost Software License, Version 1.0. (www.boost.org)
 */

#include <ostream>

// N = characters stored in stack
// C = char type
// T = std::char_traits
template <size_t N, class C = char, class T = std::char_traits<char> >
class sstring
{
public:
    /** STL iterator */
    typedef const C * const_iterator;

    /** STL iterator */
    typedef C * iterator;

    /** default constructor, empty string "" */
    sstring() : m_size(N), m_length(0), m_p(m_buf), m_is_stack(true) {
        m_p[0] = '\0';
    }

    /** construct from another object, possibly of different N */
    template <size_t N2>
    sstring(const sstring<N2>& other)
      : m_length(other.m_length)
    {
        p_construct(other.m_length);
        T::copy(m_p, other.m_p, other.m_length + 1); // include '\0' terminator
    }

    /** STL */
    template <class InputIterator>
    sstring(InputIterator first, InputIterator last) {
        size_t len = last - first; // FIX-ok?
        m_length = len;
        p_construct(len);
        T::copy(m_p, first, len + 1); // include '\0' terminator
    }

    /** STL */
    sstring(const C * s)
       : m_length(T::length(s))
    { 
        p_construct(m_length);
        T::copy(m_p, s, m_length + 1); // include '\0' terminator
    } 

    /** STL */
    sstring(const C * s, size_t len)
      : m_length(len)
    {
        p_construct(len);
        T::copy(m_p, s, len + 1); // include '\0' terminator
    }

    // reserve at least--fix: reserve less too
    void reserve(size_t sz) {
        if (m_is_stack) {
            if (sz > N) {
                // convert from stack to heap
                m_p = new C[sz + 1];
                m_size = sz;
                m_is_stack = false;

                T::copy(m_p, m_buf, m_length + 1);
            }
        }
        else {
            if (sz > m_size) {
                // increase heap
                C * p = new C[sz + 1];
                T::copy(p, m_p, m_length + 1);
                delete m_p;
                m_p = p;
            }
        }
    }

    /** STL */
    sstring & append(const C * s) { 
        size_t sz = T::length(s);
        if (m_length + sz > m_size) {
            reserve(m_length + sz);
        }
        T::copy(m_buf + m_length, s, sz);
        m_length += sz;
        m_buf[m_length] = '\0';
        return *this;
    }

    template <size_t N2>
    sstring & append(const sstring<N2> & other) {
        size_t sz = other.length();
        if (m_length + sz > m_size) {
            reserve(m_length + sz);
        }
        T::copy(m_buf + m_length, other.c_str(), sz);
        m_length += sz;
        m_buf[m_length] = '\0';
        return *this;
    }

    /** STL */
    C * begin() const { return m_p; }

    /** STL */
    C * end() const { return m_p + m_length; }

    /** STL */
    const C * c_str() const { return m_p; }

    /** STL */
    size_t length() const { return m_length; }

    /** STL */
    size_t size() const { return m_size; } //FIX:rename capacity

    /** STL */
    //FIX: what if erase(end()) ?
    iterator erase(iterator p) {
        T::move(p, p+1, m_p + m_length - p - 1);
        m_length--;
        return p; //FIX--correct?
    }

    /** STL */
    //FIX: what if erase(end()) ?
    iterator erase(iterator p, iterator q) {
        T::move(p, q, m_p + m_length - q);
        m_length -= (q - p);
        return p; //FIX--correct?
    }

    /** STL */
    iterator insert(iterator p, const C& x) {
        if (m_length + 1 > m_size) {
            reserve(m_length + 1);
        }
        T::move(p+1, p, m_p + m_length - p + 1); // note: include '\0' terminator
        m_length++;
        return p; //FIX-ok?
    }

    /** STL */
    template <class InputIterator>
    iterator insert(iterator pos, InputIterator f, InputIterator l) {
        size_t sz = l-f; // FIX-ok?
        if (m_length + sz > m_size) {
            reserve(m_length + sz);
        }
        T::move(pos + sz, pos, sz + 1); // noet: include '\0' terminator
        m_length += sz;
        return pos; //FIX-ok?
    }

    /** STL */
    sstring<N> & operator += (const C * other) {
        return append(other);
    }

    /** STL */
    template <size_t N2>
    sstring<N> & operator += (sstring<N2> & other) {
        return append(other);
    }

private:

    // construct space for string of size len.
    void p_construct(size_t len) {
        if (len <= N) {
           // make on stack
            m_is_stack = true;
            m_size = N;
            m_p = m_buf;
        }
        else {
            // make on heap
            m_is_stack = false;
            m_size = m_length;
            m_p = new C[len + 1];
        }
    }

    size_t m_size;   /** capacity of buffer (not including '\0') */
    size_t m_length; /** length of srting */
    C m_buf[N+1];    /** stack buffer */
    C * m_p;         /** pointer to either stack or heap bufffer */
    bool m_is_stack; /** whether stack buffer is used */

    template <size_t N2, class C2, class T2>
    friend class sstring;
};

/** STL */
template <class C, class T, size_t N>
std::basic_ostream<C, T>& 
operator << (std::basic_ostream<C, T>& os, sstring<N,C> & s)
{
    os.write(s.c_str(), s.length());
    return os;
}

#endif // first include