Documentation

Class of types that can be mapped by a lens or a projection to an Ord type.

For a type V, defines a lens from V to and Ord type K.

A general-purpose finite, insert-ordered, map that is strict in its keys and values.

The strictness is enforced by the underlying strict Map that can be looked-up by a projection or lens. and the ordering is maintained by the constructing functions, leveraging StrictSeq to hold the insert-order of the keys.

TODO: DecShareCBOR instance

\(O(1)\).

\(O(1)\).

\(O(1)\).

\(O(1)\). Strict in its arguments.

\(O(\log n)\). If the key is not present lookup returns Nothing.

\(O(\log n)\). Key membership check.

fliped version of lookup

\(O(n \log n)\).

\(O(n \log n)\). Checks membership before snoc'ing. De-duplicates the StrictSeq without overwriting. Starts from the left or head, using foldl`

\(O(n \log n)\). Checks membership before snoc'ing. De-duplicates the StrictSeq and collects and returns the duplicates found. Starts from the left or head, using foldl`

\(O(1)\).

\(O(n \log n)\).

\(O(1)\).

\(O(n \log n)\).

\(O(1)\). Shallow invariant using just length and size.

\(O(n \log n)\). Deep, costly invariant using membership check for each value. By the pigeon-hole principle, this check is exhaustive.

\(O(\log n)\). Checks membership before snoc'ing.

\(O(\log n)\). Checks membership before cons'ing.

\(O(\log n)\). Checks membership before cons'ing. Overwrites a duplicate.

\(O(\log n)\). Checks membership before snoc'ing. Overwrites a duplicate.

\( O(n \log m) \). For every uncons-ed element from the sequence on the right, check its membership in the sequence on the left, before snoc'ing it. Preserve order. Remove duplicates from sequence on the right.

\( O(m \log n) \). For every unsnoc-ed element from the sequence on the left, check its membership in the sequence on the right, before cons'ing it. Preserve order. Remove duplicates from sequence on the left.

\(O(\log n)\). Value membership check.

\(O(n)\). Given a Set of ks, and an OMap k v return a pair of Map and OMap where the ks in the Set have been removed from the OMap and presented as a separate Map.

\(O(n)\). Like adjust.

Returns the original OMap unaltered when the key does not exist.

If the key exists, then the function is applied to the value, but we need to consider three possible cases:

1. The modified value's okeyL is unaltered - we return omap with the adjusted value,
2. The modified value's okeyL is altered, but not a duplicate - we return the omap with adjusted key (in place) and value
3. The modified value's okeyL is altered and is a duplicate - we return the omap with the old key deleted from the sequence but without inserting the new key since it is a duplicate, and deleting old value and inserting the new value in place of its duplicate.

Examples:

>>> import Data.OMap.Strict
>>> import Lens.Micro
>>> instance HasOKey Int (Int, Char) where okeyL = _1
>>> let m = fromFoldable $ zip [1,2] ['a','b'] :: OMap Int (Int, Char)
>>> m
StrictSeq {fromStrict = fromList [(1,(1,'a')),(2,(2,'b'))]}
>>> let adjustingFn (k, v) = (k, succ v) -- Changes the value
>>> let overwritingAdjustingFn (k,v) = (succ k, v) -- Changes the `okeyL`.
>>> adjust adjustingFn 1 m
StrictSeq {fromStrict = fromList [(1,(1,'b')),(2,(2,'b'))]}
>>> adjust overwritingAdjustingFn  1 m
StrictSeq {fromStrict = fromList [(2,(2,'a'))]}

\( O(n \log n) \)