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

[Zoltan Somogyi]

On 13-Jun-2003, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> On 13-Jun-2003, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> > During a conversation with Fergus, we agreed that it would be a good idea
> > to move predicates and functions in list.m and map.m that are used by the
> > compiler but are not all that generally useful to new modules. I therefore
> > propose to set up two new modules, list_util.m and map_util.m, and I propose
> > that their initial contents be the following:
> 
> Where would these new modules reside?

In the library directory,

> > map_util:
> > :- 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.

Zoltan.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------