{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts, FlexibleInstances #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveFunctor #-}
-- | Warning, this is Experimental!
--
-- Data.NonNull attempts to extend the concepts from
-- 'Data.List.NonEmpty' to any 'IsSequence'.
--
-- 'NonNull' is for a sequence with 1 or more elements.
-- 'Stream' is for a 'NonNull' that supports efficient
-- modification of the front of the sequence.
--
-- This code is experimental and likely to change dramatically and future versions.
-- Please send your feedback.
module Data.NonNull (
    NonNull(..)
  , SafeSequence(..)
  , NotEmpty
  , MonoFoldable1(..)
  , OrdNonNull(..)
  , (<|)
) where

import Prelude hiding (head, tail, init, last, reverse, seq, filter, replicate)
import Data.MonoTraversable
import Data.Sequences
import Control.Exception.Base (Exception, throw)
import Data.Semigroup
import qualified Data.Monoid as Monoid
import Data.Data
import Data.Maybe (fromMaybe)
import qualified Data.List.NonEmpty as NE
import qualified Data.Foldable as F

import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L
import qualified Data.Text as T
import qualified Data.Text.Lazy as TL
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Storable as VS
import qualified Data.Sequence as Seq

data NullError = NullError String deriving (Show, Typeable)
instance Exception NullError

-- | a 'NonNull' sequence has 1 or more items
-- In contrast, 'IsSequence' is allowed to have zero items.
--
-- Any NonNull functions that
-- decreases the number of elements in the sequences
-- will return a different 'Nullable' type.
--
-- The Nullable type for a 'NonEmpty' List is the normal List '[]'
--
-- NonNull allows one to safely perform what would otherwise be partial functions.
-- Hopefully you have abandoned partial functions, perhaps you are using the safe package.
-- However, safe essentially provides convenience functions for null checking.
-- With NonNull rather than always reacting with null checks we can proactively encode in our program when we know that a type is NonNull.
-- Now we have an invariant encoded in our types, making our program easier to understand.
-- This information is leveraged to avoid awkward null checking later on.
class (SemiSequence seq, IsSequence (Nullable seq), Element seq ~ Element (Nullable seq)) => NonNull seq where
    type Nullable seq

    -- | safely construct a 'NonNull' sequence from a 'NonEmpty' list
    fromNonEmpty :: NE.NonEmpty (Element seq) -> seq

    -- | safely convert a 'Nullable' to a 'NonNull'
    fromNullable :: Nullable seq -> Maybe seq

    -- | convert a 'Nullable' with elements to a 'NonNull'
    -- throw an exception if the 'Nullable' is empty.
    -- do not use this unless you have proved your structure is non-null
    nonNull :: Nullable seq -> seq
    nonNull nullable = case fromNullable nullable of
                         Nothing -> throw $ NullError "Data.NonNull.nonNull (NonNull default): expected non-null"
                         Just xs -> xs

    -- | used internally to construct a 'NonNull'.
    -- does not check whether the 'Nullable' is empty
    -- do not use this unless you have proved your structure is nonNull
    -- nonNullUnsafe :: Nullable seq -> seq

    -- | convert a 'NonNull' to a 'Nullable'
    toNullable :: seq -> Nullable seq

    -- | Like cons, prepends an element.
    -- However, the prepend is to a Nullable, creating a 'NonNull'
    --
    -- Generally this uses cons underneath.
    -- cons is not efficient for most data structures.
    --
    -- Alternatives:
    --   * if you don't need to cons, use 'fromNullable' or 'nonNull' if you can create your structure in one go.
    --   * if you need to cons, you might be able to start off with an efficient data structure such as a 'NonEmpty' List.
    --     'fronNonEmpty' will convert that to your data structure using the structure's fromList function.
    ncons :: Element seq -> Nullable seq -> seq

    -- | like 'uncons' of 'SemiSequence'
    nuncons :: seq -> (Element seq, Maybe seq)
    nuncons xs = case uncons $ toNullable xs of
                   Nothing -> error "Data.NonNull.nuncons: data structure is null, it should be non-null"
                   Just (x, xsNullable) -> (x, fromNullable xsNullable)

    -- | like 'uncons' of 'SemiSequence'
    splitFirst :: seq -> (Element seq, Nullable seq)
    splitFirst xs = case uncons $ toNullable xs of
                     Nothing -> error "Data.NonNull.splitFirst: data structure is null, it should be non-null"
                     Just tup -> tup


    -- | like 'Sequence.filter', but starts with a NonNull
    nfilter :: (Element seq -> Bool) -> seq -> Nullable seq

    -- | like 'Sequence.filterM', but starts with a NonNull
    nfilterM :: Monad m => (Element seq -> m Bool) -> seq -> m (Nullable seq)

    -- | i must be > 0. like 'Sequence.replicate'
    nReplicate :: Index seq -> Element seq -> seq

{-
maybeToNullable :: (Monoid (Nullable seq), NonNull seq) => Maybe seq -> Nullable seq
maybeToNullable Nothing   = mempty
maybeToNullable (Just xs) = toNullable xs
-}

-- | SafeSequence contains functions that would be partial on a 'Nullable'
class SafeSequence seq where
    -- | like Data.List, but not partial on a NonEmpty
    head :: seq -> Element seq
    -- | like Data.List, but not partial on a NonEmpty
    tail :: seq -> Nullable seq
    -- | like Data.List, but not partial on a NonEmpty
    last :: seq -> Element seq
    -- | like Data.List, but not partial on a NonEmpty
    init :: seq -> Nullable seq




-- | NonNull list reuses 'Data.List.NonEmpty'
instance NonNull (NE.NonEmpty a) where
    type Nullable (NE.NonEmpty a) = [a]

    fromNonEmpty = id
    {-# INLINE fromNonEmpty #-}
    fromNullable = NE.nonEmpty

    nonNull = NE.fromList
    -- nonNullUnsafe = nonNull

    toNullable = NE.toList

    ncons = (NE.:|)

    nfilter = NE.filter
    nfilterM f = filterM f . toNullable

    nReplicate i x = NE.unfold unfold i
      where
        unfold countdown | countdown < 1 = (x, Nothing)
                         | otherwise     = (x, Just (countdown - 1))

instance SafeSequence (NE.NonEmpty a) where
    head = NE.head
    tail = NE.tail
    last = NE.last
    init = NE.init


-- | a newtype wrapper indicating there are 1 or more elements
-- unwrap with 'toNullable'
newtype NotEmpty seq = NotEmpty { fromNotEmpty :: seq }
                       deriving (Eq, Ord, Read, Show, Data, Typeable, Functor)
type instance Element (NotEmpty seq) = Element seq
deriving instance MonoFunctor seq => MonoFunctor (NotEmpty seq)
deriving instance MonoFoldable seq => MonoFoldable (NotEmpty seq)
deriving instance MonoTraversable seq => MonoTraversable (NotEmpty seq)

instance Monoid seq => Semigroup (NotEmpty seq) where
  x <> y  = NotEmpty (fromNotEmpty x `Monoid.mappend` fromNotEmpty y)
  sconcat = NotEmpty . Monoid.mconcat . fmap fromNotEmpty . NE.toList



instance SemiSequence seq => SemiSequence (NotEmpty seq) where
    type Index (NotEmpty seq) = Index seq

    singleton     = NotEmpty . singleton
    intersperse e = fmap $ intersperse e
    reverse       = fmap reverse
    find f        = find f . fromNotEmpty
    cons x        = fmap $ cons x
    snoc xs x     = fmap (flip snoc x) xs
    sortBy f      = fmap $ sortBy f


-- normally we favor defaulting, should we use it here?
-- this re-uses IsSequence functions and IsSequence uses defaulting
instance IsSequence seq => NonNull (NotEmpty seq) where
    type Nullable (NotEmpty seq) = seq

    fromNonEmpty = NotEmpty . fromList . NE.toList
    fromNullable xs | onull xs = Nothing
                    | otherwise = Just $ NotEmpty xs

    nonNull xs | onull xs = throw $ NullError "Data.NonNull.nonNull expected NotEmpty"
               | otherwise = NotEmpty xs

    -- nonNullUnsafe = NotEmpty
    toNullable = fromNotEmpty
    ncons x xs = NotEmpty $ cons x xs

    -- | i must be > 0. like 'Sequence.replicate'
    -- < 0 produces a 1 element NonEmpty
    nReplicate i x | i < 1 = ncons x mempty
                   | otherwise = NotEmpty $ replicate i x

    nfilter f = filter f . toNullable
    nfilterM f = filterM f . toNullable


instance SafeSequence (NotEmpty (Seq.Seq a)) where
    head = flip Seq.index 1 . fromNotEmpty
    last (NotEmpty xs) = Seq.index xs (Seq.length xs - 1)
    tail = Seq.drop 1 . fromNotEmpty
    init (NotEmpty xs) = Seq.take (Seq.length xs - 1) xs

instance SafeSequence (NotEmpty (V.Vector a)) where
    head = V.head . fromNotEmpty
    tail = V.tail . fromNotEmpty
    last = V.last . fromNotEmpty
    init = V.init . fromNotEmpty

instance U.Unbox a => SafeSequence (NotEmpty (U.Vector a)) where
    head = U.head . fromNotEmpty
    tail = U.tail . fromNotEmpty
    last = U.last . fromNotEmpty
    init = U.init . fromNotEmpty

instance VS.Storable a => SafeSequence (NotEmpty (VS.Vector a)) where
    head = VS.head . fromNotEmpty
    tail = VS.tail . fromNotEmpty
    last = VS.last . fromNotEmpty
    init = VS.init . fromNotEmpty

instance SafeSequence (NotEmpty S.ByteString) where
    head = S.head . fromNotEmpty
    tail = S.tail . fromNotEmpty
    last = S.last . fromNotEmpty
    init = S.init . fromNotEmpty

instance SafeSequence (NotEmpty T.Text) where
    head = T.head . fromNotEmpty
    tail = T.tail . fromNotEmpty
    last = T.last . fromNotEmpty
    init = T.init . fromNotEmpty

instance SafeSequence (NotEmpty L.ByteString) where
    head = L.head . fromNotEmpty
    tail = L.tail . fromNotEmpty
    last = L.last . fromNotEmpty
    init = L.init . fromNotEmpty

instance SafeSequence (NotEmpty TL.Text) where
    head = TL.head . fromNotEmpty
    tail = TL.tail . fromNotEmpty
    last = TL.last . fromNotEmpty
    init = TL.init . fromNotEmpty

infixr 5 <|

-- | Prepend an element to a NonNull
(<|) :: NonNull seq => Element seq -> seq -> seq
(<|) = cons


-- | fold operations that assume one or more elements
-- Guaranteed to be safe on a NonNull
class (NonNull seq, MonoFoldable (Nullable seq)) => MonoFoldable1 seq where
  ofoldMap1 :: Semigroup m => (Element seq -> m) -> seq -> m
  ofoldMap1 f = maybe (error "Data.NonNull.foldMap1 (MonoFoldable1)") id . getOption . ofoldMap (Option . Just . f) . toNullable

  -- ofold1 :: (Semigroup m ~ Element seq) => seq -> Element seq
  -- ofold1 = ofoldMap1 id

  -- @'foldr1' f = 'Prelude.foldr1' f . 'otoList'@
  ofoldr1 :: (Element seq -> Element seq -> Element seq) -> seq -> Element seq
  ofoldr1 f = fromMaybe (error "Data.NonNull.foldr1 (MonoFoldable1): empty structure") .
                  (ofoldr mf Nothing) . toNullable
    where
      mf x Nothing = Just x
      mf x (Just y) = Just (f x y)

  -- | A variant of 'ofoldl\'' that has no base case,
  -- and thus may only be applied to non-empty structures.
  --
  -- @'foldl1\'' f = 'Prelude.foldl1' f . 'otoList'@
  ofoldl1' :: (Element seq -> Element seq -> Element seq) -> seq -> Element seq
  ofoldl1' f = fromMaybe (error "ofoldl1': empty structure") .
                  (ofoldl' mf Nothing) . toNullable
    where
      mf Nothing y = Just y
      mf (Just x) y = Just (f x y)


instance MonoFoldable1 (NE.NonEmpty a)
-- normally we favor defaulting, should we be using it here?
instance (MonoFoldable mono, IsSequence mono) => MonoFoldable1 (NotEmpty mono)


class (MonoFoldable1 seq, OrdSequence (Nullable seq)) => OrdNonNull seq where
    -- | like Data.List, but not partial on a NonNull
    maximum :: seq -> Element seq
    default maximum :: (MonoFoldable1 seq) => seq -> Element seq
    maximum = ofoldr1 max

    -- | like Data.List, but not partial on a NonNull
    minimum :: seq -> Element seq
    default minimum :: (MonoFoldable1 seq, Element (Nullable seq) ~ Element seq) => seq -> Element seq
    minimum = ofoldr1 min

    -- | like Data.List, but not partial on a NonNull
    maximumBy :: (Element seq -> Element seq -> Ordering) -> seq -> Element seq
    default maximumBy :: (MonoFoldable1 seq) => (Element seq -> Element seq -> Ordering) -> seq -> Element seq
    maximumBy cmp = ofoldr1 max'
      where max' x y = case cmp x y of
                            GT -> x
                            _  -> y

    -- | like Data.List, but not partial on a NonNull
    minimumBy :: (Element seq -> Element seq -> Ordering) -> seq -> Element seq
    default minimumBy :: (MonoFoldable1 seq) => (Element seq -> Element seq -> Ordering) -> seq -> Element seq
    minimumBy cmp = ofoldr1 min'
      where min' x y = case cmp x y of
                            GT -> y
                            _  -> x

instance Ord a => OrdNonNull (NE.NonEmpty a) where
    maximum = F.maximum
    minimum = F.minimum
    maximumBy = F.maximumBy
    minimumBy = F.minimumBy

instance Ord a => OrdNonNull (NotEmpty (Seq.Seq a))
instance Ord a => OrdNonNull (NotEmpty (V.Vector a))
instance OrdNonNull (NotEmpty (S.ByteString))
instance OrdNonNull (NotEmpty (L.ByteString))
instance OrdNonNull (NotEmpty (T.Text))
instance OrdNonNull (NotEmpty (TL.Text))