@@ -1,116 +0,0 @@
-#
-# $Id: Binary.pm,v 1.5 1998/12/15 20:55:08 rantapaa Exp $
-#
-# Seach::Binary
-
-package Search::Binary;
-
-=head1 NAME
-
-Search::Binary -- generic binary search
-
-=head1 SYNOPSIS
-
- use Seach::Binary;
- $pos = binary_search($min, $max, $val, $read, $handle, [$size]);
-
-=head1 DESCRIPTION
-
-C<binary_search> implements a generic binary search algorithm returning the
-I<position> of the first I<record> whose I<index value> is greater than or
-equal to C<$val>. The search routine does not define any of the terms
-I<position>, I<record> or I<index value>, but leaves their interpretation
-and implementation to the user supplied function C<&$read()>. The only
-restriction is that positions must be integer scalars.
-
-During the search the read function will be called with three arguments:
-the input parameters C<$handle> and C<$val>, and a position. If the position
-is not C<undef>, the read function should read the first whole record starting
-at or after the position; otherwise, the read function should read the record
-immediately following the last record it read. The search algorithm will
-guarantee that the first call to the read function will not be with a position
-of C<undef>. The read function needs to return a two element array consisting
-of the result of comparing C<$val> with the index value of the read record and
-the position of the read record. The comparison value must be positive if
-C<$val> is strictly greater than the index value of the read record, C<0>
-if equal, and negative if strictly less. Furthermore, the returned position
-value must be greater than or equal to the position the read function was
-called with.
-
-The input parameters C<$min> and C<$max> are positions and represents the
-extent of the search. Only records which begin at positions within this range
-(inclusive) will be searched. Moreover, C<$min> must be the starting position
-of a record. If present C<$size> is a difference between positions and
-determines when the algorithms switches to a sequential search. C<$val> is
-an index value. The value of C<$handle> is of no consequence to the binary
-search algorithm; it is merely passed as a convenience to the read function.
-
-=head1 COPYRIGHT
-
- Copyright 1998, Erik Rantapaa
-
-This library is free software; you can redistribute it and/or
-modify it under the same terms as Perl itself.
-
-=cut
-
-# use strict;
-require Exporter;
-@ISA = qw(Exporter);
-@EXPORT = qw(binary_search);
-
-$VERSION = "0.95";
-
-sub binary_search {
- my $posmin = shift;
- my $posmax = shift;
- my $target = shift;
- my $readfn = shift;
- my $handle = shift;
- my $smallblock = shift || 512;
-
- my ($x, $compare, $mid, $lastmid);
- my ($seeks, $reads);
-
- # assert $posmin <= $posmax
-
- $seeks = $reads = 0;
- $lastmid = int(($posmin + $posmax)/2)-1;
- while ($posmax - $posmin > $smallblock) {
-
- # assert: $posmin is the beginning of a record
- # and $target >= index value for that record
-
- $seeks++;
- $x = int(($posmin + $posmax)/2);
- ($compare, $mid) = &$readfn($handle, $target, $x);
-
- unless (defined($compare)) {
- $posmax = $mid;
- next;
- }
- last if ($mid == $lastmid);
- if ($compare > 0) {
- $posmin = $mid;
- } else {
- $posmax = $mid;
- }
- $lastmid = $mid;
- }
-
- # Switch to sequential search.
-
- $x = $posmin;
- while ($posmin <= $posmax) {
-
- # same loop invarient as above applies here
-
- $reads++;
- ($compare, $posmin) = &$readfn($handle, $target, $x);
- last unless (defined($compare) && $compare > 0);
- $x = undef;
- }
- wantarray ? ($posmin, $seeks, $reads) : $posmin;
-}
-
-1;
@@ -1,4 +0,0 @@
-
-Tue Dec 15 1998
-
- Initial public release
@@ -0,0 +1,29 @@
+0.99 2014-09-30 XAERXESS
+
+ - Added LICENSE file to MANIFEST (it was missing in 0.98 tarball)
+ - Cleaned up README
+
+0.98 2014-09-30 XAERXESS
+
+ - Removed undocumented behavior when binary_search was invoked in list
+ context (RT #58234)
+ - Added LICENSE file
+ - Mentioned List::BinarySearch::XS and removed TODO
+
+0.97 2014-09-30 XAERXESS
+
+ - Grzegorz Rożniecki (XAERXESS) has taken over maintenance
+ - Added deprecation notice and suggested using List::BinarySearch
+ - Changed default $size param value to 0 (RT #58233)
+ (previously it defaulted to 512 and caused sequential search)
+ - Fixed possible integer overflow (RT #19862)
+ - Fixed typo in documentation (RT #58143)
+ - Added tests for maintaining compatibility with List::BinarySearch
+ - Updated revision history in Changes (as per CPAN::Changes::Spec)
+ - Cleaned up documentation
+ - Moved Binary.pm to lib/Search/Binary.pm
+ - Tweaked Makefile.PL
+
+0.95 1998-12-15
+
+ - Initial public release
@@ -0,0 +1,379 @@
+This software is copyright (c) 1998 by Erik Rantapaa.
+
+This is free software; you can redistribute it and/or modify it under
+the same terms as the Perl 5 programming language system itself.
+
+Terms of the Perl programming language system itself
+
+a) the GNU General Public License as published by the Free
+ Software Foundation; either version 1, or (at your option) any
+ later version, or
+b) the "Artistic License"
+
+--- The GNU General Public License, Version 1, February 1989 ---
+
+This software is Copyright (c) 1998 by Erik Rantapaa.
+
+This is free software, licensed under:
+
+ The GNU General Public License, Version 1, February 1989
+
+ GNU GENERAL PUBLIC LICENSE
+ Version 1, February 1989
+
+ Copyright (C) 1989 Free Software Foundation, Inc.
+ 51 Franklin St, Suite 500, Boston, MA 02110-1335 USA
+
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+ Preamble
+
+ The license agreements of most software companies try to keep users
+at the mercy of those companies. By contrast, our General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users. The
+General Public License applies to the Free Software Foundation's
+software and to any other program whose authors commit to using it.
+You can use it for your programs, too.
+
+ When we speak of free software, we are referring to freedom, not
+price. Specifically, the General Public License is designed to make
+sure that you have the freedom to give away or sell copies of free
+software, 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
+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 software, or if you modify it.
+
+ For example, if you distribute copies of a such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have. You must make sure that they, too, receive or can get the
+source code. And you must tell them their rights.
+
+ We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+ Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software. If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+ The precise terms and conditions for copying, distribution and
+modification follow.
+
+ GNU GENERAL PUBLIC LICENSE
+ TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+ 0. This License Agreement applies to any program or other work which
+contains a notice placed by the copyright holder saying it may be
+distributed under the terms of this General Public License. The
+"Program", below, refers to any such program or work, and a "work based
+on the Program" means either the Program or any work containing the
+Program or a portion of it, either verbatim or with modifications. Each
+licensee is addressed as "you".
+
+ 1. You may copy and distribute verbatim copies of the Program's source
+code as you receive it, in any medium, provided that you conspicuously and
+appropriately publish on each copy an appropriate copyright notice and
+disclaimer of warranty; keep intact all the notices that refer to this
+General Public License and to the absence of any warranty; and give any
+other recipients of the Program a copy of this General Public License
+along with the Program. You may charge a fee for the physical act of
+transferring a copy.
+
+ 2. You may modify your copy or copies of the Program or any portion of
+it, and copy and distribute such modifications under the terms of Paragraph
+1 above, provided that you also do the following:
+
+ a) cause the modified files to carry prominent notices stating that
+ you changed the files and the date of any change; and
+
+ b) cause the whole of any work that you distribute or publish, that
+ in whole or in part contains the Program or any part thereof, either
+ with or without modifications, to be licensed at no charge to all
+ third parties under the terms of this General Public License (except
+ that you may choose to grant warranty protection to some or all
+ third parties, at your option).
+
+ c) If the modified program normally reads commands interactively when
+ run, you must cause it, when started running for such interactive use
+ in the simplest and most usual way, to print or display an
+ announcement including an appropriate copyright notice and a notice
+ that there is no warranty (or else, saying that you provide a
+ warranty) and that users may redistribute the program under these
+ conditions, and telling the user how to view a copy of this General
+ Public License.
+
+ d) You may charge a fee for the physical act of transferring a
+ copy, and you may at your option offer warranty protection in
+ exchange for a fee.
+
+Mere aggregation of another independent work with the Program (or its
+derivative) on a volume of a storage or distribution medium does not bring
+the other work under the scope of these terms.
+
+ 3. You may copy and distribute the Program (or a portion or derivative of
+it, under Paragraph 2) in object code or executable form under the terms of
+Paragraphs 1 and 2 above provided that you also do one of the following:
+
+ a) accompany it with the complete corresponding machine-readable
+ source code, which must be distributed under the terms of
+ Paragraphs 1 and 2 above; or,
+
+ b) accompany it with a written offer, valid for at least three
+ years, to give any third party free (except for a nominal charge
+ for the cost of distribution) a complete machine-readable copy of the
+ corresponding source code, to be distributed under the terms of
+ Paragraphs 1 and 2 above; or,
+
+ c) accompany it with the information you received as to where the
+ corresponding source code may be obtained. (This alternative is
+ allowed only for noncommercial distribution and only if you
+ received the program in object code or executable form alone.)
+
+Source code for a work means the preferred form of the work for making
+modifications to it. For an executable file, complete source code means
+all the source code for all modules it contains; but, as a special
+exception, it need not include source code for modules which are standard
+libraries that accompany the operating system on which the executable
+file runs, or for standard header files or definitions files that
+accompany that operating system.
+
+ 4. You may not copy, modify, sublicense, distribute or transfer the
+Program except as expressly provided under this General Public License.
+Any attempt otherwise to copy, modify, sublicense, distribute or transfer
+the Program is void, and will automatically terminate your rights to use
+the Program under this License. However, parties who have received
+copies, or rights to use copies, from you under this General Public
+License will not have their licenses terminated so long as such parties
+remain in full compliance.
+
+ 5. By copying, distributing or modifying the Program (or any work based
+on the Program) you indicate your acceptance of this license to do so,
+and all its terms and conditions.
+
+ 6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the original
+licensor to copy, distribute or modify the Program subject to these
+terms and conditions. You may not impose any further restrictions on the
+recipients' exercise of the rights granted herein.
+
+ 7. The Free Software Foundation may publish revised and/or new versions
+of the 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.
+
+Each version is given a distinguishing version number. If the Program
+specifies a version number of the license which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation. If the Program does not specify a version number of
+the license, you may choose any version ever published by the Free Software
+Foundation.
+
+ 8. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission. For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this. Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+
+ NO WARRANTY
+
+ 9. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN
+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS
+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE
+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
+REPAIR OR CORRECTION.
+
+ 10. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGES.
+
+ END OF TERMS AND CONDITIONS
+
+ Appendix: How to Apply These Terms to Your New Programs
+
+ If you develop a new program, and you want it to be of the greatest
+possible use to humanity, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these
+terms.
+
+ To do so, attach the following notices to the program. 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 program's name and a brief idea of what it does.>
+ Copyright (C) 19yy <name of author>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 1, or (at your option)
+ any later version.
+
+ This program 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 General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA
+
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+ Gnomovision version 69, Copyright (C) 19xx name of author
+ Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+ This is free software, and you are welcome to redistribute it
+ under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the
+appropriate parts of the General Public License. Of course, the
+commands you use may be called something other than `show w' and `show
+c'; they could even be mouse-clicks or menu items--whatever suits your
+program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary. Here a sample; alter the names:
+
+ Yoyodyne, Inc., hereby disclaims all copyright interest in the
+ program `Gnomovision' (a program to direct compilers to make passes
+ at assemblers) written by James Hacker.
+
+ <signature of Ty Coon>, 1 April 1989
+ Ty Coon, President of Vice
+
+That's all there is to it!
+
+
+--- The Artistic License 1.0 ---
+
+This software is Copyright (c) 1998 by Erik Rantapaa.
+
+This is free software, licensed under:
+
+ The Artistic License 1.0
+
+The Artistic License
+
+Preamble
+
+The intent of this document is to state the conditions under which a Package
+may be copied, such that the Copyright Holder maintains some semblance of
+artistic control over the development of the package, while giving the users of
+the package the right to use and distribute the Package in a more-or-less
+customary fashion, plus the right to make reasonable modifications.
+
+Definitions:
+
+ - "Package" refers to the collection of files distributed by the Copyright
+ Holder, and derivatives of that collection of files created through
+ textual modification.
+ - "Standard Version" refers to such a Package if it has not been modified,
+ or has been modified in accordance with the wishes of the Copyright
+ Holder.
+ - "Copyright Holder" is whoever is named in the copyright or copyrights for
+ the package.
+ - "You" is you, if you're thinking about copying or distributing this Package.
+ - "Reasonable copying fee" is whatever you can justify on the basis of media
+ cost, duplication charges, time of people involved, and so on. (You will
+ not be required to justify it to the Copyright Holder, but only to the
+ computing community at large as a market that must bear the fee.)
+ - "Freely Available" means that no fee is charged for the item itself, though
+ there may be fees involved in handling the item. It also means that
+ recipients of the item may redistribute it under the same conditions they
+ received it.
+
+1. You may make and give away verbatim copies of the source form of the
+Standard Version of this Package without restriction, provided that you
+duplicate all of the original copyright notices and associated disclaimers.
+
+2. You may apply bug fixes, portability fixes and other modifications derived
+from the Public Domain or from the Copyright Holder. A Package modified in such
+a way shall still be considered the Standard Version.
+
+3. You may otherwise modify your copy of this Package in any way, provided that
+you insert a prominent notice in each changed file stating how and when you
+changed that file, and provided that you do at least ONE of the following:
+
+ a) place your modifications in the Public Domain or otherwise make them
+ Freely Available, such as by posting said modifications to Usenet or an
+ equivalent medium, or placing the modifications on a major archive site
+ such as ftp.uu.net, or by allowing the Copyright Holder to include your
+ modifications in the Standard Version of the Package.
+
+ b) use the modified Package only within your corporation or organization.
+
+ c) rename any non-standard executables so the names do not conflict with
+ standard executables, which must also be provided, and provide a separate
+ manual page for each non-standard executable that clearly documents how it
+ differs from the Standard Version.
+
+ d) make other distribution arrangements with the Copyright Holder.
+
+4. You may distribute the programs of this Package in object code or executable
+form, provided that you do at least ONE of the following:
+
+ a) distribute a Standard Version of the executables and library files,
+ together with instructions (in the manual page or equivalent) on where to
+ get the Standard Version.
+
+ b) accompany the distribution with the machine-readable source of the Package
+ with your modifications.
+
+ c) accompany any non-standard executables with their corresponding Standard
+ Version executables, giving the non-standard executables non-standard
+ names, and clearly documenting the differences in manual pages (or
+ equivalent), together with instructions on where to get the Standard
+ Version.
+
+ d) make other distribution arrangements with the Copyright Holder.
+
+5. You may charge a reasonable copying fee for any distribution of this
+Package. You may charge any fee you choose for support of this Package. You
+may not charge a fee for this Package itself. However, you may distribute this
+Package in aggregate with other (possibly commercial) programs as part of a
+larger (possibly commercial) software distribution provided that you do not
+advertise this Package as a product of your own.
+
+6. The scripts and library files supplied as input to or produced as output
+from the programs of this Package do not automatically fall under the copyright
+of this Package, but belong to whomever generated them, and may be sold
+commercially, and may be aggregated with this Package.
+
+7. C or perl subroutines supplied by you and linked into this Package shall not
+be considered part of this Package.
+
+8. The name of the Copyright Holder may not be used to endorse or promote
+products derived from this software without specific prior written permission.
+
+9. THIS PACKAGE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED
+WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+
+The End
+
@@ -1,5 +1,15 @@
+Changes
+LICENSE
MANIFEST
-README
-ChangeLog
-Binary.pm
Makefile.PL
+README
+lib/Search/Binary.pm
+t/00-load.t
+t/01-kwalitee.t
+t/02-changes.t
+t/10-basic.t
+t/11-lbs-compat.t
+t/12-rt52326.t
+t/lib/Search/Binary/TestUtils.pm
+META.yml Module YAML meta-data (added by MakeMaker)
+META.json Module JSON meta-data (added by MakeMaker)
@@ -0,0 +1,63 @@
+{
+ "abstract" : "generic binary search (DEPRECATED)",
+ "author" : [
+ "Erik Rantapaa <rantapaa@uswest.net>"
+ ],
+ "dynamic_config" : 1,
+ "generated_by" : "ExtUtils::MakeMaker version 6.92, CPAN::Meta::Converter version 2.140640",
+ "license" : [
+ "perl_5"
+ ],
+ "meta-spec" : {
+ "url" : "http://search.cpan.org/perldoc?CPAN::Meta::Spec",
+ "version" : "2"
+ },
+ "name" : "Search-Binary",
+ "no_index" : {
+ "directory" : [
+ "t",
+ "inc"
+ ]
+ },
+ "prereqs" : {
+ "build" : {
+ "requires" : {
+ "ExtUtils::MakeMaker" : "0"
+ }
+ },
+ "configure" : {
+ "requires" : {
+ "ExtUtils::MakeMaker" : "0"
+ }
+ },
+ "runtime" : {
+ "requires" : {
+ "Carp" : "0",
+ "Exporter" : "0",
+ "lib" : "0",
+ "parent" : "0",
+ "perl" : "5.006000",
+ "strict" : "0",
+ "warnings" : "0"
+ }
+ },
+ "test" : {
+ "requires" : {
+ "Test::More" : "0.96",
+ "Test::Warnings" : "0.012"
+ }
+ }
+ },
+ "release_status" : "stable",
+ "resources" : {
+ "bugtracker" : {
+ "web" : "https://rt.cpan.org/Dist/Display.html?Name=Search-Binary"
+ },
+ "repository" : {
+ "type" : "git",
+ "url" : "git://github.com/Xaerxess/Search-Binary.git",
+ "web" : "https://github.com/Xaerxess/Search-Binary"
+ }
+ },
+ "version" : "0.99"
+}
@@ -0,0 +1,33 @@
+---
+abstract: 'generic binary search (DEPRECATED)'
+author:
+ - 'Erik Rantapaa <rantapaa@uswest.net>'
+build_requires:
+ ExtUtils::MakeMaker: '0'
+ Test::More: '0.96'
+ Test::Warnings: '0.012'
+configure_requires:
+ ExtUtils::MakeMaker: '0'
+dynamic_config: 1
+generated_by: 'ExtUtils::MakeMaker version 6.92, CPAN::Meta::Converter version 2.140640'
+license: perl
+meta-spec:
+ url: http://module-build.sourceforge.net/META-spec-v1.4.html
+ version: '1.4'
+name: Search-Binary
+no_index:
+ directory:
+ - t
+ - inc
+requires:
+ Carp: '0'
+ Exporter: '0'
+ lib: '0'
+ parent: '0'
+ perl: '5.006000'
+ strict: '0'
+ warnings: '0'
+resources:
+ bugtracker: https://rt.cpan.org/Dist/Display.html?Name=Search-Binary
+ repository: git://github.com/Xaerxess/Search-Binary.git
+version: '0.99'
@@ -1,14 +1,61 @@
-#
-# $Id: Makefile.PL,v 1.1 1998/12/01 08:36:23 rantapaa Exp $
-#
-
+use strict;
+use warnings;
use ExtUtils::MakeMaker;
-require 5.002 ;
+my %WriteMakefileArgs = (
+ NAME => 'Search::Binary',
+ VERSION_FROM => 'lib/Search/Binary.pm',
+ MIN_PERL_VERSION => '5.6.0',
+ PREREQ_PM => {
+ 'Carp' => 0,
+ 'Exporter' => 0,
+ 'lib' => 0,
+ 'parent' => 0,
+ 'strict' => 0,
+ 'warnings' => 0,
+ },
+ TEST_REQUIRES => {
+ 'Test::More' => 0.96,
+ 'Test::Warnings' => 0.012,
+ },
+ ABSTRACT_FROM => 'lib/Search/Binary.pm',
+ AUTHOR => 'Erik Rantapaa <rantapaa@uswest.net>',
+ LICENSE => 'perl_5',
+ META_MERGE => {
+ 'meta-spec' => { version => 2 },
+ resources => {
+ repository => {
+ type => 'git',
+ url => 'git://github.com/Xaerxess/Search-Binary.git',
+ web => 'https://github.com/Xaerxess/Search-Binary',
+ },
+ bugtracker => {
+ web => 'https://rt.cpan.org/Dist/Display.html?Name=Search-Binary',
+ },
+ },
+ },
+ test => {
+ TESTS => "t/*.t"
+ },
+);
+
+unless (eval { ExtUtils::MakeMaker->VERSION(6.64) }) {
+ my $test_requires = delete $WriteMakefileArgs{TEST_REQUIRES};
+ if (eval { ExtUtils::MakeMaker->VERSION(6.5503) }) {
+ $WriteMakefileArgs{BUILD_REQUIRES} = $test_requires;
+ }
+}
+
+unless (eval { ExtUtils::MakeMaker->VERSION(6.48) }) {
+ delete $WriteMakefileArgs{MIN_PERL_VERSION};
+}
+
+unless (eval { ExtUtils::MakeMaker->VERSION(6.46) }) {
+ delete $WriteMakefileArgs{META_MERGE};
+}
+
+unless (eval { ExtUtils::MakeMaker->VERSION(6.31) }) {
+ delete $WriteMakefileArgs{LICENSE};
+}
-WriteMakefile(
- NAME => 'Search::Binary',
- VERSION_FROM => 'Binary.pm',
- 'linkext' => {LINKTYPE => ''},
- 'dist' => {COMPRESS=>'gzip', SUFFIX=>'gz'},
- ) ;
+WriteMakefile(%WriteMakefileArgs);
@@ -1,15 +1,47 @@
+Search-Binary
+=============
This module implements a generic binary search algorithm.
-You install the module by running these commands:
+INSTALLATION
+------------
+
+To install the module from CPAN, use
+
+ cpan Search::Binary
+
+If you have the App::cpanminus installer, you may prefer
+
+ cpanm Search::Binary
+
+To install this module from tarball archive file containing this distribution,
+type
perl Makefile.PL
make
+ make test
make install
-Please report any bugs/suggestions to Erik Rantapaa <rantapaa@uswest.net>
+DOCUMENTATION
+-------------
+
+You can read the documentation for the module online at the following websites:
+
+ * http://search.cpan.org/perldoc?Search::Binary
+ * http://metacpan.org/release/Search::Binary
+
+After installing the module, you can read the documentation on your computer
+using
+
+ perldoc Search::Binary
+
+COPYRIGHT AND LICENSE
+---------------------
Copyright 1998 Erik Rantapaa. All rights reserved.
This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.
+
+The full text of the license can be found in the LICENSE file included with
+this module.
@@ -0,0 +1,160 @@
+package Search::Binary;
+
+use strict;
+use warnings;
+use Carp;
+use parent 'Exporter';
+our @EXPORT = qw(binary_search);
+
+our $VERSION = '0.99';
+
+sub binary_search {
+ my ($posmin, $posmax, $target, $readfn, $handle, $smallblock) = @_;
+ $smallblock ||= 0;
+ if ($posmin > $posmax) {
+ carp 'First argument must be less then or equal to second argument'
+ . " (min: $posmin, max: $posmax)";
+ return 0; # some libraries rely on this behavior
+ }
+
+ my ($x, $compare, $mid);
+
+ # assert $posmin <= $posmax
+
+ my $lastmid = int($posmin + (($posmax - $posmin) / 2)) - 1;
+ while ($posmax - $posmin > $smallblock) {
+
+ # assert: $posmin is the beginning of a record
+ # and $target >= index value for that record
+
+ $x = int($posmin + (($posmax - $posmin) / 2));
+ ($compare, $mid) = $readfn->($handle, $target, $x);
+
+ unless (defined($compare)) {
+ $posmax = $mid;
+ next;
+ }
+ last if ($mid == $lastmid);
+ if ($compare > 0) {
+ $posmin = $mid;
+ } else {
+ $posmax = $mid;
+ }
+ $lastmid = $mid;
+ }
+
+ # Switch to sequential search.
+
+ $x = $posmin;
+ while ($posmin <= $posmax) {
+
+ # same loop invarient as above applies here
+
+ ($compare, $posmin) = $readfn->($handle, $target, $x);
+ last unless (defined($compare) && $compare > 0);
+ $x = undef;
+ }
+ return $posmin;
+}
+
+1;
+__END__
+
+=head1 NAME
+
+Search::Binary - generic binary search (DEPRECATED)
+
+=head1 SYNOPSIS
+
+ use Search::Binary;
+ my $pos = binary_search($min, $max, $val, $read, $handle, [$size]);
+
+=head1 DESCRIPTION
+
+Instead of using C<Search:Binary>, for most cases L<List::BinarySearch> offers
+same functionality with simpler, more robust API and thus the latter should be
+preferred and B<this module should be considered deprecated>.
+
+C<binary_search> subroutine (which is exported by default) implements a generic
+binary search algorithm returning the I<position> of the first I<record> which
+I<index value> is greater than or equal to C<$val>. The search routine does not
+define any of the terms I<position>, I<record> or I<index value>, but leaves
+their interpretation and implementation to the user supplied function
+C<&$read()>. The only restriction is that positions must be integer scalars.
+
+During the search the read function will be called with three arguments:
+the input parameters C<$handle> and C<$val>, and a position. If the position
+is not C<undef>, the read function should read the first whole record starting
+at or after the position; otherwise, the read function should read the record
+immediately following the last record it read. The search algorithm will
+guarantee that the first call to the read function will not be with a position
+of C<undef>. The read function needs to return a two element array consisting
+of the result of comparing C<$val> with the index value of the read record and
+the position of the read record. The comparison value must be positive if
+C<$val> is strictly greater than the index value of the read record, C<0>
+if equal, and negative if strictly less. Furthermore, the returned position
+value must be greater than or equal to the position the read function was
+called with.
+
+The input parameters C<$min> and C<$max> are positions and represents the
+extent of the search. Only records which begin at positions within this range
+(inclusive) will be searched. Moreover, C<$min> must be the starting position
+of a record. If present C<$size> is a difference between positions and
+determines when the algorithms switches to a sequential search. C<$val> is
+an index value. The value of C<$handle> is of no consequence to the binary
+search algorithm; it is merely passed as a convenience to the read function.
+
+=head1 USAGE
+
+For simple case of binary search in array of numbers, one can use
+C<Search::Binary> with following closure accepting array reference and
+returning reader function:
+
+ sub make_numeric_array_reader {
+ my ( $array ) = @_;
+ my $current_pos = 0;
+ return sub {
+ my ( $self, $value, $pos ) = @_;
+ $pos = $current_pos + 1 unless defined $pos;
+ $current_pos = $pos;
+ return ( $pos < scalar @{$array}
+ ? $value <=> $array->[$pos]
+ : -1, # see RT #52326
+ $pos );
+ };
+ }
+ # search $value position in non-empty @array of numbers
+ binary_search 0, @array - 1, $value, make_numeric_array_reader(\@array);
+
+Using L<List::BinarySearch>, equivaluent of above code would be:
+
+ binsearch_pos { $a <=> $b } $value, @array;
+
+so unless one wants to use more generic algorithm, L<List::BinarySearch>
+functions should be preferred. There's also L<List::BinarySearch::XS> which
+is faster alternative to pure Perl solutions, if C compiler is available.
+
+=head1 WARNINGS
+
+Prior to version 0.98, C<binary_search> returned array of three elements in
+list context, but it was undocumented and in newer versions this behavior was
+removed.
+
+=head1 SEE ALSO
+
+=over 4
+
+=item * L<List::BinarySearch>
+
+=item * L<List::BinarySearch::XS>
+
+=back
+
+=head1 COPYRIGHT AND LICENSE
+
+Copyright 1998, Erik Rantapaa
+
+This library is free software; you can redistribute it and/or
+modify it under the same terms as Perl itself.
+
+=cut
@@ -0,0 +1,6 @@
+use strict;
+use warnings;
+use Test::More tests => 1;
+
+use_ok 'Search::Binary';
+diag "Testing Search::Binary $Search::Binary::VERSION, Perl $], $^X";
@@ -0,0 +1,18 @@
+use strict;
+use warnings;
+
+BEGIN {
+ unless ($ENV{RELEASE_TESTING}) {
+ use Test::More;
+ plan(skip_all => 'these tests are for release candidate testing');
+ }
+}
+
+eval {
+ require Test::Kwalitee;
+ Test::Kwalitee->import();
+ 1;
+} or do {
+ plan(skip_all => 'Test::Kwalitee not installed; skipping');
+ done_testing();
+};
@@ -0,0 +1,5 @@
+use Test::More;
+eval 'use Test::CPAN::Changes';
+plan skip_all => 'Test::CPAN::Changes required for this test' if $@;
+
+changes_ok();
@@ -0,0 +1,43 @@
+use strict;
+use warnings;
+use Test::More 0.96;
+use Test::Warnings qw(warning);
+
+use Search::Binary;
+use lib 't/lib';
+use Search::Binary::TestUtils qw(make_numeric_array_reader);
+
+sub binary_search_whole_array {
+ my ( $array, $value ) = @_;
+ return binary_search 0, @{$array} - 1, $value, make_numeric_array_reader($array);
+}
+
+subtest 'Basic operations' => sub {
+ my $ints = [ 0..9 ];
+ is(binary_search_whole_array($ints, -100), 0,
+ 'binary_search - element less than all elements in array.');
+ is(binary_search_whole_array($ints, 100), scalar @{$ints},
+ 'binary_search - element greater than all elements in array.');
+ is(binary_search_whole_array($ints, 3), 3, 'binary_search - element in array.');
+ is(binary_search_whole_array($ints, 8), 8, 'binary_search - element in array.');
+};
+
+subtest 'Check stable search' => sub {
+ my $all_equal = [ ( map { 1 } 0..99 ), ( map { 2 } 0..99 ) ];
+ is(binary_search_whole_array($all_equal, 1), 0,
+ 'binary_search - integer (1) equal to few elements in array.');
+ is(binary_search_whole_array($all_equal, 2), 100,
+ 'binary_search - integer (2) equal to few elements in array.');
+};
+
+subtest 'Check warnings' => sub {
+ my @ints = [ 0..9 ];
+ my $warning = warning {
+ is(binary_search(0, -1, 0, make_numeric_array_reader(\@ints)), 0,
+ 'binary_search maintains backwards compatibility if $posmax is less than $posmin');
+ };
+ like($warning, qr/First argument must be less then or equal to second argument/,
+ 'binary_search warns if second argument ($posmax) is less than first argument ($posmin)');
+};
+
+done_testing();
@@ -0,0 +1,68 @@
+use strict;
+use warnings;
+use Test::More 0.96;
+
+use Search::Binary;
+use lib 't/lib';
+use Search::Binary::TestUtils qw(make_numeric_array_reader);
+
+# Tests borrowed from List::BinarySearch
+# See https://metacpan.org/source/DAVIDO/List-BinarySearch-0.20/t/11-search.t
+
+my @integers = ( 100, 200, 300, 400, 500 );
+my @even_length = ( 100, 200, 300, 400, 500, 600 );
+my @non_unique = ( 100, 200, 200, 400, 400, 400, 500, 500 );
+
+subtest "Numeric comparator tests (odd-length list)." => sub {
+ plan tests => 5;
+ for my $ix ( 0 .. $#integers ) {
+ is( binary_search( 0, $#integers, $integers[$ix], make_numeric_array_reader(\@integers) ),
+ $ix,
+ "binary_search: Integer ($integers[$ix]) "
+ . "found in position ($ix)."
+ );
+ }
+ done_testing();
+};
+
+subtest "Even length list tests." => sub {
+ plan tests => 6;
+ for my $ix ( 0 .. $#even_length ) {
+ is( binary_search( 0, $#even_length, $even_length[$ix], make_numeric_array_reader(\@even_length) ),
+ $ix,
+ "binary_search: Even-list: ($even_length[$ix])"
+ . " found at index ($ix)."
+ );
+ }
+ done_testing();
+};
+
+subtest "Non-unique key tests (stable search guarantee)." => sub {
+ plan tests => 3;
+ is( binary_search( 0, $#non_unique, 200, make_numeric_array_reader(\@non_unique) ),
+ 1,
+ "binary_search: First non-unique key of 200 found at 1." );
+ is( binary_search( 0, $#non_unique, 400, make_numeric_array_reader(\@non_unique) ),
+ 3,
+ "binary_search: First occurrence of 400 found at 3 "
+ . "(odd index)."
+ );
+
+ is( binary_search( 0, $#non_unique, 500, make_numeric_array_reader(\@non_unique) ),
+ 6,
+ "binary_search: First occurrence of 500 found at 6 "
+ . "(even index)."
+ );
+
+ done_testing();
+};
+
+my @new_test = ( 100, 200, 300 );
+my $found_ix = binary_search 0, $#new_test, 200, make_numeric_array_reader(\@new_test);
+is( $found_ix, 1, 'binary_search returns correct found index.' );
+$found_ix = binary_search 0, $#new_test, 250, make_numeric_array_reader(\@new_test);
+is( $found_ix, 2, 'binary_search returns correct insertion point.' );
+$found_ix = binary_search 0, $#new_test, 350, make_numeric_array_reader(\@new_test);
+is( $found_ix, 3, 'binary_search returns correct insertion point for value greater than all elements.' );
+
+done_testing();
@@ -0,0 +1,22 @@
+use strict;
+use Test::More;
+END { done_testing }
+use Search::Binary;
+
+sub make_reader {
+ my ( $array ) = @_;
+ my $last_pos;
+ return sub {
+ my (undef, $val, $pos) = @_;
+ $pos = $last_pos + 1 unless defined $pos;
+ $last_pos = $pos;
+ return ($val <=> $array->[$pos]{a}, $pos);
+ }
+}
+
+my @x = ({a => 1}, {a => 4}, {a => 5}, {a => 9}, {a => 12});
+
+foreach my $x (15, 15) {
+ my $next_pos = binary_search(0, $#x, $x, make_reader([ @x ]), undef);
+ is $next_pos, 5;
+}
@@ -0,0 +1,22 @@
+package Search::Binary::TestUtils;
+
+use strict;
+use warnings;
+use parent 'Exporter';
+our @EXPORT_OK = qw(make_numeric_array_reader);
+
+sub make_numeric_array_reader {
+ my ( $array ) = @_;
+ my $current_pos = 0;
+ return sub {
+ my ( $self, $value, $pos ) = @_;
+ $pos = $current_pos + 1 unless defined $pos;
+ $current_pos = $pos;
+ return ( $pos < scalar @{$array}
+ ? $value <=> $array->[$pos]
+ : -1, # see RT #52326
+ $pos );
+ };
+}
+
+1;