module M where

data Turny a = Turny [a] [a] Int

-- need at least one value to do iteration
initTurny :: a -> Turny a
initTurny x = Turny [x] [x] 0

-- who's turn is it? And step the state
stepTurny :: Turny a -> (a, Turny a)
stepTurny (Turny l [] i) = stepTurny (Turny l l 0)
stepTurny (Turny l (x:xs) i) = (x, Turny l xs (i+1))

insert :: Ord a => a -> Turny a -> Turny a
insert val = \(Turny l tl i) ->
  let (j, l') = go 0 l
  in if j >= i
       then let (pre, post) = splitAt (j - i) tl
            in Turny l' (pre ++ val : post) i
       else -- insert happened before cursor, so need to step
            Turny l' tl (i+1)
  where
    go idx [] = (idx, [val])
    go idx (x:xs)
      | val >= x = (idx, val:x:xs)
      | otherwise = (x:) <$> go (idx+1) xs