/** @file hash_vector.h
 *
 *	Declaration and definition of very simple hashing container.
 *
 *	Note: this container is designed on purpose! It's not intended to be used
 *	as general (STL-like) container. Not only much of general containers
 *	functionality is missing, but (what's serious matter) there is some extra
 *	stuff, that's adjusted to storage of pointers to NGram instances!
 *
 *	(C) Ceslav Przywara 2008, MFF UK Prague
 *
 */

#ifndef _HASH_H
#define _HASH_H

#include <algorithm>
#include <functional>
#include <vector>

namespace ace {

// NOTE: Class is designed with above-lying structure in mind,
// which is generally (very) bad idea. But performace is... performance.

/** Class for storage of 
 *	@param _StType Stored type (should be pointer to NGram).
 *	@param _HashFunc Hashing function type.
 */
template<class _StType, class _HashFunc>
class HashVector {
public:
	/** Stored type definition.
	 */
	typedef _StType type;

private:
	/** Container for items (to be stored) - aka bucket.
	 */
	typedef typename std::vector<_StType> _store_t;
	/** Container for buckets - aka hash table.
	 */
	typedef typename std::vector<_store_t> _buckets_t;

	/** We begin with _init_size buckets (shall be power of two).
	 */
	size_t _init_size;
	/** How much items (in average) per bucket?
	 */
	size_t _bucket_size;
	/** Buckets (hash table).
	 */
	std::vector<_store_t> _buckets;	
	/** Hash function object.
	 */
	_HashFunc _h;
	/** Items counter.
	 */
	size_t _items;
	/** If capacity of vector is bigger than (crop ratio * its size), then we "crop" it.
	 */
	size_t _crop_ratio;

	/** Function object for equal to comparison of two N-gram pointers
	 *	(one passed as constructor param, second as unary operator() param).
	 *	We want to compare pointed values, not pointers themself,
	 *	so this simple functor helps us to do it.
	 */
	class items_compare: public std::unary_function<_StType, bool> {
		/** Searched item (pointer to).
		 */
		const _StType _look_for;
	public:
		/** @param look_for Pointer to searched item.
		 */
		items_compare(_StType look_for): _look_for(look_for) {}
		/**	@param ptr Item to compare with searched one.
		 *	@return Bool, if item pointed to by ptr is equal to item pointed to
		 *		by instance pointer.
		 */
		bool operator()(_StType ptr) const {
			return *ptr == *_look_for;
		}
	};

	/** Function object for less than comparison of two N-gram pointers
	 *	which is based on frequencies of instances they point to.
	 */
	class items_sort: public std::binary_function<_StType, _StType, bool> {
	public:
		/**	@param lhs Left-hand argument (pointer).
		 *	@param rhs Right-hand argument (pointer).
		 *	@return Bool, if instance left hand argument pointed to by ptr is equal to item pointed to
		 *		by instance pointer.
		 */
		bool operator()(_StType lhs, _StType rhs) const {
			// > -> we want descending order!
			return lhs->frequency() > rhs->frequency();
		}
	};

