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