/** @file strings.h
 *
 *	Declaration of string store interface.
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _STRINGS_H
#define	_STRINGS_H

#include <limits>
#include <set>
#include <vector>

//
#include "exceptions.h"
// Memory pool needed.
#include "pool.h"

namespace ace {

// Forward declaration needed.
template<class _IndType>
class StringStoreLessComparator;

// Forward declaration needed.
template<class _IndType>
class StringStoreEqualComparator;

/** Class purpose is to store unique C-strings and let them be accessed (later)
 *	by unique numeral indices of given type (which shall be the smallest one
 *	unsigned type capable of store as much values as the number of C-strings
 *	expected).
 *	The equality of strings is based just on their bitwise values (so "String"
 *	and "string" will be considered as two different strings).
 *	Class provides O(log N) when inserting new C-string and O(1) time when
 *	retrieving stored string (by accessing it by its index).
 *	Note that this concept of string storage has one advantage - when comparing
 *	two strings stored within same storage to determine if they are equal, one
 *	has only to compare the indices themself, not the strings they "point" to.
 *	@param _IndType Type for string indices, can be any of unsigned types.
 *		When new string is inserted, overflow check is performed.
 */
template<class _IndType>
class StringStore {
public:
	/** Typedef for container of pointers to stored strings which acts as
	 *	conversion table: index -> pointer (to C-string).
	 */
	typedef std::vector<const char *> table_t;

private:
	/** Typedef for set which is used as index above the conversion table.
	 */
	typedef typename std::set<_IndType, StringStoreLessComparator<_IndType> > _index_t;
	
	/** Memory pool used to store the C-strings.
	 */
	RandomSizedMemoryPool<char> _memory_pool;

	/** Container with pointers to string instances (conversion table).
	 */
	table_t _strings_table;

	/** Container acts as index above strings pointers container.
	 */
	_index_t _strings_index;

	/** Comparator needed for determination of two C-strings (un)equality.
	 */
	StringStoreEqualComparator<_IndType> _str_equal_comp;

public:
	/** Constructs new StringStore.
	 *	@param max_string_length Maximum storable string length.
	 */
	StringStore(size_t max_string_length);
	/** Drops all stored strings.
	 */
	void clear(void);
	/** @return True, if all available indices has been spent (overflow almost guaranteed).
	 */
	inline bool is_full(void) const { return _strings_table.size() == std::numeric_limits<_IndType>::max(); }
	/** Retrieves pointer to string instance tied to given index.
	 *	Note: No range checks are performed!
	 *	@param index Index of C-string to rietrieve.
	 *	@return Pointer to stored C-string instance.
	 */
	inline const char * get(_IndType index) const { return _strings_table[index]; }
	/** Stores the string and returns string index within store.
	 *	@param str Pointer to C-string to store within.
	 *	@return Index of stored copy.
	 *	@throw string_index_overflow When insertion of new string would cause
	 *		overflow of _IndType.
	 */
	_IndType store(const char *str);
	/** @return Size of the store (number of unique strings within).
	 */
	inline size_t size(void) const { return _strings_table.size(); }
};


/** Functor designed for less than comparison of C-strings stored within StringStore.
 *	@param _StIndex StringStore index.
 *	@param _IndType Type of numerical indices of strings within given StringStore.
 */
template <class _IndType>
class StringStoreLessComparator: public std::binary_function<_IndType, _IndType, bool> {
	/** Reference to table to which indices passed for comparation relates to.
	 */
	const typename StringStore<_IndType>::table_t& _table;
public:
	/** @param table Reference to table to which indices passed for comparation relates to.
	 */
	StringStoreLessComparator(const typename StringStore<_IndType>::table_t& table): _table(table) {}
	/** @return True, if left-hand argument is lesser than right hand argument.
	 */
	inline bool operator()(_IndType lhs, _IndType rhs) const {
		return strcmp(_table[lhs], _table[rhs]) == -1;
	}
};

/** Functor designed for equal to comparison of C-strings stored within StringStore.
 *	@param _StIndex StringStore index.
 *	@param _IndType Type of numerical indices of strings within given StringStore.
 */
template <class _IndType>
class StringStoreEqualComparator: public std::binary_function<_IndType, _IndType, bool> {
	/** Reference to table to which indices passed for comparation relates to.
	 */
	const typename StringStore<_IndType>::table_t& _table;
public:
	/** @param table Reference to table to which indices passed for comparation relates to.
	 */
	StringStoreEqualComparator(const typename StringStore<_IndType>::table_t& table): _table(table) {}
	/** @return True, if left-hand argument is equal to right hand argument.
	 */
	inline bool operator()(_IndType lhs, _IndType rhs) const {
		// We can't compare just the indices, because newly stored string must be first
		// inserted into store, then compared (and eventually popped out, if founded).
		return strcmp(_table[lhs], _table[rhs]) == 0;
	}
};


//// StringStore (method definitions) ////

/*	Interface item definition.
 */
template <class _IndType>
StringStore<_IndType>::StringStore(size_t max_string_length): _memory_pool(max_string_length + 1), _strings_table(), _strings_index(StringStoreLessComparator<_IndType>(_strings_table)), _str_equal_comp(_strings_table) {}

/*	Interface item definition.
 */
template <class _IndType>
void StringStore<_IndType>::clear(void) {
	_strings_index.clear();
	_strings_table.clear();
	_memory_pool.clear();
}

/*	Interface item definition.
 */
template <class _IndType>
_IndType StringStore<_IndType>::store(const char *str) {			

	// String must be stored to be comparable.
	_IndType index = static_cast<_IndType>(_strings_table.size());
	_strings_table.push_back(str);

	// Search for given string in string index.
	typename _index_t::iterator i_str = _strings_index.lower_bound(index);
	if ( i_str != _strings_index.end() ) {
		// Compare strings for equality.
		if ( _str_equal_comp(static_cast<_IndType>(*i_str), index) ) {
			// Already exists. Pop string back.
			_strings_table.pop_back();
			return static_cast<_IndType>(*i_str);
		}
	}

	if ( this->is_full() ) {
		// No index left to spend...
		throw index_overflow("String store overflow!");
	}

	// New object - new memory needed...
	size_t memory_needed = strlen(str) + 1;
	char* mem = _memory_pool.get_memory(memory_needed); // This may throw!

	// Copy passed string into brand new memory.
	memcpy(mem, str, memory_needed);
	// Store pointer between strings (overwrite temporary stored param).
	_strings_table[index] = mem;
	// Insert and return dereferenced iterator.
	return static_cast<_IndType>(*_strings_index.insert(i_str, index));
}

} // namespace ace

#endif
