summaryrefslogtreecommitdiffstats
path: root/vendor/textwrap/src/wrap_algorithms.rs
blob: 5ca49c3352db1997889e18fff4ec0dadffbf26d3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
//! Word wrapping algorithms.
//!
//! After a text has been broken into words (or [`Fragment`]s), one
//! now has to decide how to break the fragments into lines. The
//! simplest algorithm for this is implemented by [`wrap_first_fit`]:
//! it uses no look-ahead and simply adds fragments to the line as
//! long as they fit. However, this can lead to poor line breaks if a
//! large fragment almost-but-not-quite fits on a line. When that
//! happens, the fragment is moved to the next line and it will leave
//! behind a large gap. A more advanced algorithm, implemented by
//! [`wrap_optimal_fit`], will take this into account. The optimal-fit
//! algorithm considers all possible line breaks and will attempt to
//! minimize the gaps left behind by overly short lines.
//!
//! While both algorithms run in linear time, the first-fit algorithm
//! is about 4 times faster than the optimal-fit algorithm.

#[cfg(feature = "smawk")]
mod optimal_fit;
#[cfg(feature = "smawk")]
pub use optimal_fit::{wrap_optimal_fit, OverflowError, Penalties};

use crate::core::{Fragment, Word};

/// Describes how to wrap words into lines.
///
/// The simplest approach is to wrap words one word at a time and
/// accept the first way of wrapping which fit
/// ([`WrapAlgorithm::FirstFit`]). If the `smawk` Cargo feature is
/// enabled, a more complex algorithm is available which will look at
/// an entire paragraph at a time in order to find optimal line breaks
/// ([`WrapAlgorithm::OptimalFit`]).
#[derive(Clone, Copy)]
pub enum WrapAlgorithm {
    /// Wrap words using a fast and simple algorithm.
    ///
    /// This algorithm uses no look-ahead when finding line breaks.
    /// Implemented by [`wrap_first_fit`], please see that function for
    /// details and examples.
    FirstFit,

    /// Wrap words using an advanced algorithm with look-ahead.
    ///
    /// This wrapping algorithm considers the entire paragraph to find
    /// optimal line breaks. When wrapping text, "penalties" are
    /// assigned to line breaks based on the gaps left at the end of
    /// lines. See [`Penalties`] for details.
    ///
    /// The underlying wrapping algorithm is implemented by
    /// [`wrap_optimal_fit`], please see that function for examples.
    ///
    /// **Note:** Only available when the `smawk` Cargo feature is
    /// enabled.
    #[cfg(feature = "smawk")]
    OptimalFit(Penalties),

    /// Custom wrapping function.
    ///
    /// Use this if you want to implement your own wrapping algorithm.
    /// The function can freely decide how to turn a slice of
    /// [`Word`]s into lines.
    ///
    /// # Example
    ///
    /// ```
    /// use textwrap::core::Word;
    /// use textwrap::{wrap, Options, WrapAlgorithm};
    ///
    /// fn stair<'a, 'b>(words: &'b [Word<'a>], _: &'b [usize]) -> Vec<&'b [Word<'a>]> {
    ///     let mut lines = Vec::new();
    ///     let mut step = 1;
    ///     let mut start_idx = 0;
    ///     while start_idx + step <= words.len() {
    ///       lines.push(&words[start_idx .. start_idx+step]);
    ///       start_idx += step;
    ///       step += 1;
    ///     }
    ///     lines
    /// }
    ///
    /// let options = Options::new(10).wrap_algorithm(WrapAlgorithm::Custom(stair));
    /// assert_eq!(wrap("First, second, third, fourth, fifth, sixth", options),
    ///            vec!["First,",
    ///                 "second, third,",
    ///                 "fourth, fifth, sixth"]);
    /// ```
    Custom(for<'a, 'b> fn(words: &'b [Word<'a>], line_widths: &'b [usize]) -> Vec<&'b [Word<'a>]>),
}

impl std::fmt::Debug for WrapAlgorithm {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            WrapAlgorithm::FirstFit => f.write_str("FirstFit"),
            #[cfg(feature = "smawk")]
            WrapAlgorithm::OptimalFit(penalties) => write!(f, "OptimalFit({:?})", penalties),
            WrapAlgorithm::Custom(_) => f.write_str("Custom(...)"),
        }
    }
}

impl WrapAlgorithm {
    /// Create new wrap algorithm.
    ///
    /// The best wrapping algorithm is used by default, i.e.,
    /// [`WrapAlgorithm::OptimalFit`] if available, otherwise
    /// [`WrapAlgorithm::FirstFit`].
    pub const fn new() -> Self {
        #[cfg(not(feature = "smawk"))]
        {
            WrapAlgorithm::FirstFit
        }

        #[cfg(feature = "smawk")]
        {
            WrapAlgorithm::new_optimal_fit()
        }
    }

