/* libobby - Network text editing library
 * Copyright (C) 2005, 2006 0x539 dev group
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include "text.hpp"

namespace
{
	const obby::text::size_type CHUNK_INIT =
		~static_cast<obby::text::size_type>(0);

	inline obby::text::size_type CHUNK_SIZE(obby::text::size_type size)
	{
		return size == obby::text::npos ? CHUNK_INIT : size;
	}

	// find_chunk implementation to avoid code duplication for
	// iterator and const_iterator versions
	template<typename List, typename Iter>
	Iter find_chunk(List list, obby::text::size_type& pos)
	{
		for(Iter it = list.begin(); it != list.end(); ++ it)
		{
			if( (*it)->get_length() > pos)
				return it;
			else
				pos -= (*it)->get_length();
		}

		if(pos == 0) return list.end();

		throw std::logic_error(
			"obby::text::find_chunk:\n"
			"Requested position exceeds text's size"
		);
	}
}

obby::text::chunk::chunk(const chunk& other):
	m_text(other.m_text), m_author(other.m_author)
{
}

obby::text::chunk::chunk(const string_type& string,
                         const user* author):
	m_text(string),
	m_author(author)
{
}

obby::text::chunk::chunk(const net6::packet& pack,
                         unsigned int& index,
                         const user_table& table):
	m_text(pack.get_param(index + 0).as<std::string>() ),
	m_author(
		pack.get_param(index + 1).as<const user*>(
			::serialise::hex_context_from<const user*>(table)
		)
	)
{
	index += 2;
}

obby::text::chunk::chunk(const serialise::object& obj,
                         const user_table& table):
	m_text(obj.get_required_attribute("content").as<std::string>() ),
	m_author(
		obj.get_required_attribute("author").as<const user*>(
			::serialise::default_context_from<const user*>(table)
		)
	)
{
}

void obby::text::chunk::serialise(serialise::object& obj) const
{
	obj.add_attribute("content").set_value(m_text);
	obj.add_attribute("author").set_value(m_author);
}

void obby::text::chunk::append_packet(net6::packet& pack) const
{
	pack << m_text << m_author;
}

void obby::text::chunk::prepend(const string_type& text)
{
	m_text.insert(0, text);
}

void obby::text::chunk::append(const string_type& text)
{
	m_text.append(text);
}

void obby::text::chunk::insert(size_type pos, const string_type& text)
{
	m_text.insert(pos, text);
}

void obby::text::chunk::erase(size_type pos, size_type len)
{
	m_text.erase(pos, len);
}

const obby::text::string_type& obby::text::chunk::get_text() const
{
	return m_text;
}

const obby::user* obby::text::chunk::get_author() const
{
	return m_author;
}

obby::text::size_type obby::text::chunk::get_length() const
{
	return m_text.length();
}

obby::text::text(size_type initial_chunk_size):
	m_max_chunk(CHUNK_SIZE(initial_chunk_size) )
{
}

obby::text::text(const text& other):
	m_max_chunk(other.m_max_chunk)
{
	for(list_type::const_iterator iter = other.m_chunks.begin();
	    iter != other.m_chunks.end();
	    ++ iter)
	{
		m_chunks.push_back(new chunk(**iter) );
	}
}

obby::text::text(const string_type& string,
                 const user* author,
                 size_type initial_chunk_size):
	m_max_chunk(CHUNK_SIZE(initial_chunk_size) )
{
	for(size_type n = 0; n < string.length(); ++ n)
	{
		size_type len = std::min(string.length() - n, m_max_chunk);
		m_chunks.push_back(new chunk(string.substr(n, len), author) );
	}
}

obby::text::text(const net6::packet& pack,
                 unsigned int& index,
                 const user_table& table):
	m_max_chunk(CHUNK_INIT)
{
	unsigned int count = pack.get_param(index ++).as<unsigned int>();
	for(unsigned int i = 0; i < count; ++ i)
		m_chunks.push_back(new chunk(pack, index, table) );
}

obby::text::text(const serialise::object& obj,
                 const user_table& table):
	m_max_chunk(CHUNK_INIT)
{
	for(serialise::object::child_iterator iter = obj.children_begin();
	    iter != obj.children_end();
	    ++ iter)
	{
		if(iter->get_name() == "chunk")
		{
			m_chunks.push_back(new chunk(*iter, table) );
		}
		else
		{
			// TODO: unexpected_child_error
			format_string str(_("Unexpected child node: '%0%'") );
			str << iter->get_name();
			throw serialise::error(str.str(), iter->get_line() );
		}
	}
}

obby::text::~text()
{
	clear();
}

obby::text& obby::text::operator=(const text& other)
{
	if(&other == this) return *this;

	clear();
	m_max_chunk = other.m_max_chunk;

	for(list_type::const_iterator iter = other.m_chunks.begin();
	    iter != other.m_chunks.end();
	    ++ iter)
	{
		m_chunks.push_back(new chunk(**iter) );
	}

	return *this;
}

void obby::text::serialise(serialise::object& obj) const
{
	for(list_type::const_iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it)
	{
		serialise::object& part = obj.add_child();
		part.set_name("chunk");
		(*it)->serialise(part);
	}
}

void obby::text::append_packet(net6::packet& pack) const
{
	pack << m_chunks.size();
	for(list_type::const_iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it)
	{
		(*it)->append_packet(pack);
	}
}

void obby::text::clear()
{
	for(list_type::iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it)
	{
		delete *it;
	}

	m_chunks.clear();
}

obby::text obby::text::substr(size_type pos, size_type len) const
{
	text new_text;
	list_type::const_iterator iter = find_chunk(pos);

	chunk* prev_chunk = NULL;
	while( (len == npos || len > 0) && (iter != m_chunks.end()) )
	{
		chunk* cur_chunk = *iter;
		size_type count = cur_chunk->get_length() - pos;

		if(len != npos)
		{
			count = std::min(count, len);
			len -= count;
		}

		if(prev_chunk != NULL &&
		   prev_chunk->get_author() == cur_chunk->get_author() &&
		   prev_chunk->get_length() + cur_chunk->get_length() <=
		   m_max_chunk)
		{
			prev_chunk->append(
				cur_chunk->get_text().substr(pos, count)
			);
		}
		else
		{
			prev_chunk = new chunk(
				cur_chunk->get_text().substr(pos, count),
				cur_chunk->get_author()
			);

			new_text.m_chunks.push_back(prev_chunk);
		}

		++ iter; pos = 0;
	}

	if(len > 0 && len != npos)
	{
		throw std::logic_error(
			"obby::text::substr:\n"
			"len is out or range"
		);
	}

	return new_text;
}

void obby::text::insert(size_type pos,
                        const string_type& str,
                        const user* author)
{
	list_type::iterator ins_pos = find_chunk(pos);
	insert_chunk(ins_pos, pos, str, author);
}

void obby::text::insert(size_type pos,
                        const text& str)
{
	list_type::iterator ins_pos = find_chunk(pos);
	for(list_type::const_iterator it = str.m_chunks.begin();
	    it != str.m_chunks.end();
	    ++ it)
	{
		ins_pos = insert_chunk(
			ins_pos,
			pos,
			(*it)->get_text(),
			(*it)->get_author()
		);
	}
}

void obby::text::erase(size_type pos, size_type len)
{
	list_type::iterator ers_pos = find_chunk(pos);
	list_type::iterator first_chunk = ers_pos;
	size_type first_pos = pos;

	// Remember first chunk position that will not be removed.
	// After having erased a chunk in the middle, something may have
	// been mergen with this first chunk that should have been deleted.
	// We watch it and remove merged stuff if the chunk grew.
	if(first_pos == 0 && first_chunk != m_chunks.begin() )
	{
		-- first_chunk;
		first_pos = (*first_chunk)->get_length();
	}

	while( (len == npos || len > 0) && ers_pos != m_chunks.end() )
	{
		size_type count = (*ers_pos)->get_length() - pos;
		if(len != npos)
		{
			count = std::min(count, len);
			len -= count;
		}

		ers_pos = erase_chunk(ers_pos, pos, count);

		if(first_pos > 0 && (*first_chunk)->get_length() > first_pos)
		{
			ers_pos = first_chunk;
			pos = first_pos;
		}
		else
		{
			pos = 0;
		}
	}

	if(len != npos && len > 0)
	{
		throw std::logic_error(
			"obby::text::erase:\n"
			"len is out of range"
		);
	}
}

void obby::text::append(const string_type& str,
                        const user* author)
{
	chunk* last_chunk = NULL;
	if(!m_chunks.empty() ) last_chunk = *m_chunks.rbegin();
	size_type pos = 0;

	// Merge beginning of str with last chunk if possible
	if(last_chunk != NULL &&
	   last_chunk->get_author() == author &&
	   last_chunk->get_length() < m_max_chunk)
	{
		pos = std::min(
			m_max_chunk - last_chunk->get_length(),
			str.length()
		);

		last_chunk->append(str.substr(0, pos) );
	}

	// Append rest of string
	for(; pos < str.length(); pos += m_max_chunk)
	{
		size_type count = std::min(str.length() - pos, m_max_chunk);
		m_chunks.push_back(new chunk(str.substr(pos, count), author) );
	}
}

void obby::text::append(const text& str)
{
	// Simply append all chunks of str
	for(list_type::const_iterator it = str.m_chunks.begin();
	    it != str.m_chunks.end();
	    ++ it)
	{
		append( (*it)->get_text(), (*it)->get_author() );
	}
}

void obby::text::prepend(const string_type& str,
                         const user* author)
{
	chunk* first_chunk = NULL;
	if(!m_chunks.empty() ) first_chunk = *m_chunks.begin();

	size_type len = str.length();

	// Prepend end of str to first chunk if possible
	if(first_chunk != NULL &&
	   first_chunk->get_author() == author &&
	   first_chunk->get_length() < m_max_chunk)
	{
		size_type count = std::min(
			m_max_chunk - first_chunk->get_length(),
			len
		);

		len -= count;
		first_chunk->prepend(str.substr(len, count) );
	}

	// Insert chunks before for the rest of str
	while(len > 0)
	{
		size_type count = std::min(
			len,
			m_max_chunk
		);

		len -= count;
		m_chunks.push_front(new chunk(str.substr(len, count), author));
	}
}

void obby::text::prepend(const text& str)
{
	for(list_type::const_reverse_iterator it = str.m_chunks.rbegin();
	    it != str.m_chunks.rend();
	    ++ it)
	{
		prepend( (*it)->get_text(), (*it)->get_author() );
	}
}

obby::text::size_type obby::text::length() const
{
	// TODO: Cache this value?
	size_type len = 0;
	for(list_type::const_iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it)
	{
		len += (*it)->get_length();
	}

	return len;
}

bool obby::text::operator==(const text& other) const
{
	return compare(other) == EQUAL_OWNERMATCH;
}

bool obby::text::operator!=(const text& other) const
{
	return compare(other) != EQUAL_OWNERMATCH;
}

bool obby::text::operator<(const text& other) const
{
	return compare(other) == LESS;
}

bool obby::text::operator>(const text& other) const
{
	return compare(other) == GREATER;
}

bool obby::text::operator<=(const text& other) const
{
	return compare(other) != GREATER;
}

bool obby::text::operator>=(const text& other) const
{
	return compare(other) != LESS;
}

bool obby::text::operator==(const string_type& other) const
{
	return compare(other) == EQUAL;
}

bool obby::text::operator!=(const string_type& other) const
{
	return compare(other) != EQUAL;
}

bool obby::text::operator<(const string_type& other) const
{
	return compare(other) == LESS;
}

bool obby::text::operator>(const string_type& other) const
{
	return compare(other) == GREATER;
}

bool obby::text::operator<=(const string_type& other) const
{
	return compare(other) != GREATER;
}

bool obby::text::operator>=(const string_type& other) const
{
	return compare(other) != LESS;
}

bool obby::text::empty() const
{
	return m_chunks.empty();
}

obby::text::chunk_iterator obby::text::chunk_begin() const
{
	return chunk_iterator(m_chunks.begin() );
}

obby::text::chunk_iterator obby::text::chunk_end() const
{
	return chunk_iterator(m_chunks.end() );
}

void obby::text::set_max_chunk_size(size_type max_chunk)
{
	m_max_chunk = max_chunk;
	if(m_chunks.empty() ) return;

	// Merge and/or split current chunks
	list_type::iterator next = m_chunks.begin(); ++ next;
	for(list_type::iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it, ++ next)
	{
		chunk* cur_chunk = *it;

		chunk* next_chunk = NULL;
		if(next != m_chunks.end() ) next_chunk = *next;

		// Split current chunk if necessary
		if(cur_chunk->get_length() > m_max_chunk)
		{
			size_type pos = m_max_chunk;
			while(cur_chunk->get_length() - pos > 0)
			{
				// Merge with next if possible
				if(next_chunk != NULL &&
				   next_chunk->get_author() ==
				   cur_chunk->get_author() &&
				   cur_chunk->get_length() - pos +
				   next_chunk->get_length() <= m_max_chunk)
				{
					// Note that this could also be done
					// in the merging process below but
					// then we would split the chunk up
					// just to merge it then...
					next_chunk->prepend(
						cur_chunk->get_text().substr(
							pos
						)
					);

					pos += (cur_chunk->get_length() - pos);
				}
				// Split otherwise
				else
				{
					size_type len = std::min(
						cur_chunk->get_length() - pos,
						m_max_chunk
					);

					const std::string& text =
						cur_chunk->get_text();

					it = m_chunks.insert(
						next,
						new chunk(
							text.substr(
								pos,
								len
							),
							cur_chunk->get_author()
						)
					);

					pos += len;
				}

			}

			// Remove splitted/merged stuff from current one
			cur_chunk->erase(m_max_chunk);
			cur_chunk = *it;
		}
		// Merge chunk with next
		else if(next_chunk != NULL &&
		        cur_chunk->get_author() == next_chunk->get_author() &&
		        cur_chunk->get_length() + next_chunk->get_length() <=
		        m_max_chunk)
		{
			cur_chunk->append(next_chunk->get_text() );

			delete next_chunk;
			next = m_chunks.erase(next);
		}
	}
}

obby::text::operator string_type() const
{
	string_type str;
	str.reserve(length() );

	for(list_type::const_iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it)
	{
		str.append( (*it)->get_text() );
	}

	return str;
}

obby::text::list_type::iterator
obby::text::find_chunk(size_type& pos)
{
	return ::find_chunk<list_type&, list_type::iterator>(
		m_chunks,
		pos
	);
}

obby::text::list_type::const_iterator
obby::text::find_chunk(size_type& pos) const
{
	return ::find_chunk<const list_type&, list_type::const_iterator>(
		m_chunks,
		pos
	);
}

obby::text::list_type::iterator
obby::text::insert_chunk(list_type::iterator chunk_it,
                         size_type& chunk_pos,
                         const string_type& str,
                         const user* author)
{
	chunk* cur_chunk = NULL;
	if(chunk_it != m_chunks.end() ) cur_chunk = *chunk_it;

	list_type::iterator ins_pos = chunk_it;

	// Get previous chunk
	chunk* prev_chunk = NULL;
	list_type::iterator prev_pos = ins_pos;
	if(prev_pos != m_chunks.begin() )
	{
		-- prev_pos;
		prev_chunk = *prev_pos;
	}

	// Merge with previous
	if(prev_chunk != NULL &&
	   chunk_pos == 0 &&
	   author == prev_chunk->get_author() &&
	   str.length() + prev_chunk->get_length() <= m_max_chunk)
	{
		prev_chunk->append(str);
		return chunk_it;
	}
	else if(cur_chunk == NULL)
	{
		// Insertion at end (no current chunk) and cannot merge with
		// previous: Need to create a new one, do nothing here - this
		// is done below
	}
	// Merge with current
	else if(author == cur_chunk->get_author() &&
	        str.length() + cur_chunk->get_length() <= m_max_chunk)
	{
		cur_chunk->insert(chunk_pos, str);
		chunk_pos += str.length();
		return chunk_it;
	}
	// Insert new chunk after current chunk if str is inserted at
	// end of current chunk
	else if(chunk_pos == cur_chunk->get_length() )
	{
		++ ins_pos;
	}
	// Insert new chunk before current chunk if str is inserted at
	// the beginning of current chunk
	else if(chunk_pos > 0)
	{
		// Split up otherwise
		chunk* new_chunk = new chunk(
			cur_chunk->get_text().substr(chunk_pos),
			cur_chunk->get_author()
		);

		cur_chunk->erase(chunk_pos);
		chunk_pos = 0;

		++ ins_pos;
		ins_pos = m_chunks.insert(
			ins_pos,
			new_chunk
		);

		// Try to merge with both chunks - they may be smaller
		// and thus fit into max chunk size
		if(cur_chunk->get_author() == author)
		{
			if(cur_chunk->get_length() + str.length() <=
			   m_max_chunk)
			{
				cur_chunk->append(str);
				chunk_pos = cur_chunk->get_length();
				-- ins_pos;
				return ins_pos;
			}
			else if(new_chunk->get_length() +
			        str.length() <= m_max_chunk)
			{
				new_chunk->prepend(str);
				chunk_pos = str.length();
				return ins_pos;
			}
		}

		// If not insert another new chunk between
		// the chunks split up - ins_pos points already
		// to the correct position
	}

	// Insert one new chunk if str fits into
	if(str.length() <= m_max_chunk)
	{
		chunk_pos = 0;
		m_chunks.insert(ins_pos, new chunk(str, author) );
		return ins_pos;
	}
	else
	{
		// Make multiple chunks otherwise
		// TODO: Fill up previous chunk if author matches and ins_pos
		// is != m_chunks.begin()
		cur_chunk = ( (ins_pos == m_chunks.end()) ? NULL : *ins_pos);
		for(size_type n = 0; n < str.length(); n += m_max_chunk)
		{
			size_type len = std::min(str.length() - n, m_max_chunk);

			// Merge with next
			if(cur_chunk &&
			   cur_chunk->get_author() == author &&
			   len + cur_chunk->get_length() <= m_max_chunk)
			{
				// Must be last chunk to insert since all
				// others are m_max_chunk in size and thus
				// may not be merged
				cur_chunk->prepend(str.substr(n, len) );
				chunk_pos = len;
				return ins_pos;
			}
			else
			{
				/*result =*/ m_chunks.insert(
					ins_pos,
					new chunk(str.substr(n, len), author)
				);
			}
		}

		chunk_pos = 0;
		return ins_pos;
	}
}

