2010/05/03(Mon) 09:57:47 編集(投稿者)
using System;
using System.Collections;
using System.Collections.ObjectModel;
using System.Collections.Generic;
using System.Text;
namespace Rei {
/// <summary>
/// 二つのリストの変更情報を作成・保持するクラス。
/// 非変更点も保持する場合は変更後のリストと変更前のリストの全ての情報を保持します。
/// 非変更点を保持しない場合は、変更後のリストがあれば変更前のリストを、
/// 変更前のリストがあれば変更後のリストを復元できます。
/// オブジェクトの比較にはObject.Equals(A,B)を用います。
/// </summary>
public class DifferenceList<T> : IList<DifferenceList<T>.DifferenceListEntry> {
#region private
private List<DifferenceListEntry> _list;
private bool _containsunchanged;
/// <summary>
/// +-のインデックスを取れるFPの配列
/// </summary>
private class FPList {
List<FP> _list;
int _delta;
public FPList(int delta) {
_delta = delta;
_list = new List<FP>(_delta + 2);
for (int i = 0; i <= _delta; i++) _list.Add(new FP());
}
public FP this[int index] {
get {
if (index > _delta) index = _delta + (index - _delta) * 2;
else if (index < 0) index = _delta - index * 2 - 1;
while (index >= _list.Count) _list.Add(new FP());
return _list[index];
}
}
}
/// <summary>
/// エディットパスと現在のyを保存するノード
/// </summary>
private class FP {
public int value;
public PathLink path;
public FP() {
value = -1;
path = null;
}
}
/// <summary>
/// エディットパスを保存するための一方行リンクリスト
/// </summary>
private class PathLink {
public PathLink previous;
public ChangeType type;
public PathLink(PathLink previous, ChangeType type) {
this.previous = previous;
this.type = type;
}
}
private static bool snake(FPList fp, IList<T> A, IList<T> B, int k) {
int x, y, y2;
y = fp[k - 1].value + 1;
y2 = fp[k + 1].value;
if (y > y2) {
fp[k].path = new PathLink(fp[k - 1].path, ChangeType.Deleted);
} else {
fp[k].path = new PathLink(fp[k + 1].path, ChangeType.Added);
y = y2;
}
for (x = y - k; x < A.Count - 1 && y < B.Count - 1 && object.Equals(A[x + 1], B[y + 1]); ) {
x++; y++;
fp[k].path = new PathLink(fp[k].path, ChangeType.Unchanged);
}
if (x == A.Count - 1 && y == B.Count - 1) return true;
fp[k].value = y;
return false;
}
private DifferenceList() {
_list = new List<DifferenceListEntry>();
_containsunchanged = ContainsUnchanged;
}
#endregion
/// <summary>
/// 2つのリストの変更方法のリストを取得します。
/// 変更内容は含まれません。
/// </summary>
/// <param name="originallist">変更前のリスト</param>
/// <param name="new">変更後のリスト</param>
/// <returns></returns>
public static ChangeType[] GetChanges(IList<T> originallist, IList<T> newlist) {
ChangeType[] r;
if (originallist.Count == 0) {
//変更前の長さが0の時
//全部Addに。
r = new ChangeType[newlist.Count];
for (int i = 0; i < newlist.Count; i++) r[i] = ChangeType.Added;
return r;
} else if (newlist.Count == 0) {
//変更後の長さが0の時
//全部Deleteに。
r = new ChangeType[originallist.Count];
for (int i = 0; i < originallist.Count; i++) r[i] = ChangeType.Deleted;
return r;
}
IList<T> A;
IList<T> B;
//長いほうをBに。
if (originallist.Count > newlist.Count) {
A = newlist; B = originallist;
} else {
A = originallist; B = newlist;
}
int delta = B.Count - A.Count;
FPList fp = new FPList(delta);
int k;
int p;
p = 0;
//最初だけ例外
fp[-1].value = -2;
//メインループ
while (true) {
for (k = -p; k < delta; k++) if (snake(fp, A, B, k)) goto find;
for (k = delta + p; k >= delta; k--) if (snake(fp, A, B, k)) goto find;
p++;
}
find:
LinkedList<ChangeType> l = new LinkedList<ChangeType>();
PathLink pl = fp[delta].path;
if (originallist.Count > newlist.Count) {
while (pl != null) {
l.AddFirst(pl.type);
pl = pl.previous;
}
} else {
while (pl != null) {
l.AddFirst((ChangeType)(-(int)pl.type));
pl = pl.previous;
}
}
//先頭は意味無いので削除
l.RemoveFirst();
r = new ChangeType[l.Count];
l.CopyTo(r, 0);
return r;
}
/// <summary>
/// 二つのリストの変更情報を保持するDifferenceListを作成します。
/// </summary>
/// <param name="originallist">差分を取得する変更前のリスト</param>
/// <param name="newlist">差分を取得する変更後のリスト</param>
/// <param name="ContainsUnchanged">originallistを保持する場合はtrue。しない場合はfalse。</param>
public DifferenceList(IList<T> originallist, IList<T> newlist, bool ContainsUnchanged) {
_list = new List<DifferenceListEntry>();
_containsunchanged = ContainsUnchanged;
ChangeType[] list1 = GetChanges(originallist, newlist);
int newindex = 0;
int originalindex = 0;
for (int i = 0; i < list1.Length; i++) {
if (list1[i] != ChangeType.Unchanged || this.ContainsUnchanged) {
if (list1[i] == ChangeType.Added) {
_list.Add(new DifferenceListEntry(ChangeType.Added, newlist[newindex], originalindex, newindex));
} else {
_list.Add(new DifferenceListEntry(list1[i], originallist[originalindex], originalindex, newindex));
}
}
switch (list1[i]) {
case ChangeType.Deleted:
originalindex++;
break;
case ChangeType.Added:
newindex++;
break;
default:
newindex++;
originalindex++;
break;
}
}
}
/// <summary>
/// 非変更点を保持しているかを表します。
/// </summary>
public bool ContainsUnchanged {
get {
return _containsunchanged;
}
}
/// <summary>
/// ContainsUnchangedがtrueの時に変更前のリストを取得します。
/// ContainsUnchangedがfalseの時は例外を投げます。
/// </summary>
/// <returns></returns>
public List<T> GetOriginal() {
if (!ContainsUnchanged) throw new InvalidOperationException();
List<T> l = new List<T>();
for (int i = 0; i < _list.Count; i++) {
if (_list[i].Type != ChangeType.Added) {
l.Add(_list[i].Difference);
}
}
return l;
}
/// <summary>
/// ContainsUnchangedがtrueの時に変更後のリストを取得します。
/// ContainsUnchangedがfalseの時は例外を投げます。
/// </summary>
/// <returns></returns>
public List<T> GetNew() {
if (!ContainsUnchanged) throw new InvalidOperationException();
List<T> l = new List<T>();
for (int i = 0; i < _list.Count; i++) {
if (_list[i].Type != ChangeType.Deleted) {
l.Add(_list[i].Difference);
}
}
return l;
}