revision algorithms

[herc]

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.

Can anyone point me to any good examples?

[Derrick Coetzee [MSFT]]

Re: revision algorithms

herc wrote:[color=blue]
> 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.[/color]

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.