/*
  コンパイル方法（Linux）：
	$  cc  -lncursesw  -lm  line.c  -o  line

  実行方法：
	$  ./line
    or	$  ./line  計算回数

  操作方法：
	[Q] 終了
	[S] 描画On/Off
	[Space等] 再計算
*/
#include <ncurses.h>
#include <locale.h>
#include <sys/time.h>
#include <math.h>
#include <stdlib.h>

WINDOW *target = NULL;		// 表示先

// 画面表示を切り替える関数
void setTarget(WINDOW *win)
{
	target = win;
}

// 点を描く関数
// x, y：座標
// c：文字
void Plot(int x, int y, char c)
{
	mvwaddch(target, y, x, c);
}

// 直線を描く関数（低速版，直接解法）
// x1, y1：始点の座標
// x2, y2：終点の座標
// c：文字
void SlowDrawLine(int x1, int y1, int x2, int y2, char c)
{
	double	m;
	int	dx, dy;
	int	x, y;

	dx = x2 - x1;
	dy = y2 - y1;
	m = (double)dy/(double)dx;
	for (x = 0; x <= dx; x++) {
//		y = (int)round(m*x);	// round() は四捨五入 <math.h>
		y = m*x + 0.5;		// 正の数ならこれでも同じだし速い
		Plot(x1 + x, y1 + y, c);
	}
}

// 直線を描く関数（高速版）
//
// 実数版DDA（インクリメンタル計算の基本形）
void FastDrawLineDDA1(int x1, int y1, int x2, int y2, char c)
{
	double	m;
	int	dx, dy;
	int	x, y;
	double	e;

	dx = x2 - x1;			// 線分のx方向の長さ
	dy = y2 - y1;			// 線分のy方向の長さ
	m = (double)dy/(double)dx;	// 線分の傾き（微分値）

	e = 0.0;	// y座標の誤差
	y = 0;		// y座標の整数値
		// 基本的な考え方：正確な y座標 = y + e
	for (x = 0; x <= dx; x++) {
		Plot(x1 + x, y1 + y, c);

		e += m;	// 誤差に微分値を加算
			// !! 実数計算の誤差蓄積により直線が歪む可能性あり
		if (e >= 0.5) {		// 誤差が0.5以上なら...
			y++;			// y座標を増やす
			e -= 1.0;		// 誤差は減らす
		} 
	}
}

// 整数版DDA（誤差蓄積を解消，速度も向上）
// （実数版の数式を全体的に dx 倍し，すべての計算を整数化）
void FastDrawLineDDA2(int x1, int y1, int x2, int y2, char c)
{
//	double	m;		// もう要らねー
	int	dx, dy;
	int	x, y;
//	double	e;		// 整数化したったー
	int	e;

	dx = x2 - x1;
	dy = y2 - y1;

	e = 0;
	y = 0;
	for (x = 0; x <= dx; x++) {
		Plot(x1 + x, y1 + y, c);

		e += dy;
		if (2*e >= dx) {
			y++;
			e -= dx;
		} 
	}
}

// DDA微改良（ループ内の計算 2* を削減し効率化）
// （変数を事前に 2倍しておいた）
void FastDrawLineDDA3(int x1, int y1, int x2, int y2, char c)
{
	int	dx, dy;
	int	x, y;
	int	e;
	int	dx2, dy2;		// 効率化版 dx, dy

	dx = x2 - x1;
	dy = y2 - y1;
	dx2 = dx*2;
	dy2 = dy*2;

	e = 0;
	y = 0;
	for (x = 0; x <= dx; x++) {
		Plot(x1 + x, y1 + y, c);

		e += dy2;
		if (e >= dx) {
			y++;
			e -= dx2;
		} 
	}
}

// DDA更に微改良（ループ内の計算を更に効率化）
// （誤差を事前に更新し，ループ内の更新処理を 1〜2回から常に 1回だけに削減）
void FastDrawLineDDA4(int x1, int y1, int x2, int y2, char c)
{
	int	dx, dy;
	int	x, y;
	int	e;
	int	dx2, dy2;
	int	dd2;			// 誤差更新 2回分の合計

	dx = x2 - x1;
	dy = y2 - y1;
	dx2 = dx*2;
	dy2 = dy*2;
	dd2 = dy2 - dx2;

	e = dy2;			// e += dy2; ループの事前に更新
	y = 0;
	for (x = 0; x <= dx; x++) {
		Plot(x1 + x, y1 + y, c);

		if (e >= dx) {
			y++;
			e += dd2;	// 今回分 -dx2 と次回分 +dy2 を一括更新
		} else {
			e += dy2;	// 次回分の事前更新
		}
	}
}

// ブレゼンハムのアルゴリズム
void FastDrawLineBA(int x1, int y1, int x2, int y2, char c)
{
	// ... 課題：定義せよ ...
}


// 時間測定関数
double Timer()
{
	struct timeval	tv;		// 時刻データの構造体

	gettimeofday(&tv, NULL);	// 現在時刻を取得
			// tv.tv_sec：整数成分（秒）
			// tv.tv_usec：小数成分（μ秒）

	return (tv.tv_sec + tv.tv_usec*1.0e-6);
}

int main(int argc, char **argv)
{
	double	t0, t;			// 計算の開始時刻，終了時刻
	int	n = 100000;		// 計算回数
	int	i;			// 計算回数のカウンタ
	int	show = 1;		// 画面表示フラグ
	int	key;			// キーコード
	int	dx = 30, dy = 5;	// 線分の長さのx成分，y成分

	if (argc == 2) n = atoi(argv[1]);	// 計算回数を指定

	setlocale(LC_ALL, "");
	initscr();
	curs_set(0);
	noecho();
	while (1) {
		erase();	// 画面をクリア

		if (show) {	// 図形を画面に...
			setTarget(stdscr);	// 表示（画像出力の時間もかさむ）
		} else {
			setTarget(NULL);	// 非表示（純粋に計算時間だけ測定）
		}


		// 処理時間の測定

		// 低速版
		t0 = Timer();
		for (i = 0; i < n; i++) SlowDrawLine(40,  5, 40+dx, 5+dy, '#');
		t = Timer() - t0;
		mvprintw( 5, 0, "直接解法：\t%f sec", t);

		// 高速版
		t0 = Timer();
		for (i = 0; i < n; i++) FastDrawLineDDA1(40, 10, 40+dx, 10+dy, '#');
		t = Timer() - t0;
		mvprintw(10, 0, "DDA1：\t%f sec", t);

		t0 = Timer();
		for (i = 0; i < n; i++) FastDrawLineDDA2(40, 15, 40+dx, 15+dy, '#');
		t = Timer() - t0;
		mvprintw(15, 0, "DDA2：\t%f sec", t);

		// ...他の手法も同様に測定せよ


		refresh();	// 画面を表示
		key = getch();	// キー入力を取得
		if (key == 'q') break;
		if (key == 's') show = (show + 1)%2;	// 描き込みOn/Off
	}
	endwin();

	return (0);
}