/* library for manipulations on lists - by Marc BARILLEY*/

fun listcat (p, q)=
  if p==nil
  then
    q
  else let p -> [h nxt] in
    h::listcat nxt q;;

fun listlength (l)=
  if l==nil
  then 0
  else
    let l->[_ n] in
    1 + listlength n;;

fun dividelist (cmpfun, x, l, a1, a2) =
  if l==nil
  then [a1 a2]
  else let l -> [h nxt] in
    if (exec cmpfun with [x h]) < 0 /*x<h*/
    then dividelist cmpfun x nxt [h a1] a2
    else dividelist cmpfun x nxt a1 [h a2];;

fun quicksort (cmpfun, list)=
  if list==nil
  then
    nil
  else
    let list->[h nxt] in
    let dividelist cmpfun h nxt nil nil -> [l1 l2] in
    listcat quicksort cmpfun l1 h::quicksort cmpfun l2;;

fun mirror (list)=
  if list==nil
  then nil
  else
    let list -> [first next] in
    listcat mirror next first::nil;;

fun remove_nth_from_list (list, n)=
  if n < 0
  then
    list
  else
    let list -> [first next] in
      if n==0
      then
        next
      else
        first::remove_nth_from_list next n-1;;

fun removef_from_list(l, f, x)=
 if l==nil then nil
 else
  let l -> [a next] in
    if exec f with [a x]
    then
      next
    else
      a::removef_from_list next f x;;

fun replace_nth_in_list (list, n, x)=
  if n < 0
  then
    list
  else
    let list -> [first next] in
      if n==0
      then
        x::next
      else
        first::replace_nth_in_list next n-1 x;;

fun replace_in_list (list, old, new)=
  if list==nil
  then
    nil
  else
    let list -> [first next] in
      if first==old
      then
        new::next
      else
        first::replace_in_list next old new;;

fun add_nth_in_list (list, n, x)=
  if n < 0
  then
    listcat list x::nil
  else
    let list -> [first next] in
      if n==0
      then
        x::list
      else
        first::add_nth_in_list next n-1 x;;

fun is_in_list (l, x)=
  if l==nil
  then
    0
  else
    let l->[a nxt] in
      (a==x)||is_in_list nxt x;;

fun isf_in_list (l, f, x)=
  if l==nil
  then
    0
  else
    let l->[a nxt] in
      (exec f with [a x])||isf_in_list nxt f x;;

fun posf_in_list (l, f, x)=
  if l==nil
  then
    nil
  else
    if exec f with [hd l x]
    then
      0
    else
      1+posf_in_list tl l f x;;

fun search_all_in_list (l, f, x)=
  if l==nil
  then
    nil
  else
    let l -> [a nxt] in
      if exec f with [a x]
      then
        a::search_all_in_list nxt f x
      else
        search_all_in_list nxt f x;;