1 ! Copyright (C) 2008, 2010 Slava Pestov.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: accessors arrays combinators hints kernel locals math
4 math.order sequences sequences.private ;
9 :: (search) ( seq from to quot: ( elt -- <=> ) -- i elt )
10 from to + 2/ :> midpoint@
11 midpoint@ seq nth-unsafe :> midpoint
17 { +eq+ [ midpoint@ midpoint ] }
18 { +lt+ [ seq from midpoint@ quot (search) ] }
19 { +gt+ [ seq midpoint@ to quot (search) ] }
21 ] if ; inline recursive
25 : search ( seq quot: ( elt -- <=> ) -- i elt )
26 over empty? [ 2drop f f ] [ [ 0 over length ] dip (search) ] if ;
29 : natural-search ( obj seq -- i elt )
32 HINTS: natural-search array ;
34 : sorted-index ( obj seq -- i )
37 : sorted-member? ( obj seq -- ? )
38 dupd natural-search nip = ;
40 : sorted-member-eq? ( obj seq -- ? )
41 dupd natural-search nip eq? ;