    /// New [`WrapAlgorithm::OptimalFit`] with default penalties. This
    /// works well for monospace text.
    ///
    /// **Note:** Only available when the `smawk` Cargo feature is
    /// enabled.
    #[cfg(feature = "smawk")]
    pub const fn new_optimal_fit() -> Self {
        WrapAlgorithm::OptimalFit(Penalties::new())
    }

    /// Wrap words according to line widths.
    ///
    /// The `line_widths` slice gives the target line width for each
    /// line (the last slice element is repeated as necessary). This
    /// can be used to implement hanging indentation.
    #[inline]
    pub fn wrap<'a, 'b>(
        &self,
        words: &'b [Word<'a>],
        line_widths: &'b [usize],
    ) -> Vec<&'b [Word<'a>]> {
        // Every integer up to 2u64.pow(f64::MANTISSA_DIGITS) = 2**53
        // = 9_007_199_254_740_992 can be represented without loss by
        // a f64. Larger line widths will be rounded to the nearest
        // representable number.
        let f64_line_widths = line_widths.iter().map(|w| *w as f64).collect::<Vec<_>>();

        match self {
            WrapAlgorithm::FirstFit => wrap_first_fit(words, &f64_line_widths),

            #[cfg(feature = "smawk")]
            WrapAlgorithm::OptimalFit(penalties) => {
                // The computation cannnot overflow when the line
                // widths are restricted to usize.
                wrap_optimal_fit(words, &f64_line_widths, penalties).unwrap()
            }

            WrapAlgorithm::Custom(func) => func(words, line_widths),
        }
    }
}

impl Default for WrapAlgorithm {
    fn default() -> Self {
        WrapAlgorithm::new()
    }
}

