takayukisの日記 このページをアンテナに追加 RSSフィード

2016.10.26(水)

[]Diff

こちらの「Wu氏らの手法(the O(NP) algorithm)によるdiff」のJavaScriptのコードをJavaに移植したものです。

アルゴリズムの詳細やソースコードのコメントは上記のサイトを参照してください。

移植したついでに文字列以外のデータ型にも使えるようにしてあります。

package diff;

import java.util.ArrayList;
import java.util.List;
import java.util.function.BiPredicate;

public class Diff<E> {

	private int M;
	private int N;
	private int offset;
	private FP[] fp;
	private BiPredicate<E, E> func;
	private E[] A;
	private E[] B;

	public List<DiffResult<E>> diff(E[] A, E[] B, BiPredicate<E, E> func) {
		this.A = A;
		this.B = B;
		this.func = func;
		M = A.length;
		N = B.length;

		boolean exchanged = false;

		if (N > M) {
			exchanged = true;
			E[] t;
			t = A;
			A = B;
			this.A = B;
			B = t;
			this.B = t;

			int t2 = M;
			M = N;
			N = t2;
		}

		offset = N;
		int delta = M - N;
		int size = M + N + 1;
		fp = new FP[size];
		for (int i = 0; i < size; ++i) {
			fp[i] = new FP();
		}
		int p = -1;
		int k = 0;
		while (fp[delta + offset].y == null || fp[delta + offset].y < N) {
			p = p + 1;
			for (k = -p; k < delta; ++k) {
				snake(k);
			}
			for (k = delta + p; k > delta; --k) {
				snake(k);
			}
			snake(delta);
		}

		FP current = fp[delta + offset];
		List<DiffResult<E>> list = new ArrayList<>();
		char type = 0;
		int a_index = M - 1;
		int b_index = N - 1;
		for (Tree i = current.tree; i != null; i = i.prev) {
			type = i.type;
			if (type == '+') {
				list.add(0, new DiffResult<>(exchanged ? '-' : '+', B[b_index]));
				--b_index;
			} else if (type == '-') {
				list.add(0, new DiffResult<>(exchanged ? '+' : '-', A[a_index]));
				--a_index;
			} else {
				list.add(0, new DiffResult<>('|', A[a_index]));
				--a_index;
				--b_index;
			}
		}
		return list;

	}

	private void snake(int k) {
		if ((k < -N) || (M < k)) {
			return;
		} else {
			FP current = fp[k + offset];
			if (k == -N) {
				FP down = fp[k + 1 + offset];
				current.y = down.y + 1;
				current.tree = new Tree('+', down.tree);
			} else if (k == M) {
				FP slide = fp[k - 1 + offset];
				current.y = slide.y;
				current.tree = new Tree('-', slide.tree);
			} else {
				FP slide = fp[k - 1 + offset];
				FP down = fp[k + 1 + offset];
				if (slide.y == null && down.y == null) {
					current.y = 0;
				} else if (down.y == null || slide.y == null) {
					if (down.y == null) {
						current.y = slide.y;
						current.tree = new Tree('-', slide.tree);
					} else {
						current.y = down.y + 1;
						current.tree = new Tree('+', down.tree);
					}
				} else {
					if (slide.y > (down.y + 1)) {
						current.y = slide.y;
						current.tree = new Tree('-', slide.tree);
					} else {
						current.y = down.y + 1;
						current.tree = new Tree('+', down.tree);
					}
				}
			}
			int y = current.y;
			int x = y + k;
			while (x < M && y < N && func.test(A[x], B[y])) {
				current.tree = new Tree('|', current.tree);
				x++;
				y++;
			}
			current.y = y;
		}
	}

	private static class FP {
		Integer y;
		Tree tree;
	}

	private static class Tree {
		char type;
		Tree prev;

		public Tree(char type, Tree prev) {
			this.type = type;
			this.prev = prev;
		}
	}

	public static void main(String[] args) {
		Diff<Character> diff = new Diff<>();
		List<DiffResult<Character>> result = diff.diff(toChars("string"), toChars("strength"), Character::equals);
		for (DiffResult<Character> dr : result) {
			System.out.print(dr.type);
			System.out.print(" ");
			System.out.println(dr.element);
		}
	}

	static Character[] toChars(String str) {
		Character[] cs = new Character[str.length()];
		for (int i = 0; i < cs.length; i++) {
			cs[i] = Character.valueOf(str.charAt(i));
		}
		return cs;
	}
}
package diff;

public class DiffResult<E> {
	public E element;
	public char type;

	public DiffResult(char type, E element) {
		this.type = type;
		this.element = element;
	}
}

2016.10.15(土)

[]Shell Folders (特殊フォルダ)をコマンドラインで取得する

reg query "HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Explorer\Shell Folders" /s

