content: module Axel.Utils.List where
  
  import Axel.Prelude
  
  import Axel.Utils.Tuple
    ( Annotated
    , annotate
    , annotateWith
    , annotation
    , unannotate
    )
  
  import Control.Lens ((%~), (&), (^.), _1, _2)
  
  import Data.Function (on)
  import Data.List (elemIndex, isPrefixOf, sortOn)
  import Data.List.NonEmpty (NonEmpty((:|)))
  import qualified Data.List.NonEmpty as NE (groupBy, head, map)
  import Data.Maybe (fromJust, listToMaybe)
  
  head' :: [a] -> Maybe a
  head' = listToMaybe
  
  -- | 'unsafeHead' == 'head'.
  unsafeHead :: [a] -> a
  unsafeHead = fromJust . listToMaybe
  
  groupAllWith :: (Ord b) => (a -> b) -> [a] -> [Annotated b (NonEmpty a)]
  groupAllWith f =
    map extractAnnotation .
    NE.groupBy ((==) `on` (^. annotation)) . map (annotateWith f)
    where
      extractAnnotation xs =
        annotate (NE.head xs ^. annotation) (NE.map unannotate xs)
  
  -- This is not stable in the technical sense of the term, just roughly stable-ish for limited use cases.
  stablyGroupAllWith ::
       (Eq a, Ord b) => (a -> b) -> [a] -> [Annotated b (NonEmpty a)]
  stablyGroupAllWith f xs =
    map unannotate $
    sortOn (^. annotation) $
    map
      (annotateWith $ \(groupRepresentative :| _, _) ->
         elemIndex groupRepresentative xs) $
    groupAllWith f xs
  
  removeOut :: (Eq a) => (a -> Bool) -> [a] -> ([a], [a])
  removeOut f xs =
    let removed = filter f xs
        xs' = filter (not . (`elem` removed)) xs
     in (xs', removed)
  
  remove :: (Eq a) => (a -> Bool) -> [a] -> [a]
  remove f xs = fst $ removeOut f xs
  
  -- https://stackoverflow.com/a/26530188/2391244
  takeUntil :: (Eq a) => [a] -> [a] -> [a]
  takeUntil _ [] = []
  takeUntil [] _ = []
  takeUntil xs (y:ys) =
    if xs `isPrefixOf` (y : ys)
      then []
      else y : takeUntil xs ys
  
  filterMapOut :: (a -> Maybe b) -> [a] -> ([a], [b])
  filterMapOut f =
    foldr
      (\x acc ->
         case f x of
           Just x' -> acc & _2 %~ (x' :)
           Nothing -> acc & _1 %~ (x :))
      ([], [])
  
  filterMap :: (a -> Maybe b) -> [a] -> [b]
  filterMap f xs = snd $ filterMapOut f xs
  