Data.LinearSplit

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.

Documentation

data Item a b

Representation of the work item

Constructors

Item

Fields

item :: 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

Range of work items

Constructors

Range

Fields

price :: 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]

Partition items to minimize the maximum cost over all ranges

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

Partition items with accumulating small items

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

Partition the items based on the greedy algoritm