
#ifndef TINYSTL_STRING
#define TINYSTL_STRING

// C mem* and str* functions
#include <string.h>

// realloc
#include <stdlib.h>

#include <istream>
#include <ostream>

namespace std {
  
  /* This is just the start - the string class has quite many
     overloaded methods ... */
  
  template <typename T>
  class basic_string
  {
  public:
    
    typedef int size_type;
    typedef T* iterator;
    typedef const T* const_iterator;
    typedef iterator reverse_iterator;
    typedef const_iterator reverse_const_iterator;
    
    // TODO: should be -1
    static const size_type npos = 2147483647;
    
    basic_string () {
      m_str = 0;
      m_str_size = m_str_alloc = 0;
    }
    
    basic_string (const basic_string& str, size_type idx = 0, size_type len = npos) {
      // TODO: throw out_of_range if idx > str.size() ?
      m_str = 0;
      m_str_size = m_str_alloc = 0;

      size_type l = str.size() - idx;
      l = l < len ? l : len;
      
      assign(str.m_str + idx, l);
    }

    basic_string (const char* cstr) {
      m_str = 0;
      m_str_size = m_str_alloc = 0;
      
      assign(cstr);
    }

    basic_string (const char* chars, size_type chars_len) {
      m_str = 0;
      m_str_size = m_str_alloc = 0;
      
      assign(chars, chars_len);
    }
    
    basic_string (size_type num, char c) {
      m_str = 0;
      m_str_size = m_str_alloc = 0;
      reserve(num);
      memset (m_str, c, num);
      m_str_size = num;
    }
    
    ~basic_string () {
      if (m_str) {
	delete (m_str); 
	m_str = 0;
	m_str_size = m_str_alloc = 0;
      }
    }
    
    basic_string& operator= (const basic_string& str) {
      return assign (str);
    }
    
    basic_string& assign(const basic_string& str) {
      reserve (str.size());
      memcpy(m_str, str.m_str, str.size());
      m_str_size = str.size();
      return *this;
    }

    basic_string& assign(const char* cstr) {
      size_type cstr_len = strlen(cstr);
      reserve (cstr_len);
      memcpy(m_str, cstr, cstr_len);
      m_str_size = cstr_len;
      return *this;
    }

    basic_string& assign(const char* chars, size_type chars_len) {
      reserve (chars_len);
      memcpy(m_str, chars, chars_len);
      m_str_size = chars_len;
      return *this;
    }
    
    // TODO: swap();
    
    // TODO: more +=s
    
    basic_string& append (const basic_string& str) {
      reserve (size() + str.size());
      memcpy (m_str + m_str_size, str.m_str, str.size());
      m_str_size += str.size();
      return *this;
    }
    
    basic_string& operator+= (const basic_string& str) {
      return append (str);
    }
    
    basic_string& append (const basic_string& str, size_type str_idx, size_type str_num) {
      if (str_num == npos)
	str_num = str.size() - str_idx;
      
      reserve (size() + str_num);
      
      memcpy (m_str + m_str_size, str.m_str + str_idx, str_num);
      m_str_size += str_num;
      return *this;
    }
    
    basic_string& append (char c) {
      reserve (size() + 1);
      m_str [m_str_size++] = c;
      return *this;
    }

    basic_string& operator+= (char c) {
      return append (c);
    }
    
    basic_string& push_back(char c) {
      return append (c);
    }
    
    /*insert(); */
    
    void clear() {
      m_str_size = 0;
      reserve (m_str_size);
    }
    
    // TODO: iterator erases ...
    basic_string& erase() {
      clear();
      return *this;
    }
    
    basic_string& erase(size_type idx, size_type len = npos) {
      // TODO: range check, exception ...
      
      if (len == npos)
	len = m_str_size - idx;
      
      if (idx + len == m_str_size)
	m_str_size = idx;
      else {
	memmove (m_str + idx, m_str + idx + len, m_str_size - idx - len);
	m_str_size -= len;
      }
      return *this;
    }
    
    /* resize(); */
    
    // TODO: more replaces
    basic_string& replace(size_type idx, size_type len, const basic_string& str,
		    size_type str_idx = 0, size_type str_num = npos) {
      if (len == npos)
	len = size() - idx;
      if (str_num == npos)
	str_num = str.m_str_size - str_idx;
      
      for ( ; idx < m_str_size && str_idx < str.m_str_size &&
	      len > 0  && str_num > 0 ; --len, --str_num) {
	m_str [idx++] = str [str_idx++];
      }
      if (str_num > 0)
	append (str, str_idx, str_num);
      else if (len > 0)
	erase (idx, len);
      return *this;
    }
    
