From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Xavier.Leroy@inria.fr>
X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled 
	version=3.1.3
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by yquem.inria.fr (Postfix) with ESMTP id 39153BBC1
	for <caml-list@yquem.inria.fr>; Wed, 13 Feb 2008 09:50:58 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AgAAAJc+skfAXQInh2dsb2JhbACQPAEBAQgKKZww
X-IronPort-AV: E=Sophos;i="4.25,345,1199660400"; 
   d="scan'208";a="8011302"
Received: from concorde.inria.fr ([192.93.2.39])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 13 Feb 2008 09:50:57 +0100
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id m1D8ovTR001796
	(version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK)
	for <caml-list@inria.fr>; Wed, 13 Feb 2008 09:50:57 +0100
X-IronPort-AV: E=Sophos;i="4.25,345,1199660400"; 
   d="scan'208";a="22569985"
Received: from estephe.inria.fr (HELO [128.93.11.95]) ([128.93.11.95])
  by mail4-relais-sop.national.inria.fr with ESMTP; 13 Feb 2008 09:50:57 +0100
Message-ID: <47B2AF71.8050504@inria.fr>
Date: Wed, 13 Feb 2008 09:50:57 +0100
From: Xavier Leroy <Xavier.Leroy@inria.fr>
User-Agent: Thunderbird 1.5.0.7 (X11/20060915)
MIME-Version: 1.0
To: tmp123 <tmp123@menta.net>
Cc: Caml List <caml-list@inria.fr>
Subject: Re: [Caml-list] next eleemnt in set
References: <47B2ABE6.9090605@menta.net>
In-Reply-To: <47B2ABE6.9090605@menta.net>
X-Enigmail-Version: 0.94.0.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Miltered: at concorde with ID 47B2AF71.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)!
X-Spam: no; 0.00; elt:01 elt:01 logarithmic:01 abstract:01 assert:01 caml-list:01 parameter:02 module:03 element:03 element:03 library:03 let:03 let:03 correctly:04 exists:05 

> 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