[m-rev.] for review: version array reimplementation

[Ralph Becket]

Peter Wang, Monday, 27 July 2009:
> Branches: main
> 
> Make the version array implementation do what it says on the tin.  It claims
> O(1) access for the latest version of the array, but that's true only if the
> array hasn't had any updates, or if you're accessing the last element that was
> updated.  The existing data structure is essentially this:
> 
>         :- type version_array(T)
>             --->    update(
>                         index   :: int,
>                         value   :: T,
>                         next    :: version_array(T)
>                     )
>             ;       base(array(T)).
> 
> Note that even getting the size of the array is O(k), where k is the number of
> updates on the array.

If I recall correctly, my implementation should have ensured that the
latest version of the array was always represented as a base/1 value,
giving the O(1) properties.  Was there a bug in the code?
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------