[C言語]GLUTのマウス読み取りの仕組み

glutMouseFunc()でマウスボタンの操作を知る

#include <stdio.h>
#include <GL/glut.h>

void display(void){
	glClear(GL_COLOR_BUFFER_BIT);
	glFlush(); 
}

void resize(int w, int h){
	glViewport(0, 0, w, h);
	glLoadIdentity();
}

void mouse(int button, int state, int x, int y){
	switch(button){
		case GLUT_LEFT_BUTTON:
			printf("left");
			break;
		case GLUT_MIDDLE_BUTTON:
			printf("middle");
			break;
		case GLUT_RIGHT_BUTTON:
			printf("right");
			break;
		default:
			break;
	}

	printf(" button is ");

	switch(state){
		case GLUT_UP:
			printf("up");
			break;
		case GLUT_DOWN:
			printf("down");
			break;
		default:
			break;
	}

	printf(" at (%d, %d)\n", x, y);
}

void init(void){
	glClearColor(1.0, 1.0, 1.0, 1.0); 
}

int main(int argc, char *argv[]){
	glutInitWindowPosition(100, 100);
	glutInitWindowSize(320, 240);
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_RGBA); 
	glutCreateWindow(argv[0]); 
	glutDisplayFunc(display); 
	glutReshapeFunc(resize);
	glutMouseFunc(mouse);
	init();
	glutMainLoop(); 
	return 0;
}

$ ./app
libGL error: No matching fbConfigs or visuals found
libGL error: failed to load driver: swrast
left button is down at (172, 123)
left button is up at (172, 123)
right button is down at (188, 65)
right button is up at (188, 65)
right button is down at (188, 65)
right button is up at (186, 123)
left button is down at (186, 123)
left button is up at (109, 116)
left button is down at (207, 222)
left button is up at (207, 222)
left button is down at (103, 74)
left button is up at (102, 170)

お、大分シューティングゲームのイメージが出来てきました。
### ボタンを押した位置から離した位置まで線を引く

#include <stdio.h>
#include <GL/glut.h>

void display(void){
	glClear(GL_COLOR_BUFFER_BIT);
	glFlush(); 
}

void resize(int w, int h){
	glViewport(0, 0, w, h);
	glLoadIdentity();
	glOrtho(-0.5, (GLdouble)w - 0.5, (GLdouble)h - 0.5, -0.5, -1.0, 1.0);
}

void mouse(int button, int state, int x, int y){

	static int x0, y0;

	switch(button){
		case GLUT_LEFT_BUTTON:
			if(state == GLUT_UP){
				glColor3d(0.0, 0.0, 0.0);
				glBegin(GL_LINES);
				glVertex2i(x0, y0);
				glVertex2i(x, y);
				glEnd();
				glFlush();
			} else {
				x0 = x;
				y0 = y;
			}
			break;
		case GLUT_MIDDLE_BUTTON:
			break;
		case GLUT_RIGHT_BUTTON:
			break;
		default:
			break;
	}

}

void init(void){
	glClearColor(1.0, 1.0, 1.0, 1.0); 
}

int main(int argc, char *argv[]){
	glutInitWindowPosition(100, 100);
	glutInitWindowSize(320, 240);
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_RGBA); 
	glutCreateWindow(argv[0]); 
	glutDisplayFunc(display); 
	glutReshapeFunc(resize);
	glutMouseFunc(mouse);
	init();
	glutMainLoop(); 
	return 0;
}

すげえええええええええええええええ
マウス処理そのものやんか

### 配列に位置を記憶する

#include 
#include 

#define MAXPOINTS 100 /* 記憶する点の数 */
GLint point[MAXPOINTS][2]; /* 座標を記憶する配列 */
int pointnum = 0; /* 記憶した座標の数 */

void display(void){
	int i;

	glClear(GL_COLOR_BUFFER_BIT);

	if(pointnum > 1){
		glColor3d(0.0, 0.0, 0.0);
		glBegin(GL_LINES);
		for (i = 0; i < pointnum; ++i){
			glVertex2iv(point[i]);
		}
		glEnd();
	}
	glFlush(); 
}

