optics-extra-0.1: src/Optics/Extra/Internal/Vector.hs

module Optics.Extra.Internal.Vector
  ( ordinalNub
  ) where

import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet

-- | Return the the subset of given ordinals within a given bound and in order
-- of the first occurrence seen.
--
-- Bound: @0 <= x < l@
--
-- >>> ordinalNub 3 [-1,2,1,4,2,3]
-- [2,1]
ordinalNub ::
  Int   {- ^ strict upper bound -} ->
  [Int] {- ^ ordinals           -} ->
  [Int] {- ^ unique, in-bound ordinals, in order seen -}
ordinalNub l xs = foldr (ordinalNubHelper l) (const []) xs IntSet.empty

ordinalNubHelper :: Int -> Int -> (IntSet -> [Int]) -> (IntSet -> [Int])
ordinalNubHelper l x next seen
  | outOfBounds || notUnique = next seen
  | otherwise                = x : next (IntSet.insert x seen)
  where
  outOfBounds = x < 0 || l <= x
  notUnique   = x `IntSet.member` seen