/* * Copyright (c) 1983-2013 Trevor Wishart and Composers Desktop Project Ltd * http://www.trevorwishart.co.uk * http://www.composersdesktop.com * This file is part of the CDP System. The CDP System is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. The CDP System 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with the CDP System; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ /* floatsam version: no changes */ #include #include #include #include #include #include #include #include static void rndpermm(int k,int pindex,int **permm,dataptr dz); static void insert(int m,int t,int pindex,int **permm,dataptr dz); static void prefix(int m,int pindex,int **permm,dataptr dz); static void shuflup(int k,int pindex, int **permm,dataptr dz); /******************************** DOPERM ********************************* * * Either deliver next item in a permuted set, or (if set exhausted) * generate a randon permutation of the set and deliver its first * element. * * (1) If this permset does not have the same length as the last... * (2) Set a new permset length. * (3) If a permset already exists (i.e. this is not first) * Free the permset space, and malloc a new space of correct size, * (4) Create a random permutation of elements into the permset. * (5) Set the pointer-to-the-set to 0. * (6) Set the size of the previous perm (which will be this one, * next time!) to this permset size. * (6a) Whether or not a new perm set has been set up... * (7) Get the value of the next item in the current permset, * incrementing the set pointer in the process. * (8) If this has the same value as the previous-one-output-from-doperm * increment the repetition counter. * (9) Otherwise set the repetition counter to 1. * (10) If the set pointer has run beyond the permset. * (11) reset the pointer to 0. * (12) generate a new random perm (of same length). * (13) Continue this process if the number of permissible repetitions * is exceeded. * (14) Set the value for lastpermval, for next call. * (15) Return the value. */ int doperm(int k,int pindex,int *val,dataptr dz) { int i, OK; int **permm = dz->tex->perm; if(pindex >= PERMCNT) { sprintf(errstr,"doperm(): Perm index %d too big (max = %d)\n",pindex,PERMCNT); return(PROGRAM_ERROR); } if(k <= 1) { if(k>=0) { *val = 0; return(FINISHED); } else { sprintf(errstr,"doperm(): Invalid perm count %d\n",k); return(PROGRAM_ERROR); } } if((k*dz->iparray[TXRPT][pindex])!=dz->iparray[TXLASTPERMLEN][pindex]) { /* 1 */ dz->iparray[TXPERMLEN][pindex] = (int)(k * dz->iparray[TXRPT][pindex]); /* 2 */ if(permm[pindex] != (int *)0) /* 3 */ free(permm[pindex]); if((permm[pindex] = (int *)malloc(dz->iparray[TXPERMLEN][pindex] * sizeof(int)))==NULL) { sprintf(errstr,"INSUFFICIENT MEMORY for permutation %d\n",pindex+1); return(MEMORY_ERROR); } rndpermm(k,pindex,permm,dz); /* 4 */ dz->iparray[TXPERMINDEX][pindex] = 0; /* 5 */ dz->iparray[TXLASTPERMLEN][pindex] = dz->iparray[TXPERMLEN][pindex]; /* 6 */ } do { /* 6a */ OK = 1; i = *(permm[pindex] + (dz->iparray[TXPERMINDEX][pindex]++)); /* 7 */ if(i==dz->iparray[TXLASTPERMVAL][pindex]) { /* 8 */ dz->iparray[TXREPETCNT][pindex]++; if(dz->iparray[TXREPETCNT][pindex]>dz->iparray[TXRPT][pindex]) { dz->iparray[TXREPETCNT][pindex] = dz->iparray[TXRPT][pindex]; OK = 0; } } else { dz->iparray[TXREPETCNT][pindex]=1; } if(dz->iparray[TXPERMINDEX][pindex]>=dz->iparray[TXPERMLEN][pindex]) { /* 10 */ dz->iparray[TXPERMINDEX][pindex] = 0; /* 11 */ rndpermm(k,pindex,permm,dz); /* 12 */ } }while(!OK); /* 13 */ dz->iparray[TXLASTPERMVAL][pindex] = i; /* 14 */ *val = i; return(FINISHED); /* 15 */ } /*************************** RNDPERMM ******************************* * * Produce a permutation of k objects and store it in permutation-store * number 'pindex'. * * (1) permlen is the number of objects (k) times the number of repetitions * permitted (rpt[pindex]) = N. * (2) This is the efficient algorithm for distributing N objects into * a random perm. * (3) As we really only have k objects, we take the value%rpt in each * permutation location. * e.g. 3 objects repeated 3 times would give us a random perm of * nine objects such as * 5 6 2 8 3 0 1 7 4 * applying %3 to this we get * 2 0 2 2 0 0 1 1 1 * i.e. a perm of 3 objects with no more than 3 consecutive repets * of any one object!! */ void rndpermm(int k,int pindex,int **permm,dataptr dz) { int n, t; for(n=0;niparray[TXPERMLEN][pindex];n++) { /* 1 */ t = (int)(drand48() * (double)(n+1)); /* 2 */ if(t==n) { prefix(n,pindex,permm,dz); } else { insert(n,t,pindex,permm,dz); } } for(n=0;niparray[TXPERMLEN][pindex];n++) /* 3 */ *(permm[pindex]+n) = (int)(*(permm[pindex]+n) % k); } /***************************** INSERT ********************************** * * Insert the value m AFTER the T-th element in permm[pindex]. */ void insert(int m,int t,int pindex,int **permm,dataptr dz) { shuflup(t+1,pindex,permm,dz); *(permm[pindex]+t+1) = m; } /***************************** PREFIX ************************************ * * Insert the value m at start of the permutation permm[pindex]. */ void prefix(int m,int pindex,int **permm,dataptr dz) { shuflup(0,pindex,permm,dz); *permm[pindex] = m; } /****************************** SHUFLUP *********************************** * * move set members in permm[pindex] upwards, starting from element k. */ void shuflup(int k,int pindex, int **permm,dataptr dz) { int n, *i; int z = dz->iparray[TXPERMLEN][pindex] - 1; i = permm[pindex] + z; for(n = z;n > k;n--) { *i = *(i-1); i--; } }