#pragma region CPL License
/*
Nuclex Native Framework
Copyright (C) 2002-2015 Nuclex Development Labs

This library is free software; you can redistribute it and/or
modify it under the terms of the IBM Common Public License as
published by the IBM Corporation; either version 1.0 of the
License, or (at your option) any later version.

This library 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
IBM Common Public License for more details.

You should have received a copy of the IBM Common Public
License along with this library
*/
#pragma endregion // CPL License

#ifndef NUCLEX_GEOMETRY_VOLUMES_HEIGHTFIELD3_H
#define NUCLEX_GEOMETRY_VOLUMES_HEIGHTFIELD3_H

#include "../Point3.h"
#include "../Vector3.h"
#include <algorithm>
#include <stdexcept>
#include <memory>

namespace Nuclex { namespace Geometry { namespace Volumes {

  // ------------------------------------------------------------------------------------------- //

  /// <summary>3D height field with infinite borders on the X and Z axes</summary>
  /// <remarks>
  ///   <para>
  ///     A border-clamped height field is one that extends towards infinity at the borders
  ///     of the grid of defined height values. This is a very useful attribute since it
  ///     prevents gaps resulting from rounding errors when multiple height fields are
  ///     stitched together like it is commonly done with terrain.
  ///   </para>
  ///   <example>
  ///     <code>
  ///            |    |    |      Example of a 2x2 height field with 3x3 height samples.
  ///            |    |    |
  ///       2----+----+----+----  The LinearInterpolateHeightAt() method will continue the
  ///            |:\::|:\::|      heights present at the bordering cells towards infinity.
  ///            |::\:|::\:|
  ///       1----+----+----+----  Some examples:
  ///            |:\::|:\::|        - Querying the height at -100.0, -100.0 will always return
  ///            |::\:|::\:|          the height sample at 0,0.
  ///       0----+----+----+----    - Querying the height at 1.5, -100 will return the height
  ///            |    |    |          half-way between the height samples at 1,0 and 2,0.
  ///       y    |    |    |
  ///        x   0    1    2
  ///     </code>
  ///   </example>
  ///   <para>
  ///     Another attribute of this height field is that for reasons of stability, it is not
  ///     intended as an infinitely thin layer with empty space below it and empty space above
  ///     it, but everything below it is considered to be &quot;inside&quot; while everything
  ///     above it is considered to be &quot;outside&quot;.
  ///   </para>
  /// </remarks>
  template <typename TScalar>
  struct HeightField3 {
  
    /// <summary>Initializes a height field with the specified width and length</summary>
    /// <param name="width">Width of the height field on the X axis in cells</param>
    /// <param name="length">Length of the height field on the Y axis in cells</param>
    /// <remarks>
    ///   Note that the width and length is specified in cells. A height field of just
    ///   1x1 cell will have 4 height samples. So if you want to create a height field
    ///   for a terrain of 257x257 vertices, construct a height field with a size of
    ///   256x256 cells.
    /// </remarks>
    public: HeightField3(std::size_t width, std::size_t length) :
      width(width),
      length(length),
      memory(nullptr),
      heights(nullptr),
      X(0),
      Y(0) {

      // There is one more height sample than there are cells in the height field
      // on each axis (notice we're only changing the local variables here)
      ++width;
      ++length;

      // Set up the memory used to store the height field's height samples
      {
        std::unique_ptr<TScalar *[]> heights(new TScalar *[length]);

        this->memory = new TScalar[width * length];
        for(std::size_t z = 0; z < length; ++z) {
          heights[z] = &this->memory[z * width];
        }

        this->heights = heights.release();
      }
    }

    /// <summary>Destroys the height field</summary>
    public: ~HeightField3() {
      delete []this->memory;
      delete []this->heights;
    }

    /// <summary>Retrieves the width of the height field</summary>
    /// <returns>The height field's width</returns>
    public: std::size_t GetWidth() const { return this->width; }

    /// <summary>Retrieves the length of the height field</summary>
    /// <returns>The height field's length</returns>
    public: std::size_t GetLength() const { return this->length; }

    /// <summary>Clears the entire height field to the specified height</summary>
    /// <param name="height">Height that will be assigned to the height field</param>
    /// <remarks>
    ///   This method works on height samples directly from the height array, not adjusted
    ///   for the position the height field has been placed at.
    /// </remarks>
    public: void Clear(TScalar height = 0) {
      std::size_t count = (this->width + 1) * (this->length + 1);
      std::fill(this->memory, this->memory + count, height);
    }

    /// <summary>Retrieves the height sample at the specified grid location</summary>
    /// <param name="x">X coordinate of the grid location that will be looked up</param>
    /// <param name="y">Y coordinate of the grid location that will be looked up</param>
    /// <returns>The height assigned to the specified grid location</returns>
    /// <remarks>
    ///   This method works on height samples directly from the height array, not adjusted
    ///   for the position the height field has been placed at.
    /// </remarks>
    public: TScalar GetHeightAt(std::size_t x, std::size_t y) const {
      if((x > this->width) || (y > this->length)) {
        throw std::out_of_range("Location is outside of the grid");
      }

      return this->heights[y][x];
    }

    /// <summary>Sets the height sample at the specified grid location</summary>
    /// <param name="x">X coordinate of the grid location that will be set</param>
    /// <param name="y">Y coordinate of the grid location that will be set</param>
    /// <param name="height">Height that will be assigned to the grid location</param>
    /// <remarks>
    ///   This method works on height samples directly from the height array, not adjusted
    ///   for the position the height field has been placed at.
    /// </remarks>
    public: void SetHeightAt(std::size_t x, std::size_t y, TScalar height) {
      if((x > this->width) || (y > this->length)) {
        throw std::out_of_range("Location is outside of the grid");
      }

      this->heights[y][x] = height;
    }

