Xref: utzoo comp.lang.pascal:3966 comp.sys.ibm.pc:54384
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!usc!chaph.usc.edu!aludra.usc.edu
From: ajayshah@aludra.usc.edu (Ajay Shah)
Newsgroups: comp.lang.pascal,comp.sys.ibm.pc
Subject: (Source) Program to put a set of files on as few floppies a.p.
Message-ID: <11550@chaph.usc.edu>
Date: 21 Aug 90 06:14:34 GMT
Sender: news@chaph.usc.edu
Followup-To: comp.lang.pascal
Organization: University of Southern California, Los Angeles, CA
Lines: 317
Nntp-Posting-Host: aludra.usc.edu
Originator: ajayshah@aludra.usc.edu


This program takes on StdIn a list of file names and sizes.

It generates on StdOut a IBM PC batch file with the appropriate
noises so as to backup these files over many floppies.  It makes
assumptions about the capacity of your floppy drive and it's name
(a: or b: or whatever); these are hardcoded in a set of constant
declarations at the top, and readily altered.  There are no
command line arguments.

I call this program 'p.pas' for want of a better name.  So the
executable is p.exe. Given a list of files (demo below) in file
flist, you'd say

	$ p < flist > docopy.bat

and dcopy.bat is ready-to-run.  On the StdErr stream, p tells you
the number of floppies he'll need.  I believe the algorithm used
guarantees that there is no alternative layout of files over
floppies which could consume fewer floppies.  Tell me if i'm
wrong!.  (My intuitive justification uses the analogy between
this algorithm and dynamic programming).

Now insert the first floppy into the relevant drive and say

	$ dcopy

and the deed is done.  The most convenient way to generate the
input file (flist above) is to say something like 

	$ ls -la | gawk '{print $NF " " $4}' > flist

or so.  The best solution, of course, is

	$ ls -la | gawk '{print $NF " " $4}' | p > flist
	$ flist


(Am I using DOS or Unix?  I boot DOS 3.31 with the bourne shell
v1.62 and my \bin contains it's associated package of Unix tools 
and the GNU Awk.  Awk.  Never leave home without it.)

---------------------------------------------------------------------------

E.g., given this input

bibtex.zip 119242
blatex.zip 261357
bmf1.zip 266516
bmf2.zip 274272
btex1.zip 265158
btex2.zip 281372
changes 10153
delete.exe 31837
dvidrv1.zip 99441
dvidrv2.zip 342592
dvidrv3.zip 294915
dvidrvma.zip 99444
emsy.zip 7547
help 16987
latex1.zip 248725
latex2.zip 219596
latexdoc.zip 109357
makeindx.zip 50016
mf1.zip 249894
mf2.zip 341071
mf3.zip 278545
mfware1.zip 320774
mfware2.zip 137079
misc_mf.zip 36790
pcdvips1.zip 243867
pcdvips2.zip 333526
pictex.zip 43915
pkedit.zip 52014
readme 90190
readme.ans 349
remove.exe 58474
tex1.zip 360068
tex2.zip 267004
texcad.zip 116865
texware.zip 270391
web.zip 132469

it generates

xcopy web.zip b:
xcopy texware.zip b:
xcopy texcad.zip b:
xcopy tex2.zip b:
xcopy tex1.zip b:
xcopy remove.exe b:
xcopy readme.ans b:
xcopy readme b:
xcopy pkedit.zip b:
xcopy pictex.zip b:
xcopy misc_mf.zip b:
xcopy emsy.zip b:
echo Wasted space = 3588
echo Insert next disk..
pause
xcopy pcdvips2.zip b:
xcopy pcdvips1.zip b:
xcopy mfware2.zip b:
xcopy mfware1.zip b:
xcopy mf3.zip b:
xcopy makeindx.zip b:
xcopy help b:
xcopy delete.exe b:
xcopy changes b:
echo Wasted space = 21380
echo Insert next disk..
pause
xcopy mf2.zip b:
xcopy mf1.zip b:
xcopy latexdoc.zip b:
xcopy latex2.zip b:
xcopy latex1.zip b:
xcopy dvidrvma.zip b:
xcopy dvidrv1.zip b:
echo Wasted space = 79636
echo Insert next disk..
pause
xcopy dvidrv3.zip b:
xcopy dvidrv2.zip b:
xcopy btex2.zip b:
xcopy btex1.zip b:
xcopy bmf1.zip b:
echo Wasted space = -389
echo Insert next disk..
pause
xcopy bmf2.zip b:
xcopy blatex.zip b:
xcopy bibtex.zip b:
echo Wasted space = 798293
echo Insert next disk..
pause