    basic_string& replace(size_type idx, size_type len,
		    const char* chars, size_type chars_len) {
      size_type end = idx + len;
      reserve (end);
      
      for ( ; idx < end  && chars_len > 0 ; ) {
	// TODO: range check with throw out_of_range exception?
	m_str [idx++] = *chars++; --chars_len;
      }
      return *this;
    }

    basic_string& replace(size_type idx, size_type len, const char* cstr) {
      return replace(idx, len, cstr, strlen(cstr));
    }
    
    bool operator== (const basic_string& str) const {
      if (size() != str.size())
	return false;
      else
	return memcmp (m_str, str.m_str, size()) == 0;
    }
    
    bool operator!= (const basic_string& str) const {
      return !operator== (str);
    }
    

    /*
    <();
    <=();
    >();
    >=();
    compare(); */
    
    size_type size() const {
      return m_str_size;
    }
    
    size_type length() const {
      return size();
    }

    // TODO: max_size() const
    
    bool empty() const {
      return m_str_size == 0;
    }
    
    size_type capacity() const {
      return m_str_alloc;
    }
    
    void reserve () {
      reserve (m_str_size);
    }
    
    void reserve (size_type num) {
      // assumes realloc (NULL, num) is equivalent to malloc (num) ...
      
      if (num > m_str_alloc) {
	m_str_alloc = num > m_str_alloc + m_block_size ? num :
	  m_str_alloc + m_block_size;
	m_str = (char*)realloc (m_str, m_str_alloc);
      }
      else if (num + m_block_size < m_str_alloc && num >= m_str_size) {
	m_str_alloc = num > m_str_size + m_block_size ? num :
	  m_str_size + m_block_size;
	m_str = (char*)realloc (m_str, m_str_alloc);
      }
    }
    
    char& operator[] (size_type idx) {
      return m_str[idx];
    }
    char operator[] (size_type idx) const {
      return m_str[idx];
    }
    
    char& at (size_type idx) {
      return m_str[idx];
    }
    char at (size_type idx) const {
      return m_str[idx];
    }
    
    // TODO: copy();
    
    const char* c_str () const {
      // temp. zero termination
      const_cast<basic_string*> (this)->reserve(size()+1);
      m_str[size()] = 0;
      return m_str;
    }
    const char* data () const {
      return m_str;
    }
    
    basic_string substr (size_type idx = 0, size_type len = npos) const {
      return basic_string (*this, idx, len);
    }
    
    iterator begin() {
      return m_str;
    }
    const_iterator begin() const {
      return m_str;
    }
    
    iterator end() {
      return m_str + m_str_size + 1;
    }
    const_iterator end() const {
      return m_str + m_str_size + 1;
    }
    
    reverse_iterator rbegin();
    reverse_const_iterator rbegin() const;
    
    reverse_iterator rend();
    reverse_const_iterator rend() const;
    
    // find
    size_type find (const char c, size_type idx = 0) const {
      for (size_type i = idx; i < m_str_size; ++i)
	if (m_str[i] == c)
	  return i;
      return npos;
    }
    
    size_type find (const basic_string& str, size_type idx = 0) const {
      return find (str.m_str, idx, str.m_size);
    }
    
    size_type find (const char* cstr, size_type idx = 0) const {
      return find (cstr, idx, strlen(cstr));
    }
    
    size_type find (const char* chars, size_type idx,
		    size_type chars_len) const {
      for ( ;idx < m_str_size; ++idx) {
	const char* c = chars;
	while (c != chars + chars_len &&
	       idx < m_str_size &&
	       m_str[idx] == *c) {
	  ++c; ++idx;
	}
	if (c == chars + chars_len)
	  return idx;
      }
      return npos;
    }
    
    // find_first
    size_type find_first_of (const basic_string& str, size_type idx = 0) const {
      return find_first_of (str.m_str, idx, str.m_str_size);
    }
    
    size_type find_first_not_of (const basic_string& str, size_type idx = 0) const {
      return find_first_not_of (str.m_str, idx, str.m_str_size);
    }

    size_type find_first_of (const char* cstr, size_type idx = 0) const {
      return find_first_of (cstr, idx, strlen(cstr));
    }
    
    size_type find_first_not_of (const char* cstr, size_type idx = 0) const {
      return find_first_not_of (cstr, idx, strlen(cstr));
    }

    size_type find_first_of (const char* chars, size_type idx,
			     size_type chars_len) const {
      for ( ;idx < m_str_size; ++idx)
	for (const char* c = chars; c != chars + chars_len; ++c)
	  if (m_str[idx] == *c)
	    return idx;
      return npos;
    }
    
