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.

cpanm POSIX::bsearch

perl -MCPAN -e shell
install POSIX::bsearch