В настоящее время я пишу diff-алгоритм для обнаружения вставок, удалений, обновлений и перемещений между двумя ревизиями дерева, тогда как у каждого узла есть уникальный идентификатор, который не изменяется при ревизиях.
Iсобираюсь обойти каждое дерево в предзаказе и генерировать различия между двумя узлами на лету и соответственно перемещать cursors (например, после того, как удаленный узел обнаружен, только курсор на старой ревизии перемещается вперед и наоборот для вставленных узлов).
Теперь моя проблема в том, что мне нужно определить точки вырезания и вставки в случае перемещений (когда перемещенный узел вырезается из старой ревизии и вставляется в новую ревизию), чтобы переместить вправокурсор вперед и для последующей визуализации агломерированного представления дерева.
У нас есть простая кодировка parent/leftsibling/rightsibling/firstchild/currnode, тогда как каждый узел имеет уникальный идентификатор, длинное значение.Поскольку в этой кодировке нет сведений о глобальном упорядочении, я сначала подумал о поиске oldNodeKey в новой ревизии после текущего узла в порядке документов и наоборот сделать указатель на старую ревизию и сохранить, если узел найден, и через сколькопосещения узла:
/**
* Search for the supplied node key in following nodes.
*
* @param paramRtx
* Treetank {@link IReadTransaction}
* @param paramNodeKey
* node key to search for
* @return {@code true} if found, {@code false} otherwise
*/
protected Result searchNode(final IReadTransaction paramRtx, final long paramNodeKey) {
checkNotNull(paramRtx);
checkArgument(paramNodeKey >= 0);
final long nodeKey = paramRtx.getNode().getNodeKey();
boolean found = false;
int sumNodes = 0;
for (final AbsAxis axis = new DescendantAxis(paramRtx); !found && axis.hasNext(); axis.next()) {
sumNodes++;
if (axis.getTransaction().getNode().getNodeKey() == paramNodeKey) {
found = true;
}
}
for (final AbsAxis axis = new FollowingAxis(paramRtx); !found && axis.hasNext(); axis.next()) {
sumNodes++;
if (axis.getTransaction().getNode().getNodeKey() == paramNodeKey) {
found = true;
}
}
paramRtx.moveTo(nodeKey);
return new Result(found, sumNodes);
}
По существу, если newResult.mSum> oldResult.mSum, это означает, что узел был "вставлен" и наоборот, и особый случай для newResult.mSum == oldResult.mSum, но я думаю,это неправильно в случае слишком большого количества модификаций, точки вырезания и вставки не будут правильно определены.Я написал много кода для отслеживания различных случаев, но я думаю, что мне нужно переосмыслить весь процесс обнаружения движений: - (
Например, я реализовал что-то вроде этого:
if (mMovedMap.get(newKey) == null && mMovedMap.get(oldKey) == null) {
final ExecutorService pool = Executors.newFixedThreadPool(2);
final Future<Result> foundNew = pool.submit(new Callable<Result>() {
@Override
public Result call() throws Exception {
return searchNode(paramNewRtx, oldKey);
}
});
final Future<Result> foundOld = pool.submit(new Callable<Result>() {
@Override
public Result call() throws Exception {
return searchNode(paramOldRtx, newKey);
}
});
pool.shutdown();
try {
final Result resultNew = foundNew.get();
final Result resultOld = foundOld.get();
paramNewRtx.moveTo(newKey);
paramOldRtx.moveTo(oldKey);
if (resultNew.mFound && resultOld.mFound && resultNew.mSumNodes > resultOld.mSumNodes) {
moveToNextRightNode(paramOldRtx, null);
if (paramOldRtx.getNode().getNodeKey() == newKey) {
diff = EDiff.MOVEDCUT;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedOldDiffs(paramOldRtx, paramNewRtx, oldKey, diff, paramDepth);
} else {
diff = EDiff.MOVEDPASTE;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedNewDiffs(paramOldRtx, paramNewRtx, newKey, diff, paramDepth);
}
} else if (resultNew.mFound && resultOld.mFound
&& resultNew.mSumNodes < resultOld.mSumNodes) {
moveToNextRightNode(paramNewRtx, null);
if (paramNewRtx.getNode().getNodeKey() == oldKey) {
diff = EDiff.MOVEDPASTE;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedNewDiffs(paramOldRtx, paramNewRtx, newKey, diff, paramDepth);
} else {
diff = EDiff.MOVEDCUT;
paramOldRtx.moveTo(oldKey);
paramNewRtx.moveTo(newKey);
fireMovedOldDiffs(paramOldRtx, paramNewRtx, oldKey, diff, paramDepth);
}
} else {
assert foundOld.get() != null && foundOld.get().mFound;
assert foundNew.get() != null && foundNew.get().mFound;
assert foundNew.get().mSumNodes == foundOld.get().mSumNodes;
...
}
тогда как mMovedMap - это простая карта для отслеживания перемещенных узлов после того, как они были обнаружены.
Редактирование: я пытаюсь обнаружить вставки / удаления / обновления и перемещения в дереве, тогда как узлы имеют уникальныеИдентификаторы. Сложная часть, кажется, обнаруживает ходы. Я делаю два обхода предварительного заказа (один поверх старой ревизии и один над новой ревизией). Довольно легко определить вставки / удаления и обновления, но у меня проблемы с обнаружением ходови потому что я всегда сравниваю два узла (один в старой ревизии с одним в новой), я должен знать, какой из двух фактически переместился (если это был узел в старой ревизии, это точка отсечения, еслиузел в новой ревизии был перемещен, это точка вставки). Я также должен знать, является ли это узлом в старой ревизии или узлом в новойревизия, которая была перемещена и как, потому что я создаю агломерированное древовидное представление со всеми операциями редактирования, включенными для визуализации различий в специализированном представлении Sunburst.
Edit: я думаю, что невозможно решить, какой из них вырезанузел (или поддерево) и какой вставленный узел (или поддерево), даже если бы у меня были глобальные идентификаторы.Недостаточно знать, какой из этих двух узлов стоит первым из-за других модификаций: (* 1021 *
Редактировать: Кто-нибудь знает, является ли проблема выяснения, какой узел был перемещен (сравнение двух узлов) в дереве, является NP?-complete? Или, в более общем случае, обнаружение, был ли перемещен один из обоих узлов с учетом курсора на узле в старой ревизии, а другой курсор находится в узле в новой ревизии и был ли перемещенный узел вырезан из старого дереваили если перемещенный узел был вставлен в новую позицию? Алгоритм diff разработан таким образом, что я могу объединять или объединять два дерева так, чтобы они разделяли общие узлы, что хорошо для вставок / удалений / тех же узлов / обновленийи, скорее всего, также для замененных узлов, но я думаю, что это не может быть сделано для ходов? Мне нужна ссылка, если она завершена или неразрешима, потому что это часть моей магистерской диссертации, и, по крайней мере, я хочу описать, почему яне реализовали обнаружение движения (или вернули неработоспособностьреализация; -)).
Редактировать: Может быть решение:
// Check if it has been INSERTED, DELETED or MOVED.
// ================================================================
final long nodeKeyOld = paramOldRtx.getNode().getNodeKey();
final long nodeKeyNew = paramNewRtx.getNode().getNodeKey();
final boolean movedOld = paramOldRtx.moveTo(nodeKeyNew);
final boolean movedNew = paramNewRtx.moveTo(nodeKeyOld);
if (!movedNew && mDiff == EDiff.DELETED) {
paramOldRtx.moveTo(nodeKeyOld);
if (paramOldRtx.getNode().getNodeKey() == mDeletedKey) {
movedNew = true;
}
}
if (movedOld && movedNew) {
diff = EDiff.MOVED;
} else if (movedOld) {
paramOldRtx.moveTo(nodeKeyOld);
mDeletedKey = paramOldRtx.getNode().getNodeKey();
diff = EDiff.DELETED;
} else {
diff = EDiff.INSERTED;
}
для обнаружения самой операции MOVE, как я это делаю сейчас (особый случай проверки !movedNew && mDiff == EDiff.DELETED необходим для конца дерева, где были выполнены только DELETES, но узлы также могут быть перемещены). Во всех других случаях должно быть достаточно проверить, можно ли переместить курсор (транзакцию) на новой ревизии на узел в старой ревизии, а курсор на старую ревизию можно переместить на узел в новой ревизии, верно?
Затем я должен отслеживать все предстоящие изменения (или также идентичные узлы), и если обнаруживается другое движение, я должен проверить, является ли один из двух ключей узла (от узла в старой ревизии и узла в новая редакция) встречалась раньше. Если это старый узел, он должен быть вырезан, а текущее движение - вставка, в противном случае наоборот). Если это не один из ключей, это должна быть другая операция перемещения.
Что ты думаешь? Я немного неохотно реализую это, если я не уверен, по крайней мере, на 99%, работает ли он. Я потратил около 6 дней на решение, которое не сработало.
Редактировать: Хорошо, я думаю, что это плохая идея, потому что я не знаю, как двигать курсоры вперед, если я не знаю, в какой момент именно это узел, который был перемещен.
С уважением,
Johannes