471,306 Members | 1,226 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,306 software developers and data experts.

revision algorithms

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?

Feb 23 '06 #1
1 1411
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.
Feb 24 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

reply views Thread by Richard Joseph | last post: by
reply views Thread by chris-list-python | last post: by
1 post views Thread by Burghew | last post: by
4 posts views Thread by Burghew | last post: by
13 posts views Thread by IndianaJonesWB | last post: by
2 posts views Thread by Mark | last post: by
4 posts views Thread by Pietro | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.