Re: Incremental Data Structures

[David Fotland <fotland@xxxxxxxxxxxxx>]

At 03:39 PM 8/17/98 -0400, David Mechner wrote:
>Serge Boisse STNA 7P (33) 562 14 5731 wrote:
>> David Mechner wrote:
>> >
>> > Incremental update done by storing changes adds substantial complexity
>> > to the program, and requires a great deal of effort to design and
>> > implement. It has the advantage that, if done well, is nearly
>> > transparent and puts no pressure on you to steer clear of complex or
>> > expensive algorithms, allowing you to concentrate on generating the
>> > information that you think best allows you to solve problems in go.
>> 
>> Wrong. it is not transparent at all if the structure is complex : 
>> [objects' addresses change as a result of reading and/or backtracking]
>
>We also made this mistake when we first implemented the system. What we
>do now to avoid this problem is copy the value of the saved version back
>to the original location in memory when we revert so all preexisting
>references to objects remain valid. It's quite transparent.

I've also run into this problem.  After some reading I might revert to the
same position, but the group numbers are different.  If I had an old group
number and I use it, I get stale data.  I solve this by using some
canonical property of each data structure to identify it.  For groups, it
is the first stone played in the group for example.  I can get the group 
number from the location of any stone in the group, so I can find the new
group number.

David

>
>Tim and I will post the source code for our revertable object system
>shortly.
>
>-David
>
>-- 
>David A. Mechner            Center for Neural Science
>mechner@xxxxxxxxxxxxxxxxx         4 Washington Place, New York, NY 10003
>212.998.3580                http://cns.nyu.edu/~mechner/
>
>