<commit_before>#include "data.table.h"

// #define TIMING_ON

/* Only forder() is meant for use by other C code in data.table, hence all functions here other than forder are static.
They make use of global variables, so access must be via forder only.
The coding techniques deployed here are for efficiency.*/

/* Notes regarding the addition of 'nalast' argument:

*/

static int *gs[2] = {NULL};                                         // gs = groupsizes e.g. 23,12,87,2,1,34,...
static int flip = 0;                                                // two vectors flip flopped: flip and 1-flip
static int gsalloc[2] = {0};                                        // allocated stack size
static int gsngrp[2] = {0};                                         // used
static int gsmax[2] = {0};                                          // max grpn so far
static int gsmaxalloc = 0;                                          // max size of stack, set by forder to nrows
static Rboolean stackgrps = TRUE;                                   // switched off for last column when not needed by setkey
static Rboolean sortStr = TRUE;                                     // TRUE for setkey, FALSE for by=
static int *newo = NULL;                                            // used by forder and [i|d|c]sort to reorder order. not needed if length(by)==1

static int nalast = -1;                                             // =1, 0, -1 for TRUE, NA, FALSE respectively. Value rewritten inside forder().
                                                                    // note that na.last=NA (0) removes NAs, not retains them.
static int order = 1;                                               // =1, -1 for ascending and descending order respectively

#define N_SMALL 200                                                 // replaced n < 200 with n < N_SMALL. Easier to change later
#define N_RANGE 100000                                              // range limit for counting sort. UPDATE: should be less than INT_MAX (see setRange for details)

#define Error(...) do {savetl_end(); error(__VA_ARGS__);} while(0)  // http://gcc.gnu.org/onlinedocs/cpp/Swallowing-the-Semicolon.html#Swallowing-the-Semicolon
#undef warning
#define warning(...) Do not use warning in this file                // since it can be turned to error via warn=2
/* use malloc/realloc (not Calloc/Realloc) so we can trap errors 
and call savetl_end() before the error(). */

static void growstack(int newlen) {
    if (newlen==0) newlen=100000;                                   // no link to icount range restriction, just 100,000 seems a good minimum at 0.4MB.
    if (newlen>gsmaxalloc) newlen=gsmaxalloc;
    gs[flip] = realloc(gs[flip], newlen*sizeof(int));
    if (gs[flip] == NULL) Error("Failed to realloc working memory stack to %d*4bytes (flip=%d)", newlen, flip);
    gsalloc[flip] = newlen;
}

static void push(int x) {
    if (!stackgrps || x==0) return;
    if (gsalloc[flip] == gsngrp[flip]) growstack(gsngrp[flip]*2);
    gs[flip][gsngrp[flip]++] = x;
    if (x > gsmax[flip]) gsmax[flip] = x;
}

static void mpush(int x, int n) {
    if (!stackgrps || x==0) return;
    if (gsalloc[flip] < gsngrp[flip]+n) growstack((gsngrp[flip]+n)*2);
    for (int i=0; i<n; i++) gs[flip][gsngrp[flip]++] = x;
    if (x > gsmax[flip]) gsmax[flip] = x;
}

static void flipflop() {
    flip = 1-flip;
    gsngrp[flip] = 0;
    gsmax[flip] = 0;
    if (gsalloc[flip] < gsalloc[1-flip]) growstack(gsalloc[1-flip]*2);
}

static void gsfree() {
    free(gs[0]); free(gs[1]);
    gs[0] = NULL; gs[1]= NULL;
    flip = 0;
    gsalloc[0] = gsalloc[1] = 0;
    gsngrp[0] = gsngrp[1] = 0;
    gsmax[0] = gsmax[1] = 0;
    gsmaxalloc = 0;
}

#ifdef TIMING_ON
  // many calls to clock() can be expensive, hence compiled out rather than switch(verbose)
  #include <time.h>
  #define NBLOCK 20  
  static clock_t tblock[NBLOCK], tstart;
  static int nblock[NBLOCK];
  #define TBEG() tstart = clock();
  #define TEND(i) tblock[i] += clock()-tstart; nblock[i]++; tstart = clock();
#else
  #define TBEG()
  #define TEND(i)
#endif


