squeeze 1.0.1.4 → 1.0.2.0
raw patch · 18 files changed
+692/−550 lines, 18 filesdep +factorydep +randomdep −paralleldep ~toolshed
Dependencies added: factory, random
Dependencies removed: parallel
Dependency ranges changed: toolshed
Files
- changelog +17/−5
- debian/DEBIAN/control +3/−3
- makefile +5/−1
- man/man1/squeeze.1 +20/−8
- squeeze.cabal +14/−15
- squeeze.spec +1/−1
- src/Main.hs +95/−60
- src/Squeeze/CommandOptions.hs +0/−74
- src/Squeeze/Data/CommandOptions.hs +90/−0
- src/Squeeze/Data/File.hs +108/−0
- src/Squeeze/Data/FileCombination.hs +97/−0
- src/Squeeze/File.hs +0/−97
- src/Squeeze/FileCombination.hs +0/−76
- src/Squeeze/FileSizeBounds.hs +0/−56
- src/Squeeze/QC.hs +0/−80
- src/Squeeze/Squeeze.hs +112/−74
- src/Squeeze/Test/Performance.hs +49/−0
- src/Squeeze/Test/QC.hs +81/−0
changelog view
@@ -18,20 +18,32 @@ * Replaced 'Data.List.subsequences' with a tailored version which terminates combinations when they've grown too large, providing a better and more predictable performance-gain than recursive list-bisection. * Reduced recursive list-bisection to a single bisection, for the sole purpose of facilitating parallelisation. * Added module "Squeeze.QC" to define "Test.QuickCheck" tests and command-line option "--verbose", to govern level of output.- * Split of new modules; "Squeeze.File", "Squeeze.FileSizeBounds" and "Squeeze.FileCombination".+ * Partitioned into new modules; "Squeeze.File", "Squeeze.FileSizeBounds" and "Squeeze.FileCombination". 1.0.1.2- * Fixed typo in CPP-statement in 'QC.hs'.+ * Fixed typo in CPP-statement in "Squeeze.QC". * Fixed negated reference to unparenthesised CPP-macro 'MIN_VERSION'.- * Protected reference in "Main.hs", to 'Test.QuickCheck.verboseCheck', using CPP-statement.+ * Protected reference in "Main", to 'Test.QuickCheck.verboseCheck', using CPP-statement. 1.0.1.3 * Amended "squeeze.spec" to define RPM-package, to install under "/usr", rather than "/usr/local". * Renamed package from 'Squeeze' to 'squeeze', for compatibility with Debian's ".deb"-format. * Added directory-structure required to build ".deb" package. 1.0.1.4 * Corrected command-line processing of the special file "-", which read standard-input as requested, but disregarded any other command-line options.- * Refined man-page to be an 'extra-source-file' in .cabal & .spec files.- * Ported to compile against alternative integral definitions of 'File.FileSize'.+ * Refined man-page to be an 'extra-source-file' in "squeeze.cabal" and "squeeze.spec" files.+ * Ported to compile against alternative integral definitions of 'Squeeze.File.FileSize'. * Added manually controlled "llvm" flag to "squeeze.cabal". * Replaced references to the module "ToolShed.Package" with "Distribution.Package". * Reacted to the creation of module "ToolShed.Defaultable".+ * Uploaded to <http://hackage.haskell.org/packages/hackage.html>.+1.0.2.0+ * Reimplemented 'Squeeze.File.aggregateSize' using 'foldr' rather than 'foldl'.+ * Removed use of "Control.Parallel.Strategies" from "Squeeze.Squeeze", which ruined performance on one core and had no obvious benefit on two.+ * Changed the definition of 'Squeeze.FileCombinations.FileCombinations' from a 'Pair' to a record-style data-type with selective strictness-annotation.+ * Renamed 'Squeeze.FileCombination.concatenate' to '(Squeeze.FileCombination.<+>)' and 'Squeeze.FileCombination.prepend' to '(Squeeze.FileCombination.+>)'.+ * Used new module "ToolShed.TimeAction", to permit measurement of the CPU-time required to find the best fit.+ * Added the number, mean file-size and standard-deviation, to the output, when flag '--verbose' is specified; and as a side-effect, created a dependency on the package 'factory'.+ * Replaced module "Squeeze.FileSizeBounds" with "Factory.Data.Interval", requiring use of 'toolshed-0.12.0.0'.+ * Made the data-type 'CommandOptions.CommandOptions' polymorphic in terms of the /ratio/-type fields.+ * Inserted new layers "Data" and "Test" into the module-hierarchy, and relocated existing modules accordingly.+ * Added module "Squeeze.Test.Performance" to test with randomly generated virtual files.
debian/DEBIAN/control view
@@ -1,10 +1,10 @@ Package: squeeze-Version: 1.0.1.4-1+Version: 1.0.2.0-1 Section: utils Priority: optional Architecture: i386-Depends: libc6 (>= 2.3.6-6~), libgmp3c2-Installed-size: 1036+Depends: libc6 (>= 2.7)+Installed-size: 1612 Maintainer: Dr. Alistair Ward Provides: Homepage: http://functionalley.eu
makefile view
@@ -13,7 +13,7 @@ # You should have received a copy of the GNU General Public License # along with this program. If not, see <http://www.gnu.org/licenses/>. -.PHONY: all build clean clobber configure copy deb haddock help hlint install lintian prof rpm rpmlint sdist +.PHONY: all build check clean clobber configure copy deb haddock help hlint install lintian prof rpm rpmlint sdist all: install @@ -45,6 +45,9 @@ sdist: configure runhaskell Setup.hs $@ +check: sdist+ cabal upload --check --verbose=3 dist/*.tar.gz;+ rpm: squeeze.spec rpmbuild -bb -- $^ mv -- `find /usr/src/packages/ -type f -name 'squeeze*.rpm' -mtime 0 -print` ./@@ -66,6 +69,7 @@ clean: runhaskell Setup.hs $@ rm -rf 'debian/usr/' 'debian/DEBIAN/md5sums'+ find src -type f \( -name '*.o' -o -name '*.hi' \) -delete clobber: clean rm -f -- *.rpm *.deb
man/man1/squeeze.1 view
@@ -14,25 +14,37 @@ .SS "Selection" .TP \fB-b\fR, \fB--bisectionRatio=\fR\fILHS/Total\fR-Defines the ratio (in the range 0.0 .. 1.0, defaulting to 0.5), at which the file-list will be bisected.-The first combination from the LHS is then concatenated with each combination from the RHS, in parallel with the same operation on subsequent combinations from the LHS.-This option leads to a performance-gain when used on a multi-core machine, in combination with GHC-runtime flags \fB+RTS -N -H\fR\fIHEAP-SIZE\fR \fB-RTS\fR; (e.g. \fB-H100M\fR).-On a single-core machine, \fB-b0\fR is slightly faster.-Because the order in which file-combinations are assessed, depends on this ratio, the set of suitable combinations returned may differ, though the optimum value remains the same.+Defines the ratio (in the unit interval [0 .. 1], defaulting to 1/2), at which the file-list will be bisected.+The first of the combinations generated from the LHS, is then concatenated with each of the combinations generated from the RHS.+The same operation is then performed on subsequent combinations from the LHS.+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 Define 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\fIRATIO\fR Define the minimum acceptable usage-ratio of \fBmaximumBytes\fR,-from 0.0 .. 1.0, defaulting to \fB0.99\fR, i.e. 99%.+from 0 .. 1, defaulting to \fB99/100\fR, i.e. 99%. .TP \fB-q\fR, \fB--runQuickChecks\fR Run Quick-checks using arbitrary data & then exit.-Specify '\fB--verbose\fR' before this option, for additional output. .TP+\fB--testPerformance\fR='(<Int>, \fBPoissonDistribution\fR \fIlambda\fR | \fBNormalDistribution\fR \fImean\fR \fIvariance\fR)'+Measure 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 required probability-distribution,+and the names of which reflect their size, & then exit.+.TP+\fB--graphPerformance\fR='\fBPoissonDistribution\fR \fIlambda\fR | \fBNormalDistribution\fR \fImean\fR \fIvariance\fR'+Measure 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 required probability-distribution,+and the names of which reflect their size.+Doesn't normally terminate.+.TP \fB-v\fR, \fB--verbose\fR Produce additional explanatory output where appropriate.+This option, if required, may need to precede other options. .SS "Generic Program-information" .TP \fB--version\fR@@ -44,7 +56,7 @@ .TP When a \fIFILE\fR is defined as a single hyphen-minus (\fB-\fR), replace it with the list of file-names read from standard-input. .SH EXIT-STATUS-\fB0\fR on success, and >\fB0\fR if an error occurs.+\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.
squeeze.cabal view
@@ -1,6 +1,6 @@ --Package-properties Name: squeeze-Version: 1.0.1.4+Version: 1.0.2.0 Cabal-Version: >= 1.6 Copyright: (C) 2010 Dr. Alistair Ward License: GPL@@ -18,37 +18,36 @@ Data-files: Extra-Source-Files: man/man1/*.1, *.spec, changelog, copyright, debian/DEBIAN/control, makefile -flag threaded- Description: Link with the threaded runtime.- default: True- flag llvm- Description: Whether the 'llvm' backend has been installed and is required for code-generation.+ Description: Whether the 'llvm' compiler-backend has been installed and is required for code-generation. manual: True default: False Executable squeeze hs-source-dirs: src Main-Is: Main.hs- Other-modules: Squeeze.CommandOptions Squeeze.File Squeeze.FileSizeBounds Squeeze.FileCombination Squeeze.QC Squeeze.Squeeze+ Other-modules:+ Squeeze.Data.CommandOptions+ Squeeze.Data.File+ Squeeze.Data.FileCombination+ Squeeze.Squeeze+ Squeeze.Test.Performance+ Squeeze.Test.QC+ Build-depends: base == 4.*, Cabal >= 1.6 && < 2, directory,+ factory >= 0.1, filepath, haskell98, QuickCheck >= 2.4,- unix,- toolshed == 0.11.*+ random,+ toolshed >= 0.12,+ unix GHC-options: -Wall -O2 GHC-prof-options: -prof -auto-all -caf-all-- if flag(threaded)- Build-depends: parallel >= 3.0- GHC-options: -threaded -feager-blackholing- else- Build-depends: parallel if impl(ghc >= 7.0) GHC-options: -rtsopts
squeeze.spec view
@@ -7,7 +7,7 @@ Summary: Finds the optimal subset of the specified files, to fit into a limited space, with minimal wastage. Name: squeeze-Version: 1.0.1.4+Version: 1.0.2.0 Release: 1 License: GPLv3 #From '/usr/share/doc/packages/rpm/GROUPS'.
src/Main.hs view
@@ -27,40 +27,52 @@ module Main( -- * Type-classes+-- CommandOptions', -- CommandLineAction, -- * Functions main ) where import Control.Applicative((<*>), (<$>))-import qualified Control.Exception import qualified Data.List+import qualified Data.Ratio import qualified Distribution.Package import qualified Distribution.Text import qualified Distribution.Version-import qualified Squeeze.CommandOptions as CommandOptions-import qualified Squeeze.File as File-import qualified Squeeze.FileCombination as FileCombination-import qualified Squeeze.Squeeze as Squeeze-import qualified Squeeze.QC as QC+import qualified Factory.Math.Probability as Math.Probability+import qualified Squeeze.Data.CommandOptions as Data.CommandOptions+import qualified Squeeze.Data.File as Data.File+import qualified Squeeze.Squeeze as Squeeze+import qualified Squeeze.Test.Performance as Test.Performance+import qualified Squeeze.Test.QC as Test.QC import qualified System-import qualified System.Console.GetOpt as G+import qualified System.Console.GetOpt as G import qualified System.IO import qualified System.IO.Error import qualified Test.QuickCheck-import qualified ToolShed.Defaultable as Defaultable+import qualified ToolShed.Defaultable as Defaultable+import qualified ToolShed.TimeAction as TimeAction+import qualified ToolShed.SelfValidate as SelfValidate +-- | Coerce the polymorphic data-type to concrete instance, in order that it's fields may be read from the command-line.+type CommandOptions' = Data.CommandOptions.CommandOptions Data.Ratio.Rational --'Double' would also be a suitable type-parameter.+ -- | Used to thread user-defined command-line options, though the list of functions which implement them.-type CommandLineAction = (CommandOptions.CommandOptions -> IO CommandOptions.CommandOptions) --Supplied as the type-argument to 'G.OptDescr'.+type CommandLineAction = (CommandOptions' -> IO CommandOptions') --Supplied as the type-argument to 'G.OptDescr'. {- |- * Parses the command-line arguments, to determine 'CommandOptions.CommandOptions', some of which may over-ride the 'Defaultable.defaultValue'.+ * Parses the command-line arguments, to determine 'Data.CommandOptions.CommandOptions', some of which may over-ride the 'Defaultable.defaultValue'. - * Arguments following known 'CommandOptions.CommandOptions', are interpreted as file-names to consider when attempting to find a suitable fit for the specified space-constraints.+ * Any arguments which follow known 'Data.CommandOptions.CommandOptions',+ are interpreted as file-names to consider when attempting to find a suitable fit for the specified space-constraints. - * If the specified file-name is @-@, then 'System.IO.stdin' is read, to augment other non-options specified.+ * If the specified file-name is /-/, then 'System.IO.stdin' is read, to augment other non-options specified. - * Delegates the donkey-work to 'Squeeze.squeeze', then formats & prints the resulting list of candidate solutions, each at least as good as the last.+ * Delegates the donkey-work to 'Squeeze.squeeze'.+ Because this may take an inordinately long time,+ it prints the results in real time, rather than batching until the optimum has been determined.++ * If /verbose/ has been specified, prints the CPU-time used, -} main :: IO () main = do@@ -69,58 +81,75 @@ let usage :: String- usage = "Usage:\t" ++ G.usageInfo progName optDescrList ++ " [<file/directory-name>, ...]\n\nExamples:\n\t" ++ progName ++ " -M 700000000 *.ogg\t\t#Find the best-fit for the globbed file-names, into the space available on a CD.\n\t" ++ progName ++ " Directory/ *.avi +RTS -N -H100M\t#Find the best-fit, for an atomic directory & the globbed files, into the default space, (ie that available on a DVD), using multiple cores, with extra heap pre-allocated."+ usage = "Usage:\t" ++ G.usageInfo progName optDescrList ++ " [<file/directory-name>, ...]\n\nExamples:\n\t" ++ progName ++ " -M 700000000 *.ogg\t\t#Find the best-fit for the globbed file-names, into the space available on a CD." + defaultValue :: CommandOptions'+ defaultValue = Defaultable.defaultValue+ optDescrList :: [G.OptDescr CommandLineAction] optDescrList = [--- String [String] (G.ArgDescr CommandLineAction) String- G.Option "b" ["bisectionRatio"] (setBisectionRatio `G.ReqArg` "<Double>") ("To facilitate parallelization, the file-list is bisected at LHS/Total, and combinations from the LHS are concatenated in parallel with each of those from the RHS; default '" ++ show (CommandOptions.bisectionRatio Defaultable.defaultValue) ++ "'. Requires runtime-flags '+RTS -N -H100M -RTS'."),- G.Option "M" ["maximumBytes"] (setMaximumBytes `G.ReqArg` "<Int>") ("The maximum bytes of available space; default '" ++ show (CommandOptions.maximumBytes Defaultable.defaultValue) ++ "'."),- G.Option "m" ["minimumUsageRatio"] (setMinimumUsageRatio `G.ReqArg` "<Double>") ("The minimum acceptable space usage-ratio; default '" ++ show (CommandOptions.minimumUsageRatio Defaultable.defaultValue) ++ "'."),- G.Option "q" ["runQuickChecks"] (G.NoArg runQuickChecks) "Run Quick-checks using arbitrary data & then exit. Specify '--verbose' before this option, for detailed output.",- G.Option "v" ["verbose"] (G.NoArg $ return . CommandOptions.setVerbose) "Produce additional explanatory output where appropriate.",- G.Option "" ["version"] (G.NoArg $ const printVersion) "Print version-information & then exit.",- G.Option "?" ["help"] (G.NoArg $ const printUsage) "Display this help & then exit."+-- String [String] (G.ArgDescr CommandLineAction) String+ G.Option "b" ["bisectionRatio"] (setBisectionRatio `G.ReqArg` "<Ratio>") ("The file-list is bisected at LHS/Total, & combinations from the LHS, concatenated with each of those from the RHS; default '" ++ show (Data.CommandOptions.bisectionRatio defaultValue) ++ "'."),+ G.Option "M" ["maximumBytes"] (setMaximumBytes `G.ReqArg` "<Integer>") ("The maximum bytes of available space; default '" ++ show (Data.CommandOptions.maximumBytes defaultValue) ++ "'."),+ G.Option "m" ["minimumUsageRatio"] (setMinimumUsageRatio `G.ReqArg` "<Ratio>") ("The minimum acceptable space usage-ratio; default '" ++ show (Data.CommandOptions.minimumUsageRatio defaultValue) ++ "'."),+ G.Option "q" ["runQuickChecks"] (G.NoArg runQuickChecks) "Run Quick-checks using arbitrary data & then exit.",+ G.Option "" ["testPerformance"] (+ testPerformance `G.ReqArg` "(<Int>, <Factory.Math.Probability.DiscreteDistribution>)"+ ) "Test the performance, using the specified number of randomly generated virtual files, the size of which conform to the specified probability-distribution; then exit.",+ G.Option "" ["graphPerformance"] (+ graphPerformance `G.ReqArg` "<Factory.Math.Probability.DiscreteDistribution>"+ ) "Graph the performance, against a linearly increasing number of randomly generated virtual files, the size of which conform to the specified probability-distribution. Doesn't normally terminate.",+ G.Option "v" ["verbose"] (G.NoArg $ return . Data.CommandOptions.setVerbose) "Produce additional explanatory output where appropriate. CAVEAT: should precede other options.",+ G.Option "" ["version"] (G.NoArg $ const printVersion) "Print version-information, & then exit.",+ G.Option "?" ["help"] (G.NoArg $ const printUsage) "Display this help, & then exit." ] where- setBisectionRatio, setMaximumBytes, setMinimumUsageRatio :: String -> CommandLineAction- setBisectionRatio arg commandLineArgs- | ratio < 0.0 = Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("bisectionRatio='" ++ arg ++ "' must be >= 0.0") Nothing Nothing- | ratio > 1.0 = Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("bisectionRatio='" ++ arg ++ "' must be <= 1.0") Nothing Nothing- | otherwise = return {-to IO-monad-} commandLineArgs {CommandOptions.bisectionRatio = ratio}- where- ratio = read arg+ setBisectionRatio, setMaximumBytes, setMinimumUsageRatio, testPerformance, graphPerformance :: String -> CommandLineAction+ setBisectionRatio arg commandOptions = return {-to IO-monad-} commandOptions {Data.CommandOptions.bisectionRatio = read arg}+ setMaximumBytes arg commandOptions = return {-to IO-monad-} commandOptions {Data.CommandOptions.maximumBytes = read arg}+ setMinimumUsageRatio arg commandOptions = return {-to IO-monad-} commandOptions {Data.CommandOptions.minimumUsageRatio = read arg} - setMaximumBytes arg commandLineArgs- | bytes <= 0 = Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("maximumBytes='" ++ arg ++ "' must be > 0") Nothing Nothing- | otherwise = return {-to IO-monad-} commandLineArgs {CommandOptions.maximumBytes = bytes}+ testPerformance arg commandOptions = if not $ SelfValidate.isValid commandOptions+ then error $ "Invalid " ++ show commandOptions+ else do+ TimeAction.printCPUSeconds $ Test.Performance.run commandOptions fileCount probabilityDistribution >>= mapM_ print++ System.exitWith System.ExitSuccess where- bytes = read arg+ fileCount :: Int+ probabilityDistribution :: Math.Probability.DiscreteDistribution Double+ (fileCount, probabilityDistribution) = read arg - setMinimumUsageRatio arg commandLineArgs- | ratio < 0.0 = Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("minimumUsageRatio='" ++ arg ++ "' must be >= 0.0") Nothing Nothing- | ratio > 1.0 = Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("minimumUsageRatio='" ++ arg ++ "' must be <= 1.0") Nothing Nothing- | otherwise = return {-to IO-monad-} commandLineArgs {CommandOptions.minimumUsageRatio = ratio}+ graphPerformance arg commandOptions = if not $ SelfValidate.isValid commandOptions+ then error $ "Invalid " ++ show commandOptions+ else do+ mapM_ (\fileCount -> TimeAction.printCPUSeconds $ Test.Performance.run commandOptions fileCount probabilityDistribution >>= mapM_ print) [1 ..]++ System.exitWith $ System.ExitFailure 1 where- ratio = read arg+ probabilityDistribution :: Math.Probability.DiscreteDistribution Double+ probabilityDistribution = read arg - runQuickChecks :: CommandOptions.CommandOptions -> IO CommandOptions.CommandOptions- runQuickChecks commandOptions = QC.quickChecks (- if CommandOptions.verbose commandOptions- then+ runQuickChecks :: (Num f, Ord f) => Data.CommandOptions.CommandOptions f -> IO (Data.CommandOptions.CommandOptions f)+ runQuickChecks commandOptions = if not $ SelfValidate.isValid commandOptions+ then error $ "Invalid " ++ show commandOptions+ else do+ Test.QC.quickChecks $ if Data.CommandOptions.verbose commandOptions+ then #if MIN_VERSION_QuickCheck(2,4,0)- Test.QuickCheck.verboseCheck+ Test.QuickCheck.verboseCheck #else- error "'Test.QuickCheck.verboseCheck' is only available as of 'QuickCheck-2.4'."+ error "'Test.QuickCheck.verboseCheck' is only available as of 'QuickCheck-2.4'." #endif- else Test.QuickCheck.quickCheck- ) >> System.exitWith System.ExitSuccess+ else Test.QuickCheck.quickCheck - printVersion, printUsage :: IO CommandOptions.CommandOptions+ System.exitWith System.ExitSuccess++ printVersion, printUsage :: IO (Data.CommandOptions.CommandOptions f) printVersion = System.IO.hPutStrLn System.IO.stderr (Distribution.Text.display packageIdentifier ++ "\n\nCopyright (C) 2010 Dr. Alistair Ward.\nThis program comes with ABSOLUTELY NO WARRANTY.\nThis is free software, and you are welcome to redistribute it under certain conditions.\n\nWritten by Dr. Alistair Ward.") >> System.exitWith System.ExitSuccess where packageIdentifier :: Distribution.Package.PackageIdentifier packageIdentifier = Distribution.Package.PackageIdentifier { Distribution.Package.pkgName = Distribution.Package.PackageName "squeeze",- Distribution.Package.pkgVersion = Distribution.Version.Version [1, 0, 1, 4] []+ Distribution.Package.pkgVersion = Distribution.Version.Version [1, 0, 2, 0] [] } printUsage = System.IO.hPutStrLn System.IO.stderr usage >> System.exitWith System.ExitSuccess@@ -132,18 +161,24 @@ return {-to IO-monad-} Defaultable.defaultValue ) {-transform using CommandLineAction-mutators-} commandLineActions --ie: do o1 <- CommandLineAction[0] commandOptions[0]; o2 <- CommandLineAction[1] o1; ... - mapM_ (putStrLn . (`FileCombination.showFileCombination` "")) =<< Squeeze.squeeze commandOptions =<< if null nonOptions- then Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.doesNotExistErrorType "No files specified" Nothing Nothing- else {-files specified-} if "-" `elem` nonOptions- then let- getFilePaths :: IO File.FilePathList- getFilePaths = do- eof <- System.IO.isEOF+ if not $ SelfValidate.isValid commandOptions+ then error $ "Invalid " ++ show commandOptions+ else (+ if Data.CommandOptions.verbose commandOptions+ then TimeAction.printCPUSeconds+ else id+ ) $ mapM_ print {-print immediately rather than batching-} =<< Squeeze.squeeze commandOptions =<< if null nonOptions+ then error "No files specified."+ else if "-" `elem` nonOptions+ then let+ getFilePaths :: IO Data.File.FilePathList+ getFilePaths = do+ eof <- System.IO.isEOF - if eof- then return {-to IO-monad-} []- else {-more to read-} (:) <$> getLine <*> getFilePaths {-recurse-}- in (filter (/= "-") nonOptions ++) <$> getFilePaths- else {-real fileNames-} return {-to IO-monad-} nonOptions+ if eof+ then return {-to IO-monad-} []+ else {-more to read-} (:) <$> getLine <*> getFilePaths {-recurse-}+ in (filter (/= "-") nonOptions ++) <$> getFilePaths+ else {-real fileNames-} return {-to IO-monad-} nonOptions (_, _, errors) -> System.IO.Error.ioError . System.IO.Error.userError $ concatMap init {-chop-} errors
− src/Squeeze/CommandOptions.hs
@@ -1,74 +0,0 @@-{-- Copyright (C) 2010 Dr. Alistair Ward-- 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.-- 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, see <http://www.gnu.org/licenses/>.--}-{- |- [@AUTHOR@] Dr. Alistair Ward-- [@DESCRIPTION@]-- * Defines options for program-operation, which are expected to be set from the command-line.-- * Defines appropriate default values.--}--module Squeeze.CommandOptions(--- * Types--- ** Data-types- CommandOptions(--- MkCommandOptions,- bisectionRatio,- maximumBytes,- minimumUsageRatio,- verbose- ),--- * Functions- fileSizeBounds,- minimumBytes,- setVerbose-) where--import qualified Squeeze.File as File-import qualified Squeeze.FileSizeBounds as FileSizeBounds-import qualified ToolShed.Defaultable as Defaultable---- | Declare a record used to contain command-line options.-data CommandOptions = MkCommandOptions {- bisectionRatio :: Double, -- ^ To facilitate parallelization, the file-list is bisected at LHS/Total, and combinations from the LHS are concatenated in parallel with each of those from the RHS.- maximumBytes :: File.FileSize, -- ^ The maximum space (in bytes) available in which to store a subset of the specified files.- minimumUsageRatio :: Double, -- ^ The minimum acceptable usage of 'maximumBytes'.- verbose :: Bool -- ^ The minimum acceptable usage of 'maximumBytes'.-}--instance Defaultable.Defaultable CommandOptions where- defaultValue = MkCommandOptions {- bisectionRatio = 0.5, --Setting this this option to 'Nothing', will prevent parallelization, but will return solutions in a more predictable order.- maximumBytes = 4700000000, --DVD-size; just under 4.4GiB.- minimumUsageRatio = 0.99, --99% full.- verbose = False- }---- | Derives the minimum number of bytes, from other options.-minimumBytes :: CommandOptions -> File.FileSize-minimumBytes commandOptions = floor $ minimumUsageRatio commandOptions * fromIntegral (maximumBytes commandOptions)---- | The permissible bounds on the size of a file, or set of files.-fileSizeBounds :: CommandOptions -> FileSizeBounds.FileSizeBounds-fileSizeBounds commandOptions = (minimumBytes commandOptions, maximumBytes commandOptions)---- | Mutator.-setVerbose :: CommandOptions -> CommandOptions-setVerbose commandOptions = commandOptions { verbose = True }-
+ src/Squeeze/Data/CommandOptions.hs view
@@ -0,0 +1,90 @@+{-+ Copyright (C) 2010 Dr. Alistair Ward++ 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.++ 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, see <http://www.gnu.org/licenses/>.+-}+{- |+ [@AUTHOR@] Dr. Alistair Ward++ [@DESCRIPTION@]++ * Defines options for program-operation, which are expected to be set from the command-line.++ * Defines an appropriate default value.++ * Self-validates.+-}++module Squeeze.Data.CommandOptions(+-- * Types+-- ** Data-types+ CommandOptions(+-- MkCommandOptions,+ bisectionRatio,+ maximumBytes,+ minimumUsageRatio,+ verbose+ ),+-- * Functions+ fileSizeBounds,+ minimumBytes,+ setVerbose+) where++import qualified Factory.Data.Interval as Data.Interval+import qualified Squeeze.Data.File as Data.File+import qualified ToolShed.Defaultable as Defaultable+import qualified ToolShed.SelfValidate as SelfValidate++{- |+ * Declare a record to contain command-line options.++ * This data-type is polymorphic, but the constraint is only applied at the level of individual functions.+-}+data CommandOptions ratio = MkCommandOptions {+ bisectionRatio :: ratio, -- ^ The file-list is bisected at LHS/Total, and combinations from the LHS are concatenated with each of those from the RHS.+ maximumBytes :: Data.File.FileSize, -- ^ The maximum space (in bytes) available in which to store a subset of the specified files.+ minimumUsageRatio :: ratio, -- ^ The minimum acceptable usage of 'maximumBytes'.+ verbose :: Bool -- ^ Output ancillary information.+} deriving Show++instance Fractional f => Defaultable.Defaultable (CommandOptions f) where+ defaultValue = MkCommandOptions {+ bisectionRatio = recip 2, --Bisection the file-list into equal halves.+ maximumBytes = 4700000000, --DVD-size; just under 4.4GiB.+ minimumUsageRatio = 99 / 100, --99% full.+ verbose = False+ }++instance (Num f, Ord f) => SelfValidate.SelfValidator (CommandOptions f) where+ isValid commandOptions = all ($ commandOptions) [+ (>= 0) . bisectionRatio,+ (<= 1) . bisectionRatio,+ (>= 0) . maximumBytes,+ (>= 0) . minimumUsageRatio,+ (<= 1) . minimumUsageRatio+ ]++-- | Derives the minimum number of bytes, from other options.+minimumBytes :: RealFrac f => CommandOptions f -> Data.File.FileSize+minimumBytes commandOptions = floor $ minimumUsageRatio commandOptions * realToFrac (maximumBytes commandOptions)++-- | The permissible bounds on the size of a file, or set of files.+fileSizeBounds :: RealFrac f => CommandOptions f -> Data.Interval.Interval Data.File.FileSize+fileSizeBounds commandOptions = (minimumBytes commandOptions, maximumBytes commandOptions)++-- | Mutator.+setVerbose :: CommandOptions f -> CommandOptions f+setVerbose commandOptions = commandOptions { verbose = True }+
+ src/Squeeze/Data/File.hs view
@@ -0,0 +1,108 @@+{-+ Copyright (C) 2010 Dr. Alistair Ward++ 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.++ 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, see <http://www.gnu.org/licenses/>.+-}+{- |+ [@AUTHOR@] Dr. Alistair Ward++ [@DESCRIPTION@] Defines file-related type-synonyms, and associated operations.+-}++module Squeeze.Data.File (+-- * Types+-- ** Type-synonyms+ FilePathList,+ FileSize,+ FileSizeAndPath,+-- * Functions+ accumulateSize,+ aggregateSize,+-- findSize,+ findSizes,+ order,+-- ** Accessors+ getSize,+ getPath,+-- ** Predicates+ hasSize+) where++import Control.Applicative((<$>))+import qualified Control.Exception+--import qualified Data.Int+import qualified Data.List+import qualified Data.Ord+import qualified System.Directory+import System.FilePath((</>))+import qualified System.IO+import qualified System.IO.Error+import qualified System.Posix.Files++-- | A type suitable for containing an arbitrary set of file-paths.+type FilePathList = [System.IO.FilePath]++-- | A type-synonym specifically to hold file-sizes (in bytes).+--type FileSize = Data.Int.Int64 --About 1/6th faster.+type FileSize = Integer --Matches the return-type of 'IO.hFileSize'.++-- | A type suitable for containing a file-path, qualified by the corresponding 'FileSize'.+type FileSizeAndPath = (FileSize, System.IO.FilePath)++-- | Accessor.+getSize :: FileSizeAndPath -> FileSize+getSize = fst++-- | Accessor.+getPath :: FileSizeAndPath -> System.IO.FilePath+getPath = snd++-- | Sum the 'FileSize's contained in the specified list.+aggregateSize :: [FileSizeAndPath] -> FileSize+aggregateSize = foldr ((+) . getSize) 0++{- |+ * Returns the cumulative sequence of sizes, as each file is prepended to the specified list.++ * CAVEAT: the list-length is one greater than that supplied, since the last element represents the size with zero files.+-}+accumulateSize :: [FileSizeAndPath] -> [FileSize]+accumulateSize = scanr ((+) . getSize) 0++-- | Get the size of a file, treating a directory as an atomic unit.+findSize :: System.IO.FilePath -> IO FileSize+findSize f = do+ stat <- System.Posix.Files.getFileStatus f --CAVEAT: throws if the user is unauthorised, or the file is non-existent.++ if System.Posix.Files.isRegularFile stat+ then Control.Exception.bracket (System.IO.openFile f System.IO.ReadMode) System.IO.hClose $ \handle -> fromInteger <$> System.IO.hFileSize handle+ else {-not a regular file-} if System.Posix.Files.isDirectory stat+ then System.Directory.getDirectoryContents f >>= fmap {-into IO-monad-} aggregateSize . findSizes . map (f </>) . filter (`notElem` [".", ".."]) --Treat any directory as an atomic unit.+ else {-non-directory-} Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("file='" ++ f ++ "' has unexpected type") Nothing (Just f)++-- | Finds file-sizes.+findSizes :: FilePathList -> IO [FileSizeAndPath]+findSizes filePathList = (`zip` filePathList) <$> {-lift into IO-monad-} mapM findSize filePathList++-- | Sorts a list of 'FileSizeAndPath' by reverse order of size; ie. largest first.+order :: [FileSizeAndPath] -> [FileSizeAndPath]+order = Data.List.sortBy (flip $ Data.Ord.comparing getSize)++-- | 'True' if the specified file has the required size according to the specified predicate.+hasSize ::+ (FileSize -> Bool) -- ^ The predicate.+ -> FileSizeAndPath -- ^ The file-parameters to be tested.+ -> Bool+hasSize f = f . getSize+
+ src/Squeeze/Data/FileCombination.hs view
@@ -0,0 +1,97 @@+{-+ Copyright (C) 2010 Dr. Alistair Ward++ 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.++ 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, see <http://www.gnu.org/licenses/>.+-}+{- |+ [@AUTHOR@] Dr. Alistair Ward++ [@DESCRIPTION@] A data-type which references a set of files by their paths, and qualifies them with their aggregate size.+-}++module Squeeze.Data.FileCombination (+-- * Types+-- ** Data-types+ FileCombination(+-- MkFileCombination,+ getAggregateFileSize+-- getFilePathList+ ),+-- * Constants+ nullFileCombination,+-- * Functions+-- ** Constructors+ singleton,+-- ** Operators+ (<+>),+ (+>),+-- ** Predicates+ hasSize+) where++import qualified Data.List+import qualified Squeeze.Data.File as Data.File++-- | Declare a list of files qualified by its aggregate size.+data FileCombination = MkFileCombination {+ getAggregateFileSize :: !Data.File.FileSize, -- ^ The aggregate size of the files referenced by 'getFilePathList'.+ getFilePathList :: Data.File.FilePathList -- ^ A list of the paths, defining a set of files.+} deriving (Eq, Ord)++instance Show FileCombination where+ showsPrec _ MkFileCombination {+ getAggregateFileSize = s,+ getFilePathList = l+ } = shows s . showChar '\t' . shows (Data.List.sort l)++-- | A constant empty instance.+nullFileCombination :: FileCombination+nullFileCombination = MkFileCombination 0 []++-- | Construct a 'FileCombination' from a single 'Data.File.FileSizeAndPath'.+singleton :: Data.File.FileSizeAndPath -> FileCombination+singleton (fileSize, filePath) = MkFileCombination fileSize [filePath]++-- | Prepend a 'Data.File.FileSizeAndPath' to an existing 'FileCombination'.+{-# INLINE (+>) #-}+(+>) ::+ Data.File.FileSizeAndPath -- ^ The new path to prepend to the incumbent file-combination.+ -> FileCombination -- ^ The incumbent combination of files.+ -> FileCombination+(fileSize, filePath) +> MkFileCombination {+ getAggregateFileSize = s,+ getFilePathList = l+} = MkFileCombination (fileSize + s) (filePath : l)++-- | Add two 'FileCombination's.+(<+>) ::+ FileCombination -- ^ The combination to be prepended.+ -> FileCombination -- ^ The incumbent to which the new value is prepended.+ -> FileCombination+MkFileCombination {+ getAggregateFileSize = sL,+ getFilePathList = lL+} <+> MkFileCombination {+ getAggregateFileSize = sR,+ getFilePathList = lR+} = MkFileCombination (sL + sR) (lL ++ lR)++-- | Predicate used to determine whether a specific file-combination matches a size-related requirement.+{-# INLINE hasSize #-}+hasSize ::+ (Data.File.FileSize -> Bool) -- ^ The predicate.+ -> FileCombination -- ^ The input datum to be tested.+ -> Bool+hasSize f MkFileCombination { getAggregateFileSize = s } = f s+
− src/Squeeze/File.hs
@@ -1,97 +0,0 @@-{-- Copyright (C) 2010 Dr. Alistair Ward-- 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.-- 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, see <http://www.gnu.org/licenses/>.--}-{- |- [@AUTHOR@] Dr. Alistair Ward-- [@DESCRIPTION@] Defines file-related type-synonyms, and associated operations.--}--module Squeeze.File (--- * Types--- ** Type-synonyms- FilePathList,- FileSize,- FileSizeAndPath,--- * Functions- aggregateSize,--- findSize,- findSizes,- getPath,- getSize,- hasSize,- order-) where--import Control.Applicative((<$>))-import System.FilePath((</>))-import qualified Control.Exception---import qualified Data.Int-import qualified Data.List-import qualified Data.Ord-import qualified System.IO-import qualified System.Directory-import qualified System.IO.Error-import qualified System.Posix.Files---- | A type suitable for containing an arbitrary set of file-paths.-type FilePathList = [System.IO.FilePath]---- | A type-synonym specifically to hold file-sizes (in bytes); 'Integer' matches the return-type of 'IO.hFileSize', but 'Data.Int.Int64' is about 4% faster.---type FileSize = Data.Int.Int64-type FileSize = Integer---- | A type suitable for containing a file-path, qualified by the corresponding 'FileSize'.-type FileSizeAndPath = (FileSize, System.IO.FilePath)---- | Accessor.-getSize :: FileSizeAndPath -> FileSize-getSize = fst---- | Accessor.-getPath :: FileSizeAndPath -> System.IO.FilePath-getPath = snd---- | Sum the 'FileSize's contained in the specified list.-aggregateSize :: [FileSizeAndPath] -> FileSize-aggregateSize = Data.List.foldl' (\accumulator -> (accumulator +) . getSize) 0 --Three times faster than 'sum' & marginally faster than 'foldr'.---- | Get the size of a file, treating a directory as an atomic unit.-findSize :: System.IO.FilePath -> IO FileSize-findSize f = do- stat <- System.Posix.Files.getFileStatus f --CAVEAT: throws if user unauthorised, or file non-existent.-- if System.Posix.Files.isRegularFile stat- then Control.Exception.bracket (System.IO.openFile f System.IO.ReadMode) System.IO.hClose $ \handle -> fromInteger <$> System.IO.hFileSize handle- else {-not a regular file-} if System.Posix.Files.isDirectory stat- then System.Directory.getDirectoryContents f >>= fmap {-into IO-monad-} aggregateSize . findSizes . map (f </>) . filter (`notElem` [".", ".."]) --Treat any directory as an atomic unit.- else {-non-directory-} Control.Exception.throw $ System.IO.Error.mkIOError System.IO.Error.illegalOperationErrorType ("file='" ++ f ++ "' has unexpected type") Nothing (Just f)---- | Finds file-sizes.-findSizes :: FilePathList -> IO [FileSizeAndPath]-findSizes filePathList = (`zip` filePathList) <$> {-lift into IO-monad-} mapM findSize filePathList---- | Sorts list of 'FileSizeAndPath' by size, largest first.-order :: [FileSizeAndPath] -> [FileSizeAndPath]-order = Data.List.sortBy (flip $ Data.Ord.comparing getSize)---- | 'True' if the specified file has the required size according to the specified predicate.-hasSize ::- (FileSize -> Bool) -- ^ The predicate.- -> FileSizeAndPath -- ^ The file parameters to be tested.- -> Bool-hasSize f = f . getSize-
− src/Squeeze/FileCombination.hs
@@ -1,76 +0,0 @@-{-- Copyright (C) 2010 Dr. Alistair Ward-- 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.-- 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, see <http://www.gnu.org/licenses/>.--}-{- |- [@AUTHOR@] Dr. Alistair Ward-- [@DESCRIPTION@] A type-synonym for a combination of files, and associated operations.--}--module Squeeze.FileCombination (--- * Types--- ** Type-synonyms- FileCombination,--- * Constants- nullFileCombination,--- * Functions- concatenate,- hasSize,- mkCombination,- prepend,- singleton,- showFileCombination-) where--import Control.Arrow((***), (&&&))-import qualified Control.Arrow-import qualified Data.List-import qualified Squeeze.File as File---- | Declare a list of files qualified by its aggregate size.-type FileCombination = (File.FileSize, File.FilePathList)---- | A constant.-nullFileCombination :: FileCombination-nullFileCombination = (0, [])---- | Create a 'FileCombination' from a list of 'File.FileSizeAndPath'.-mkCombination :: [File.FileSizeAndPath] -> FileCombination-mkCombination = File.aggregateSize &&& map File.getPath---- | Construct a 'FileCombination' from a single 'File.FileSizeAndPath'.-singleton :: File.FileSizeAndPath -> FileCombination-singleton = Control.Arrow.second return---- | Prepend a 'File.FileSizeAndPath' to an existing 'FileCombination'.-prepend ::- File.FileSizeAndPath -- ^ The new path to prepend to the existing file-combination.- -> FileCombination -- ^ The incumbent combination of files.- -> FileCombination-prepend (fileSize, filePath) = (fileSize +) *** (filePath :)---- | Concatenate two 'FileCombination's.-concatenate :: FileCombination -> FileCombination -> FileCombination-concatenate (fileSize, filePathList) = (fileSize +) *** (filePathList ++)---- | Output.-showFileCombination :: FileCombination -> ShowS-showFileCombination (fileSize, filePathList) = shows fileSize . showChar '\t' . shows (Data.List.sort filePathList)---- | Predicate used to determine whether a specific file-combination matches a size-related requirement.-hasSize :: (File.FileSize -> Bool) -> FileCombination -> Bool-hasSize f = f . fst-
− src/Squeeze/FileSizeBounds.hs
@@ -1,56 +0,0 @@-{-- Copyright (C) 2010 Dr. Alistair Ward-- 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.-- 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, see <http://www.gnu.org/licenses/>.--}-{- |- [@AUTHOR@] Dr. Alistair Ward-- [@DESCRIPTION@] Defines a type-synonym for the permissible bounds on the size of a file or set of files, and associated operations.--}--module Squeeze.FileSizeBounds (--- * Types--- ** Type-synonyms- FileSizeBounds,--- * Functions- inside,- precisely,- shift-) where--import Control.Arrow((&&&), (***))-import qualified Squeeze.File as File---- | Used to define the minimum and maximum permissible bounds on the size of a file or set of files.-type FileSizeBounds = (File.FileSize, File.FileSize)---- | Predicate.-inside ::- FileSizeBounds -- ^ The bounds defining /inside/ from /outside/.- -> File.FileSize -- ^ The file-parameters to be tested.- -> Bool-inside (i, j) x = ($ x) `all` [(>= i), (<= j)]---- | Construct the bounds from a single 'FileSize'.-precisely :: File.FileSize -> FileSizeBounds-precisely = id &&& id---- | Shift of both bounds by the specified amount.-shift ::- File.FileSize -- ^ The magnitude of the require shift.- -> FileSizeBounds -- ^ The input set of bounds.- -> FileSizeBounds-shift i = (+ i) *** (+ i)-
− src/Squeeze/QC.hs
@@ -1,80 +0,0 @@-{-# OPTIONS_GHC -fno-warn-orphans #-}-{-- Copyright (C) 2010 Dr. Alistair Ward-- 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.-- 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, see <http://www.gnu.org/licenses/>.--}-{- |- [@AUTHOR@] Dr. Alistair Ward-- [@DESCRIPTION@] Defines tests to dynamically verify the module "Squeeze.Squeeze" against arbitrary data.--}--module Squeeze.QC(--- * Types--- ** Type-synonyms--- Testable,--- * Functions- quickChecks-) where--import qualified Control.Arrow-import qualified Data.List-import qualified Test.QuickCheck-import qualified Squeeze.File as File-import qualified Squeeze.FileSizeBounds as FileSizeBounds-import qualified Squeeze.Squeeze as Squeeze--type Testable = [File.FileSizeAndPath] -> Test.QuickCheck.Property---- | Defines invariant properties, which must hold for any 'FileSizeAndPath'.-quickChecks :: (Testable -> IO ()) -> IO ()-quickChecks = (`mapM_` [prop_bisectionRatio, prop_totalCombinations, prop_bounds, prop_all]) where- translate :: [File.FileSizeAndPath] -> [File.FileSizeAndPath]- translate = Data.List.nub . map (Control.Arrow.first abs)-- prop_bisectionRatio, prop_totalCombinations, prop_bounds, prop_all :: Testable- prop_bisectionRatio fileSizeAndPathList = Test.QuickCheck.label "prop_bisectionRatio" $ (== 1) . length . Data.List.nub . map (- \bisectionRatio -> Data.List.sort . Squeeze.distribute bisectionRatio fileSizeBounds $ File.order l- ) . take 8 {-arbitrarily-} $ map ((1.0 /) . fromInteger) [1 ..] where- l :: [File.FileSizeAndPath]- l = take 10 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.-- fileSizeBounds :: FileSizeBounds.FileSizeBounds- fileSizeBounds = (minimumBytes, maximumBytes) where- maximumBytes, minimumBytes :: File.FileSize- maximumBytes = round $ fromIntegral (File.aggregateSize l) / (4.0 :: Double) --Arbitrarily.- minimumBytes = maximumBytes `div` 2 --Arbitrarily.-- prop_totalCombinations fileSizeAndPathList = Test.QuickCheck.label "prop_totalCombinations" $ (length . Data.List.nub . Squeeze.findCombinations (0, fromIntegral (maxBound :: Int)) $ File.order l) == 2 ^ length l where- l :: [File.FileSizeAndPath]- l = take 10 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.-- prop_bounds fileSizeAndPathList = Test.QuickCheck.label "prop_bounds" $ all (FileSizeBounds.inside fileSizeBounds) . map fst . Squeeze.findCombinations fileSizeBounds $ File.order l where- l :: [File.FileSizeAndPath]- l = take 16 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.-- fileSizeBounds :: FileSizeBounds.FileSizeBounds- fileSizeBounds = (minimumBytes, maximumBytes) where- maximumBytes, minimumBytes :: File.FileSize- maximumBytes = round $ fromIntegral (File.aggregateSize l) / (4.0 :: Double) --Arbitrarily.- minimumBytes = maximumBytes `div` 2 --Arbitrarily.-- prop_all fileSizeAndPathList = Test.QuickCheck.label "prop_all" $ (== bytes) . last . map fst $ Squeeze.findBestFit 0.5 (FileSizeBounds.precisely bytes) l where- l :: [File.FileSizeAndPath]- l = take 16 {-arbitrarily-} . translate $ fileSizeAndPathList --CAVEAT: may be shorter than requested.-- bytes :: File.FileSize- bytes = File.aggregateSize l-
src/Squeeze/Squeeze.hs view
@@ -1,4 +1,3 @@-{-# LANGUAGE CPP #-} {- Copyright (C) 2010 Dr. Alistair Ward @@ -29,43 +28,46 @@ [@CAVEATS@] - Though it runs in constant space, the algorithm has @O(2^n)@ time-complexity, & may take an excessive time to calculate all possibilities.- Because of this, it prints progressively better matches as they're found, rather than waiting to find the best.+ Though it runs in constant space, the algorithm has @O(2^n)@ time-complexity, and may take an excessive time to calculate all possibilities. -} module Squeeze.Squeeze( -- * Functions+-- risingFilter,+ findCombinations, distribute, findBestFit,- findCombinations,--- risingFilter,+-- getFileSizeStatistics,+ findBestFitM, squeeze ) where -import Control.Applicative((<$>))+import Control.Arrow((&&&)) import qualified Control.Arrow+import qualified Control.Monad import qualified Data.List-import qualified Squeeze.CommandOptions as CommandOptions-import qualified Squeeze.File as File-import qualified Squeeze.FileCombination as FileCombination-import qualified Squeeze.FileSizeBounds as FileSizeBounds--#if MIN_VERSION_parallel(3,0,0)-import qualified Control.Parallel.Strategies-#endif+import qualified Factory.Data.Interval as Data.Interval+import qualified Factory.Math.Statistics as Math.Statistics+import qualified Squeeze.Data.CommandOptions as Data.CommandOptions+import qualified Squeeze.Data.File as Data.File+import qualified Squeeze.Data.FileCombination as Data.FileCombination+import Squeeze.Data.FileCombination((<+>), (+>))+import qualified System.IO -- | Progressively raises the selection-criterion, as each match is found. risingFilter ::- File.FileSize -- ^ The initial minimum byte-size of file to accept.- -> [FileCombination.FileCombination] -- ^ The input list of files to filter.- -> [FileCombination.FileCombination] -- ^ The resulting list of files, which have met rising criterion.-risingFilter minimumBytes (x@(size, _) : xs)- | size >= minimumBytes = x : risingFilter size xs- | otherwise = risingFilter minimumBytes xs+ Data.File.FileSize -- ^ The initial minimum byte-size of file to accept.+ -> [Data.FileCombination.FileCombination] -- ^ The input list of files to filter.+ -> [Data.FileCombination.FileCombination] -- ^ The resulting list of files, which have met rising criterion. risingFilter _ [] = []+risingFilter minimumSize (x : xs)+ | aggregateFileSize >= minimumSize = x : risingFilter aggregateFileSize xs+ | otherwise = risingFilter minimumSize xs+ where+ aggregateFileSize = Data.FileCombination.getAggregateFileSize x {- |- * Checks that the total aggregate 'File.FileSize', meets or exceeds 'minimumBytes'.+ * Checks that theo total aggregate 'Data.File.FileSize', meets or exceeds 'minimumBytes'. * Drops excessively large files, assuming that the file-list has been sorted by size, largest first. @@ -76,81 +78,117 @@ though the order in which the combinations are concatenated is rather arbitrary. -} findCombinations ::- FileSizeBounds.FileSizeBounds -- ^ The bounds within which to find file-combinations.- -> [File.FileSizeAndPath] -- ^ The input list of file-names and sizes.- -> [FileCombination.FileCombination] -- ^ The resulting unordered list of suitable file-combinations.-findCombinations (minimumBytes, maximumBytes) = filter (- FileCombination.hasSize (>= minimumBytes)+ Data.Interval.Interval Data.File.FileSize -- ^ The acceptable size-span of file-combinations.+ -> [Data.File.FileSizeAndPath] -- ^ The input list of file-names and sizes.+ -> [Data.FileCombination.FileCombination] -- ^ The resulting unordered list of suitable file-combinations.+findCombinations (minimumCombinationSize, maximumCombinationSize) = filter (+ Data.FileCombination.hasSize (>= minimumCombinationSize) ) . (- FileCombination.nullFileCombination :- ) . nonEmptyCombinations minimumBytes . dropWhile (- File.hasSize (> maximumBytes)+ Data.FileCombination.nullFileCombination : --Required to form combinations with the other portion of the bisected file-list.+ ) . nonEmptyCombinations minimumCombinationSize . uncurry zip . (+ id &&& Data.File.accumulateSize --Associate the list of possible files with its accumulating size.+ ) . dropWhile (+ Data.File.hasSize (> maximumCombinationSize) --Remove files which individually exceed the maximum permissible; assuming they've been reverse sorted by size. ) where- nonEmptyCombinations :: File.FileSize -> [File.FileSizeAndPath] -> [FileCombination.FileCombination]- nonEmptyCombinations minimumBytes' fileSizeAndPathList@(x : xs)- | minimumBytes' > 0 && File.aggregateSize fileSizeAndPathList < minimumBytes' = []- | otherwise = FileCombination.singleton x : foldr (- \y -> (y :) . let- combination = FileCombination.prepend x y- in if FileCombination.hasSize (<= maximumBytes) combination- then (combination :)- else id- ) [] (nonEmptyCombinations (minimumBytes' - File.getSize x) xs {-recurse-})+ nonEmptyCombinations :: Data.File.FileSize -> [(Data.File.FileSizeAndPath, Data.File.FileSize)] -> [Data.FileCombination.FileCombination] nonEmptyCombinations _ [] = []+ nonEmptyCombinations minimumBytes ((fileSizeAndPath, aggregateSize) : remainder)+ | aggregateSize < minimumBytes = [] --Even if all the files are selected, the minimum-size criterion won't be satisfied.+ | otherwise = Data.FileCombination.singleton fileSizeAndPath : foldr binaryChoice [] (+ nonEmptyCombinations (minimumBytes - Data.File.getSize fileSizeAndPath) remainder --Recurse.+ )+ where+ binaryChoice :: Data.FileCombination.FileCombination -> [Data.FileCombination.FileCombination] -> [Data.FileCombination.FileCombination]+ binaryChoice combinationExcluding+ | Data.FileCombination.hasSize (<= maximumCombinationSize) combinationIncluding = (combinationExcluding :) . (combinationIncluding :)+ | otherwise = (combinationExcluding :)+ where+ combinationIncluding :: Data.FileCombination.FileCombination+ combinationIncluding = fileSizeAndPath +> combinationExcluding --- | Splits up the task, to facilitate parallelization, before calling 'findCombinations'.-distribute ::- Double -- ^ The ratio at which to bisect the list of files, in a divide and conquer strategy.- -> FileSizeBounds.FileSizeBounds -- ^ The bounds within which to find file-combinations.- -> [File.FileSizeAndPath] -- ^ The input list of file-names and sizes.- -> [FileCombination.FileCombination] -- ^ The complete unordered list of suitable file-combinations.+-- | Bisects the data and calls 'findCombinations' on the halves.+distribute :: RealFrac ratio+ => ratio -- ^ The ratio at which to bisect the list of files, in a /divide-and-conquer/ strategy.+ -> Data.Interval.Interval Data.File.FileSize -- ^ The /interval/ within which to find file-combinations.+ -> [Data.File.FileSizeAndPath] -- ^ The input list of file-names and sizes.+ -> [Data.FileCombination.FileCombination] -- ^ The complete unordered list of suitable file-combinations. distribute bisectionRatio fileSizeBounds fileSizeAndPathList- | bisectionIndex <= 0 || bisectionIndex >= fileSizeAndPathListLength = findCombinations fileSizeBounds fileSizeAndPathList- | otherwise = distribute' `uncurry` splitAt bisectionIndex fileSizeAndPathList+ | any ($ bisectionIndex) [+ (<= 0),+ (>= fileSizeAndPathListLength)+ ] = findCombinations fileSizeBounds fileSizeAndPathList --Bisecting @ either the zeroeth, or the last element, leaves only one non-null list.+ | otherwise = distribute' `uncurry` splitAt bisectionIndex fileSizeAndPathList where fileSizeAndPathListLength, bisectionIndex :: Int fileSizeAndPathListLength = length fileSizeAndPathList bisectionIndex = round $ bisectionRatio * fromIntegral fileSizeAndPathListLength - distribute' :: [File.FileSizeAndPath] -> [File.FileSizeAndPath] -> [FileCombination.FileCombination]- distribute' fileSizeAndPathListL fileSizeAndPathListR =-#if MIN_VERSION_parallel(3,0,0)- concat $ Control.Parallel.Strategies.parMap (- Control.Parallel.Strategies.evalList $ Control.Parallel.Strategies.evalTuple2 Control.Parallel.Strategies.rdeepseq Control.Parallel.Strategies.r0 --Evaluate the aggregate size, but not the path-list.- )-#else- concatMap-#endif- (- \combinationL@(fileSize, _) -> FileCombination.concatenate combinationL `map` findCombinations (negate fileSize `FileSizeBounds.shift` fileSizeBounds) fileSizeAndPathListR- ) $ Control.Arrow.first (\minimumBytes -> minimumBytes - File.aggregateSize fileSizeAndPathListR) fileSizeBounds `findCombinations` fileSizeAndPathListL+ distribute' :: [Data.File.FileSizeAndPath] -> [Data.File.FileSizeAndPath] -> [Data.FileCombination.FileCombination]+ distribute' fileSizeAndPathListL fileSizeAndPathListR = concatMap (+ \combinationL -> (combinationL <+>) `map` findCombinations (+ negate (Data.FileCombination.getAggregateFileSize combinationL) `Data.Interval.shift` fileSizeBounds+ ) fileSizeAndPathListR+ ) $ Control.Arrow.first (+ negate (Data.File.aggregateSize fileSizeAndPathListR)) {-Adjust the lower bound-} fileSizeBounds `findCombinations` fileSizeAndPathListL {- |- * Calls 'File.order' to sort the files by size (largest first), on the empirical basis that the generated file-combinations, will more quickly result in a good match for the available space.+ * Calls 'Data.File.order' to sort the files by size (largest first), on the empirical basis that the generated file-combinations, will more quickly result in a good match for the available space. * Calls 'distribute' to split the job, to facilitate parallelization. * Calls the private function 'risingFilter' to progressively select better file-combinations from those returned by 'distribute'. -}-findBestFit ::- Double -- ^ The ratio at which to bisect the list of files, in a divide and conquer strategy.- -> FileSizeBounds.FileSizeBounds -- ^ The bounds within which to find file-combinations.- -> [File.FileSizeAndPath] -- ^ The input list of file-names and sizes.- -> [FileCombination.FileCombination] -- ^ A reduced list of suitable file-combinations, sorted best first.-findBestFit bisectionRatio fileSizeBounds@(minimumBytes, _) = risingFilter minimumBytes . distribute bisectionRatio fileSizeBounds . File.order+findBestFit :: RealFrac ratio+ => ratio -- ^ The ratio at which to bisect the list of files, in a /divide-and-conquer/ strategy.+ -> Data.Interval.Interval Data.File.FileSize -- ^ The /interval/ within which to find file-combinations.+ -> [Data.File.FileSizeAndPath] -- ^ The input list of file-names and sizes.+ -> [Data.FileCombination.FileCombination] -- ^ A reduced list of suitable file-combinations, sorted best first.+findBestFit bisectionRatio fileSizeBounds = risingFilter (Data.Interval.getMinBound fileSizeBounds) . distribute bisectionRatio fileSizeBounds . Data.File.order -{- |- * Removes duplicate file-names.+-- | Acquire statistics related to a list of files.+getFileSizeStatistics :: (Fractional mean, Floating standardDeviation) => [Data.File.FileSizeAndPath] -> (Int, Data.File.FileSize, mean, standardDeviation)+getFileSizeStatistics l = (length l, sum sizes, Math.Statistics.getMean sizes, Math.Statistics.getStandardDeviation sizes) where+ sizes = map Data.File.getSize l - * Determines the size of each specified file.+{- |+ * Optionally prints file-statistics. * Unpacks the command-line options. + * Removes files which individually are of unsuitable size.++ * Optionally prints file-size statistics.+ * Calls 'findBestFit' to solve the problem. -}-squeeze ::- CommandOptions.CommandOptions -- ^ The the caller's selection-criteria.- -> File.FilePathList -- ^ The list of file-names from which to select.- -> IO [FileCombination.FileCombination]-squeeze commandOptions = (CommandOptions.bisectionRatio commandOptions `findBestFit` CommandOptions.fileSizeBounds commandOptions <$>) . File.findSizes . Data.List.nub+findBestFitM :: RealFrac ratio+ => Data.CommandOptions.CommandOptions ratio -- ^ The caller's selection-criteria.+ -> [Data.File.FileSizeAndPath] -- ^ The input list of file-names and sizes.+ -> IO [Data.FileCombination.FileCombination] -- ^ A reduced list of suitable file-combinations, sorted best first.+findBestFitM commandOptions fileSizeAndPathList = let+ bisectionRatio = Data.CommandOptions.bisectionRatio commandOptions+ fileSizeBounds = Data.CommandOptions.fileSizeBounds commandOptions+ maximumBytes = Data.CommandOptions.maximumBytes commandOptions+ verbose = Data.CommandOptions.verbose commandOptions++ (fileSizeAndPathList', rejectedFiles) = Data.List.partition (Data.File.hasSize (\size -> all ($ size) [(>= 0), (<= maximumBytes)])) fileSizeAndPathList+ in do+ Control.Monad.when verbose $ do+ Control.Monad.unless (null rejectedFiles) . System.IO.hPutStrLn System.IO.stderr $ "Squeeze.Squeeze:\trejecting files of unsuitable size; " ++ show rejectedFiles++ System.IO.hPutStrLn System.IO.stderr $ "Squeeze.Squeeze:\tfile-(count, total size, mean, standard-deviation):\t" ++ show (getFileSizeStatistics fileSizeAndPathList' :: (Int, Data.File.FileSize, Double, Double))++ return $ findBestFit bisectionRatio fileSizeBounds fileSizeAndPathList'++{- |+ * Removes duplicate file-names.++ * Determines the size of each specified file.++ * Calls 'findBestFitM' to solve the problem.+-}+squeeze :: RealFrac ratio+ => Data.CommandOptions.CommandOptions ratio -- ^ The caller's selection-criteria.+ -> Data.File.FilePathList -- ^ The list of file-names from which to select.+ -> IO [Data.FileCombination.FileCombination]+squeeze commandOptions filePathList = Data.File.findSizes (Data.List.nub filePathList) >>= findBestFitM commandOptions
+ src/Squeeze/Test/Performance.hs view
@@ -0,0 +1,49 @@+{-+ Copyright (C) 2011 Dr. Alistair Ward++ 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.++ 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, see <http://www.gnu.org/licenses/>.+-}+{- |+ [@AUTHOR@] Dr. Alistair Ward++ [@DESCRIPTION@] Defines a performance-test, based on randomly generated /virtual/ files.+-}++module Squeeze.Test.Performance(+-- * Functions+ run+) where++import Control.Arrow((&&&))+import qualified Factory.Math.Probability as Math.Probability+import qualified Squeeze.Data.CommandOptions as Data.CommandOptions+import qualified Squeeze.Data.FileCombination as Data.FileCombination+import qualified Squeeze.Squeeze as Squeeze+import qualified System.Random++{- |+ * Find the best-fit, into the available space,+ using a set composed from the specified number of /virtual/ files.++ * The files have a random size, conforming to the requested distribution.++ * The generated file-name, arbitrarily reflects its size.+-}+run :: (RealFrac ratio, RealFloat f, System.Random.Random f)+ => Data.CommandOptions.CommandOptions ratio+ -> Int -- ^ The number of /virtual/ files to randomly generate.+ -> Math.Probability.DiscreteDistribution f+ -> IO [Data.FileCombination.FileCombination] -- ^ The results.+run commandOptions fileCount probabilityDistribution = System.Random.getStdGen >>= Squeeze.findBestFitM commandOptions . map (id &&& show) . Math.Probability.generateDiscretePopulation fileCount probabilityDistribution+
+ src/Squeeze/Test/QC.hs view
@@ -0,0 +1,81 @@+{-+ Copyright (C) 2010 Dr. Alistair Ward++ 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.++ 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, see <http://www.gnu.org/licenses/>.+-}+{- |+ [@AUTHOR@] Dr. Alistair Ward++ [@DESCRIPTION@] Defines tests to dynamically verify the module "Squeeze.Squeeze" against arbitrary data.+-}++module Squeeze.Test.QC(+-- * Types+-- ** Type-synonyms+-- Testable,+-- * Functions+ quickChecks+) where++import qualified Control.Arrow+import qualified Data.List+import qualified Factory.Data.Interval as Data.Interval+import qualified Squeeze.Data.File as Data.File+import qualified Squeeze.Data.FileCombination as Data.FileCombination+import qualified Squeeze.Squeeze as Squeeze+import qualified Test.QuickCheck+import Test.QuickCheck((==>))++type Testable = [Data.File.FileSizeAndPath] -> Test.QuickCheck.Property++-- | Defines invariant properties, which must hold for any 'FileSizeAndPath'.+quickChecks :: (Testable -> IO ()) -> IO ()+quickChecks = (`mapM_` [prop_bisectionRatio, prop_totalCombinations, prop_bounds, prop_all]) where+ translate :: [Data.File.FileSizeAndPath] -> [Data.File.FileSizeAndPath]+ translate = Data.List.nub . map (Control.Arrow.first abs)++ prop_bisectionRatio, prop_totalCombinations, prop_bounds, prop_all :: Testable+ prop_bisectionRatio fileSizeAndPathList = not (null l) ==> Test.QuickCheck.label "prop_bisectionRatio" $ (== 1) . length . Data.List.nub . map (+ \bisectionRatio -> Data.List.sort . Squeeze.distribute bisectionRatio fileSizeBounds $ Data.File.order l+ ) . take (length l) $ map recip [1 :: Double ..] where+ l :: [Data.File.FileSizeAndPath]+ l = take 14 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.++ fileSizeBounds :: Data.Interval.Interval Data.File.FileSize+ fileSizeBounds = (minimumBytes, maximumBytes) where+ maximumBytes, minimumBytes :: Data.File.FileSize+ maximumBytes = round $ fromIntegral (Data.File.aggregateSize l) / (4.0 :: Double) --Arbitrarily.+ minimumBytes = maximumBytes `div` 2 --Arbitrarily.++ prop_totalCombinations fileSizeAndPathList = Test.QuickCheck.label "prop_totalCombinations" $ (length . Data.List.nub . Squeeze.findCombinations (0, fromIntegral (maxBound :: Int)) $ Data.File.order l) == 2 ^ length l where+ l :: [Data.File.FileSizeAndPath]+ l = take 10 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.++ prop_bounds fileSizeAndPathList = Test.QuickCheck.label "prop_bounds" . all ((`Data.Interval.elem'` fileSizeBounds) . Data.FileCombination.getAggregateFileSize) . Squeeze.findCombinations fileSizeBounds $ Data.File.order l where+ l :: [Data.File.FileSizeAndPath]+ l = take 16 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.++ fileSizeBounds :: Data.Interval.Interval Data.File.FileSize+ fileSizeBounds = (minimumBytes, maximumBytes) where+ maximumBytes, minimumBytes :: Data.File.FileSize+ maximumBytes = round $ fromIntegral (Data.File.aggregateSize l) / (4.0 :: Double) --Arbitrarily.+ minimumBytes = maximumBytes `div` 2 --Arbitrarily.++ prop_all fileSizeAndPathList = Test.QuickCheck.label "prop_all" . (== bytes) . last . map Data.FileCombination.getAggregateFileSize $ Squeeze.findBestFit (recip 2 :: Double) (Data.Interval.precisely bytes) l where+ l :: [Data.File.FileSizeAndPath]+ l = take 16 {-arbitrarily-} $ translate fileSizeAndPathList --CAVEAT: may be shorter than requested.++ bytes :: Data.File.FileSize+ bytes = Data.File.aggregateSize l+