fork download

copy

exception Empty
 
module type ORDERED = sig
    type t
 
    val eq : t -> t -> bool
    val lt : t -> t -> bool
    val leq : t -> t -> bool
end
 
module type HEAP = sig
    module Elem : ORDERED
 
    type heap
 
    val empty : heap
    val is_empty : heap -> bool
 
    val insert : Elem.t -> heap -> heap
    val merge : heap -> heap -> heap
 
    val find_min : heap -> Elem.t
    val delete_min : heap -> heap
end
 
module SplayHeap (Element : ORDERED) : (HEAP with module Elem = Element) =
struct
  module Elem = Element
 
  type heap = E | T of heap * Elem.t * heap
 
  let empty = E
  let is_empty = ( = ) E
 
  let rec partition pivot = function
    | T (a, x, b) as t -> 
      if x <= pivot then begin
          match b with
            | E -> (t, E)
            | T (b', y, b'') ->
                if y <= pivot then
                    let (small, big) = partition pivot b''
                    in (T (T (a, x, b), y, small), big)
                else
                    let (small,big) = partition pivot b'
                    in (T (a, x, small), T (big, y, b''))
        end else begin
          match a with
            | E -> (E, t)
            | T (a', y, a'') ->
                if y <= pivot then
                    let (small, big) = partition pivot a''
                    in (T (a', y, small), T (big, x, b))
                else
                    let (small, big) = partition pivot a'
                    in (small, T (big, y, T (a'', x, b)))
        end
    | E -> (E, E)
end

File "prog.ml", line 27, characters 0-1006:
Signature mismatch:
Modules do not match:
  sig
    module Elem :
      sig
        type t = Element.t
        val eq : t -> t -> bool
        val lt : t -> t -> bool
        val leq : t -> t -> bool
      end
    type heap = E | T of heap * Elem.t * heap
    val empty : heap
    val is_empty : heap -> bool
    val partition : Elem.t -> heap -> heap * heap
  end
is not included in
  sig
    module Elem :
      sig
        type t = Element.t
        val eq : t -> t -> bool
        val lt : t -> t -> bool
        val leq : t -> t -> bool
      end
    type heap
    val empty : heap
    val is_empty : heap -> bool
    val insert : Elem.t -> heap -> heap
    val merge : heap -> heap -> heap
    val find_min : heap -> Elem.t
    val delete_min : heap -> heap
  end
The field `delete_min' is required but not provided
The field `find_min' is required but not provided
The field `merge' is required but not provided
The field `insert' is required but not provided

Standard output is empty