LinearSplit-0.1: Partition the sequence of items to the subsequences in the order given

Portability non-portable experimental virukav@gmail.com

Data.LinearSplit

Description

The LinearSplit module implements partitioning the sequence of items to the subsequences in the order given. The next functions are exported: a) gPartition - split the sequence of items items using greedy heuristic. b) lPartition - split the sequence of items to minimize the maximum cost over all the subsequences using linear partition algorithm (see the 'The Algorithm Design Manual' by Steven S. Skiena..) c) ltPartition - the approximation of the linear partition algorithm. The large size of the work items space is decreased by combining the consecutive items based on the threshold parameter.

Synopsis

# Documentation

data Item a b Source

Representation of the work item

Constructors

 Item Fieldsitem :: a weight :: b

Instances

 (Eq a, Eq b) => Eq (Item a b) (Ord a, Ord b) => Ord (Item a b) (Show a, Show b) => Show (Item a b)

data Range a b Source

Range of work items

Constructors

 Range Fieldsprice :: b low :: a high :: a

Instances

 (Eq a, Eq b) => Eq (Range a b) (Ord a, Ord b) => Ord (Range a b) (Show a, Show b) => Show (Range a b)

lPartition :: (Num b, Ord b) => Int -> [Item a b] -> [Range a b]Source

Partition items to minimize the maximum cost over all ranges

ltPartition :: (Num b, Ord b) => Int -> [Item a b] -> b -> [Range a b]Source

Partition items with accumulating small items

gPartition :: (Ord b, Num b) => ([Item a b] -> Bool) -> Int -> [Item a b] -> [Range a b]Source

Partition the items based on the greedy algoritm