factor: trim using lists

[factor.git] / extra / math / transforms / bwt / bwt.factor

diff --git a/extra/math/transforms/bwt/bwt.factor b/extra/math/transforms/bwt/bwt.factor
index 0b1340a3fd6220168c4fd977a9b75acd0888a453..3572e083e0abb3878313750c9e2466a01088184a 100644 (file)
--- a/extra/math/transforms/bwt/bwt.factor
+++ b/extra/math/transforms/bwt/bwt.factor
@@ -1,15 +1,17 @@
 ! Copyright (C) 2012 John Benediktsson
 ! See http://factorcode.org/license.txt for BSD license
-USING: arrays fry kernel math sequences sequences.extras
+USING: accessors assocs kernel sequences sequences.rotated
 sorting ;
 IN: math.transforms.bwt
 
-! Inefficient versions of Burrows-Wheeler Transform
+! Semi-efficient versions of Burrows-Wheeler Transform
 
-: bwt ( seq -- newseq )
-    0 suffix all-rotations natural-sort [ last ] map ;
+:: bwt ( seq -- i newseq )
+    seq all-rotations natural-sort
+    [ [ n>> 0 = ] find drop ] keep
+    [ last ] seq map-as ;
 
-: ibwt ( newseq -- seq )
-    [ length [ { } <array> ] keep ] keep
-    '[ _ [ prefix ] 2map natural-sort ] times
-    [ { 0 } tail? ] find nip but-last ;
+: ibwt ( i newseq -- seq )
+    [ length ]
+    [ <enumerated> sort-values '[ _ nth first2 ] ]
+    [ replicate-as ] tri nip ;