## list-set-g.pkg
# Compiled by:
# src/lib/std/standard.lib# An implementation of finite sets of ordered values
# which uses a sorted list representation. Normally
# src/lib/src/red-black-set-g.pkg# is preferred.
### "Lisp has jokingly been called "the most
### intelligent way to misuse a computer".
### I think that description is a great
### compliment because it transmits the
### full flavor of liberation: it has assisted
### a number of our most gifted fellow humans
### in thinking previously impossible thoughts."
###
### -- Edsger Dijkstra, CACM, 15:10
generic package list_set_g (k: Key) # Key is from src/lib/src/key.api:
Set # Set is from src/lib/src/set.apiwhere
key::Key == k::Key
=
package {
package key = k;
# Sets are represented as
# ordered lists of key values:
#
Item = key::Key;
Set = List( Item );
empty = [];
fun all_invariants_hold set = TRUE; # Placeholder.
fun singleton x = [x];
fun add (l, item)
=
f l
where
fun f []
=>
[item];
f (element ! r)
=>
case (key::compare (item, element))
LESS => item ! element ! r;
EQUAL => item ! r;
GREATER => element ! (f r);
esac;
end;
end;
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)
=
{
items' = list::fold_forward (\\ (x, set) => add (set, x); end ) [] items;
union (l, items');
};
fun from_list l
=
add_list (empty, l);
stipulate
# Remove an item, returning new map and value removed.
# Raise LibBase::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 (key::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 (key::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 ! r1, y ! r2) => (key::compare (x, y) == EQUAL) 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); end ) [] s1;
fold_backward = list::fold_backward;
fold_forward = list::fold_forward;
filter = list::filter;
partition = list::partition;
exists = list::exists;
find = list::find;
}; # generic package list_set_g
## COPYRIGHT (c) 1996 by AT&T Research. See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.