! Copyright (C) 2007, 2008 Ryan Murphy, Doug Coleman,
! Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays assocs combinators fry kernel
-kernel.private locals math math.order math.private sequences
-sequences.private summary vectors ;
+USING: accessors arrays assocs fry kernel kernel.private
+math math.order math.private sequences sequences.private summary
+vectors ;
IN: heaps
GENERIC: heap-push* ( value key heap -- entry )
: <max-heap> ( -- max-heap ) max-heap <heap> ;
-M: heap heap-empty? ( heap -- ? )
- data>> empty? ; inline
+M: heap heap-empty? data>> empty? ; inline
-M: heap heap-size ( heap -- n )
- data>> length ; inline
+M: heap heap-size data>> length ; inline
<PRIVATE
: >entry< ( entry -- value key )
[ value>> ] [ key>> ] bi ; inline
-M: heap heap-peek ( heap -- value key )
+M: heap heap-peek
data>> first >entry< ;
<PRIVATE
! A quote from cpython's implementation:
! > We *could* break out of the loop as soon as we find a pos where newitem <=
! > both its children, but turns out that's not a good idea [...]
-! Indeed the code is 33% slower if we remove this optmization.
+! Indeed the code is 33% slower if we remove this optimization.
:: sift-up ( heap n -- )
heap data>> :> data
data length :> end