void resize(int w, int h){
	glViewport(0, 0, w, h);
	glLoadIdentity();
	glOrtho(-0.5, (GLdouble)w - 0.5, (GLdouble)h - 0.5, -0.5, -1.0, 1.0);
}

void mouse(int button, int state, int x, int y){

	switch(button){
		case GLUT_LEFT_BUTTON:
			point[pointnum][0] = x;
			point[pointnum][1] = y;
			if(state == GLUT_UP){
				glColor3d(0.0, 0.0, 0.0);
				glBegin(GL_LINES);
				glVertex2iv(point[pointnum - 1]);
				glVertex2iv(point[pointnum]);
				glEnd();
				glFlush();
			} else {
			}
			if(pointnum < MAXPOINTS - 1) ++pointnum;
			break;
		case GLUT_MIDDLE_BUTTON:
			break;
		case GLUT_RIGHT_BUTTON:
			break;
		default:
			break;
	}

}

void init(void){
	glClearColor(1.0, 1.0, 1.0, 1.0); 
}

int main(int argc, char *argv[]){
	glutInitWindowPosition(100, 100);
	glutInitWindowSize(320, 240);
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_RGBA); 
	glutCreateWindow(argv[0]); 
	glutDisplayFunc(display); 
	glutReshapeFunc(resize);
	glutMouseFunc(mouse);
	init();
	glutMainLoop(); 
	return 0;
}

画面のマウス操作そのもの。
なるほど、OSはこういうGLエンジンも使ってるってことか。

C言語でfreeコマンドを書きたい

メモリを調べるにはfree, top, ps, vmstat, /proc/meminfoなどがある

$ free
total used free shared buff/cache available
Mem: 1008620 312640 186604 2200 509376 542844
Swap: 0 0 0

– 単位はバイト
– メモリ8Gのマシンなら、8G

■freeコマンドの項目
total: 全メモリ
free: 全く利用されていないメモリ
buff/cache: キャッシュとして利用されているけど、解放できる可能性のあるメモリ
used: = total – free – buff/cache

■swapとは
メモリ-の一部をディスク(HDDなど)に退避させて計算を続ける事ができる。この様にしてメモリ-の容量を実際よりも大きく見せるメカニズムを仮想メモリという。そのためにディスクにメモリを退避させるための領域をswapという

メモリ消費量を見積もるには /proc/pid/status の VmHWM

#include <stdio.h>


int main(){

	char command[128];

	sprintf(command, "grep VmHWM /proc/%d/status", getpid()); // getpid():プロセスのIDを知る
	system(command);

	return 0;
}

$ ./dev
VmHWM: 720 kB

■物理メモリ使用量の調べ方
$ ps
PID TTY TIME CMD
459 pts/0 00:00:00 bash
687 pts/0 00:00:00 bash
2490 pts/0 00:00:00 bash
4458 pts/0 00:00:00 ps
18043 pts/0 00:00:00 dev
18140 pts/0 00:00:00 dev
18499 pts/0 00:00:00 dev
18505 pts/0 00:00:00 dev
32396 pts/0 00:00:00 bash
32437 pts/0 00:00:00 bash
32556 pts/0 00:00:00 bash
32600 pts/0 00:00:00 bash