    /// <summary>Retrieves the lowest height sample present in the height field</summary>
    /// <returns>The lowest height sample present in the height field</returns>
    /// <remarks>
    ///   This is the height sample directly from the height array, not adjusted for
    ///   the position the height field has been placed at (in other words, local height
    ///   field coordinates).
    /// </remarks>
    public: TScalar GetMinimumHeight() const {
      std::size_t sampleCount = (this->width + 1) * (this->length + 1);

      TScalar minimumHeight = this->memory[0];
      for(std::size_t index = 1; index < sampleCount; ++index) {
        if(this->memory[index] < minimumHeight) {
          minimumHeight = this->memory[index];
        }
      }

      return minimumHeight;
    }

    /// <summary>Retrieves the highest height sample present in the height field</summary>
    /// <returns>The highest height sample present in the height field</returns>
    /// <remarks>
    ///   This is the height sample directly from the height array, not adjusted for
    ///   the position the height field has been placed at (in other words, local height
    ///   field coordinates).
    /// </remarks>
    public: TScalar GetMaximumHeight() const {
      std::size_t sampleCount = (this->width + 1) * (this->length + 1);

      TScalar maximumHeight = this->memory[0];
      for(std::size_t index = 1; index < sampleCount; ++index) {
        if(this->memory[index] > maximumHeight) {
          maximumHeight = this->memory[index];
        }
      }

      return maximumHeight;
    }

    /// <summary>Uses linear interpolation to get the height at an arbitrary location</summary>
    /// <param name="x">X coordinate that will be interpolated</param>
    /// <param name="y">Y coordinate that will be interpolated</param>
    /// <returns>The height at the specified location</returns>
    public: TScalar LinearInterpolateHeightAt(TScalar x, TScalar y) const {
      x -= this->X;
      y -= this->Y;

      // Calculate the grid index of the X coordinate, clamped to the size of
      // the height map, and the fractional position inside the grid cell
      std::size_t gridX;
      if(x <= 0) {
        gridX = 0;
        x = 0;
      } else {
        gridX = static_cast<std::size_t>(x); // cut off decimal places
        if(gridX >= this->width) {
          gridX = this->width - 1;
          x = 1;
        } else {
          x -= static_cast<TScalar>(gridX);
        }
      }

      // Calculate the grid index of the Y coordinate, clamped to the size of
      // the height map, and the fractional position inside the grid cell
      std::size_t gridY;
      if(y <= 0) {
        gridY = 0;
        y = 0;
      } else {
        gridY = static_cast<std::size_t>(y); // cut off decimal places
        if(gridY >= this->length) {
          gridY = this->length - 1;
          y = 1;
        } else {
          y -= static_cast<TScalar>(gridY);
        }
      }

      TScalar base;
      if((x + y) < 1) {
        // +
        // |\  We're in the near left triangle of the quad
        // +-+
        base = this->heights[gridY][gridX];
        x = (this->heights[gridY][gridX + 1] - base) * x;
        y = (this->heights[gridY + 1][gridX] - base) * y;
      } else {
        // +-+
        //  \| We're in the far right triangle of the quad
        //   +
        base = this->heights[gridY + 1][gridX + 1];
        x = (this->heights[gridY + 1][gridX] - base) * (1 - x);
        y = (this->heights[gridY][gridX + 1] - base) * (1 - y);
      }

      return (base + x + y);
    }

    /// <summary>Offsets the entire height field by the specified amount</summary>
    /// <param name="amountX">Amount the height field will be offset on the X axis</param>
    /// <param name="amountY">Amount the height field will be offset on the Y axis</param>
    /// <param name="amountZ">Amount the height field will be offset on the Z axis</param>
    public: void ShiftBy(TScalar amountX, TScalar amountY, TScalar amountZ) {
      this->X += amountX;
      this->Y += amountY;

      if(amountZ != 0) {
        std::size_t sampleCount = this->width * this->length;
        for(std::size_t index = 1; index < sampleCount; ++index) {
          this->memory[index] += amountZ;
        }
      }
    }

    /// <summary>Offsets the entire height field by the specified amount</summary>
    /// <param name="amount">Amount the height field will be offset</param>
    public: void ShiftBy(const Vector3<TScalar> &amount) {
      this->X += amount.X;
      this->Y += amount.Y;

      if(amount.Z != 0) {
        std::size_t sampleCount = this->width * this->length;
        for(std::size_t index = 1; index < sampleCount; ++index) {
          this->memory[index] += amount.Z;
        }
      }
    }

    /// <summary>Position of the height field on the X axis</summary>
    public: TScalar X;
    /// <summary>Position of the height field on the Y axis</summary>
    public: TScalar Y;

    /// <summary>Width of the height field in cells</summary>
    private: std::size_t width;
    /// <summary>Length of the height field in cells</summary>
    private: std::size_t length;
    /// <summary>Addresses of the height rows in the height field</summary>
    private: TScalar **heights;
    /// <summary>Memory allocated for the entire height field</summary>
    private: TScalar *memory;

  };

  // ------------------------------------------------------------------------------------------- //

}}} // namespace Nuclex::Geometry::Volumes

#endif // NUCLEX_GEOMETRY_VOLUMES_HEIGHTFIELD3_H