#pragma once 

#ifdef  WIN32
#ifdef IVY_EXPORTS
class _declspec(dllexport) string;
#else
#pragma comment(lib,"Ivy.LIB" )
class _declspec(dllimport) string;
#endif
#endif

class string {
public:
	string(size_t len = 0)
		{ ptr = allocBuffer( len ); };
	string ( const string& s )
		{ ptr = 0; copy( s.ptr, s.size );  }
	string( const char * s, int len = -1 )
		{
		ptr = 0;
		if ( len < 0 )
			len = strlen(s) ;
		copy( s, len ); 
		}
	
	~string()
		{ delete ptr; }
	size_t length()
		{ return size; }
	bool empty() const
		{ return size==0; }
	void copy( const char * s, int len  )
		{
		char *newptr = allocBuffer( len );
		strncpy( newptr, s, len ); 
		if ( ptr ) delete [] ptr;
		ptr = newptr;
		}
	void erase(int start=0, int len = -1)
		{
		char *newptr;
		size_t real_len;
		real_len = len < 0 ? size - start : len;
		if ( real_len > size ) real_len = size;
		newptr = allocBuffer( size - real_len );
		strncpy( newptr, ptr , start );
		strncpy( &newptr[start], &ptr[start+real_len], size - start  );
		delete ptr;
		ptr = newptr;
		}
	void append( const char *s , int len = -1 )
		{
		insert ( size, s , len );
		}
	void insert(int index, const char * s, int len = -1)
		{
		char *newptr;
		if ( len < 0 ) len = strlen(s) ;
		newptr = allocBuffer( size + len );
		strncpy( newptr , ptr, index );
		strncpy( newptr+index , s, len ) ;
		strncpy( newptr+index+len , &ptr[index], len ) ;
		delete ptr;
		ptr = newptr;
		}
	string substr( int start, int len  = -1 )
		{ return string ( &ptr[start], len ); }
	int find_first_of( const char* strCharSet )
		{ char *fnd = strpbrk( ptr, strCharSet ); if ( fnd ) return fnd - ptr; else return -1; }
	int rfind( char c )
		{ char *fnd = strrchr( ptr, c); if ( fnd ) return fnd - ptr; else return -1; }
//	friend string operator + (const string& left, const char* right);
//	friend string operator + (const char* left, const string& right);
	friend string operator + (const string& left, const string& right)
		{
		string str( left.size + right.size ); 
		str.append( left.ptr, left.size);
		str.append( right.ptr, right.size);
		return str;
		}
	operator +=(string s)
		{
		append( s.ptr, s.size );
		}
	operator +=(char c)
		{ append( &c, 1);}
	string operator +(string s) const
		{ string str ( ptr, size ); str.append( s.ptr, s.size ); return str; }
	string operator +(const char c) const
		{ string str ( ptr, size ); str.append( &c, 1); return str; }
	string& operator=(const string& s)
		{ copy(s.ptr,s.size); return *this; }
	string& operator=(const char* s)
		{ copy(s,strlen(s)); return *this; }
	// Nondestructive typecast operator
	operator const char*() const
		{ return ptr; }
	const char *c_str() const // remove this ugly thing
		{ return ptr; }
private:
	char *ptr;
	size_t size;
	// always allocate one extra character for '\0' termination
	char *allocBuffer(int len)
	{
		char *newptr;
		size = len;
		newptr = new char[len+1] ;
		newptr[len] = '\0'; 
		return newptr;
	}

};




template <class T> class list {

protected:
	struct _Node;
	friend struct _Node;
	typedef struct _Node Node;
	typedef Node* NodePtr;
	struct _Node {
		NodePtr next, prev;
		T value;
		};

public:

	friend class iterator;
	class iterator  {
	public:
		iterator()
			{ptr = 0;}
		iterator(NodePtr p)
			{ptr = p;}
		T& operator*() const
			{return ptr->value; }
		T* operator->() const
			{return &(ptr->value); }
		iterator& operator++()
			{ptr = ptr->next;
			return (*this); }
		iterator operator++(int)
			{iterator tmp = *this;
			++*this;
			return (tmp); }
		iterator& operator--()
			{ptr = ptr.prev;);
			return (*this); }
		iterator operator--(int)
			{iterator tmp = *this;
			--*this;
			return (tmp); }
		bool operator==(const iterator& p) const
			{return (ptr == p.ptr); }
		bool operator!=(const iterator& p) const
			{return (ptr != p.ptr);  }
		NodePtr next() const 
			{return  ptr->next; };
		NodePtr prev() const 
			{return ptr->prev ; };
		NodePtr node() const
			{return (ptr); }
	protected:
		NodePtr ptr;
	};

	list()
		{ head = 0; }
	bool empty()  
		{ return head == 0 ; }
	T& front()
		{return head->value; }
	iterator erase(iterator n)
		{
		NodePtr p = n.prev();
		NodePtr s = (n++).node();
		delete p->next;
		p->next = s;
		s->prev = p;
		return n;
		}
	void pop_front()
		{
		NodePtr newhead = head->next;
		newhead->prev = head->prev;
		head->prev->next = newhead;
		delete head;
		head = (head == newhead) ? 0 : newhead;
		}
	iterator erase(iterator first, iterator last)
		{
		while (first != last)
			erase(first++);
		return (first);
		}
	void clear()
		{erase(begin(), end()); }
	void push_back( T value )
		{
		NodePtr p = new Node;
		p->value = value;
		if ( head )
		{
		p->next = head;
		p->prev = head->prev;
		head->prev->next = p;
		head->prev = p;
		}
		else {
		 head = p;
		 p->next = p->prev = p;
		}
		}
	void remove( const T& data )
		{
		iterator last = end();
		for (iterator iter = begin(); iter != last; )
			if (*iter == data)
				erase(iter++);
			else
				++iter; 
		}
	iterator begin()
		{return (iterator(head)); }
	iterator end()
	{
		if (head ) 
		return (iterator(head->prev));
		else return (iterator(head));
	}
	protected:
		NodePtr head;
	
};

template <class T> class vector {
public:

	vector ( )
		{ data = 0; len = 0; }
	size_t size()
		{ return len; }
	void reserve( size_t index )
		{
		if ( index >= len )
		{
		size_t i;
		T* newdata = new T[index+1];
		for ( i = 0; i < len ; i ++ )
			newdata[i] = data[i];
		for ( i = len; i < index+1 ; i ++ )
			newdata[i] = 0;
		if ( data ) delete [] data;
		data = newdata;
		len = index+1;
		}
		}
	// Accesses indexed component of vector
	T & operator [](size_t index )
		{
		// reserve( index ); // TODO or NOT check range
		return data[index] ;
		}
	T &	operator [](size_t index ) const
		{
		return data[index] ;
		}
	void push_back( const T& value )
		{
		T* newdata = new T[len+1];
		for ( unsigned int i = 0; i < len ; i ++ )
			newdata[i] = data[i];
		newdata[len++] = value;
		if ( data ) delete [] data;
		data = newdata;
		}
	void erase( int i )
		{
		data[i] = 0;
		}
	void clear()
		{
		delete [] data;
		data = 0;
		len = 0;
		}

private:
	T* data;
	size_t len;
};