Data.IntMap.NonEmpty.Lazy

A non-empty (by construction) map from integer keys to values a. At least one key-value pair exists in an NEIntMap v at all times.

Functions that take an NEIntMap can safely operate on it with the assumption that it has at least one key-value pair.

Functions that return an NEIntMap provide an assurance that the result has at least one key-value pair.

Data.IntMap.NonEmpty.Lazy re-exports the API of Data.IntMap.Lazy, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output maps are both non-empty (like insert) return NEIntMap, but functions that might potentially return an empty map (like delete) return a IntMap instead.

You can directly construct an NEIntMap with the API from Data.IntMap.NonEmpty.Lazy; it's more or less the same as constructing a normal IntMap, except you don't have access to Data.IntMap.empty. There are also a few ways to construct an NEIntMap from a IntMap:

1. The nonEmptyMap smart constructor will convert a IntMap k a into a Maybe (NEIntMap k a), returning Nothing if the original IntMap was empty.

2. You can use the Data.IntMap.NonEmpty.insertIntMap family of functions to insert a value into a IntMap to create a guaranteed NEIntMap.

3. You can use the IsNonEmpty and IsEmpty patterns to "pattern match" on a IntMap to reveal it as either containing a NEIntMap or an empty map.

4. withNonEmpty offers a continuation-based interface for deconstructing a IntMap and treating it as if it were an NEIntMap.

You can convert an NEIntMap into a IntMap with toMap or IsNonEmpty, essentially "obscuring" the non-empty property from the type.

O(1). A map with a single element.

singleton 1 'a'        == fromList ((1, 'a') :| [])
size (singleton 1 'a') == 1

O(n). Build a non-empty map from a non-empty set of keys and a function which for each key computes its value.

fromSet (\k -> replicate k 'a') (Data.Set.NonEmpty.fromList (3 :| [5])) == fromList ((5,"aaaaa") :| [(3,"aaa")])

O(log n). Insert a new key and value in the map. If the key is already present in the map, the associated value is replaced with the supplied value. insert is equivalent to insertWith const.

See insertMap for a version where the first argument is a IntMap.

insert 5 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'x')])
insert 7 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'a'), (7, 'x')])

O(log n). Insert with a function, combining new value and old value. insertWith f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key, f new_value old_value).

See Data.IntMap.NonEmpty.insertIntMapWith for a version where the first argument is a IntMap.

insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")])
insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])

O(log n). Insert with a function, combining key, new value and old value. insertWithKey f key value mp will insert the pair (key, value) into mp if key does not exist in the map. If the key does exist, the function will insert the pair (key,f key new_value old_value). Note that the key passed to f is the same key passed to insertWithKey.

See insertMapWithKey for a version where the first argument is a IntMap.

let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:xxx|a")])
insertWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")])

O(log n). Combines insert operation with old value retrieval. The expression (insertLookupWithKey f k x map) is a pair where the first element is equal to (lookup k map) and the second element equal to (insertWithKey f k x map).

let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
insertLookupWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "5:xxx|a")]))
insertLookupWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  fromList ((3, "b") :| [(5, "a"), (7, "xxx")]))

This is how to define insertLookup using insertLookupWithKey:

let insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t
insertLookup 5 "x" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "x")]))
insertLookup 7 "x" (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  fromList ((3, "b") :| [(5, "a"), (7, "x")]))

O(log n). Delete a key and its value from the non-empty map. A potentially empty map (IntMap) is returned, since this might delete the last item in the NEIntMap. When the key is not a member of the map, is equivalent to toMap.

delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.Singleton [(3, "b"), (5, "a")]

O(log n). Delete a key and its value from the non-empty map, returning Nothing if the result would be empty.

This is more efficient than nonEmptyMap . delete k because it avoids converting the known-minimum representation back through IntMap when the deleted key is not the minimum.

O(log n). Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

adjust ("new " ++) 5 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "new a")])
adjust ("new " ++) 7 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a")])

O(log n). Adjust a value at a specific key. When the key is not a member of the map, the original map is returned.

let f key x = (show key) ++ ":new " ++ x
adjustWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:new a")])
adjustWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a")])

O(log n). The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

