#ifndef STRING_
#define STRING_

#include <string.h>

#include "new"
#include "vector"
#include "iostream"
#include "helpers/iterator.h"

namespace std {

	/**
	 * Incomplete and naiv implementation of std::basic_string
	 * Warning: Does only work for types that can be duplicated by plain
	 * memcpy!
	 */
	template<typename T>
	class basic_string
	{
	public:
		typedef size_t size_type;
		typedef private_stuff::iterator_base<T> iterator;
		typedef private_stuff::iterator_base<const T> const_iterator;
	
		basic_string()
			: str(NULL), len(0)
		{
		}
		
		basic_string(const T* other)
			: str(NULL), len(0)
		{
			*this = other;
		}
		
		basic_string(const basic_string& other)
		{
			if(other.len == 0) {
				len = 0;
				str = NULL;
			} else {
				len = other.len;
				str = new T[len+1];
				memcpy(str, other.c_str(), (len + 1) * sizeof(T));
			}
		}
		
		basic_string(const basic_string& other, size_type p1, size_type p2)
		{
			assert(p1 < other.len && p2 <= other.len);
			assert(p2 >= p1);
			len = p2 - p1;
			str = new T[len+1];
			memcpy(str, other.c_str() + p1, len * sizeof(T));
			str[len] = 0;
		}
		
		~basic_string()
		{
			delete[] str;
		}
		
		basic_string substr(size_type pos, size_type count) const
		{
			return basic_string(*this, pos, pos + count);
		}

		basic_string& operator= (const basic_string& other)
		{
			*this = other.c_str();
			return *this;
		}
		
		basic_string& operator= (const T* other)
		{
			if(other == NULL) {
				str = NULL;
				len = 0;
				return *this;
			}
			
			size_t new_len = 0;
			for(const T* p = other; *p != static_cast<T>(0); ++p)
				++new_len;
				
			T* new_str = new T[new_len + 1];
			memcpy(new_str, other, new_len * sizeof(T));
			new_str[new_len] = 0;
			
			delete[] str;
			str = new_str;
			len = new_len;
			
			return *this;
		}
		
		basic_string& operator+= (const basic_string& other)
		{
			size_t new_len = size() + other.size();
			
			T* new_str = new T[new_len + 1];
			memcpy(new_str, str, size() * sizeof(T));
			memcpy(new_str + size(), other.c_str(), other.size() * sizeof(T));
			new_str[new_len] = 0;
			
			delete[] str;
			str = new_str;
			len = new_len;
			
			return *this;
		}
		
		basic_string operator+ (const basic_string& other) const
		{
			basic_string result(*this);
			result += other;
			
			return result;
		}
		
		const T* c_str() const
		{
			return str;
		}

		char& operator[] (size_t idx)
		{
			assert(idx < len);
			return str[idx];
		}

		char operator[] (size_t idx) const
		{
			assert(idx < len);
			return str[idx];
		}
		
		bool operator==(const basic_string& other) const
		{
			const_iterator i, i2;
			for(i = begin(), i2 = other.begin(); i != end() && i2 != other.end(); ++i, ++i2) {
				if(*i != *i2)
					return false;
			}
			
			return i == end() && i2 == other.end();
		}
		
		bool operator<(const basic_string& other) const
		{
			const_iterator i, i2;
			for(i = begin(), i2 = other.begin(); i != end() && i2 != other.end(); ++i, ++i2) {
				if(*i == *i2)
					continue;

				return *i < *i2;				
			}
			
			if(i != end())
				return false;
				
			return i2 != other.end();
		}
		
		bool operator>(const basic_string& other) const
		{
			const_iterator i, i2;
			for(i = begin(), i2 = other.begin(); i != end() && i2 != other.end(); ++i, ++i2) {
				if(*i == *i2)
					continue;

				return *i > *i2;				
			}
			
			if(i2 != other.end())
				return false;
				
			return i != end();
		}		
		
		bool operator !=(const basic_string& other) const
		{
			return ! (*this == other);
		}
		
		iterator begin()
		{
			return iterator(str);
		}
		
		const_iterator begin() const
		{
			return const_iterator(str);
		}
		
		iterator end()
		{
			return iterator(str + len);
		}
		
		const_iterator end() const
		{
			return const_iterator(str + len);
		}
		
		size_type size() const
		{
			return len;
		}

		size_type length() const
		{
			return len;
		}
		
		bool empty() const
		{
			return len == 0;
		}
				
	private:
		T* str;
		size_t len;
	};
	
	typedef basic_string<char> string;
	
	static inline ostream& operator<<(ostream& out, const string& str)
	{
		return (out << str.c_str());
	}	
}

#endif /*STRING_*/