Copyright	Copyright (C) 2008-2011 John Goerzen
License	BSD-3-Clause
Stability	stable
Portability	portable
Safe Haskell	Safe
Language	Haskell2010

Data.BinPacking

Description

Tools for packing into bins

Written by John Goerzen, jgoerzen@complete.org

This module is designed to solve this type of problem: Given a bunch of objects of varying sizes, what is the best possible way to pack them into fixed-size bins? This can be used, for instance, by the datapacker program to pack files onto CDs or DVDs; by manufacturing environments to pack physical items into physicl bins; etc.

A description of bin packing algorithms can be found at http://en.wikipedia.org/wiki/Bin_packing_problem.

Synopsis

type BinPacker = forall size obj. (Num size, Ord size, Show size, Show obj) => [size] -> [(size, obj)] -> Either (BinPackerError size obj) [[(size, obj)]]
data (Num size, Ord size, Show size, Show obj) => BinPackerError size obj
- = BPTooFewBins [(size, obj)]
- | BPSizeTooLarge size (size, obj)
- | BPOther String
packByOrder :: BinPacker
packLargeFirst :: BinPacker

Documentation

type BinPacker = forall size obj. (Num size, Ord size, Show size, Show obj) => [size] -> [(size, obj)] -> Either (BinPackerError size obj) [[(size, obj)]] Source #

The primary type for bin-packing functions.

These functions take a list of size of bins. If every bin is the same size, you can pass repeat binSize to pass an infinite list of bins if the same size. Any surplus bins will simply be ignored.

[size] is the sizes of bins
[(size, obj)] is the sizes and objects
result is Either error or results

data (Num size, Ord size, Show size, Show obj) => BinPackerError size obj Source #

Potential errors returned as Left values by BinPacker functions. Calling show on this value will produce a nice error message suitable for display.

Constructors

BPTooFewBins [(size, obj)]	Ran out of bins; attached value is the list of objects that do not fit
BPSizeTooLarge size (size, obj)	Bin size1 exceeded by at least the given object and size
BPOther String	Other error

Instances

Instances details

(Num size, Ord size, Show size, Show obj, Read size, Read obj) => Read (BinPackerError size obj) Source #
Instance details Defined in Data.BinPacking Methods readsPrec :: Int -> ReadS (BinPackerError size obj) # readList :: ReadS [BinPackerError size obj] # readPrec :: ReadPrec (BinPackerError size obj) # readListPrec :: ReadPrec [BinPackerError size obj] #
(Num size, Ord size, Show size, Show obj) => Show (BinPackerError size obj) Source #
Instance details Defined in Data.BinPacking Methods showsPrec :: Int -> BinPackerError size obj -> ShowS # show :: BinPackerError size obj -> String # showList :: [BinPackerError size obj] -> ShowS #
(Num size, Ord size, Show size, Show obj, Eq obj) => Eq (BinPackerError size obj) Source #
Instance details Defined in Data.BinPacking Methods (==) :: BinPackerError size obj -> BinPackerError size obj -> Bool # (/=) :: BinPackerError size obj -> BinPackerError size obj -> Bool #
(Num size, Ord size, Show size, Show obj) => Error (BinPackerError size obj) Source #	Let us use this as part of the Either monad
Instance details Defined in Data.BinPacking Methods noMsg :: BinPackerError size obj # strMsg :: String -> BinPackerError size obj #

packByOrder :: BinPacker Source #

Pack objects into bins, preserving order. Objects will be taken from the input list one by one, and added to each bin until the bin is full. Work will then proceed on the next bin. No attempt is made to optimize allocations to bins. This is the simplest and most naive bin-packing algorithm, but may not make very good use of bin space.

packLargeFirst :: BinPacker Source #

Pack objects into bins. For each bin, start with the largest objects, and keep packing the largest object from the remainder until no object can be found to put in the bin. This is substantially more efficient than packByOrder, but requires sorting the input.