Home » Recent acquisitions » Acorn ADFS disks » adfs_AcornUser_199512_2.adf » !Regulars » Regulars/StarInfo/Seery/c/fit
Regulars/StarInfo/Seery/c/fit
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » Recent acquisitions » Acorn ADFS disks » adfs_AcornUser_199512_2.adf » !Regulars |
| Filename: | Regulars/StarInfo/Seery/c/fit |
| Read OK: | ✔ |
| File size: | 2826 bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
File contents
/** fit.c ********************************************************************
*
* Calculates best-fit statistics for the programmes and videos lists, and
* leaves this in a global data structure where it can be picked up later.
*
* The fitting itself is a little tricky. It is related basically to
* anagram-producing routines, and the same sort of algorithms are used.
* Basically we fit every combination of programmes across every combination
* of tapes. Actually, although I said 'combination', it should read
* 'permutation' as we don't check for combinations that have already been
* considered.
*
* Permutations are calculated, taking programmes as an example, by
* recursively considering the list. At each stage one less programme is
* considered by the algorithm. The item at the front of the list is
* re-arranged by considering each discrete programme in turn, and the
* rest of the list constructed by passing the remainder of the programmes
* to the next layer in the recursive chain.
*
* Permutations of tapes work in much the same way.
*
* (c) David Seery 1995
*
*****************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <time.h>
#include <math.h>
#include "fittapes.h"
/** Locals *******************************************************************/
typedef enum {badclass, badprecedes, badfollows, valid} verification;
static void permProgrammes(int level, int maxvideos);
static void permVideos(int level);
static void fitPermutation(void);
static void cleanUp(void);
static verification verifyFit(void);
static int minTapes = INT_MAX;
static int minUnused = INT_MAX; /* catch first instances */
static ProgrammeList pList_head = NULL, pList_tail = NULL;
static VideoList vList_head = NULL, vList_tail = NULL;
static double programme_perms_considered = 0;
static double video_perms_considered = 0;
static double perms_considered = 0;
static double viable_perms_considered = 0;
static double perms_index = 1;
/*****************************************************************************/
void fit(FILE *f)
{
int maxprogrammes = 0, maxvideos = 0;
Programme p;
ProgrammeList pL;
Video v;
VideoList vL;
time_t begin_time, end_time;
/* set up the initial programme list and tape list that will be modified
* by the perming routines */
for (p = progList_head; p != NULL; p = p->next)
{
pL = malloc(sizeof(programmeList_instance));
pL->programme = p;
pL->next = NULL;
if (pList_head == NULL)
{
pList_head = pList_tail = pL;
}
else
{
pList_tail->next = pL;
pList_tail = pL;
}
maxprogrammes++;
}
for (v = videoList_head; v != NULL; v = v->next)
{
vL = malloc(sizeof(videoList_instance));
vL->video = v;
vL->programmes = NULL;
vL->next = NULL;
if (vList_head == NULL)
{
vList_head = vList_tail = vL;
}
else
{
vList_tail->next = vL;
vList_tail = vL;
}
maxvideos++;
}
printf("Processing .");
begin_time = time(NULL);
permProgrammes(maxprogrammes,maxvideos);
end_time = time(NULL);
printf("\n");
fprintf(f,"\n"
"** Fit Data **\n\n");
fprintf(f,"Processing completed in %.0lf minutes\n\n",
difftime(end_time,begin_time) / 60);
fprintf(f,"%.0lf permutations of programmes considered\n",
programme_perms_considered);
fprintf(f,"%.0lf permutations of videos considered\n",
video_perms_considered);
fprintf(f,"%.0lf permutations of programmes and videos considered\n",
perms_considered);
fprintf(f,"%.0lf viable permutations of programmes and videos considered\n",
viable_perms_considered);
fprintf(f,"\n"
"** Final Fit **\n\n");
fprintf(f,"\tTapes used = %d\n",minTapes);
fprintf(f,"\tWasted time = %d seconds\n"
"\t (%.2d:%.2d:%.2d)\n",
minUnused,minUnused/60/60,minUnused/60%60,minUnused%60);
}
/*****************************************************************************/
static void permProgrammes(int level, int maxvideos)
{
Programme p;
ProgrammeList considered_pL, pL;
int i;
verification v;
/* will alter programme list in-situ */
if (level == 0)
{
programme_perms_considered++;
if ((v = verifyFit()) == valid)
{
video_perms_considered = 0;
permVideos(maxvideos);
}
}
else
{
for (i = 0, pL = pList_head;
i < level - 1;
i++, pL = pL->next);
considered_pL = pL;
for (i = 0, pL = pList_head;
i < level;
i++, pL = pL->next)
{
p = considered_pL->programme;
considered_pL->programme = pL->programme;
pL->programme = p;
permProgrammes(level - 1,maxvideos);
pL->programme = considered_pL->programme;
considered_pL->programme = p;
}
}
}
static void permVideos(int level)
{
Video v;
VideoList considered_vL, vL;
int i;
/* alters video list in-situ */
if (level == 0)
{
video_perms_considered++;
perms_considered++;
fitPermutation();
}
else
{
for (i = 0, vL = vList_head;
i < level - 1;
i++, vL = vL->next);
considered_vL = vL;
for (i = 0, vL = vList_head;
i < level;
i++, vL = vL->next)
{
v = considered_vL->video;
considered_vL->video = vL->video;
vL->video = v;
permVideos(level - 1);
vL->video = considered_vL->video;
considered_vL->video = v;
}
}
}
static void fitPermutation()
{
/* fit programmeList across videoList */
ProgrammeList pL, ppL, pppL;
VideoList vL, vvL, vvvL;
int tapes_used = 1;
int wasted_time = 0;
if (perms_considered == pow(10,perms_index))
{
printf(".");
perms_index++;
}
vL = vList_head;
vL->usedTime = 0;
vL->programmes = NULL;
for (pL = pList_head; pL != NULL; pL = pL->next)
{
if (vL->usedTime + pL->programme->length <= vL->video->length)
{
/* add programme to this video */
ppL = malloc(sizeof(programmeList_instance));
ppL->programme = pL->programme;
ppL->next = NULL;
if (vL->programmes == NULL)
{
vL->programmes = ppL;
}
else
{
for (pppL = vL->programmes; pppL->next != NULL; pppL = pppL->next);
pppL->next = ppL;
}
vL->usedTime += pL->programme->length;
}
else
{
/* move to next video */
wasted_time += vL->video->length - vL->usedTime;
vL = vL->next;
tapes_used++;
if (vL == NULL)
{
/* won't fit - perm isn't viable */
cleanUp();
return;
}
/* add programme */
ppL = malloc(sizeof(programmeList_instance));
ppL->programme = pL->programme;
ppL->next = NULL;
vL->programmes = ppL;
vL->usedTime = pL->programme->length;
}
}
wasted_time += vL->video->length - vL->usedTime;
viable_perms_considered++;
if (tapes_used < minTapes && wasted_time < minUnused)
{
minTapes = tapes_used;
minUnused = wasted_time;
/* copy structure */
if (bestFit != NULL)
{
/* free up existing structure */
vvL = NULL;
for (vL = bestFit; vL != NULL; vL = vL->next)
{
if (vvL != NULL)
{
free(vvL);
vvL = NULL;
}
for (pL = vL->programmes; pL != NULL;
ppL = pL, pL = pL->next, free(ppL));
vvL = vL;
}
if (vvL != NULL)
{
free(vvL);
}
}
bestFit = NULL;
for (vL = vList_head; vL != NULL; vL = vL->next)
{
vvL = malloc(sizeof(videoList_instance));
vvL->video = vL->video;
vvL->usedTime = vL->usedTime;
vvL->programmes = NULL;
for (pL = vL->programmes; pL != NULL; pL = pL->next)
{
ppL = malloc(sizeof(programmeList_instance));
ppL->programme = pL->programme;
ppL->next = NULL;
if (vvL->programmes == NULL)
{
vvL->programmes = ppL;
}
else
{
for (pppL = vvL->programmes; pppL->next != NULL; pppL = pppL->next);
pppL->next = ppL;
}
}
vvL->next = NULL;
if (bestFit == NULL)
{
bestFit = vvL;
}
else
{
for (vvvL = bestFit; vvvL->next != NULL; vvvL = vvvL->next);
vvvL->next = vvL;
}
}
}
else
{
cleanUp();
}
}
static void cleanUp()
{
VideoList vL;
ProgrammeList pL, ppL;
for (vL = vList_head; vL != NULL; vL = vL->next)
{
for (pL = vL->programmes; pL != NULL;
ppL = pL, pL = pL->next, free(ppL));
vL->programmes = NULL;
vL->usedTime = 0;
}
}
static verification verifyFit()
{
ProgrammeList pL, last_pL = NULL;
Programme p;
boolean *considered;
int i, last_type = -1;
boolean void_type = false;
/* check categories */
considered = calloc(number_categories+1,sizeof(boolean));
for (i = 0; i <= number_categories; i++)
{
considered[i] = false;
}
for (pL = pList_head; pL != NULL; pL = pL->next)
{
p = pL->programme;
if (p->type != NULL && considered[p->type->number])
{
free(considered);
return (badclass);
}
if (p->type == NULL)
{
void_type = true;
}
else
{
if (p->type->number == last_type && void_type)
{
free(considered);
return (badclass);
}
void_type = false;
}
if (p->type != NULL && p->type->number != last_type && last_type != -1)
{
considered[last_type] = true;
}
if (p->type != NULL)
{
last_type = p->type->number;
}
}
free(considered);
/* check groups ('precedes' and 'follows') */
for (pL = pList_head; pL != NULL; pL = pL->next)
{
p = pL->programme;
if (p->precedes != NULL)
{
if (pL->next == NULL)
{
return (badprecedes);
}
if (strcmp(p->precedes,pL->next->programme->name) != 0)
{
return (badprecedes);
}
}
if (p->follows != NULL)
{
if (last_pL == NULL)
{
return (badfollows);
}
if (strcmp(p->follows,last_pL->programme->name) != 0)
{
return (badfollows);
}
}
last_pL = pL;
}
return (valid);
}
00000000 2f 2a 2a 20 66 69 74 2e 63 20 2a 2a 2a 2a 2a 2a |/** fit.c ******|
00000010 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |****************|
*
00000040 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 0a 20 |**************. |
00000050 2a 0a 20 2a 20 20 43 61 6c 63 75 6c 61 74 65 73 |*. * Calculates|
00000060 20 62 65 73 74 2d 66 69 74 20 73 74 61 74 69 73 | best-fit statis|
00000070 74 69 63 73 20 66 6f 72 20 74 68 65 20 70 72 6f |tics for the pro|
00000080 67 72 61 6d 6d 65 73 20 61 6e 64 20 76 69 64 65 |grammes and vide|
00000090 6f 73 20 6c 69 73 74 73 2c 20 61 6e 64 0a 20 2a |os lists, and. *|
000000a0 20 20 6c 65 61 76 65 73 20 74 68 69 73 20 69 6e | leaves this in|
000000b0 20 61 20 67 6c 6f 62 61 6c 20 64 61 74 61 20 73 | a global data s|
000000c0 74 72 75 63 74 75 72 65 20 77 68 65 72 65 20 69 |tructure where i|
000000d0 74 20 63 61 6e 20 62 65 20 70 69 63 6b 65 64 20 |t can be picked |
000000e0 75 70 20 6c 61 74 65 72 2e 0a 20 2a 0a 20 2a 20 |up later.. *. * |
000000f0 20 54 68 65 20 66 69 74 74 69 6e 67 20 69 74 73 | The fitting its|
00000100 65 6c 66 20 69 73 20 61 20 6c 69 74 74 6c 65 20 |elf is a little |
00000110 74 72 69 63 6b 79 2e 20 20 49 74 20 69 73 20 72 |tricky. It is r|
00000120 65 6c 61 74 65 64 20 62 61 73 69 63 61 6c 6c 79 |elated basically|
00000130 20 74 6f 0a 20 2a 20 20 61 6e 61 67 72 61 6d 2d | to. * anagram-|
00000140 70 72 6f 64 75 63 69 6e 67 20 72 6f 75 74 69 6e |producing routin|
00000150 65 73 2c 20 61 6e 64 20 74 68 65 20 73 61 6d 65 |es, and the same|
00000160 20 73 6f 72 74 20 6f 66 20 61 6c 67 6f 72 69 74 | sort of algorit|
00000170 68 6d 73 20 61 72 65 20 75 73 65 64 2e 0a 20 2a |hms are used.. *|
00000180 20 20 42 61 73 69 63 61 6c 6c 79 20 77 65 20 66 | Basically we f|
00000190 69 74 20 65 76 65 72 79 20 63 6f 6d 62 69 6e 61 |it every combina|
000001a0 74 69 6f 6e 20 6f 66 20 70 72 6f 67 72 61 6d 6d |tion of programm|
000001b0 65 73 20 61 63 72 6f 73 73 20 65 76 65 72 79 20 |es across every |
000001c0 63 6f 6d 62 69 6e 61 74 69 6f 6e 0a 20 2a 20 20 |combination. * |
000001d0 6f 66 20 74 61 70 65 73 2e 20 20 41 63 74 75 61 |of tapes. Actua|
000001e0 6c 6c 79 2c 20 61 6c 74 68 6f 75 67 68 20 49 20 |lly, although I |
000001f0 73 61 69 64 20 27 63 6f 6d 62 69 6e 61 74 69 6f |said 'combinatio|
00000200 6e 27 2c 20 69 74 20 73 68 6f 75 6c 64 20 72 65 |n', it should re|
00000210 61 64 0a 20 2a 20 20 27 70 65 72 6d 75 74 61 74 |ad. * 'permutat|
00000220 69 6f 6e 27 20 61 73 20 77 65 20 64 6f 6e 27 74 |ion' as we don't|
00000230 20 63 68 65 63 6b 20 66 6f 72 20 63 6f 6d 62 69 | check for combi|
00000240 6e 61 74 69 6f 6e 73 20 74 68 61 74 20 68 61 76 |nations that hav|
00000250 65 20 61 6c 72 65 61 64 79 20 62 65 65 6e 0a 20 |e already been. |
00000260 2a 20 20 63 6f 6e 73 69 64 65 72 65 64 2e 0a 20 |* considered.. |
00000270 2a 0a 20 2a 20 20 50 65 72 6d 75 74 61 74 69 6f |*. * Permutatio|
00000280 6e 73 20 61 72 65 20 63 61 6c 63 75 6c 61 74 65 |ns are calculate|
00000290 64 2c 20 74 61 6b 69 6e 67 20 70 72 6f 67 72 61 |d, taking progra|
000002a0 6d 6d 65 73 20 61 73 20 61 6e 20 65 78 61 6d 70 |mmes as an examp|
000002b0 6c 65 2c 20 62 79 0a 20 2a 20 20 72 65 63 75 72 |le, by. * recur|
000002c0 73 69 76 65 6c 79 20 63 6f 6e 73 69 64 65 72 69 |sively consideri|
000002d0 6e 67 20 74 68 65 20 6c 69 73 74 2e 20 20 41 74 |ng the list. At|
000002e0 20 65 61 63 68 20 73 74 61 67 65 20 6f 6e 65 20 | each stage one |
000002f0 6c 65 73 73 20 70 72 6f 67 72 61 6d 6d 65 20 69 |less programme i|
00000300 73 0a 20 2a 20 20 63 6f 6e 73 69 64 65 72 65 64 |s. * considered|
00000310 20 62 79 20 74 68 65 20 61 6c 67 6f 72 69 74 68 | by the algorith|
00000320 6d 2e 20 20 54 68 65 20 69 74 65 6d 20 61 74 20 |m. The item at |
00000330 74 68 65 20 66 72 6f 6e 74 20 6f 66 20 74 68 65 |the front of the|
00000340 20 6c 69 73 74 20 69 73 0a 20 2a 20 20 72 65 2d | list is. * re-|
00000350 61 72 72 61 6e 67 65 64 20 62 79 20 63 6f 6e 73 |arranged by cons|
00000360 69 64 65 72 69 6e 67 20 65 61 63 68 20 64 69 73 |idering each dis|
00000370 63 72 65 74 65 20 70 72 6f 67 72 61 6d 6d 65 20 |crete programme |
00000380 69 6e 20 74 75 72 6e 2c 20 61 6e 64 20 74 68 65 |in turn, and the|
00000390 0a 20 2a 20 20 72 65 73 74 20 6f 66 20 74 68 65 |. * rest of the|
000003a0 20 6c 69 73 74 20 63 6f 6e 73 74 72 75 63 74 65 | list constructe|
000003b0 64 20 62 79 20 70 61 73 73 69 6e 67 20 74 68 65 |d by passing the|
000003c0 20 72 65 6d 61 69 6e 64 65 72 20 6f 66 20 74 68 | remainder of th|
000003d0 65 20 70 72 6f 67 72 61 6d 6d 65 73 0a 20 2a 20 |e programmes. * |
000003e0 20 74 6f 20 74 68 65 20 6e 65 78 74 20 6c 61 79 | to the next lay|
000003f0 65 72 20 69 6e 20 74 68 65 20 72 65 63 75 72 73 |er in the recurs|
00000400 69 76 65 20 63 68 61 69 6e 2e 0a 20 2a 0a 20 2a |ive chain.. *. *|
00000410 20 20 50 65 72 6d 75 74 61 74 69 6f 6e 73 20 6f | Permutations o|
00000420 66 20 74 61 70 65 73 20 77 6f 72 6b 20 69 6e 20 |f tapes work in |
00000430 6d 75 63 68 20 74 68 65 20 73 61 6d 65 20 77 61 |much the same wa|
00000440 79 2e 0a 20 2a 0a 20 2a 20 20 28 63 29 20 44 61 |y.. *. * (c) Da|
00000450 76 69 64 20 53 65 65 72 79 20 31 39 39 35 0a 20 |vid Seery 1995. |
00000460 2a 0a 20 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |*. *************|
00000470 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |****************|
*
000004b0 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 64 |/..#include <std|
000004c0 6c 69 62 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 |lib.h>.#include |
000004d0 3c 73 74 64 69 6f 2e 68 3e 0a 23 69 6e 63 6c 75 |<stdio.h>.#inclu|
000004e0 64 65 20 3c 73 74 72 69 6e 67 2e 68 3e 0a 23 69 |de <string.h>.#i|
000004f0 6e 63 6c 75 64 65 20 3c 6c 69 6d 69 74 73 2e 68 |nclude <limits.h|
00000500 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 74 69 6d 65 |>.#include <time|
00000510 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 3c 6d 61 |.h>.#include <ma|
00000520 74 68 2e 68 3e 0a 0a 23 69 6e 63 6c 75 64 65 20 |th.h>..#include |
00000530 22 66 69 74 74 61 70 65 73 2e 68 22 0a 0a 2f 2a |"fittapes.h"../*|
00000540 2a 20 4c 6f 63 61 6c 73 20 2a 2a 2a 2a 2a 2a 2a |* Locals *******|
00000550 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |****************|
*
00000580 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 74 |************/..t|
00000590 79 70 65 64 65 66 20 65 6e 75 6d 20 7b 62 61 64 |ypedef enum {bad|
000005a0 63 6c 61 73 73 2c 20 62 61 64 70 72 65 63 65 64 |class, badpreced|
000005b0 65 73 2c 20 62 61 64 66 6f 6c 6c 6f 77 73 2c 20 |es, badfollows, |
000005c0 76 61 6c 69 64 7d 20 76 65 72 69 66 69 63 61 74 |valid} verificat|
000005d0 69 6f 6e 3b 0a 0a 73 74 61 74 69 63 20 76 6f 69 |ion;..static voi|
000005e0 64 20 70 65 72 6d 50 72 6f 67 72 61 6d 6d 65 73 |d permProgrammes|
000005f0 28 69 6e 74 20 6c 65 76 65 6c 2c 20 69 6e 74 20 |(int level, int |
00000600 6d 61 78 76 69 64 65 6f 73 29 3b 0a 73 74 61 74 |maxvideos);.stat|
00000610 69 63 20 76 6f 69 64 20 70 65 72 6d 56 69 64 65 |ic void permVide|
00000620 6f 73 28 69 6e 74 20 6c 65 76 65 6c 29 3b 0a 73 |os(int level);.s|
00000630 74 61 74 69 63 20 76 6f 69 64 20 66 69 74 50 65 |tatic void fitPe|
00000640 72 6d 75 74 61 74 69 6f 6e 28 76 6f 69 64 29 3b |rmutation(void);|
00000650 0a 73 74 61 74 69 63 20 76 6f 69 64 20 63 6c 65 |.static void cle|
00000660 61 6e 55 70 28 76 6f 69 64 29 3b 0a 73 74 61 74 |anUp(void);.stat|
00000670 69 63 20 76 65 72 69 66 69 63 61 74 69 6f 6e 20 |ic verification |
00000680 76 65 72 69 66 79 46 69 74 28 76 6f 69 64 29 3b |verifyFit(void);|
00000690 0a 0a 73 74 61 74 69 63 20 69 6e 74 20 6d 69 6e |..static int min|
000006a0 54 61 70 65 73 20 3d 20 49 4e 54 5f 4d 41 58 3b |Tapes = INT_MAX;|
000006b0 0a 73 74 61 74 69 63 20 69 6e 74 20 6d 69 6e 55 |.static int minU|
000006c0 6e 75 73 65 64 20 3d 20 49 4e 54 5f 4d 41 58 3b |nused = INT_MAX;|
000006d0 20 2f 2a 20 63 61 74 63 68 20 66 69 72 73 74 20 | /* catch first |
000006e0 69 6e 73 74 61 6e 63 65 73 20 2a 2f 0a 0a 73 74 |instances */..st|
000006f0 61 74 69 63 20 50 72 6f 67 72 61 6d 6d 65 4c 69 |atic ProgrammeLi|
00000700 73 74 20 70 4c 69 73 74 5f 68 65 61 64 20 3d 20 |st pList_head = |
00000710 4e 55 4c 4c 2c 20 70 4c 69 73 74 5f 74 61 69 6c |NULL, pList_tail|
00000720 20 3d 20 4e 55 4c 4c 3b 0a 73 74 61 74 69 63 20 | = NULL;.static |
00000730 56 69 64 65 6f 4c 69 73 74 20 76 4c 69 73 74 5f |VideoList vList_|
00000740 68 65 61 64 20 3d 20 4e 55 4c 4c 2c 20 76 4c 69 |head = NULL, vLi|
00000750 73 74 5f 74 61 69 6c 20 3d 20 4e 55 4c 4c 3b 0a |st_tail = NULL;.|
00000760 0a 73 74 61 74 69 63 20 64 6f 75 62 6c 65 20 70 |.static double p|
00000770 72 6f 67 72 61 6d 6d 65 5f 70 65 72 6d 73 5f 63 |rogramme_perms_c|
00000780 6f 6e 73 69 64 65 72 65 64 20 3d 20 30 3b 0a 73 |onsidered = 0;.s|
00000790 74 61 74 69 63 20 64 6f 75 62 6c 65 20 76 69 64 |tatic double vid|
000007a0 65 6f 5f 70 65 72 6d 73 5f 63 6f 6e 73 69 64 65 |eo_perms_conside|
000007b0 72 65 64 20 3d 20 30 3b 0a 73 74 61 74 69 63 20 |red = 0;.static |
000007c0 64 6f 75 62 6c 65 20 70 65 72 6d 73 5f 63 6f 6e |double perms_con|
000007d0 73 69 64 65 72 65 64 20 3d 20 30 3b 0a 73 74 61 |sidered = 0;.sta|
000007e0 74 69 63 20 64 6f 75 62 6c 65 20 76 69 61 62 6c |tic double viabl|
000007f0 65 5f 70 65 72 6d 73 5f 63 6f 6e 73 69 64 65 72 |e_perms_consider|
00000800 65 64 20 3d 20 30 3b 0a 0a 73 74 61 74 69 63 20 |ed = 0;..static |
00000810 64 6f 75 62 6c 65 20 70 65 72 6d 73 5f 69 6e 64 |double perms_ind|
00000820 65 78 20 3d 20 31 3b 0a 0a 2f 2a 2a 2a 2a 2a 2a |ex = 1;../******|
00000830 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |****************|
*
00000870 2a 2a 2a 2a 2a 2a 2a 2f 0a 0a 76 6f 69 64 20 66 |*******/..void f|
00000880 69 74 28 46 49 4c 45 20 2a 66 29 0a 7b 0a 20 20 |it(FILE *f).{. |
00000890 69 6e 74 20 6d 61 78 70 72 6f 67 72 61 6d 6d 65 |int maxprogramme|
000008a0 73 20 3d 20 30 2c 20 6d 61 78 76 69 64 65 6f 73 |s = 0, maxvideos|
000008b0 20 3d 20 30 3b 0a 20 20 50 72 6f 67 72 61 6d 6d | = 0;. Programm|
000008c0 65 20 70 3b 0a 20 20 50 72 6f 67 72 61 6d 6d 65 |e p;. Programme|
000008d0 4c 69 73 74 20 70 4c 3b 0a 20 20 56 69 64 65 6f |List pL;. Video|
000008e0 20 76 3b 0a 20 20 56 69 64 65 6f 4c 69 73 74 20 | v;. VideoList |
000008f0 76 4c 3b 0a 20 20 74 69 6d 65 5f 74 20 62 65 67 |vL;. time_t beg|
00000900 69 6e 5f 74 69 6d 65 2c 20 65 6e 64 5f 74 69 6d |in_time, end_tim|
00000910 65 3b 0a 0a 20 20 2f 2a 20 73 65 74 20 75 70 20 |e;.. /* set up |
00000920 74 68 65 20 69 6e 69 74 69 61 6c 20 70 72 6f 67 |the initial prog|
00000930 72 61 6d 6d 65 20 6c 69 73 74 20 61 6e 64 20 74 |ramme list and t|
00000940 61 70 65 20 6c 69 73 74 20 74 68 61 74 20 77 69 |ape list that wi|
00000950 6c 6c 20 62 65 20 6d 6f 64 69 66 69 65 64 0a 20 |ll be modified. |
00000960 20 20 2a 20 62 79 20 74 68 65 20 70 65 72 6d 69 | * by the permi|
00000970 6e 67 20 72 6f 75 74 69 6e 65 73 20 2a 2f 0a 0a |ng routines */..|
00000980 20 20 66 6f 72 20 28 70 20 3d 20 70 72 6f 67 4c | for (p = progL|
00000990 69 73 74 5f 68 65 61 64 3b 20 70 20 21 3d 20 4e |ist_head; p != N|
000009a0 55 4c 4c 3b 20 70 20 3d 20 70 2d 3e 6e 65 78 74 |ULL; p = p->next|
000009b0 29 0a 20 20 7b 0a 20 20 20 20 70 4c 20 3d 20 6d |). {. pL = m|
000009c0 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 70 72 6f |alloc(sizeof(pro|
000009d0 67 72 61 6d 6d 65 4c 69 73 74 5f 69 6e 73 74 61 |grammeList_insta|
000009e0 6e 63 65 29 29 3b 0a 20 20 20 20 70 4c 2d 3e 70 |nce));. pL->p|
000009f0 72 6f 67 72 61 6d 6d 65 20 3d 20 70 3b 0a 20 20 |rogramme = p;. |
00000a00 20 20 70 4c 2d 3e 6e 65 78 74 20 3d 20 4e 55 4c | pL->next = NUL|
00000a10 4c 3b 0a 20 20 20 20 69 66 20 28 70 4c 69 73 74 |L;. if (pList|
00000a20 5f 68 65 61 64 20 3d 3d 20 4e 55 4c 4c 29 0a 20 |_head == NULL). |
00000a30 20 20 20 7b 0a 20 20 20 20 20 20 70 4c 69 73 74 | {. pList|
00000a40 5f 68 65 61 64 20 3d 20 70 4c 69 73 74 5f 74 61 |_head = pList_ta|
00000a50 69 6c 20 3d 20 70 4c 3b 0a 20 20 20 20 7d 0a 20 |il = pL;. }. |
00000a60 20 20 20 65 6c 73 65 0a 20 20 20 20 7b 0a 20 20 | else. {. |
00000a70 20 20 20 20 70 4c 69 73 74 5f 74 61 69 6c 2d 3e | pList_tail->|
00000a80 6e 65 78 74 20 3d 20 70 4c 3b 0a 20 20 20 20 20 |next = pL;. |
00000a90 20 70 4c 69 73 74 5f 74 61 69 6c 20 3d 20 70 4c | pList_tail = pL|
00000aa0 3b 0a 20 20 20 20 7d 0a 0a 20 20 20 20 6d 61 78 |;. }.. max|
00000ab0 70 72 6f 67 72 61 6d 6d 65 73 2b 2b 3b 0a 20 20 |programmes++;. |
00000ac0 7d 0a 0a 20 20 66 6f 72 20 28 76 20 3d 20 76 69 |}.. for (v = vi|
00000ad0 64 65 6f 4c 69 73 74 5f 68 65 61 64 3b 20 76 20 |deoList_head; v |
00000ae0 21 3d 20 4e 55 4c 4c 3b 20 76 20 3d 20 76 2d 3e |!= NULL; v = v->|
00000af0 6e 65 78 74 29 0a 20 20 7b 0a 20 20 20 20 76 4c |next). {. vL|
00000b00 20 3d 20 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 | = malloc(sizeof|
00000b10 28 76 69 64 65 6f 4c 69 73 74 5f 69 6e 73 74 61 |(videoList_insta|
00000b20 6e 63 65 29 29 3b 0a 20 20 20 20 76 4c 2d 3e 76 |nce));. vL->v|
00000b30 69 64 65 6f 20 3d 20 76 3b 0a 20 20 20 20 76 4c |ideo = v;. vL|
00000b40 2d 3e 70 72 6f 67 72 61 6d 6d 65 73 20 3d 20 4e |->programmes = N|
00000b50 55 4c 4c 3b 0a 20 20 20 20 76 4c 2d 3e 6e 65 78 |ULL;. vL->nex|
00000b60 74 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 69 66 |t = NULL;. if|
00000b70 20 28 76 4c 69 73 74 5f 68 65 61 64 20 3d 3d 20 | (vList_head == |
00000b80 4e 55 4c 4c 29 0a 20 20 20 20 7b 0a 20 20 20 20 |NULL). {. |
00000b90 20 20 76 4c 69 73 74 5f 68 65 61 64 20 3d 20 76 | vList_head = v|
00000ba0 4c 69 73 74 5f 74 61 69 6c 20 3d 20 76 4c 3b 0a |List_tail = vL;.|
00000bb0 20 20 20 20 7d 0a 20 20 20 20 65 6c 73 65 0a 20 | }. else. |
00000bc0 20 20 20 7b 0a 20 20 20 20 20 20 76 4c 69 73 74 | {. vList|
00000bd0 5f 74 61 69 6c 2d 3e 6e 65 78 74 20 3d 20 76 4c |_tail->next = vL|
00000be0 3b 0a 20 20 20 20 20 20 76 4c 69 73 74 5f 74 61 |;. vList_ta|
00000bf0 69 6c 20 3d 20 76 4c 3b 0a 20 20 20 20 7d 0a 0a |il = vL;. }..|
00000c00 20 20 20 20 6d 61 78 76 69 64 65 6f 73 2b 2b 3b | maxvideos++;|
00000c10 0a 20 20 7d 0a 0a 20 20 70 72 69 6e 74 66 28 22 |. }.. printf("|
00000c20 50 72 6f 63 65 73 73 69 6e 67 20 2e 22 29 3b 0a |Processing .");.|
00000c30 0a 20 20 62 65 67 69 6e 5f 74 69 6d 65 20 3d 20 |. begin_time = |
00000c40 74 69 6d 65 28 4e 55 4c 4c 29 3b 0a 0a 20 20 70 |time(NULL);.. p|
00000c50 65 72 6d 50 72 6f 67 72 61 6d 6d 65 73 28 6d 61 |ermProgrammes(ma|
00000c60 78 70 72 6f 67 72 61 6d 6d 65 73 2c 6d 61 78 76 |xprogrammes,maxv|
00000c70 69 64 65 6f 73 29 3b 0a 0a 20 20 65 6e 64 5f 74 |ideos);.. end_t|
00000c80 69 6d 65 20 3d 20 74 69 6d 65 28 4e 55 4c 4c 29 |ime = time(NULL)|
00000c90 3b 0a 0a 20 20 70 72 69 6e 74 66 28 22 5c 6e 22 |;.. printf("\n"|
00000ca0 29 3b 0a 0a 20 20 66 70 72 69 6e 74 66 28 66 2c |);.. fprintf(f,|
00000cb0 22 5c 6e 22 0a 20 20 09 20 20 20 20 22 2a 2a 20 |"\n". . "** |
00000cc0 46 69 74 20 44 61 74 61 20 2a 2a 5c 6e 5c 6e 22 |Fit Data **\n\n"|
00000cd0 29 3b 0a 20 20 66 70 72 69 6e 74 66 28 66 2c 22 |);. fprintf(f,"|
00000ce0 50 72 6f 63 65 73 73 69 6e 67 20 63 6f 6d 70 6c |Processing compl|
00000cf0 65 74 65 64 20 69 6e 20 25 2e 30 6c 66 20 6d 69 |eted in %.0lf mi|
00000d00 6e 75 74 65 73 5c 6e 5c 6e 22 2c 0a 20 20 09 20 |nutes\n\n",. . |
00000d10 20 64 69 66 66 74 69 6d 65 28 65 6e 64 5f 74 69 | difftime(end_ti|
00000d20 6d 65 2c 62 65 67 69 6e 5f 74 69 6d 65 29 20 2f |me,begin_time) /|
00000d30 20 36 30 29 3b 0a 20 20 66 70 72 69 6e 74 66 28 | 60);. fprintf(|
00000d40 66 2c 22 25 2e 30 6c 66 20 70 65 72 6d 75 74 61 |f,"%.0lf permuta|
00000d50 74 69 6f 6e 73 20 6f 66 20 70 72 6f 67 72 61 6d |tions of program|
00000d60 6d 65 73 20 63 6f 6e 73 69 64 65 72 65 64 5c 6e |mes considered\n|
00000d70 22 2c 0a 20 20 09 20 20 70 72 6f 67 72 61 6d 6d |",. . programm|
00000d80 65 5f 70 65 72 6d 73 5f 63 6f 6e 73 69 64 65 72 |e_perms_consider|
00000d90 65 64 29 3b 0a 20 20 66 70 72 69 6e 74 66 28 66 |ed);. fprintf(f|
00000da0 2c 22 25 2e 30 6c 66 20 70 65 72 6d 75 74 61 74 |,"%.0lf permutat|
00000db0 69 6f 6e 73 20 6f 66 20 76 69 64 65 6f 73 20 63 |ions of videos c|
00000dc0 6f 6e 73 69 64 65 72 65 64 5c 6e 22 2c 0a 20 20 |onsidered\n",. |
00000dd0 09 20 20 76 69 64 65 6f 5f 70 65 72 6d 73 5f 63 |. video_perms_c|
00000de0 6f 6e 73 69 64 65 72 65 64 29 3b 0a 20 20 66 70 |onsidered);. fp|
00000df0 72 69 6e 74 66 28 66 2c 22 25 2e 30 6c 66 20 70 |rintf(f,"%.0lf p|
00000e00 65 72 6d 75 74 61 74 69 6f 6e 73 20 6f 66 20 70 |ermutations of p|
00000e10 72 6f 67 72 61 6d 6d 65 73 20 61 6e 64 20 76 69 |rogrammes and vi|
00000e20 64 65 6f 73 20 63 6f 6e 73 69 64 65 72 65 64 5c |deos considered\|
00000e30 6e 22 2c 0a 20 20 09 20 20 70 65 72 6d 73 5f 63 |n",. . perms_c|
00000e40 6f 6e 73 69 64 65 72 65 64 29 3b 0a 20 20 66 70 |onsidered);. fp|
00000e50 72 69 6e 74 66 28 66 2c 22 25 2e 30 6c 66 20 76 |rintf(f,"%.0lf v|
00000e60 69 61 62 6c 65 20 70 65 72 6d 75 74 61 74 69 6f |iable permutatio|
00000e70 6e 73 20 6f 66 20 70 72 6f 67 72 61 6d 6d 65 73 |ns of programmes|
00000e80 20 61 6e 64 20 76 69 64 65 6f 73 20 63 6f 6e 73 | and videos cons|
00000e90 69 64 65 72 65 64 5c 6e 22 2c 0a 20 20 09 20 20 |idered\n",. . |
00000ea0 76 69 61 62 6c 65 5f 70 65 72 6d 73 5f 63 6f 6e |viable_perms_con|
00000eb0 73 69 64 65 72 65 64 29 3b 0a 20 20 66 70 72 69 |sidered);. fpri|
00000ec0 6e 74 66 28 66 2c 22 5c 6e 22 0a 20 20 09 20 20 |ntf(f,"\n". . |
00000ed0 20 20 22 2a 2a 20 46 69 6e 61 6c 20 46 69 74 20 | "** Final Fit |
00000ee0 2a 2a 5c 6e 5c 6e 22 29 3b 0a 20 20 66 70 72 69 |**\n\n");. fpri|
00000ef0 6e 74 66 28 66 2c 22 5c 74 54 61 70 65 73 20 75 |ntf(f,"\tTapes u|
00000f00 73 65 64 20 3d 20 25 64 5c 6e 22 2c 6d 69 6e 54 |sed = %d\n",minT|
00000f10 61 70 65 73 29 3b 0a 20 20 66 70 72 69 6e 74 66 |apes);. fprintf|
00000f20 28 66 2c 22 5c 74 57 61 73 74 65 64 20 74 69 6d |(f,"\tWasted tim|
00000f30 65 20 3d 20 25 64 20 73 65 63 6f 6e 64 73 5c 6e |e = %d seconds\n|
00000f40 22 0a 20 20 09 20 20 20 20 22 5c 74 20 20 20 20 |". . "\t |
00000f50 20 20 20 20 20 20 20 20 20 20 28 25 2e 32 64 3a | (%.2d:|
00000f60 25 2e 32 64 3a 25 2e 32 64 29 5c 6e 22 2c 0a 20 |%.2d:%.2d)\n",. |
00000f70 20 09 20 20 6d 69 6e 55 6e 75 73 65 64 2c 6d 69 | . minUnused,mi|
00000f80 6e 55 6e 75 73 65 64 2f 36 30 2f 36 30 2c 6d 69 |nUnused/60/60,mi|
00000f90 6e 55 6e 75 73 65 64 2f 36 30 25 36 30 2c 6d 69 |nUnused/60%60,mi|
00000fa0 6e 55 6e 75 73 65 64 25 36 30 29 3b 0a 7d 0a 0a |nUnused%60);.}..|
00000fb0 2f 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |/***************|
00000fc0 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a |****************|
*
00000ff0 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2f 0a |**************/.|
00001000 0a 73 74 61 74 69 63 20 76 6f 69 64 20 70 65 72 |.static void per|
00001010 6d 50 72 6f 67 72 61 6d 6d 65 73 28 69 6e 74 20 |mProgrammes(int |
00001020 6c 65 76 65 6c 2c 20 69 6e 74 20 6d 61 78 76 69 |level, int maxvi|
00001030 64 65 6f 73 29 0a 7b 0a 20 20 50 72 6f 67 72 61 |deos).{. Progra|
00001040 6d 6d 65 20 70 3b 0a 20 20 50 72 6f 67 72 61 6d |mme p;. Program|
00001050 6d 65 4c 69 73 74 20 63 6f 6e 73 69 64 65 72 65 |meList considere|
00001060 64 5f 70 4c 2c 20 70 4c 3b 0a 20 20 69 6e 74 20 |d_pL, pL;. int |
00001070 69 3b 0a 20 20 76 65 72 69 66 69 63 61 74 69 6f |i;. verificatio|
00001080 6e 20 76 3b 0a 0a 20 20 2f 2a 20 77 69 6c 6c 20 |n v;.. /* will |
00001090 61 6c 74 65 72 20 70 72 6f 67 72 61 6d 6d 65 20 |alter programme |
000010a0 6c 69 73 74 20 69 6e 2d 73 69 74 75 20 2a 2f 0a |list in-situ */.|
000010b0 0a 20 20 69 66 20 28 6c 65 76 65 6c 20 3d 3d 20 |. if (level == |
000010c0 30 29 0a 20 20 7b 0a 20 20 20 20 70 72 6f 67 72 |0). {. progr|
000010d0 61 6d 6d 65 5f 70 65 72 6d 73 5f 63 6f 6e 73 69 |amme_perms_consi|
000010e0 64 65 72 65 64 2b 2b 3b 0a 0a 20 20 20 20 69 66 |dered++;.. if|
000010f0 20 28 28 76 20 3d 20 76 65 72 69 66 79 46 69 74 | ((v = verifyFit|
00001100 28 29 29 20 3d 3d 20 76 61 6c 69 64 29 0a 20 20 |()) == valid). |
00001110 20 20 7b 0a 20 20 20 20 20 20 76 69 64 65 6f 5f | {. video_|
00001120 70 65 72 6d 73 5f 63 6f 6e 73 69 64 65 72 65 64 |perms_considered|
00001130 20 3d 20 30 3b 0a 20 20 20 20 20 20 70 65 72 6d | = 0;. perm|
00001140 56 69 64 65 6f 73 28 6d 61 78 76 69 64 65 6f 73 |Videos(maxvideos|
00001150 29 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 65 |);. }. }. e|
00001160 6c 73 65 0a 20 20 7b 0a 20 20 20 20 66 6f 72 20 |lse. {. for |
00001170 28 69 20 3d 20 30 2c 20 70 4c 20 3d 20 70 4c 69 |(i = 0, pL = pLi|
00001180 73 74 5f 68 65 61 64 3b 0a 20 20 20 20 09 20 69 |st_head;. . i|
00001190 20 3c 20 6c 65 76 65 6c 20 2d 20 31 3b 0a 20 20 | < level - 1;. |
000011a0 20 20 09 20 69 2b 2b 2c 20 70 4c 20 3d 20 70 4c | . i++, pL = pL|
000011b0 2d 3e 6e 65 78 74 29 3b 0a 20 20 20 20 63 6f 6e |->next);. con|
000011c0 73 69 64 65 72 65 64 5f 70 4c 20 3d 20 70 4c 3b |sidered_pL = pL;|
000011d0 0a 0a 20 20 20 20 66 6f 72 20 28 69 20 3d 20 30 |.. for (i = 0|
000011e0 2c 20 70 4c 20 3d 20 70 4c 69 73 74 5f 68 65 61 |, pL = pList_hea|
000011f0 64 3b 0a 20 20 20 20 09 20 69 20 3c 20 6c 65 76 |d;. . i < lev|
00001200 65 6c 3b 0a 20 20 20 20 09 20 69 2b 2b 2c 20 70 |el;. . i++, p|
00001210 4c 20 3d 20 70 4c 2d 3e 6e 65 78 74 29 0a 20 20 |L = pL->next). |
00001220 20 20 7b 0a 20 20 20 20 20 20 70 20 3d 20 63 6f | {. p = co|
00001230 6e 73 69 64 65 72 65 64 5f 70 4c 2d 3e 70 72 6f |nsidered_pL->pro|
00001240 67 72 61 6d 6d 65 3b 0a 20 20 20 20 20 20 63 6f |gramme;. co|
00001250 6e 73 69 64 65 72 65 64 5f 70 4c 2d 3e 70 72 6f |nsidered_pL->pro|
00001260 67 72 61 6d 6d 65 20 3d 20 70 4c 2d 3e 70 72 6f |gramme = pL->pro|
00001270 67 72 61 6d 6d 65 3b 0a 20 20 20 20 20 20 70 4c |gramme;. pL|
00001280 2d 3e 70 72 6f 67 72 61 6d 6d 65 20 3d 20 70 3b |->programme = p;|
00001290 0a 20 20 20 20 20 20 70 65 72 6d 50 72 6f 67 72 |. permProgr|
000012a0 61 6d 6d 65 73 28 6c 65 76 65 6c 20 2d 20 31 2c |ammes(level - 1,|
000012b0 6d 61 78 76 69 64 65 6f 73 29 3b 0a 20 20 20 20 |maxvideos);. |
000012c0 20 20 70 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 20 | pL->programme |
000012d0 3d 20 63 6f 6e 73 69 64 65 72 65 64 5f 70 4c 2d |= considered_pL-|
000012e0 3e 70 72 6f 67 72 61 6d 6d 65 3b 0a 20 20 20 20 |>programme;. |
000012f0 20 20 63 6f 6e 73 69 64 65 72 65 64 5f 70 4c 2d | considered_pL-|
00001300 3e 70 72 6f 67 72 61 6d 6d 65 20 3d 20 70 3b 0a |>programme = p;.|
00001310 20 20 20 20 7d 0a 20 20 7d 0a 7d 0a 0a 73 74 61 | }. }.}..sta|
00001320 74 69 63 20 76 6f 69 64 20 70 65 72 6d 56 69 64 |tic void permVid|
00001330 65 6f 73 28 69 6e 74 20 6c 65 76 65 6c 29 0a 7b |eos(int level).{|
00001340 0a 20 20 56 69 64 65 6f 20 76 3b 0a 20 20 56 69 |. Video v;. Vi|
00001350 64 65 6f 4c 69 73 74 20 63 6f 6e 73 69 64 65 72 |deoList consider|
00001360 65 64 5f 76 4c 2c 20 76 4c 3b 0a 20 20 69 6e 74 |ed_vL, vL;. int|
00001370 20 69 3b 0a 0a 20 20 2f 2a 20 61 6c 74 65 72 73 | i;.. /* alters|
00001380 20 76 69 64 65 6f 20 6c 69 73 74 20 69 6e 2d 73 | video list in-s|
00001390 69 74 75 20 2a 2f 0a 0a 20 20 69 66 20 28 6c 65 |itu */.. if (le|
000013a0 76 65 6c 20 3d 3d 20 30 29 0a 20 20 7b 0a 20 20 |vel == 0). {. |
000013b0 20 20 76 69 64 65 6f 5f 70 65 72 6d 73 5f 63 6f | video_perms_co|
000013c0 6e 73 69 64 65 72 65 64 2b 2b 3b 0a 20 20 20 20 |nsidered++;. |
000013d0 70 65 72 6d 73 5f 63 6f 6e 73 69 64 65 72 65 64 |perms_considered|
000013e0 2b 2b 3b 0a 20 20 20 20 66 69 74 50 65 72 6d 75 |++;. fitPermu|
000013f0 74 61 74 69 6f 6e 28 29 3b 0a 20 20 7d 0a 20 20 |tation();. }. |
00001400 65 6c 73 65 0a 20 20 7b 0a 20 20 20 20 66 6f 72 |else. {. for|
00001410 20 28 69 20 3d 20 30 2c 20 76 4c 20 3d 20 76 4c | (i = 0, vL = vL|
00001420 69 73 74 5f 68 65 61 64 3b 0a 20 20 20 20 09 20 |ist_head;. . |
00001430 69 20 3c 20 6c 65 76 65 6c 20 2d 20 31 3b 0a 20 |i < level - 1;. |
00001440 20 20 20 09 20 69 2b 2b 2c 20 76 4c 20 3d 20 76 | . i++, vL = v|
00001450 4c 2d 3e 6e 65 78 74 29 3b 0a 20 20 20 20 63 6f |L->next);. co|
00001460 6e 73 69 64 65 72 65 64 5f 76 4c 20 3d 20 76 4c |nsidered_vL = vL|
00001470 3b 0a 0a 20 20 20 20 66 6f 72 20 28 69 20 3d 20 |;.. for (i = |
00001480 30 2c 20 76 4c 20 3d 20 76 4c 69 73 74 5f 68 65 |0, vL = vList_he|
00001490 61 64 3b 0a 20 20 20 20 09 20 69 20 3c 20 6c 65 |ad;. . i < le|
000014a0 76 65 6c 3b 0a 20 20 20 20 09 20 69 2b 2b 2c 20 |vel;. . i++, |
000014b0 76 4c 20 3d 20 76 4c 2d 3e 6e 65 78 74 29 0a 20 |vL = vL->next). |
000014c0 20 20 20 7b 0a 20 20 20 20 20 20 76 20 3d 20 63 | {. v = c|
000014d0 6f 6e 73 69 64 65 72 65 64 5f 76 4c 2d 3e 76 69 |onsidered_vL->vi|
000014e0 64 65 6f 3b 0a 20 20 20 20 20 20 63 6f 6e 73 69 |deo;. consi|
000014f0 64 65 72 65 64 5f 76 4c 2d 3e 76 69 64 65 6f 20 |dered_vL->video |
00001500 3d 20 76 4c 2d 3e 76 69 64 65 6f 3b 0a 20 20 20 |= vL->video;. |
00001510 20 20 20 76 4c 2d 3e 76 69 64 65 6f 20 3d 20 76 | vL->video = v|
00001520 3b 0a 20 20 20 20 20 20 70 65 72 6d 56 69 64 65 |;. permVide|
00001530 6f 73 28 6c 65 76 65 6c 20 2d 20 31 29 3b 0a 20 |os(level - 1);. |
00001540 20 20 20 20 20 76 4c 2d 3e 76 69 64 65 6f 20 3d | vL->video =|
00001550 20 63 6f 6e 73 69 64 65 72 65 64 5f 76 4c 2d 3e | considered_vL->|
00001560 76 69 64 65 6f 3b 0a 20 20 20 20 20 20 63 6f 6e |video;. con|
00001570 73 69 64 65 72 65 64 5f 76 4c 2d 3e 76 69 64 65 |sidered_vL->vide|
00001580 6f 20 3d 20 76 3b 0a 20 20 20 20 7d 0a 20 20 7d |o = v;. }. }|
00001590 0a 7d 0a 0a 73 74 61 74 69 63 20 76 6f 69 64 20 |.}..static void |
000015a0 66 69 74 50 65 72 6d 75 74 61 74 69 6f 6e 28 29 |fitPermutation()|
000015b0 0a 7b 0a 20 20 2f 2a 20 66 69 74 20 70 72 6f 67 |.{. /* fit prog|
000015c0 72 61 6d 6d 65 4c 69 73 74 20 61 63 72 6f 73 73 |rammeList across|
000015d0 20 76 69 64 65 6f 4c 69 73 74 20 2a 2f 0a 20 20 | videoList */. |
000015e0 50 72 6f 67 72 61 6d 6d 65 4c 69 73 74 20 70 4c |ProgrammeList pL|
000015f0 2c 20 70 70 4c 2c 20 70 70 70 4c 3b 0a 20 20 56 |, ppL, pppL;. V|
00001600 69 64 65 6f 4c 69 73 74 20 76 4c 2c 20 76 76 4c |ideoList vL, vvL|
00001610 2c 20 76 76 76 4c 3b 0a 20 20 69 6e 74 20 74 61 |, vvvL;. int ta|
00001620 70 65 73 5f 75 73 65 64 20 3d 20 31 3b 0a 20 20 |pes_used = 1;. |
00001630 69 6e 74 20 77 61 73 74 65 64 5f 74 69 6d 65 20 |int wasted_time |
00001640 3d 20 30 3b 0a 0a 20 20 69 66 20 28 70 65 72 6d |= 0;.. if (perm|
00001650 73 5f 63 6f 6e 73 69 64 65 72 65 64 20 3d 3d 20 |s_considered == |
00001660 70 6f 77 28 31 30 2c 70 65 72 6d 73 5f 69 6e 64 |pow(10,perms_ind|
00001670 65 78 29 29 0a 20 20 7b 0a 20 20 20 20 70 72 69 |ex)). {. pri|
00001680 6e 74 66 28 22 2e 22 29 3b 0a 20 20 20 20 70 65 |ntf(".");. pe|
00001690 72 6d 73 5f 69 6e 64 65 78 2b 2b 3b 0a 20 20 7d |rms_index++;. }|
000016a0 0a 0a 20 20 76 4c 20 3d 20 76 4c 69 73 74 5f 68 |.. vL = vList_h|
000016b0 65 61 64 3b 0a 20 20 76 4c 2d 3e 75 73 65 64 54 |ead;. vL->usedT|
000016c0 69 6d 65 20 3d 20 30 3b 0a 20 20 76 4c 2d 3e 70 |ime = 0;. vL->p|
000016d0 72 6f 67 72 61 6d 6d 65 73 20 3d 20 4e 55 4c 4c |rogrammes = NULL|
000016e0 3b 0a 20 20 66 6f 72 20 28 70 4c 20 3d 20 70 4c |;. for (pL = pL|
000016f0 69 73 74 5f 68 65 61 64 3b 20 70 4c 20 21 3d 20 |ist_head; pL != |
00001700 4e 55 4c 4c 3b 20 70 4c 20 3d 20 70 4c 2d 3e 6e |NULL; pL = pL->n|
00001710 65 78 74 29 0a 20 20 7b 0a 20 20 20 20 69 66 20 |ext). {. if |
00001720 28 76 4c 2d 3e 75 73 65 64 54 69 6d 65 20 2b 20 |(vL->usedTime + |
00001730 70 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 2d 3e 6c |pL->programme->l|
00001740 65 6e 67 74 68 20 3c 3d 20 76 4c 2d 3e 76 69 64 |ength <= vL->vid|
00001750 65 6f 2d 3e 6c 65 6e 67 74 68 29 0a 20 20 20 20 |eo->length). |
00001760 7b 0a 20 20 20 20 20 20 2f 2a 20 61 64 64 20 70 |{. /* add p|
00001770 72 6f 67 72 61 6d 6d 65 20 74 6f 20 74 68 69 73 |rogramme to this|
00001780 20 76 69 64 65 6f 20 2a 2f 0a 20 20 20 20 20 20 | video */. |
00001790 70 70 4c 20 3d 20 6d 61 6c 6c 6f 63 28 73 69 7a |ppL = malloc(siz|
000017a0 65 6f 66 28 70 72 6f 67 72 61 6d 6d 65 4c 69 73 |eof(programmeLis|
000017b0 74 5f 69 6e 73 74 61 6e 63 65 29 29 3b 0a 20 20 |t_instance));. |
000017c0 20 20 20 20 70 70 4c 2d 3e 70 72 6f 67 72 61 6d | ppL->program|
000017d0 6d 65 20 3d 20 70 4c 2d 3e 70 72 6f 67 72 61 6d |me = pL->program|
000017e0 6d 65 3b 0a 20 20 20 20 20 20 70 70 4c 2d 3e 6e |me;. ppL->n|
000017f0 65 78 74 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 |ext = NULL;. |
00001800 20 20 69 66 20 28 76 4c 2d 3e 70 72 6f 67 72 61 | if (vL->progra|
00001810 6d 6d 65 73 20 3d 3d 20 4e 55 4c 4c 29 0a 20 20 |mmes == NULL). |
00001820 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 76 4c | {. vL|
00001830 2d 3e 70 72 6f 67 72 61 6d 6d 65 73 20 3d 20 70 |->programmes = p|
00001840 70 4c 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 |pL;. }. |
00001850 20 20 65 6c 73 65 0a 20 20 20 20 20 20 7b 0a 20 | else. {. |
00001860 20 20 20 20 20 20 20 66 6f 72 20 28 70 70 70 4c | for (pppL|
00001870 20 3d 20 76 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 | = vL->programme|
00001880 73 3b 20 70 70 70 4c 2d 3e 6e 65 78 74 20 21 3d |s; pppL->next !=|
00001890 20 4e 55 4c 4c 3b 20 70 70 70 4c 20 3d 20 70 70 | NULL; pppL = pp|
000018a0 70 4c 2d 3e 6e 65 78 74 29 3b 0a 20 20 20 20 20 |pL->next);. |
000018b0 20 20 20 70 70 70 4c 2d 3e 6e 65 78 74 20 3d 20 | pppL->next = |
000018c0 70 70 4c 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 |ppL;. }. |
000018d0 20 20 20 76 4c 2d 3e 75 73 65 64 54 69 6d 65 20 | vL->usedTime |
000018e0 2b 3d 20 70 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 |+= pL->programme|
000018f0 2d 3e 6c 65 6e 67 74 68 3b 0a 20 20 20 20 7d 0a |->length;. }.|
00001900 20 20 20 20 65 6c 73 65 0a 20 20 20 20 7b 0a 20 | else. {. |
00001910 20 20 20 20 20 2f 2a 20 6d 6f 76 65 20 74 6f 20 | /* move to |
00001920 6e 65 78 74 20 76 69 64 65 6f 20 2a 2f 0a 20 20 |next video */. |
00001930 20 20 20 20 77 61 73 74 65 64 5f 74 69 6d 65 20 | wasted_time |
00001940 2b 3d 20 76 4c 2d 3e 76 69 64 65 6f 2d 3e 6c 65 |+= vL->video->le|
00001950 6e 67 74 68 20 2d 20 76 4c 2d 3e 75 73 65 64 54 |ngth - vL->usedT|
00001960 69 6d 65 3b 0a 20 20 20 20 20 20 76 4c 20 3d 20 |ime;. vL = |
00001970 76 4c 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 20 20 |vL->next;. |
00001980 74 61 70 65 73 5f 75 73 65 64 2b 2b 3b 0a 20 20 |tapes_used++;. |
00001990 20 20 20 20 69 66 20 28 76 4c 20 3d 3d 20 4e 55 | if (vL == NU|
000019a0 4c 4c 29 0a 20 20 20 20 20 20 7b 0a 20 20 20 20 |LL). {. |
000019b0 20 20 20 20 2f 2a 20 77 6f 6e 27 74 20 66 69 74 | /* won't fit|
000019c0 20 2d 20 70 65 72 6d 20 69 73 6e 27 74 20 76 69 | - perm isn't vi|
000019d0 61 62 6c 65 20 2a 2f 0a 20 20 20 20 20 20 20 20 |able */. |
000019e0 63 6c 65 61 6e 55 70 28 29 3b 0a 20 20 20 20 20 |cleanUp();. |
000019f0 20 20 20 72 65 74 75 72 6e 3b 0a 20 20 20 20 20 | return;. |
00001a00 20 7d 0a 20 20 20 20 20 20 2f 2a 20 61 64 64 20 | }. /* add |
00001a10 70 72 6f 67 72 61 6d 6d 65 20 2a 2f 0a 20 20 20 |programme */. |
00001a20 20 20 20 70 70 4c 20 3d 20 6d 61 6c 6c 6f 63 28 | ppL = malloc(|
00001a30 73 69 7a 65 6f 66 28 70 72 6f 67 72 61 6d 6d 65 |sizeof(programme|
00001a40 4c 69 73 74 5f 69 6e 73 74 61 6e 63 65 29 29 3b |List_instance));|
00001a50 0a 20 20 20 20 20 20 70 70 4c 2d 3e 70 72 6f 67 |. ppL->prog|
00001a60 72 61 6d 6d 65 20 3d 20 70 4c 2d 3e 70 72 6f 67 |ramme = pL->prog|
00001a70 72 61 6d 6d 65 3b 0a 20 20 20 20 20 20 70 70 4c |ramme;. ppL|
00001a80 2d 3e 6e 65 78 74 20 3d 20 4e 55 4c 4c 3b 0a 20 |->next = NULL;. |
00001a90 20 20 20 20 20 76 4c 2d 3e 70 72 6f 67 72 61 6d | vL->program|
00001aa0 6d 65 73 20 3d 20 70 70 4c 3b 0a 20 20 20 20 20 |mes = ppL;. |
00001ab0 20 76 4c 2d 3e 75 73 65 64 54 69 6d 65 20 3d 20 | vL->usedTime = |
00001ac0 70 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 2d 3e 6c |pL->programme->l|
00001ad0 65 6e 67 74 68 3b 0a 20 20 20 20 7d 0a 20 20 7d |ength;. }. }|
00001ae0 0a 20 20 77 61 73 74 65 64 5f 74 69 6d 65 20 2b |. wasted_time +|
00001af0 3d 20 76 4c 2d 3e 76 69 64 65 6f 2d 3e 6c 65 6e |= vL->video->len|
00001b00 67 74 68 20 2d 20 76 4c 2d 3e 75 73 65 64 54 69 |gth - vL->usedTi|
00001b10 6d 65 3b 0a 0a 20 20 76 69 61 62 6c 65 5f 70 65 |me;.. viable_pe|
00001b20 72 6d 73 5f 63 6f 6e 73 69 64 65 72 65 64 2b 2b |rms_considered++|
00001b30 3b 0a 0a 20 20 69 66 20 28 74 61 70 65 73 5f 75 |;.. if (tapes_u|
00001b40 73 65 64 20 3c 20 6d 69 6e 54 61 70 65 73 20 26 |sed < minTapes &|
00001b50 26 20 77 61 73 74 65 64 5f 74 69 6d 65 20 3c 20 |& wasted_time < |
00001b60 6d 69 6e 55 6e 75 73 65 64 29 0a 20 20 7b 0a 20 |minUnused). {. |
00001b70 20 20 20 6d 69 6e 54 61 70 65 73 20 3d 20 74 61 | minTapes = ta|
00001b80 70 65 73 5f 75 73 65 64 3b 0a 20 20 20 20 6d 69 |pes_used;. mi|
00001b90 6e 55 6e 75 73 65 64 20 3d 20 77 61 73 74 65 64 |nUnused = wasted|
00001ba0 5f 74 69 6d 65 3b 0a 20 20 20 20 2f 2a 20 63 6f |_time;. /* co|
00001bb0 70 79 20 73 74 72 75 63 74 75 72 65 20 2a 2f 0a |py structure */.|
00001bc0 20 20 20 20 69 66 20 28 62 65 73 74 46 69 74 20 | if (bestFit |
00001bd0 21 3d 20 4e 55 4c 4c 29 0a 20 20 20 20 7b 0a 20 |!= NULL). {. |
00001be0 20 20 20 20 20 2f 2a 20 66 72 65 65 20 75 70 20 | /* free up |
00001bf0 65 78 69 73 74 69 6e 67 20 73 74 72 75 63 74 75 |existing structu|
00001c00 72 65 20 2a 2f 0a 20 20 20 20 20 20 76 76 4c 20 |re */. vvL |
00001c10 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 66 6f |= NULL;. fo|
00001c20 72 20 28 76 4c 20 3d 20 62 65 73 74 46 69 74 3b |r (vL = bestFit;|
00001c30 20 76 4c 20 21 3d 20 4e 55 4c 4c 3b 20 76 4c 20 | vL != NULL; vL |
00001c40 3d 20 76 4c 2d 3e 6e 65 78 74 29 0a 20 20 20 20 |= vL->next). |
00001c50 20 20 7b 0a 20 20 20 20 20 20 20 20 69 66 20 28 | {. if (|
00001c60 76 76 4c 20 21 3d 20 4e 55 4c 4c 29 0a 20 20 20 |vvL != NULL). |
00001c70 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 20 | {. |
00001c80 20 66 72 65 65 28 76 76 4c 29 3b 0a 20 20 20 20 | free(vvL);. |
00001c90 20 20 20 20 20 20 76 76 4c 20 3d 20 4e 55 4c 4c | vvL = NULL|
00001ca0 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 |;. }. |
00001cb0 20 20 20 20 66 6f 72 20 28 70 4c 20 3d 20 76 4c | for (pL = vL|
00001cc0 2d 3e 70 72 6f 67 72 61 6d 6d 65 73 3b 20 70 4c |->programmes; pL|
00001cd0 20 21 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 | != NULL;. |
00001ce0 20 20 20 20 20 20 20 70 70 4c 20 3d 20 70 4c 2c | ppL = pL,|
00001cf0 20 70 4c 20 3d 20 70 4c 2d 3e 6e 65 78 74 2c 20 | pL = pL->next, |
00001d00 66 72 65 65 28 70 70 4c 29 29 3b 0a 20 20 20 20 |free(ppL));. |
00001d10 20 20 20 20 76 76 4c 20 3d 20 76 4c 3b 0a 20 20 | vvL = vL;. |
00001d20 20 20 20 20 7d 0a 20 20 20 20 20 20 69 66 20 28 | }. if (|
00001d30 76 76 4c 20 21 3d 20 4e 55 4c 4c 29 0a 20 20 20 |vvL != NULL). |
00001d40 20 20 20 7b 0a 20 20 20 20 20 20 20 20 66 72 65 | {. fre|
00001d50 65 28 76 76 4c 29 3b 0a 20 20 20 20 20 20 7d 0a |e(vvL);. }.|
00001d60 20 20 20 20 7d 0a 20 20 20 20 62 65 73 74 46 69 | }. bestFi|
00001d70 74 20 3d 20 4e 55 4c 4c 3b 0a 20 20 20 20 66 6f |t = NULL;. fo|
00001d80 72 20 28 76 4c 20 3d 20 76 4c 69 73 74 5f 68 65 |r (vL = vList_he|
00001d90 61 64 3b 20 76 4c 20 21 3d 20 4e 55 4c 4c 3b 20 |ad; vL != NULL; |
00001da0 76 4c 20 3d 20 76 4c 2d 3e 6e 65 78 74 29 0a 20 |vL = vL->next). |
00001db0 20 20 20 7b 0a 20 20 20 20 20 20 76 76 4c 20 3d | {. vvL =|
00001dc0 20 6d 61 6c 6c 6f 63 28 73 69 7a 65 6f 66 28 76 | malloc(sizeof(v|
00001dd0 69 64 65 6f 4c 69 73 74 5f 69 6e 73 74 61 6e 63 |ideoList_instanc|
00001de0 65 29 29 3b 0a 20 20 20 20 20 20 76 76 4c 2d 3e |e));. vvL->|
00001df0 76 69 64 65 6f 20 3d 20 76 4c 2d 3e 76 69 64 65 |video = vL->vide|
00001e00 6f 3b 0a 20 20 20 20 20 20 76 76 4c 2d 3e 75 73 |o;. vvL->us|
00001e10 65 64 54 69 6d 65 20 3d 20 76 4c 2d 3e 75 73 65 |edTime = vL->use|
00001e20 64 54 69 6d 65 3b 0a 20 20 20 20 20 20 76 76 4c |dTime;. vvL|
00001e30 2d 3e 70 72 6f 67 72 61 6d 6d 65 73 20 3d 20 4e |->programmes = N|
00001e40 55 4c 4c 3b 0a 20 20 20 20 20 20 66 6f 72 20 28 |ULL;. for (|
00001e50 70 4c 20 3d 20 76 4c 2d 3e 70 72 6f 67 72 61 6d |pL = vL->program|
00001e60 6d 65 73 3b 20 70 4c 20 21 3d 20 4e 55 4c 4c 3b |mes; pL != NULL;|
00001e70 20 70 4c 20 3d 20 70 4c 2d 3e 6e 65 78 74 29 0a | pL = pL->next).|
00001e80 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 | {. |
00001e90 70 70 4c 20 3d 20 6d 61 6c 6c 6f 63 28 73 69 7a |ppL = malloc(siz|
00001ea0 65 6f 66 28 70 72 6f 67 72 61 6d 6d 65 4c 69 73 |eof(programmeLis|
00001eb0 74 5f 69 6e 73 74 61 6e 63 65 29 29 3b 0a 20 20 |t_instance));. |
00001ec0 20 20 20 20 20 20 70 70 4c 2d 3e 70 72 6f 67 72 | ppL->progr|
00001ed0 61 6d 6d 65 20 3d 20 70 4c 2d 3e 70 72 6f 67 72 |amme = pL->progr|
00001ee0 61 6d 6d 65 3b 0a 20 20 20 20 20 20 20 20 70 70 |amme;. pp|
00001ef0 4c 2d 3e 6e 65 78 74 20 3d 20 4e 55 4c 4c 3b 0a |L->next = NULL;.|
00001f00 20 20 20 20 20 20 20 20 69 66 20 28 76 76 4c 2d | if (vvL-|
00001f10 3e 70 72 6f 67 72 61 6d 6d 65 73 20 3d 3d 20 4e |>programmes == N|
00001f20 55 4c 4c 29 0a 20 20 20 20 20 20 20 20 7b 0a 20 |ULL). {. |
00001f30 20 20 20 20 20 20 20 20 20 76 76 4c 2d 3e 70 72 | vvL->pr|
00001f40 6f 67 72 61 6d 6d 65 73 20 3d 20 70 70 4c 3b 0a |ogrammes = ppL;.|
00001f50 20 20 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 | }. |
00001f60 20 20 65 6c 73 65 0a 20 20 20 20 20 20 20 20 7b | else. {|
00001f70 0a 20 20 20 20 20 20 20 20 20 20 66 6f 72 20 28 |. for (|
00001f80 70 70 70 4c 20 3d 20 76 76 4c 2d 3e 70 72 6f 67 |pppL = vvL->prog|
00001f90 72 61 6d 6d 65 73 3b 20 70 70 70 4c 2d 3e 6e 65 |rammes; pppL->ne|
00001fa0 78 74 20 21 3d 20 4e 55 4c 4c 3b 20 70 70 70 4c |xt != NULL; pppL|
00001fb0 20 3d 20 70 70 70 4c 2d 3e 6e 65 78 74 29 3b 0a | = pppL->next);.|
00001fc0 20 20 20 20 20 20 20 20 20 20 70 70 70 4c 2d 3e | pppL->|
00001fd0 6e 65 78 74 20 3d 20 70 70 4c 3b 0a 20 20 20 20 |next = ppL;. |
00001fe0 20 20 20 20 7d 0a 20 20 20 20 20 20 7d 0a 20 20 | }. }. |
00001ff0 20 20 20 20 76 76 4c 2d 3e 6e 65 78 74 20 3d 20 | vvL->next = |
00002000 4e 55 4c 4c 3b 0a 20 20 20 20 20 20 69 66 20 28 |NULL;. if (|
00002010 62 65 73 74 46 69 74 20 3d 3d 20 4e 55 4c 4c 29 |bestFit == NULL)|
00002020 0a 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 |. {. |
00002030 20 62 65 73 74 46 69 74 20 3d 20 76 76 4c 3b 0a | bestFit = vvL;.|
00002040 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 65 6c | }. el|
00002050 73 65 0a 20 20 20 20 20 20 7b 0a 20 20 20 20 20 |se. {. |
00002060 20 20 20 66 6f 72 20 28 76 76 76 4c 20 3d 20 62 | for (vvvL = b|
00002070 65 73 74 46 69 74 3b 20 76 76 76 4c 2d 3e 6e 65 |estFit; vvvL->ne|
00002080 78 74 20 21 3d 20 4e 55 4c 4c 3b 20 76 76 76 4c |xt != NULL; vvvL|
00002090 20 3d 20 76 76 76 4c 2d 3e 6e 65 78 74 29 3b 0a | = vvvL->next);.|
000020a0 20 20 20 20 20 20 20 20 76 76 76 4c 2d 3e 6e 65 | vvvL->ne|
000020b0 78 74 20 3d 20 76 76 4c 3b 0a 20 20 20 20 20 20 |xt = vvL;. |
000020c0 7d 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 65 6c |}. }. }. el|
000020d0 73 65 0a 20 20 7b 0a 20 20 20 20 63 6c 65 61 6e |se. {. clean|
000020e0 55 70 28 29 3b 0a 20 20 7d 0a 7d 0a 0a 73 74 61 |Up();. }.}..sta|
000020f0 74 69 63 20 76 6f 69 64 20 63 6c 65 61 6e 55 70 |tic void cleanUp|
00002100 28 29 0a 7b 0a 20 20 56 69 64 65 6f 4c 69 73 74 |().{. VideoList|
00002110 20 76 4c 3b 0a 20 20 50 72 6f 67 72 61 6d 6d 65 | vL;. Programme|
00002120 4c 69 73 74 20 70 4c 2c 20 70 70 4c 3b 0a 0a 20 |List pL, ppL;.. |
00002130 20 66 6f 72 20 28 76 4c 20 3d 20 76 4c 69 73 74 | for (vL = vList|
00002140 5f 68 65 61 64 3b 20 76 4c 20 21 3d 20 4e 55 4c |_head; vL != NUL|
00002150 4c 3b 20 76 4c 20 3d 20 76 4c 2d 3e 6e 65 78 74 |L; vL = vL->next|
00002160 29 0a 20 20 7b 0a 20 20 20 20 66 6f 72 20 28 70 |). {. for (p|
00002170 4c 20 3d 20 76 4c 2d 3e 70 72 6f 67 72 61 6d 6d |L = vL->programm|
00002180 65 73 3b 20 70 4c 20 21 3d 20 4e 55 4c 4c 3b 0a |es; pL != NULL;.|
00002190 20 20 20 20 09 20 70 70 4c 20 3d 20 70 4c 2c 20 | . ppL = pL, |
000021a0 70 4c 20 3d 20 70 4c 2d 3e 6e 65 78 74 2c 20 66 |pL = pL->next, f|
000021b0 72 65 65 28 70 70 4c 29 29 3b 0a 20 20 20 20 76 |ree(ppL));. v|
000021c0 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 73 20 3d 20 |L->programmes = |
000021d0 4e 55 4c 4c 3b 0a 20 20 20 20 76 4c 2d 3e 75 73 |NULL;. vL->us|
000021e0 65 64 54 69 6d 65 20 3d 20 30 3b 0a 20 20 7d 0a |edTime = 0;. }.|
000021f0 7d 0a 0a 73 74 61 74 69 63 20 76 65 72 69 66 69 |}..static verifi|
00002200 63 61 74 69 6f 6e 20 76 65 72 69 66 79 46 69 74 |cation verifyFit|
00002210 28 29 0a 7b 0a 20 20 50 72 6f 67 72 61 6d 6d 65 |().{. Programme|
00002220 4c 69 73 74 20 70 4c 2c 20 6c 61 73 74 5f 70 4c |List pL, last_pL|
00002230 20 3d 20 4e 55 4c 4c 3b 0a 20 20 50 72 6f 67 72 | = NULL;. Progr|
00002240 61 6d 6d 65 20 70 3b 0a 20 20 62 6f 6f 6c 65 61 |amme p;. boolea|
00002250 6e 20 2a 63 6f 6e 73 69 64 65 72 65 64 3b 0a 20 |n *considered;. |
00002260 20 69 6e 74 20 69 2c 20 6c 61 73 74 5f 74 79 70 | int i, last_typ|
00002270 65 20 3d 20 2d 31 3b 0a 20 20 62 6f 6f 6c 65 61 |e = -1;. boolea|
00002280 6e 20 76 6f 69 64 5f 74 79 70 65 20 3d 20 66 61 |n void_type = fa|
00002290 6c 73 65 3b 0a 0a 20 20 2f 2a 20 63 68 65 63 6b |lse;.. /* check|
000022a0 20 63 61 74 65 67 6f 72 69 65 73 20 2a 2f 0a 0a | categories */..|
000022b0 20 20 63 6f 6e 73 69 64 65 72 65 64 20 3d 20 63 | considered = c|
000022c0 61 6c 6c 6f 63 28 6e 75 6d 62 65 72 5f 63 61 74 |alloc(number_cat|
000022d0 65 67 6f 72 69 65 73 2b 31 2c 73 69 7a 65 6f 66 |egories+1,sizeof|
000022e0 28 62 6f 6f 6c 65 61 6e 29 29 3b 0a 20 20 66 6f |(boolean));. fo|
000022f0 72 20 28 69 20 3d 20 30 3b 20 69 20 3c 3d 20 6e |r (i = 0; i <= n|
00002300 75 6d 62 65 72 5f 63 61 74 65 67 6f 72 69 65 73 |umber_categories|
00002310 3b 20 69 2b 2b 29 0a 20 20 7b 0a 20 20 20 20 63 |; i++). {. c|
00002320 6f 6e 73 69 64 65 72 65 64 5b 69 5d 20 3d 20 66 |onsidered[i] = f|
00002330 61 6c 73 65 3b 0a 20 20 7d 0a 0a 20 20 66 6f 72 |alse;. }.. for|
00002340 20 28 70 4c 20 3d 20 70 4c 69 73 74 5f 68 65 61 | (pL = pList_hea|
00002350 64 3b 20 70 4c 20 21 3d 20 4e 55 4c 4c 3b 20 70 |d; pL != NULL; p|
00002360 4c 20 3d 20 70 4c 2d 3e 6e 65 78 74 29 0a 20 20 |L = pL->next). |
00002370 7b 0a 20 20 20 20 70 20 3d 20 70 4c 2d 3e 70 72 |{. p = pL->pr|
00002380 6f 67 72 61 6d 6d 65 3b 0a 20 20 20 20 69 66 20 |ogramme;. if |
00002390 28 70 2d 3e 74 79 70 65 20 21 3d 20 4e 55 4c 4c |(p->type != NULL|
000023a0 20 26 26 20 63 6f 6e 73 69 64 65 72 65 64 5b 70 | && considered[p|
000023b0 2d 3e 74 79 70 65 2d 3e 6e 75 6d 62 65 72 5d 29 |->type->number])|
000023c0 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 66 72 65 |. {. fre|
000023d0 65 28 63 6f 6e 73 69 64 65 72 65 64 29 3b 0a 20 |e(considered);. |
000023e0 20 20 20 20 20 72 65 74 75 72 6e 20 28 62 61 64 | return (bad|
000023f0 63 6c 61 73 73 29 3b 0a 20 20 20 20 7d 0a 20 20 |class);. }. |
00002400 20 20 69 66 20 28 70 2d 3e 74 79 70 65 20 3d 3d | if (p->type ==|
00002410 20 4e 55 4c 4c 29 0a 20 20 20 20 7b 0a 20 20 20 | NULL). {. |
00002420 20 20 20 76 6f 69 64 5f 74 79 70 65 20 3d 20 74 | void_type = t|
00002430 72 75 65 3b 0a 20 20 20 20 7d 0a 20 20 20 20 65 |rue;. }. e|
00002440 6c 73 65 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 |lse. {. |
00002450 69 66 20 28 70 2d 3e 74 79 70 65 2d 3e 6e 75 6d |if (p->type->num|
00002460 62 65 72 20 3d 3d 20 6c 61 73 74 5f 74 79 70 65 |ber == last_type|
00002470 20 26 26 20 76 6f 69 64 5f 74 79 70 65 29 0a 20 | && void_type). |
00002480 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 66 | {. f|
00002490 72 65 65 28 63 6f 6e 73 69 64 65 72 65 64 29 3b |ree(considered);|
000024a0 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 |. return |
000024b0 28 62 61 64 63 6c 61 73 73 29 3b 0a 20 20 20 20 |(badclass);. |
000024c0 20 20 7d 0a 20 20 20 20 20 20 76 6f 69 64 5f 74 | }. void_t|
000024d0 79 70 65 20 3d 20 66 61 6c 73 65 3b 0a 20 20 20 |ype = false;. |
000024e0 20 7d 0a 20 20 20 20 69 66 20 28 70 2d 3e 74 79 | }. if (p->ty|
000024f0 70 65 20 21 3d 20 4e 55 4c 4c 20 26 26 20 70 2d |pe != NULL && p-|
00002500 3e 74 79 70 65 2d 3e 6e 75 6d 62 65 72 20 21 3d |>type->number !=|
00002510 20 6c 61 73 74 5f 74 79 70 65 20 26 26 20 6c 61 | last_type && la|
00002520 73 74 5f 74 79 70 65 20 21 3d 20 2d 31 29 0a 20 |st_type != -1). |
00002530 20 20 20 7b 0a 20 20 20 20 20 20 63 6f 6e 73 69 | {. consi|
00002540 64 65 72 65 64 5b 6c 61 73 74 5f 74 79 70 65 5d |dered[last_type]|
00002550 20 3d 20 74 72 75 65 3b 0a 20 20 20 20 7d 0a 0a | = true;. }..|
00002560 20 20 20 20 69 66 20 28 70 2d 3e 74 79 70 65 20 | if (p->type |
00002570 21 3d 20 4e 55 4c 4c 29 0a 20 20 20 20 7b 0a 20 |!= NULL). {. |
00002580 20 20 20 20 20 6c 61 73 74 5f 74 79 70 65 20 3d | last_type =|
00002590 20 70 2d 3e 74 79 70 65 2d 3e 6e 75 6d 62 65 72 | p->type->number|
000025a0 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 0a 20 20 66 |;. }. }.. f|
000025b0 72 65 65 28 63 6f 6e 73 69 64 65 72 65 64 29 3b |ree(considered);|
000025c0 0a 0a 20 20 2f 2a 20 63 68 65 63 6b 20 67 72 6f |.. /* check gro|
000025d0 75 70 73 20 28 27 70 72 65 63 65 64 65 73 27 20 |ups ('precedes' |
000025e0 61 6e 64 20 27 66 6f 6c 6c 6f 77 73 27 29 20 2a |and 'follows') *|
000025f0 2f 0a 0a 20 20 66 6f 72 20 28 70 4c 20 3d 20 70 |/.. for (pL = p|
00002600 4c 69 73 74 5f 68 65 61 64 3b 20 70 4c 20 21 3d |List_head; pL !=|
00002610 20 4e 55 4c 4c 3b 20 70 4c 20 3d 20 70 4c 2d 3e | NULL; pL = pL->|
00002620 6e 65 78 74 29 0a 20 20 7b 0a 20 20 20 20 70 20 |next). {. p |
00002630 3d 20 70 4c 2d 3e 70 72 6f 67 72 61 6d 6d 65 3b |= pL->programme;|
00002640 0a 0a 20 20 20 20 69 66 20 28 70 2d 3e 70 72 65 |.. if (p->pre|
00002650 63 65 64 65 73 20 21 3d 20 4e 55 4c 4c 29 0a 20 |cedes != NULL). |
00002660 20 20 20 7b 0a 20 20 20 20 20 20 69 66 20 28 70 | {. if (p|
00002670 4c 2d 3e 6e 65 78 74 20 3d 3d 20 4e 55 4c 4c 29 |L->next == NULL)|
00002680 0a 20 20 20 20 20 20 7b 0a 20 20 20 20 20 20 20 |. {. |
00002690 20 72 65 74 75 72 6e 20 28 62 61 64 70 72 65 63 | return (badprec|
000026a0 65 64 65 73 29 3b 0a 20 20 20 20 20 20 7d 0a 20 |edes);. }. |
000026b0 20 20 20 20 20 69 66 20 28 73 74 72 63 6d 70 28 | if (strcmp(|
000026c0 70 2d 3e 70 72 65 63 65 64 65 73 2c 70 4c 2d 3e |p->precedes,pL->|
000026d0 6e 65 78 74 2d 3e 70 72 6f 67 72 61 6d 6d 65 2d |next->programme-|
000026e0 3e 6e 61 6d 65 29 20 21 3d 20 30 29 0a 20 20 20 |>name) != 0). |
000026f0 20 20 20 7b 0a 20 20 20 20 20 20 20 20 72 65 74 | {. ret|
00002700 75 72 6e 20 28 62 61 64 70 72 65 63 65 64 65 73 |urn (badprecedes|
00002710 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 7d |);. }. }|
00002720 0a 20 20 20 20 69 66 20 28 70 2d 3e 66 6f 6c 6c |. if (p->foll|
00002730 6f 77 73 20 21 3d 20 4e 55 4c 4c 29 0a 20 20 20 |ows != NULL). |
00002740 20 7b 0a 20 20 20 20 20 20 69 66 20 28 6c 61 73 | {. if (las|
00002750 74 5f 70 4c 20 3d 3d 20 4e 55 4c 4c 29 0a 20 20 |t_pL == NULL). |
00002760 20 20 20 20 7b 0a 20 20 20 20 20 20 20 20 72 65 | {. re|
00002770 74 75 72 6e 20 28 62 61 64 66 6f 6c 6c 6f 77 73 |turn (badfollows|
00002780 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 |);. }. |
00002790 20 69 66 20 28 73 74 72 63 6d 70 28 70 2d 3e 66 | if (strcmp(p->f|
000027a0 6f 6c 6c 6f 77 73 2c 6c 61 73 74 5f 70 4c 2d 3e |ollows,last_pL->|
000027b0 70 72 6f 67 72 61 6d 6d 65 2d 3e 6e 61 6d 65 29 |programme->name)|
000027c0 20 21 3d 20 30 29 0a 20 20 20 20 20 20 7b 0a 20 | != 0). {. |
000027d0 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 28 62 | return (b|
000027e0 61 64 66 6f 6c 6c 6f 77 73 29 3b 0a 20 20 20 20 |adfollows);. |
000027f0 20 20 7d 0a 20 20 20 20 7d 0a 0a 20 20 20 20 6c | }. }.. l|
00002800 61 73 74 5f 70 4c 20 3d 20 70 4c 3b 0a 20 20 7d |ast_pL = pL;. }|
00002810 0a 0a 20 20 72 65 74 75 72 6e 20 28 76 61 6c 69 |.. return (vali|
00002820 64 29 3b 0a 7d 0a |d);.}.|
00002826 
.