third_party/rust/textwrap/src/wrap_algorithms.rs

   1 //! Word wrapping algorithms.
   2 //!
   3 //! After a text has been broken into words (or [`Fragment`]s), one
   4 //! now has to decide how to break the fragments into lines. The
   5 //! simplest algorithm for this is implemented by
   6 //! [`wrap_first_fit()`]: it uses no look-ahead and simply adds
   7 //! fragments to the line as long as they fit. However, this can lead
   8 //! to poor line breaks if a large fragment almost-but-not-quite fits
   9 //! on a line. When that happens, the fragment is moved to the next
  10 //! line and it will leave behind a large gap.
  11 //!
  12 //! A more advanced algorithm, implemented by [`wrap_optimal_fit()`],
  13 //! will take this into account. The optimal-fit algorithm considers
  14 //! all possible line breaks and will attempt to minimize the gaps
  15 //! left behind by overly short lines.
  16 //!
  17 //! While both algorithms run in linear time, the first-fit algorithm
  18 //! is about 4 times faster than the optimal-fit algorithm.
  19
  20 #[cfg(feature = "smawk")]
  21 mod optimal_fit;
  22 #[cfg(feature = "smawk")]
  23 pub use optimal_fit::{wrap_optimal_fit, OverflowError, Penalties};
  24
  25 use crate::core::{Fragment, Word};
  26
  27 /// Describes how to wrap words into lines.
  28 ///
  29 /// The simplest approach is to wrap words one word at a time and
  30 /// accept the first way of wrapping which fit
  31 /// ([`WrapAlgorithm::FirstFit`]). If the `smawk` Cargo feature is
  32 /// enabled, a more complex algorithm is available which will look at
  33 /// an entire paragraph at a time in order to find optimal line breaks
  34 /// ([`WrapAlgorithm::OptimalFit`]).
  35 #[derive(Clone, Copy)]
  36 pub enum WrapAlgorithm {
  37     /// Wrap words using a fast and simple algorithm.
  38     ///
  39     /// This algorithm uses no look-ahead when finding line breaks.
  40     /// Implemented by [`wrap_first_fit()`], please see that function
  41     /// for details and examples.
  42     FirstFit,
  43
  44     /// Wrap words using an advanced algorithm with look-ahead.
  45     ///
  46     /// This wrapping algorithm considers the entire paragraph to find
  47     /// optimal line breaks. When wrapping text, "penalties" are
  48     /// assigned to line breaks based on the gaps left at the end of
  49     /// lines. See [`Penalties`] for details.
  50     ///
  51     /// The underlying wrapping algorithm is implemented by
  52     /// [`wrap_optimal_fit()`], please see that function for examples.
  53     ///
  54     /// **Note:** Only available when the `smawk` Cargo feature is
  55     /// enabled.
  56     #[cfg(feature = "smawk")]
  57     OptimalFit(Penalties),
  58
  59     /// Custom wrapping function.
  60     ///
  61     /// Use this if you want to implement your own wrapping algorithm.
  62     /// The function can freely decide how to turn a slice of
  63     /// [`Word`]s into lines.
  64     ///
  65     /// # Example
  66     ///
  67     /// ```
  68     /// use textwrap::core::Word;
  69     /// use textwrap::{wrap, Options, WrapAlgorithm};
  70     ///
  71     /// fn stair<'a, 'b>(words: &'b [Word<'a>], _: &'b [usize]) -> Vec<&'b [Word<'a>]> {
  72     ///     let mut lines = Vec::new();
  73     ///     let mut step = 1;
  74     ///     let mut start_idx = 0;
  75     ///     while start_idx + step <= words.len() {
  76     ///       lines.push(&words[start_idx .. start_idx+step]);
  77     ///       start_idx += step;
  78     ///       step += 1;
  79     ///     }
  80     ///     lines
  81     /// }
  82     ///
  83     /// let options = Options::new(10).wrap_algorithm(WrapAlgorithm::Custom(stair));
  84     /// assert_eq!(wrap("First, second, third, fourth, fifth, sixth", options),
  85     ///            vec!["First,",
  86     ///                 "second, third,",
  87     ///                 "fourth, fifth, sixth"]);
  88     /// ```
  89     Custom(for<'a, 'b> fn(words: &'b [Word<'a>], line_widths: &'b [usize]) -> Vec<&'b [Word<'a>]>),
  90 }
  91
  92 impl PartialEq for WrapAlgorithm {
  93     /// Compare two wrap algorithms.
  94     ///
  95     /// ```
  96     /// use textwrap::WrapAlgorithm;
  97     ///
  98     /// assert_eq!(WrapAlgorithm::FirstFit, WrapAlgorithm::FirstFit);
  99     /// #[cfg(feature = "smawk")] {
 100     ///     assert_eq!(WrapAlgorithm::new_optimal_fit(), WrapAlgorithm::new_optimal_fit());
 101     /// }
 102     /// ```
 103     ///
 104     /// Note that `WrapAlgorithm::Custom` values never compare equal:
 105     ///
 106     /// ```
 107     /// use textwrap::WrapAlgorithm;
 108     ///
 109     /// assert_ne!(WrapAlgorithm::Custom(|words, line_widths| vec![words]),
 110     ///            WrapAlgorithm::Custom(|words, line_widths| vec![words]));
 111     /// ```
 112     fn eq(&self, other: &Self) -> bool {
 113         match (self, other) {
 114             (WrapAlgorithm::FirstFit, WrapAlgorithm::FirstFit) => true,
 115             #[cfg(feature = "smawk")]
 116             (WrapAlgorithm::OptimalFit(a), WrapAlgorithm::OptimalFit(b)) => a == b,
 117             (_, _) => false,
 118         }
 119     }
 120 }
 121
 122 impl std::fmt::Debug for WrapAlgorithm {
 123     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 124         match self {
 125             WrapAlgorithm::FirstFit => f.write_str("FirstFit"),
 126             #[cfg(feature = "smawk")]
 127             WrapAlgorithm::OptimalFit(penalties) => write!(f, "OptimalFit({:?})", penalties),
 128             WrapAlgorithm::Custom(_) => f.write_str("Custom(...)"),
 129         }
 130     }
 131 }
 132
 133 impl WrapAlgorithm {
 134     /// Create new wrap algorithm.
 135     ///
 136     /// The best wrapping algorithm is used by default, i.e.,
 137     /// [`WrapAlgorithm::OptimalFit`] if available, otherwise
 138     /// [`WrapAlgorithm::FirstFit`].
 139     pub const fn new() -> Self {
 140         #[cfg(not(feature = "smawk"))]
 141         {
 142             WrapAlgorithm::FirstFit
 143         }
 144
 145         #[cfg(feature = "smawk")]
 146         {
 147             WrapAlgorithm::new_optimal_fit()
 148         }
 149     }
 150
 151     /// New [`WrapAlgorithm::OptimalFit`] with default penalties. This
 152     /// works well for monospace text.
 153     ///
 154     /// **Note:** Only available when the `smawk` Cargo feature is
 155     /// enabled.
 156     #[cfg(feature = "smawk")]
 157     pub const fn new_optimal_fit() -> Self {
 158         WrapAlgorithm::OptimalFit(Penalties::new())
 159     }
 160
 161     /// Wrap words according to line widths.
 162     ///
 163     /// The `line_widths` slice gives the target line width for each
 164     /// line (the last slice element is repeated as necessary). This
 165     /// can be used to implement hanging indentation.
 166     #[inline]
 167     pub fn wrap<'a, 'b>(
 168         &self,
 169         words: &'b [Word<'a>],
 170         line_widths: &'b [usize],
 171     ) -> Vec<&'b [Word<'a>]> {
 172         // Every integer up to 2u64.pow(f64::MANTISSA_DIGITS) = 2**53
 173         // = 9_007_199_254_740_992 can be represented without loss by
 174         // a f64. Larger line widths will be rounded to the nearest
 175         // representable number.
 176         let f64_line_widths = line_widths.iter().map(|w| *w as f64).collect::<Vec<_>>();
 177
 178         match self {
 179             WrapAlgorithm::FirstFit => wrap_first_fit(words, &f64_line_widths),
 180
 181             #[cfg(feature = "smawk")]
 182             WrapAlgorithm::OptimalFit(penalties) => {
 183                 // The computation cannot overflow when the line
 184                 // widths are restricted to usize.
 185                 wrap_optimal_fit(words, &f64_line_widths, penalties).unwrap()
 186             }
 187
 188             WrapAlgorithm::Custom(func) => func(words, line_widths),
 189         }
 190     }
 191 }
 192
 193 impl Default for WrapAlgorithm {
 194     fn default() -> Self {
 195         WrapAlgorithm::new()
 196     }
 197 }
 198
 199 /// Wrap abstract fragments into lines with a first-fit algorithm.
 200 ///
 201 /// The `line_widths` slice gives the target line width for each line
 202 /// (the last slice element is repeated as necessary). This can be
 203 /// used to implement hanging indentation.
 204 ///
 205 /// The fragments must already have been split into the desired
 206 /// widths, this function will not (and cannot) attempt to split them
 207 /// further when arranging them into lines.
 208 ///
 209 /// # First-Fit Algorithm
 210 ///
 211 /// This implements a simple “greedy” algorithm: accumulate fragments
 212 /// one by one and when a fragment no longer fits, start a new line.
 213 /// There is no look-ahead, we simply take first fit of the fragments
 214 /// we find.
 215 ///
 216 /// While fast and predictable, this algorithm can produce poor line
 217 /// breaks when a long fragment is moved to a new line, leaving behind
 218 /// a large gap:
 219 ///
 220 /// ```
 221 /// use textwrap::core::Word;
 222 /// use textwrap::wrap_algorithms::wrap_first_fit;
 223 /// use textwrap::WordSeparator;
 224 ///
 225 /// // Helper to convert wrapped lines to a Vec<String>.
 226 /// fn lines_to_strings(lines: Vec<&[Word<'_>]>) -> Vec<String> {
 227 ///     lines.iter().map(|line| {
 228 ///         line.iter().map(|word| &**word).collect::<Vec<_>>().join(" ")
 229 ///     }).collect::<Vec<_>>()
 230 /// }
 231 ///
 232 /// let text = "These few words will unfortunately not wrap nicely.";
 233 /// let words = WordSeparator::AsciiSpace.find_words(text).collect::<Vec<_>>();
 234 /// assert_eq!(lines_to_strings(wrap_first_fit(&words, &[15.0])),
 235 ///            vec!["These few words",
 236 ///                 "will",  // <-- short line
 237 ///                 "unfortunately",
 238 ///                 "not wrap",
 239 ///                 "nicely."]);
 240 ///
 241 /// // We can avoid the short line if we look ahead:
 242 /// #[cfg(feature = "smawk")]
 243 /// use textwrap::wrap_algorithms::{wrap_optimal_fit, Penalties};
 244 /// #[cfg(feature = "smawk")]
 245 /// assert_eq!(lines_to_strings(wrap_optimal_fit(&words, &[15.0], &Penalties::new()).unwrap()),
 246 ///            vec!["These few",
 247 ///                 "words will",
 248 ///                 "unfortunately",
 249 ///                 "not wrap",
 250 ///                 "nicely."]);
 251 /// ```
 252 ///
 253 /// The [`wrap_optimal_fit()`] function was used above to get better
 254 /// line breaks. It uses an advanced algorithm which tries to avoid
 255 /// short lines. This function is about 4 times faster than
 256 /// [`wrap_optimal_fit()`].
 257 ///
 258 /// # Examples
 259 ///
 260 /// Imagine you're building a house site and you have a number of
 261 /// tasks you need to execute. Things like pour foundation, complete
 262 /// framing, install plumbing, electric cabling, install insulation.
 263 ///
 264 /// The construction workers can only work during daytime, so they
 265 /// need to pack up everything at night. Because they need to secure
 266 /// their tools and move machines back to the garage, this process
 267 /// takes much more time than the time it would take them to simply
 268 /// switch to another task.
 269 ///
 270 /// You would like to make a list of tasks to execute every day based
 271 /// on your estimates. You can model this with a program like this:
 272 ///
 273 /// ```
 274 /// use textwrap::core::{Fragment, Word};
 275 /// use textwrap::wrap_algorithms::wrap_first_fit;
 276 ///
 277 /// #[derive(Debug)]
 278 /// struct Task<'a> {
 279 ///     name: &'a str,
 280 ///     hours: f64,   // Time needed to complete task.
 281 ///     sweep: f64,   // Time needed for a quick sweep after task during the day.
 282 ///     cleanup: f64, // Time needed for full cleanup if day ends with this task.
 283 /// }
 284 ///
 285 /// impl Fragment for Task<'_> {
 286 ///     fn width(&self) -> f64 { self.hours }
 287 ///     fn whitespace_width(&self) -> f64 { self.sweep }
 288 ///     fn penalty_width(&self) -> f64 { self.cleanup }
 289 /// }
 290 ///
 291 /// // The morning tasks
 292 /// let tasks = vec![
 293 ///     Task { name: "Foundation",  hours: 4.0, sweep: 2.0, cleanup: 3.0 },
 294 ///     Task { name: "Framing",     hours: 3.0, sweep: 1.0, cleanup: 2.0 },
 295 ///     Task { name: "Plumbing",    hours: 2.0, sweep: 2.0, cleanup: 2.0 },
 296 ///     Task { name: "Electrical",  hours: 2.0, sweep: 1.0, cleanup: 2.0 },
 297 ///     Task { name: "Insulation",  hours: 2.0, sweep: 1.0, cleanup: 2.0 },
 298 ///     Task { name: "Drywall",     hours: 3.0, sweep: 1.0, cleanup: 2.0 },
 299 ///     Task { name: "Floors",      hours: 3.0, sweep: 1.0, cleanup: 2.0 },
 300 ///     Task { name: "Countertops", hours: 1.0, sweep: 1.0, cleanup: 2.0 },
 301 ///     Task { name: "Bathrooms",   hours: 2.0, sweep: 1.0, cleanup: 2.0 },
 302 /// ];
 303 ///
 304 /// // Fill tasks into days, taking `day_length` into account. The
 305 /// // output shows the hours worked per day along with the names of
 306 /// // the tasks for that day.
 307 /// fn assign_days<'a>(tasks: &[Task<'a>], day_length: f64) -> Vec<(f64, Vec<&'a str>)> {
 308 ///     let mut days = Vec::new();
 309 ///     // Assign tasks to days. The assignment is a vector of slices,
 310 ///     // with a slice per day.
 311 ///     let assigned_days: Vec<&[Task<'a>]> = wrap_first_fit(&tasks, &[day_length]);
 312 ///     for day in assigned_days.iter() {
 313 ///         let last = day.last().unwrap();
 314 ///         let work_hours: f64 = day.iter().map(|t| t.hours + t.sweep).sum();
 315 ///         let names = day.iter().map(|t| t.name).collect::<Vec<_>>();
 316 ///         days.push((work_hours - last.sweep + last.cleanup, names));
 317 ///     }
 318 ///     days
 319 /// }
 320 ///
 321 /// // With a single crew working 8 hours a day:
 322 /// assert_eq!(
 323 ///     assign_days(&tasks, 8.0),
 324 ///     [
 325 ///         (7.0, vec!["Foundation"]),
 326 ///         (8.0, vec!["Framing", "Plumbing"]),
 327 ///         (7.0, vec!["Electrical", "Insulation"]),
 328 ///         (5.0, vec!["Drywall"]),
 329 ///         (7.0, vec!["Floors", "Countertops"]),
 330 ///         (4.0, vec!["Bathrooms"]),
 331 ///     ]
 332 /// );
 333 ///
 334 /// // With two crews working in shifts, 16 hours a day:
 335 /// assert_eq!(
 336 ///     assign_days(&tasks, 16.0),
 337 ///     [
 338 ///         (14.0, vec!["Foundation", "Framing", "Plumbing"]),
 339 ///         (15.0, vec!["Electrical", "Insulation", "Drywall", "Floors"]),
 340 ///         (6.0, vec!["Countertops", "Bathrooms"]),
 341 ///     ]
 342 /// );
 343 /// ```
 344 ///
 345 /// Apologies to anyone who actually knows how to build a house and
 346 /// knows how long each step takes :-)
 347 pub fn wrap_first_fit<'a, T: Fragment>(
 348     fragments: &'a [T],
 349     line_widths: &[f64],
 350 ) -> Vec<&'a [T]> {
 351     // The final line width is used for all remaining lines.
 352     let default_line_width = line_widths.last().copied().unwrap_or(0.0);
 353     let mut lines = Vec::new();
 354     let mut start = 0;
 355     let mut width = 0.0;
 356
 357     for (idx, fragment) in fragments.iter().enumerate() {
 358         let line_width = line_widths
 359             .get(lines.len())
 360             .copied()
 361             .unwrap_or(default_line_width);
 362         if width + fragment.width() + fragment.penalty_width() > line_width && idx > start {
 363             lines.push(&fragments[start..idx]);
 364             start = idx;
 365             width = 0.0;
 366         }
 367         width += fragment.width() + fragment.whitespace_width();
 368     }
 369     lines.push(&fragments[start..]);
 370     lines
 371 }
 372
 373 #[cfg(test)]
 374 mod tests {
 375     use super::*;
 376
 377     #[derive(Debug, PartialEq)]
 378     struct Word(f64);
 379
 380     #[rustfmt::skip]
 381     impl Fragment for Word {
 382         fn width(&self) -> f64 { self.0 }
 383         fn whitespace_width(&self) -> f64 { 1.0 }
 384         fn penalty_width(&self) -> f64 { 0.0 }
 385     }
 386
 387     #[test]
 388     fn wrap_string_longer_than_f64() {
 389         let words = vec![
 390             Word(1e307),
 391             Word(2e307),
 392             Word(3e307),
 393             Word(4e307),
 394             Word(5e307),
 395             Word(6e307),
 396         ];
 397         // Wrap at just under f64::MAX (~19e307). The tiny
 398         // whitespace_widths disappear because of loss of precision.
 399         assert_eq!(
 400             wrap_first_fit(&words, &[15e307]),
 401             &[
 402                 vec![
 403                     Word(1e307),
 404                     Word(2e307),
 405                     Word(3e307),
 406                     Word(4e307),
 407                     Word(5e307)
 408                 ],
 409                 vec![Word(6e307)]
 410             ]
 411         );
 412     }
 413 }