/* 
   icount originally copied from do_radixsort in src/main/sort.c @ rev 51389. Then reworked here again in forder.c in v1.8.11
   base::sort.list(method="radix") turns out not to be a radix sort, but a counting sort, and we like it.
   See http://r.789695.n4.nabble.com/method-radix-in-sort-list-isn-t-actually-a-radix-sort-tp3309470p3309470.html
   Main changes :
     1. Negatives are fine. Btw, wish raised for simple change to base R : https://bugs.r-project.org/bugzilla3/show_bug.cgi?id=15644
     2. Doesn't cummulate through 0's for speed in repeated calls of sparse counts by saving memset back to 0 of many 0
     3. Separated setRange so forder can redirect to iradix
*/

static int range, off;                                                      // used by both icount and forder
static void setRange(int *x, int n)
{
    int i, tmp;
    int xmin = NA_INTEGER, xmax = NA_INTEGER;
    double overflow;
    
    off = (nalast == 1) ? 0 : 1;   // nalast^decreasing ? 0 : 1;            // off=0 will store values starting from index 0. NAs will go last.
                                                                            // off=1 will store values starting from index 1. NAs will be at 0th index.
    i = 0;
    while(i<n && x[i]==NA_INTEGER) i++;
    if (i<n) xmax = xmin = x[i];
    for(; i < n; i++) {
        tmp = x[i];
        if(tmp == NA_INTEGER) continue;
        if (tmp > xmax) xmax = tmp;
        else if (tmp < xmin) xmin = tmp;
    }
    if(xmin == NA_INTEGER) {range = NA_INTEGER; return;}                    // all NAs, nothing to do    

    if (order == -1) {                                                      // instead of multiplying each time with "order" in the above for-loop, 
        tmp  = order*xmin;                                                  // get 'xmin' and 'xmax' first and change them if order == -1
        xmin = order*xmax;
        xmax = tmp;
    }
    
    overflow = (double)xmax - (double)xmin + 1;                             // ex: x=c(-2147483647L, NA_integer_, 1L) results in overflowing int range.
    if (overflow > INT_MAX) {range = INT_MAX; return;}                      // detect and force iradix here, since icount is out of the picture
    range = xmax-xmin+1;
    off = -xmin+off;                                                        // changed from -xmin+1 to -xmin+off to take care of 'na.last' argument
    return;
}

static void icount(int *x, int *o, int n)
/* Counting sort:
    1. Places the ordering into o directly, overwriting whatever was there
    2. Doesn't change x
    3. Pushes group sizes onto stack
*/
{
    int i=0, tmp;
    int napos = (nalast == 1) ? range : 0;      // increasing ? 0 : range   // take care of 'nalast' argument
    static unsigned int counts[N_RANGE+1] = {0};                            // static is IMPORTANT, counting sort is called repetitively.
    /* counts are set back to 0 at the end efficiently. 1e5 = 0.4MB i.e 
    tiny. We'll only use the front part of it, as large as range. So it's 
    just reserving space, not using it. Have defined N_RANGE to be 100000.*/
    if (range > N_RANGE) Error("Internal error: range = %d; isorted can't handle range > %d", range, N_RANGE);
    for(i=0; i<n; i++) {
        if (x[i] == NA_INTEGER) counts[napos]++;                            // For nalast=NA case, we won't remove/skip NAs, rather set 'o' indices
        else counts[off+ order*x[i]]++;                                     // to 0. subset will skip them. We can't know how many NAs to skip 
    }                                                                       // beforehand - i.e. while allocating "ans" vector
    // TO DO: at this point if the last count==n then it's all the same number and we can stop now.
    // Idea from Terdiman, then improved on that by not needing to loop through counts.
    
    tmp = 0;                                                                // *** BLOCK 4 ***
    for (i=0; i<=range; i++) 
    /* no point in adding tmp<n && i<=range, since range includes max, 
       need to go to max, unlike 256 loops elsewhere in forder.c */
    {
        if (counts[i]) {                                                    // cumulate but not through 0's. Helps resetting zeros when n<range, below.
            push(counts[i]);
            counts[i] = (tmp += counts[i]);
        }
    }
    for(i=n-1; i>=0; i--) {
        tmp = order*x[i];                                                   // take care of na.last=NA after this loop separately.
        o[--counts[(tmp == NA_INTEGER) ? napos : off+tmp]] = (int)(i+1);    // This way na.last=TRUE/FALSE cases will have just a single if-check overhead.
    }
    if (nalast == 0)                                                        // nalast = 1, -1 are both taken care already.
        for (i=0; i<n; i++) o[i] = (x[o[i]-1] == NA_INTEGER) ? 0 : o[i];    // nalast = 0 is dealt with separately as it just sets o to 0
                                                                            // at those indices where x is NA. x[o[i]-1] because x is not modifed here.

    /* counts were cumulated above so leaves non zero. 
    Faster to clear up now ready for next time. */
    if (n < range) {
        /* Many zeros in counts already. Loop through n instead, 
        doesn't matter if we set to 0 several times on any repeats */
        counts[napos]=0;
        for (i=0; i<n; i++) {
            tmp = order*x[i];
            if (tmp!=NA_INTEGER) counts[off+tmp]=0;
        }
    } else {
        memset(counts, 0, (range+1)*sizeof(int));                           // *** BLOCK 6 ***
    }
    return;
}

