herc wrote:
I am looking for an algorithm to implement a revision system. The
data is quite simple. There is a array of objects. New objects can
be added, objects can be deleted, and objects can be moved around in
the array.
I am looking for an efficient way to look at two versions of this
list, capture what changed, and be able to return to init state.
This is somewhat off-topic, but if I understand you correctly you're looking
for a way to store an array along with history difference information which
allows you to revert to any previous version. The simplest way to do this is
to keep a log of each action (add, remove, or move) and go through the log
backwards reversing the actions. Another way is to switch to a persistent
(functional) data structure, such as a persistent red-black tree - then you
could simply keep a reference to the root for each previous version that you
want to return to, and it would remain valid. I don't know of an existing
functional red-black tree implementation in C# though.
Describing differences is trickier, and usually involves first computing the
two versions and then comparing them somehow, such as by using the
Levenshtein distance algorithm to find the minimal set of element additions
and removals to get from the old to the new version. Here's a C#
implementation of the Levenshtein distance algorithm (you would just need to
modify it to deal with your array elements instead of strings):
http://www.merriampark.com/ldcsharp.htm
Hope this helps.
--
Derrick Coetzee, MCAD, MSFT (Speech Server)
This posting is provided "AS IS" with no warranties, and confers no
rights.
