Squeeze.hs

{-
	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@]

	* Returns combinations of the specified files, which fit into the available space, without wasting more than the specified ratio.

	* Any directory-names are treated as atomic units, rather than individual files.

	* Because of the explosion 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
) where

import			Control.Arrow((&&&))
import qualified	Factory.Data.Interval
import qualified	Squeeze.Data.File		as Data.File
import qualified	Squeeze.Data.FileCombination	as Data.FileCombination

{- |
	* Checks that the 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.

	* 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.

	* 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.
-}
findCombinations
	:: Factory.Data.Interval.Interval Data.File.FileSize	-- ^ The closed interval of acceptible aggregate size, for file-combinations.
	-> [Data.File.FileSizeAndPath]				-- ^ The list of file-names & sizes, ordered by decreasing size.
	-> [Data.FileCombination.FileCombination]		-- ^ The resulting unordered list of suitable file-combinations.
findCombinations (minimumCombinationSize, maximumCombinationSize)	= filter (
	Data.FileCombination.hasSizeBy (>= minimumCombinationSize)
 ) . (
	Data.FileCombination.nullFileCombination :
 ) . 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.
 ) where
	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.hasSizeBy (<= maximumCombinationSize) combinationIncluding	= (combinationExcluding :) . (combinationIncluding :)
				| otherwise										= (combinationExcluding :)
				where
					combinationIncluding :: Data.FileCombination.FileCombination
					combinationIncluding	= Data.FileCombination.prepend fileSizeAndPath combinationExcluding

-- | 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.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-}