	/** Double sizes the buckets (hash table) and rehashes all containers.
	 */
	void _expand(void) {
		//
		size_t _recent_buckets_size = _buckets.size();

		// Double size buckets table.
		_buckets.resize(_recent_buckets_size * 2);

		bool any_empty = false;
		size_t bucket_index = 0, index_of_empty = 0;
		// Process each bucket (except newly added of course).
		for ( size_t i = 0; i < _recent_buckets_size; ++i ) {
			any_empty = false; // !
			for ( size_t j = 0; j < _buckets[i].size(); ++j ) {
				// Get bucket no.
				bucket_index = _h(_buckets[i][j]) % _buckets.size();				
				if ( bucket_index != i ) {
					// Copy to new bucket.
					_buckets[bucket_index].push_back(_buckets[i][j]);
					if ( !any_empty ) {
						any_empty = true; index_of_empty = j;
					}
				} else if ( any_empty ) {
					// Any empty before?
					_buckets[i][index_of_empty] = _buckets[i][j];
					++index_of_empty;
					// We get rid of tail empty elements later...
				}
			}

			// Really remove "removed" elements (we have to count number of elements added into new bucket,
			// to know how much elements to erase (from end).
			_buckets[i].erase(_buckets[i].end() - _buckets[i + _recent_buckets_size].size(), _buckets[i].end());

			// STD way.
			// The two calls below does exactly the same, as the loop and erase command above.
			// It's a pity, remove_copy_if doesn't really "remove" elements (even in remove_if way!).
			//std::remove_copy_if(_buckets[i].begin(), _buckets[i].end(), std::back_inserter(_buckets[i+_recent_buckets_size]), std::not1(hash_compare(i, _buckets.size())));
			// Two calls are more expensive then one hand written loop.
			//_buckets[i].erase(std::remove_if(_buckets[i].begin(), _buckets[i].end(), hash_compare(i, _buckets.size())), _buckets[i].end());

			// Too much unused space in bucket?
			if ( _crop_ratio ) {
				if ( (_buckets[i].size() * _crop_ratio) < _buckets[i].capacity() ) {
					// So do crop!
					std::vector<_StType>(_buckets[i]).swap(_buckets[i]);
				}
			}
		}
	}

public:
	/** Iterator class needed (simple - only forward, no random access!).
	 */
	class iterator {
		/**
		 */
		typedef HashVector<_StType, _HashFunc> _hash_t;
		/** Iterator pointing at buckets end.
		 */
		typename _hash_t::_buckets_t::const_iterator _end_of_buckets;
		/** Iterator pointing to current bucket.
		 */
		typename _hash_t::_buckets_t::const_iterator _i_bucket;
		/** Iterator pointing to current bucket item.
		 */
		typename _hash_t::_store_t::const_iterator _i_item;
		/** End reached?
		 */
		inline bool _end(void) const { return _i_bucket == _end_of_buckets; }
		/**
		 */
		void _init_item(void) {
			if ( _end() ) {
				return;
			}
			if ( _i_bucket->empty() ) {
				// Find first non empty bucket.
				_next();
			} else {
				_i_item = _i_bucket->begin();
			}
		}
		/**
		 */
		void _next(void) {
			// Go to next non empty bucket.
			while ( (++_i_bucket != _end_of_buckets) && _i_bucket->empty() );
			if ( _i_bucket != _end_of_buckets ) {
				//
				_i_item = _i_bucket->begin();
			}
		}

	public:
		/** Constructs "beginning" iterator.
		 *	@param hash_buckets Reference to const instance of hash table.		 
		 */
		explicit iterator(const typename _hash_t::_buckets_t& hash_buckets): _end_of_buckets(hash_buckets.end()), _i_bucket(hash_buckets.begin()), _i_item() {
			_init_item();
		}
		/** Constructs iterator pointing at the beginning of given bucket (or next in row,
		 *	which is non empty).
		 *	@param hash_buckets Reference to const instance of hash table.
		 *	@param i_bucket Const iterator to certain bucket within given hash table.
		 */
		explicit iterator(const typename _hash_t::_buckets_t& hash_buckets, typename _hash_t::_buckets_t::const_iterator i_bucket): _end_of_buckets(hash_buckets.end()), _i_bucket(i_bucket), _i_item() {
			_init_item();
		}
		/** Constructs iterator pointing at given bucket and given bucket item (must be valid).
		 *	@param hash_buckets Reference to const instance of hash table.
		 *	@param i_bucket Const iterator to certain bucket within given hash table.
		 *	@param i_item Const iterator to certain item within given bucket of given hash table.
		 */
		explicit iterator(const typename _hash_t::_buckets_t& hash_buckets, typename _hash_t::_buckets_t::const_iterator i_bucket, typename _hash_t::_store_t::const_iterator i_item): _end_of_buckets(hash_buckets.end()), _i_bucket(i_bucket), _i_item(i_item) {}

		// Following operators are needed to satisfy NGramStore functionality.

		/** Prefix inc operator.
		 */
		iterator& operator++(void) {
			if ( _end() ) {
				// Do nothing.
				return *this;
			}
			if ( ++_i_item == _i_bucket->end() ) {
				// Find next non empty bucket and set item iterator to its beginning.
				_next();
			}
			return *this;
		}

		/** Dereference operator.
		 *	@return Reference to const instance of stored type.
		 */
		const typename _hash_t::type& operator*(void) const {
			// If invalid, would fall as it should.
			return *_i_item;
		}

