#pragma once

#include <vector>
#include <array>

struct rgb_t {
  std::array<unsigned char, 3> data;

};

// 実数座標と色情報
struct dpixel_t {
  double x, y;
  rgb_t c;
  dpixel_t(double x_, double y_, rgb_t c_) :
    x(x_), y(y_), c(c_) {}
};

// 一つのピクセル。
// そのピクセルの色と、そのピクセル内に入った実数座標の点が記録できる
struct pixel_t {
  rgb_t color;
  std::vector< dpixel_t > points;
public:
  bool plot(const double x, const double y,const rgb_t rgba) {
    if (abs(x) > 0.5)
      return false;

    points.emplace_back(x,y, rgba);
  }
  void set(rgb_t c) {
    color = c;
  }
  size_t count()const { return points.size(); }

};

// 実数型のピクセルを書き込める画像データ型
class CRealPixel {

  int _width;
  int _height;

  std::vector< pixel_t > _img;

public:

  // 画像のピクセル数（整数）を指定
  void set_size(int width_,int height_) {
    _width = width_;
    _height = height_;
    _img.resize(_width * _height);

  }

  // 画像のピクセル数を取得
  size_t size()const { return _width * _height; }

  //画素へ書き込み（整数のIndex）
  rgb_t& operator[](const size_t index) {
    return _img[index].color;

  }

  // 画素を取得（二次元）
  rgb_t& get(const int x, const int y) {
    return operator[](y * _width + x);
  }

  // 実数座標の頂点を追加
  void plot(const double x_, const double y_, rgb_t c_) {
    int ix = round(x_);
    int iy = round(y_);
    double x = x_ - ix;
    double y = y_ - iy;
    _img[iy * _width + ix].plot(x, y, c_);
  }

  // RGBの画像を作成
  // まず画素の色で塗りつぶし、その中に実数座標の頂点をプロットする
  // img_ ... 結果の出力先。RGBの配列。
  // ratio_ ... １ピクセルを何ピクセルで表現するか
  // width ... img_の画素数。 width = _width * ratio_;
  // height ... img_の画素数。 height = _height * ratio_;
  void make_int(std::vector<rgb_t>& img_,int ratio_,int*width,int*height) {

    int rwidth = _width * ratio_;
    int rheight = _height * ratio_;
    *width = rwidth;
    *height = rheight;

    img_.resize(rwidth * rheight);

    for (size_t x = 0; x < _width; x++) {
      for (size_t y = 0; y < _height; y++) {

        // このブロックを全着色
        for (size_t ax = x*ratio_; ax < (x+1)*ratio_; ax++) {
          for (size_t ay = y * ratio_; ay < (y + 1) * ratio_; ay++) {

            img_[ay * rwidth + ax] = _img[y * _width + x].color;


          }
        }

        // このブロック内の小数点以下のピクセルをプロット
        for (size_t j = 0; j < _img[y * _width + x].count(); j++) {
          double dx = _img[y * _width + x].points[j].x;
          double dy = _img[y * _width + x].points[j].y;

          //このブロックの中央
          dx += 0.5;
          dy += 0.5;

          int rx = x * ratio_ + (ratio_ * dx);
          int ry = y * ratio_ + (ratio_ * dy);

          img_[ry * rwidth + rx] = _img[y * _width + x].points[j].c;

        }
      }

    }

  }
};

#include <iostream>

#pragma warning(disable:4996)

#include "CRealPixel.hpp"

////////////////////////////////////////////////////////
////////////////////////////////////////////////////////
////////////////////////////////////////////////////////

void Bresenham(
  CRealPixel& img,
  const int width,
  const int height,
  const int sx,
  const int sy,
  const int ex,
  const int ey,
  const rgb_t color
);

////////////////////////////////////////////////////////

void ppmP3_write(
  const char* const fname,
  const int width,
  const int height,
  const unsigned char* const p,
  const int vmax
);