---------------------------------------------------------------------------
No, that -389 above is not a rotten bug.  Start of source:

program packfiles;

{Given a list of filenames and file sizes, this program writes a
batch file which optimally backs up these files over a set of
floppies.  "Optimally" == as few floppies as possible.}

const
	MaxFiles = 500; {there are memory constriants}
	disk_limit:longint = 1457664; {3.5" HD}
	target : string = 'b:'; {destination drive}
        SAFETY = 1500;
        {This is my assumed wastage of space per file on disk
         (owing to large clusters)}

type
	fnstring = string[65];
	onefile = record
		fname : fnstring;
		fsize : longint;
		taken : boolean;
	end;

	FListType = array[1..MaxFiles] of onefile;

procedure Pack(N:integer; var flist:FListType);

	function find(max:longint):integer;
	type
		Candidate = record
			index : 1..MaxFiles;
			size : longint
		end;
	var
		C: array[1..MaxFiles] of Candidate;
		i, num : integer;
		tmpC : Candidate;
		nochange : boolean;
	begin
		num := 0;
		for i := 1 to N do
			if not flist[i].taken then
				if flist[i].fsize <= max then
				begin
					inc(num);
					C[num].index := i;
					C[num].size := flist[i].fsize
				end;

		if num = 0 then {no file small enough found.}
		begin
			find := 0; exit
		end;

		{Now bubblesort C}
		repeat
			nochange := true;
			for i := 1 to num-1 do
				if C[i].size > C[i+1].size then
				begin
					tmpC := C[i];
					C[i] := C[i+1];
					C[i+1] := C[i];
					nochange := false
				end;
		until nochange;
		find := C[num].index {index of largest file of list}
	end;

	procedure TakeOneDisk(var num:integer);
	var
		done : boolean;
		remaining : longint;
                newfile : integer;
	begin
		num := 0;
		done := false;
		remaining := disk_limit;
		repeat
			newfile := find(remaining);
			if newfile <> 0 then {he found a file}
				with flist[newfile] do
				begin
					writeln('xcopy ', fname, ' b:');
					taken := true;
					remaining := remaining - fsize - SAFETY;
					inc(num)
				end
			else {no file which fits in remaining}
				done := true
		until done;
		writeln('echo Wasted space = ', remaining);
		
	end;

var
   taken, thisdisk : integer;
   diskcount : integer;
   f : text;
begin
	taken := 0; diskcount := 0;
	repeat
		TakeOneDisk(thisdisk);
                taken := taken + thisdisk;
                inc(diskcount);
                if taken <> N then
                begin
                     writeln('echo Insert next disk..');
		     writeln('pause')
                end;
	until taken = N;
        assign(f, 'con'); rewrite(f);
        writeln(f, 'Totally ', diskcount, ' disks needed.');
        writeln(f, '(This assumed disks of capacity ', disk_limit, ' each.)')
end;

procedure Parse(s:string;
		var fname:fnstring;
                var size:longint);
var
   num:integer;
   error : integer;
begin
     if length(s) = 0 then
     begin
          writeln('Illegal (blank) line on StdIn.');
          halt(1)
     end;
     while s[1] = ' ' do delete(s, 1, 1);
     while s[length(s)] = ' ' do delete(s, length(s), 1);
     num := length(s);
     repeat
           dec(num)
     until s[num] = ' ';
     fname := copy(s, 1, num-1);
     val(copy(s, num+1, length(s)), size, error);
     if error <> 0 then
     begin
          writeln('Numeric Format Error in file size of this line: ');
          writeln;
          writeln(s);
          writeln;
          halt(1)
     end
end;


var
	files : FListType;
	num : integer;
        s : string;

begin
	num := 0;
	repeat
		inc(num);
		with files[num] do
		begin
                	readln(s);
			Parse(s, fname, fsize);
			if fsize > disk_limit then
			begin
				writeln('ERROR:');
				writeln('File ', fname, ' is too large');
				writeln('for disks of capacity ', disk_limit, '.');
				halt(1)
			end;
                        taken := false;
		end
	until seekeof;
	Pack(num, files)
end.

-- 
_______________________________________________________________________________
Ajay Shah, (213)747-9991, ajayshah@usc.edu
                              The more things change, the more they stay insane.
_______________________________________________________________________________