Implement Min\/Max ops

1 files changed, 50 insertions, 16 deletions

diff --git a/src/Data/Dependent/EnumMap/Strict/Internal.hs b/src/Data/Dependent/EnumMap/Strict/Internal.hs
index 2726a50..c93b821 100644
--- a/src/Data/Dependent/EnumMap/Strict/Internal.hs
+++ b/src/Data/Dependent/EnumMap/Strict/Internal.hs
@@ -77,6 +77,7 @@ singleton k v =
   let (i, inf) = fromEnum1 k
   in DEnumMap (IM.singleton i (KV inf v))
 
+-- TODO: probably doesn't make much sense until we have DEnumSet? Or should we ust lists instead?
 -- fromSet
 
 -- ** From Unordered Lists
@@ -292,7 +293,7 @@ unionWithKey f (DEnumMap m1 :: DEnumMap k v) (DEnumMap m2) = DEnumMap (IM.unionW
     f' :: Int -> KV k v -> KV k v -> KV k v
     f' i (KV inf1 v1) (KV inf2 v2) = case toEnum1 i inf1 of
       Some k1 -> typeCheck1 k1 i inf2 $ KV inf1 (f k1 (coe1 v1) (coe1 v2))
-        -- TODO: are the coe1 correct? is the use of typeCheck1 fine?
+        -- TODO: are the coe1 correct? is the typeCheck1 needed?
 
 unions :: (Foldable f, Enum1 k, TestEquality k) => f (DEnumMap k v) -> DEnumMap k v
 unions xs = Foldable.foldl' union empty xs
@@ -409,6 +410,7 @@ mapAccumRWithKey f acc0 (DEnumMap m) =
 
 -- * Folds
 
+-- TODO: did I miss any typeCheck1 or typeCheck2 here or anywhere else? Or are any checks spurious?
 foldr :: (forall a. v a -> acc -> acc) -> acc -> DEnumMap k v -> acc
 foldr f acc0 (DEnumMap m) = IM.foldr (\(KV _ v) acc -> f v acc) acc0 m
 
@@ -527,6 +529,7 @@ split k (DEnumMap m) = bimap DEnumMap DEnumMap (IM.split (fst $ fromEnum1 k) m)
 
 -- TODO: is this coe1 fine or can we readably check that IM doesn't cheat
 -- and give us a value with a wrong type?
+-- Or Maybe we should return @Some v@ instead of @v a@? But it has to match @k a@, right?
 splitLookup :: Enum1 k => k a -> DEnumMap k v -> (DEnumMap k v, Maybe (v a), DEnumMap k v)
 splitLookup k (DEnumMap m) =
   let (m1, mkv, m2) = IM.splitLookup (fst $ fromEnum1 k) m
@@ -542,21 +545,52 @@ splitRoot (DEnumMap m) = DEnumMap <$> IM.splitRoot m
 
 -- * Min\/Max
 
--- lookupMin
--- lookupMax
--- findMin
--- findMax
--- deleteMin
--- deleteMax
--- deleteFindMin
--- deleteFindMax
--- updateMin
--- updateMax
--- updateMinWithKey
--- updateMaxWithKey
--- minView
--- maxView
--- minViewWithKey
+lookupMin :: Enum1 k => DEnumMap k v -> Maybe (DSum k v)
+lookupMin (DEnumMap m) = kVToDSum <$> IM.lookupMin m
+
+lookupMax :: Enum1 k => DEnumMap k v -> Maybe (DSum k v)
+lookupMax (DEnumMap m) = kVToDSum <$> IM.lookupMax m
+
+findMin :: Enum1 k => DEnumMap k v -> DSum k v
+findMin (DEnumMap m) = kVToDSum $ IM.findMin m
+
+findMax :: Enum1 k => DEnumMap k v -> DSum k v
+findMax (DEnumMap m) = kVToDSum $ IM.findMax m
+
+deleteMin :: DEnumMap k v -> DEnumMap k v
+deleteMin (DEnumMap m) = DEnumMap $ IM.deleteMin m
+
+deleteMax :: DEnumMap k v -> DEnumMap k v
+deleteMax (DEnumMap m) = DEnumMap $ IM.deleteMax m
+
+deleteFindMin :: Enum1 k => DEnumMap k v -> (DSum k v, DEnumMap k v)
+deleteFindMin (DEnumMap m) = bimap kVToDSum DEnumMap $ IM.deleteFindMin m
+
+deleteFindMax :: Enum1 k => DEnumMap k v -> (DSum k v, DEnumMap k v)
+deleteFindMax (DEnumMap m) = bimap kVToDSum DEnumMap $ IM.deleteFindMax m
+
+updateMin :: forall c (k :: c -> Type) (v :: c -> Type). Enum1 k => (forall a. v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v
+updateMin f = updateMinWithKey (\_ x -> f x)
+
+updateMinWithKey :: Enum1 k => (forall a. k a -> v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v
+updateMinWithKey f (DEnumMap m) =
+  DEnumMap (IM.updateMinWithKey (\i (KV inf v) -> case toEnum1 i inf of Some k -> KV inf <$> f k (coe1 v)) m)
+
+updateMax :: forall c (k :: c -> Type) (v :: c -> Type). Enum1 k => (forall a. v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v
+updateMax f = updateMaxWithKey (\_ x -> f x)
+
+updateMaxWithKey :: Enum1 k => (forall a. k a -> v a -> Maybe (v a)) -> DEnumMap k v -> DEnumMap k v
+updateMaxWithKey f (DEnumMap m) =
+  DEnumMap (IM.updateMaxWithKey (\i (KV inf v) -> case toEnum1 i inf of Some k -> KV inf <$> f k (coe1 v)) m)
+
+minView :: DEnumMap k v -> Maybe (v a, DEnumMap k v)
+minView (DEnumMap m) = bimap (\(KV _ v) -> coe1 v) DEnumMap <$> IM.minView m
+
+maxView :: DEnumMap k v -> Maybe (v a, DEnumMap k v)
+maxView (DEnumMap m) = bimap (\(KV _ v) -> coe1 v) DEnumMap <$> IM.maxView m
+
+minViewWithKey :: Enum1 k => DEnumMap k v -> Maybe (DSum k v, DEnumMap k v)
+minViewWithKey (DEnumMap m) = bimap kVToDSum DEnumMap <$> IM.minViewWithKey m
 
 maxViewWithKey :: Enum1 k => DEnumMap k v -> Maybe (DSum k v, DEnumMap k v)
 maxViewWithKey (DEnumMap m) = bimap kVToDSum DEnumMap <$> IM.maxViewWithKey m