content: {-# LANGUAGE OverloadedStrings #-}
  
  -- |
  -- SPDX-License-Identifier: BSD-3-Clause
  --
  -- Sliding window for activity monitoring.
  module Swarm.Util.WindowedCounter (
    WindowedCounter,
    Offsettable (..),
  
    -- * Construction
    mkWindow,
  
    -- * Querying
    getOccupancy,
  
    -- * Maintenance
    insert,
    discardGarbage,
  ) where
  
  import Data.Aeson
  import Data.Set (Set)
  import Data.Set qualified as Set
  import Swarm.Util.UnitInterval
  import Prelude hiding (length)
  
  -- | Values that can be offset by an integral amount
  class Offsettable a where
    offsetBy :: Int -> a -> a
  
  -- | A "sliding window" of a designated span that supports insertion
  -- of tick "timestamps" that represent some state of interest during that tick.
  -- This data structure supports efficient querying of the ratio of
  -- {ticks for which that state existed}
  -- to the
  -- {total number of ticks spanned by the window}.
  --
  -- The primary use case is in displaying the "activity level" of a robot.
  --
  -- == Efficiency considerations
  --
  -- The data retention of the window shall be maintained externally by
  -- invoking the 'discardGarbage' function. However, we should not
  -- unconditionally invoke this function upon each game tick.
  --
  -- For efficiency, we do not want to iterate over every robot
  -- upon every tick; we only want to "visit" a robot if it is actually
  -- doing work that tick.
  -- Because of this, there may be some ticks in which the oldest element
  -- that is still stored falls outside of the nominal retention window
  -- while a robot is inactive.
  --
  -- One might think we could perform garbage collection whenever we execute queries.
  -- However, in the context in which the view powered by the query is generated, we
  -- are not permitted to mutate the "state" of the game
  -- (the type signature of the rendering function is @AppState -> Widget Name@).
  --
  -- Therefore, when we perform "queries" on the window, we must apply some
  -- filtering to exclude the "stragglers"; data members that have already fallen outside
  -- the window but have not yet been "garbage collected".
  -- We use a 'Set' to allow this filtering to be performed in @O(log n)@ time.
  --
  -- In the worst case, the entire dataset may "age out" without being garbage collected,
  -- so that an @O(log n)@ filtering operation might be performed upon every "frame refresh"
  -- of the UI view.
  -- However, we also store the largest element of the window separately from the 'Set' so that
  -- we can compare against it for a @O(1)@ short-circuited path once every member ages out.
  --
  -- The maximum number of elements ever stored in the 'Set' will be the width of the nominal
  -- span, even after some protracted failure to "garbage collect".
  data WindowedCounter a = WindowedCounter
    { _members :: Set a
    , _lastLargest :: Maybe a
    -- ^ NOTE: It is possible that '_lastLargest' may not exist in the 'Set'.
    , _nominalSpan :: Int
    -- ^ Data retention window. This value is guaranteed positive by the smart constructor.
    }
    deriving (Eq, Show)
  
  -- | Automatically deriving 'FromJSON' circumvents the protection offered by "smart constructors",
  -- and the 'ToJSON' instance may expose internal details.
  -- Therefore, we write our own custom implementations.
  --
  -- This 'ToJSON' instance is strictly for diagnostic purposes, and we can reveal
  -- a bit more information than is used for parsing.
  instance (ToJSON a) => ToJSON (WindowedCounter a) where
    toJSON (WindowedCounter membersSet _lastLargest nominalSpan) =
      object
        [ "members" .= toJSON membersSet
        , "span" .= nominalSpan
        ]
  
  -- | We discard any "internal state" revealed by the 'ToJSON' instance and
  -- just use the "span" so that we can rely on any guarantees offered by the
  -- smart constructor, no matter the origin of the JSON.
  --
  -- Discarding the internal state is OK, because it is not integral to gameplay;
  -- it is merely informational as a live indicator in the UI.
  instance FromJSON (WindowedCounter a) where
    parseJSON = withObject "WindowedCounter" $ \v -> do
      s <- v .: "span"
      return $ mkWindow s
  
  -- | NOTE: We take the absolute value of the "window span" argument
  -- so that we can make guarantees about the output of 'getOccupancy'.
  mkWindow ::
    -- | window span
    Int ->
    WindowedCounter a
  mkWindow = WindowedCounter Set.empty Nothing . abs
  
  -- | Return the ratio of {members in the window} to the {integral span
  -- represented by the window}.
  --
  -- The "current time" should be at least as large as the largest
  -- element of the window.
  --
  -- A fully-contiguous collection of ticks would have an occupancy ratio of @1@.
  --
  -- == Unit interval guarantee
  -- The returned ratio is /guaranteed/ to lie on the unit interval, because:
  --
  -- * Both the numerator and denominator of the ratio are guaranteed positive, and
  -- * 'discardGarbage' guarantees that the set size is less than or equal to
  --   the nominal span.
  getOccupancy ::
    (Ord a, Offsettable a) =>
    -- | current time
    a ->
    WindowedCounter a ->
    UnitInterval Double
  getOccupancy currentTime wc@(WindowedCounter s lastLargest nominalSpan) =
    mkInterval $
      if Set.null s || maybe False (< referenceTick) lastLargest
        then 0
        else fromIntegral (Set.size culledSet) / fromIntegral nominalSpan
   where
    referenceTick = offsetBy (negate nominalSpan) currentTime
    -- Cull the window according to the current time
    WindowedCounter culledSet _ _ = discardGarbage currentTime wc
  
  -- | Invocations of this function shall be guarded externally
  -- by the conditions meant to be tracked in the window.
  --
  -- Proper usage dictates that the value inserted should always
  -- be at least as large as the current largest element of the set.
  --
  -- The 'discardGarbage' function is called from inside this function
  -- so that maintenance of the data structure is simplified.
  insert ::
    (Ord a, Offsettable a) =>
    -- | current time
    a ->
    WindowedCounter a ->
    WindowedCounter a
  insert x (WindowedCounter s lastLargest nominalSpan) =
    discardGarbage x $ WindowedCounter (Set.insert x s) newLargest nominalSpan
   where
    newLargest = Just $! maybe x (max x) lastLargest
  
  -- | Drop the leading elements that are not larger than the cutoff.
  --
  -- This function is already called by the 'insert' function, so clients
  -- do not necessarily ever have to call this directly.
  -- However, there may
  -- be opportunity to call this even more often, i.e. in code paths where the
  -- robot is visited but the condition for insertion is not met.
  --
  -- == Invariant
  -- If the largest member of the set is the current time,
  -- then after calling this function, the difference between smallest and largest
  -- value in the set is strictly less than the "nominal span", and the size of the
  -- set is less than or equal to the nominal span.
  --
  -- For example, if the nominal span is @3@, the current time is @7@, and the
  -- set entails a contiguous sequence @{2, 3, 4, 5, 6, 7}@, then the pivot for 'Set.split' will be
  -- @7 - 3 = 4@. The set becomes @{5, 6, 7}@, with cardinality equal to the nominal span.
  discardGarbage ::
    (Ord a, Offsettable a) =>
    -- | current time
    a ->
    WindowedCounter a ->
    WindowedCounter a
  discardGarbage currentTime (WindowedCounter s lastLargest nominalSpan) =
    WindowedCounter larger lastLargest nominalSpan
   where
    -- NOTE: Neither output set of 'split' includes the "pivot" value.
    (_smaller, larger) = Set.split (offsetBy (negate nominalSpan) currentTime) s
  