ただし

!Do not use this registry key REG_SZ Use the SHGetFolderPath or SHGetKnownFolderPath function instead

[]かなり前のCollabNet Subversion Edgeを復旧した時のメモ

かなり前のCollabNet Subversion Edgeは、Java 6でしか動かないという代物で、知らずにJava 8をインストールして環境を壊した時のメモ。

以下のように自分でサービスを登録して復旧し、たしかviewvcというWebブラウザインターフェースは壊したまま放置した。

sc create "CollabNet Subversion Edge" binPath= "C:\Program Files\Java\jdk1.7.0_80\bin\java.exe -classpath C:\csvn\svcwrapper\wrapper.jar -Xrs -Dwrapper.service=true -Dwrapper.working.dir=C:\csvn\svcwrapper\..\appserver -Dwrapper.config=C:\csvn\svcwrapper\conf\wrapper.conf -Dwrapper.additional.1x=-Xrs org.rzo.yajsw.boot.WrapperServiceBooter"

2016.05.30(月)

[]Gitbucket + Jetty + SSL + Windowsサービス化

環境は以下の通り。少し前のメモなので古いです。

インストール

C:\GitBucketJetty

ここにJettyの配布ファイルを展開した中身を置きます。

demo-baseをコピーして必要なファイルのみ残します。

gitbucket-base
│  start.ini
│
├─etc
│      keystore
│
├─lib
│  └─ext
├─resources
├─start.d
│      https.ini
│      ssl.ini
│
└─webapps
       gitbucket.war
  • libとresourcesは、jettyを実行すると自動的に作成されます(作成したとき、jettyは自動的に終了する)。
  • keystoreは確認のために使用し、後で入れ替えます。

start.ini

コメントアウトした項目

jaas, rewrite, websocket, test-realm, jndi

その他も不要なモジュールがあるかもしれないが、とりあえずそのままにしている。

リポジトリの保存先を環境変数で指定

システム環境変数 GITBUCKET_HOME にリポジトリの保存先のパスを指定する。

C:\GitBucketJetty\gitrepos

サービスに登録

Apache commons daemonを使用してサービスに登録する。

commons-daemon-1.0.15-bin-windows.zipをダウンロードした。

アーカイブから次のファイルをコピーしてリネーム

/prunmgr.exe
/amd64/prunsrv.exe

C:\GitBucketJetty\GitBucketJettySrv.exe
C:\GitBucketJetty\prunmgr.exe
サービスインストール用バッチファイル

install_jetty_gitbucket.bat

set JETTY_HOME=C:\GitBucketJetty
GitBucketJettySrv.exe ^
//IS//GitBucketJettyService ^
--DisplayName="GitBucketJetty Service" ^
--Install=%JETTY_HOME%\GitBucketJettySrv.exe ^
--LogPath=%JETTY_HOME%\logs ^
--LogLevel=Debug ^
--StdOutput=auto ^
--StdError=auto ^
--StartMode=Java ^
--StopMode=Java ^
--Startup=auto ^
--StartPath=%JETTY_HOME% ^
--Classpath=%JETTY_HOME%\start.jar ^
--StartClass=org.eclipse.jetty.start.Main ^
--StopClass=org.eclipse.jetty.start.Main ^
++StopParams=--stop ^
++JvmOptions=-Xmx64m ^
++StartParams=jetty.home=%JETTY_HOME% ^
++StartParams=jetty.base=%JETTY_HOME%\gibucket-base ^
++JvmOptions=-DSTOP.PORT=8079 ^
++JvmOptions=-DSTOP.KEY=jetty ^
++StartParams=jetty.logs=%JETTY_HOME%\logs ^
++StartParams=org.mortbay.jetty.Request.maxFormContentSize=1000000

※メモリ関連のJVMオプションは適当

サービスアンインストール用バッチファイル
set JETTY_HOME=C:\GitBucketJetty
GitBucketJettySrv.exe //DS//GitBucketJettyService

ここまでできたらサービスを起動して、Webブラウザで以下のURLにアクセスし、正常起動を確認する。

https://localhost:8443/gitbucket/

確認ができたらサービスは終了しておく。

設定によっては終了もうまくいかない場合があるので、タスクマネージャを起動してプロセスが消えることを確認する。

