Ignore:
Timestamp:
Feb 27, 2013, 2:03:12 PM (7 years ago)
Author:
sacerdot
Message:

Porting the graph colouring stuff from the untrusted prototype to the extracted
code.

Location:
extracted/untrusted
Files:
1 added
1 moved

Legend:

Unmodified
Added
Removed
  • extracted/untrusted/pset.ml

    r2735 r2738  
    22
    33    type 'a set = Empty | Node of 'a set * 'a * 'a set * int
     4
     5    let empty = Empty
     6
     7    let is_empty = function Empty -> true | Node _ -> false
    48
    59    let height = function
     
    4953         if c < 0 then bal (add x l) v r else bal l v (add x r)
    5054
     55    let singleton elt = add elt Empty
     56
    5157    let rec min_elt = function
    5258        Empty -> raise Not_found
     
    6470      | (t, Empty) -> t
    6571      | (_, _) -> bal t1 (min_elt t2) (remove_min_elt t2)
     72
     73    let rec remove x = function
     74        Empty -> Empty
     75      | Node(l, v, r, _) ->
     76          let c = compare x v in
     77          if c = 0 then merge l r else
     78          if c < 0 then bal (remove x l) v r else bal l v (remove x r)
     79
     80    let rec fold f s accu =
     81      match s with
     82        Empty -> accu
     83      | Node(l, v, r, _) -> fold f r (f v (fold f l accu))
     84
     85    let rec iter f = function
     86        Empty -> ()
     87      | Node(l, v, r, _) -> iter f l; f v; iter f r
     88
     89    let rec cardinal = function
     90        Empty -> 0
     91      | Node(l, v, r, _) -> cardinal l + 1 + cardinal r
    6692
    6793    let rec join l v r =
     
    170196    let equal s1 s2 =
    171197      compare s1 s2 = 0
    172 
    173     let matitabool_of_bool b = if b then Bool.True else Bool.False
    174 
    175 (** val set_empty : 'a1 set0 **)
    176 let set_empty = Empty
    177 
    178 (** val set_member :
    179     ('a1 -> 'a1 -> Bool.bool) -> 'a1 -> 'a1 set0 -> Bool.bool **)
    180 let set_member _ x s = matitabool_of_bool (mem x s)
    181 
    182 (** val set_equal :
    183     ('a1 -> 'a1 -> Bool.bool) -> 'a1 set0 -> 'a1 set0 -> Bool.bool **)
    184 let set_equal _ s1 s2 = matitabool_of_bool (equal s1 s2)
    185 
    186 (** val set_diff : 'a1 set0 -> 'a1 set0 -> 'a1 set0 **)
    187 let set_diff = diff
    188 
    189 (** val set_singleton : 'a1 -> 'a1 set0 **)
    190 let set_singleton elt =
    191   add elt set_empty
    192 
    193 (** val set_from_list : 'a1 List.list -> 'a1 set0 **)
    194 let set_from_list the_list =
    195   List.foldr add set_empty the_list
    196 
    197 (** val set_subset :
    198     ('a1 -> 'a1 -> Bool.bool) -> 'a1 set0 -> 'a1 set0 -> Bool.bool **)
    199 let set_subset _ s1 s2 = matitabool_of_bool (subset s1 s2)
    200 
    201 (** val set_union : 'a1 set0 -> 'a1 set0 -> 'a1 set0 **)
    202 let set_union = union
Note: See TracChangeset for help on using the changeset viewer.