int main()
{
  int width = 100;
  int height = 40;


  CRealPixel crp;

  crp.set_size(width, height);

  // クリア
  for (size_t i = 0; i < crp.size(); i++) {
    crp[i] = rgb_t{ 255,255,255 };
  }

  // ブレゼンハムで書き込み
  int sx = 5;
  int sy = 7;
  int ex = 90;
  int ey = 30;
  Bresenham(crp, width, height, sx, sy, ex, ey, { 0,0,0 });

  // 浮動小数点型で書き込み
  double dx = ex - sx;
  double dy = ey - sy;
  double a = dy / dx;
  double b = 7 - a * 5;
  for (float fx = sx; fx < ex; fx+=0.1) {

    float fy = a * fx + b;

    if (round(fx) >= width)break;
    if (round(fy) >= height)break;

    crp.plot(fx,fy, { 255,0,0 });

  }

  // ピクセル単位で書き込まれた内容と、実数単位で書き込まれた内容を
  // RGBの画像へ変換
  std::vector<rgb_t> ii;
  int w, h;
  crp.make_int(ii, 5, &w, &h);

  // 変換した画像をファイル保存
  ppmP3_write(
    "aaa.ppm",
    w, h,
    &ii[0].data[0], 255
  );

}


//////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////


//! @brief ブレゼンハムの直線描画
//! @param [out] img 画像データ（一次元配列）へのポインタ
//! @param [in] width 画像の幅（画素数）
//! @param [in] height 画像の高さ（画素数）
//! @param [in] sx 線の始点X
//! @param [in] sy 線の始点Y
//! @param [in] ex 線の終点X
//! @param [in] ey 線の終点Y
//! @param [in] color 線の色
void Bresenham(
  CRealPixel& img,
  const int width,
  const int height,
  const int sx,
  const int sy,
  const int ex,
  const int ey,
  const rgb_t color
) {

  const int dx = std::abs(ex - sx);
  const int dy = std::abs(ey - sy);

  const int nx = (sx < ex) ? 1 : -1;
  const int ny = (sy < ey) ? 1 : -1;

  int err = dx - dy;

  int x = sx;
  int y = sy;
  while (1) {

    if (x >= 0 && y >= 0 && x < width && y < height) {
      img[y * width + x] = color;
    }

    if (x == ex && y == ey)
      break;

    const int e2 = 2 * err;
    if (e2 > -dy) {
      err = err - dy;
      x += nx;
    }
    if (e2 < dx) {
      err = err + dx;
      y += ny;
    }
  }
}



// 
// 
// 
/////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////

//! @brief PPM(RGB各1byte,カラー,テキスト)を書き込む
//! @param [in] fname ファイル名
//! @param [in] width 画像の幅
//! @param [in] height 画像の高さ
//! @param [in] p 画像のメモリへのアドレス
//! @param [in] vmax 全てのRGBの中の最大値。普通の画像なら255
//! @details RGBRGBRGB....のメモリを渡すと、RGBテキストでファイル名fnameで書き込む
void ppmP3_write(
  const char* const fname,
  const int width,
  const int height,
  const unsigned char* const p,
  const int vmax
) {

  FILE* fp = fopen(fname, "wb");
  fprintf(fp, "P3\n%d %d\n%d\n", width, height, vmax);

  size_t k = 0;
  for (size_t i = 0; i < (size_t)height; i++) {
    for (size_t j = 0; j < (size_t)width; j++) {
      fprintf(fp, "%d %d %d ",
        p[k * 3 + 0],
        p[k * 3 + 1],
        p[k * 3 + 2]
      );
      k++;
    }
    fprintf(fp, "\n");
  }

  fclose(fp);
}

#pragma warning(disable:4996)

#include <iostream>

#include <array>
#include <vector>
#include <optional>

using rgb_t = std::array<unsigned char, 3>;

struct Image_t {
  int width;
  int height;
  std::vector<rgb_t> data;
  Image_t(int _width_, int _height_) {
    width = _width_;
    height = _height_;
    data = std::vector<rgb_t>(width * height);
  }

  inline int pos(const int x, const int y)const {
    return y * width + x;
  }
  inline bool valid(const int x, const int y)const {
    if (x < 0)return false;
    if (y < 0)return false;
    if (x >= width)return false;
    if (y >= height)return false;
  }
};

void ppmP3_write(
  const char* const fname,
  const int width,
  const int height,
  const unsigned char* const p
);


struct coord_t { 
  int x, y; 
  bool operator==(const coord_t& src) {
    return x == src.x && y == src.y;
  }
  bool operator!=(const coord_t& src) {
    return x != src.x || y != src.y;
  }
};
struct coordd_t {
  double x, y;
};



//! @brief 画像をクリア
//! @param [in,out] img クリアする画像
//! @param [in] color クリアする色
//! @return なし
void fill(Image_t& img, const rgb_t color) {
  std::fill(img.data.begin(), img.data.end(), color);
}

