## int-list-set.pkg
# Compiled by:
# src/lib/std/standard.lib# An implementation of finite sets of integers which
# uses a sorted list representation. Normally
# src/lib/src/int-red-black-set.pkg# is preferred.
### "Solitary trees, if they grow at all, grow strong."
###
### -- Winston Churchill
package int_list_set : Set # Set is from src/lib/src/set.apiwhere
key::Key == int::Int
=
package {
package key {
Key = Int;
compare = int::compare;
};
# Sets are represented as
# ordered lists of integers:
#
Item = key::Key;
Set = List( Item );
empty = [];
fun all_invariants_hold set = TRUE; # Placeholder.
fun singleton x = [x];
fun add (l, item)
=
{ fun f [] => [item];
f (element ! r)
=>
case (key::compare (item, element))
LESS => item ! element ! r;
EQUAL => item ! r;
GREATER => element ! (f r);
esac;
end;
f l;
};
fun add' (s, x)
=
add (x, s);
fun union (s1, s2)
=
merge (s1, s2)
where
fun merge ([], l2) => l2;
merge (l1, []) => l1;
merge (x ! r1, y ! r2)
=>
case (key::compare (x, y))
LESS => x ! merge (r1, y ! r2);
EQUAL => x ! merge (r1, r2);
GREATER => y ! merge (x ! r1, r2);
esac;
end;
end;
fun intersection (s1, s2)
=
merge (s1, s2)
where
fun merge ([], l2) => [];
merge (l1, []) => [];
merge (x ! r1, y ! r2)
=>
case (key::compare (x, y))
LESS => merge (r1, y ! r2);
EQUAL => x ! merge (r1, r2);
GREATER => merge (x ! r1, r2);
esac;
end;
end;
fun difference (s1, s2)
=
merge (s1, s2)
where
fun merge ([], l2) => [];
merge (l1, []) => l1;
merge (x ! r1, y ! r2)
=>
case (key::compare (x, y))
LESS => x ! merge (r1, y ! r2);
EQUAL => merge (r1, r2);
GREATER => merge (x ! r1, r2);
esac;
end;
end;
fun add_list (l, items)
=
union (l, items')
where
items' = list::fold_forward (\\ (x, set) = add (set, x)) [] items;
end;
fun from_list l
=
add_list (empty, l);
stipulate
# Remove an item, returning new map and value removed.
# Raise lib_base::NOT_FOUND if not found.
#
fun drop' (l, element)
=
f ([], l)
where
fun f (_, [])
=>
raise exception lib_base::NOT_FOUND;
f (prefix, element' ! r)
=>
case (key::compare (element, element'))
#
LESS => raise exception lib_base::NOT_FOUND;
EQUAL => list::reverse_and_prepend (prefix, r);
GREATER => f (element' ! prefix, r);
esac;
end;
end;
herein
fun drop (l, element)
=
drop' (l, element)
except
lib_base::NOT_FOUND = l;
end;
fun member (l, item)
=
f l
where
fun f [] => FALSE;
#
f (element ! r)
=>
case (key::compare (item, element))
#
LESS => FALSE;
EQUAL => TRUE;
GREATER => f r;
esac;
end;
end;
fun preceding_member (l, key)
=
f (l, NULL)
where
fun f (key' ! r, result)
=>
case (int::compare (key, key'))
#
LESS => result;
EQUAL => result;
GREATER => f (r, THE key');
esac;
f ([], result) => result;
end;
end;
fun following_member (l, key)
=
f l
where
fun f (key' ! r)
=>
case (int::compare (key, key'))
#
LESS => THE key';
EQUAL => f r;
GREATER => f r;
esac;
f [] => NULL;
end;
end;
fun is_empty [] => TRUE;
is_empty _ => FALSE;
end;
fun equal (s1, s2)
=
f (s1, s2)
where
fun f ([], []) => TRUE;
f ((x: Int) ! r1, y ! r2) => x == y and f (r1, r2);
f _ => FALSE;
end;
end;
fun compare ([], []) => EQUAL;
compare ([], _) => LESS;
compare (_, []) => GREATER;
compare (x1 ! r1, x2 ! r2)
=>
case (key::compare (x1, x2))
#
EQUAL => compare (r1, r2);
order => order;
esac;
end;
# Return TRUE if and only if
# the first set is a subset
# of the second
#
fun is_subset (s1, s2)
=
f (s1, s2)
where
fun f ([], _) => TRUE;
f (_, []) => FALSE;
f (x ! r1, y ! r2)
=>
case (key::compare (x, y))
#
LESS => FALSE;
EQUAL => f (r1, r2);
GREATER => f (x ! r1, r2);
esac;
end;
end;
# Return the number of items in the set
#
fun vals_count l
=
list::length l;
# Return a list of the items in the set
#
fun vals_list l
=
l;
apply = list::apply;
fun map f s1
=
list::fold_forward (\\ (x, s) = add (s, f x)) [] s1;
fold_backward = list::fold_backward;
fold_forward = list::fold_forward;
filter = list::filter;
partition = list::partition;
exists = list::exists;
find = list::find;
}; # int_list_map