// Send bugs to tony.bruguier@gmail.com

#include <stdio.h>
#include <math.h>

size_t * find_dup(const bool *mat, const size_t n, const size_t m)
{
    size_t *rows = new size_t[n];
    size_t *r0   = new size_t[n];
    size_t *r1   = new size_t[n];
    
    for(size_t ii = 0; ii < n; ++ii)
        rows[ii] = ii;
    
    // Do a radix sort
    for(size_t jj = 0; jj < m; ++jj)
        {
        size_t n0 = 0;
        size_t n1 = 0;
        
        for(size_t ii = 0; ii < n; ++ii)
            if(mat[rows[ii]*m + jj])
                r1[n1++] = rows[ii];
            else
                r0[n0++] = rows[ii];
        
        for(size_t ii = 0; ii < n0; ++ii)
            rows[     ii] = r0[ii];
        for(size_t ii = 0; ii < n1; ++ii)
            rows[n0 + ii] = r1[ii]; 
        }
    
    // Find the duplicates
    size_t * dup_idx = new size_t[n];
    dup_idx[rows[0]] = rows[0];
    
    for(size_t ii = 1; ii < n; ++ii)
        {
        bool dup = true;
        for(size_t jj = 0; jj < m && dup; ++jj)
            if(mat[rows[ii-1]*m + jj] != mat[rows[ii]*m + jj])
                dup = false;
        
        if(dup)
            dup_idx[rows[ii]] = dup_idx[rows[ii-1]];
        else
            dup_idx[rows[ii]] = rows[ii];
        }
    
    delete [] r1;   r1   = NULL;
    delete [] r0;   r0   = NULL;
    delete [] rows; rows = NULL;
    
    return dup_idx;
}

int main(int argc, char **argv)
{
    const size_t n = 4;
    const size_t m = 4;
    bool *mat = (n * m == 0) ? NULL : (new bool[n * m]);
    
    for(size_t kk = 0; kk < n * m; ++kk)
        {
        float val = sqrt(kk);
        mat[kk] = (((char*)(&val))[sizeof(float)-2] & 0x01) == 0; // Pseudo random
        }
    
    size_t * dup_idx = find_dup(mat, n, m);
    
    for(size_t ii = 0; ii < n; ++ii)
        {
        for(size_t jj = 0; jj < m; ++jj)
            printf(mat[m * ii + jj]  ? "1" : "0");
        
        printf("\t%d\n", (int)dup_idx[ii]);
        }
    printf("\n");
    
    delete [] dup_idx; dup_idx = NULL;
    delete [] mat;     mat     = NULL;
    
    return 0;
}