################################################################################
#
#  kPerl Logics/Mathematics Library Group
#  Library for Sorting Operations and Algorithms
#
#  copyright (c)
#    Institute of Molecular Biotechnology Jena, Dept. Genome Analysis, 1998-2003
#    Karol Szafranski and Inst. Physiol. Chem., Univ. Düsseldorf, 1997-1998
#  author
#    Karol Szafranski, karol.szafranski@leibniz-fli.de
#
################################################################################
#
#  DESCRIPTION
#
# - individual description of functions can be found at the beginning of the
#   code blocks
#
################################################################################
#
#  FUNCTIONS, DATA
#
#   @EXPORT
#
# - sorted access
#   &ListLocateSorted
#
#
#  STD OPTIONS
#
#   -debug      print debug protocol to STDERR
#
################################################################################

package Math::Sort;

# includes
use strict; #use warnings;  # OK 20040810
use MainLib::Misc;

# symbol export
use Exporter qw(import);
our @EXPORT = qw (
  &ListLocateSorted
  );


################################################################################
# sorted access
################################################################################


# calculate right boundary of a new element in a sorted list
#
# INTERFACE
# - argument 1: reference to list
# - argument 2: reference to new element
#
# - options:
#   -debug      [STD]
#   -sort       sort by function, default:
#                 sub{ $EnNew=$_[0];$EnList=$_[1]; $EnNew cmp $EnList; }
#               The sorting unit function is different from generic sort in
#               that the arguments have a defined identity.
#               This function gives you control about how to access the data
#               value via the array entry. By default the array entry itself
#               is the data value.
#
# - return val: - array position of right boundary, in range 0 .. int (@list)
#               - undef if an error occurred
#
# DESCRIPTION
# - if there's a fully matching element in the list, this one is returned.
#   So, in this case we're not returning the right neighbor, nor are we
#   looking for the most right of a sub-array of identical entries.
#
sub ListLocateSorted {
  my ($pList, $EnQuery, %opt) = @_;
  my ($debug, $ActionSort);
  my ($NumPre, $NumAft, $NumMid, $cmp);

  # function parameters
  $debug = $opt{-debug};
  unless (@$pList) { return undef }
  $ActionSort = $opt{-sort}
    || sub { my $EnNew=$_[0]; my $EnList=$_[1]; $EnNew cmp $EnList; };
  $debug and printf STDERR "%s. number of entries: %d\n", &MySub, int(@$pList);

  # initialize search interval
  $NumPre = -1;  # though minimum result value is 0! This is alright
  $NumAft = int (@$pList);  # maximum result value

  # search
  while (($NumAft - $NumPre) > 1) {
    $NumMid = int (($NumAft+$NumPre) / 2);
    $debug and printf STDERR "%s. interval: %d to %d (mid %d)\n", &MySub, $NumPre, $NumAft, $NumMid;

    # no difference
    unless ($cmp = &$ActionSort($EnQuery,$$pList[$NumMid])) {
      return $NumMid;
    }

    # higher or lower
    elsif ($cmp < 0) {
      $NumAft = $NumMid;
      next;
    } else  {
      $NumPre = $NumMid;
      next;
    }
  }

  # reduced interval to size 1
  $debug and printf STDERR "%s. right / matching entry: %d\n", &MySub, $NumAft;
  return $NumAft;
}


1;
# $Id: Sort.pm,v 1.4 2018/06/05 18:02:56 szafrans Exp $
