(**************************************************************************)
(*                                                                        *)
    : a generic graph library for OCaml                         
   Copyright ( C ) 2004 - 2010                                               
     ,     and   
(*                                                                        *)
(*  This software is free software; you can redistribute it and/or        *)
   modify it under the terms of the GNU Library General Public           
   License version 2.1 , with the special exception on linking            
(*  described in file LICENSE.                                            *)
(*                                                                        *)
(*  This software is distributed in the hope that it will be useful,      *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
(*                                                                        *)
(**************************************************************************)


module type Ordered = sig
  type t
  val compare : t -> t -> int
end

exception EmptyHeap

S Imperative implementation .

module Imperative(X: Ordered) : sig

  (* Type of imperative heaps.
     (In the following [n] refers to the number of elements in the heap) *)

  type t 

  (* [create c] creates a new heap, with initial capacity of [c] *)
  val create : int -> t

  (* [is_empty h] checks the emptiness of [h] *)
  val is_empty : t -> bool

  (* [add x h] adds a new element [x] in heap [h]; size of [h] is doubled
     when maximum capacity is reached; complexity $O(log(n))$ *)
  val add : t -> X.t -> unit

  (* [maximum h] returns the maximum element of [h]; raises [EmptyHeap]
     when [h] is empty; complexity $O(1)$ *)
  val maximum : t -> X.t

  (* [remove h] removes the maximum element of [h]; raises [EmptyHeap]
     when [h] is empty; complexity $O(log(n))$ *)
  val remove : t -> unit

  (* [pop_maximum h] removes the maximum element of [h] and returns it;
     raises [EmptyHeap] when [h] is empty; complexity $O(log(n))$ *)
  val pop_maximum : t -> X.t

  (* usual iterators and combinators; elements are presented in
     arbitrary order *)
  val iter : (X.t -> unit) -> t -> unit

  val fold : (X.t -> 'a -> 'a) -> t -> 'a -> 'a

end

(*S Functional implementation. *)

module type FunctionalSig = sig

  (* heap elements *)
  type elt

  (* Type of functional heaps *)
  type t

  (* The empty heap *)
  val empty : t

  (* [add x h] returns a new heap containing the elements of [h], plus [x];
     complexity $O(log(n))$ *)
  val add : elt -> t -> t

  (* [maximum h] returns the maximum element of [h]; raises [EmptyHeap]
     when [h] is empty; complexity $O(1)$ *)
  val maximum : t -> elt

  (* [remove h] returns a new heap containing the elements of [h], except
     the maximum of [h]; raises [EmptyHeap] when [h] is empty; 
     complexity $O(log(n))$ *) 
  val remove : t -> t

  (* usual iterators and combinators; elements are presented in
     arbitrary order *)
  val iter : (elt -> unit) -> t -> unit

  val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a

end

module Functional(X: Ordered) : FunctionalSig with type elt = X.t

************************************************************************
                                                                        
                                                                        
  This software is free software; you can redistribute it and/or        
  described in file LICENSE.                                            
                                                                        
  This software is distributed in the hope that it will be useful,      
  but WITHOUT ANY WARRANTY; without even the implied warranty of        
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  
                                                                        
************************************************************************
 Type of imperative heaps.
     (In the following [n] refers to the number of elements in the heap) 
 [create c] creates a new heap, with initial capacity of [c] 
 [is_empty h] checks the emptiness of [h] 
 [add x h] adds a new element [x] in heap [h]; size of [h] is doubled
     when maximum capacity is reached; complexity $O(log(n))$ 
 [maximum h] returns the maximum element of [h]; raises [EmptyHeap]
     when [h] is empty; complexity $O(1)$ 
 [remove h] removes the maximum element of [h]; raises [EmptyHeap]
     when [h] is empty; complexity $O(log(n))$ 
 [pop_maximum h] removes the maximum element of [h] and returns it;
     raises [EmptyHeap] when [h] is empty; complexity $O(log(n))$ 
 usual iterators and combinators; elements are presented in
     arbitrary order 
S Functional implementation. 
 heap elements 
 Type of functional heaps 
 The empty heap 
 [add x h] returns a new heap containing the elements of [h], plus [x];
     complexity $O(log(n))$ 
 [maximum h] returns the maximum element of [h]; raises [EmptyHeap]
     when [h] is empty; complexity $O(1)$ 
 [remove h] returns a new heap containing the elements of [h], except
     the maximum of [h]; raises [EmptyHeap] when [h] is empty; 
     complexity $O(log(n))$ 
 usual iterators and combinators; elements are presented in
     arbitrary order 
    : a generic graph library for OCaml                         
   Copyright ( C ) 2004 - 2010                                               
     ,     and   
   modify it under the terms of the GNU Library General Public           
   License version 2.1 , with the special exception on linking            


module type Ordered = sig
  type t
  val compare : t -> t -> int
end

exception EmptyHeap

S Imperative implementation .

module Imperative(X: Ordered) : sig


  type t 

  val create : int -> t

  val is_empty : t -> bool

  val add : t -> X.t -> unit

  val maximum : t -> X.t

  val remove : t -> unit

  val pop_maximum : t -> X.t

  val iter : (X.t -> unit) -> t -> unit

  val fold : (X.t -> 'a -> 'a) -> t -> 'a -> 'a

end


module type FunctionalSig = sig

  type elt

  type t

  val empty : t

  val add : elt -> t -> t

  val maximum : t -> elt

  val remove : t -> t

  val iter : (elt -> unit) -> t -> unit

  val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a

end

module Functional(X: Ordered) : FunctionalSig with type elt = X.t
