.TH squeeze 1
.SH NAME
\fBsqueeze\fR - Finds the best subset, of the specified files, which fits into a given space.
.SH SYNOPSIS
\fBsqueeze\fR [\fIOPTIONS\fR] [\fIFile-path\fR ...]
.SH DESCRIPTION
.PP
Finds the subset of the specified \fIFile-path\fRs, which fits into the specified \fIBytes\fR, with least room to spare, whilst meeting \fBminimumUsageRatio\fR.
.PP
Any directories amongst the specified \fIFile-path\fRs are treated as atomic units, & therefore only solutions which involve either all or none of the files contained, are returned.
.PP
Because of its exponential time-complexity, solutions of increasing suitability are continuously returned, rather than waiting until the optimal solution is known (which might take an inordinately long time).
.SH OPTIONS
.SS "Selection"
.TP
\fB-b\fR, \fB--bisectionRatio='\fR\fILHS%Total\fR\fB'\fR
Defines the ratio (in the closed unit-interval [0,1], defaulting to '\fB1%2\fR', i.e. 50%), @ which the list of file-paths will be bisected.
The first of the combinations generated from the first list, is then concatenated with each of the combinations generated from the second list.
The same operation is then performed on subsequent combinations generated from the first list.
This alters the order in which file-combinations are assessed, & so the set of suitable combinations returned may differ, though the optimum value remains the same.
.TP
\fB-M\fR, \fB--maximumBytes=\fR\fIBytes\fR
Defines the maximum available space, in bytes; defaulting to the space available on a DVD, i.e. \fB4700000000\fR bytes.
.TP
\fB-m\fR, \fB--minimumUsageRatio='\fR\fIRational\fR\fB'\fR
Defines the minimum acceptable usage-ratio (in the closed unit-interval [0,1], defaulting to '\fB99%100\fR', i.e. 99%), of \fBmaximumBytes\fR.
.TP
\fB-z\fR, \fB--includeEmpty=\fR\fIBool\fR
When \fBTrue\fR, any empty file or directory, can be a member of all solutions.
.br
CAVEAT: for \fIn\fR such files or directories, a factor of \fI2^n\fR more viable solutions exist, obscuring the minimal solutions on which they're based.
.SS Test
.TP
\fB-q\fR, \fB--runQuickChecks\fR
Uses \fBQuickCheck\fR to validate invariant properties, using arbitrary data ... & then exits.
.TP
\fB--testPerformance='(\fR\fIInteger\fR\fB,\fR \fBPoissonDistribution\fR \fIlambda\fR\fB)'\fR
Measures the CPU-time required to find the best fit,
for the specified number of randomly generated virtual files,
the size of which conform to the specified probability-distribution,
& the names of which reflect their size ... & then exits.
.TP
\fB--graphPerformance='\fR\fBPoissonDistribution\fR \fIlambda\fR\fB'\fR
Measures the CPU-time required to find the best fit,
for a linearly increasing number of randomly generated virtual files,
the size of which conform to the specified probability-distribution,
& the names of which reflect their size.
.br
Doesn't normally terminate.
.TP
\fB-v\fR, \fB--verbose\fR
Produces additional explanatory output where appropriate.
.br
This option, if required, may need to precede other options.
.SS "Generic Program-information"
.TP
.B --version
Outputs version-information & then exits.
.TP
\fB-?\fR, \fB--help\fR
Displays help & then exits.
.SS "File-paths"
.TP
If \fIFile-path\fR is a single hyphen-minus (\fB-\fR), replace it with the list of file-paths read from standard-input.
.SH EXIT-STATUS
\fB0\fR on success, & >\fB0\fR if an error occurs.
.SH EXAMPLES
.SS Trial 1
Say we've a directory of audio-files, categorised by artist.
.TP
\fBls -p\fR
ArabStrap/ BobDylan/ JeffBuckley/ JohnMartyn/ JoniMitchell/ ReservoirDogsOST/ RichardThompson/ SethLakeman/ SusheelaRaman/ TeddyThompson/ Vangelis/
.PP
.nf
\fBsqueeze -M 700000000 -m '999%1000' *\fR
	699871313	["BobDylan","RichardThompson","SethLakeman","TeddyThompson"]
	699893320	["ArabStrap","BobDylan","JeffBuckley","JohnMartyn","SethLakeman","SusheelaRaman"]
	\fI699998310\fR	["ArabStrap","BobDylan","JoniMitchell","ReservoirDogsOST","SethLakeman","TeddyThompson","Vangelis"]
.fi
.PP 
Note that the proposed solutions don't split any of the directories, into their constituent files.
.PP
We can confirm the validity of the optimal result:
.PP
.nf
\fBfind ArabStrap BobDylan JoniMitchell ReservoirDogsOST SethLakeman TeddyThompson Vangelis -type f -print | perl -e 'use List::Util qw(sum); printf(qq(%d\\n), sum map { chomp; (stat)[7] } <>);'\fR
	699998310
