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-14 (08:33)
From: tmp123 <tmp123@m...>
Subject: Re: [Caml-list] next eleemnt in set
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
<body bgcolor="#ffffff" text="#000000">
Xavier Leroy wrote:
<blockquote cite="" type="cite">
  <blockquote type="cite">
    <pre wrap="">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.
  <pre wrap=""><!---->
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

Hello Mr. Leroy,<br>
Thanks a lot for your help.<br>
I will try the algoritm you suggests (my only remaining doubt is if it
is more efficient than keep an array sorted (Array.blit), and make
binary searchs, taken into account that the amount of data is around
200 elements).<br>
Thanks again.<br>