//! @brief 大きさのある点（矩形）を書き込む
//! @param [in,out] img 書き込む画像
//! @param [in] pos 書き込む位置
//! @param [in] color 書き込む色
//! @param [in] size 点の大きさ
//! @return なし
void plot(Image_t& img, const coord_t pos, const rgb_t color, const int size) {

  int bx = pos.x - size / 2;
  int ax = bx + size;
  int by = pos.y - size / 2;
  int ay = by + size;
  for (size_t x = bx; x < ax; x++) {
    for (size_t y = by; y < ay; y++) {
      if (img.valid(x, y)) {
        img.data[img.pos(x, y)] = color;
      }
    }
  }

}

struct QuadraticEquation {
  double plus;
  double minus;
};
 

//! @brief Bezierのtを求める関数
//! @param [in] P1 最初の点の座標
//! @param [in] P2 ハンドルの点の座標
//! @param [in] P3 最後の点の座標
//! @param [in] p求めたい点の座標
//! @return pを得るためのtの値 値は零個～最大二個。零個の時はstd::nulloptを返す
std::optional<QuadraticEquation> BezierInverse(double P1,double P2,double P3,double p) {
  double a = P1 - 2 * P2 + P3;
  double b = 2 * (-P1 + P2);
  double c = P1 - p;

  double test = pow(b, 2) - 4 * a * c;

  // (-b +- sqrt(test)) /  (2*a)

  double plus,minus;
  if (test < 0) {
    //sqrtの中が負数なら虚数なので解をなしとする
    return std::nullopt;
  }
  else {
    plus = (-b + sqrt(test)) / (2 * a);
    minus = (-b - sqrt(test)) / (2 * a);
  }

  
  return QuadraticEquation{ plus,minus };
}

coordd_t BezierXY(coord_t P1, coord_t P2, coord_t P3, double t) {

  double ti = 1.0 - t;

  coordd_t dP;
  dP.x = 
    pow(ti, 2) * P1.x +
    2 * ti * t * P2.x +
    pow(t, 2) * P3.x;
  dP.y = 
    pow(ti, 2) * P1.y +
    2 * ti * t * P2.y +
    pow(t, 2) * P3.y;

  return dP;

}

//! @brief Bézier Curve
//! @param [in,out] img 書き込む画像
//! @param [in] 制御点三点
//! @param [in] color 書き込む色
//! @return なし
//! @sa https://ja.javascript.info/bezier-curve
void Bezier(Image_t& img, const std::array<coord_t, 3>& points, const rgb_t& color) {

  const int step = 30;


  coord_t P1 = points[0];
  coord_t P2 = points[1];
  coord_t P3 = points[2];

  coord_t Pbefore = P1;

  //最初の一点をプロット
  if (img.valid(P1.x, P1.y)) {
    plot(img, P1, color, 1);
  }

  // tの候補を確認
  std::vector< double > cands;

  double t = 0.0;
  while (t < 1.0 && Pbefore!=P3){

    coord_t P = Pbefore;

    double derror = (std::numeric_limits<double>::max)();
    double rett = 100;
    coord_t Pn;
    coord_t tmp;
    coordd_t cd;

    cands.clear();

    // 現在の頂点の周辺
    for (int x = -1; x <= 1; x++) {
      auto tx = BezierInverse(P1.x, P2.x, P3.x, P.x + x);
      if (tx != std::nullopt) {
        cands.push_back(tx.value().plus);
        cands.push_back(tx.value().minus);
      }
    }
    for (int y = -1; y <= 1; y++) {
      auto ty = BezierInverse(P1.y, P2.y, P3.y, P.y + y);
      if (ty != std::nullopt) {
        cands.push_back(ty.value().plus);
        cands.push_back(ty.value().minus);
      }
    }

    for (auto tt : cands) {

      // 直前の点を描いたtより大きく、
      // かつ0.0～1.0に収まっている場合
      if (tt > t && tt > 0.0 && tt <= 1.0 ) {

        cd = BezierXY(P1, P2, P3, tt);
        tmp.x = round(cd.x);
        tmp.y = round(cd.y);

        if (tmp != P) {
          
          double d = pow(cd.x - P.x, 2) + pow(cd.y - P.y, 2);
          if (d < derror) {

            Pn = tmp;

            derror = d;

            rett = tt;
          }
        }

      }

    }

    t = rett;
    if (img.valid(Pn.x, Pn.y)) {
      plot(img, Pn, color, 1);
    }
    else {
      printf("%d %d", Pn.x, Pn.y);
    }

    Pbefore = Pn;

  }

}