-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Common bin packing heuristics
--
-- An implementation of the first-fit, modified-first-fit, last-fit,
-- best-fit, worst-fit, and almost-last-fit bin packing heuristics. Items
-- can be packed in order of both decreasing and increasing size (and, of
-- course, in unmodified order).
--
-- The module supports both the standard (textbook) minimization problem
-- (How many bins do I need?) and the more practical fitting
-- problem (I've got n bins; which items can I take?).
--
-- The API is simple and the module is documented with Haddock (complete
-- with examples). The implementation of the above-mentioned heuristics
-- is complete and partially tested with QuickCheck. However, note that
-- speed has not been a primary concern to date.
--
-- Patches and feedback are very welcome.
@package Binpack
@version 0.3
-- | This module implements a number of common bin packing heurstics:
-- FirstFit, LastFit, BestFit, WorstFit, and
-- AlmostWorstFit. In addtion, the not-so-common, but analytically
-- superior (in terms of worst-case behavior), ModifiedFirstFit
-- heuristic is also supported. Items can be packed in order of both
-- Decreasing and Increasing size (and, of course, in
-- unmodified order; see AsGiven).
--
-- The module supports both the standard (textbook) minimization problem
-- ("How many bins do I need to pack all items?"; see
-- minimizeBins and countBins) and the more practical
-- fitting problem ("I've got n bins; which items can I take?";
-- see binpack).
--
-- The well-known heuristics are described online in many places and are
-- not further discussed here. For example, see
-- http://www.cs.arizona.edu/icon/oddsends/bpack/bpack.htm for an
-- overview. A description of the ModifiedFirstFit algorithm is
-- harder to come by online, hence a brief description and references are
-- provided below.
--
-- Note that most published analysis assumes items to be sorted in some
-- specific (mostly Decreasing) order. This module does not
-- enforce such assumptions, rather, any ordering can be combined with
-- any placement heuristic.
--
-- If unsure what to pick, then try FirstFit Decreasing as
-- a default. Use BestFit (in combination with binpack) if
-- you want your bins filled evenly.
--
-- A short overview of the ModifiedFirstFit heuristic follows.
-- This overview is based on the description given in (Yue and Zhang,
-- 1995).
--
-- Let lst denote the list of items to be bin-packed, let
-- x denote the size of the smallest element in lst,
-- and let cap denote the capacity of one bin. lst is
-- split into the four sub-lists, lA, lB, lC,
-- lD.
--
--
-- - lA All items strictly larger than
-- cap/2.
-- - lB All items of size at most cap/2 and
-- strictly larger than cap/3.
-- - lC All items of size at most cap/3 and
-- stricly larger than (cap - x)/5.
-- - lD The rest, i.e., all items of size at
-- most (cap - x)/5.
--
--
-- Items are placed as follows:
--
--
-- - Create a list of length lA bins. Place each item in
-- lA into its own bin (while maintaining relative item order
-- with respect to lst). Note: relevant published analysis
-- assumes that lst is sorted in order of decreasing
-- size.
-- - Take the list of bins created in Step 1 and reverse it.
-- - Sequentially consider each bin b. If the two smallest
-- items in lC do NOT fit together into b of if there a
-- less than two items remaining in lC, then pack nothing into
-- b and move on to the next bin (if any). If they do fit
-- together, then find the largest item x1 in lC that
-- would fit together with the smallest item in lC into
-- b. Remove x1 from lC. Then find the largest
-- item x2, x2 \= x1, in lC that will now fit
-- into b together with x1. Remove x1
-- from lC. Place both x1 and x2 into
-- b and move on to the next item.
-- - Reverse the list of bins again.
-- - Use the FirstFit heuristic to place all remaining items,
-- i.e., lB, lD, and any remaining items of
-- lC.
--
--
-- References:
--
--
-- - D.S. Johnson and M.R. Garey. A 71/60 Theorem for Bin-Packing.
-- Journal of Complexity, 1:65-106, 1985.
-- - M. Yue and L. Zhang. A Simple Proof of the Inequality MFFD(L)
-- <= 71/60 OPT(L) + 1, L for the MFFD Bin-Packing Algorithm. Acta
-- Mathematicae Applicatae Sinica, 11(3):318-330, 1995.
--
module Data.BinPack
-- | What placement heuristic should be used?
data PlacementPolicy
-- | Traverse bin list from head to last and place item in
-- the first bin that has sufficient capacity.
FirstFit :: PlacementPolicy
-- | See above.
ModifiedFirstFit :: PlacementPolicy
-- | Traverse bin list from last to head and place item in
-- the first bin that has sufficient capacity.
LastFit :: PlacementPolicy
-- | Place item in the bin with the most capacity.
BestFit :: PlacementPolicy
-- | Place item in the bin with the least (but sufficient) capacity.
WorstFit :: PlacementPolicy
-- | Choose the 2nd to worst-fitting bin.
AlmostWorstFit :: PlacementPolicy
-- | How to pre-process the input.
data OrderPolicy
-- | Don't modify item order.
AsGiven :: OrderPolicy
-- | Sort from largest to smallest.
Decreasing :: OrderPolicy
-- | Sort from smallest to largest.
Increasing :: OrderPolicy
-- | A function that maps an item b to its size a. The
-- constraint (Num a, Ord a) has been omitted from
-- the type, but is required by the exposed functions.
type Measure a b = b -> a
-- | A Bin is a list of items.
type Bin = []
-- | The list of all possible OrderPolicy choices. Useful for
-- benchmarking.
allOrders :: [OrderPolicy]
-- | The list of all possible PlacmentPolicy choices. Useful for
-- benchmarking.
allPlacements :: [PlacementPolicy]
-- | All supported ordering and placment choices. Useful for benchmarking.
allHeuristics :: [(PlacementPolicy, OrderPolicy)]
-- | Bin packing without a limit on the number of bins (minimization
-- problem). Assumption: The maximum item size is at most the size of one
-- bin (this is not checked).
--
-- Examples:
--
--
-- - Pack the words of the senctene "Bin packing heuristics are a
-- lot of fun!" into bins of size 11, assuming the size of a word is
-- its length. The Increasing ordering yields a sub-optimal result
-- that leaves a lot of empty space in the bins.
--
--
--
-- minimizeBins FirstFit Increasing length 11 (words "Bin packing heuristics are a lot of fun!")
-- ~~> ([1,4,4,2],[["heuristics"],["packing"],["fun!","lot"],["are","Bin","of","a"]])
--
--
--
-- - Similarly, for Int. Note that we use id as the
-- Measure for the size of an Int. In this case, all bins
-- are full.
--
--
--
-- minimizeBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4]
-- ~~> ([0,0,0],[[2,3,3,3],[4,7],[1,10]])
--
minimizeBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> ([a], [Bin b])
-- | Wrapper around minimizeBins; useful if only the number of
-- required bins is of interest. See minimizeBins for a
-- description of the arguments.
--
-- Examples:
--
--
-- - How many bins of size 11 characters each do we need to pack the
-- words of the sentence "Bin packing heuristics are a lot of
-- fun!"?
--
--
--
-- countBins FirstFit Increasing length 11 (words "Bin packing heuristics are a lot of fun!")
-- ~~> 4
--
--
--
-- - Similarly, for Int. Note that we use id as the
-- Measure for the size of an Int.
--
--
--
-- countBins FirstFit Decreasing id 11 [3,7,10,3,1,3,2,4]
-- ~~> 3
--
countBins :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> a -> [b] -> Int
-- | Bin pack with a given limit on the number (and sizes) of bins. Instead
-- of creating new bins, this version will return a list of items that
-- could not be packed (if any).
--
-- Example: We have two bins, one of size 10 and one of size 12. Which
-- words can we fit in there?
--
--
-- binpack WorstFit Decreasing length [10, 12] (words "Bin packing heuristics are a lot of fun!")
-- ~~> ([0,0],[["heuristics"],["a","fun!","packing"]],["of","lot","are","Bin"])
--
binpack :: (Num a, Ord a) => PlacementPolicy -> OrderPolicy -> Measure a b -> [a] -> [b] -> ([a], [Bin b], [b])
instance Show PlacementPolicy
instance Eq PlacementPolicy
instance Ord PlacementPolicy
instance Show OrderPolicy
instance Eq OrderPolicy
instance Ord OrderPolicy
instance Arbitrary PlacementPolicy
instance Arbitrary OrderPolicy