NAME
POSIX::bsearch - supplies (and extends) a function missing from the POSIX module
SYNOPSIS
bsearch(\&SortFunc,$key,@SortedTable) returns a possibly empty list of all elements from the sorted list matching $key according to the sort function.
In scalar context, the first matching element located is returned and the $POSIX::bsearch::count variable is left alone.
use POSIX::bsearch;
sub SortFunc {
$a->{lastname} cmp $b->{lastname} or
$a->{firstname} cmp $b->{firstname}
}
my @SortedList = sort SortFunc GetRecords();
for ( bsearch
\&SortFunc # a block would work too
{ lastname => 'Strummer', firstname => 'Joe' }, # key record
@SortedList, # uses \@ prototype
){
$_->{city} eq 'London' and $_->PrintRecord
};
print "Found $POSIX::bsearch::count ";
print "Joes Strummer starting at index $POSIX::bsearch::index\n";DESCRIPTION
Generally, in Perl, you don't need bsearch as we prefer to keep our data in hash tables rather than in sorted lists. So the POSIX module explicitly does not supply a bsearch function.
But here one is. In case you want, for instance, a range of consecutive records.
The function takes three arguments, a comparison function, a key, and a sorted array. Side effects include setting the $POSIX::bsearch::count and $POSIX::bsearch::index variables.
Results and behavior are not defined when applying this function to a list that is not sorted congruently with the provided comparison function. You might get a TABLE NOT SORTED exception, you might get results.
POSIX SEMANTICS
Call bsearch in scalar context to get any matching element.
EXTENDED SEMANTICS
Call bsearch in list context to trigger the extended semantics. Futher exploration of the table is done to find the first and last matching elements. All matching elements are returned in the result set, and two package variables are set.
$POSIX::bsearch::index Set in both scalar and array context, $POSIX::bsearch::index holds the index of the first record that gives a nonnegative comparison result, or -1 when the key is under the 0th element, or the array length when over the last.
$POSIX::bsearch::count
the number of records that give zero comparison result
undefined when called in scalar context
reentrancy
it should be possible to call bsearch within another bsearch's comparison function, although this feature is not explicitly checked in this revision's .t file. The index and count variables will be from the last completed bsearch called in array context.
EXPORT
bsearch
HISTORY
initial version 0.01 written March 4, 2010, in response to a discussion on the perl 5 porters mailng list concerning possible perl uses for bsearch.
version 0.02 edited August 23, 2010, now handles a key that is previous to the first element in the sorted list, also handles larger lists without claiming to be stuck, also sets $POSIX::bsearch::index indicatively when the key is over or under the data range. Stefane Leforestier kindly brought the bug to my attention.
SEE ALSO
look into "Schwarz-Gutman transform" to see the generally recognized best practice for sorting objects by creating a unique string for each object and sorting the strings.
AUTHOR
David Nicol
COPYRIGHT AND LICENSE
Copyright (C) 2010 by David Nicol / Tipjar LLC
This work is licensed under the Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/ or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, California, 94105, USA.
Leaving this section of the documentation in your installed copy of this module intact is sufficient attribution. A source code comment mentioning the POSIX::bsearch module from CPAN is sufficient attribution in derivative works.