Move suffix arrays to basis

diff --git a/basis/suffix-arrays/authors.txt b/basis/suffix-arrays/authors.txt
new file mode 100755 (executable)
index 0000000..e4a36df
--- /dev/null
+++ b/basis/suffix-arrays/authors.txt
@@ -0,0 +1 @@
+Marc Fauconneau
\ No newline at end of file

diff --git a/basis/suffix-arrays/suffix-arrays-docs.factor b/basis/suffix-arrays/suffix-arrays-docs.factor
new file mode 100755 (executable)
index 0000000..87df272
--- /dev/null
+++ b/basis/suffix-arrays/suffix-arrays-docs.factor
@@ -0,0 +1,45 @@
+! Copyright (C) 2008 Marc Fauconneau.
+! See http://factorcode.org/license.txt for BSD license.
+USING: arrays help.markup help.syntax io.streams.string
+sequences strings math suffix-arrays.private ;
+IN: suffix-arrays
+
+HELP: >suffix-array
+{ $values
+     { "seq" sequence }
+     { "array" array } }
+{ $description "Creates a suffix array from the input sequence.  Suffix arrays are arrays of slices." } ;
+
+HELP: SA{
+{ $description "Creates a new literal suffix array at parse-time." } ;
+
+HELP: suffixes
+{ $values
+     { "string" string }
+     { "suffixes-seq" "a sequence of slices" } }
+{ $description "Returns a sequence of tail slices of the input string." } ;
+
+HELP: from-to
+{ $values
+     { "index" integer } { "begin" sequence } { "suffix-array" "a suffix-array" }
+     { "from/f" "an integer or f" } { "to/f" "an integer or f" } }
+{ $description "Finds the bounds of the suffix array that match the input sequence. A return value of " { $link f } " means that the endpoint is included." }
+{ $notes "Slices are [m,n) and we want (m,n) so we increment." } ;
+
+HELP: query
+{ $values
+     { "begin" sequence } { "suffix-array" "a suffix-array" }
+     { "matches" array } }
+{ $description "Returns a sequence of sequences from the suffix-array that contain the input sequence. An empty array is returned when there are no matches." } ;
+
+ARTICLE: "suffix-arrays" "Suffix arrays"
+"The " { $vocab-link "suffix-arrays" } " vocabulary implements the suffix array data structure for efficient lookup of subsequences. This suffix array implementation is a sorted array of suffixes. Querying it for matches uses binary search for efficiency." $nl
+
+"Creating new suffix arrays:"
+{ $subsection >suffix-array }
+"Literal suffix arrays:"
+{ $subsection POSTPONE: SA{ }
+"Querying suffix arrays:"
+{ $subsection query } ;
+
+ABOUT: "suffix-arrays"

diff --git a/basis/suffix-arrays/suffix-arrays-tests.factor b/basis/suffix-arrays/suffix-arrays-tests.factor
new file mode 100755 (executable)
index 0000000..5149804
--- /dev/null
+++ b/basis/suffix-arrays/suffix-arrays-tests.factor
@@ -0,0 +1,38 @@
+! Copyright (C) 2008 Marc Fauconneau.
+! See http://factorcode.org/license.txt for BSD license.
+USING: tools.test suffix-arrays kernel namespaces sequences ;
+IN: suffix-arrays.tests
+
+! built from [ all-words 10 head [ name>> ] map ]
+[ ] [ 
+     {
+        "run-tests"
+        "must-fail-with"
+        "test-all"
+        "short-effect"
+        "failure"
+        "test"
+        "<failure>"
+        "this-test"
+        "(unit-test)"
+        "unit-test"
+    } >suffix-array "suffix-array" set
+] unit-test
+
+[ t ]
+[ "suffix-array" get "" swap query empty? not ] unit-test
+
+[ { } ]
+[ SA{ } "something" swap query ] unit-test
+
+[ V{ "unit-test" "(unit-test)" } ]
+[ "suffix-array" get "unit-test" swap query ] unit-test
+
+[ t ]
+[ "suffix-array" get "something else" swap query empty? ] unit-test
+
+[ V{ "rofl" } ] [ SA{ "rofl" } "r" swap query ] unit-test
+[ V{ "rofl" } ] [ SA{ "rofl" } "o" swap query ] unit-test
+[ V{ "rofl" } ] [ SA{ "rofl" } "f" swap query ] unit-test
+[ V{ "rofl" } ] [ SA{ "rofl" } "l" swap query ] unit-test
+[ V{ } ] [ SA{ "rofl" } "t" swap query ] unit-test

diff --git a/basis/suffix-arrays/suffix-arrays.factor b/basis/suffix-arrays/suffix-arrays.factor
new file mode 100755 (executable)
index 0000000..b181ba9
--- /dev/null
+++ b/basis/suffix-arrays/suffix-arrays.factor
@@ -0,0 +1,39 @@
+! Copyright (C) 2008 Marc Fauconneau.
+! See http://factorcode.org/license.txt for BSD license.
+USING: parser kernel arrays math accessors sequences
+math.vectors math.order sorting binary-search sets assocs fry ;
+IN: suffix-arrays
+
+<PRIVATE
+: suffixes ( string -- suffixes-seq )
+    dup length [ tail-slice ] with map ;
+
+: prefix<=> ( begin seq -- <=> )
+    [ <=> ] [ swap head? ] 2bi [ drop +eq+ ] when ;
+ 
+: find-index ( begin suffix-array -- index/f )
+    [ prefix<=> ] with search drop ;
+
+: from-to ( index begin suffix-array -- from/f to/f )
+    swap '[ _ head? not ]
+    [ find-last-from drop dup [ 1+ ] when ]
+    [ find-from drop ] 3bi ;
+
+: <funky-slice> ( from/f to/f seq -- slice )
+    [
+        tuck
+        [ drop 0 or ] [ length or ] 2bi*
+        [ min ] keep
+    ] keep <slice> ; inline
+
+PRIVATE>
+
+: >suffix-array ( seq -- array )
+    [ suffixes ] map concat natural-sort ;
+
+: SA{ \ } [ >suffix-array ] parse-literal ; parsing
+
+: query ( begin suffix-array -- matches )
+    2dup find-index dup
+    [ -rot [ from-to ] keep <funky-slice> [ seq>> ] map prune ]
+    [ 3drop { } ] if ;

diff --git a/basis/suffix-arrays/summary.txt b/basis/suffix-arrays/summary.txt
new file mode 100755 (executable)
index 0000000..71eda47
--- /dev/null
+++ b/basis/suffix-arrays/summary.txt
@@ -0,0 +1 @@
+Suffix arrays

diff --git a/basis/suffix-arrays/tags.txt b/basis/suffix-arrays/tags.txt
new file mode 100755 (executable)
index 0000000..42d711b
--- /dev/null
+++ b/basis/suffix-arrays/tags.txt
@@ -0,0 +1 @@
+collections

diff --git a/basis/suffix-arrays/words/words.factor b/basis/suffix-arrays/words/words.factor
new file mode 100755 (executable)
index 0000000..74e2fc2
--- /dev/null
+++ b/basis/suffix-arrays/words/words.factor
@@ -0,0 +1,19 @@
+! Copyright (C) 2008 Marc Fauconneau.\r
+! See http://factorcode.org/license.txt for BSD license.\r
+USING: kernel arrays math accessors sequences math.vectors\r
+math.order sorting binary-search sets assocs fry suffix-arrays ;\r
+IN: suffix-arrays.words\r
+\r
+! to search on word names\r
+\r
+: new-word-sa ( words -- sa )\r
+    [ name>> ] map >suffix-array ;\r
+\r
+: name>word-map ( words -- map )\r
+    dup [ name>> V{ } clone ] H{ } map>assoc\r
+    [ '[ dup name>> _ at push ] each ] keep ;\r
+\r
+: query-word-sa ( map begin sa -- matches ) query '[ _ at ] map concat ;\r
+\r
+! usage example :\r
+! clear all-words 100 head dup name>word-map "test" rot new-word-sa query .\r

diff --git a/extra/suffix-arrays/authors.txt b/extra/suffix-arrays/authors.txt
deleted file mode 100755 (executable)
index e4a36df..0000000
--- a/extra/suffix-arrays/authors.txt
+++ /dev/null
@@ -1 +0,0 @@
-Marc Fauconneau
\ No newline at end of file

diff --git a/extra/suffix-arrays/suffix-arrays-docs.factor b/extra/suffix-arrays/suffix-arrays-docs.factor
deleted file mode 100755 (executable)
index 87df272..0000000
--- a/extra/suffix-arrays/suffix-arrays-docs.factor
+++ /dev/null
@@ -1,45 +0,0 @@
-! Copyright (C) 2008 Marc Fauconneau.
-! See http://factorcode.org/license.txt for BSD license.
-USING: arrays help.markup help.syntax io.streams.string
-sequences strings math suffix-arrays.private ;
-IN: suffix-arrays
-
-HELP: >suffix-array
-{ $values
-     { "seq" sequence }
-     { "array" array } }
-{ $description "Creates a suffix array from the input sequence.  Suffix arrays are arrays of slices." } ;
-
-HELP: SA{
-{ $description "Creates a new literal suffix array at parse-time." } ;
-
-HELP: suffixes
-{ $values
-     { "string" string }
-     { "suffixes-seq" "a sequence of slices" } }
-{ $description "Returns a sequence of tail slices of the input string." } ;
-
-HELP: from-to
-{ $values
-     { "index" integer } { "begin" sequence } { "suffix-array" "a suffix-array" }
-     { "from/f" "an integer or f" } { "to/f" "an integer or f" } }
-{ $description "Finds the bounds of the suffix array that match the input sequence. A return value of " { $link f } " means that the endpoint is included." }
-{ $notes "Slices are [m,n) and we want (m,n) so we increment." } ;
-
-HELP: query
-{ $values
-     { "begin" sequence } { "suffix-array" "a suffix-array" }
-     { "matches" array } }
-{ $description "Returns a sequence of sequences from the suffix-array that contain the input sequence. An empty array is returned when there are no matches." } ;
-
-ARTICLE: "suffix-arrays" "Suffix arrays"
-"The " { $vocab-link "suffix-arrays" } " vocabulary implements the suffix array data structure for efficient lookup of subsequences. This suffix array implementation is a sorted array of suffixes. Querying it for matches uses binary search for efficiency." $nl
-
-"Creating new suffix arrays:"
-{ $subsection >suffix-array }
-"Literal suffix arrays:"
-{ $subsection POSTPONE: SA{ }
-"Querying suffix arrays:"
-{ $subsection query } ;
-
-ABOUT: "suffix-arrays"

diff --git a/extra/suffix-arrays/suffix-arrays-tests.factor b/extra/suffix-arrays/suffix-arrays-tests.factor
deleted file mode 100755 (executable)
index 5149804..0000000
--- a/extra/suffix-arrays/suffix-arrays-tests.factor
+++ /dev/null
@@ -1,38 +0,0 @@
-! Copyright (C) 2008 Marc Fauconneau.
-! See http://factorcode.org/license.txt for BSD license.
-USING: tools.test suffix-arrays kernel namespaces sequences ;
-IN: suffix-arrays.tests
-
-! built from [ all-words 10 head [ name>> ] map ]
-[ ] [ 
-     {
-        "run-tests"
-        "must-fail-with"
-        "test-all"
-        "short-effect"
-        "failure"
-        "test"
-        "<failure>"
-        "this-test"
-        "(unit-test)"
-        "unit-test"
-    } >suffix-array "suffix-array" set
-] unit-test
-
-[ t ]
-[ "suffix-array" get "" swap query empty? not ] unit-test
-
-[ { } ]
-[ SA{ } "something" swap query ] unit-test
-
-[ V{ "unit-test" "(unit-test)" } ]
-[ "suffix-array" get "unit-test" swap query ] unit-test
-
-[ t ]
-[ "suffix-array" get "something else" swap query empty? ] unit-test
-
-[ V{ "rofl" } ] [ SA{ "rofl" } "r" swap query ] unit-test
-[ V{ "rofl" } ] [ SA{ "rofl" } "o" swap query ] unit-test
-[ V{ "rofl" } ] [ SA{ "rofl" } "f" swap query ] unit-test
-[ V{ "rofl" } ] [ SA{ "rofl" } "l" swap query ] unit-test
-[ V{ } ] [ SA{ "rofl" } "t" swap query ] unit-test

diff --git a/extra/suffix-arrays/suffix-arrays.factor b/extra/suffix-arrays/suffix-arrays.factor
deleted file mode 100755 (executable)
index b181ba9..0000000
--- a/extra/suffix-arrays/suffix-arrays.factor
+++ /dev/null
@@ -1,39 +0,0 @@
-! Copyright (C) 2008 Marc Fauconneau.
-! See http://factorcode.org/license.txt for BSD license.
-USING: parser kernel arrays math accessors sequences
-math.vectors math.order sorting binary-search sets assocs fry ;
-IN: suffix-arrays
-
-<PRIVATE
-: suffixes ( string -- suffixes-seq )
-    dup length [ tail-slice ] with map ;
-
-: prefix<=> ( begin seq -- <=> )
-    [ <=> ] [ swap head? ] 2bi [ drop +eq+ ] when ;
- 
-: find-index ( begin suffix-array -- index/f )
-    [ prefix<=> ] with search drop ;
-
-: from-to ( index begin suffix-array -- from/f to/f )
-    swap '[ _ head? not ]
-    [ find-last-from drop dup [ 1+ ] when ]
-    [ find-from drop ] 3bi ;
-
-: <funky-slice> ( from/f to/f seq -- slice )
-    [
-        tuck
-        [ drop 0 or ] [ length or ] 2bi*
-        [ min ] keep
-    ] keep <slice> ; inline
-
-PRIVATE>
-
-: >suffix-array ( seq -- array )
-    [ suffixes ] map concat natural-sort ;
-
-: SA{ \ } [ >suffix-array ] parse-literal ; parsing
-
-: query ( begin suffix-array -- matches )
-    2dup find-index dup
-    [ -rot [ from-to ] keep <funky-slice> [ seq>> ] map prune ]
-    [ 3drop { } ] if ;

diff --git a/extra/suffix-arrays/summary.txt b/extra/suffix-arrays/summary.txt
deleted file mode 100755 (executable)
index 71eda47..0000000
--- a/extra/suffix-arrays/summary.txt
+++ /dev/null
@@ -1 +0,0 @@
-Suffix arrays

diff --git a/extra/suffix-arrays/tags.txt b/extra/suffix-arrays/tags.txt
deleted file mode 100755 (executable)
index 42d711b..0000000
--- a/extra/suffix-arrays/tags.txt
+++ /dev/null
@@ -1 +0,0 @@
-collections

diff --git a/extra/suffix-arrays/words/words.factor b/extra/suffix-arrays/words/words.factor
deleted file mode 100755 (executable)
index 74e2fc2..0000000
--- a/extra/suffix-arrays/words/words.factor
+++ /dev/null
@@ -1,19 +0,0 @@
-! Copyright (C) 2008 Marc Fauconneau.\r
-! See http://factorcode.org/license.txt for BSD license.\r
-USING: kernel arrays math accessors sequences math.vectors\r
-math.order sorting binary-search sets assocs fry suffix-arrays ;\r
-IN: suffix-arrays.words\r
-\r
-! to search on word names\r
-\r
-: new-word-sa ( words -- sa )\r
-    [ name>> ] map >suffix-array ;\r
-\r
-: name>word-map ( words -- map )\r
-    dup [ name>> V{ } clone ] H{ } map>assoc\r
-    [ '[ dup name>> _ at push ] each ] keep ;\r
-\r
-: query-word-sa ( map begin sa -- matches ) query '[ _ at ] map concat ;\r
-\r
-! usage example :\r
-! clear all-words 100 head dup name>word-map "test" rot new-word-sa query .\r