Re: [Caml-list] next eleemnt in set

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> 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