(* Remove duplicate elements.

   This implementation is for elements that contain a "this has been
   seen" flag. It is O(n) in the number of elements.

   Also, this implementation demonstrates that imperative programming,
   without dependent types or proofs, is possible in ATS. *)

#include "share/atspre_staload.hats"

(* A tuple in the heap. *)
typedef seen_or_not (a : t@ype+) = '(a, ref bool)

(* How the remove_dups function will be called. *)
extern fn {a : t@ype}
remove_dups
          (given_data          : arrszref (seen_or_not a),
           space_for_result    : arrszref (seen_or_not a),
           num_of_unique_elems : &size_t? >> size_t)
    : void

implement {a}
remove_dups (given_data, space_for_result, num_of_unique_elems) =
  let
    macdef seen (i) = given_data[,(i)].1

    var i : size_t
    var j : size_t
  in
    (* Clear all the "seen" flags. *)
    for (i := i2sz 0; i <> size given_data; i := succ i)
      !(seen i) := false;

    (* Loop through given_data, copying (pointers to) any values that
       have not yet been seen. *)
    j := i2sz 0;
    for (i := i2sz 0; i <> size given_data; i := succ i)
      if !(seen i) then
        ()          (* Skip any element that has already been seen. *)
      else
        begin
          !(seen i) := true;    (* Mark the element as seen. *)
          space_for_result[j] := given_data[i];
          j := succ j
        end;

    num_of_unique_elems := j
  end

implement                       (* A demonstration. *)
main0 () =
  let
    (* Define some values. *)
    val a = '("a", ref<bool> false)
    val b = '("b", ref<bool> false)
    val c = '("c", ref<bool> false)
    val d = '("d", ref<bool> false)
    val e = '("e", ref<bool> false)

    (* Fill an array with values. *)
    val data =
      arrszref_make_list ($list (a, c, b, e, a, a, d, d, b, c))

    (* Allocate storage for the result. *)
    val unique_elems = arrszref_make_elt (i2sz 10, a)
    var num_of_unique_elems : size_t

    var i : size_t
  in
    (* Remove duplicates. *)
    remove_dups<string> (data, unique_elems, num_of_unique_elems);

    (* Print the results. *)
    for (i := i2sz 0; i <> num_of_unique_elems; i := succ i)
      print! (" ", unique_elems[i].0);
    println! ()
  end