#ifndef _MATT_STRING
#define _MATT_STRING

#include <new>
#include <cstring>

#include <stdio.h>
#include <assert.h>

namespace std {

template< class Char >
class basic_string {
public:
   typedef Char * iterator;
   typedef unsigned int size_type;

private:
   Char * array;
   size_t the_size;

public:
   static unsigned int npos;


   basic_string() {
//printf("basic_string::basic_string()\n");
      the_size = 0;
//printf("basic_string...\n");
      array = new Char[1];
///printf("basic_string...\n");
      memset(array, 0, 1);
//printf("basic_string...\n");
   }

   basic_string(const Char & ch) {
      the_size = 1;
      array = new char[2];
      memset(array, 0, 2);
   }

   basic_string(const Char * str) {
//printf("basic_string::basic_string(%s)\n", str);
//printf("this == %d\n", this);
      the_size = strlen(str);
      array = new Char[the_size+1];
      memset(array, 0, the_size+1);
      strcpy(array, str); 
   }

   basic_string(const basic_string & cp) {
//printf("basic_string::basic_string(%s)\n", cp.array);
//printf("this == %d\n", this);
      the_size = cp.the_size;
      array = new Char[the_size+1];
      memset(array, 0, the_size+1);
      strcpy(array, cp.array);
   }

   void clear() {
      if(the_size != 0) {
         delete [] array;
         the_size = 0;
         array = new Char[1];
         array[0] = '\0';
      }
   }

   void erase(iterator & it) {
      size_t i = 0;
      while(&array[i] != it) {
         i++;
      }
      for(size_t j = i; j < strlen(&array[i]); j++)
         array[j] = array[j+1];
      the_size--;
      array[the_size] = '\0';
   }

   ~basic_string() {
      delete [] array;
   }

   size_type rfind(const basic_string & str) const {
      size_type index = npos;
      if(size() > str.size()) { 
         for(int i = size()-str.size(); i >= 0; i--) {
            index = i;
            for(int j = 0; j < str.size(); j++) {
               if(array[i] == str[i]) {

               }
               else {
                  index = npos;
                  break;
               } 
            }
         }
      }
      return index;
   }

   basic_string & operator=(const basic_string & right) {
//printf("basic_string::operator=(const basic_string & right)\n");
      if(array == right.array) {
      }
      else {
         if(array)
            delete [] array;
         array = new Char[right.the_size+1];
         memset(array, 0, right.the_size+1);
         strcpy(array, right.array);
         the_size = right.the_size;
      }
      return *this;
   }

   basic_string & operator=(const Char ch) {
      delete [] array;
      array = new Char[2];
      array[0] = ch;
      array[1] = '\0';
      the_size = 1;
      return *this;
   }

   basic_string & operator=(const Char * str) {
//printf("basic_string::operator=(const Char * str)\n");
      delete [] array;
      the_size = strlen(str);
      array = new Char[the_size+1];
      memset(array, 0, the_size+1);
      strcpy(array, str);
      return *this;
   }

   Char & operator[](const size_t i) { return array[i]; }
   Char & operator[](const size_t i) const { return array[i]; }

   basic_string operator+(const basic_string & right) const {
      basic_string retval2;
      Char * temp = new Char[right.the_size + the_size + 1];
      memset(temp, 0, right.the_size + the_size + 1);
      strcpy(temp, array);
      strcat(temp, right.array);
      delete [] retval2.array;
      retval2.array = temp;
      retval2.the_size = right.the_size + the_size;
      return retval2;
   }

   basic_string operator+(const Char * right) const {
      basic_string retval;
      unsigned int right_size = strlen(right);
      Char * temp = new Char[right_size + the_size + 1];
      memset(temp, 0, right_size + the_size + 1);
      strcpy(temp, array);
      strcat(temp, right);
      delete [] retval.array;
      retval.array = temp;
      retval.the_size = right_size + the_size;
      return retval;
   }

   basic_string operator+(const Char & right) const {
      basic_string retval;
      retval += right;
      return retval;
   }