$ cat /proc/18043/status
Name: dev
Umask: 0002
State: T (stopped)
Tgid: 18043
Ngid: 0
Pid: 18043
PPid: 2490
TracerPid: 0
Uid: 1000 1000 1000 1000
Gid: 1000 1000 1000 1000
FDSize: 256
Groups: 1000
NStgid: 18043
NSpid: 18043
NSpgid: 18043
NSsid: 2490
VmPeak: 4508 kB
VmSize: 4508 kB
VmLck: 0 kB
VmPin: 0 kB
VmHWM: 704 kB
VmRSS: 700 kB
RssAnon: 60 kB
RssFile: 640 kB
RssShmem: 0 kB
VmData: 176 kB
VmStk: 132 kB
VmExe: 4 kB
VmLib: 2112 kB
VmPTE: 56 kB
VmSwap: 0 kB
HugetlbPages: 0 kB
CoreDumping: 0
Threads: 1
SigQ: 0/3838
SigPnd: 0000000000000000
ShdPnd: 0000000000000000
SigBlk: 0000000000000000
SigIgn: 0000000000000000
SigCgt: 0000000000000000
CapInh: 0000000000000000
CapPrm: 0000000000000000
CapEff: 0000000000000000
CapBnd: 0000003fffffffff
CapAmb: 0000000000000000
NoNewPrivs: 0
Seccomp: 0
Speculation_Store_Bypass: vulnerable
Cpus_allowed: 3
Cpus_allowed_list: 0-1
Mems_allowed: 00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000001
Mems_allowed_list: 0
voluntary_ctxt_switches: 3
nonvoluntary_ctxt_switches: 2

C言語でaproposコマンドを書きたい

■要求定義
– manページの内容を検索する
– whatisと名付けられたいくつかのファイルを検索している

e.g.
$ apropos passwd
chgpasswd (8) – update group passwords in batch mode
chpasswd (8) – update passwords in batch mode
fgetpwent_r (3) – get passwd file entry reentrantly
getpwent_r (3) – get passwd file entry reentrantly
gpasswd (1) – administer /etc/group and /etc/gshadow
grub-mkpasswd-pbkdf2 (1) – generate hashed password for GRUB
htpasswd (1) – Manage user files for basic authentication
openssl-passwd (1ssl) – compute password hashes
pam_localuser (8) – require users to be listed in /etc/passwd
passwd (1) – change user password
passwd (1ssl) – compute password hashes
passwd (5) – the password file
passwd2des (3) – RFS password encryption
update-passwd (8) – safely update /etc/passwd, /etc/shadow and /etc/group

キーワード検索の原理はregexと同じか。。

C言語でmanコマンドを書きたい

■要求定義
– コマンドのマニュアルを表示する

$ man 調べる語句

/usr/share/man 直下にソースコードがある
man1 ユーザプログラム
man2 システム呼び出し
man3 ライブラリ呼び出し
man4 特殊ファイル
man5 ファイルフォーマット
man6 ゲーム
man7 その他
man8 システム管理者

e.g.
/usr/share/man/man1/ln.1.gz を解凍する

.\" DO NOT MODIFY THIS FILE!  It was generated by help2man 1.47.3.
.TH LN "1" "January 2018" "GNU coreutils 8.28" "User Commands"
.SH NAME
ln \- make links between files
.SH SYNOPSIS
.B ln
[\fI\,OPTION\/\fR]... [\fI\,-T\/\fR] \fI\,TARGET LINK_NAME   (1st form)\/\fR
.br
.B ln
[\fI\,OPTION\/\fR]... \fI\,TARGET                  (2nd form)\/\fR
.br
.B ln
[\fI\,OPTION\/\fR]... \fI\,TARGET\/\fR... \fI\,DIRECTORY     (3rd form)\/\fR
.br
.B ln
[\fI\,OPTION\/\fR]... \fI\,-t DIRECTORY TARGET\/\fR...  \fI\,(4th form)\/\fR
.SH DESCRIPTION
.\" Add any additional description here
.PP
In the 1st form, create a link to TARGET with the name LINK_NAME.
// 省略

$ man ln
make links between files と書かれているのがわかります。

■検討
– gzファイルを配置して、解凍して中身を読み取るプログラムを書いていく
$ ls -l
total 20
-rwxrwxr-x 1 vagrant vagrant 8344 May 18 08:34 dev
-rw-rw-r– 1 vagrant vagrant 267 May 18 08:34 hello.c
-rw-rw-r– 1 vagrant vagrant 1728 May 18 10:53 ln.1.gz

#include <stdio.h>
#include <stdlib.h>

