content: {-# LANGUAGE CPP #-}
  -------------------------------------------------------------------------------
  -- |
  -- Module      :  Silica.Internal.List
  -- Copyright   :  (C) 2014-2016 Edward Kmett and Eric Mertens
  -- License     :  BSD-style (see the file LICENSE)
  -- Maintainer  :  Edward Kmett <ekmett@gmail.com>
  -- Stability   :  provisional
  -- Portability :  non-portable
  --
  -- This module provides utility functions on lists used by the library
  -- implementation.
  -------------------------------------------------------------------------------
  module Silica.Internal.List
    ( ordinalNub
    ) where
  
  import Data.IntSet (IntSet)
  import qualified Data.IntSet as IntSet
  
  #ifdef HLINT
  {-# ANN module "HLint: ignore Redundant bracket" #-}
  #endif
  
  -- | 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
  