static int icheck(int x) {
    // return ((nalast != 1) ? x : ((x == NA_INTEGER) ? INT_MAX : x-1));       // if nalast==1, NAs must go last.
    return ((nalast != 1) ? ((x != NA_INTEGER) ? x*order : x) : ((x != NA_INTEGER) ? (x*order)-1 : INT_MAX)); // if nalast==1, NAs must go last.
}

static void iinsert(int *x, int *o, int n)
/*  orders both x and o by reference in-place. Fast for small vectors, low overhead.
    don't be tempted to binsearch backwards here, have to shift anyway; 
    many memmove would have overhead and do the same thing. */
/*  when nalast == 0, iinsert will be called only from within iradix, where o[.] = 0 
    for x[.]=NA is already taken care of */
{
    int i, j, xtmp, otmp, tt;
    for (i=1; i<n; i++) {
        xtmp = x[i];
        if (xtmp < x[i-1]) {
            j = i-1;
            otmp = o[i];
            while (j>=0 && xtmp < x[j]) { 
                x[j+1] = x[j];
                o[j+1] = o[j];
                j--;
            }
            x[j+1] = xtmp;
            o[j+1] = otmp;
        }
    }    
    tt = 0;
    for (i=1; i<n; i++) if (x[i]==x[i-1]) tt++; else { push(tt+1); tt=0; }
    push(tt+1);
}

/*<commit_msg>inlined 'icheck' and upated notes<commit_after>#include "data.table.h"
// #define TIMING_ON

/* 
    - Only forder() and *twiddle() functions are meant for use by other C code in data.table, hence all other functions here except forder and *twiddle are static.
    - The static functions here make use of global variables, whose scope is limited to the same translation unit; therefore access from outside this file must be via forder and/or *twiddle only. 
    - The coding techniques deployed here are for efficiency; e.g. i) the static functions are recursive or called repetitively and we wish to minimise stack overhead, or ii) reach outside themselves to place results in the end result directly rather than returning small bits of memory.
*/

static int *gs[2] = {NULL};                                         // gs = groupsizes e.g. 23,12,87,2,1,34,...
static int flip = 0;                                                // two vectors flip flopped: flip and 1-flip
static int gsalloc[2] = {0};                                        // allocated stack size
static int gsngrp[2] = {0};                                         // used
static int gsmax[2] = {0};                                          // max grpn so far
static int gsmaxalloc = 0;                                          // max size of stack, set by forder to nrows
static Rboolean stackgrps = TRUE;                                   // switched off for last column when not needed by setkey
static Rboolean sortStr = TRUE;                                     // TRUE for setkey, FALSE for by=
static int *newo = NULL;                                            // used by forder and [i|d|c]sort to reorder order. not needed if length(by)==1

static int nalast = -1;                                             // =1, 0, -1 for TRUE, NA, FALSE respectively. Value rewritten inside forder().
                                                                    // note that na.last=NA (0) removes NAs, not retains them.
static int order = 1;                                               // =1, -1 for ascending and descending order respectively

#define N_SMALL 200                                                 // replaced n < 200 with n < N_SMALL. Easier to change later
#define N_RANGE 100000                                              // range limit for counting sort. UPDATE: should be less than INT_MAX (see setRange for details)

#define Error(...) do {savetl_end(); error(__VA_ARGS__);} while(0)  // http://gcc.gnu.org/onlinedocs/cpp/Swallowing-the-Semicolon.html#Swallowing-the-Semicolon
#undef warning
#define warning(...) Do not use warning in this file                // since it can be turned to error via warn=2
/* use malloc/realloc (not Calloc/Realloc) so we can trap errors 
and call savetl_end() before the error(). */

static void growstack(int newlen) {
    if (newlen==0) newlen=100000;                                   // no link to icount range restriction, just 100,000 seems a good minimum at 0.4MB.
    if (newlen>gsmaxalloc) newlen=gsmaxalloc;
    gs[flip] = realloc(gs[flip], newlen*sizeof(int));
    if (gs[flip] == NULL) Error("Failed to realloc working memory stack to %d*4bytes (flip=%d)", newlen, flip);
    gsalloc[flip] = newlen;
}