int main(){

	char cmd[256];
	char str[256];
	char filename[] = "./ln.1.gz"; //  /usr/share/man/man1/ln.1.gz

	sprintf(cmd, "gzip -d %s", filename); // gzip -d(ファイル展開)が指す書式文字列に従って cmdが指す文字配列へ書き込み
	
	FILE *fp;
	fp = popen(cmd, "r"); // popenはプロセスをオープンする
	while(fgets(str, 256, fp)){
		printf("%s", str);
	}
	pclose(fp);

	return 0;
}

zipオープンまではいくが、fgetsの出力がうまくいかんな。

C言語でlnコマンドを書きたい

■要求定義
– ファイルやフォルダにリンクを設定する

■lnコマンドの使い方
$ ls -l
total 16
-rw-rw-r– 1 vagrant vagrant 0 May 18 07:09 0516.txt
-rw-rw-r– 1 vagrant vagrant 0 May 18 07:09 0517.txt
-rw-rw-r– 1 vagrant vagrant 0 May 18 07:09 0518.txt
$ ln -s 0518.txt MuseumDay // ln -sでシンボリックリンクを作る
$ ls -l
total 28
-rw-rw-r– 1 vagrant vagrant 11 May 18 08:09 0516.txt
-rw-rw-r– 1 vagrant vagrant 11 May 18 08:09 0517.txt
-rw-rw-r– 1 vagrant vagrant 11 May 18 08:09 0518.txt
lrwxrwxrwx 1 vagrant vagrant 8 May 18 08:11 MuseumDay -> 0518.txt
$ cat MuseumDay // シンボリックリンクの中身を確認
abcde
12345
$ sudo vi MuseumDay
$ cat 0518.txt // シンボリックリンクを編集すると、ファイルが更新されている
abcde
12345
asdf

■検討
– symlinkでシンボリックリンクを作成する
#include
int symlink(const char *oldpath, const char *newpath);

#include <stdio.h>
#include <unistd.h>  // standard symbolic constants and types

int main(){

	if(symlink("./0517.txt", "NYSE") == 0){
		printf("シンボリックリンクを作成しました。\n");
	} else {
		printf("失敗しました。\n");
	}
	
	return 0;
}

$ ls -l
-rw-rw-r– 1 vagrant vagrant 11 May 18 08:09 0516.txt
-rw-rw-r– 1 vagrant vagrant 11 May 18 08:09 0517.txt
-rw-rw-r– 1 vagrant vagrant 17 May 18 08:14 0518.txt
lrwxrwxrwx 1 vagrant vagrant 8 May 18 08:11 MuseumDay -> 0518.txt
lrwxrwxrwx 1 vagrant vagrant 10 May 18 08:34 NYSE -> ./0517.txt

シンボリックリンクそのものは、ファイルまでのパスを含んだ小さなファイル
リダイレクトファイルみたいなものか??


Symbolic links were already present by 1978 in minicomputer operating systems from DEC and Data General’s RDOS.

■アルゴリズム
1. check: old_file must exist and new_file not yet exist
2. create new file, change new file to Link type
3. store old file name in newfile’s INODE.i_block [] area
set file size to length of old_file name
mark new file’s minode dirty
input newfile’s minode
4. mark new file parent minode dirty
input new file’s parent minode

inodeとは 主にUNIX系で使われる、ファイルやディレクトリの属性情報が書いてあるデータ

なるほど、inodeにリンク先の情報が書かれているわけだ。道理で中身を見れないわけだ。

C言語でhistoryコマンドを書きたい

■要求定義
– コマンドの履歴を表示する

■検討
– historyの使われ方
$ history | head // 過去のコマンド一覧
$ history 10 // 最近実行したコマンド

このコマンドの履歴は、.bash_historyに格納されている。catでも見ることができる。
$ cat .bash_history

#include <stdio.h>

int main(){

	FILE *fp;
	char str[1024];

	fp = fopen("./../.bash_history","r");

	if(fp == NULL){
		printf("failed.\n");
		return -1;
	}

	while((fgets(str,256,fp)) !=NULL){
		printf("%s", str);
	}
	fclose(fp);

	return 0;
}

