#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

#include "ppport.h"

enum { false, true };

bool
quick_sort (const long *num1, const long *num2)
{
    if (*num1 <  *num2) return -1;
    if (*num1 == *num2) return  0;
    if (*num1 >  *num2) return  1;
}

void
bubble_sort (long *numbers, unsigned int realitems)
{
    bool sorted;
    unsigned int i;
    long buffer;

    do
      {
        sorted = true;
        for (i = 0; i < (realitems - 1); i++)
          {
            if ((numbers[i - 1] < numbers[i]) && (numbers[i] < numbers[i + 1]))
              continue;
            if (numbers[i] > numbers[i + 1])
              {
                buffer         = numbers[i];
                numbers[i]     = numbers[i + 1];
                numbers[i + 1] = buffer;
                sorted = false;
              }
          }
      }
    while (!sorted);
}

MODULE = Algorithm::MedianSelect::XS        PACKAGE = Algorithm::MedianSelect::XS

void
xs_median (...)
    PROTOTYPE: @\@
    INIT:
      long numbers[items > 1 ? items : (av_len ((AV*)SvRV(ST(0))) + 1)];
      unsigned int i, median, realitems;
      AV* aref;
    PPCODE:
      if (items == 1)
        {
          if (SvROK (ST(0)))
            {
              if (SvTYPE (SvRV(ST(0))) == SVt_PVAV)
                {
                  aref = (AV*) SvRV (ST(0));
                  for (i = 0; i <= av_len (aref); i++)
                    numbers[i] = SvIV (*av_fetch(aref, i, 0));
                  realitems = av_len (aref) + 1;
                }
              else
                croak ("median(): reference is not a list reference");
            }
          else
            croak ("median(): requires either list or reference to list");
        }
      else
        {
          for (i = 0; i < items; i++)
            numbers[i] = SvIV (ST(i));
          realitems = items;
        }

      switch (SvIV (get_sv("Algorithm::MedianSelect::XS::ALGORITHM", FALSE)))
        {
          case 1:
            bubble_sort (numbers, realitems);
            break;
          case 2:
            qsort (numbers, realitems, sizeof (long), (void *) quick_sort);
            break;
          default:
            croak ("median(): internal error: no mode available");
            break;
        }

      if (realitems % 2 == 0)
        median = realitems / 2;
      else
        median = (realitems - 1) / 2;

      EXTEND (SP, 1);
      PUSHs (sv_2mortal(newSViv(numbers[median])));