next eleemnt in set

next eleemnt in set

[tmp123]

Hello,

Thanks for your time.

I'm wondering which abstract type (set, map, ...) is the most useful to 
implement the following 3 methods: given a set of values, that are 
unique and ordered (it exists a "compare" function), it is necessary, in 
addition to the "add" and "remove element" methods, to have a "next" 
method. The next method takes as parameter one element of the set, and 
must return the immediatelly next element of the set, according to the 
provided compare function.

Please, have someone any suggestion?

Thanks again.

Re: [Caml-list] next eleemnt in set

[Xavier Leroy]

> I'm wondering which abstract type (set, map, ...) is the most useful to
> implement the following 3 methods: given a set of values, that are
> unique and ordered (it exists a "compare" function), it is necessary, in
> addition to the "add" and "remove element" methods, to have a "next"
> method. The next method takes as parameter one element of the set, and
> must return the immediatelly next element of the set, according to the
> provided compare function.

If I understand correctly your needs, you could use sets as provided
by the standard library with the following definition of "next":

module S = Set.Make(...)

let next elt s =
  let (below, present, above) = S.split elt s in
  assert (present);
  S.min_elt above

This should run in logarithmic time, although the constant factor
might be a little high.

Hope this helps,

- Xavier Leroy

Re: [Caml-list] next eleemnt in set

[tmp123]

[-- Attachment #1: Type: text/html, Size: 1587 bytes --]