Returns a potentially empty map (IntMap), because we can't know ahead of time if the function returns Nothing and deletes the final item in the NEIntMap.

let f x = if x == "a" then Just "new a" else Nothing
update f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "new a")]
update f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
update f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

O(log n). The expression (updateWithKey f k map) updates the value x at k (if it is in the map). If (f k x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

Returns a potentially empty map (IntMap), because we can't know ahead of time if the function returns Nothing and deletes the final item in the NEIntMap.

let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "5:new a")]
updateWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
updateWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

O(min(n,W)). Lookup and update. The function returns original value, if it is updated. This is different behavior than Data.Map.NonEmpty.updateLookupWithKey. Returns the original key value if the map entry is deleted.

Returns a potentially empty map (IntMap) in the case that we delete the final key of a singleton map.

let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
updateLookupWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == (Just "5:new a", Data.IntMap.fromList ((3, "b") :| [(5, "5:new a")]))
updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing,  Data.IntMap.fromList ((3, "b") :| [(5, "a")]))
updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.IntMap.singleton 5 "a")

O(log n). The expression (alter f k map) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a IntMap. In short : Data.IntMap.lookup k (alter f k m) = f (lookup k m).

Returns a potentially empty map (IntMap), because we can't know ahead of time if the function returns Nothing and deletes the final item in the NEIntMap.

See alterF' for a version that disallows deletion, and so therefore can return NEIntMap.

let f _ = Nothing
alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")]
alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"

let f _ = Just "c"
alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a"), (7, "c")]
alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "c")]

O(log n). The expression (alterF f k map) alters the value x at k, or absence thereof. alterF can be used to inspect, insert, delete, or update a value in a IntMap. In short: Data.IntMap.lookup k <$> alterF f k m = f (lookup k m).

Example:

interactiveAlter :: Int -> NEIntMap Int String -> IO (IntMap Int String)
interactiveAlter k m = alterF f k m where
  f Nothing = do
     putStrLn $ show k ++
         " was not found in the map. Would you like to add it?"
     getUserResponse1 :: IO (Maybe String)
  f (Just old) = do
     putStrLn $ "The key is currently bound to " ++ show old ++
         ". Would you like to change or delete it?"
     getUserResponse2 :: IO (Maybe String)

Like Data.IntMap.alterF for IntMap, alterF can be considered to be a unifying generalization of lookup and delete; however, as a constrast, it cannot be used to implement insert, because it must return a IntMap instead of an NEIntMap (because the function might delete the final item in the NEIntMap). When used with trivial functors like Identity and Const, it is often slightly slower than specialized lookup and delete. However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.

See alterF' for a version that disallows deletion, and so therefore can return NEIntMap and be used to implement insert

Note on rewrite rules:

This module includes GHC rewrite rules to optimize alterF for the Const and Identity functors. In general, these rules improve performance. The sole exception is that when using Identity, deleting a key that is already absent takes longer than it would without the rules. If you expect this to occur a very large fraction of the time, you might consider using a private copy of the Identity type.

Note: Unlike Data.IntMap.alterF for IntMap, alterF is not a flipped version of the at combinator from Control.Lens.At. However, it match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.

O(log n). Variant of alter that disallows deletion. Allows us to guarantee that the result is also a non-empty IntMap.

O(log n). Variant of alterF that disallows deletion. Allows us to guarantee that the result is also a non-empty IntMap.

Like Data.IntMap.alterF for IntMap, can be used to generalize and unify lookup and insert. However, because it disallows deletion, it cannot be used to implement delete.

See alterF for usage information and caveats.

Note: Neither alterF nor alterF' can be considered flipped versions of the at combinator from Control.Lens.At. However, this can match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.

WARNING: The rewrite rule for Identity exposes an inconsistency in undefined behavior for Data.IntMap. Data.IntMap.alterF will actually maintain the original key in the map when used with Identity; however, Data.IntMap.insertWith will replace the orginal key in the map. The rewrite rule for alterF' has chosen to be faithful to Data.IntMap.insertWith, and not Data.IntMap.alterF, for the sake of a cleaner implementation.

O(n). Fold the values in the map using the given right-associative binary operator, such that foldr f z == foldr f z . elems.

