From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 6697F7EEFA for ; Tue, 10 Nov 2015 15:37:08 +0100 (CET) IronPort-PHdr: 9a23:h2XJ5hLm29KgwiB0P9mcpTZWNBhigK39O0sv0rFitYgUI/jxwZ3uMQTl6Ol3ixeRBMOAu68C17ed7fuocFdDyKjCmUhKSIZLWR4BhJdetC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TWM5DIfUi/yKRBybrysXNWC0oLriqvsoNX6WEZhunmUWftKNhK4rAHc5IE9oLBJDeIP8CbPuWZCYO9MxGlldhq5lhf44dqsrtY4q3wD89pozcNLUL37cqIkVvQYSW1+ayFmrPHs4DfZRA2E4XoHGk8biBdODAXfpEX0RJ73uSz7rax31TOXO8L7V5g1Xy6j5uFlUkm7pj0AMmsC8WTQjIRblr9Sph+670hkwovTZseeLud3eK7GO4lCHTVpW5pBEStbDdXvPMM0E+MdMLMA/MHGrFwUoE77XFH0CQ== Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=Neutral smtp.pra=simon.cruanes.2007@m4x.org; spf=Pass smtp.mailfrom=SRS0=DT/w=LN=m4x.org=simon.cruanes.2007@bounces.m4x.org; spf=Pass smtp.helo=postmaster@mx1.polytechnique.org Received-SPF: Neutral (mail2-smtp-roc.national.inria.fr: domain of simon.cruanes.2007@m4x.org does not assert whether or not 129.104.30.34 is permitted sender) identity=pra; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=DT/w=LN=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="simon.cruanes.2007@m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of SRS0=DT/w=LN=m4x.org=simon.cruanes.2007@bounces.m4x.org designates 129.104.30.34 as permitted sender) identity=mailfrom; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=DT/w=LN=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="SRS0=DT/w=LN=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-conformance=sidf_compatible; x-record-type="spf2.0" Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of postmaster@mx1.polytechnique.org designates 129.104.30.34 as permitted sender) identity=helo; client-ip=129.104.30.34; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="SRS0=DT/w=LN=m4x.org=simon.cruanes.2007@bounces.m4x.org"; x-sender="postmaster@mx1.polytechnique.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0DRAAC5/0FWnCIeaIFeFoN4b4QovDCCPoJnggU7EQEBAQEBAQEBEAEBAQEBCAsJCSEugi6CCAEFI0IUEAshEw4CAg8FSYhBDbIgkHgJi1KHdYFEBZZBB4UdgnCFEYIsmiE3hDFxAYUtAQEB X-IPAS-Result: A0DRAAC5/0FWnCIeaIFeFoN4b4QovDCCPoJnggU7EQEBAQEBAQEBEAEBAQEBCAsJCSEugi6CCAEFI0IUEAshEw4CAg8FSYhBDbIgkHgJi1KHdYFEBZZBB4UdgnCFEYIsmiE3hDFxAYUtAQEB X-IronPort-AV: E=Sophos;i="5.20,270,1444687200"; d="asc'?scan'208";a="186945761" Received: from mx1.polytechnique.org ([129.104.30.34]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/ADH-AES256-GCM-SHA384; 10 Nov 2015 15:37:08 +0100 Received: from nunchakus.loria.fr (unknown [152.81.10.98]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ssl.polytechnique.org (Postfix) with ESMTPSA id AF46D5648BD; Tue, 10 Nov 2015 15:37:06 +0100 (CET) Date: Tue, 10 Nov 2015 15:37:14 +0100 From: Simon Cruanes To: Francois Berenger Cc: OCaml List Message-ID: <20151110143714.GJ8217@nunchakus.loria.fr> References: <563A42E9.7010008@inria.fr> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="guYUoZW38XEuSLXo" Content-Disposition: inline In-Reply-To: <563A42E9.7010008@inria.fr> User-Agent: Mutt/1.5.23.1 (2014-03-12) X-AV-Checked: ClamAV using ClamSMTP at svoboda.polytechnique.org (Tue Nov 10 15:37:06 2015 +0100 (CET)) X-Spam-Flag: No, tests=bogofilter, spamicity=0.000000, queueID=EC0395648BE X-Org-Mail: simon.cruanes.2007@polytechnique.org Subject: Re: [Caml-list] Do we have a B-tree implementation in ocaml? --guYUoZW38XEuSLXo Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable I also have a weight-balanced tree implementation (quite experimental, but there are tests), in containers.data: `CCWBTree` (http://cedeela.fr/~simon/software/containers/CCWBTree.S.html). It should provide all the operations you ask for in O(log(n)), and takes a total order as a parameter. Cheers, Le Wed, 04 Nov 2015, Francois Berenger a =C3=A9crit : > I am looking for even a simple implementation with at > least the following operations: >=20 > insert/add, remove, mem/contains and at_rank. >=20 > The at_rank is especially important since it is inefficient > to implement it using fold in a set like the ones from the stdlib. >=20 > Thanks a lot, > F. --=20 Simon Cruanes http://weusepgp.info/ key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3 7D8D 4AC0 1D08 49AA 62B6 --guYUoZW38XEuSLXo Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v2 iQIcBAEBCAAGBQJWQgEWAAoJEErAHQhJqmK2G34QALimMRDzbkPaR7cYjQBuGulu WFKlvX2GSDEmbLPtMZXJqMDMLxmC/gLS4hrbqGgMI+i14GxGA27rxT9DSUJ5AFEx mcoDHfSNev7uL1o5OZp86bJeMymD08ZOuFk8XnCRerTc5DoxeIeVZPrCmYtsqin6 nhOvnK84+YuhQ0TkFvIahiQJ9GJlzNCS15RZVz4jYyYBSTn9rfNOrqsR/P1YlyL3 z6EdHhYb6OwOb9VCGtPgxO9ZRakPA8Ggu2V58y+gqZMFzb5c7P1IGxEq8s7Mlqqz /fkB21s8+mEb0DiQPqoCJr9Z0F4yzXBY67s7LJ2QexGAtkHiqatQbaYEIQVwj5xD sdx9F/DxDebMVpeWDz/CJMyJQg2ic0w5XDNzLUt3HZBTZXh1CRZRRzQi1jI0Sv3Q a8hUIgCyJaUb6Wc6BN0xOh5osfdnSCMY8rRnaY/FhbZmcci+PTjYNrgJU8EkBD/e wT97xAxKGvmVfnulQ/AbcBFmSsSZj/mO3vZs1aZbJUcMA+NEHzO13lqGvAruzi9i Qu/dMM2T6Awy5cZHgTc73lFgIglorBx8VUtN2d4hzl3U0tRjPtPS2WqPsMKhi0Yy D0++VhRzu738Q/7TDtNwXGTrtcYAkbW0DgXSjypW8/kcmdTT0zdfslrR5SvDytvn DITL4fRH7e2GkaQzEmmK =gajV -----END PGP SIGNATURE----- --guYUoZW38XEuSLXo--