historyはコマンドプロンプトの履歴だが、原理は.bash_historyを見ているだけなので、catコマンドと一緒
隠しファイルの理由の一つは、ユーザが誤って変更や削除しないようにする為とのこと

チーム開発で何かあった時に、.bash_historyを確認する、って工程は使えそうだな。

C言語でchownコマンドを書きたい

■要求定義
– ファイルやフォルダのオーナーやグループを変更する
– chown [オプション] ユーザー[:グループ] ファイル

■chownサンプル
$ ls -l sample.txt
–w–wx-wT 1 vagrant vagrant 89 May 17 11:50 sample.txt
// ここではユーザー所有権「vagrant」、グループ所有権「vagrant」
// [vagrant]から[root]に変更する
$ sudo chown root sample.txt
$ ls -l sample.txt
–w–wx-wT 1 root vagrant 89 May 17 11:50 sample.txt

基本的にファイルを作成したユーザがユーザ所有権者になる
ユーザ所有権を変更すると、所有権者以外はファイルの変更ができなくなる

所有者を自分にしておき、パーミッションを700にすると、他のユーザは見ることができない
ユーザグループに属しておけば、ユーザグループの権限が作業できる

■検討
#include
int chown(const char *path, uid_t owner, gid_t group);

– whoamiで自分のユーザ名、id ${ユーザ名}でuid, gidを調べられる
$ whoami
vagrant
$ id vagrant
uid=1000(vagrant) gid=1000(vagrant) groups=1000(vagrant)

– ユーザ名一覧は「/etc/passwd」ファイルにある
$ cat /etc/passwd
root:x:0:0:root:/root:/bin/bash
// 省略
ubuntu:x:1001:1001:Ubuntu:/home/ubuntu:/bin/bash
mysql:x:111:115:MySQL Server,,,:/nonexistent:/bin/false

■ユーザ追加の手順
$ sudo su –
$ useradd -m hpscript
$ passwd ${ユーザ名} // パスワード設定
$ usermod -G sudo hpscript // sudoユーザに追加
$ cat /etc/group | grep hpscript
sudo:x:27:ubuntu,hpscript
hpscript:x:1002:

■ユーザ変更の手順
$ su hpscript

■グループ追加の手順
$ groupadd test-group

■グループにユーザ追加の手順
$ sudo gpasswd -a hpscript test-group
Adding user hpscript to group test-group
$ id hpscript
uid=1002(hpscript) gid=1002(hpscript) groups=1002(hpscript),1003(test-group)

$ sudo touch hpscript.txt
$ ls -l
-rw-r–r– 1 root root 0 May 18 03:51 hpscript.txt
あれ、sudoでtouchをするとルートユーザで作成したことになりますな。

#include <stdio.h>
#include <unistd.h>

int main(){

	char *fp;
	fp = "./hpscript.txt";
	int uid = 1001;
	int gid = 1001;

	if(chown(fp, uid, gid) == 0){
		printf("success\n");
	} else {
		printf("try again\n");
	};

	return 0;
}

$ ./dev
try again

あれ、なんでやろう??

C言語でchmodコマンドを書きたい

■要求定義
– ファイルやフォルダのアクセス権限を変更する

e.g.
$ ls -l
-rw-rw-r– 1 vagrant vagrant 89 May 17 11:50 sample.txt
$ chmod 777 sample.txt
$ ls -l
-rwxrwxrwx 1 vagrant vagrant 89 May 17 11:50 sample.txt

#include <stdio.h>
#include <sys/stat.h>

int main(void){

	FILE *fp = "./sample.txt";

	chmod(fp, 666);

	return 0;
}

これでは上手く行かない。

#include <stdio.h>
#include <sys/stat.h>

