From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.5 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE, DNS_FROM_RFC_POST,HTML_MESSAGE,MIME_HTML_ONLY autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 04F74BBCA for ; Thu, 14 Feb 2008 09:33:59 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAIuLs0c+KuYMhmdsb2JhbACCOzYpjASBIwEBAQgCCAcIAggJB51C X-IronPort-AV: E=Sophos;i="4.25,351,1199660400"; d="scan'208,217";a="7299783" Received: from smtp.ono.com (HELO resmaa05.ono.com) ([62.42.230.12]) by mail2-smtp-roc.national.inria.fr with ESMTP; 14 Feb 2008 09:33:55 +0100 Received: from [159.23.98.243] (192.146.187.87) by resmaa05.ono.com (7.3.118.8) (authenticated as tmp123@menta.net) id 47B2DDC200103B49 for caml-list@yquem.inria.fr; Thu, 14 Feb 2008 09:44:59 +0100 Message-ID: <47B3FCD9.5000906@menta.net> Date: Thu, 14 Feb 2008 09:33:29 +0100 From: tmp123 User-Agent: Thunderbird 2.0.0.9 (Windows/20071031) MIME-Version: 1.0 To: caml-list Subject: Re: [Caml-list] next eleemnt in set References: <47B2ABE6.9090605@menta.net> <47B2AF71.8050504@inria.fr> In-Reply-To: <47B2AF71.8050504@inria.fr> Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; elt:01 elt:01 logarithmic:01 blit:01 wrote:01 abstract:01 assert:01 caml-list:01 data:02 parameter:02 binary:02 module:03 element:03 element:03 library:03 Xavier Leroy wrote:

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

Hello Mr. Leroy,

Thanks a lot for your help.

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

Thanks again.