elemsList map = foldr (:) [] map

let f a len = len + (length a)
foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4

O(n). Fold the values in the map using the given left-associative binary operator, such that foldl f z == foldl f z . elems.

elemsList = reverse . foldl (flip (:)) []

let f len a = len + (length a)
foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4

O(n). A version of foldr that uses the value at the maximal key in the map as the starting value.

Note that, unlike foldr1 for IntMap, this function is total if the input function is total.

O(n). A version of foldl that uses the value at the minimal key in the map as the starting value.

Note that, unlike foldl1 for IntMap, this function is total if the input function is total.

O(n). Fold the keys and values in the map using the given right-associative binary operator, such that foldrWithKey f z == Prelude.foldr (uncurry f) z . toAscList.

For example,

keysList map = foldrWithKey (\k x ks -> k:ks) [] map

O(n). Fold the keys and values in the map using the given left-associative binary operator, such that foldlWithKey f z == Prelude.foldl (\z' (kx, x) -> f z' kx x) z . toAscList.

For example,

keysList = reverse . foldlWithKey (\ks k x -> k:ks) []

O(n). Fold the keys and values in the map using the given semigroup, such that

foldMapWithKey f = fold1 . Data.IntMap.NonEmpty.mapWithKey f

WARNING: Differs from Data.IntMap.foldMapWithKey, which traverses positive items first, then negative items.

This can be an asymptotically faster than Data.IntMap.NonEmpty.foldrWithKey or Data.IntMap.NonEmpty.foldlWithKey for some monoids.

O(n). Return all elements of the map in the ascending order of their keys.

elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])

O(n). Return all keys of the map in ascending order.

keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5])

O(n). An alias for toAscList. Return all key/value pairs in the map in ascending key order.

assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])

O(n). The non-empty set of all keys of the map.

keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5])

O(n). Filter all values that satisfy the predicate.

Returns a potentially empty map (IntMap), because we could potentailly filter out all items in the original NEIntMap.

filter (> "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"
filter (> "x") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty
filter (< "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty

O(n). Filter all keys/values that satisfy the predicate.

Returns a potentially empty map (IntMap), because we could potentailly filter out all items in the original NEIntMap.

filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

O(m*log(n/m + 1)), m <= n. Restrict an NEIntMap to only those keys found in a Set.

m `restrictKeys` s = filterWithKey (k _ -> k `Set.member` s) m
m `restrictKeys` s = m `intersection` fromSet (const ()) s

O(m*log(n/m + 1)), m <= n. Remove all keys in a Set from an NEIntMap.

m `withoutKeys` s = filterWithKey (k _ -> k `Set.notMember` s) m
m `withoutKeys` s = m `difference` fromSet (const ()) s

O(n). Partition the map according to a predicate.

Returns a These with potentially two non-empty maps:

• This n1 means that the predicate was true for all items.

• That n2 means that the predicate was false for all items.

• These n1 n2 gives n1 (all of the items that were true for the predicate) and n2 (all of the items that were false for the predicate).

See also split.

partition (> "a") (fromList ((5,"a") :| [(3,"b")])) == These (singleton 3 "b") (singleton 5 "a")
partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))

O(n). Partition the map according to a predicate.

Returns a These with potentially two non-empty maps:

• This n1 means that the predicate was true for all items, returning the original map.

• That n2 means that the predicate was false for all items, returning the original map.

• These n1 n2 gives n1 (all of the items that were true for the predicate) and n2 (all of the items that were false for the predicate).

See also split.

partitionWithKey (\ k _ -> k > 3) (fromList ((5,"a") :| [(3,"b")])) == These (singleton 5 "a") (singleton 3 "b")
partitionWithKey (\ k _ -> k < 7) (fromList ((5,"a") :| [(3,"b")])) == This  (fromList ((3, "b") :| [(5, "a")]))
partitionWithKey (\ k _ -> k > 7) (fromList ((5,"a") :| [(3,"b")])) == That  (fromList ((3, "b") :| [(5, "a")]))

O(n). Map values and collect the Just results.

Returns a potentially empty map (IntMap), because the function could potentially return Nothing on all items in the NEIntMap.

