Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
next eleemnt in set
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-02-13 (08:50)
From: Xavier Leroy <Xavier.Leroy@i...>
Subject: Re: [Caml-list] next eleemnt in set
> 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