/**
 * Height map.
 * The data structure is used at many places, it contains requirements from all its users.
 * The tgp Perlin map generator is a more demanding user.
 */
struct HeightMap
{
	HeightMap();
	~HeightMap();

	/** Fixed point type for heights, required by Perlin map generator tgp. */
	typedef int16 height_t;

	height_t *h;     //< Array of heights (#size_x + 1) * (#size_y + 1).
	/* (from tgp) Even though the sizes are always positive, there are many cases where
	 * X and Y need to be signed integers due to subtractions. */
	uint dim_x;      //< Line length #size_x + 1.
	uint total_size; //< height map total size
	uint map_size;   //< Number of tiles in the map.
	uint size_x;     //< Size of the map in X direction.
	uint size_y;     //< Size of the map in Y direction.
	uint log_x;      //< 2log of #size_x.
	uint log_y;      //< 2log of #size_y.

	/**
	 * Get the size of the map in X direction.
	 * @return The size of the map in X direction.
	 */
	inline int MapSizeX() const
	{
		return this->size_x;
	}

	/**
	 * Get the size of the map in Y direction.
	 * @return The size of the map in Y direction.
	 */
	inline int MapSizeY() const
	{
		return this->size_y;
	}

	/**
	 * Get the number of tiles in the map.
	 * @return Number of files in the map.
	 */
	inline int MapSize() const
	{
		return this->map_size;
	}

	/**
	 * Is the given coordinate valid as map coordinate?
	 * @param x X coordinate.
	 * @param y Y coordinate.
	 * @return Whether the indicated position in on the map.
	 */
	inline bool IsValidXY(int x, int y) const
	{
		return x >= 0 && x < (int)this->MapSizeX() && y >= 0 && y < (int)this->MapSizeY();
	}

	/**
	 * Get biggest coordinate of the map in X direction.
	 * @return The biggest coordinate of the map in X direction.
	 */
	inline int MapMaxX() const
	{
		return this->size_x - 1;
	}

	/**
	 * Get biggest coordinate of the map in Y direction.
	 * @return The biggest coordinate of the map in Y direction.
	 */
	inline int MapMaxY() const
	{
		return this->size_y - 1;
	}

	/**
	 * Get the number of bits needed for storing an X coordinate.
	 * @return Number of bits needed for storing an X coordinate.
	 */
	inline int MapLogX() const
	{
		return this->log_x;
	}

	/**
	 * Get the number of bits needed for storing an Y coordinate.
	 * @return Number of bits needed for storing an Y coordinate.
	 */
	inline int MapLogY() const
	{
		return this->log_y;
	}

	/**
	 * Scales the given value by the map size, where the given value is for a 256 by 256 map.
	 * @param n the value to scale.
	 * @return the scaled size.
	 */
	inline uint ScaleByMapSize(uint n) const
	{
		/* Subtract 12 from shift in order to prevent integer overflow
		 * for large values of n. It's safe since the min mapsize is 64x64. */
		return CeilDiv(n << (this->MapLogX() + this->MapLogY() - 12), 1 << 4);
	}

	/**
	 * Height map access (both read and write).
	 * @param x X position.
	 * @param y Y position.
	 * @return height data.
	 */
	inline height_t &Height(uint x, uint y)
	{
		return this->h[x + y * this->dim_x];
	}

	/**
	 * Get height of the map at a given position.
	 * @param x X position.
	 * @param y Y position.
	 * @return height data.
	 */
	inline height_t Height(uint x, uint y) const
	{
		return this->h[x + y * this->dim_x];
	}

	void Setup(uint size_x, uint size_y, HeightMap::height_t initial_height);
	void FixSlopes();
	void CopyToGlobalMap();
};