78 lines
2.2 KiB
Plaintext
78 lines
2.2 KiB
Plaintext
(* 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
|