/usr/lib/ats2-postiats-0.2.6/libats/ATS1/SATS/funheap_braun.sats is in ats2-lang 0.2.6-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | (***********************************************************************)
(* *)
(* Applied Type System *)
(* *)
(* Hongwei Xi *)
(* *)
(***********************************************************************)
(*
** ATS - Unleashing the Potential of Types!
** Copyright (C) 2002-2011 Hongwei Xi, Boston University
** All rights reserved
**
** ATS is free software; you can redistribute it and/or modify it under
** the terms of the GNU GENERAL PUBLIC LICENSE (GPL) as published by the
** Free Software Foundation; either version 3, or (at your option) any
** later version.
**
** ATS 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. See the GNU General Public License
** for more details.
**
** You should have received a copy of the GNU General Public License
** along with ATS; see the file COPYING. If not, please write to the
** Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
** 02110-1301, USA.
*)
(* ****** ****** *)
(*
**
** A functional heap implementation based on Braun trees
**
** Contributed by Hongwei Xi (hwxi AT cs DOT bu DOT edu)
** Time: April, 2010 // based on a version done in November, 2008
**
*)
(* ****** ****** *)
//
// HX-2011-11-13:
// This style of heap is VERY inefficient! Please use funheap_binomial
// instead, which is about 20 times faster for a heap of the size 1M.
//
(* ****** ****** *)
//
// HX-2014-01-15:
// Porting to ATS2 from ATS1
//
(* ****** ****** *)
//
abstype
heap_t0ype_type (a:t@ype+) = ptr
//
typedef
heap(a:t0p) = heap_t0ype_type (a)
//
(* ****** ****** *)
typedef
cmp (a:t0p) = (a, a) -<cloref> int
(* ****** ****** *)
fun{a:t0p}
compare_elt_elt
(x1: a, x2: a, cmp: cmp a):<> int
// end of [compare_elt_elt]
(* ****** ****** *)
fun{} funheap_make_nil{a:t0p} ():<> heap (a)
(* ****** ****** *)
//
fun{a:t0p}
funheap_size (heap(INV(a))):<> Size
//
(* ****** ****** *)
//
// HX: primarily for statistics
//
fun{a:t0p}
funheap_height (hp: heap(INV(a))):<> intGte(0)
//
(* ****** ****** *)
fun{a:t0p}
funheap_insert
(hp: &heap(INV(a)) >> _, x: a, cmp: cmp a):<!wrt> void
(* ****** ****** *)
fun{a:t@ype}
funheap_getmin (
hp: heap (INV(a)), cmp: cmp a, res: &a? >> opt (a, b)
) :<!wrt> #[b:bool] bool b // end of [funheap_getmin]
fun{a:t0p}
funheap_getmin_opt
(hp: heap(INV(a)), cmp: cmp a):<!wrt> Option_vt (a)
// end of [funheap_getmin_opt]
(* ****** ****** *)
fun{a:t0p}
funheap_delmin (
hp: &heap(INV(a)) >> _, cmp: cmp a, res: &a? >> opt (a, b)
) :<!wrt> #[b:bool] bool b // end of [funheap_delim]
fun{a:t0p}
funheap_delmin_opt
(hp: &heap(INV(a)) >> _, cmp: cmp a):<!wrt> Option_vt (a)
// end of [funheap_delmin_opt]
(* ****** ****** *)
(* end of [funheap_braun.sats] *)
|