1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
{-# LANGUAGE DeriveGeneric #-}
-- | Ring buffers.
module Game.LambdaHack.Common.RingBuffer
( RingBuffer
, empty, cons, toList, length
) where
import Prelude ()
import Game.LambdaHack.Core.Prelude hiding (length, uncons)
import Data.Binary
import qualified Data.Foldable as Foldable
import qualified Data.Sequence as Seq
import GHC.Generics (Generic)
-- | Ring buffers of a size determined at initialization.
data RingBuffer a = RingBuffer
{ rbCarrier :: Seq.Seq a
, rbMaxSize :: Int
, rbNext :: Int
, rbLength :: Int
}
deriving (Show, Generic)
instance Binary a => Binary (RingBuffer a)
-- Only takes O(log n)).
empty :: Int -> a -> RingBuffer a
empty size dummy =
let rbMaxSize = max 1 size
in RingBuffer (Seq.replicate rbMaxSize dummy) rbMaxSize 0 0
cons :: a -> RingBuffer a -> RingBuffer a
cons a RingBuffer{..} =
let incNext = (rbNext + 1) `mod` rbMaxSize
incLength = min rbMaxSize $ rbLength + 1
in RingBuffer (Seq.update rbNext a rbCarrier) rbMaxSize incNext incLength
toList :: RingBuffer a -> [a]
toList RingBuffer{..} =
let l = Foldable.toList rbCarrier
start = (rbNext + rbMaxSize - rbLength) `mod` rbMaxSize
in take rbLength $ drop start $ l ++ l
length :: RingBuffer a -> Int
length RingBuffer{rbLength} = rbLength
|
