lib/mlton/heap/heap.sig

   1 (* Copyright (C) 2009 Matthew Fluet.
   2  * Copyright (C) 1999-2006 Henry Cejtin, Matthew Fluet, Suresh
   3  *    Jagannathan, and Stephen Weeks.
   4  *
   5  * MLton is released under a BSD-style license.
   6  * See the file MLton-LICENSE for details.
   7  *)
   8
   9 signature HEAP_STRUCTS =
  10    sig
  11       structure Key: BOUNDED_ORDER
  12    end
  13
  14 signature HEAP =
  15    sig
  16       include HEAP_STRUCTS
  17
  18       structure Elt:
  19          sig
  20             type 'a t
  21
  22             val key: 'a t -> Key.t
  23             val value: 'a t -> 'a
  24          end
  25
  26       type 'a t
  27
  28       val decreaseKey: 'a t * 'a Elt.t * Key.t -> unit
  29       val delete: 'a t * 'a Elt.t -> unit
  30       val deleteMin: 'a t -> 'a
  31       val empty: unit -> 'a t
  32       val insert: 'a t * Key.t * 'a -> 'a Elt.t
  33       val isEmpty: 'a t -> bool
  34       val min: 'a t -> 'a Elt.t
  35       val new: (Key.t * 'a) list -> 'a t
  36       (* union(h, h') unions h' into h, destroying h'. *)
  37       val union: 'a t * 'a t -> unit
  38    end