{-# LANGUAGE Safe, MagicHash, MultiParamTypeClasses, FlexibleInstances #-}

{- |
    Module      :  SDP.ByteList.Ublist
    Copyright   :  (c) Andrey Mulik 2019
    License     :  BSD-style
    Maintainer  :  work.a.mulik@gmail.com
    Portability :  portable
    
    "SDP.ByteList.Ublist" provides 'Ublist' - strict boxed unrolled linked list.
-}
module SDP.ByteList.Ublist
(
  -- * Exports
  module SDP.Indexed,
  module SDP.Unboxed,
  module SDP.Sort,
  module SDP.Scan,
  module SDP.Set,
  
  -- * Ublist
  Ublist
)
where

import Prelude ()
import SDP.SafePrelude
import SDP.Indexed
import SDP.Unboxed
import SDP.Sort
import SDP.Scan
import SDP.Set

import SDP.Templates.AnyChunks
import SDP.Prim.SBytes
import SDP.SortM.Tim

default ()

--------------------------------------------------------------------------------

-- | 'Ublist' is unrolled linked list of unboxed values.
type Ublist = AnyChunks SBytes#

--------------------------------------------------------------------------------

instance (Unboxed e) => Sort (Ublist e) e
  where
    sortBy :: Compare e -> Ublist e -> Ublist e
sortBy Compare e
cmp Ublist e
es = (forall s. ST s (Ublist e)) -> Ublist e
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Ublist e)) -> Ublist e)
-> (forall s. ST s (Ublist e)) -> Ublist e
forall a b. (a -> b) -> a -> b
$ do STBytes# s e
es' <- Ublist e -> ST s (STBytes# s e)
forall (m :: * -> *) v v'. Thaw m v v' => v -> m v'
thaw Ublist e
es; Compare e -> STBytes# s e -> ST s ()
forall (m :: * -> *) v e i.
(LinearM m v e, BorderedM m v i) =>
Compare e -> v -> m ()
timSortBy Compare e
cmp STBytes# s e
es'; STBytes# s e -> ST s (Ublist e)
forall e s. Unboxed e => STBytes# s e -> ST s (Ublist e)
done STBytes# s e
es'
    
    sortedBy :: (e -> e -> Bool) -> Ublist e -> Bool
sortedBy e -> e -> Bool
f = [SBytes# e] -> Bool
forall s. (Sort s e, Linear s e) => [s] -> Bool
go ([SBytes# e] -> Bool)
-> (Ublist e -> [SBytes# e]) -> Ublist e -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Ublist e -> [SBytes# e]
forall (rep :: * -> *) e. AnyChunks rep e -> [rep e]
toChunks
      where
        go :: [s] -> Bool
go (s
x1 : s
x2 : [s]
xs) = (e -> e -> Bool) -> s -> Bool
forall s e. Sort s e => (e -> e -> Bool) -> s -> Bool
sortedBy e -> e -> Bool
f s
x1 Bool -> Bool -> Bool
&& s -> e
forall l e. Linear l e => l -> e
last s
x1 e -> e -> Bool
`f` s -> e
forall l e. Linear l e => l -> e
head s
x2 Bool -> Bool -> Bool
&& [s] -> Bool
go (s
x2 s -> [s] -> [s]
forall a. a -> [a] -> [a]
: [s]
xs)
        go      [s
x1]      = (e -> e -> Bool) -> s -> Bool
forall s e. Sort s e => (e -> e -> Bool) -> s -> Bool
sortedBy e -> e -> Bool
f s
x1
        go       []       = Bool
True

--------------------------------------------------------------------------------

{-# INLINE done #-}
done :: (Unboxed e) => STBytes# s e -> ST s (Ublist e)
done :: STBytes# s e -> ST s (Ublist e)
done =  STBytes# s e -> ST s (Ublist e)
forall (m :: * -> *) v' v. Freeze m v' v => v' -> m v
unsafeFreeze