SSL用のkeystoreの作成(オレオレ証明書

フォルダを1つ作って、その中で作業を行うことにする。

C:\GitBucketJetty\keys

gnuwin32がインストールされていればopensslコマンドがある。

OpenSSL for Windowsインストールしても良い。

openssl.cnf

いずれの場合も、openssl.cnfが存在しないため、エラーになるので存在させておく。

空のファイルでもエラーになるため、次のファイルを用意する。

後ほど、このファイルのパスを環境変数 OPENSSL_CONF に設定する。

※このopenssl.cnfは適当に検索して見つけた。

C:\GitBucketJetty\keys\openssl.cnf

#
# SSLeay example properties file.
# This is mostly being used for generation of certificate requests.
#

RANDFILE        = .rnd

####################################################################
[ ca ]
default_ca    = CA_default        # The default ca section

####################################################################
[ CA_default ]

dir        = C:\\openssl\\\bin\\demoCA    # Where everything is kept
certs        = $dir\\certs                # Where the issued certs are kept
crl_dir    = $dir\\crl                # Where the issued crl are kept
database    = $dir\\index.txt            # database index file.
new_certs_dir    = $dir\\newcerts            # default place for new certs.

certificate    = $dir\\cacert.pem                # The CA certificate
serial        = $dir\\serial                # The current serial number
crl        = $dir\\crl.pem                # The current CRL
private_key    = $dir\\private\\cakey.pem       # The private key
RANDFILE    = $dir\\private\\private.rnd     # private random number file

x509_extensions    = x509v3_extensions    # The extentions to add to the cert
default_days        = 365            # how long to certify for
default_crl_days    = 30            # how long before next CRL
default_md        = md5            # which md to use.
preserve        = no            # keep passed DN ordering

# A few difference way of specifying how similar the request should look
# For type CA, the listed attributes must be the same, and the optional
# and supplied fields are just that :-)
policy        = policy_match

# For the CA policy
[ policy_match ]
countryName            = match
stateOrProvinceName        = match
organizationName        = match
organizationalUnitName    = optional
commonName            = supplied
emailAddress            = optional

# For the ’anything’ policy
# At this point in time, you must list all acceptable ’object’
# types.
[ policy_anything ]
countryName        = optional
stateOrProvinceName    = optional
localityName        = optional
organizationName    = optional
organizationalUnitName    = optional
commonName            = supplied
emailAddress            = optional

####################################################################
[ req ]
default_bits        = 1024
default_keyfile     = privkey.pem
distinguished_name    = req_distinguished_name
attributes        = req_attributes

[ req_distinguished_name ]
countryName            = Country Name (2 letter code)
countryName_min        = 2
countryName_max        = 2

stateOrProvinceName        = State or Province Name (full name)

localityName            = Locality Name (eg, city)

0.organizationName        = Organization Name (eg, company)

organizationalUnitName    = Organizational Unit Name (eg, section)

commonName            = Common Name (eg, your website’s domain name)
commonName_max        = 64

emailAddress            = Email Address
emailAddress_max        = 40

[ req_attributes ]
challengePassword        = A challenge password
challengePassword_min    = 4
challengePassword_max    = 20

[ x509v3_extensions ]
ランダムファイル

パスを指定する必要がある。

後ほど、環境変数 RANDFILE に設定する。

キーの生成

次のバッチファイルを実行し、実行中に聞かれるパスワードなどに答えていく。

入力を間違った場合は、再実行すればよい。

最後にJettyのバージョンに依存したファイル名が登場するので、バージョンが異なる場合は適宜修正すること。

環境変数 JAVA_HOME も使用しているので、事前に設定しておくこと。

テスト用なので、10年間有効な証明書を生成している。

C:\GitBucketJetty\keys\genkey.bat

set BASEPATH=C:\GitBucketJetty\keys
cd %BASEPATH%
set OPENSSL_CONF=%BASEPATH%\openssl.cnf
set RANDFILE=%BASEPATH%\.rnd

rm jetty.pkcs12
rm keystore
rm server.crt
rm server.key

rem http://www.eclipse.org/jetty/documentation/current/configuring-ssl.html
rem Generating Keys and Certificates with OpenSSL
openssl genrsa -aes256 -out server.key 2048
openssl req -new -x509 -days 3650 -key server.key -out server.crt

rem Loading Keys and Certificates via PKCS12
openssl pkcs12 -inkey server.key -in server.crt -export -out jetty.pkcs12
"%JAVA_HOME%\bin\keytool.exe" -importkeystore -srckeystore jetty.pkcs12 -srcstoretype PKCS12 -destkeystore keystore

rem Generating obfuscated password
set /P PASSWORD="Enter password for keystore:"
java -cp ..\lib\jetty-util-9.3.7.v20160115.jar org.eclipse.jetty.util.security.Password %PASSWORD%

「Enter password for keystore:」では、「出力先キーストアのパスワードを入力してください:」で

入力したパスワードと同じものを指定する。

最後にkeystoreのパスワードを難読化して表示する。

OBF:で始まる文字列は後で使用する。

keystoreのコピー

このファイルを上書きする。

C:\GitBucketJetty\gibucket-base\etc\keystore

keystoreのパスワードを設定ファイルに記述

C:\GitBucketJetty\gibucket-base\start.d\ssl.ini

jetty.sslContext.keyStorePassword=OBF:1v2j1uum1xtv1zej1zer1xtn1uvk1v1v
jetty.sslContext.keyManagerPassword=OBF:1v2j1uum1xtv1zej1zer1xtn1uvk1v1v
jetty.sslContext.trustStorePassword=OBF:1v2j1uum1xtv1zej1zer1xtn1uvk1v1v

Webブラウザでの確認

サービスを起動して正常起動を確認する。

Webブラウザで証明書の情報を確認する。

ファイアウォールの設定を行いアクセス可能にする

する。

rootパスワード変更とユーザー作成

Gitbucketのユーザー作成。

テスト用リポジトリの作成

作る。

GitSSLの検証を行わないように設定する

C:\Program Files (x86)\Git\etc\gitconfig

管理者権限でエディタを起動して sslVerify = false の行を追加する。

[http]
	sslCAinfo = /bin/curl-ca-bundle.crt
	sslVerify = false

※最新のgit 2.7.2にはgitconfigファイルが無かったが、Eclipseの Team -> Git -> Configurationで、

キー: http.sslVerify
値: false

を設定することでSSLの検証を回避できた。

ユーザーごとの設定は以下にある模様。

C:\Users\nobody\.gitconfig

git cloneして確認

確認する。

2016.05.23(月)

[]MySQLで日本語の文字が入ったレコードが検索できない時 (JDBC)

JDBC URLに次のプロパティを追加する。

jdbc:mysql://address:3306/dbname?useUnicode=true&characterEncoding=UTF-8

XMLに書くときは、 & を &amp; に。

ツールにはしっかり設定していたのに、サーバの設定ファイルに付け忘れてた。意味不明の結果にしばらく悩んだ(恥)。


追記

utf8mb4を使っている時は characterEncoding=UTF-8JDBC URLから削除して、MySQLのmy.cnfなどで character-set-server = utf8mb4 を設定する。

[]関連レコード件数で一括update (MySQL)

テーブルAとテーブルBが1対多の関係にあって、最適化か何かのためにAにBの件数を保持するような列があるとすると、以下のような書き方で一括設定できる。

UPDATE
    A, (SELECT count(*) as C, id FROM B) B2
SET
    A.count_cache = B2.C
WHERE
    A.id = B2.id

こんな書き方できるのかっていう。

2016.05.18(水)

[]子とすべての先祖の組み合わせを列挙

下のような複数の親と複数の子を持つことができる構造のデータで、子とすべての先祖の組み合わせを列挙してみます。

A→       →D
    B →C
E→       →F

子→親 とします。

public class Pair {
	public String key;
	public String val;
	public Pair(String key, String val) {
		this.key = key;
		this.val = val;
	}
}
public class FlowNetNode {
	public String name;
	public List<FlowNetNode> parents = new ArrayList<>();
	public FlowNetNode(String name) {
		this.name = name;
	}
	public boolean isAncestorName(String name) {
		for (FlowNetNode node : parents) {
			if (node.name.equals(name)) {
				return true;
			}
			if (node.isAncestorName(name)) {
				return true;
			}
		}
		return false;
	}
	public void addPairs(String key, List<Pair> pairs) {
		pairs.add(new Pair(key, name));
		for (FlowNetNode node : parents) {
			node.addPairs(key, pairs);
		}
	}
}
public class FlowNet {
	public Map<String, FlowNetNode> nodeMap = new HashMap<>();
	public void addFlow(String... nameList) {
		List<String> list = Arrays.asList(nameList);
		addFlow(list);
	}
	public void addFlow(List<String> nameList) {
		FlowNetNode parent = null;
		for (int i = nameList.size() - 1; i >= 0; i--) {
			String name = nameList.get(i);
			FlowNetNode node = nodeMap.get(name);
			if (node == null) {
				node = new FlowNetNode(name);
				nodeMap.put(name, node);
			}
			if (parent != null) {
				if (parent.isAncestorName(name)) {
					throw new RuntimeException("Duplication:" + name);
				}
				node.parents.add(parent);
			}
			parent = node;
		}
	}
	public List<Pair> makePair() {
		List<Pair> result = new ArrayList<>();
		for (Entry<String, FlowNetNode> entry : nodeMap.entrySet()) {
			FlowNetNode node = entry.getValue();
			node.addPairs(node.name, result);
		}
		return result;
	}
	public static void main(String[] args) {
		FlowNet net = new FlowNet();
		net.addFlow("A", "B", "C", "D");
		net.addFlow("B", "E");
		net.addFlow("G", "H", "I", "J");
		net.addFlow("H", "K");
		net.addFlow("L", "H");
		List<Pair> pairs = net.makePair();
		for (Pair pair : pairs) {
			System.out.println(pair.key + "=" + pair.val);
		}
	}
}