Hello community, here is the log from the commit of package ocaml-ptmap for openSUSE:Factory checked in at 2020-09-14 12:30:09 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Comparing /work/SRC/openSUSE:Factory/ocaml-ptmap (Old) and /work/SRC/openSUSE:Factory/.ocaml-ptmap.new.4249 (New) ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ocaml-ptmap" Mon Sep 14 12:30:09 2020 rev:4 rq:834213 version:2.0.5 Changes: -------- --- /work/SRC/openSUSE:Factory/ocaml-ptmap/ocaml-ptmap.changes 2020-08-24 15:07:30.190522724 +0200 +++ /work/SRC/openSUSE:Factory/.ocaml-ptmap.new.4249/ocaml-ptmap.changes 2020-09-14 12:31:20.201213756 +0200 @@ -1,0 +2,6 @@ +Mon Sep 7 07:07:07 UTC 2020 - [email protected] + +- Update to 2.0.5 + remove merged ptmap-ocaml-4.11.patch + +------------------------------------------------------------------- Old: ---- ocaml-ptmap-2.0.4.tar.xz ptmap-ocaml-4.11.patch New: ---- ocaml-ptmap-2.0.5.tar.xz ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Other differences: ------------------ ++++++ ocaml-ptmap.spec ++++++ --- /var/tmp/diff_new_pack.YkD8wT/_old 2020-09-14 12:31:21.241214419 +0200 +++ /var/tmp/diff_new_pack.YkD8wT/_new 2020-09-14 12:31:21.241214419 +0200 @@ -17,7 +17,7 @@ Name: ocaml-ptmap -Version: 2.0.4 +Version: 2.0.5 Release: 0 %{?ocaml_preserve_bytecode} Summary: Maps over integers implemented as Patricia trees @@ -25,7 +25,6 @@ Group: Development/Languages/OCaml URL: https://opam.ocaml.org/packages/ptmap Source0: %{name}-%{version}.tar.xz -Patch0: ptmap-ocaml-4.11.patch BuildRequires: ocaml BuildRequires: ocaml-dune BuildRequires: ocaml-rpm-macros >= 20200514 ++++++ _service ++++++ --- /var/tmp/diff_new_pack.YkD8wT/_old 2020-09-14 12:31:21.269214437 +0200 +++ /var/tmp/diff_new_pack.YkD8wT/_new 2020-09-14 12:31:21.269214437 +0200 @@ -1,10 +1,13 @@ <services> <service name="tar_scm" mode="disabled"> <param name="filename">ocaml-ptmap</param> - <param name="revision">dune</param> + <param name="revision">e08084caa43fa7c1e08c43858cb04cb6c42cf2df</param> <param name="scm">git</param> - <param name="url">https://github.com/olafhering/ocaml-ptmap.git</param> - <param name="versionformat">2.0.4</param> + <param name="submodules">disable</param> + <param name="url">https://github.com/backtracking/ptmap.git</param> + <param name="versionformat">@PARENT_TAG@</param> + <param name="versionrewrite-pattern">[v]?([^+]+)(.*)</param> + <param name="versionrewrite-replacement">\1</param> </service> <service name="recompress" mode="disabled"> <param name="file">*.tar</param> ++++++ ocaml-ptmap-2.0.4.tar.xz -> ocaml-ptmap-2.0.5.tar.xz ++++++ diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/CHANGES.md new/ocaml-ptmap-2.0.5/CHANGES.md --- old/ocaml-ptmap-2.0.4/CHANGES.md 1970-01-01 01:00:00.000000000 +0100 +++ new/ocaml-ptmap-2.0.5/CHANGES.md 2020-09-04 13:21:59.000000000 +0200 @@ -0,0 +1,16 @@ + +# 2.0.5 + - switch from obuild to dune and to opam 2.0 + - fixed compilation with old versions of OCaml + - document the difference wrt `Map.S` specs (issue #11) + - more efficient implementation of `union` (issue #7) + - add `update` (Andy Li) + - add `filter_map` (rwmjones) + - no more use of qtest, move tests from ptmap.ml to test.ml + +# 2.0.0 + - added missing functions to conform to `Map.S` (Francois Berenger) + - unit tests (Francois Berenger) + +# 1.0.0 + - first opam package diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/COPYING new/ocaml-ptmap-2.0.5/COPYING --- old/ocaml-ptmap-2.0.4/COPYING 1970-01-01 01:00:00.000000000 +0100 +++ new/ocaml-ptmap-2.0.5/COPYING 2020-09-04 13:21:59.000000000 +0200 @@ -0,0 +1,12 @@ +bitv - Objective Caml bit vectors library +Copyright (C) 1999 Jean-Christophe FILLIATRE + +This software is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public +License version 2, with the special exception on linking +described in file LICENSE. + +This software is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/LICENSE new/ocaml-ptmap-2.0.5/LICENSE --- old/ocaml-ptmap-2.0.4/LICENSE 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/LICENSE 2020-09-04 13:21:59.000000000 +0200 @@ -1,142 +1,130 @@ -ptmap is distributed under the terms of the -GNU Lesser General Public License (LGPL) version 2.1 (included below). +The Library is distributed under the terms of the GNU Library General +Public License version 2 (included below). -As a special exception to the GNU Lesser General Public License, you may link, -statically or dynamically, a "work that uses ptmap" with a publicly distributed -version of ptmap to produce an executable file containing portions of ptmap, and -distribute that executable file under terms of your choice, without any of the -additional requirements listed in clause 6 of the GNU Lesser General Public -License. By "a publicly distributed version of ptmap", we mean either the -unmodified ptmap as distributed, or a modified version of the ptmap that is -distributed under the conditions defined in clause 2 of the GNU Lesser General -Public License. This exception does not however invalidate any other reasons -why the executable file might be covered by the GNU Lesser General Public License. +As a special exception to the GNU Library General Public License, you +may link, statically or dynamically, a "work that uses the Library" +with a publicly distributed version of the Library to produce an +executable file containing portions of the Library, and distribute +that executable file under terms of your choice, without any of the +additional requirements listed in clause 6 of the GNU Library General +Public License. By "a publicly distributed version of the Library", we +mean either the unmodified Library as distributed, or a +modified version of the Library that is distributed under the +conditions defined in clause 3 of the GNU Library General Public +License. This exception does not however invalidate any other reasons +why the executable file might be covered by the GNU Library General +Public License. + +====================================================================== + GNU LIBRARY GENERAL PUBLIC LICENSE + Version 2, June 1991 ----------------------------------------------------------------------- - - GNU LESSER GENERAL PUBLIC LICENSE - Version 2.1, February 1999 - - Copyright (C) 1991, 1999 Free Software Foundation, Inc. - 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + Copyright (C) 1991 Free Software Foundation, Inc. + 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Everyone is permitted to copy and distribute verbatim copies of this license document, but changing it is not allowed. -[This is the first released version of the Lesser GPL. It also counts - as the successor of the GNU Library Public License, version 2, hence - the version number 2.1.] +[This is the first released version of the library GPL. It is + numbered 2 because it goes with version 2 of the ordinary GPL.] - Preamble + Preamble The licenses for most software are designed to take away your freedom to share and change it. By contrast, the GNU General Public Licenses are intended to guarantee your freedom to share and change free software--to make sure the software is free for all its users. - This license, the Lesser General Public License, applies to some -specially designated software packages--typically libraries--of the -Free Software Foundation and other authors who decide to use it. You -can use it too, but we suggest you first think carefully about whether -this license or the ordinary General Public License is the better -strategy to use in any particular case, based on the explanations -below. - - When we speak of free software, we are referring to freedom of use, -not price. Our General Public Licenses are designed to make sure that -you have the freedom to distribute copies of free software (and charge -for this service if you wish); that you receive source code or can get -it if you want it; that you can change the software and use pieces of -it in new free programs; and that you are informed that you can do -these things. + This license, the Library General Public License, applies to some +specially designated Free Software Foundation software, and to any +other libraries whose authors decide to use it. You can use it for +your libraries, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. To protect your rights, we need to make restrictions that forbid -distributors to deny you these rights or to ask you to surrender these -rights. These restrictions translate to certain responsibilities for -you if you distribute copies of the library or if you modify it. +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if +you distribute copies of the library, or if you modify it. For example, if you distribute copies of the library, whether gratis or for a fee, you must give the recipients all the rights that we gave you. You must make sure that they, too, receive or can get the source -code. If you link other code with the library, you must provide -complete object files to the recipients, so that they can relink them -with the library after making changes to the library and recompiling +code. If you link a program with the library, you must provide +complete object files to the recipients so that they can relink them +with the library, after making changes to the library and recompiling it. And you must show them these terms so they know their rights. - We protect your rights with a two-step method: (1) we copyright the -library, and (2) we offer you this license, which gives you legal + Our method of protecting your rights has two steps: (1) copyright +the library, and (2) offer you this license which gives you legal permission to copy, distribute and/or modify the library. - To protect each distributor, we want to make it very clear that -there is no warranty for the free library. Also, if the library is -modified by someone else and passed on, the recipients should know -that what they have is not the original version, so that the original -author's reputation will not be affected by problems that might be -introduced by others. + Also, for each distributor's protection, we want to make certain +that everyone understands that there is no warranty for this free +library. If the library is modified by someone else and passed on, we +want its recipients to know that what they have is not the original +version, so that any problems introduced by others will not reflect on +the original authors' reputations. - Finally, software patents pose a constant threat to the existence of -any free program. We wish to make sure that a company cannot -effectively restrict the users of a free program by obtaining a -restrictive license from a patent holder. Therefore, we insist that -any patent license obtained for a version of the library must be -consistent with the full freedom of use specified in this license. - - Most GNU software, including some libraries, is covered by the -ordinary GNU General Public License. This license, the GNU Lesser -General Public License, applies to certain designated libraries, and -is quite different from the ordinary General Public License. We use -this license for certain libraries in order to permit linking those -libraries into non-free programs. - - When a program is linked with a library, whether statically or using -a shared library, the combination of the two is legally speaking a -combined work, a derivative of the original library. The ordinary -General Public License therefore permits such linking only if the -entire combination fits its criteria of freedom. The Lesser General -Public License permits more lax criteria for linking other code with -the library. - - We call this license the "Lesser" General Public License because it -does Less to protect the user's freedom than the ordinary General -Public License. It also provides other free software developers Less -of an advantage over competing non-free programs. These disadvantages -are the reason we use the ordinary General Public License for many -libraries. However, the Lesser license provides advantages in certain -special circumstances. - - For example, on rare occasions, there may be a special need to -encourage the widest possible use of a certain library, so that it -becomes a de-facto standard. To achieve this, non-free programs must -be allowed to use the library. A more frequent case is that a free -library does the same job as widely used non-free libraries. In this -case, there is little to gain by limiting the free library to free -software only, so we use the Lesser General Public License. - - In other cases, permission to use a particular library in non-free -programs enables a greater number of people to use a large body of -free software. For example, permission to use the GNU C Library in -non-free programs enables many more people to use the whole GNU -operating system, as well as its variant, the GNU/Linux operating -system. - - Although the Lesser General Public License is Less protective of the -users' freedom, it does ensure that the user of a program that is -linked with the Library has the freedom and the wherewithal to run -that program using a modified version of the Library. + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that companies distributing free +software will individually obtain patent licenses, thus in effect +transforming the program into proprietary software. To prevent this, +we have made it clear that any patent must be licensed for everyone's +free use or not licensed at all. + + Most GNU software, including some libraries, is covered by the ordinary +GNU General Public License, which was designed for utility programs. This +license, the GNU Library General Public License, applies to certain +designated libraries. This license is quite different from the ordinary +one; be sure to read it in full, and don't assume that anything in it is +the same as in the ordinary license. + + The reason we have a separate public license for some libraries is that +they blur the distinction we usually make between modifying or adding to a +program and simply using it. Linking a program with a library, without +changing the library, is in some sense simply using the library, and is +analogous to running a utility program or application program. However, in +a textual and legal sense, the linked executable is a combined work, a +derivative of the original library, and the ordinary General Public License +treats it as such. + + Because of this blurred distinction, using the ordinary General +Public License for libraries did not effectively promote software +sharing, because most developers did not use the libraries. We +concluded that weaker conditions might promote sharing better. + + However, unrestricted linking of non-free programs would deprive the +users of those programs of all benefit from the free status of the +libraries themselves. This Library General Public License is intended to +permit developers of non-free programs to use free libraries, while +preserving your freedom as a user of such programs to change the free +libraries that are incorporated in them. (We have not seen how to achieve +this as regards changes in header files, but we have achieved it as regards +changes in the actual functions of the Library.) The hope is that this +will lead to faster development of free libraries. The precise terms and conditions for copying, distribution and modification follow. Pay close attention to the difference between a "work based on the library" and a "work that uses the library". The -former contains code derived from the library, whereas the latter must -be combined with the library in order to run. +former contains code derived from the library, while the latter only +works together with the library. + + Note that it is possible for a library to be covered by the ordinary +General Public License rather than by this special one. - GNU LESSER GENERAL PUBLIC LICENSE + GNU LIBRARY GENERAL PUBLIC LICENSE TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION - 0. This License Agreement applies to any software library or other -program which contains a notice placed by the copyright holder or -other authorized party saying it may be distributed under the terms of -this Lesser General Public License (also called "this License"). -Each licensee is addressed as "you". + 0. This License Agreement applies to any software library which +contains a notice placed by the copyright holder or other authorized +party saying it may be distributed under the terms of this Library +General Public License (also called "this License"). Each licensee is +addressed as "you". A "library" means a collection of software functions and/or data prepared so as to be conveniently linked with application programs @@ -153,8 +141,8 @@ "Source code" for a work means the preferred form of the work for making modifications to it. For a library, complete source code means all the source code for all modules it contains, plus any associated -interface definition files, plus the scripts used to control -compilation and installation of the library. +interface definition files, plus the scripts used to control compilation +and installation of the library. Activities other than copying, distribution and modification are not covered by this License; they are outside its scope. The act of @@ -163,7 +151,7 @@ on the Library (independent of the use of the Library in a tool for writing it). Whether that is true depends on what the Library does and what the program that uses the Library does. - + 1. You may copy and distribute verbatim copies of the Library's complete source code as you receive it, in any medium, provided that you conspicuously and appropriately publish on each copy an @@ -285,7 +273,7 @@ Any executables containing that work also fall under Section 6, whether or not they are linked directly with the Library itself. - 6. As an exception to the Sections above, you may also combine or + 6. As an exception to the Sections above, you may also compile or link a "work that uses the Library" with the Library to produce a work containing portions of the Library, and distribute that work under terms of your choice, provided that the terms permit @@ -312,31 +300,23 @@ Library will not necessarily be able to recompile the application to use the modified definitions.) - b) Use a suitable shared library mechanism for linking with the - Library. A suitable mechanism is one that (1) uses at run time a - copy of the library already present on the user's computer system, - rather than copying library functions into the executable, and (2) - will operate properly with a modified version of the library, if - the user installs one, as long as the modified version is - interface-compatible with the version that the work was made with. - - c) Accompany the work with a written offer, valid for at least - three years, to give the same user the materials specified in - Subsection 6a, above, for a charge no more than the cost of - performing this distribution. + b) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. - d) If distribution of the work is made by offering access to copy + c) If distribution of the work is made by offering access to copy from a designated place, offer equivalent access to copy the above specified materials from the same place. - e) Verify that the user has already received a copy of these + d) Verify that the user has already received a copy of these materials or that you have already sent this user a copy. For an executable, the required form of the "work that uses the Library" must include any data and utility programs needed for reproducing the executable from it. However, as a special exception, -the materials to be distributed need not include anything that is -normally distributed (in either source or binary form) with the major +the source code distributed need not include anything that is normally +distributed (in either source or binary form) with the major components (compiler, kernel, and so on) of the operating system on which the executable runs, unless that component itself accompanies the executable. @@ -385,7 +365,7 @@ original licensor to copy, distribute, link with or modify the Library subject to these terms and conditions. You may not impose any further restrictions on the recipients' exercise of the rights granted herein. -You are not responsible for enforcing compliance by third parties with +You are not responsible for enforcing compliance by third parties to this License. 11. If, as a consequence of a court judgment or allegation of patent @@ -401,10 +381,9 @@ the only way you could satisfy both it and this License would be to refrain entirely from distribution of the Library. -If any portion of this section is held invalid or unenforceable under -any particular circumstance, the balance of the section is intended to -apply, and the section as a whole is intended to apply in other -circumstances. +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. It is not the purpose of this section to induce you to infringe any patents or other property right claims or to contest validity of any @@ -422,14 +401,14 @@ 12. If the distribution and/or use of the Library is restricted in certain countries either by patents or by copyrighted interfaces, the -original copyright holder who places the Library under this License -may add an explicit geographical distribution limitation excluding those -countries, so that distribution is permitted only in or among -countries not thus excluded. In such case, this License incorporates -the limitation as if written in the body of this License. +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. 13. The Free Software Foundation may publish revised and/or new -versions of the Lesser General Public License from time to time. +versions of the Library General Public License from time to time. Such new versions will be similar in spirit to the present version, but may differ in detail to address new problems or concerns. @@ -450,7 +429,7 @@ of all derivatives of our free software and of promoting the sharing and reuse of software generally. - NO WARRANTY + NO WARRANTY 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. @@ -473,49 +452,46 @@ SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. - END OF TERMS AND CONDITIONS + END OF TERMS AND CONDITIONS How to Apply These Terms to Your New Libraries If you develop a new library, and you want it to be of the greatest possible use to the public, we recommend making it free software that everyone can redistribute and change. You can do so by permitting -redistribution under these terms (or, alternatively, under the terms -of the ordinary General Public License). - - To apply these terms, attach the following notices to the library. -It is safest to attach them to the start of each source file to most -effectively convey the exclusion of warranty; and each file should -have at least the "copyright" line and a pointer to where the full -notice is found. +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. <one line to give the library's name and a brief idea of what it does.> Copyright (C) <year> <name of author> This library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public + modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. + version 2 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. + Library General Public License for more details. - You should have received a copy of the GNU Lesser General Public - License along with this library; if not, write to the Free Software - Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + You should have received a copy of the GNU Library General Public + License along with this library; if not, write to the Free + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Also add information on how to contact you by electronic and paper mail. -You should also get your employer (if you work as a programmer) or -your school, if any, to sign a "copyright disclaimer" for the library, -if necessary. Here is a sample; alter the names: +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: Yoyodyne, Inc., hereby disclaims all copyright interest in the - library `Frob' (a library for tweaking knobs) written by James - Random Hacker. + library `Frob' (a library for tweaking knobs) written by James Random Hacker. <signature of Ty Coon>, 1 April 1990 Ty Coon, President of Vice diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/Makefile new/ocaml-ptmap-2.0.5/Makefile --- old/ocaml-ptmap-2.0.4/Makefile 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/Makefile 2020-09-04 13:21:59.000000000 +0200 @@ -1,21 +1,12 @@ -PREFIX_ARG := $(if $(PREFIX),--prefix $(PREFIX),) -LIBDIR_ARG := $(if $(LIBDIR),--libdir $(LIBDIR),) -DESTDIR_ARG := $(if $(DESTDIR),--destdir $(DESTDIR),) -INSTALL_ARGS := $(PREFIX_ARG) $(LIBDIR_ARG) $(DESTDIR_ARG) -DUNE_ARGS = -DUNE = dune -default: - $(DUNE) build @install $(DUNE_ARGS) - -doc: - $(DUNE) build @doc $(DUNE_ARGS) - -install: default - $(DUNE) install $(INSTALL_ARGS) $(DUNE_ARGS) +all: + dune build test: - $(DUNE) runtest $(DUNE_ARGS) + dune runtest + +doc: + dune build @doc clean: - $(DUNE) clean $(DUNE_ARGS) + dune clean diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/README.md new/ocaml-ptmap-2.0.5/README.md --- old/ocaml-ptmap-2.0.4/README.md 1970-01-01 01:00:00.000000000 +0100 +++ new/ocaml-ptmap-2.0.5/README.md 2020-09-04 13:21:59.000000000 +0200 @@ -0,0 +1,8 @@ +Integer map implementation using Patricia trees + +Follows "Fast Mergeable Integer Maps" by Chris Okasaki and Andrew Gill +(Workshop on ML, 1998) + +Note: In 2017, a bug was found in the paper above, which is described +in "QuickChecking Patricia Trees" by Jan Midtgaard. This is fixed in +the present OCaml code. diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/dune new/ocaml-ptmap-2.0.5/dune --- old/ocaml-ptmap-2.0.4/dune 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/dune 2020-09-04 13:21:59.000000000 +0200 @@ -1,19 +1,9 @@ (library (public_name ptmap) - (wrapped false) - (libraries seq) - (synopsis "Maps over integers implemented as Patricia trees") - (modules ptmap)) + (modules ptmap) + (libraries seq)) (test - (name inline_test) - (modules inline_test) - (libraries ptmap oUnit qcheck stdlib-shims)) - -(rule - (target inline_test.ml) - (deps ptmap.ml) - (action - (with-stdout-to - %{target} - (run qtest extract %{deps})))) + (name test) + (modules test) + (libraries stdlib-shims ptmap)) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/dune-project new/ocaml-ptmap-2.0.5/dune-project --- old/ocaml-ptmap-2.0.4/dune-project 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/dune-project 2020-09-04 13:21:59.000000000 +0200 @@ -1,19 +1,3 @@ -(lang dune 1.11) - -(generate_opam_files true) - -(license "LGPL-2.1-or-later WITH OCaml-LGPL-linking-exception") - -(authors "Jean-Christophe Filliatre <[email protected]>") - -(maintainers "Jean-Christophe Filliatre <[email protected]>") - -(homepage "https://www.lri.fr/~filliatr/software.en.html";) - -(bug_reports "https://github.com/backtracking/ptmap/issues";) - -(package - (name ptmap) - (synopsis "Maps over integers implemented as Patricia trees") - (description - "Jean-Christophe Filli\195\162tre's implementation of maps over integers implemented as Patricia trees.")) +(lang dune 2.0) +(name ptmap) +(formatting (enabled_for dune)) diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/ptmap.ml new/ocaml-ptmap-2.0.5/ptmap.ml --- old/ocaml-ptmap-2.0.4/ptmap.ml 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/ptmap.ml 2020-09-04 13:21:59.000000000 +0200 @@ -13,8 +13,6 @@ (* *) (**************************************************************************) -(*i $Id$ i*) - (*s Maps of integers implemented as Patricia trees, following Chris Okasaki and Andrew Gill's paper {\em Fast Mergeable Integer Maps} ({\tt\small http://www.cs.columbia.edu/\~{}cdo/papers.html\#ml98maps}). @@ -46,16 +44,19 @@ let find_opt k m = try Some (find k m) with Not_found -> None +(* Note: find_first/last have to look in both subtrees + as these are little-endian Patricia trees *) let rec find_first_opt f = function | Empty -> None | Leaf (j,x) -> if f j then Some (j,x) else None | Branch (_, _, l, r) -> match find_first_opt f l, find_first_opt f r with - | Some (lk,lv) , Some (rk,rv) -> if lk < rk then Some (lk,lv) else Some (rk,rv) + | Some (lk,lv) , Some (rk,rv) -> + if lk < rk then Some (lk,lv) else Some (rk,rv) | Some v, None | None, Some v -> Some v | None, None -> None -let rec find_first f = function +let find_first f = function | Empty -> raise Not_found | Leaf (j,x) -> if f j then (j,x) else raise Not_found | Branch (_, _, l, r) -> @@ -69,11 +70,12 @@ | Leaf (j,x) -> if f j then Some (j,x) else None | Branch (_, _, l, r) -> match find_last_opt f l, find_last_opt f r with - | Some (lk,lv) , Some (rk,rv) -> if lk > rk then Some (lk,lv) else Some (rk,rv) + | Some (lk,lv) , Some (rk,rv) -> + if lk > rk then Some (lk,lv) else Some (rk,rv) | Some v, None | None, Some v -> Some v | None, None -> None -let rec find_last f = function +let find_last f = function | Empty -> raise Not_found | Leaf (j,x) -> if f j then (j,x) else raise Not_found | Branch (_, _, l, r) -> @@ -136,22 +138,10 @@ in rmv t -(* utility fun for unit tests *) -(*$inject - let of_list l = - List.fold_left (fun acc (k, v) -> - add k v acc - ) empty l -*) - let rec cardinal = function | Empty -> 0 | Leaf _ -> 1 | Branch (_,_,t0,t1) -> cardinal t0 + cardinal t1 -(*$T cardinal - cardinal empty = 0 - cardinal (of_list [(-1,false); (5,true); (0,false)]) = 3 -*) let rec iter f = function | Empty -> () @@ -188,6 +178,11 @@ | Leaf (k, v) as t -> if pr k v then t else Empty | Branch (p,m,t0,t1) -> branch (p, m, filter pr t0, filter pr t1) +let rec filter_map pr = function + | Empty -> Empty + | Leaf (k, v) -> (match pr k v with Some v' -> Leaf (k, v') | None -> Empty) + | Branch (p,m,t0,t1) -> branch (p, m, filter_map pr t0, filter_map pr t1) + let partition p s = let rec part (t,f as acc) = function | Empty -> acc @@ -200,10 +195,6 @@ | Empty -> raise Not_found | Leaf (k, v) -> (k, v) | Branch (_, _, t0, _) -> choose t0 (* we know that [t0] is non-empty *) -(*$T choose - try let _ = choose empty in false with Not_found -> true - choose (add 1 true empty) = (1, true) -*) let rec choose_opt = function | Empty -> None @@ -225,20 +216,16 @@ let (ks, _) as bs = min_binding s in let (kt, _) as bt = min_binding t in if ks < kt then bs else bt -(*$T min_binding - (try let _ = min_binding empty in false with Not_found -> true) = true - min_binding (of_list [(-1,false); (5,true); (0,false)]) = (-1,false) -*) let rec min_binding_opt = function | Empty -> None | Leaf (k, v) -> Some (k, v) | Branch (_,_,s,t) -> match (min_binding_opt s, min_binding_opt t) with - | (None, None) -> None - | (None, bt) -> bt - | (bs, None) -> bs - | ((Some (ks, _) as bs), (Some (kt, _) as bt)) -> + | None, None -> None + | None, bt -> bt + | bs, None -> bs + | (Some (ks, _) as bs), (Some (kt, _) as bt) -> if ks < kt then bs else bt let rec max_binding = function @@ -248,29 +235,20 @@ let (ks, _) as bs = max_binding s in let (kt, _) as bt = max_binding t in if ks > kt then bs else bt -(*$T max_binding - (try let _ = max_binding empty in false with Not_found -> true) = true - max_binding (of_list [(-1,false); (5,true); (0,false)]) = (5,true) -*) let rec max_binding_opt = function | Empty -> None | Leaf (k, v) -> Some (k, v) | Branch (_,_,s,t) -> - match (max_binding_opt s, max_binding_opt t) with - | (None, None) -> None - | (None, bt) -> bt - | (bs, None) -> bs - | ((Some (ks, _) as bs), (Some (kt, _) as bt)) -> + match max_binding_opt s, max_binding_opt t with + | None, None -> None + | None, bt -> bt + | bs, None -> bs + | (Some (ks, _) as bs), (Some (kt, _) as bt) -> if ks > kt then bs else bt let bindings m = fold (fun k v acc -> (k, v) :: acc) m [] -(*$T bindings - bindings empty = [] - List.sort Stdlib.compare (bindings (of_list [(-1,false); (5,true); (0,false)])) = \ - [(-1,false); (0,false); (5,true)] -*) (* we order constructors as Empty < Leaf < Branch *) let compare cmp t1 t2 = @@ -312,49 +290,43 @@ (* then bindings in m2 that are not in m1 *) fold (fun k2 v2 m -> if mem k2 m1 then m else add m k2 (f k2 None (Some v2))) m2 m -(*$T merge - let l1 = [(-1,-1); (0,0); (5,4)] in \ - let l2 = [(5,5)] in \ - let l3 = [(-1,-1); (0,0); (5,5)] in \ - equal (=) (of_list l3) \ - (merge (fun _k x y -> max x y) (of_list l1) (of_list l2)) -*) - -let union f m1 m2 = - (* first, consider all bindings in m1 or in (m1 inter m2) *) - let m = - fold (fun k v m -> - match find_opt k m2 with - | None -> add k v m (* only in m1 *) - | Some w -> - begin (* in (m1 inter m2) *) - match f k v w with - | None -> m (* key is dropped *) - | Some z -> add k z m - end - ) m1 empty - in - (* last, consider all bindings only in m2 *) - fold (fun k v m -> - match find_opt k m1 with - | None -> add k v m (* only in m2 *) - | Some _ -> m (* already processed before *) - ) m2 m -(*$T union - let l1 = [(-1,false); (0,false); (5,true)] in \ - let l2 = [(0,true); (6,true)] in \ - let l3 = [(-1,false); (5,true); (6,true)] in \ - let m1 = of_list l1 in \ - let m2 = of_list l2 in \ - let m3 = of_list l3 in \ - equal (=) m3 (union (fun _ _ _ -> None) m1 m2) -*) let update x f m = match f (find_opt x m) with | None -> remove x m | Some z -> add x z m +let unsigned_lt n m = n >= 0 && (m < 0 || n < m) + +let rec union f = function + | Empty, t -> t + | t, Empty -> t + | Leaf (k,v1), t -> + update k (function None -> Some v1 | Some v2 -> f k v1 v2) t + | t, Leaf (k,v2) -> + update k (function None -> Some v2 | Some v1 -> f k v1 v2) t + | (Branch (p,m,s0,s1) as s), (Branch (q,n,t0,t1) as t) -> + if m == n && match_prefix q p m then + (* The trees have the same prefix. Merge the subtrees. *) + branch (p, m, union f (s0,t0), union f (s1,t1)) + else if unsigned_lt m n && match_prefix q p m then + (* [q] contains [p]. Merge [t] with a subtree of [s]. *) + if zero_bit q m then + branch (p, m, union f (s0,t), s1) + else + branch (p, m, s0, union f (s1,t)) + else if unsigned_lt n m && match_prefix p q n then + (* [p] contains [q]. Merge [s] with a subtree of [t]. *) + if zero_bit p n then + branch (q, n, union f (s,t0), t1) + else + branch (q, n, t0, union f (s,t1)) + else + (* The prefixes disagree. *) + join (p, s, q, t) + +let union f s t = union f (s,t) + let to_seq m = let rec prepend_seq m s = match m with | Empty -> s diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/ptmap.mli new/ocaml-ptmap-2.0.5/ptmap.mli --- old/ocaml-ptmap-2.0.4/ptmap.mli 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/ptmap.mli 2020-09-04 13:21:59.000000000 +0200 @@ -13,14 +13,98 @@ (* *) (**************************************************************************) -(*i $Id$ i*) +(** Maps over integers implemented as Patricia trees. -(*s Maps over integers implemented as Patricia trees. - The following signature is exactly [Map.S with type key = int], - with the same specifications. *) + The following signature is a subset of [Map.S with type key = int], + with the same specifications (not repeated here) unless specified + otherwise. -include Map.S with type key = int + These are little-endian Patricia trees, so there is no efficient + ordering of keys within the structure. Consequently, + - [min/max_binding], [find_first/last] are rather inefficient (linear) + - [iter], [fold] *do not* iterate in the key order + - [bindings] is *not sorted* by keys +*) -(*s Warning: [min_binding] and [max_binding] are linear w.r.t. the - size of the map. They are barely more efficient than a - straightforward implementation using [fold]. *) +type key = int + +type (+'a) t + +val empty: 'a t + +val is_empty: 'a t -> bool + +val mem: key -> 'a t -> bool + +val add: key -> 'a -> 'a t -> 'a t + +val update: key -> ('a option -> 'a option) -> 'a t -> 'a t + +val singleton: key -> 'a -> 'a t + +val remove: key -> 'a t -> 'a t + +val merge: + (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t + +val union: (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t + +val compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int + +val equal: ('a -> 'a -> bool) -> 'a t -> 'a t -> bool + +val iter: (key -> 'a -> unit) -> 'a t -> unit + +val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b + +val for_all: (key -> 'a -> bool) -> 'a t -> bool + +val exists: (key -> 'a -> bool) -> 'a t -> bool + +val filter: (key -> 'a -> bool) -> 'a t -> 'a t + +val filter_map: (key -> 'a -> 'b option) -> 'a t -> 'b t + +val partition: (key -> 'a -> bool) -> 'a t -> 'a t * 'a t + +val cardinal: 'a t -> int + +val bindings: 'a t -> (key * 'a) list + +val min_binding: 'a t -> (key * 'a) + +val min_binding_opt: 'a t -> (key * 'a) option + +val max_binding: 'a t -> (key * 'a) + +val max_binding_opt: 'a t -> (key * 'a) option + +val choose: 'a t -> (key * 'a) + +val choose_opt: 'a t -> (key * 'a) option + +val split: key -> 'a t -> 'a t * 'a option * 'a t + +val find: key -> 'a t -> 'a + +val find_opt: key -> 'a t -> 'a option + +val find_first: (key -> bool) -> 'a t -> key * 'a + +val find_first_opt: (key -> bool) -> 'a t -> (key * 'a) option + +val find_last: (key -> bool) -> 'a t -> key * 'a + +val find_last_opt: (key -> bool) -> 'a t -> (key * 'a) option + +val map: ('a -> 'b) -> 'a t -> 'b t + +val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t + +val to_seq : 'a t -> (key * 'a) Seq.t + +val to_seq_from : key -> 'a t -> (key * 'a) Seq.t + +val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t + +val of_seq : (key * 'a) Seq.t -> 'a t diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/ptmap.opam new/ocaml-ptmap-2.0.5/ptmap.opam --- old/ocaml-ptmap-2.0.4/ptmap.opam 1970-01-01 01:00:00.000000000 +0100 +++ new/ocaml-ptmap-2.0.5/ptmap.opam 2020-09-04 13:21:59.000000000 +0200 @@ -0,0 +1,22 @@ +opam-version: "2.0" +maintainer: "[email protected]" +authors: "Jean-Christophe Filliâtre" +synopsis: "Maps of integers implemented as Patricia trees" +description: "An implementation inspired by Okasaki & Gill's paper +'Fast Mergeable Integer Maps'" +license: "LGPL-2.1" +homepage: "https://github.com/backtracking/ptmap"; +doc: "https://backtracking.github.io/ptmap"; +bug-reports: "https://github.com/backtracking/ptmap/issues"; +depends: [ + "ocaml" + "stdlib-shims" + "seq" + "dune" {>= "2.0.0"} +] +build: [ + ["dune" "subst"] {pinned} + ["dune" "build" "-p" name "-j" jobs] + ["dune" "runtest" "-p" name] {with-test} +] +dev-repo: "git+https://github.com/backtracking/ptmap.git"; diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn' '--exclude=.svnignore' old/ocaml-ptmap-2.0.4/test.ml new/ocaml-ptmap-2.0.5/test.ml --- old/ocaml-ptmap-2.0.4/test.ml 2019-10-21 09:05:41.000000000 +0200 +++ new/ocaml-ptmap-2.0.5/test.ml 2020-09-04 13:21:59.000000000 +0200 @@ -1,13 +1,19 @@ -let rec int_pow a = function - | 0 -> 1 - | 1 -> a - | n -> - let b = int_pow a (n / 2) in - b * b * (if n mod 2 = 0 then 1 else a) -let max_int = (int_pow 2 30) -1 +open Ptmap -let test empty add mem = +let of_list l = + List.fold_left (fun acc (k, v) -> add k v acc) empty l + +let list_to_map lst = + let rec loop l map = match l with + | [] -> map + | item :: ls -> loop ls (add item true map) + in + loop lst empty + +(* basic add/mem test *) +let () = + let max_int = 1 lsl 30 - 1 in let seed = Random.int max_int in Random.init seed; let s = @@ -17,89 +23,141 @@ loop empty 0 in Random.init seed; - for i = 0 to 999 do assert (mem (Random.int max_int) s) done + for _i = 0 to 999 do assert (mem (Random.int max_int) s) done -let list_to_map lst = - let rec loop l map = match l with - | [] -> map - | item :: ls -> loop ls (Ptmap.add item true map) - in - loop lst Ptmap.empty - -let test_find_first = - let k,v = Ptmap.find_first (fun i -> i > 3) (list_to_map [3; 1; 2; 4; 6; 5]) in +(* the bug from "QuickChecking Patricia Trees" is fixed *) +let () = + let m1 = add min_int true (add 0 true empty) in + let m2 = add min_int true (add 1 true empty) in + let m = union (fun _ _ _ -> Some true) m1 m2 in + assert (cardinal m = 3) + +let interval lo hi = + let rec build k m = if k > hi then m else build (k+1) (add k true m) in + build lo empty + +(* cardinal *) +let () = + assert (cardinal empty = 0); + assert (cardinal (of_list [(-1,false); (5,true); (0,false)]) = 3); + assert (cardinal (interval (-10) 10) = 21) + +(* choose *) +let () = + assert (try let _ = choose empty in false with Not_found -> true); + assert (choose (add 1 true empty) = (1, true)) + +(* min/max_binding *) +let () = + assert (try let _ = min_binding empty in false with Not_found -> true); + assert (min_binding (of_list [(-1,false); (5,true); (0,false)]) = (-1,false)); + assert (try let _ = max_binding empty in false with Not_found -> true); + assert (max_binding (of_list [(-1,false); (5,true); (0,false)]) = (5,true)) + +(* bindings *) +let () = + assert (bindings empty = []); + let l = bindings (of_list [(-1,false); (5,true); (0,false)]) in + assert (List.sort Stdlib.compare l = [(-1,false); (0,false); (5,true)]); + let itv = bindings (interval (-10) 10) in + assert (List.length itv = 21) + +(* merge *) +let () = + let l1 = [(-1,-1); (0,0); (5,4)] in + let l2 = [(5,5)] in + let l3 = [(-1,-1); (0,0); (5,5)] in + assert (equal (=) (of_list l3) + (merge (fun _k x y -> max x y) (of_list l1) (of_list l2))) + +(* union *) +let () = + let l1 = [(-1,false); (0,false); (5,true)] in + let l2 = [(0,true); (6,true)] in + let l3 = [(-1,false); (5,true); (6,true)] in + let m1 = of_list l1 in + let m2 = of_list l2 in + let m3 = of_list l3 in + assert (equal (=) m3 (union (fun _ _ _ -> None) m1 m2)) + +(* find_first *) +let () = + let k,_ = find_first (fun i -> i > 3) (list_to_map [3; 1; 2; 4; 6; 5]) in assert (k = 4) -let test_find_first_opt = - match Ptmap.find_first_opt (fun i -> i > 3) (list_to_map [3; 1; 2; 4; 6; 5]) with - | Some (4, v) -> assert true +(* find_first_opt *) +let () = + assert (find_first_opt (fun _ -> true) empty = None); + match find_first_opt (fun i -> i > 3) (list_to_map [3; 1; 2; 4; 6; 5]) with + | Some (4, _) -> assert true | _ -> assert false -let test_find_last = - let k,v = Ptmap.find_last (fun i -> i < 4) (list_to_map [3; 1; 2; 4; 6; 5]) in +(* find_last *) +let () = + let k,_ = find_last (fun i -> i < 4) (list_to_map [3; 1; 2; 4; 6; 5]) in assert (k = 3) -let test_find_last_opt = - match Ptmap.find_last_opt (fun i -> i < 4) (list_to_map [3; 1; 2; 4; 6; 5]) with - | Some (3, v) -> assert true +(* find_last_opt *) +let () = + assert (find_last_opt (fun _ -> true) empty = None); + match find_last_opt (fun i -> i < 4) (list_to_map [3; 1; 2; 4; 6; 5]) with + | Some (3, _) -> assert true | _ -> assert false -let test_update_remove = - let m = Ptmap.update 2 (fun _ -> None) (list_to_map [3; 1; 2; 4; 6; 5]) in - match Ptmap.find_opt 2 m with +(* update_remove *) +let () = + let m = update 2 (fun _ -> None) (list_to_map [3; 1; 2; 4; 6; 5]) in + match find_opt 2 m with | None -> assert true | _ -> assert false -let test_update_add = - let m = Ptmap.update 2 (fun _ -> Some true) (list_to_map [3; 1; 4; 6; 5]) in - match Ptmap.find_opt 2 m with +(* update_add *) +let () = + let m = update 2 (fun _ -> Some true) (list_to_map [3; 1; 4; 6; 5]) in + match find_opt 2 m with | Some true -> assert true | _ -> assert true -let test_update_update = - let m = Ptmap.update 2 (fun _ -> Some false) (list_to_map [3; 1; 2; 4; 6; 5]) in - match Ptmap.find_opt 2 m with +(* update_update *) +let () = + let m = update 2 (fun _ -> Some false) (list_to_map [3; 1; 2; 4; 6; 5]) in + match find_opt 2 m with | Some false -> assert true | _ -> assert true -let test_to_seq = +let list_of_seq s = Seq.fold_left (fun l b -> b :: l) [] s +let list_to_seq l = + let rec aux l () = match l with + | [] -> Seq.Nil | x :: tail -> Seq.Cons (x, aux tail) in + aux l + +(* to_seq *) +let () = let o = [3; 1; 2; 4; 6; 5] in - let l = List.of_seq (Ptmap.to_seq (list_to_map o)) in + let l = list_of_seq (to_seq (list_to_map o)) in assert (List.length l = List.length o); - assert (List.for_all (fun (k,v) -> List.exists (fun ok -> ok = k) o) l) + assert (List.for_all (fun (k,_) -> List.exists ((=) k) o) l) -let test_to_seq_from = +(* to_seq_from *) +let () = let o = [3; 1; 2; 4; 6; 5] in let r = [3; 4; 5; 6] in - let l = List.of_seq (Ptmap.to_seq_from 3 (list_to_map o)) in + let l = list_of_seq (to_seq_from 3 (list_to_map o)) in assert (List.length l = List.length r); - assert (List.for_all (fun (k,v) -> List.exists (fun ok -> ok = k) r) l) + assert (List.for_all (fun (k,_) -> List.exists ((=) k) r) l) -let test_of_seq = +(* of_seq *) +let () = let o = [3; 1; 2; 4; 6; 5] in - let m = Ptmap.of_seq (List.to_seq (List.map (fun v -> (v, true)) o)) in - assert (Ptmap.cardinal m = List.length o); - assert (Ptmap.for_all (fun k v -> List.exists (fun ok -> ok = k) o) m) + let m = of_seq (list_to_seq (List.map (fun v -> (v, true)) o)) in + assert (cardinal m = List.length o); + assert (for_all (fun k _ -> List.exists ((=) k) o) m) -let test_add_seq = +(* add_seq *) +let () = let o = [3; 1; 6; 5] in let a = [2; 4] in let r = [3; 1; 2; 4; 6; 5] in - let m = Ptmap.add_seq (List.to_seq (List.map (fun v -> (v, true)) a)) (list_to_map o) in - assert (Ptmap.cardinal m = List.length r); - assert (Ptmap.for_all (fun k v -> List.exists (fun ok -> ok = k) r) m) - -let main () = - test Ptmap.empty Ptmap.add Ptmap.mem; - test_find_first; - test_find_first_opt; - test_find_last; - test_find_last_opt; - test_update_remove; - test_update_add; - test_update_update; - test_to_seq; - test_to_seq_from; - test_of_seq - -let () = main () + let m = add_seq (list_to_seq (List.map (fun v -> (v, true)) a)) (list_to_map o) in + assert (cardinal m = List.length r); + assert (for_all (fun k _ -> List.exists ((=) k) r) m)
