/**************************************************************************

    randomlist.cpp  - Some "random functions" :-)
    Copyright (C) 1997,98  Antonio Larrosa Jimenez

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

    Send comments and bug fixes to larrosa@kde.org
    or to Antonio Larrosa, Rio Arnoya, 10 5B, 29006 Malaga, Spain

***************************************************************************/
#include "randomlist.h"
#include <stdlib.h>
#include <stdio.h>

#define RAND_UNIFORM (double)rand()/(double)RAND_MAX

int random_discrete(double *distrib,int n)
{
    int i=0;
    double g=0.0;
    double z=0.0;
    while ((z==0.0)||(z==1.0)) z=RAND_UNIFORM;
    while ((g<z)&&(i<n))
    {
        g+=distrib[i];
        i++;
    };
    return i-1;
}

double *generate_discrete_uniform_distrib(int n)
{
    double *distrib=new double[n];

    for (int i=0;i<n;i++)
        distrib[i]=1.0/(double)n;

    return distrib;
}

void remove_lmn_from_discrete_distrib(int k,double *distrib,int n,int used=0)
{
    int i;
    if (used==0)  //guess how many values of the v.a. are strictly positive
    {
        for (i=0;i<n;i++) if (distrib[i]>0) used++;
    };
    used--; // k will no longer be used :-)
    if (used==0) return;
    double piece=distrib[k]/(double)used;
    distrib[k]=0.0;
    for (i=0;i<n;i++) if (distrib[i]>0) distrib[i]+=piece;
}

void show_distrib(double *distrib,int n)
{
    printf("(");
    for (int j=0;j<n;j++) printf("%g,",distrib[j]);
    printf(")\n");
}

int *generate_random_list(int n)
{
    if (n==0) return NULL;
    int *list=new int[n];
    double *distrib=generate_discrete_uniform_distrib(n);
    int used=n;
    int x;
    int i=1;
    while (used>0)
    {
        x=random_discrete(distrib,n);
        list[x]=i;
        i++;
        remove_lmn_from_discrete_distrib(x,distrib,n,used);
        used--;
    };
    delete distrib;
    
    return list;
}

int *generate_list(int n)
{
    int *list=new int[n];
    for (int i=0;i<n;i++)
        list[i]=i+1;

    return list;
}