/// Wrap abstract fragments into lines with a first-fit algorithm.
///
/// The `line_widths` slice gives the target line width for each line
/// (the last slice element is repeated as necessary). This can be
/// used to implement hanging indentation.
///
/// The fragments must already have been split into the desired
/// widths, this function will not (and cannot) attempt to split them
/// further when arranging them into lines.
///
/// # First-Fit Algorithm
///
/// This implements a simple “greedy” algorithm: accumulate fragments
/// one by one and when a fragment no longer fits, start a new line.
/// There is no look-ahead, we simply take first fit of the fragments
/// we find.
///
/// While fast and predictable, this algorithm can produce poor line
/// breaks when a long fragment is moved to a new line, leaving behind
/// a large gap:
///
/// ```
/// use textwrap::core::Word;
/// use textwrap::wrap_algorithms::wrap_first_fit;
/// use textwrap::WordSeparator;
///
/// // Helper to convert wrapped lines to a Vec<String>.
/// fn lines_to_strings(lines: Vec<&[Word<'_>]>) -> Vec<String> {
///     lines.iter().map(|line| {
///         line.iter().map(|word| &**word).collect::<Vec<_>>().join(" ")
///     }).collect::<Vec<_>>()
/// }
///
/// let text = "These few words will unfortunately not wrap nicely.";
/// let words = WordSeparator::AsciiSpace.find_words(text).collect::<Vec<_>>();
/// assert_eq!(lines_to_strings(wrap_first_fit(&words, &[15.0])),
///            vec!["These few words",
///                 "will",  // <-- short line
///                 "unfortunately",
///                 "not wrap",
///                 "nicely."]);
///
/// // We can avoid the short line if we look ahead:
/// #[cfg(feature = "smawk")]
/// use textwrap::wrap_algorithms::{wrap_optimal_fit, Penalties};
/// #[cfg(feature = "smawk")]
/// assert_eq!(lines_to_strings(wrap_optimal_fit(&words, &[15.0], &Penalties::new()).unwrap()),
///            vec!["These few",
///                 "words will",
///                 "unfortunately",
///                 "not wrap",
///                 "nicely."]);
/// ```
///
/// The [`wrap_optimal_fit`] function was used above to get better
/// line breaks. It uses an advanced algorithm which tries to avoid
/// short lines. This function is about 4 times faster than
/// [`wrap_optimal_fit`].
///
/// # Examples
///
/// Imagine you're building a house site and you have a number of
/// tasks you need to execute. Things like pour foundation, complete
/// framing, install plumbing, electric cabling, install insulation.
///
/// The construction workers can only work during daytime, so they
/// need to pack up everything at night. Because they need to secure
/// their tools and move machines back to the garage, this process
/// takes much more time than the time it would take them to simply
/// switch to another task.
///
/// You would like to make a list of tasks to execute every day based
/// on your estimates. You can model this with a program like this:
///
/// ```
/// use textwrap::core::{Fragment, Word};
/// use textwrap::wrap_algorithms::wrap_first_fit;
///
/// #[derive(Debug)]
/// struct Task<'a> {
///     name: &'a str,
///     hours: f64,   // Time needed to complete task.
///     sweep: f64,   // Time needed for a quick sweep after task during the day.
///     cleanup: f64, // Time needed for full cleanup if day ends with this task.
/// }
///
/// impl Fragment for Task<'_> {
///     fn width(&self) -> f64 { self.hours }
///     fn whitespace_width(&self) -> f64 { self.sweep }
///     fn penalty_width(&self) -> f64 { self.cleanup }
/// }
///
/// // The morning tasks
/// let tasks = vec![
///     Task { name: "Foundation",  hours: 4.0, sweep: 2.0, cleanup: 3.0 },
///     Task { name: "Framing",     hours: 3.0, sweep: 1.0, cleanup: 2.0 },
///     Task { name: "Plumbing",    hours: 2.0, sweep: 2.0, cleanup: 2.0 },
///     Task { name: "Electrical",  hours: 2.0, sweep: 1.0, cleanup: 2.0 },
///     Task { name: "Insulation",  hours: 2.0, sweep: 1.0, cleanup: 2.0 },
///     Task { name: "Drywall",     hours: 3.0, sweep: 1.0, cleanup: 2.0 },
///     Task { name: "Floors",      hours: 3.0, sweep: 1.0, cleanup: 2.0 },
///     Task { name: "Countertops", hours: 1.0, sweep: 1.0, cleanup: 2.0 },
///     Task { name: "Bathrooms",   hours: 2.0, sweep: 1.0, cleanup: 2.0 },
/// ];
///
/// // Fill tasks into days, taking `day_length` into account. The
/// // output shows the hours worked per day along with the names of
/// // the tasks for that day.
/// fn assign_days<'a>(tasks: &[Task<'a>], day_length: f64) -> Vec<(f64, Vec<&'a str>)> {
///     let mut days = Vec::new();
///     // Assign tasks to days. The assignment is a vector of slices,
///     // with a slice per day.
///     let assigned_days: Vec<&[Task<'a>]> = wrap_first_fit(&tasks, &[day_length]);
///     for day in assigned_days.iter() {
///         let last = day.last().unwrap();
///         let work_hours: f64 = day.iter().map(|t| t.hours + t.sweep).sum();
///         let names = day.iter().map(|t| t.name).collect::<Vec<_>>();
///         days.push((work_hours - last.sweep + last.cleanup, names));
///     }
///     days
/// }
///
/// // With a single crew working 8 hours a day:
/// assert_eq!(
///     assign_days(&tasks, 8.0),
///     [
///         (7.0, vec!["Foundation"]),
///         (8.0, vec!["Framing", "Plumbing"]),
///         (7.0, vec!["Electrical", "Insulation"]),
///         (5.0, vec!["Drywall"]),
///         (7.0, vec!["Floors", "Countertops"]),
///         (4.0, vec!["Bathrooms"]),
///     ]
/// );
///
/// // With two crews working in shifts, 16 hours a day:
/// assert_eq!(
///     assign_days(&tasks, 16.0),
///     [
///         (14.0, vec!["Foundation", "Framing", "Plumbing"]),
///         (15.0, vec!["Electrical", "Insulation", "Drywall", "Floors"]),
///         (6.0, vec!["Countertops", "Bathrooms"]),
///     ]
/// );
/// ```
///
/// Apologies to anyone who actually knows how to build a house and
/// knows how long each step takes :-)
pub fn wrap_first_fit<'a, 'b, T: Fragment>(
    fragments: &'a [T],
    line_widths: &'b [f64],
) -> Vec<&'a [T]> {
    // The final line width is used for all remaining lines.
    let default_line_width = line_widths.last().copied().unwrap_or(0.0);
    let mut lines = Vec::new();
    let mut start = 0;
    let mut width = 0.0;

    for (idx, fragment) in fragments.iter().enumerate() {
        let line_width = line_widths
            .get(lines.len())
            .copied()
            .unwrap_or(default_line_width);
        if width + fragment.width() + fragment.penalty_width() > line_width && idx > start {
            lines.push(&fragments[start..idx]);
            start = idx;
            width = 0.0;
        }
        width += fragment.width() + fragment.whitespace_width();
    }
    lines.push(&fragments[start..]);
    lines
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Debug, PartialEq)]
    struct Word(f64);

    #[rustfmt::skip]
    impl Fragment for Word {
        fn width(&self) -> f64 { self.0 }
        fn whitespace_width(&self) -> f64 { 1.0 }
        fn penalty_width(&self) -> f64 { 0.0 }
    }

    #[test]
    fn wrap_string_longer_than_f64() {
        let words = vec![
            Word(1e307),
            Word(2e307),
            Word(3e307),
            Word(4e307),
            Word(5e307),
            Word(6e307),
        ];
        // Wrap at just under f64::MAX (~19e307). The tiny
        // whitespace_widths disappear because of loss of precision.
        assert_eq!(
            wrap_first_fit(&words, &[15e307]),
            &[
                vec![
                    Word(1e307),
                    Word(2e307),
                    Word(3e307),
                    Word(4e307),
                    Word(5e307)
                ],
                vec![Word(6e307)]
            ]
        );
    }
}