module Data.Text.ParagraphLayout.Internal.BiDiReorder (reorder)
where

import Data.List.NonEmpty (NonEmpty ((:|)))
import qualified Data.List.NonEmpty as NonEmpty
import Data.Semigroup (sconcat)

import Data.Text.ParagraphLayout.Internal.BiDiLevels

-- | Generic reordering of bidirectional text according to rule L2 of UAX #9
-- <https://www.unicode.org/reports/tr9/#Reordering_Resolved_Levels>.
--
-- Given an input in logical order and its corresponding BiDi levels,
-- this algorithm produces output in visual order, always from left to right.
--
-- Although defined by UAX #9 for reordering on the glyph level, this can also
-- be used for reordering runs of text, provided that the glyphs within each
-- shaped run are already ordered visually from left to right. This is the case
-- for HarfBuzz output.
reorder :: WithLevel a => NonEmpty a -> NonEmpty a
reorder xs = reorderLevels minOddLevel maxLevel xs
    where
        minOddLevel = minimum oddLevels
        maxLevel = maximum levels
        oddLevels = 1 :| NonEmpty.filter odd levels
        levels = NonEmpty.map level xs

-- | For each integer value from @high@ to @low@ inclusive, reverse any
-- contiguous sequence of items that are at the given level or higher.
--
-- The value of @low@ must be at least 1 to avoid integer overflow.
reorderLevels :: WithLevel a => Level -> Level -> NonEmpty a -> NonEmpty a
reorderLevels low high xs =
    if low > high
        then xs
        else reorderLevels low (high - 1) $ reorderLevel high xs

-- | Reverse any contiguous sequence of items that are at level @lvl@ or higher.
reorderLevel :: WithLevel a => Level -> NonEmpty a -> NonEmpty a
reorderLevel lvl xs = sconcat $ NonEmpty.map reverseHigh $ groupHigh xs
    where
        reverseHigh g@(x :| _) = if isHigh x then NonEmpty.reverse g else g
        groupHigh = NonEmpty.groupWith1 isHigh
        isHigh x = level x >= lvl