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