Function textwrap::wrap_algorithms::wrap_first_fit

pub fn wrap_first_fit<'a, 'b, T: Fragment>(
    fragments: &'a [T], 
    line_widths: &'b [usize]
) -> Vec<&'a [T]>

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;
use textwrap::word_separators::{AsciiSpace, 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 = AsciiSpace.find_words(text).collect::<Vec<_>>();
assert_eq!(lines_to_strings(wrap_algorithms::wrap_first_fit(&words, &[15])),
           vec!["These few words",
                "will",  // <-- short line
                "unfortunately",
                "not wrap",
                "nicely."]);

// We can avoid the short line if we look ahead:
#[cfg(feature = "smawk")]
assert_eq!(lines_to_strings(wrap_algorithms::wrap_optimal_fit(&words, &[15])),
           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::wrap_algorithms::wrap_first_fit;
use textwrap::core::{Fragment, Word};

#[derive(Debug)]
struct Task<'a> {
    name: &'a str,
    hours: usize,   // Time needed to complete task.
    sweep: usize,   // Time needed for a quick sweep after task during the day.
    cleanup: usize, // Time needed for full cleanup if day ends with this task.
}

impl Fragment for Task<'_> {
    fn width(&self) -> usize { self.hours }
    fn whitespace_width(&self) -> usize { self.sweep }
    fn penalty_width(&self) -> usize { self.cleanup }
}

// The morning tasks
let tasks = vec![
    Task { name: "Foundation",  hours: 4, sweep: 2, cleanup: 3 },
    Task { name: "Framing",     hours: 3, sweep: 1, cleanup: 2 },
    Task { name: "Plumbing",    hours: 2, sweep: 2, cleanup: 2 },
    Task { name: "Electrical",  hours: 2, sweep: 1, cleanup: 2 },
    Task { name: "Insulation",  hours: 2, sweep: 1, cleanup: 2 },
    Task { name: "Drywall",     hours: 3, sweep: 1, cleanup: 2 },
    Task { name: "Floors",      hours: 3, sweep: 1, cleanup: 2 },
    Task { name: "Countertops", hours: 1, sweep: 1, cleanup: 2 },
    Task { name: "Bathrooms",   hours: 2, sweep: 1, cleanup: 2 },
];

// 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: usize) -> Vec<(usize, 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: usize = 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),
    [
        (7, vec!["Foundation"]),
        (8, vec!["Framing", "Plumbing"]),
        (7, vec!["Electrical", "Insulation"]),
        (5, vec!["Drywall"]),
        (7, vec!["Floors", "Countertops"]),
        (4, vec!["Bathrooms"]),
    ]
);

// With two crews working in shifts, 16 hours a day:
assert_eq!(
    assign_days(&tasks, 16),
    [
        (14, vec!["Foundation", "Framing", "Plumbing"]),
        (15, vec!["Electrical", "Insulation", "Drywall", "Floors"]),
        (6, vec!["Countertops", "Bathrooms"]),
    ]
);

Apologies to anyone who actually knows how to build a house and knows how long each step takes :-)