.fi
.PP
NB: \fBdu\fR will return a slightly larger size, since it includes the space required for directory-structures.
.SS Trial 2
We can improve on that result if we're prepared to split some of the artist-specific directories into individual albums.
.PP
.nf
\fBsqueeze -M 700000000 -m '99999%100000' ArabStrap BobDylan/* JeffBuckley JohnMartyn JoniMitchell ReservoirDogsOST RichardThompson SethLakeman SusheelaRaman TeddyThompson Vangelis\fR
	699995815	["ArabStrap","BobDylan/BlondeOnBlonde","BobDylan/Highway61Revisited","BobDylan/ModernTimes","BobDylan/StreetLegal","BobDylan/SubterraneanHomesickBlues","JoniMitchell","RichardThompson","SusheelaRaman","TeddyThompson","Vangelis"]
	699998578	["BobDylan/Desire","BobDylan/Highway61Revisited","BobDylan/Infidels","BobDylan/StreetLegal","JeffBuckley","JohnMartyn","JoniMitchell","RichardThompson","SethLakeman","SusheelaRaman","TeddyThompson","Vangelis"]
	\fI699999112\fR	["BobDylan/BlondeOnBlonde","BobDylan/Desire","BobDylan/Highway61Revisited","BobDylan/Infidels","BobDylan/ModernTimes","JeffBuckley","JohnMartyn","ReservoirDogsOST","RichardThompson","SusheelaRaman","TeddyThompson","Vangelis"]
.fi
.SS Trial 3
If we're prepared to add individual files from another artist:
.PP
.nf
\fBsqueeze -M 700000000 -m '9999999%10000000' ArabStrap  BobDylan/*  JeffBuckley  JohnMartyn  JoniMitchell  ReservoirDogsOST  $(find RichardThompson -type f)  SethLakeman  SusheelaRaman  TeddyThompson  Vangelis\fR
	699999964	["ArabStrap","BobDylan/Desire","BobDylan/Infidels","BobDylan/ModernTimes","BobDylan/OhMercy","BobDylan/SubterraneanHomesickBlues","BobDylan/TimeOutOfMind","JeffBuckley","JohnMartyn","JoniMitchell","ReservoirDogsOST","RichardThompson/FrontParlourBallads/RichardThompson-06-MySoulMySoul.ogg","RichardThompson/RumorAndSigh/RichardThompson-12-MotherKnowsBest.ogg","RichardThompson/TheOldKitBag/RichardThompson-01-Gethsemane.ogg","RichardThompson/TheOldKitBag/RichardThompson-11-OutsideOfTheInside.ogg","SethLakeman","SusheelaRaman","TeddyThompson","Vangelis"]
	699999987	["BobDylan/BlondeOnBlonde","BobDylan/BloodOnTheTracks","BobDylan/Desire","BobDylan/ModernTimes","BobDylan/OhMercy","BobDylan/StreetLegal","BobDylan/SubterraneanHomesickBlues","BobDylan/TimeOutOfMind","JoniMitchell","ReservoirDogsOST","RichardThompson/FrontParlourBallads/RichardThompson-01-LetItBlow.ogg","RichardThompson/IWantToSeeTheBrightLightsTonight/RichardAndLindaThompson-13-TheCalvaryCross[Live-Bonus].ogg","RichardThompson/TheOldKitBag/RichardThompson-01-Gethsemane.ogg","RichardThompson/TheOldKitBag/RichardThompson-06-FirstBreath.ogg","RichardThompson/TheOldKitBag/RichardThompson-11-OutsideOfTheInside.ogg","SethLakeman","SusheelaRaman","TeddyThompson","Vangelis"]
	\fI700000000\fR	["ArabStrap","BobDylan/Desire","BobDylan/Highway61Revisited","BobDylan/Infidels","BobDylan/ModernTimes","BobDylan/StreetLegal","BobDylan/SubterraneanHomesickBlues","BobDylan/TimeOutOfMind","JeffBuckley","JoniMitchell","ReservoirDogsOST","RichardThompson/FrontParlourBallads/RichardThompson-01-LetItBlow.ogg","RichardThompson/RumorAndSigh/RichardThompson-08-BacklashLoveAffair.ogg","RichardThompson/RumorAndSigh/RichardThompson-12-MotherKnowsBest.ogg","RichardThompson/TheOldKitBag/RichardThompson-01-Gethsemane.ogg","RichardThompson/TheOldKitBag/RichardThompson-04-ALoveYouCantSurvive.ogg","RichardThompson/TheOldKitBag/RichardThompson-06-FirstBreath.ogg","SusheelaRaman","TeddyThompson","Vangelis"]
.fi
.PP
^C
.PP
The exact match isn't unexpected, given the 2^71 possible combinations.
The process was terminated after this solution was found, though where time permits, one may choose to wait for alternative exact matches.
.SH AUTHOR
Written by Dr. Alistair Ward.
.SH BUGS
.SS "REPORTING BUGS"
Report bugs to \fBsqueeze\fR \fIat\fR \fBfunctionalley\fR \fIdot\fR \fBeu\fR
.SH COPYRIGHT
Copyright \(co 2010 Dr. Alistair Ward
.PP
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 3 of the License, or (at your option) any later version.
.PP
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.
.PP
You should have received a copy of the GNU General Public License along with this program. If not, see \fB<http://www.gnu.org/licenses/>\fR.
.SH "SEE ALSO"
.IP \(bu
Home-page: \fBhttp://functionalley.eu\fR
.IP \(bu
Source-documentation is generated by \fBHaddock\fR, & is available in the distribution.
.IP \(bu
.I http://www.haskell.org/haddock/
.IP \(bu
.I http://en.wikipedia.org/wiki/QuickCheck