1 ! Copyright (C) 2008, 2009 Slava Pestov.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: kernel sequences sequences.private accessors math
4 math.order combinators hints arrays ;
9 : midpoint ( seq -- elt )
10 [ midpoint@ ] keep nth-unsafe ; inline
12 : decide ( quot seq -- quot seq <=> )
13 [ midpoint swap call ] 2keep rot ; inline
15 : finish ( quot slice -- i elt )
16 [ [ from>> ] [ midpoint@ ] bi + ] [ seq>> ] bi
17 [ drop ] [ dup ] [ ] tri* nth ; inline
21 : keep-searching ( seq quot -- slice )
22 [ dup midpoint@ ] dip call collapse-slice slice boa (search) ; inline
24 : (search) ( quot: ( elt -- <=> ) seq -- i elt )
30 { +lt+ [ [ (head) ] keep-searching ] }
31 { +gt+ [ [ (tail) ] keep-searching ] }
33 ] if ; inline recursive
37 : search ( seq quot -- i elt )
38 over empty? [ 2drop f f ] [ swap <flat-slice> (search) ] if ;
41 : natural-search ( obj seq -- i elt )
44 HINTS: natural-search array ;
46 : sorted-index ( obj seq -- i )
49 : sorted-member? ( obj seq -- ? )
50 dupd natural-search nip = ;
52 : sorted-member-eq? ( obj seq -- ? )
53 dupd natural-search nip eq? ;