Distribution.Solver.Modular.WeightedPSQ

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.

O(N log N).

O(1). Return the elements in order.

O(N). Return the keys in order.

O(N). Return the weights in order.

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

O(N).

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

O(N). Update the values.

O(N log N). Update the weights.

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

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.

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