obby::text::list_type::iterator
obby::text::erase_chunk(list_type::iterator chunk_it,
                        size_type pos,
                        size_type len)
{
	chunk* prev_chunk = NULL;
	chunk* next_chunk = NULL;

	list_type::iterator prev_it = chunk_it;
	if(prev_it != m_chunks.begin() ) { -- prev_it; prev_chunk = *prev_it; }

	list_type::iterator next_it = chunk_it;
	++ next_it;
	if(next_it != m_chunks.end() ) { next_chunk = *next_it; }

	chunk* cur_chunk = *chunk_it;
	//if(len == npos) len = cur_chunk->get_length() - pos;

	if(pos + len > cur_chunk->get_length() )
	{
		throw std::logic_error(
			"obby::text::erase_chunk:\n"
			"Chunk len exceeded"
		);
	}

	// Complete erasure
	if(len == cur_chunk->get_length() )
	{
		delete cur_chunk;
		m_chunks.erase(chunk_it);

		// Merge surrounding chunks if possible
		if(next_chunk != NULL && prev_chunk != NULL &&
		   next_chunk->get_author() == prev_chunk->get_author() &&
		   next_chunk->get_length() + prev_chunk->get_length() <
		   m_max_chunk)
		{
			prev_chunk->append(next_chunk->get_text() );

			delete next_chunk;
			next_it = m_chunks.erase(next_it);
		}

		return next_it;
	}

	// Merge with previous
	if(prev_chunk != NULL &&
	   prev_chunk->get_author() == cur_chunk->get_author() &&
	   cur_chunk->get_length() - len + prev_chunk->get_length() <
	   m_max_chunk)
	{
		if(pos > 0)
		{
			prev_chunk->append(
				cur_chunk->get_text().substr(0, pos)
			);
		}

		if(pos + len < cur_chunk->get_length() )
		{
			prev_chunk->append(
				cur_chunk->get_text().substr(pos + len)
			);
		}

		delete cur_chunk;
		m_chunks.erase(chunk_it);

		// Merge result with next if possible
		if(next_chunk != NULL &&
		   prev_chunk->get_author() == next_chunk->get_author() &&
		   prev_chunk->get_length() + next_chunk->get_length() <=
		   m_max_chunk)
		{
			prev_chunk->append(next_chunk->get_text() );

			delete next_chunk;
			next_it = m_chunks.erase(next_it);
		}

		return next_it;
	}

	// Merge with next
	if(next_chunk != NULL &&
	   next_chunk->get_author() == cur_chunk->get_author() &&
	   cur_chunk->get_length() - len + next_chunk->get_length() <
	   m_max_chunk)
	{
		if(pos + len < cur_chunk->get_length() )
		{
			next_chunk->prepend(
				cur_chunk->get_text().substr(pos)
			);
		}

		if(pos > 0)
		{
			next_chunk->prepend(
				cur_chunk->get_text().substr(0, pos)
			);
		}

		delete cur_chunk;
		m_chunks.erase(chunk_it);

		// No need to try to merge with previous since the check
		// above would already have done it.

		++ next_it;
		return next_it;
	}

	// No merging possible...
	cur_chunk->erase(pos, len);
	return next_it;
}

