1 ! Copyright (C) 2008 Marc Fauconneau.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: accessors binary-search fry kernel math math.order parser
4 sequences sets sorting ;
9 : suffixes ( string -- suffixes-seq )
10 dup length iota [ tail-slice ] with map ;
12 : prefix<=> ( begin seq -- <=> )
13 [ <=> ] [ swap head? ] 2bi [ drop +eq+ ] when ;
15 : find-index ( begin suffix-array -- index/f )
16 [ prefix<=> ] with search drop ;
18 : query-from ( index begin suffix-array -- from )
19 swap '[ _ head? not ] find-last-from drop [ 1 + ] [ 0 ] if* ;
21 : query-to ( index begin suffix-array -- to )
22 [ swap '[ _ head? not ] find-from drop ] [ length or ] bi ;
24 : query-range ( index begin suffix-array -- from to )
25 [ query-from ] [ query-to ] 3bi [ min ] keep ;
27 : (query) ( index begin suffix-array -- matches )
28 [ query-range ] keep <slice> [ seq>> ] map members ;
32 : >suffix-array ( seq -- suffix-array )
33 members [ suffixes ] map concat natural-sort ;
35 SYNTAX: SA{ \ } [ >suffix-array ] parse-literal ;
37 : query ( begin suffix-array -- matches )
38 [ find-index ] 2keep '[ _ _ (query) ] [ { } ] if* ;