-- This program genereates all computation steps that the
-- imperative algorithm InserSort would take while sorting a list.
-- The output might be further used for vizualizations of the
-- alorithm behavior.

-- Example usage:
-- insertSortSteps [3,2,1]

-- Result:
-- [Step {i = 0, j = 1, xs = [3,2,1]},
--  Step {i = 1, j = 2, xs = [3,1,2]},
--  Step {i = 1, j = 1, xs = [1,3,2]}]


-- The List that will be sorted.
type Input a = [a]

-- A list of this type will be the result
data ComputationStep a =
  Step { i :: Int
       , j :: Int
       , xs :: [a]
       }
  deriving Show


-- Generates a list of all comutation steps the InsertSort
-- algorithm takes to sort a list.
insertSortSteps :: Ord a => Input a -> [ComputationStep a]
insertSortSteps xs =
  scanl f (Step i j xs) ijs
    where
      n = length xs
      (i, j):ijs = [(i, j) | i <- [0..n-2], j <- [i+1,i..1]]
      f (Step _ _ xs) (i, j) =
        Step i j (updateXs xs i j)


-- Computes new xs based on an i and a j.
updateXs :: Ord a => [a] -> Int -> Int -> [a]
updateXs xs i j =
  if (xs !! j) < (xs !! pred j)
    then swap xs j (pred j)
    else xs


-- Swaps two elements in a list based on the given indices.
swap :: [a] -> Int -> Int -> [a]
swap xs i1 i2 =
  zipWith f xs [0..]
  where
    f x i
      | i == i1 = xs !! i2
      | i == i2 = xs !! i1
      | otherwise = x


-- reminder InsertSort works like this in imperative languages, e.g. in JavaScript:

-- function insertSort (input)
-- {
--   const n = input.length;
--   for (var i = 0; i < n-1 ; i++)
--   {
--     for (var j = i + 1; j >= 1; j--)
--     {
--       if (input[j] < input[j - 1])
-- 	 {
--         swap(input, j, j - 1);
-- 	 }
--     }
--   }
-- }