# 94bffb999d83c4782d92813655e000b121c585c9683eb2a51b68608245074604 Elan 2.0.0-alpha4 valid

# Implementation of the Merge sort algorithm demonstrating
# - Decomposition of the principal function 'sort' into smaller functions,
# - Recursive functions. Note that both 'sort' and 'merge' are indirectly 
#   recursive, because they delegate to other functions that invoke the function
#   they are invoked from
# - Testing. ALL functions are independently unit-tested, with normal ('happy') 
#   cases, and edge cases (where appropriate)
function sort(li as List<of String>) returns List<of String>
  return if(li.length() < 2, li, merge(sortedFrontHalf(li), sortedBackHalf(li)))
end function

function sortedFrontHalf(li as List<of String>) returns List<of String>
  let mid be divAsInt(li.length(), 2)
  let frontHalf be li.subList(0, mid)
  return sort(frontHalf)
end function

function sortedBackHalf(li as List<of String>) returns List<of String>
  let mid be divAsInt(li.length(), 2)
  let backHalf be li.subList(mid, li.length())
  return sort(backHalf)
end function

function merge(a as List<of String>, b as List<of String>) returns List<of String>
  let oneIsEmpty be (a.length() is 0) or (b.length() is 0)
  return if(oneIsEmpty, a.withAppendList(b), mergeNonEmpty(a, b))
end function

function mergeNonEmpty(a as List<of String>, b as List<of String>) returns List<of String>
  let aHead be a.head()
  let bHead be b.head()
  let aTail be a.tail()
  let bTail be b.tail()
  return if(aHead.isBefore(bHead), [aHead].withAppendList(merge(aTail, b)), [bHead].withAppendList(merge(a, bTail)))
end function

test test_sort
  # Edge case: empty
  let l1 be new List<of String>()
  assert sort(l1) is l1
  # Edge case: one item
  let li2 be ["plum"]
  assert sort(li2) is li2
  # Happy case: odd number of members
  let li3 be ["plum", "apricot", "lime", "lemon", "melon", "apple", "orange", "strawberry", "pear"]
  let sorted3 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "pear", "plum", "strawberry"]
  assert sort(li3) is sorted3
  # Happy case: even number of members
  let li4 be ["plum", "apricot", "lime", "lemon", "melon", "apple", "orange", "strawberry"]
  let sorted4 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "plum", "strawberry"]
  assert sort(li4) is sorted4
  # Edge case: already sorted
  let li5 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "pear", "strawberry"]
  assert sort(li5) is li5
end test

test test_sortedFrontHalf
  # Edge case: one item - so front half is empty
  let li1 be ["plum"]
  assert sortedFrontHalf(li1) is new List<of String>()
  # Happy case: odd number of members
  let li2 be ["plum", "apricot", "lime", "lemon", "melon", "apple", "orange", "strawberry", "pear"]
  assert sortedFrontHalf(li2) is ["apricot", "lemon", "lime", "plum"]
  # Happy case: even number of members
  let li3 be ["plum", "apricot", "lemon", "melon", "apple", "orange", "strawberry", "pear"]
  assert sortedFrontHalf(li3) is ["apricot", "lemon", "melon", "plum"]
  # Edge case: already sorted
  let li4 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "pear"]
  assert sortedFrontHalf(li4) is ["apple", "apricot", "lemon"]
end test

test test_sortedBackHalf
  # Edge case: one item - so back half is whole list
  let li1 be ["plum"]
  assert sortedBackHalf(li1) is ["plum"]
  # Happy case: odd number of members
  let li2 be ["plum", "apricot", "lime", "lemon", "melon", "apple", "orange", "strawberry", "pear"]
  assert sortedBackHalf(li2) is ["apple", "melon", "orange", "pear", "strawberry"]
  # Happy case: even number of members
  let li3 be ["plum", "apricot", "lemon", "melon", "apple", "orange", "strawberry", "pear"]
  assert sortedBackHalf(li3) is ["apple", "orange", "pear", "strawberry"]
  # Edge case: already sorted
  let li4 be ["apple", "apricot", "lemon", "lime", "melon", "orange", "pear"]
  assert sortedBackHalf(li4) is ["lime", "melon", "orange", "pear"]
end test

test test_merge
  # Happy cases:
  let l1 be ["apple", "lime", "pear"]
  let l2 be ["apricot", "lemon", "plum", "watermelon"]
  assert merge(["orange"], ["melon"]) is ["melon", "orange"]
  assert merge(l1, l2) is ["apple", "apricot", "lemon", "lime", "pear", "plum", "watermelon"]
  assert merge(l2, l1) is ["apple", "apricot", "lemon", "lime", "pear", "plum", "watermelon"]
  # Edge cases - empty list(s)
  let le be new List<of String>()
  assert merge(le, le) is le
  assert merge(l1, le) is l1
  assert merge(le, l2) is l2
  # Edge case - duplication
  assert merge(l1, l1) is ["apple", "apple", "lime", "lime", "pear", "pear"]
  # Error case lists not sorted will not produce correct result
  let lu be ["lime", "pear", "apple"]
  assert merge(lu, l2) is ["apricot", "lemon", "lime", "pear", "apple", "plum", "watermelon"]
  assert merge(lu, le) is ["lime", "pear", "apple"]
end test

test test_mergeNonEmpty
  let l1 be ["apple", "lime", "pear"]
  let l2 be ["apricot", "lemon", "plum", "watermelon"]
  assert mergeNonEmpty(["orange"], ["melon"]) is ["melon", "orange"]
  assert mergeNonEmpty(l1, l2) is ["apple", "apricot", "lemon", "lime", "pear", "plum", "watermelon"]
  assert mergeNonEmpty(l2, l1) is ["apple", "apricot", "lemon", "lime", "pear", "plum", "watermelon"]
  assert mergeNonEmpty(l1, l1) is ["apple", "apple", "lime", "lime", "pear", "pear"]
  #  Edge case: duplication
  assert mergeNonEmpty(l1, l1) is ["apple", "apple", "lime", "lime", "pear", "pear"]
  # Edge cases: single elements
  assert mergeNonEmpty(l1, ["lemon"]) is ["apple", "lemon", "lime", "pear"]
  assert mergeNonEmpty(["melon"], l1) is ["apple", "lime", "melon", "pear"]
  # Error case - pass empty list
  assert mergeNonEmpty(new List<of String>(), l1) is "Out of range index: 0 size: 0"
  #  Error case unsorted list
  let lu be ["lime", "pear", "apple"]
  assert merge(lu, l2) is ["apricot", "lemon", "lime", "pear", "apple", "plum", "watermelon"]
end test
