{-----------------------------------------------------------------------------
    reactive-banana

    Implementation of a bag whose elements are ordered by arrival time.
------------------------------------------------------------------------------}
{-# LANGUAGE TupleSections #-}
module Reactive.Banana.Prim.Low.OrderedBag where

import qualified Data.HashMap.Strict as Map
import           Data.Hashable
import           Data.List ( foldl', sortBy )
import           Data.Maybe
import           Data.Ord

{-----------------------------------------------------------------------------
    Ordered Bag
------------------------------------------------------------------------------}
type Position = Integer

data OrderedBag a = OB !(Map.HashMap a Position) !Position

empty :: OrderedBag a
empty :: forall a. OrderedBag a
empty = forall a. HashMap a Position -> Position -> OrderedBag a
OB forall k v. HashMap k v
Map.empty Position
0

-- | Add an element to an ordered bag after all the others.
-- Does nothing if the element is already in the bag.
insert :: (Eq a, Hashable a) => OrderedBag a -> a -> OrderedBag a
insert :: forall a. (Eq a, Hashable a) => OrderedBag a -> a -> OrderedBag a
insert (OB HashMap a Position
xs Position
n) a
x = forall a. HashMap a Position -> Position -> OrderedBag a
OB (forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
Map.insertWith (\Position
_new Position
old -> Position
old) a
x Position
n HashMap a Position
xs) (Position
nforall a. Num a => a -> a -> a
+Position
1)

-- | Add a sequence of elements to an ordered bag.
--
-- The ordering is left-to-right. For example, the head of the sequence
-- comes after all elements in the bag,
-- but before the other elements in the sequence.
inserts :: (Eq a, Hashable a) => OrderedBag a -> [a] -> OrderedBag a
inserts :: forall a. (Eq a, Hashable a) => OrderedBag a -> [a] -> OrderedBag a
inserts = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall a. (Eq a, Hashable a) => OrderedBag a -> a -> OrderedBag a
insert

-- | Reorder a list of elements to appear as they were inserted into the bag.
-- Remove any elements from the list that do not appear in the bag.
inOrder :: (Eq a, Hashable a) => [(a,b)] -> OrderedBag a -> [(a,b)]
inOrder :: forall a b.
(Eq a, Hashable a) =>
[(a, b)] -> OrderedBag a -> [(a, b)]
inOrder [(a, b)]
xs (OB HashMap a Position
bag Position
_) = forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing forall a b. (a, b) -> a
fst) forall a b. (a -> b) -> a -> b
$
    forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe (\(a, b)
x -> (,(a, b)
x) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
Map.lookup (forall a b. (a, b) -> a
fst (a, b)
x) HashMap a Position
bag) [(a, b)]
xs