basis/wrap/wrap.factor

   1 USING: kernel sequences math arrays locals fry accessors splitting
   2 make combinators.short-circuit namespaces grouping splitting.monotonic ;
   3 IN: wrap
   4
   5 <PRIVATE
   6
   7 ! black is the text length, white is the whitespace length
   8 TUPLE: word contents black white ;
   9 C: <word> word
  10
  11 : word-length ( word -- n )
  12     [ black>> ] [ white>> ] bi + ;
  13
  14 TUPLE: cons cdr car ; ! This order works out better
  15 C: <cons> cons
  16
  17 : >cons< ( cons -- cdr car )
  18     [ cdr>> ] [ car>> ] bi ;
  19
  20 : list-each ( list quot -- )
  21     over [
  22         [ [ car>> ] dip call ]
  23         [ [ cdr>> ] dip list-each ] 2bi
  24     ] [ 2drop ] if ; inline recursive
  25
  26 : singleton? ( list -- ? )
  27     { [ ] [ cdr>> not ] } 1&& ;
  28
  29 : <singleton> ( elt -- list )
  30     f swap <cons> ;
  31
  32 : list>array ( list -- array )
  33     [ [ , ] list-each ] { } make ;
  34
  35 : lists>arrays ( lists -- arrays )
  36     [ [ list>array , ] list-each ] { } make ;
  37
  38 TUPLE: paragraph lines head-width tail-cost ;
  39 C: <paragraph> paragraph
  40
  41 SYMBOL: line-max
  42 SYMBOL: line-ideal
  43
  44 : deviation ( length -- n )
  45     line-ideal get - sq ;
  46
  47 : top-fits? ( paragraph -- ? )
  48     [ head-width>> ]
  49     [ lines>> singleton? line-ideal line-max ? get ] bi <= ;
  50
  51 : fits? ( paragraph -- ? )
  52     ! Make this not count spaces at end
  53     { [ lines>> car>> singleton? ] [ top-fits? ] } 1|| ;
  54
  55 :: min-by ( seq quot -- elt )
  56     f 1.0/0.0 seq [| key value new |
  57         new quot call :> newvalue
  58         newvalue value < [ new newvalue ] [ key value ] if
  59     ] each drop ; inline
  60
  61 : paragraph-cost ( paragraph -- cost )
  62     [ head-width>> deviation ]
  63     [ tail-cost>> ] bi + ;
  64
  65 : min-cost ( paragraphs -- paragraph )
  66     [ paragraph-cost ] min-by ;
  67
  68 : new-line ( paragraph word -- paragraph )
  69     [ [ lines>> ] [ <singleton> ] bi* <cons> ]
  70     [ nip black>> ]
  71     [ drop paragraph-cost ] 2tri
  72     <paragraph> ;
  73
  74 : glue ( paragraph word -- paragraph )
  75     [ [ lines>> >cons< ] dip <cons> <cons> ]
  76     [ [ head-width>> ] [ word-length ] bi* + ]
  77     [ drop tail-cost>> ] 2tri
  78     <paragraph> ;
  79
  80 : wrap-step ( paragraphs word -- paragraphs )
  81     [ '[ _ glue ] map ]
  82     [ [ min-cost ] dip new-line ]
  83     2bi prefix
  84     [ fits? ] filter ;
  85
  86 : 1paragraph ( word -- paragraph )
  87     [ <singleton> <singleton> ]
  88     [ black>> ] bi
  89     0 <paragraph> ;
  90
  91 : post-process ( paragraph -- array )
  92     lines>> lists>arrays
  93     [ [ contents>> ] map ] map ;
  94
  95 : initialize ( words -- words paragraph )
  96     <reversed> unclip-slice 1paragraph 1array ;
  97
  98 : wrap ( words line-max line-ideal -- paragraph )
  99     [
 100         line-ideal set
 101         line-max set
 102         initialize
 103         [ wrap-step ] reduce
 104         min-cost
 105         post-process
 106     ] with-scope ;
 107
 108 PRIVATE>
 109
 110 TUPLE: element key width break? ;
 111 C: <element> element
 112
 113 <PRIVATE
 114
 115 : elements-length ( elements -- length )
 116     [ width>> ] map sum ;
 117
 118 : make-word ( whites blacks -- word )
 119     [ append ] [ [ elements-length ] bi@ ] 2bi <word> ;
 120
 121 : ?first2 ( seq -- first/f second/f )
 122     [ 0 swap ?nth ]
 123     [ 1 swap ?nth ] bi ;
 124
 125 : split-elements ( seq -- half-words )
 126     [ [ break?>> ] bi@ = ] monotonic-split ;
 127
 128 : ?first-break ( seq -- newseq f/word )
 129     dup first first break?>>
 130     [ unclip-slice f swap make-word ]
 131     [ f ] if ;
 132
 133 : make-words ( seq f/word -- words )
 134     [ 2 <groups> [ ?first2 make-word ] map ] dip
 135     [ prefix ] when* ;
 136
 137 : elements>words ( seq -- newseq )
 138     split-elements ?first-break make-words ;
 139
 140 PRIVATE>
 141
 142 : wrap-elements ( elements line-max line-ideal -- lines )
 143     [ elements>words ] 2dip wrap [ concat ] map ;
 144
 145 <PRIVATE
 146
 147 : split-lines ( string -- words-lines )
 148     string-lines [
 149         " \t" split harvest
 150         [ dup length 1 <word> ] map
 151     ] map ;
 152
 153 : join-words ( wrapped-lines -- lines )
 154     [ " " join ] map ;
 155
 156 : join-lines ( strings -- string )
 157     "\n" join ;
 158
 159 PRIVATE>
 160
 161 : wrap-lines ( lines width -- newlines )
 162     [ split-lines ] dip '[ _ dup wrap join-words ] map concat ;
 163
 164 : wrap-string ( string width -- newstring )
 165     wrap-lines join-lines ;
 166
 167 : wrap-indented-string ( string width indent -- newstring )
 168     [ length - wrap-lines ] keep '[ _ prepend ] map join-lines ;