int main(int argc, char**argv){

	char ans;
	int return_code = 0;

	if(argc == 2){
		printf('%sに実行許可を与えます。宜しいでしょうか(y/n)==>', *(argv+1));
		scanf('%c', &ans);

		if(ans == 'y' || ans == 'Y'){
			if(chmod(*(argv+1),
				S_IRUSR | S_IWUSR | S_IXUSR | /* S_IRUSR 00400, S_IWUSR 00200, S_IXUSR 00100 rwx*/
				S_IRGRP | S_IXGRP | /*IRGRP 00040 r-x, IXGRP 00010 */
				S_IROTH | S_IXOTH) == 0) { /*IROTH 00004, S_IXOTH 00001 */
				printf('実行許可を与えました。\n');
			} else {
				printf("実行許可を与えられませんでした\n");
				perror("");
				return 1;
			}
		} else {
			printf("キャンセルします。\n");
		}
	} else {
		printf("実行時引数の数が不正です。\n");
		return 2;
	}

	return 0;
}

■mode一覧
S_ISUID 04000:実行時のセット・ユーザー・ID(set user ID)。
S_ISGID 02000:実行時のセット・グループ・ID(set group ID)。
S_ISVTX 01000:スティッキー(sticky)ビット。
S_IRUSR 00400:所有者(owner)による読み取り(read)。
S_IWUSR 00200:所有者による書き込み(write)。
S_IXUSR 00100:所有者による実行(execute)・検索(search)。
S_IRGRP 00040:グループ(group)による読み取り。
S_IWGRP 00020:グループによる書き込み。
S_IXGRP 00010:グループによる実行・検索。
S_IROTH 00004:他人(others)による読み取り。
S_IWOTH 00002:他人による書き込み。
S_IXOTH 00001:他人による実行・検索。

C言語でgrepコマンドを書きたい

■要求定義
– 指定した文字列がテキスト内に存在した場合、その行を抽出する

e.g.
sample.txt

Aries
Taurus
Gemini
Cancer
Leo
Virgo
Libra
Scorpio
Sagittarius
Capricorn
Aquarius
Pisces