static void push(int x) {
    if (!stackgrps || x==0) return;
    if (gsalloc[flip] == gsngrp[flip]) growstack(gsngrp[flip]*2);
    gs[flip][gsngrp[flip]++] = x;
    if (x > gsmax[flip]) gsmax[flip] = x;
}

static void mpush(int x, int n) {
    if (!stackgrps || x==0) return;
    if (gsalloc[flip] < gsngrp[flip]+n) growstack((gsngrp[flip]+n)*2);
    for (int i=0; i<n; i++) gs[flip][gsngrp[flip]++] = x;
    if (x > gsmax[flip]) gsmax[flip] = x;
}

static void flipflop() {
    flip = 1-flip;
    gsngrp[flip] = 0;
    gsmax[flip] = 0;
    if (gsalloc[flip] < gsalloc[1-flip]) growstack(gsalloc[1-flip]*2);
}

static void gsfree() {
    free(gs[0]); free(gs[1]);
    gs[0] = NULL; gs[1]= NULL;
    flip = 0;
    gsalloc[0] = gsalloc[1] = 0;
    gsngrp[0] = gsngrp[1] = 0;
    gsmax[0] = gsmax[1] = 0;
    gsmaxalloc = 0;
}

#ifdef TIMING_ON
  // many calls to clock() can be expensive, hence compiled out rather than switch(verbose)
  #include <time.h>
  #define NBLOCK 20  
  static clock_t tblock[NBLOCK], tstart;
  static int nblock[NBLOCK];
  #define TBEG() tstart = clock();
  #define TEND(i) tblock[i] += clock()-tstart; nblock[i]++; tstart = clock();
#else
  #define TBEG()
  #define TEND(i)
#endif


/* 
   icount originally copied from do_radixsort in src/main/sort.c @ rev 51389. Then reworked here again in forder.c in v1.8.11
   base::sort.list(method="radix") turns out not to be a radix sort, but a counting sort, and we like it.
   See http://r.789695.n4.nabble.com/method-radix-in-sort-list-isn-t-actually-a-radix-sort-tp3309470p3309470.html
   Main changes :
     1. Negatives are fine. Btw, wish raised for simple change to base R : https://bugs.r-project.org/bugzilla3/show_bug.cgi?id=15644
     2. Doesn't cummulate through 0's for speed in repeated calls of sparse counts by saving memset back to 0 of many 0
     3. Separated setRange so forder can redirect to iradix
*/

static int range, off;                                                      // used by both icount and forder
static void setRange(int *x, int n)
{
    int i, tmp;
    int xmin = NA_INTEGER, xmax = NA_INTEGER;
    double overflow;
    
    off = (nalast == 1) ? 0 : 1;   // nalast^decreasing ? 0 : 1;            // off=0 will store values starting from index 0. NAs will go last.
                                                                            // off=1 will store values starting from index 1. NAs will be at 0th index.
    i = 0;
    while(i<n && x[i]==NA_INTEGER) i++;
    if (i<n) xmax = xmin = x[i];
    for(; i < n; i++) {
        tmp = x[i];
        if(tmp == NA_INTEGER) continue;
        if (tmp > xmax) xmax = tmp;
        else if (tmp < xmin) xmin = tmp;
    }
    if(xmin == NA_INTEGER) {range = NA_INTEGER; return;}                    // all NAs, nothing to do    

    if (order == -1) {                                                      // instead of multiplying each time with "order" in the above for-loop, 
        tmp  = order*xmin;                                                  // get 'xmin' and 'xmax' first and change them if order == -1
        xmin = order*xmax;
        xmax = tmp;
    }
    
    overflow = (double)xmax - (double)xmin + 1;                             // ex: x=c(-2147483647L, NA_integer_, 1L) results in overflowing int range.
    if (overflow > INT_MAX) {range = INT_MAX; return;}                      // detect and force iradix here, since icount is out of the picture
    range = xmax-xmin+1;
    off = -xmin+off;                                                        // changed from -xmin+1 to -xmin+off to take care of 'na.last' argument
    return;
}