    size_type find_first_not_of (const char* chars, size_type idx,
				 size_type chars_len) const {
      for ( ;idx < m_str_size; ++idx) {
	const char* c = chars;
	for ( ; c != chars + chars_len; ++c)
	  if (m_str[idx] == *c)
	    break;
	
	if (c == chars + chars_len)
	  return idx;
      }
      return npos;
    }

    size_type find_first_of (const char c, size_type idx = 0) const {
      for ( ;idx < m_str_size; ++idx)
	if (m_str[idx] == c)
	  return idx;
      return npos;
    }
    
    size_type find_first_not_of (const char c, size_type idx = 0) const {
      for ( ;idx < m_str_size; ++idx)
	if (m_str[idx] != c)
	  return idx;
      return npos;
    }
    
    // find_last
    size_type find_last_of (const basic_string& str, size_type idx = 0) const {
      return find_last_of (str.m_str, idx, str.m_str_size);
    }
    
    size_type find_last_not_of (const basic_string& str, size_type idx = 0) const {
      return find_last_not_of (str.m_str, idx, str.m_str_size);
    }

    size_type find_last_of (const char* cstr, size_type idx = 0) const {
      return find_last_of (cstr, idx, strlen(cstr));
    }
    
    size_type find_last_not_of (const char* cstr, size_type idx = 0) const {
      return find_last_not_of (cstr, idx, strlen(cstr));
    }
    
    size_type find_last_of (const char* chars, size_type idx,
			    size_type chars_len) const {
      for (size_type i = m_str_size - 1; i > 0 && i >= idx; --i) {
	for (const char* c = chars; c != chars + chars_len; ++c)
	  if (m_str[i] == *c)
	    return i;
      }
      return npos;
    }
    
    size_type find_last_not_of (const char* chars, size_type idx,
				 size_type chars_len) const {
      for (size_type i = m_str_size - 1; i > 0 && i >= idx; --i) {
	const char* c = chars;
	for ( ; c != chars + chars_len; ++c)
	  if (m_str[i] == *c)
	    break;
	
	if (c == chars + chars_len)
	  return i;
      }
      return npos;
    }

    size_type find_last_of (const char c, size_type idx = 0) const {
      for (size_type i = m_str_size - 1; i > 0 && i >= idx; --i)
	if (m_str[idx] == c)
	  return i;
      return npos;
    }
    
    size_type find_loast_not_of (const char c, size_type idx = 0) const {
      for (size_type i = m_str_size - 1; i > 0 && i >= idx; --i)
	if (m_str[idx] != c)
	  return i;
      return npos;
    }
    
    // TODO: rfind
    
    //get_allocator();
    
  private:
    
    char* m_str;
    size_type m_str_size;
    size_type m_str_alloc;
    
    const static size_type m_block_size = 16;
  };
  
  template <typename T>
  basic_string<T> operator+ (const basic_string<T>& str1,
			     const basic_string<T>& str2) {
    basic_string<T> s (str1);
    s += str2;
    return s;
  }

  template <typename T>
  basic_string<T> operator+ (const basic_string<T>& str, const char* cstr) {
    basic_string<T> s (str);
    s += cstr;
    return s;
  }

  template <typename T>
  basic_string<T> operator+ (const char* cstr, const basic_string<T>& str) {
    basic_string<T> s (cstr);
    s += str;
    return s;
  }
  
  template <typename T>
  basic_string<T> operator+ (const basic_string<T>& str, char c) {
    basic_string<T> s (str);
    s += c;
    return s;
  }
  
  template <typename T>
  basic_string<T> operator+ (const char c, const basic_string<T>& str) {
    basic_string<T> s (1, c);
    s += str;
    return s;
  }
  
  template <typename T>
  ostream& operator<< (std::ostream& os, basic_string<T> s) {
    return os.write (s.c_str(), s.size());
  }

  template <typename T>
  istream& operator>> (std::istream& is, basic_string<T>& s) {
    s.clear();
    int c;
    do {
      c = is.get();
      if (c == ' ')
	is.putback (c);
                    // TODO: '\n' is a _HACK_ !!! get rid of it !!!
      else if (c != '\n' && c != EOF)
	s.push_back (c);
    } while (c != ' ' && is.good());
    return is;
  }
  
  template <typename T>
  bool getline (std::istream& is, basic_string<T>& s, char delim = '\n') {
    s.clear();
    while (1) {
      int c = is.get();
      if (c != EOF && c != delim)
        s.push_back (c);
      else
       break;
    }
    return !is.fail();
  }
  
  typedef basic_string<char> string;
}

#endif // TINYSTL_STRING