$ grep -n Leo sample.txt // オプションの-nは行数
5:Leo
$ grep -c Leo sample.txt // オプションの-cは回数
1
$ grep Cancer ./*
./sample.txt:Cancer

■検討事項
– 正規表現で、検索文字と完全一致する文字が含まれていれば、ファイル名を返す(return 0)として、含まれていなければreturn 1とするで良いか。

strchrで先頭が一致するアドレスをポインタで返す

#include <stdio.h>
#include <string.h>

int main(void){

	char str[] = "100-0005";
	char *adr1, *adr2;

	adr1 = strchr(str, (int)'-'); //文字列 str の先頭から'-'を探し、最初に見つかった位置をポインタで返却
	printf("result1: %s\n", adr1);

	adr2 = strchr(str, (int)'x'); 
	printf("result2: %s\n", adr2);

	return 0;
}

$ ./dev
result1: -0005
result2: (null)

文字列の一致にはstrstrを使用する。

int main(void){

	char str[] = "〒100-0005 東京都千代田区丸の内一丁目";
	char *adr1, *adr2;

	adr1 = strstr(str, "千代田区"); //文字列strの中から文字列を探しそのアドレスを返す
	printf("result1: %s\n", adr1);

	adr2 = strstr(str, "港区"); 
	printf("result2: %s\n", adr2);

	return 0;
}

$ ./dev
result1: 千代田区丸の内一丁目
result2: (null)

### 正規表現を使った方法
– ヘッダーファイル「regex.h」をインクルード
– 正規表現を使った検索を行うには、正規表現のオブジェクトを格納するregex_t型の構造体と、正規表現にマッチしたインデックスを格納するregmatch_t型の構造体の配列が必要
– regcomp():正規表現コンパイル, regexec():正規表現による検索実行, regfree():regex_t型のオブジェクトのメモリ解放 を使用する

int regcomp(regex_t *preg, const char *regex, int cflags)
int regexec(const regex_t *preg, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags)

#include 
#include 

int main(void){

	char str[] = "〒100-0005 東京都千代田区丸の内一丁目";
	regex_t preg; // 正規表現のオブジェクト
	size_t num = 5;
	regmatch_t pmatch[num]; // 正規表現にマッチしたインデックスを格納

	const char pattern[] = "〒([0-9]{3})-([0-9]{4})(.+)";

	// 正規表現のコンパイル
	if (regcomp(&preg, pattern, REG_EXTENDED|REG_NEWLINE) != 0){
		printf("failed\n");
		return -1;
	}

	// 入力文字列の出力
	printf("input char is: %s\n", str);

	// 正規表現による検索
	if(regexec(&preg, str, num, pmatch, 0) != 0){
		printf("does not matched\n");
	} else {
		for (int i = 0; i < num; i++){
			if(pmatch[i].rm_so >= 0 && pmatch[i].rm_eo >= 0){
				printf("matched index is %d~%d, str: ", (int)pmatch[i].rm_so, (int)pmatch[i].rm_eo);
				for (int j = pmatch[i].rm_so ; j < pmatch[i].rm_eo; j++){
					putchar(str[j]);
				}
			}
			printf("\n");
		}
	}

	// オブジェクトのメモリ開放
	regfree(&preg);

	return 0;
}

C言語でdiffコマンドを書きたい

■要求定義
– ファイルとファイルの内容の違いを表示する
– diff 旧ファイル名 新ファイル名

■diffのサンプル
e.g.
before.txt

体重 66Kg
abcdef
123456

after.txt

体重 64Kg
abcdef
123456

$ diff before.txt after.txt
1c1
< 体重 66Kg --- > 体重 64Kg

■検討
– 差分の計算には(1)編集距離、(2)Longest Common Subsequence:最長共通部分列、(3)Shortest Edit Script
– Wuアルゴリズムでは、2つの要素列を、エディットグラフに見立てて、点(0,0)から点(M,N)までの最短経路を求める問題に還元する
– Wuアルゴリズムは難易度が高いか?

同じか否かを検出

int main(){

	int i, n, c1, c2;
	FILE *fp1, *fp2;

	fp1 = fopen("before.txt", "r");
	fp2 = fopen("after.txt", "r");

	if(fp1==NULL || fp2==NULL){
		printf("file open error\n");
		return 1;
	}

	int ln = 1;
	int cl = 0;

	while ((c1=fgetc(fp1))!=EOF && (c2=fgetc(fp2))!=EOF){
		ln += (c1 == '\n') ? 1: 0;
		cl += (c1 == '\n') ? 0: ++cl;

		if(c1 != c2){
			printf("difference found [%c][%c] at line %d col %d\n", c1, c2, ln, cl);
			fclose(fp1);
			fclose(fp2);
			return 2;
		}

	}
	printf("no difference\n");

	fclose(fp1);
	fclose(fp2);

	return 0;
}

$ ./dev
difference found [6][4] at line 1 col 1022
$ ./dev
no difference
天才がいるな。

■動的計画法(JavaScript)

function distance(A, B){
	const M = A.length;
	const N = B.length;
	// DPのテーブル(大きさ(M + 1)*(N + 1)の2次元配列)
	// D[i][j] = (0, 0)から(i, j)までの最小コスト(編集距離)
	const D = new Array(M + 1);
	for(let i = 0; i <= M; i++){
		D[i] = new Array(N + 1);
		// (0,0)から(i,0)までの距離はi
		D[i][0] = i;
	}
	for(let j = 1; j <= N; j++){
		// (0,0)から(0, j)までの距離はj
		D[0][j] = j;
	}
	// D[i][j]を順番に求める
	for(let i = 1; i <= M; i++){
		for(let j = 1; j <= N; j++){
			// 縦横については +1, 斜めの辺については + 0
			D[i][j] = A[i-1] === B[j - 1]
			 ? Math.min(D[i-1][j] +1, D[i][j-1]+1, D[i-1][j-1])
			 : Math.min(D[i-1][j] +1, D[i][j-1]+1); 
		}
	}
	return D[M][N];
}

gonpなどwuアルゴリズムにはライブラリがあるようです。