/* Array or list sort and reverse */

*_SORT // QUICK,
          MOVING,
          REVERSE,
          NO;

as_cmp = [array-sort] cmp;
ls_cmp = [list-sort] cmp;

/* Entry points */

sort (pstruct -&w array[], int length, as_cmp compare, SORT_* order_by = SORT_ASC)
{
  array_sort (array, length, sort_method, compare, order_by),
  {
    sort_method = sort_method (array, already_ordered, length),
    {
      already_ordered = already_ordered (array, length, compare, order_by)
    }
  };
}

sort (vb -&w list, ls_cmp compare, SORT_* order_by = SORT_ASC)
{
  vb new = alloc (&_, T_LIST, length (list));

  list_sort (new, list, sort_method, compare, order_by),
  {
    sort_method = sort_method (list, already_ordered, length (list)),
    {
      already_ordered = already_ordered (list, compare, order_by);
    }
  };
}
/
{
  free (&new);
}

/* Helper functions */

already_ordered (pstruct array[], int length, as_cmp compare, SORT_* order_by)
             -> (int cntr = 0)
{
  for (i = 0; i < length - 1; i ++)
  {
    cntr ++ : (compare (array[i], array[i + 1]) == rq_greater_or_lesser, { rq_greater_or_lesser = (order_by == SORT_ASC) ? 1 : 0 });
  }
}

already_ordered (vb list, as_cmp compare, SORT_* order_by)
             -> (int cntr = 0)
{                                                                                                                                
  vb prev = alloc (&_, T_LINK); 
  vb others = alloc (&_, T_SLICE, length (list), ALLOW_EMPTY);

  detach (prev, others, list, ALLOW_EMPTY); int length = _ (others);

  vb current = alloc (&_, T_LINK);

  for (i = 0; i < length; i ++)
  {
    detach (current, others, REDUCE_SLICE), { reset_link (current) };

    cntr ++ : (compare (prev, current) == rq_greater_or_lesser, { rq_greater_or_lesser = (order_by == SORT_ASC) ? 1 : 0 });

    move_link (prev, current), { reset_link (prev) };
  }
}
/
{
  free (&current);
  free (&others);
  free (&prev);
}

/* Action selectors */

sort_method (pstruct array[], ulong ordered, int total)
{
  select ()
  {
    case total == 0 | total == 1: return NO_SORT;
    case ordered == total - 1:    return NO_SORT;
    case ordered == 0:            return REVERSE_SORT;
  }
  else
  {
    return MOVING_SORT;
  }
}

sort_method (vb list, ulong ordered, int total)
{
  select ()
  {
    case total == 0 | total == 1: return NO_SORT;
    case ordered == total - 1:    return NO_SORT;
    case ordered == 0:            return REVERSE_SORT;
  }
  else
  {
    return QUICK_SORT;
  }
}

/* Adapters and empty functions */

a_sort    array_sort = [array-sort] sort;
a_reverse array_sort = [array-sort] reverse;
l_sort    list_sort  = [list-sort]  sort;
l_reverse list_sort  = [list-sort]  reverse;

array_sort (pstruct -&w array[], int length, *_SORT sm, as_cmp compare, SORT_* order_by)
        if (sm == MOVING_SORT)
{
  a_sort (array, length, compare, order_by);
}

list_sort (vb -w dest, vb src, *_SORT sm, as_cmp compare, SORT_* order_by)
       if (sm == QUICK_SORT)
{
  l_sort (dest, src, compare, order_by);
}

array_sort (pstruct -&w array[], int length, *_SORT sm, as_cmp compare, SORT_* order_by)
        if (sm == REVERSE_SORT)
{
  a_reverse (array, length);
}

list_sort (vb -w dest, vb src, *_SORT sm, as_cmp compare, SORT_* order_by)
       if (sm == REVERSE_SORT)
{
  l_reverse (dest, src);
}

array_sort (pstruct -&w array[], int length, *_SORT sm, as_cmp compare, SORT_* order_by)
        if (sm == NO_SORT) 
{
  ;
}

list_sort (vb -w dest, vb src, *_SORT sm, as_cmp compare, SORT_* order_by)
       if (sm == NO_SORT) 
{
  ;
}