		/** Equality operator.
		 *	@param rhs Iterator to be compared for equality.
		 *	@return True, if this iterator is equal to the passed one.
		 */
		bool operator==(const iterator& rhs) const {

			if ( _i_bucket != rhs._i_bucket ) {				
				// Different buckets.
				return false;
			}
			if ( _end() && rhs._end() ) {
				// Both at end.
				return true;
			}
			if ( _end() || rhs._end() ) {
				// Only one at its end, so:
				return false;
			}			
			if ( _i_item == rhs._i_item ) {
				// Both the same!
				return true;
			}
			return false;
		}

		/** Unequality operator.
		 *	@param rhs Iterator to be compared for unequality.
		 *	@return True, if this iterator is not equal to the passed one.
		 */
		bool operator!=(const iterator& rhs) const {
			return !operator==(rhs);
		}

	};

	// Following typedefs are needed to meet in hashset interface used by
	// overlying N-grams storing structure.
	
	/** Const iterator is simply iterator.
	 */
	typedef iterator const_iterator;
	/** Iterator and bool pair (insert method return value).
	 */
	typedef std::pair<iterator, bool> pair_ib;
	/** Pair of iterators (equal_range method return value).
	 */
	typedef std::pair<iterator, iterator> pair_ii;

	/** Constructor creates new hash table.
	 *	@param init_size Starting size of container.
	 *	@param bucket_size Maximum allowed ratio of |items| / |buckets|.
	 *	@param crop_ratio Crop ratio value.
	 */
	HashVector(size_t init_size, size_t bucket_size, size_t crop_ratio): _init_size(1 << init_size), _bucket_size(1 << bucket_size), _buckets(_init_size), _items(0), _crop_ratio(crop_ratio) {}

	/** Assignment operator.
	 */
	HashVector& operator=(const HashVector& rhs) {
		if ( this != &rhs ) {
			_init_size = rhs._init_size;
			_bucket_size = rhs._bucket_size;
			_buckets = rhs._buckets;
			_items = rhs._items;
			_h = rhs._h;
			_crop_ratio = rhs._crop_ratio;
		}
		return *this;
	}

	/** @return Iterator to the beginning of hash table.
	 */
	const_iterator begin(void) const {
		return const_iterator(_buckets);
	}

	/** @return Iterator to the end of hash table.
	 */
	const_iterator end(void) const {
		return const_iterator(_buckets, _buckets.end());
	}

	/** Insert totally relies on caller! No checks (if item is already in) are performed!
	 *	@param value Value to be inserted.
	 *	@return Iterator pointing to inserted value and True. Every insert succeeds!
	 */
	pair_ib insert(_StType value) {
		// Update items counter and do check...
		if ( ++_items > (_buckets.size() * _bucket_size) ) {
			// Expansion needed!
			_expand();
		}
		// Find bucket.
		typename _buckets_t::iterator bucket = _buckets.begin() + (_h(value) % _buckets.size());
		// Insert...
		bucket->push_back(value);
		// ...and return.
		return pair_ib(iterator(_buckets, bucket, bucket->end() - 1), true);
	}

	/**	Searches for given value and returns appropriate range.
	 *	@param value Value to be searched.
	 *	@return Pair of iterators determining search results range.
	 */
	pair_ii equal_range(const _StType value) const {
		
		typename _buckets_t::const_iterator bucket = _buckets.begin() + (_h(value) % _buckets.size());
		// Look into recent.
		typename _store_t::const_iterator searched = std::find_if(bucket->begin(), bucket->end(), items_compare(value));

		if ( searched != bucket->end() ) {
			// Founded!
			return pair_ii(iterator(_buckets, bucket, searched), iterator(_buckets, bucket, searched + 1));
		} else {
			// Sorry, not found.
			return pair_ii(iterator(_buckets, bucket, bucket->end()), iterator(_buckets, bucket, bucket->end()));
		}			
	}

	/** @return Number of items within container.
	 */
	inline size_t size(void) const { return _items; }

	/** Sort items in all buckets according to their frequency.
	 */
	void sort(void) {
		for ( typename _buckets_t::iterator i_bucket = _buckets.begin(); i_bucket != _buckets.end(); ++i_bucket ) {
			std::sort(i_bucket->begin(), i_bucket->end(), items_sort());
		}
	}

};

} // namespace ace

#endif