let f x = if x == "a" then Just "new a" else Nothing
mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "new a"

O(n). Map keys/values and collect the Just results.

Returns a potentially empty map (IntMap), because the function could potentially return Nothing on all items in the NEIntMap.

let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "key : 3"

O(n). Map values and separate the Left and Right results.

Returns a These with potentially two non-empty maps:

• This n1 means that the results were all Left.

• That n2 means that the results were all Right.

• These n1 n2 gives n1 (the map where the results were Left) and n2 (the map where the results were Right)

let f a = if a < "c" then Left a else Right a
mapEither f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    == These (fromList ((3,"b") :| [(5,"a")])) (fromList ((1,"x") :| [(7,"z")]))

mapEither (\ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    == That (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))

O(n). Map keys/values and separate the Left and Right results.

Returns a These with potentially two non-empty maps:

• This n1 means that the results were all Left.

• That n2 means that the results were all Right.

• These n1 n2 gives n1 (the map where the results were Left) and n2 (the map where the results were Right)

let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
mapEitherWithKey f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    == These (fromList ((1,2) :| [(3,6)])) (fromList ((5,"aa") :| [(7,"zz")]))

mapEitherWithKey (\_ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))
    == That (fromList ((1,"x") :| [(3,"b"), (5,"a"), (7,"z")]))

O(log n). The expression (split k map) is potentially a These containing up to two NEIntMaps based on splitting the map into maps containing items before and after the given key k. It will never return a map that contains k itself.

• Nothing means that k was the only key in the the original map, and so there are no items before or after it.

• Just (This n1) means k was larger than or equal to all items in the map, and n1 is the entire original map (minus k, if it was present)

• Just (That n2) means k was smaller than or equal to all items in the map, and n2 is the entire original map (minus k, if it was present)

• Just (These n1 n2) gives n1 (the map of all keys from the original map less than k) and n2 (the map of all keys from the original map greater than k)

split 2 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (fromList ((3,"b") :| [(5,"a")]))  )
split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (singleton 5 "a")                  )
split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (These (singleton 3 "b") (singleton 5 "a"))
split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (singleton 3 "b")                  )
split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (fromList ((3,"b") :| [(5,"a")]))  )
split 5 (singleton 5 "a")                 == Nothing

O(log n). The expression (splitLookup k map) splits a map just like split but also returns lookup k map, as the first field in the These:

splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That      (That  (fromList ((3,"b") :| [(5,"a")])))
splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That  (singleton 5 "a"))
splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That      (These (singleton 3 "b") (singleton 5 "a"))
splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This  (singleton 3 "b"))
splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That      (This  (fromList ((3,"b") :| [(5,"a")])))
splitLookup 5 (singleton 5 "a")                 == This  "a"

O(1). Decompose a map into pieces based on the structure of the underlying tree. This function is useful for consuming a map in parallel.

No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first submap less than all elements in the second, and so on).

Note that the current implementation does not return more than four submaps, but you should not depend on this behaviour because it can change in the future without notice.

O(m*log(n/m + 1)), m <= n. This function is defined as (isSubmapOf = isSubmapOfBy (==)).

O(m*log(n/m + 1)), m <= n. The expression (isSubmapOfBy f t1 t2) returns True if all keys in t1 are in tree t2, and when f returns True when applied to their respective values. For example, the following expressions are all True:

isSubmapOfBy (==) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
isSubmapOfBy (<=) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (fromList (('a',1) :| [('b',2)]))

But the following are all False:

isSubmapOfBy (==) (singleton 'a' 2) (fromList (('a',1) :| [('b',2)]))
isSubmapOfBy (<)  (singleton 'a' 1) (fromList (('a',1) :| [('b',2)]))
isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (singleton 'a' 1)

O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a submap but not equal). Defined as (isProperSubmapOf = isProperSubmapOfBy (==)).

O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a submap but not equal). The expression (isProperSubmapOfBy f m1 m2) returns True when m1 and m2 are not equal, all keys in m1 are in m2, and when f returns True when applied to their respective values. For example, the following expressions are all True:

isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))
isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))

But the following are all False:

isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (fromList ((1,1) :| [(2,2)]))
isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (singleton 1 1))
isProperSubmapOfBy (<)  (singleton 1 1)               (fromList ((1,1) :| [(2,2)]))

O(1). The minimal key of the map. Note that this is total, making Data.IntMap.lookupMin obsolete. It is constant-time, so has better asymptotics than Data.IntMap.lookupMin and Data.IntMap.findMin, as well.

findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b")

O(log n). The maximal key of the map. Note that this is total, making Data.IntMap.lookupMin obsolete.

findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a")

O(1). Delete the minimal key. Returns a potentially empty map (IntMap), because we might end up deleting the final key in a singleton map. It is constant-time, so has better asymptotics than Data.IntMap.deleteMin.

deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(5,"a"), (7,"c")]
deleteMin (singleton 5 "a") == Data.IntMap.empty

O(log n). Delete the maximal key. Returns a potentially empty map (IntMap), because we might end up deleting the final key in a singleton map.

deleteMax (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(3,"b"), (5,"a")]
deleteMax (singleton 5 "a") == Data.IntMap.empty

O(1). Delete and find the minimal key-value pair. It is constant-time, so has better asymptotics that Data.IntMap.minView for IntMap.

Note that unlike Data.IntMap.deleteFindMin for IntMap, this cannot ever fail, and so is a total function. However, the result IntMap is potentially empty, since the original map might have contained just a single item.

deleteFindMin (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((3,"b"), Data.IntMap.fromList [(5,"a"), (10,"c")])

O(log n). Delete and find the minimal key-value pair.

Note that unlike Data.IntMap.deleteFindMax for IntMap, this cannot ever fail, and so is a total function. However, the result IntMap is potentially empty, since the original map might have contained just a single item.

deleteFindMax (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((10,"c"), Data.IntMap.fromList [(3,"b"), (5,"a")])

O(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (IntMap), because we might end up deleting the final key in the map if the function returns Nothing. See adjustMin for a version that can guaruntee that we return a non-empty map.

updateMin (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "Xb"), (5, "a")]
updateMin (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

O(log n). Update the value at the maximal key. Returns a potentially empty map (IntMap), because we might end up deleting the final key in the map if the function returns Nothing. See adjustMax for a version that can guarantee that we return a non-empty map.

updateMax (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "Xa")]
updateMax (\ _ -> Nothing)         (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"

O(1). A version of updateMin that disallows deletion, allowing us to guarantee that the result is also non-empty.

O(log n). A version of updateMax that disallows deletion, allowing us to guarantee that the result is also non-empty.

O(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (IntMap), because we might end up deleting the final key in the map if the function returns Nothing. See adjustMinWithKey for a version that guaruntees a non-empty map.

updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

O(log n). Update the value at the maximal key. Returns a potentially empty map (IntMap), because we might end up deleting the final key in the map if the function returns Nothing. See adjustMaxWithKey for a version that guaruntees a non-empty map.

updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")]
updateMinWithKey (\ _ _ -> Nothing)                     (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"

O(1). A version of adjustMaxWithKey that disallows deletion, allowing us to guarantee that the result is also non-empty. Note that it also is able to have better asymptotics than updateMinWithKey in general.

O(log n). A version of updateMaxWithKey that disallows deletion, allowing us to guarantee that the result is also non-empty.

O(1). Retrieves the value associated with minimal key of the map, and the map stripped of that element. It is constant-time, so has better asymptotics than Data.IntMap.minView for IntMap.

Note that unlike Data.IntMap.minView for IntMap, this cannot ever fail, so doesn't need to return in a Maybe. However, the result IntMap is potentially empty, since the original map might have contained just a single item.

minView (fromList ((5,"a") :| [(3,"b")])) == ("b", Data.IntMap.singleton 5 "a")

O(log n). Retrieves the value associated with maximal key of the map, and the map stripped of that element.

Note that unlike Data.IntMap.maxView from IntMap, this cannot ever fail, so doesn't need to return in a Maybe. However, the result IntMap is potentially empty, since the original map might have contained just a single item.

maxView (fromList ((5,"a") :| [(3,"b")])) == ("a", Data.IntMap.singleton 3 "b")

O(n). Test if the internal map structure is valid.