obby::text::compare_result obby::text::compare(const text& other) const
{
	list_type::const_iterator it1 = m_chunks.begin();
	list_type::const_iterator it2 = other.m_chunks.begin();

	size_type pos1 = 0, pos2 = 0;
	bool author_match = true;

	while(it1 != m_chunks.end() && it2 != other.m_chunks.end() )
	{
		// Authors do not match: Remember this for later use. If
		// the strings differ, LESS or GREATER is returned; author
		// match does only play a role when the text content is equal
		if( (*it1)->get_author() != (*it2)->get_author() )
			author_match = false;

		size_type len = std::min(
			(*it1)->get_length() - pos1,
			(*it2)->get_length() - pos2
		);

		int res = (*it1)->get_text().compare(
			pos1,
			len,
			(*it2)->get_text(),
			pos2,
			len
		);

		if(res != 0) return res < 0 ? LESS : GREATER;

		pos1 += len;
		pos2 += len;

		if(pos1 == (*it1)->get_length() )
			{ ++ it1; pos1 = 0; }
		if(pos2 == (*it2)->get_length() )
			{ ++ it2; pos2 = 0; }
	}

	// *this has more length than other
	if(it1 != m_chunks.end() )
		return GREATER;
	// other has more length
	else if(it2 != other.m_chunks.end() )
		return LESS;
	// both text's content are equal
	else
		return author_match ? EQUAL_OWNERMATCH : EQUAL;
}

obby::text::compare_result obby::text::compare(const string_type& text) const
{
	size_type pos = 0;
	for(list_type::const_iterator it = m_chunks.begin();
	    it != m_chunks.end();
	    ++ it)
	{
		size_type len = (*it)->get_length();
		int res = text.compare(pos, len, (*it)->get_text());
		if(res != 0) return res < 0 ? LESS : GREATER;
		pos += len;
	}

	return EQUAL;
}