src/Pure/General/set.ML
changeset 77875 9374e13655e8
parent 77836 9d124714a9e8
child 77881 560bdb9f2101
equal deleted inserted replaced
77874:c274f52b11ff 77875:9374e13655e8
    22   val forall: (elem -> bool) -> T -> bool
    22   val forall: (elem -> bool) -> T -> bool
    23   val get_first: (elem -> 'a option) -> T -> 'a option
    23   val get_first: (elem -> 'a option) -> T -> 'a option
    24   val member: T -> elem -> bool
    24   val member: T -> elem -> bool
    25   val subset: T * T -> bool
    25   val subset: T * T -> bool
    26   val eq_set: T * T -> bool
    26   val eq_set: T * T -> bool
    27   val ord: T ord
       
    28   val insert: elem -> T -> T
    27   val insert: elem -> T -> T
    29   val make: elem list -> T
    28   val make: elem list -> T
    30   val merge: T * T -> T
    29   val merge: T * T -> T
    31   val merges: T list -> T
    30   val merges: T list -> T
    32   val remove: elem -> T -> T
    31   val remove: elem -> T -> T
   236           | some => some)
   235           | some => some)
   237       | get (Size (_, arg)) = get arg;
   236       | get (Size (_, arg)) = get arg;
   238   in get end;
   237   in get end;
   239 
   238 
   240 
   239 
   241 (* member *)
   240 (* member and subset *)
   242 
   241 
   243 fun member set elem =
   242 fun member set elem =
   244   let
   243   let
   245     fun elem_ord e = Key.ord (elem, e)
   244     fun elem_ord e = Key.ord (elem, e)
   246     val elem_eq = is_equal o elem_ord;
   245     val elem_eq = is_equal o elem_ord;
   272               | EQUAL => true
   271               | EQUAL => true
   273               | GREATER => mem right))
   272               | GREATER => mem right))
   274       | mem (Size (_, arg)) = mem arg;
   273       | mem (Size (_, arg)) = mem arg;
   275   in mem set end;
   274   in mem set end;
   276 
   275 
   277 
       
   278 (* subset and order *)
       
   279 
       
   280 fun subset (set1, set2) = forall (member set2) set1;
   276 fun subset (set1, set2) = forall (member set2) set1;
   281 
   277 
   282 fun eq_set (set1, set2) =
   278 fun eq_set (set1, set2) =
   283   pointer_eq (set1, set2) orelse size set1 = size set2 andalso subset (set1, set2);
   279   pointer_eq (set1, set2) orelse size set1 = size set2 andalso subset (set1, set2);
   284 
       
   285 val ord =
       
   286   pointer_eq_ord (fn sets =>
       
   287     (case int_ord (apply2 size sets) of
       
   288       EQUAL =>
       
   289         if subset sets then EQUAL
       
   290         else dict_ord Key.ord (apply2 dest sets)
       
   291     | ord => ord));
       
   292 
   280 
   293 
   281 
   294 (* insert *)
   282 (* insert *)
   295 
   283 
   296 datatype growth = Stay of T | Sprout of T * elem * T;
   284 datatype growth = Stay of T | Sprout of T * elem * T;