   basic_string & operator+=(const Char & right) {
      Char * temp;
      temp = new Char[the_size + 1 + 1];
      strcpy(temp, array);
      temp[the_size] = right;
      the_size++;
      temp[the_size] = '\0';
      delete [] array;
      array = temp;
      return *this;
   }

   basic_string & operator+=(const basic_string & right) {
      Char * temp;
      temp = new Char[the_size + right.the_size + 1];
      the_size = the_size + right.the_size;
      memset(temp, 0, the_size + 1);
      strcpy(temp, array);
      strcat(temp, right.array);
      delete [] array;
      array = temp;
      return *this;
   }

   basic_string & operator+=(const Char * right) {
      Char * temp;
      temp = new Char[the_size + strlen(right) + 1];
      the_size = the_size + strlen(right);
      memset(temp, 0, the_size + 1);
      strcpy(temp, array);
      strcat(temp, right);
      delete [] array;
      array = temp;
      return *this;
   }

   size_t size() const {
      return the_size;
   }

   basic_string substr(const size_t offset) const {
      Char * ptr = array + offset;
      return basic_string(ptr);
   }

   basic_string substr(const size_t offset, const size_t count) const {
      basic_string retval;
      Char * ptr;
      ptr = array + offset;
      for(size_t i = 0; i < count; i++) {
         retval += *ptr;
         ptr++;
      }
      return retval;
   }


   size_type find(const Char * str) const {
      if(the_size < strlen(str)) return npos;
      char * ptr = strstr(array, str);
      if(ptr) {
         size_type index = (size_type)(ptr - array);
         return index;
      }
      return npos;
   }

   size_type find(const basic_string & str) const {
      if(the_size < strlen(str.c_str())) return npos;
      char * ptr = strstr(array, str.array);
      if(ptr) {
         size_type index = (size_type)(ptr - array);
         return index;
      }
      return npos;
   }

   size_type find(const Char * str) {
      if(the_size < strlen(str)) return npos;
      char * ptr = strstr(array, str);
      if(ptr) {
         size_type index = (size_type)(ptr - array);
         return index;
      }
      return npos;
   }

   size_type find(const basic_string & str) {
      if(the_size < strlen(str.c_str())) return npos;
      char * ptr = strstr(array, str.array);
      if(ptr) {
         size_type index = (size_type)(ptr - array);
         return index;
      }
      return npos;
   }


   const Char * c_str() const { 
      return array;
   }

   const Char * c_str() { 
      return array;
   }

   bool operator==(const basic_string & right) {
      return strcmp(array, right.array) == 0;
   }

   bool operator!=(const basic_string & right) {
      return strcmp(array, right.array) != 0;
   }

   bool operator<(const basic_string & right) {
      return strcmp(array, right.array) < 0;
   }

   bool operator<=(const basic_string & right) {
      return strcmp(array, right.array) <= 0;
   }

   bool operator>(const basic_string & right) {
      return strcmp(array, right.array) > 0;
   }

   bool operator>=(const basic_string & right) {
      return strcmp(array, right.array) >= 0;
   }

   bool operator==(const basic_string & right) const {
      return strcmp(array, right.array) == 0;
   }
    
   bool operator!=(const basic_string & right) const {
      return strcmp(array, right.array) != 0;
   }
      
   bool operator<(const basic_string & right) const {
      return strcmp(array, right.array) < 0;
   }
    
   bool operator<=(const basic_string & right) const {
      return strcmp(array, right.array) <= 0;
   }
      
   bool operator>(const basic_string & right) const {
      return strcmp(array, right.array) > 0;
   }
      
   bool operator>=(const basic_string & right) const {
      return strcmp(array, right.array) >= 0;
   }

};


typedef basic_string< char > string;

template< class Char >
unsigned int basic_string< Char >::npos = 0xFFFFFFFF;

inline
string operator+(const char * left, const string & right) {
   return basic_string< char >(left) + right; 
}

inline
bool operator==(const char * left, const string & right) {
   return basic_string< char >(left) == right;
}

}

#endif /* _MATT_STL_H */
