squeeze 1.0.4.0 → 1.0.4.1
raw patch · 14 files changed
+342/−162 lines, 14 files
Files
- changelog +9/−1
- changelog.Debian +17/−0
- debian/DEBIAN/control +2/−2
- man/man1/squeeze.1 +23/−23
- squeeze.cabal +4/−2
- squeeze.spec +1/−1
- src/Main.hs +27/−70
- src/Squeeze/Data/CommandOptions.hs +19/−19
- src/Squeeze/Data/File.hs +52/−25
- src/Squeeze/Squeeze.hs +101/−12
- src/Squeeze/Test/Data/CommandOptions.hs +50/−0
- src/Squeeze/Test/Data/Verbosity.hs +30/−0
- src/Squeeze/Test/Performance.hs +4/−4
- src/Squeeze/Test/Squeeze.hs +3/−3
changelog view
@@ -81,4 +81,12 @@ * Compensated for the potential rejection of some virtual files after generation of a test-population. * Used new class 'Factory.Math.Probability.Distribution' & bumped required version to 'factory-0.2.1.0'. * Replaced the command-line option '--testPerformance', with '--testPerformanceContinuous' & '--testPerformanceDiscrete'.-+1.0.4.1+ * Removed 'ToolShed.SelfValidate.isValid commandOptions' from 'Main.runQuickChecks'; since the command-options aren't used.+ * Added 'changelog.Debian' to 'squeeze.cabal'.+ * Relocated 'Main.distribute' to 'Squeeze.Squeeze.distributeAndFindBestFit' & added check on whether maximum size has been exceeded.+ * Added 'Squeeze.Squeeze.partitionEmptyFilesAndDistributeAndFindBestFit', to efficiently account for empty files, & relocated calculation of file-statistics to this function.+ * Amended 'Test.Performance.run', replacing call to 'Squeeze.Squeeze.findBestFit' with 'Squeeze.Squeeze.distributeAndFindBestFit', to permit multi-threaded performance-tests.+ * Added function 'Squeeze.Data.CommandOptions.mkCommandOptions' & modules "Squeeze.Test.Data.Verbosity" & "Squeeze.Test.Data.CommandOptions" for future QuickChecks.+ * Extracted 'Squeeze.Data.File.expandDirectory' from 'Squeeze.Data.File.findSize' to clarify the logic. Symlinks are also now permissible input files.+ * Added 'Squeeze.Data.File.findDuplicates', & trapped duplicate files implicit within those directories specified.
+ changelog.Debian view
@@ -0,0 +1,17 @@+squeeze (1.0.1.3-1) experimental; urgency=low++ * New release.++ -- Alistair Ward <squeeze at functionalley dot eu> Wed, 12 Jan 2011 00:00:00 +0000++squeeze (1.0.1.4-1) experimental; urgency=low++ * Uploaded to <http://hackage.haskell.org/packages/hackage.html>.++ -- Alistair Ward <squeeze at functionalley dot eu> Wed, 12 Jan 2011 00:00:00 +0000++squeeze (1.0.4.1-1) experimental; urgency=low++ * Re-calculated "Installed-size".++ -- Alistair Ward <squeeze at functionalley dot eu> Wed, 24 Jul 2013 12:00:00 +0000
debian/DEBIAN/control view
@@ -1,10 +1,10 @@ Package: squeeze-Version: 1.0.4.0-1+Version: 1.0.4.1-1 Section: utils Priority: optional Architecture: i386 Depends: libc6-Installed-size: 2500+Installed-size: 1825 Maintainer: Dr. Alistair Ward <squeeze at functionalley dot eu> Provides: Homepage: http://functionalley.eu
man/man1/squeeze.1 view
@@ -6,13 +6,25 @@ .SH DESCRIPTION .PP Finds the subset of the specified \fIFile-path\fRs, which fits into the specified space with least room to spare, whilst also meeting the minimum usage-requirements;-i.e. an instance of the "0-1 Knapsac problem".+i.e. a degenerate instance of the "0-1 Knapsac problem". .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 produced lazily, rather than waiting until the optimal solution is known (which might take an inordinately long time). .SH OPTIONS+.TP+\fB--verbosity=\fR\fBSilent\fR|\fBNormal\fR|\fBVerbose\fR|\fBDeafening\fR+Produces additional explanatory output where appropriate.+.br+CAVEAT: to be effective, this option must precede other options.+.SS "Generic Program-information"+.TP+\fB-v\fR, \fB--version\fR+Outputs version-information, & then exits.+.TP+\fB-?\fR, \fB--help\fR+Displays help, & then exits. .SS "Selection" .TP \fB-M\fR \fIBytes\fR, \fB--maximumBytes=\fR\fIBytes\fR@@ -31,7 +43,7 @@ .SS Test .TP \fB-q\fR, \fB--runQuickChecks\fR-Tests the implementation, by validating some invariant properties using arbitrary data ... & then exits.+Tests the implementation, by validating some invariant properties using arbitrary data; & then exits. .TP \fB-r\fR[\fIInt\fR], \fB--randomSeed\fR[\fB=\fR\fIInt\fR] This option takes an optional integral argument with which to seed the unique random-number generator used for all random operations.@@ -44,7 +56,7 @@ \fB--testPerformanceContinuous='(\fR\fIInteger\fR\fB,\fR \fBLogNormalDistribution\fR \fIlocation\fR \fIscale^2\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, & then exits.+the size of which conform to the specified continuous probability-distribution; & then exits. .br "\fIA Large-Scale Study of File-System Contents by John R. Douceur and William J. Bolosky\fR" concludes that for arbitrary file-types, the frequency of file-sizes matches this distribution.@@ -52,28 +64,16 @@ \fB--testPerformanceDiscrete='(\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, & then exits.+the size of which conform to the specified discrete probability-distribution; & then exits. .br CAVEAT: the standard-deviation for this distribution is narrower than observed.-.TP-\fB--verbosity=\fR\fBSilent\fR|\fBNormal\fR|\fBVerbose\fR|\fBDeafening\fR-Produces additional explanatory output where appropriate.-.br-CAVEAT: to be effective, this option must precede other options.-.SS "Generic Program-information"-.TP-\fB-v\fR, \fB--version\fR-Outputs version-information & then exits.-.TP-\fB-?\fR, \fB--help\fR-Displays help & then exits.-.SS "File-paths"+.SS File-paths .TP-If \fIFile-path\fR is a single hyphen-minus (\fB-\fR), then the list of file-paths will be read from standard-input.+If \fIFile-path\fR is a single hyphen-minus ("\fB-\fR"), then the list of file-paths will be read from standard-input. .SH EXIT-STATUS \fB0\fR on success, & >\fB0\fR if an error occurs. .SH EXAMPLES-.SS Trial 1+.SS Example 1 Say we've a directory of audio-files, categorised by artist. .IP .B ls -p@@ -100,12 +100,12 @@ 699998310 .fi .PP-NB: \fBdu\fR will return a slightly larger size, since it includes the space required for directory-structures.-.SS Trial 2+NB: "\fBdu\fR" will return a slightly larger size, since it includes the space required for directory-structures.+.SS Example 2 We can improve on that result if we're prepared to split some of the artist-specific directories into individual albums. With the expection of more solutions from which to select, we also raise the bar for what is acceptible. .br-NB: from version \fB1.0.3.0\fR, the runtime can be passed a \fB-N\fR flag to request parallel execution on multiple cores,+NB: from version \fB1.0.3.0\fR, the runtime can be passed a "\fB-N\fR" flag to request parallel execution on multiple cores, which as a side-effect, alters the selection of sub-optimal solutions to return. Whether this option actually results in reduced execution-time, depends on the file-size frequency-distribution & on the available hardware. .IP@@ -115,7 +115,7 @@ 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+.SS Example 3 If we're prepared to add individual files from another artist: .IP .B squeeze -M 700000000 -m 0.9999999 ArabStrap BobDylan/* JeffBuckley JohnMartyn JoniMitchell ReservoirDogsOST $(find RichardThompson -type f) SethLakeman SusheelaRaman TeddyThompson Vangelis +RTS -N
squeeze.cabal view
@@ -1,6 +1,6 @@ --Package-properties Name: squeeze-Version: 1.0.4.0+Version: 1.0.4.1 Cabal-Version: >= 1.6 Copyright: (C) 2010-2013 Dr. Alistair Ward License: GPL@@ -16,7 +16,7 @@ Maintainer: squeeze <at> functionalley <dot> eu Bug-reports: squeeze <at> functionalley <dot> eu Data-files:-Extra-Source-Files: changelog copyright debian/DEBIAN/control makefile man/man1/squeeze.1 squeeze.spec+Extra-Source-Files: changelog copyright changelog.Debian debian/DEBIAN/control makefile man/man1/squeeze.1 squeeze.spec flag llvm Description: Whether the 'llvm' compiler-backend has been installed and is required for code-generation.@@ -36,7 +36,9 @@ Squeeze.Data.File Squeeze.Data.FileCombination Squeeze.Squeeze+ Squeeze.Test.Data.CommandOptions Squeeze.Test.Data.FileCombinations+ Squeeze.Test.Data.Verbosity Squeeze.Test.Performance Squeeze.Test.QuickChecks Squeeze.Test.Squeeze
squeeze.spec view
@@ -22,7 +22,7 @@ Summary: Finds the optimal subset of the specified files, to fit into a limited space, with minimal wastage Name: squeeze-Version: 1.0.4.0+Version: 1.0.4.1 Release: 1 License: GPLv3 #From '/usr/share/doc/packages/rpm/GROUPS'.
src/Main.hs view
@@ -29,28 +29,23 @@ module Main(main) where import Control.Applicative((<*>), (<$>))-import Control.Arrow((&&&))-import qualified Control.Concurrent import qualified Control.Monad import qualified Control.Monad.Writer import qualified Data.List import qualified Data.Maybe-import qualified Data.Ord import qualified Data.Version import qualified Distribution.Package import qualified Distribution.Text import qualified Distribution.Verbosity import qualified Distribution.Version import qualified Factory.Math.Probability-import qualified Paths_squeeze as Paths --Either local stub, or package-instance autogenerated by 'Setup.hs build'.-import qualified Squeeze.Control.Concurrent.DivideAndConquer as Control.Concurrent.DivideAndConquer-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 qualified Squeeze.Squeeze as Squeeze-import qualified Squeeze.Test.Performance as Test.Performance-import qualified Squeeze.Test.QuickChecks as Test.QuickChecks-import qualified System.Console.GetOpt as G+import qualified Paths_squeeze as Paths --Either local stub, or package-instance autogenerated by 'Setup.hs build'.+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.QuickChecks as Test.QuickChecks+import qualified System.Console.GetOpt as G import qualified System.Environment import qualified System.Exit import qualified System.FilePath@@ -87,45 +82,6 @@ bounded = fromInteger unbounded {- |- * Recursively bisects the task, distributing the sub-tasks to 'Squeeze.findBestFit', to utilise the available CPU-cores.-- * Recombines the part solutions to finds the single monotonically increasing list of file-combinations matching the original criteria.-- * CAVEAT: whilst the ultimate solution is similar, regardless of the specified number of CPU-cores available, the path leading to it typically differs.--}-distribute- :: RealFrac ratio- => Int -- ^ The number of CPU-cores available.- -> Data.CommandOptions.CommandOptions ratio- -> [Data.File.FileSizeAndPath] -- ^ The unordered list of files & sizes.- -> IO [Data.FileCombination.FileCombination]-distribute _ _ [] = return []--distribute 1 commandOptions fileSizeAndPathList = let- solutionSizeBounds = Data.CommandOptions.solutionSizeBounds commandOptions- in do- Control.Monad.when (Data.CommandOptions.getVerbosity commandOptions == maxBound) . System.IO.hPutStrLn System.IO.stderr $ "Solution-size bounds " ++ show solutionSizeBounds-- return $ Squeeze.findBestFit solutionSizeBounds fileSizeAndPathList --Single-threaded.--distribute numCapabilities commandOptions fileSizeAndPathList = let- distribute' = distribute $ numCapabilities `div` 2 --Partially apply.- (selectedFileSizeAndPath, remainingFileSizeAndPaths) = Data.List.minimumBy (Data.Ord.comparing Data.File.getSize) &&& filter (/= selectedFileSizeAndPath) $ fileSizeAndPathList --Balance the load on the two threads, by selecting the smallest file rather than the largest; this makes a big difference !- in do- Control.Monad.when (Data.CommandOptions.getVerbosity commandOptions == maxBound) . System.IO.hPutStrLn System.IO.stderr $ show numCapabilities ++ " CPU-cores => bisecting task into those, with & without, " ++ show selectedFileSizeAndPath-- fileCombinationsExcludingSelected <- distribute' commandOptions remainingFileSizeAndPaths --Recurse using all the original space, but a reduced list of files.- fileCombinationsIncludingSelected <- map (- Data.FileCombination.prepend selectedFileSizeAndPath --Prepend to all file-combinations, the file we previously removed.- ) <$> distribute' (- commandOptions {- Data.CommandOptions.getMaximumBytes = Data.CommandOptions.getMaximumBytes commandOptions - Data.File.getSize selectedFileSizeAndPath- } --Reduce the maximum size; there's no need to account for the minimum, since this is defined as a ratio of the maximum.- ) remainingFileSizeAndPaths --Recurse.-- Control.Concurrent.DivideAndConquer.divideAndConquer Data.FileCombination.risingMergeByAggregateFileSize fileCombinationsExcludingSelected fileCombinationsIncludingSelected --Merge the part-solutions.--{- | * Parses the command-line arguments, to determine 'Data.CommandOptions.CommandOptions', which over-ride the default value. * Any arguments which follow known 'Data.CommandOptions.CommandOptions',@@ -133,7 +89,7 @@ * If the specified file-name is /-/, then the actual file-names are read from /standard input/, to augment any other non-options specified. - * Delegates the donkey-work to 'distribute'.+ * Delegates the donkey-work to 'partitionEmptyFilesAndDistributeAndFindBestFit'. Because this may take a long time, it prints the results in real time, rather than batching until the optimum has been determined. -} main :: IO ()@@ -157,17 +113,19 @@ ), G.Option "v" ["version"] (G.NoArg $ const printVersion) "Print version-information, & then exit.", G.Option "z" ["includeEmpty"] (setIncludeEmpty `G.OptArg` "<Bool>") ("Whether empty files & directories may be included in any solution; default '" ++ show (Data.CommandOptions.getIncludeEmpty defaultCommandOptions) ++ "'."),- G.Option "M" ["maximumBytes"] (setMaximumBytes `G.ReqArg` "<Int>") ("The maximum bytes of available space; default '" ++ show (Data.CommandOptions.getMaximumBytes defaultCommandOptions) ++ "'."),+ G.Option "M" ["maximumBytes"] (setMaximumBytes `G.ReqArg` "<Int>") ("The maximum bytes of available space; default '" ++ show defaultMaximumBytes ++ "'."), G.Option "m" ["minimumUsageRatio"] (setMinimumUsageRatio `G.ReqArg` "<Float>") ("The minimum acceptable space usage-ratio; default '" ++ show (realToFrac $ Data.CommandOptions.getMinimumUsageRatio defaultCommandOptions :: Double) ++ "'."),- G.Option "q" ["runQuickChecks"] (G.NoArg runQuickChecks) "Run Quick-checks using arbitrary data, & then exit.",+ G.Option "q" ["runQuickChecks"] (G.NoArg runQuickChecks) "Test the implementation, by validating some invariant properties using arbitrary data; & then exit.", G.Option "r" ["randomSeed"] (G.OptArg setRandomSeed "<Int>") ("Seed the random number-generator with the specified integer, to produce a repeatable pseudo-random sequence as required for performance-testing. If this option is unspecified then the seed is unpredictable, but if only its argument is unspecified then the seed defaults to '" ++ show defaultRandomSeed ++ "'. CAVEAT: to be effective, it must precede either 'testPerformanceContinuous' or 'testPerformanceDiscrete'."), G.Option "" ["testPerformanceContinuous"] (- testPerformanceContinuous `G.ReqArg` "(<Int>, <Continuous Distribution>)"- ) "Measure the CPU-seconds required for the specified number of randomly generated virtual files, the size of which conform to the specified continuous probability-distribution; & then exit.",+ testPerformanceContinuous `G.ReqArg` "(<Int>, <ContinuousDistribution>)"+ ) "Measure the CPU-seconds required to find the best fit, for the specified number of randomly generated virtual files, the size of which conform to the specified continuous probability-distribution; & then exit.", G.Option "" ["testPerformanceDiscrete"] (- testPerformanceDiscrete `G.ReqArg` "(<Int>, <Discrete Distribution>)"- ) "Measure the CPU-seconds required for the specified number of randomly generated virtual files, the size of which conform to the specified discrete probability-distribution; & then exit."+ testPerformanceDiscrete `G.ReqArg` "(<Int>, <DiscreteDistribution>)"+ ) "Measure the CPU-seconds required to find the best fit, for the specified number of randomly generated virtual files, the size of which conform to the specified discrete probability-distribution; & then exit." ] where+ defaultMaximumBytes = Data.CommandOptions.getMaximumBytes defaultCommandOptions+ setMaximumBytes, setMinimumUsageRatio, setVerbosity, testPerformanceContinuous, testPerformanceDiscrete :: String -> CommandLineAction setMaximumBytes arg commandOptions = return {-to IO-monad-} commandOptions { Data.CommandOptions.getMaximumBytes = readCommandArg arg } setMinimumUsageRatio arg commandOptions = return {-to IO-monad-} commandOptions { Data.CommandOptions.getMinimumUsageRatio = realToFrac (readCommandArg arg :: Double) }@@ -200,9 +158,7 @@ setRandomSeed arg commandOptions = return {-to IO-monad-} commandOptions { Data.CommandOptions.getMaybeRandomSeed = Just $ Data.Maybe.maybe defaultRandomSeed readBoundedIntegral arg } runQuickChecks :: (Num f, Ord f, Show f) => Data.CommandOptions.CommandOptions f -> IO (Data.CommandOptions.CommandOptions f)- runQuickChecks commandOptions- | not $ ToolShed.SelfValidate.isValid commandOptions = fail $ ToolShed.SelfValidate.getFirstError commandOptions- | otherwise = Test.QuickChecks.run >> System.Exit.exitWith System.Exit.ExitSuccess+ runQuickChecks _ = Test.QuickChecks.run >> System.Exit.exitWith System.Exit.ExitSuccess printVersion, printUsage :: IO (Data.CommandOptions.CommandOptions f) printVersion = Text.Printf.printf "%s\n\n%s %s.\n%s.\n%s.\n%s %s.\n" packageName "Copyright (C) 2010-2013" author "This program comes with ABSOLUTELY NO WARRANTY" "This is free software, & you are welcome to redistribute it under certain conditions" "Written by" author >> System.Exit.exitWith System.Exit.ExitSuccess where@@ -223,9 +179,9 @@ ) "Float" "Int ('.' Int)?" "Int" "[0-9]+" "lambda" "Float\t(* the mean & variance of the distribution *)" "location" "Float\t(* the mean of the log of the distribution *)" "scale^2" "Float\t(* the variance of the log of the distribution *)" ( progName ++ " --verbosity=Verbose -M 700000000 *.ogg +RTS -N\t#Find the best-fit for the globbed file-names, into the space available on a CD, using multiple CPU-cores where available." ) (- progName ++ " -r --testPerformanceContinuous='(100, LogNormalDistribution 19.4 0.6)'\t#Test performance."+ progName ++ " -r --testPerformanceContinuous='(100, LogNormalDistribution " ++ show (log ((fromIntegral defaultMaximumBytes / 12) / sqrt 2) :: Float) {-location-} ++ " " ++ show (log 2 :: Float) {-scale^2-} ++ ")'\t#Test performance." ) (- progName ++ " -r --testPerformanceDiscrete='(100, PoissonDistribution 4e8)'\t#Test performance."+ progName ++ " -r --testPerformanceDiscrete='(100, PoissonDistribution " ++ show (defaultMaximumBytes `div` 12) {-lambda-} ++ ")'\t#Test performance." ) >> System.Exit.exitWith System.Exit.ExitSuccess args <- System.Environment.getArgs@@ -244,7 +200,7 @@ else let standardInputProxy = "-" in do- filePaths <- if standardInputProxy `elem` nonOptions+ filePaths <- Data.List.nub {-remove explicit duplicates-} <$> if standardInputProxy `elem` nonOptions then let getFilePaths :: IO Data.File.FilePathList getFilePaths = do@@ -261,20 +217,21 @@ else return filePaths else {-real fileNames-} return {-to IO-monad-} nonOptions + implicitDuplicateFilePaths <- Data.File.findDuplicates filePaths - (acceptedFileSizeAndPathList, logFile) <- Control.Monad.Writer.runWriter . Data.File.selectSuitableFileSizes (Data.CommandOptions.isWithinSizeBounds commandOptions) <$> Data.File.findSizes (Data.List.nub filePaths)+ Control.Monad.unless (Data.CommandOptions.getVerbosity commandOptions == minBound || null implicitDuplicateFilePaths) . System.IO.hPutStrLn System.IO.stderr $ "WARNING: there are duplicate files implicit within those directories specified; " ++ show implicitDuplicateFilePaths ++ "." - Control.Monad.when (Data.CommandOptions.getVerbosity commandOptions > minBound) . System.IO.hPutStrLn System.IO.stderr $ Data.List.intercalate "\n" logFile+ (acceptedFileSizeAndPathList, logFile) <- Control.Monad.Writer.runWriter . Data.File.selectSuitableFileSizes (<= Data.CommandOptions.getMaximumBytes commandOptions) <$> Data.File.findSizes filePaths + Control.Monad.unless (Data.CommandOptions.getVerbosity commandOptions == minBound || null logFile) . System.IO.hPutStrLn System.IO.stderr $ Data.List.intercalate "\n" logFile+ if null acceptedFileSizeAndPathList then fail "there are zero suitable files" else let aggregateSize = Data.File.aggregateSize acceptedFileSizeAndPathList minimumBytes = Data.CommandOptions.deriveMinimumBytes commandOptions in if aggregateSize < minimumBytes- then fail $ "the aggregate size of all suitable files, is insufficient; " ++ show (aggregateSize, minimumBytes)- else Control.Concurrent.getNumCapabilities >>= (- \numCapabilities -> distribute numCapabilities commandOptions acceptedFileSizeAndPathList- ) >>= mapM_ print {-lazy evaluation-}+ then fail $ "the aggregate size of all suitable files (" ++ show aggregateSize ++ " bytes), is insufficient to satisfy the minimum " ++ show minimumBytes ++ " bytes required"+ else Squeeze.partitionEmptyFilesAndDistributeAndFindBestFit commandOptions acceptedFileSizeAndPathList >>= mapM_ print {-lazy evaluation-} (_, _, errors) -> System.IO.Error.ioError . System.IO.Error.userError $ concatMap init {-chop-} errors
src/Squeeze/Data/CommandOptions.hs view
@@ -40,10 +40,11 @@ -- * Functions solutionSizeBounds, deriveMinimumBytes,--- ** Predicates- isWithinSizeBounds+-- ** Constructors+ mkCommandOptions ) where +import Control.Arrow((&&&)) import qualified Distribution.Verbosity import qualified Factory.Data.Interval import qualified Squeeze.Data.File as Data.File@@ -55,7 +56,7 @@ getIncludeEmpty :: Bool, -- ^ Whether empty directories or files should be included in any solution. getMaximumBytes :: Data.File.FileSize, -- ^ The maximum space (in bytes) available in which to store a subset of the specified files. getMaybeRandomSeed :: Maybe Int, -- ^ Optionally seed the random-number generator to produce a repeatable pseudo-random sequence.- getMinimumUsageRatio :: ratio, -- ^ The minimum acceptable usage of 'getMaximumBytes'.+ getMinimumUsageRatio :: ratio, -- ^ The minimum acceptable usage-ratio of 'getMaximumBytes'. getVerbosity :: Distribution.Verbosity.Verbosity -- ^ Set the threshold for ancillary information-output. } deriving Show @@ -68,27 +69,26 @@ getVerbosity = Distribution.Verbosity.normal } -instance (Num ratio, Ord ratio, Show ratio) => ToolShed.SelfValidate.SelfValidator (CommandOptions ratio) where+instance (Ord ratio, Real ratio) => ToolShed.SelfValidate.SelfValidator (CommandOptions ratio) where getErrors commandOptions = map snd $ filter (($ commandOptions) . fst) [- ((< 0) . getMaximumBytes, "Invalid maximumBytes=" ++ show (getMaximumBytes commandOptions) ++ "."),- ((< 0) . getMinimumUsageRatio, "Invalid minimumUsageRatio='" ++ show (getMinimumUsageRatio commandOptions) ++ "'."),- ((> 1) . getMinimumUsageRatio, "Invalid minimumUsageRatio='" ++ show (getMinimumUsageRatio commandOptions) ++ "'.")+ ((< 0) . getMaximumBytes, "invalid maximumBytes; " ++ show (getMaximumBytes commandOptions)),+ ((< 0) . getMinimumUsageRatio, "invalid minimumUsageRatio; " ++ show (realToFrac $ getMinimumUsageRatio commandOptions :: Double)),+ ((> 1) . getMinimumUsageRatio, "invalid minimumUsageRatio; " ++ show (realToFrac $ getMinimumUsageRatio commandOptions :: Double)) ] +-- | Smart constructor.+mkCommandOptions :: (Ord ratio, Real ratio) => Bool -> Data.File.FileSize -> Maybe Int -> ratio -> Distribution.Verbosity.Verbosity -> CommandOptions ratio+mkCommandOptions includeEmpty maximumBytes maybeRandomSeed minimumUsageRatio verbosity+ | ToolShed.SelfValidate.isValid commandOptions = commandOptions+ | otherwise = error $ "Squeeze.Data.CommandOptions.mkCommandOptions:\t" ++ ToolShed.SelfValidate.getFirstError commandOptions+ where+ commandOptions = MkCommandOptions includeEmpty maximumBytes maybeRandomSeed minimumUsageRatio verbosity+ -- | Derives the minimum number of bytes, from other options.-deriveMinimumBytes :: RealFrac f => CommandOptions f -> Data.File.FileSize-deriveMinimumBytes commandOptions = floor $ getMinimumUsageRatio commandOptions * realToFrac (getMaximumBytes commandOptions)+deriveMinimumBytes :: RealFrac ratio => CommandOptions ratio -> Data.File.FileSize+deriveMinimumBytes = floor . uncurry (*) . (getMinimumUsageRatio &&& realToFrac . getMaximumBytes) -- | The bounds on the aggregate size of the set of files. solutionSizeBounds :: RealFrac f => CommandOptions f -> Factory.Data.Interval.Interval Data.File.FileSize-solutionSizeBounds commandOptions = (deriveMinimumBytes commandOptions, getMaximumBytes commandOptions)---- | Whether a file of the specified size is an acceptable component of any solution.-isWithinSizeBounds :: CommandOptions f -> Data.File.FileSize -> Bool-isWithinSizeBounds commandOptions size = all ($ size) [- if getIncludeEmpty commandOptions- then (>= 0)- else (> 0),- (<= getMaximumBytes commandOptions)- ]+solutionSizeBounds = deriveMinimumBytes &&& getMaximumBytes
src/Squeeze/Data/File.hs view
@@ -1,5 +1,5 @@ {-- Copyright (C) 2010 Dr. Alistair Ward+ Copyright (C) 2010-2013 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@@ -29,10 +29,13 @@ -- * Functions accumulateSize, aggregateSize,+-- expandDirectory,+ findDuplicates, -- findSize, findSizes,- orderBySize,--- getFileSizeStatistics,+ orderByIncreasingSize,+ orderByDecreasingSize,+ getFileSizeStatistics, selectSuitableFileSizes, -- ** Accessors getSize,@@ -42,7 +45,7 @@ ) where import Control.Applicative((<$>))-import qualified Control.Exception+import Control.Arrow((&&&)) import qualified Control.Monad import qualified Control.Monad.Writer import qualified Data.List@@ -51,14 +54,14 @@ import qualified System.Directory import System.FilePath((</>)) import qualified System.IO-import qualified System.IO.Error import qualified System.Posix.Files+import qualified ToolShed.Data.Foldable -- | 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 = Integer --Matches the return-type of 'IO.hFileSize'.+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)@@ -71,7 +74,7 @@ getPath :: FileSizeAndPath -> System.IO.FilePath getPath = snd --- | Sum the 'FileSize's contained in the specified list.+-- | Sum the 'FileSize's in the specified list. aggregateSize :: [FileSizeAndPath] -> FileSize aggregateSize = foldr ((+) . getSize) 0 @@ -83,37 +86,63 @@ 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.+{- |+ * Recursively descend the specified path, accumulating a list of files. - if System.Posix.Files.isRegularFile stat- then System.IO.withFile f System.IO.ReadMode System.IO.hFileSize- 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=" ++ show f ++ " has unexpected type") Nothing (Just f)+ * CAVEAT: all non-directory files are returned; devices, pipes, sockets, symlinks ...+-}+expandDirectory :: System.IO.FilePath -> IO FilePathList+expandDirectory filePath = do+ stat <- System.Posix.Files.getFileStatus filePath --CAVEAT: throws if the user is unauthorised, or the file is non-existent. + if System.Posix.Files.isDirectory stat+ then System.Directory.getDirectoryContents filePath >>= fmap concat . mapM (+ expandDirectory {-recurse-} . (filePath </>) {-qualify the path-}+ ) . filter (+ `notElem` [".", ".."] --Prevent infinite recursion.+ )+ else {-non-directory-} return {-to IO-monad-} [filePath] --CAVEAT: this could include devices, pipes, sockets, symlinks ...++{- |+ * Finds any file-paths which have been specified more than once.++ * This includes files which have been implicitly specified via a directory.+-}+findDuplicates :: FilePathList -> IO FilePathList+findDuplicates = fmap (map head . filter ((> 1) . length) . ToolShed.Data.Foldable.gather . concat) . mapM expandDirectory++{- |+ * Get the size of a file, treating a directory as an atomic unit.++ * CAVEAT: the size of a symlink, is that of the file to which it refers.+-}+findSize :: System.IO.FilePath -> IO FileSize+findSize filePath = expandDirectory filePath >>= fmap aggregateSize . mapM (\f -> flip (,) f <$> System.IO.withFile f System.IO.ReadMode System.IO.hFileSize)+ -- | Finds file-sizes. findSizes :: FilePathList -> IO [FileSizeAndPath]-findSizes filePathList = (`zip` filePathList) <$> {-lift into IO-monad-} mapM findSize filePathList+findSizes = uncurry (<$>) . (flip zip &&& mapM findSize) --- | Sorts a list of 'FileSizeAndPath' by reverse order of size; ie. largest first.-orderBySize :: [FileSizeAndPath] -> [FileSizeAndPath]-orderBySize = Data.List.sortBy (flip $ Data.Ord.comparing getSize)+-- | Sorts a list of 'FileSizeAndPath' by increasing size; ie. smallest first.+orderByIncreasingSize :: [FileSizeAndPath] -> [FileSizeAndPath]+orderByIncreasingSize = Data.List.sortBy $ Data.Ord.comparing getSize +-- | Sorts a list of 'FileSizeAndPath' by decreasing size; ie. smallest first.+orderByDecreasingSize :: [FileSizeAndPath] -> [FileSizeAndPath]+orderByDecreasingSize = reverse . orderByIncreasingSize+ -- | True if the specified file has the required size according to the specified predicate. hasSizeBy :: (FileSize -> Bool) -- ^ The predicate. -> FileSizeAndPath -- ^ The file-parameters to be tested. -> Bool-hasSizeBy f = f . getSize+hasSizeBy predicate = predicate . getSize -- | Acquire statistics related to a list of files. getFileSizeStatistics :: (Fractional mean, Floating standardDeviation) => [FileSizeAndPath]- -> (Int, FileSize, mean, standardDeviation) -- ^ (Number of components, Total size, Mean size, Standard-deviation).+ -> (Int, FileSize, mean, standardDeviation) -- ^ (Number of components, Aggregate size, Mean size, Standard-deviation). getFileSizeStatistics l = ( length l, sum sizes,@@ -131,9 +160,7 @@ selectSuitableFileSizes predicate fileSizeAndPathList = let (accepted, rejected) = Data.List.partition (hasSizeBy predicate) fileSizeAndPathList in do- Control.Monad.unless (null rejected) $ Control.Monad.Writer.tell ["WARNING: rejecting components of unsuitable size; " ++ show rejected]-- Control.Monad.unless (null accepted) $ Control.Monad.Writer.tell ["Component-(count, total size, mean, standard-deviation): " ++ show (getFileSizeStatistics accepted :: (Int, FileSize, Double, Double))]+ Control.Monad.unless (null rejected) $ Control.Monad.Writer.tell ["WARNING: rejecting files of unsuitable size; " ++ show rejected ++ "."] return {-to Writer-monad-} accepted
src/Squeeze/Squeeze.hs view
@@ -1,5 +1,5 @@ {-- Copyright (C) 2010 Dr. Alistair Ward+ Copyright (C) 2010-2013 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@@ -23,24 +23,30 @@ * Any directory-names are treated as atomic units, rather than individual files. - * Because of the explosion of possible combinations,+ * Because of the exponential growth of possible combinations, an /exact/ match for the available space is frequently found with a surprisingly small set of files.-- [@CAVEATS@]-- * 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 findCombinations,- findBestFit+ findBestFit,+ distributeAndFindBestFit,+ partitionEmptyFilesAndDistributeAndFindBestFit ) where +import Control.Applicative((<$>))+import qualified Control.Arrow import Control.Arrow((&&&))+import qualified Control.Concurrent+import qualified Control.Monad+import qualified Data.List import qualified Factory.Data.Interval-import qualified Squeeze.Data.File as Data.File-import qualified Squeeze.Data.FileCombination as Data.FileCombination+import qualified Squeeze.Control.Concurrent.DivideAndConquer as Control.Concurrent.DivideAndConquer+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 qualified System.IO {- | * Checks that the total aggregate 'Data.File.FileSize', meets or exceeds 'minimumBytes'.@@ -50,6 +56,8 @@ * Generates up to @2^n@ combinations of the @n@ specified files; the algorithm is similar to 'Data.List.subsequences', except that unproductive lines are immediately terminated. This is the performance bottle-neck, and though there may be simpler and faster algorithms, the key attribute is that it operates in constant space. + * CAVEAT: assumes files have been sorted by decreasing size.+ * The algorithm is stable, in that it maintains the specified file-order within each combination; though the order in which the combinations are concatenated is rather arbitrary. -}@@ -64,7 +72,7 @@ ) . nonEmptyCombinations minimumCombinationSize . uncurry zip . ( id &&& Data.File.accumulateSize --Associate the list of possible files with its accumulating size. ) . dropWhile (- Data.File.hasSizeBy (> maximumCombinationSize) --Remove files which individually exceed the maximum permissible; assuming they've been reverse sorted by size.+ Data.File.hasSizeBy (> maximumCombinationSize) --Remove files which individually exceed the maximum permissible; assuming they've been sorted by decreasing size. ) where nonEmptyCombinations :: Data.File.FileSize -> [(Data.File.FileSizeAndPath, Data.File.FileSize)] -> [Data.FileCombination.FileCombination] nonEmptyCombinations _ [] = []@@ -85,7 +93,88 @@ -- | Orders the files by decreasing size, calls 'findCombinations', calls 'Data.FileCombination.risingFilter' to select progressively better solutions. findBestFit :: Factory.Data.Interval.Interval Data.File.FileSize -- ^ The closed interval of acceptible sizes for file-combinations.- -> [Data.File.FileSizeAndPath] -- ^ The input list of file-names and sizes.+ -> [Data.File.FileSizeAndPath] -- ^ The input list of file-names & sizes. -> [Data.FileCombination.FileCombination] -- ^ A reduced list of increasingly suitable file-combinations.-findBestFit solutionSizeBounds = Data.FileCombination.risingFilter (Factory.Data.Interval.getMinBound solutionSizeBounds) . findCombinations solutionSizeBounds . Data.File.orderBySize {-which makes findCombinations faster-}+findBestFit solutionSizeBounds = Data.FileCombination.risingFilter (Factory.Data.Interval.getMinBound solutionSizeBounds) . findCombinations solutionSizeBounds . Data.File.orderByDecreasingSize {-which makes findCombinations faster-} ++{- |+ * Recursively bisects the task, distributing the sub-tasks to 'findBestFit', to utilise the available CPU-cores.++ * The task is bisected by removing the smallest file, then solving the remaining problem for two independent cases; that the selected file is excluded or the selected file is included, in the final solution.+ Selecting the smallest file rather than the largest, seems to balance the load of the sub-tasks more evenly.+ CAVEAT: no account has been taken of the possibility that the smallest file has size zero, which makes the sub-tasks identical.++ * Recombines the part solutions to finds the single monotonically increasing list of file-combinations matching the original criteria.++ * CAVEAT: whilst the ultimate solution is similar, regardless of the specified number of CPU-cores available, the path leading to it typically differs.+-}+distributeAndFindBestFit+ :: RealFrac ratio+ => Data.CommandOptions.CommandOptions ratio+ -> [Data.File.FileSizeAndPath] -- ^ The unordered list of files & sizes.+ -> IO [Data.FileCombination.FileCombination]+distributeAndFindBestFit commandOptions fileSizeAndPathList = let+ slave _ _ [] = return {-to IO-monad-} [Data.FileCombination.nullFileCombination]+ slave 1 commandOptions' increasingFileSizeAndPathList = let+ solutionSizeBounds = Data.CommandOptions.solutionSizeBounds commandOptions'+ in do+ Control.Monad.when (Data.CommandOptions.getVerbosity commandOptions' == maxBound) . System.IO.hPutStrLn System.IO.stderr $ "INFO: acceptable file-size interval " ++ show solutionSizeBounds ++ " bytes."++ return {-to IO-monad-} $ findBestFit solutionSizeBounds increasingFileSizeAndPathList --Delegate the task to the single-threaded algorithm.+ slave numCapabilities' commandOptions' (selectedFileSizeAndPath {-the smallest-} : remainingFileSizeAndPaths) = let+ recurse = slave $ numCapabilities' `div` 2 --Partially apply.+ in do+ Control.Monad.when (Data.CommandOptions.getVerbosity commandOptions' == maxBound) . System.IO.hPutStrLn System.IO.stderr $ "INFO: " ++ show numCapabilities' ++ " CPU-cores => bisecting task into those, with & without " ++ show selectedFileSizeAndPath ++ "."++ fileCombinationsExcludingSelected <- recurse commandOptions' {-i.e the original space-} remainingFileSizeAndPaths --This is about half the total task.++ let maximumBytes' = Data.CommandOptions.getMaximumBytes commandOptions' - Data.File.getSize selectedFileSizeAndPath++ if maximumBytes' < 0+ then return {-to IO-monad-} fileCombinationsExcludingSelected --The selected file won't fit.+ else map (+ Data.FileCombination.prepend selectedFileSizeAndPath --Prepend the selected file to all file-combinations.+ ) <$> recurse (+ commandOptions' {+ Data.CommandOptions.getMaximumBytes = maximumBytes'+ } --Reduce the maximum size; there's no need to account for the minimum, since this is defined as a ratio of the maximum.+ ) remainingFileSizeAndPaths >>= Control.Concurrent.DivideAndConquer.divideAndConquer Data.FileCombination.risingMergeByAggregateFileSize fileCombinationsExcludingSelected --Merge the part-solutions.+ in Control.Concurrent.getNumCapabilities >>= (\numCapabilities -> slave numCapabilities commandOptions $ Data.File.orderByIncreasingSize fileSizeAndPathList)++{- |+ * Neither 'distributeAndFindBestFit' nor 'findBestFit' distinguish between empty & non-empty files,+ but empty files cause significant inefficiency in the former (where the same calculation is performed multiple times)+ & could be treated much more efficiently in the latter (since they're potentially a member of any other solution).++ * This function side-lines empty files, delegates the remaining problem to 'distributeAndFindBestFit' (& consequently 'findBestFit'),+ then prepends combinations of empty files to the resulting combinations of non-empty files.+-}+partitionEmptyFilesAndDistributeAndFindBestFit+ :: RealFrac ratio+ => Data.CommandOptions.CommandOptions ratio+ -> [Data.File.FileSizeAndPath] -- ^ The unordered list of files & sizes.+ -> IO [Data.FileCombination.FileCombination]+partitionEmptyFilesAndDistributeAndFindBestFit commandOptions fileSizeAndPathList+ | Data.CommandOptions.getIncludeEmpty commandOptions = do+ printStatistics fileSizeAndPathList++ concatMap (+ \fileCombination -> map (+ \emptyFilePathCombination -> fileCombination {+ Data.FileCombination.getFilePathList = emptyFilePathCombination ++ Data.FileCombination.getFilePathList fileCombination+ }+ ) $ Data.List.subsequences {-find all combinations-} emptyFiles+ ) <$> nonEmptyFileCombinations+ | otherwise {-exclude empty files-} = do+ Control.Monad.unless (Data.CommandOptions.getVerbosity commandOptions == minBound || null emptyFiles) . System.IO.hPutStrLn System.IO.stderr $ "WARNING: rejecting empty files; " ++ show emptyFiles ++ "."++ Control.Monad.when (null nonEmptyFilePathAndSizeList) $ fail "there are zero non-empty files"++ printStatistics nonEmptyFilePathAndSizeList++ nonEmptyFileCombinations+ where+ printStatistics l = Control.Monad.unless (Data.CommandOptions.getVerbosity commandOptions == minBound || null l) . System.IO.hPutStrLn System.IO.stderr $ "INFO: file-(count, aggregate size, mean, standard-deviation); " ++ show (Data.File.getFileSizeStatistics l :: (Int, Data.File.FileSize, Float, Float)) ++ "."+ (emptyFiles, nonEmptyFilePathAndSizeList) = Control.Arrow.first (map Data.File.getPath) $ Data.List.partition (Data.File.hasSizeBy (== 0)) fileSizeAndPathList+ nonEmptyFileCombinations = distributeAndFindBestFit commandOptions nonEmptyFilePathAndSizeList --Delegate.
+ src/Squeeze/Test/Data/CommandOptions.hs view
@@ -0,0 +1,50 @@+{-# OPTIONS_GHC -fno-warn-orphans #-}+{-+ Copyright (C) 2013 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@] Implements 'Test.QuickCheck.Arbitrary' for 'Data.CommandOptions.CommandOptions'.+-}++module Squeeze.Test.Data.CommandOptions(+-- * Types+-- ** Type-synonyms+ CommandOptions+) where++import Control.Applicative((<$>), (<*>)) +import qualified Test.QuickCheck+import qualified Squeeze.Data.CommandOptions as Data.CommandOptions+import Squeeze.Test.Data.Verbosity()++instance (+ Enum ratio,+ Fractional ratio,+ Ord ratio,+ Real ratio,+ Test.QuickCheck.Arbitrary ratio+ ) => Test.QuickCheck.Arbitrary (Data.CommandOptions.CommandOptions ratio) where+ arbitrary = Data.CommandOptions.mkCommandOptions <$> Test.QuickCheck.arbitrary {-includeEmpty-} <*> (+ abs <$> Test.QuickCheck.arbitrary --maximumBytes.+ ) <*> Test.QuickCheck.arbitrary {-maybeRandomSeed-} <*> (+ recip . succ . abs <$> Test.QuickCheck.arbitrary --minimumUsageRatio.+ ) <*> Test.QuickCheck.arbitrary {-verbosity-}++-- | Defines a concrete type for testing.+type CommandOptions = Data.CommandOptions.CommandOptions Double+
+ src/Squeeze/Test/Data/Verbosity.hs view
@@ -0,0 +1,30 @@+{-# OPTIONS_GHC -fno-warn-orphans #-}+{-+ Copyright (C) 2013 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@] Implements 'Test.QuickCheck.Arbitrary' for 'Distribution.Verbosity.Verbosity'.+-}++module Squeeze.Test.Data.Verbosity() where++import qualified Distribution.Verbosity+import qualified Test.QuickCheck++instance Test.QuickCheck.Arbitrary Distribution.Verbosity.Verbosity where+ arbitrary = Test.QuickCheck.elements [minBound .. maxBound]
src/Squeeze/Test/Performance.hs view
@@ -1,5 +1,5 @@ {-- Copyright (C) 2011 Dr. Alistair Ward+ Copyright (C) 2011-2013 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@@ -58,16 +58,16 @@ let (acceptedFileSizeAndPathList, logFile) = Control.Monad.Writer.runWriter . Data.File.selectSuitableFileSizes (- Data.CommandOptions.isWithinSizeBounds commandOptions --This may reduce the requested number of files, but compensating distorts the requested distribution.+ <= Data.CommandOptions.getMaximumBytes commandOptions --This may reduce the requested number of files, but compensating distorts the requested distribution. ) . ( `zip` map show [0 :: Int ..] --Construct a Data.File.FileSizeAndPath, by using a counter as the file-name. ) . take fileCount . filter (- /= 0 --Though a valid file-size, it doesn't work well when finding valid combinations.+ >= 0 --A suitable distribution shouldn't generate negative file-sizes. ) . map ( ceiling :: Double -> Integer --File-sizes are integral. ) $ Factory.Math.Probability.generatePopulation probabilityDistribution randomGen Control.Monad.when (Data.CommandOptions.getVerbosity commandOptions > minBound) . System.IO.hPutStrLn System.IO.stderr $ Data.List.intercalate "\n" logFile - return {-to IO-monad-} $ Squeeze.findBestFit (Data.CommandOptions.solutionSizeBounds commandOptions) acceptedFileSizeAndPathList+ Squeeze.distributeAndFindBestFit commandOptions acceptedFileSizeAndPathList
src/Squeeze/Test/Squeeze.hs view
@@ -42,10 +42,10 @@ mkFileSizeAndPathList = take 12 . Data.List.nubBy (ToolShed.Data.List.equalityBy snd) . map (toInteger . abs &&& show) --CAVEAT: may be shorter than requested. prop_totalCombinations, prop_fileSizeBounds, prop_allFiles, prop_monotonicFileSize, prop_uniqueFileNames :: [Integer] -> Test.QuickCheck.Property- prop_totalCombinations integers = Test.QuickCheck.label "prop_totalCombinations" $ (length . Data.List.nub . Squeeze.findCombinations (0, fromIntegral (maxBound :: Int)) $ Data.File.orderBySize fileSizeAndPathList) == 2 ^ length fileSizeAndPathList where+ prop_totalCombinations integers = Test.QuickCheck.label "prop_totalCombinations" $ (length . Data.List.nub . Squeeze.findCombinations (0, fromIntegral (maxBound :: Int)) $ Data.File.orderByDecreasingSize fileSizeAndPathList) == 2 ^ length fileSizeAndPathList where fileSizeAndPathList = mkFileSizeAndPathList integers - prop_fileSizeBounds integers = Test.QuickCheck.label "prop_fileSizeBounds" . all ((`Factory.Data.Interval.elem'` fileSizeBounds) . Data.FileCombination.getAggregateFileSize) . Squeeze.findCombinations fileSizeBounds $ Data.File.orderBySize fileSizeAndPathList where+ prop_fileSizeBounds integers = Test.QuickCheck.label "prop_fileSizeBounds" . all ((`Factory.Data.Interval.elem'` fileSizeBounds) . Data.FileCombination.getAggregateFileSize) . Squeeze.findCombinations fileSizeBounds $ Data.File.orderByDecreasingSize fileSizeAndPathList where fileSizeAndPathList = mkFileSizeAndPathList integers fileSizeBounds :: Factory.Data.Interval.Interval Data.File.FileSize@@ -60,7 +60,7 @@ aggregateSize :: Data.File.FileSize aggregateSize = Data.File.aggregateSize fileSizeAndPathList - prop_monotonicFileSize integers = Test.QuickCheck.label "prop_monotonicFileSize" . uncurry (==) . (id &&& Data.List.sort) . map Data.FileCombination.getAggregateFileSize $ Squeeze.findBestFit (0, fromIntegral (maxBound :: Int)) fileSizeAndPathList where+ prop_monotonicFileSize integers = Test.QuickCheck.label "prop_monotonicFileSize" . uncurry (==) . (id &&& Data.List.sort {-stable-}) . map Data.FileCombination.getAggregateFileSize $ Squeeze.findBestFit (0, fromIntegral (maxBound :: Int)) fileSizeAndPathList where fileSizeAndPathList = mkFileSizeAndPathList integers prop_uniqueFileNames integers = Test.QuickCheck.label "prop_uniqueFileNames" . all (