[m-rev.] for review: list_util and map_util

Zoltan Somogyi zs at cs.mu.OZ.AU
Fri Jun 13 18:42:17 AEST 2003

On 13-Jun-2003, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> > > :- pred lower_bound_search((map.map(K, V)), K, K, V).
> > > :- pred upper_bound_search((map.map(K, V)), K, K, V).
> > > :- pred remove_smallest((map.map(K, V)), K, V, (map.map(K, V))).
> > 
> > These operations currently take O(log N) time, but if they were
> > implemented in a different module without access to the representation
> > details of maps, they would have to take O(N) time, I think.
> They are really implemented in tree234.m. Whether the usually used interface
> predicate is in map or map_util doesn't influence performance.

On second thought, it does influence whether it will work :-) Unless map.m
exports the equivalent between map and tree234, predicates in map_util
must do their work by calling predicates in map.m (e.g. map__to_assoc_list)
to access the map elements themselves.

mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe

More information about the reviews mailing list