--------------------------------------------------------------------------------
-- |
-- Module      :  Data.List.Zipper
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--------------------------------------------------------------------------------
module Data.List.Zipper where

import qualified Data.List as List

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

-- | Simple Zipper for Lists.
data Zipper a = Zipper [a] [a] deriving (Show,Eq,Functor)

instance Foldable Zipper where
  -- Folds like it it is a normal list
  foldMap f (Zipper ls rs) = foldMap f (reverse ls) <> foldMap f rs


-- | Construct a Zipper from a list
--
-- running time: \(O(1)\)
fromList :: [a] -> Zipper a
fromList = Zipper []

-- | Go to the Next Element
--
-- running time: \(O(1)\)
goNext                :: Zipper a -> Maybe (Zipper a)
goNext (Zipper xs ys) = case ys of
                          []    -> Nothing
                          x:ys' -> Just $ Zipper (x:xs) ys'

-- | Go to the previous Element
--
-- running time: \(O(1)\)
goPrev                :: Zipper a -> Maybe (Zipper a)
goPrev (Zipper xs ys) = case xs of
                          []    -> Nothing
                          x:xs' -> Just $ Zipper xs' (x:ys)

-- | Computes all nexts, even one that has no elements initially or at
-- the end.
--
-- >>> mapM_ print $ allNexts $ fromList [1..5]
-- Zipper [] [1,2,3,4,5]
-- Zipper [1] [2,3,4,5]
-- Zipper [2,1] [3,4,5]
-- Zipper [3,2,1] [4,5]
-- Zipper [4,3,2,1] [5]
-- Zipper [5,4,3,2,1] []
allNexts :: Zipper a -> [Zipper a]
allNexts = List.unfoldr (fmap (\z -> (z,goNext z))) . Just

-- | Returns the next element, and the zipper without it
extractNext                :: Zipper a -> Maybe (a, Zipper a)
extractNext (Zipper xs ys) = case ys of
                               []      -> Nothing
                               (y:ys') -> Just (y,Zipper xs ys')


-- | Drops the next element in the zipper.
--
-- running time: \(O(1)\)
dropNext :: Zipper a -> Maybe (Zipper a)
dropNext = fmap snd . extractNext

-- | Computes all list that still have next elements.
--
-- >>> mapM_ print $ allNonEmptyNexts $ fromList [1..5]
-- Zipper [] [1,2,3,4,5]
-- Zipper [1] [2,3,4,5]
-- Zipper [2,1] [3,4,5]
-- Zipper [3,2,1] [4,5]
-- Zipper [4,3,2,1] [5]
allNonEmptyNexts :: Zipper a -> [Zipper a]
allNonEmptyNexts = List.unfoldr (\z -> (z,) <$> goNext z)