Modulecabal-install-solver-3.18.1.0Haskell2010

Distribution.Solver.Modular.WeightedPSQ

1 type
12 values

Packagecabal-install-solver-3.18.1.0
Exports13
LanguageHaskell2010
LicenceBSD-3-Clause
SourceWeightedPSQ.hs

newtypenewtype WeightedPSQ w k v

An association list that is sorted by weight.

Each element has a key (k), value (v), and weight (w). All operations that add elements or modify weights stably sort the elements by weight.

Instances5Functor, Foldable, Traversable, Eq, Show

Functor (WeightedPSQ w k)Defined in cabal-install-solver-3.18.1.0 · Distribution.Solver.Modular.WeightedPSQ
Foldable (WeightedPSQ w k)Defined in cabal-install-solver-3.18.1.0 · Distribution.Solver.Modular.WeightedPSQ
Traversable (WeightedPSQ w k)Defined in cabal-install-solver-3.18.1.0 · Distribution.Solver.Modular.WeightedPSQ
(Eq w, Eq k, Eq v) => Eq (WeightedPSQ w k v)Defined in cabal-install-solver-3.18.1.0 · Distribution.Solver.Modular.WeightedPSQ
(Show w, Show k, Show v) => Show (WeightedPSQ w k v)Defined in cabal-install-solver-3.18.1.0 · Distribution.Solver.Modular.WeightedPSQ

valuefromList :: Ord w => [(w, k, v)] -> WeightedPSQ w k v

O(N log N).

valuetoList :: WeightedPSQ w k v -> [(w, k, v)]

O(1). Return the elements in order.

valuekeys :: WeightedPSQ w k v -> [k]

O(N). Return the keys in order.

valueweights :: WeightedPSQ w k v -> [w]

O(N). Return the weights in order.

valueisZeroOrOne :: WeightedPSQ w k v -> Bool

O(1). Return True if the WeightedPSQ contains zero or one elements.

valuefilter :: (v -> Bool) -> WeightedPSQ k w v -> WeightedPSQ k w v

O(N).

valuelookup :: Eq k => k -> WeightedPSQ w k v -> Maybe v

O(N). Return the value associated with the first occurrence of the give key, if it exists.

valuemapWithKey :: (k -> v1 -> v2) -> WeightedPSQ w k v1 -> WeightedPSQ w k v2

O(N). Update the values.

valuemapWeightsWithKey

:: Ord w2
=> k -> w1 -> w2
-> WeightedPSQ w1 k v
-> WeightedPSQ w2 k v

O(N log N). Update the weights.

valuetraverseWithKey

:: Applicative f
=> k -> v -> f v'
-> WeightedPSQ w k v
-> f (WeightedPSQ w k v')

O(N). Traverse and update values in some applicative functor.

valueunion

:: Ord w
=> WeightedPSQ w k v
-> WeightedPSQ w k v
-> WeightedPSQ w k v

O((N + M) log (N + M)). Combine two WeightedPSQs, preserving all elements. Elements from the first WeightedPSQ come before elements in the second when they have the same weight.

valuetakeUntil :: (v -> Bool) -> WeightedPSQ w k v -> WeightedPSQ w k v

O(N). Return the prefix of values ending with the first element that satisfies p, or all elements if none satisfy p.