static void icount(int *x, int *o, int n)
/* Counting sort:
    1. Places the ordering into o directly, overwriting whatever was there
    2. Doesn't change x
    3. Pushes group sizes onto stack
*/
{
    int i=0, tmp;
    int napos = (nalast == 1) ? range : 0;      // increasing ? 0 : range   // take care of 'nalast' argument
    static unsigned int counts[N_RANGE+1] = {0};                            // static is IMPORTANT, counting sort is called repetitively.
    /* counts are set back to 0 at the end efficiently. 1e5 = 0.4MB i.e 
    tiny. We'll only use the front part of it, as large as range. So it's 
    just reserving space, not using it. Have defined N_RANGE to be 100000.*/
    if (range > N_RANGE) Error("Internal error: range = %d; isorted can't handle range > %d", range, N_RANGE);
    for(i=0; i<n; i++) {
        if (x[i] == NA_INTEGER) counts[napos]++;                            // For nalast=NA case, we won't remove/skip NAs, rather set 'o' indices
        else counts[off+ order*x[i]]++;                                     // to 0. subset will skip them. We can't know how many NAs to skip 
    }                                                                       // beforehand - i.e. while allocating "ans" vector
    // TO DO: at this point if the last count==n then it's all the same number and we can stop now.
    // Idea from Terdiman, then improved on that by not needing to loop through counts.
    
    tmp = 0;                                                                // *** BLOCK 4 ***
    for (i=0; i<=range; i++) 
    /* no point in adding tmp<n && i<=range, since range includes max, 
       need to go to max, unlike 256 loops elsewhere in forder.c */
    {
        if (counts[i]) {                                                    // cumulate but not through 0's. Helps resetting zeros when n<range, below.
            push(counts[i]);
            counts[i] = (tmp += counts[i]);
        }
    }
    for(i=n-1; i>=0; i--) {
        tmp = order*x[i];                                                   // take care of na.last=NA after this loop separately.
        o[--counts[(tmp == NA_INTEGER) ? napos : off+tmp]] = (int)(i+1);    // This way na.last=TRUE/FALSE cases will have just a single if-check overhead.
    }
    if (nalast == 0)                                                        // nalast = 1, -1 are both taken care already.
        for (i=0; i<n; i++) o[i] = (x[o[i]-1] == NA_INTEGER) ? 0 : o[i];    // nalast = 0 is dealt with separately as it just sets o to 0
                                                                            // at those indices where x is NA. x[o[i]-1] because x is not modifed here.

    /* counts were cumulated above so leaves non zero. 
    Faster to clear up now ready for next time. */
    if (n < range) {
        /* Many zeros in counts already. Loop through n instead, 
        doesn't matter if we set to 0 several times on any repeats */
        counts[napos]=0;
        for (i=0; i<n; i++) {
            tmp = order*x[i];
            if (tmp!=NA_INTEGER) counts[off+tmp]=0;
        }
    } else {
        memset(counts, 0, (range+1)*sizeof(int));                           // *** BLOCK 6 ***
    }
    return;
}

// When x=NA and order=-1 x*order results in integer overflow on some compilers. The commented code below returned in segfault. Fixed by adding additional check.
static inline int icheck(int x) {
    // return ((nalast != 1) ? x : ((x == NA_INTEGER) ? INT_MAX : x-1));    // if nalast==1, NAs must go last.
    return ((nalast != 1) ? ((x != NA_INTEGER) ? x*order : x) : ((x != NA_INTEGER) ? (x*order)-1 : INT_MAX)); // if nalast==1, NAs must go last.
}

static void iinsert(int *x, int *o, int n)
/*  orders both x and o by reference in-place. Fast for small vectors, low overhead.
    don't be tempted to binsearch backwards here, have to shift anyway; 
    many memmove would have overhead and do the same thing. */
/*  when nalast == 0, iinsert will be called only from within iradix, where o[.] = 0 
    for x[.]=NA is already taken care of */
{
    int i, j, xtmp, otmp, tt;
    for (i=1; i<n; i++) {
        xtmp = x[i];
        if (xtmp < x[i-1]) {
            j = i-1;
            otmp = o[i];
            while (j>=0 && xtmp < x[j]) { 
                x[j+1] = x[j];
                o[j+1] = o[j];
                j--;
            }
            x[j+1] = xtmp;
            o[j+1] = otmp;
        }
    }    
    tt = 0;
    for (i=1; i<n; i++) if (x[i]==x[i-1]) tt++; else { push(tt+1); tt=0; }
    push(tt+1);
}

/*
{'fraction_non_alphanumeric': 0.11929321015337699, 'fraction_numerical': 0.02031572338326307, 'mean_word_length': 1.718727139722019, 'pattern_counts': {'":': 0, '<': 47, '<?xml version=': 0, '>': 23, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 118, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3568760', 'n_tokens_mistral': 7177, 'n_tokens_neox': 6765, 'n_words': 2476}